数据结构教案C语言版.docx

课程教案课程名称： 数据构造 授课老师：学习对象：任课时间：一、学生状况分析数据构造是计算机专业的一门核心专业课程。学生在前期的学习中已经学习了C语言程序设计课程。通过本课程学习使学生对进步编写程序的实力以及解决实际问题的实力。二、课程教学目的数据构造是计算机学科中一门核心专业根底课。主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法的分析和评价。通过本课程的学习，使学生深透地理解数据构造的逻辑构造和物理构造的根本概念以及有关算法，培育根本的、良好的程序设计技能，编制高效牢靠的程序，为学习操作系统、编译原理和数据库等课程奠定根底。三、课程教学内容第一章 绪论教学内容：1） 什么是数据构造2） 抽象数据类型概念；数据类型；数据抽象与抽象数据类型；用于描绘数据构造的语言3） 数据构造的抽象层次4） 算法定义5）性能分析与度量；算法的性能标准；算法的后期测试；算法的事前估计；空间困难度度量；时间困难度度量；时间困难度的渐进表示法；教学要求： 理解：数据构造根本概念及数据构造的抽象层次 理解：抽象数据类型概念 理解：算法的定义及算法特性 驾驭：算法的性能分析与度量方法第二章 线性表教学内容：1） 线性表的定义和特点2） 线性表的依次存储及查找、插入和删除操作3） 线性表的链式存储及查找、插入和删除操作4） 运用线性表的实例教学要求：理解：线性表的定义和特点娴熟驾驭：线性表的依次存储构造的查找、插入和删除等根本操作娴熟驾驭：单链表、循环链表及双向链表的定义及实现驾驭：娴熟驾驭单链表的应用方法第三章 栈和队列教学内容：1） 栈：栈的抽象数据类型；栈的依次存储表示；栈的链式存储表示2） 队列：队列的抽象数据类型；队列的依次存储表示；队列的链式存储表示3） 队列的应用举例教学要求：娴熟驾驭：栈的定义及实现娴熟驾驭：队列的定义及实现驾驭：能运用栈和队列解决简洁实际问题第四章 串教学:内容：1) 字符串的抽象数据类型2) 字符串操作的实现3) 字符串的形式匹配教学要求：娴熟驾驭：字符串的定义方式娴熟驾驭：字符串的各种操作的实现理解：字符串的形式匹配算法第五章 数组和广义表教学:内容：1) 数组的定义和初始化2) 作为抽象数据类型的数组的依次存储方式教学要求：理解：作为抽象数据类型的数组的定义娴熟驾驭：依次表的数组定义方式及实现第六章 树和二叉树教学内容：1) 树和森林的概念：树的定义；树的术语；树的抽象数据类型；森林的概念2) 二叉树：二叉树的定义；二叉树的性质；二叉树的抽象数据类型3) 二叉树的表示：数组表示；链表存储表示4) 二叉树的遍历：中序遍历；前序遍历；后序遍历；应用二叉树遍历的实例；二叉树的中序非递归算法5) 线索化二叉树：线索；中序线索化二叉树；前序与后序的线索化6) 树与森林：树的存储表示；森林与二叉树的转换；树的遍历；森林的遍历7) 二叉树的计数8) 霍夫曼树：途径长度；霍夫曼树；霍夫曼树编码教学要求：理解：树和森林的概念驾驭：二叉树的概念、性质及二叉树的表示娴熟驾驭：二叉树的遍历方法驾驭：线索化二叉树的特性及找寻某结点的前驱和后继的方法驾驭：树和森林的实现及遍历方法驾驭：二叉树的计数方法及从二叉树遍历结果得到二叉树的方法驾驭：霍夫曼树的实现方法及霍夫曼编码的概念第七章 图教学内容：1）图的根本概念：图的根本概念；图的抽象数据类型2）图的存储表示：邻接矩阵；邻接表；邻接多重表3）图的遍历与连通性；深度优先搜寻；广度优先搜寻；连通重量4）最小生成树：克鲁斯卡尔算法；普里姆算法教学要求：驾驭：图的根本概念和图的存储表示娴熟驾驭：图的两种遍历方法与求解连通性问题的方法驾驭：构造最小生成树的Prim和Kruskal方法第九章 查找教学内容：1) 静态查找表：依次表的查找；有序表的查找；索引依次表的查找2) 二叉排序树：二叉排序树上的搜寻、插入和删除教学要求：娴熟驾驭：静态搜寻表的依次搜寻和折半搜寻方法娴熟驾驭：二叉搜寻树的表示、搜寻、插入、删除算法及其性能分析方法第十章 内部排序 教学内容：1) 概述2) 插入排序：干脆插入排序；对分插入排序；链表插入排序；希尔排序3) 选择排序：干脆选择排序；堆排序教学要求：驾驭：排序的根本概念和性能分析方法驾驭：插入排序、选择排序、等内排序的方法及性能分析方法单元名称：第 一 讲：绪论 一、教学目的 1.理解数据构造课程的体系构造2.驾驭本章介绍的各种根本概念和术语3.理解数据构造的二元组表示4.驾驭逻辑构造与物理构造之间的映像关系。二、重点与难点重点：数据构造的根本概念；逻辑构造与物理构造之间的映像关系。难点：逻辑构造与物理构造之间的映像关系。三、教学内容与教学过程介绍本学期课程的内容及支配本课程是计算机专业的重要专业课之一，主要介绍常用的数据构造以及相关算法。本课程主要讲授线性表、栈和队列、串、数组、树和二叉树、图、查找、排序等内容。成果考核方式为：期末成果+平常成果，其中期末成果占70%，平常成果占30%，平常成果为：作业成果+出勤率+上机成果。讲授新课1.1 什么是数据构造 讲解：（数据构造课程的探讨背景）从计算机最初以数值计算为主到大量非数值计算出现引出数据构造。讲解：（数据构造课程的探讨对象）例1-1图书馆的书目检索系统自动化问题。1-2计算机和人机对奕问题1-3多叉路口交通灯的管理问题总结：从以上三个例子可以看出，描绘这类非数值计算问题的数学模型不再是数学方程，而是诸如线性表、树和图等之类的数据构造，这些都是数据构造课程的探讨对象。因此，简洁地说，数据构造是一门探讨非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。介绍数据构造课程的开展以及与其他课程之间的关系。1.2根本概念和术语根本概念：数据、数据元素、数据项、数据对象、数据构造、构造（1）常见根本构造（逻辑构造）：集合、线性构造、树形构造、图状构造或网状构造数据构造的形式定义： 数据构造一般用一个二元组来表示：Data_Structure=(D,S)其中：D是数据元素的有限集，S是D上的关系的有限集表示一种数据构造，它由数据元素集合K和在K上定义的一种二元关系的集合R所组成。其中：是数据元素的有限集合，n为中数据元素的个数。是K上关系的有限集合，m为K上关系的个数，通常状况下m的取值为1。K上任何一个二元关系Rj是序偶的集合。对于Rj中的任一序偶<x，y>（x，yK），称x为第一个元素（或y的前驱），y为第二个元素（或x的后继）。数据构造中的数据元素和数据元素之间的关系还可以用图形直观地表示出来。图形中的每个结点对应一个数据元素，两结点之间带箭头的连线对应二元关系中的一个序偶，其中序偶的第一个元素称为弧尾，第二个元素称为弧头。举例讲解：例 数据构造line=K，R，其中K=01，02，03，04，05，06，07，08，09，10，R=r，r=<01，02>，<02，03>，<03，04>,<04，05>，<05，06>，<06，07>，<07，08>，<08，09>，<09，10>。例数据构造tree=K，R，其中K=01，02，03，04，05，06，07，08，09，10，R=r，r=<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<04，07>，<04，08>，<06，09>，<06，10>。例 数据构造graph=K，R，其中K=01，02，03，04，05，R=r，r=<01，02>，<02，01>，<01，04>，<04，01>，<01，03>，<03，01>，<02，04>，<04，02>，<03，05>，<05，03>。介绍常见数据构造（集合、线性构造、树型构造、图型构造）详细表示方式(2) 逻辑构造上述数据构造的定义是对操作对象的一种数学描绘，是从操作对象抽象出来的数学模型。构造定义中的“关系”描绘的是数据元素之间的逻辑关系，因此又称为数据的逻辑构造。依据这种逻辑关系通常将数据构造划分为线性构造和非线性构造，其中非线性构造又分为树型构造和图型构造。(3) 物理构造数据构造在计算机中的表示（存储映象）称为数据的物理构造或存储构造，它涉及到数据元素及其互相关系在计算机内部的表示形式。数据元素之间的关系在计算机中有两种不同的表示方法：依次映像和非依次映像。依据数据元素互相之间的关系在计算机中的表示形式将数据的物理构造划分为依次构造和链式构造。依次映像的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。非依次映像的特点是借助指示元素存储地址的指针表示数据元素之间的逻辑关系。留意：数据的逻辑构造和物理构造是亲密相关的两个方面，任何一个算法的设计取决于选定的数据的逻辑构造，而算法的实现依靠于采纳的存储构造。（4）数据构造一般包括三方面内容： 数据的逻辑构造、数据的存储构造、数据的运算 （举例讲解）小结：总结本讲的主要内容四、作业布置见习题集 单元名称：第 二 讲：线性表的类型定义，线性表的依次存储一、教学目的 驾驭线性表的依次表示和实现二、重点与难点线性表的依次表示和实现。三、教学过程的详细支配讲授新课2.1线性表的类型定义 线性表的定义：一个线性表是n 个数据元素的有限序列。其中每个数据元素的详细含义，在不同的状况下各不一样，但是同一线性表中的元素必定具有一样特性，即属于同一数据对象。例如：26个英文字母表；学生安康状况登记表（图2.1）等。 例如线性表（a1,ai-1,ai,ai+1,an），称ai-1是ai的干脆前驱元素， ai+1是 ai的干脆后继。引导学生自己总结线性构造的特点。线性表的长度：线性表中元素的个数（n0），n=0为空表。 线性表中数据元素的位序（如数据元素ai在线性表中的位序为i）。抽象数据类型线性表的定义：讲解定义中的数据对象，数据关系以及根本操作（教材P19），重点讲解常用的根本操作含义。通过示例2-1，2-2讲解更困难的根本操作，并分析时间困难度。2.2 线性表的依次表示和实现（1）线性表的依次表示：用一组地址连续的存储单元依次存储线性表的数据元素。（2）依次储存的地址关系：假设线性表的每个元素需占用l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个数据元素的存储位置LOC( a i+1)和第i个数据元素的存储位置LOC(a i)之间满意下列关系：LOC(a i+1)=LOC(a i)+l 线性表的第i个数据元素ai的存储位置为：LOC(ai)=LOC(a1)+(i-1)*l，其中LOC(a1)为线性表的基地址。（3）依次表及其特点, 依次储存构造是一种随机存取的存储构造。（4）线性表的动态安排依次存储构造。 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 Typedef struct ElemType *elem;int length;int listsize;SqList;(1) 基于依次存储构造的根本操作的实现主要介绍下面的根本操作并且分析时间困难度。InitList_Sq(SqList &L);ListInsert_Sq(SqList &L, int i, ElemType e); ListDelete_Sq(SqList &L, int i, ElemType &e);LocateElem_Sq(SqList L, ElemType e, Status (*compare)(ElemType, ElemType);MergeList_Sq(SqList La,SqList Lb, SqList &Lc);重点讲解：依次存储构造上实现线性表的插入操作设线性表，为了保证线性表的有序性，当在位置i之前插入一个新的数据元素x时，须要将第i个到第n个数据元素均向后挪动一个位置，然后将数据元素x存储到第i个位置上并变更线性表的长度。Status ListInsert_Sq(SqList &L, int i, ElemType e) / 在依次线性表L的第i个元素之前插入新的元素e，/ i的合法值为1iListlength_Sq(L)+1if (i < 1 | i > L.length+1) return ERROR; / 插入位置不合法if (L.length >= L.listsize) / 当前存储空间已满，增加安排 newbase = (ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof (ElemType);if (!newbase) exit(OVERFLOW); / 存储安排失败L.elem = newbase; / 新基址L.listsize += LISTINCREMENT; / 增加存储容量q = &(L.elemi-1); / q指示插入位置for (p = &(L.elemL.length-1); p >= q; -p) *(p+1) = *p;/ 插入位置及之后的元素右移*q = e; / 插入e+L.length; / 表长增1return OK; / ListInsert_Sq平均时间困难度分析： 依次存储构造上实现线性表的删除操作设线性表 ，为了保证线性表的有序性,当删除第个位置上的元素后，须要将第i+1个到第n个数据元素均向前挪动一个位置并变更线性表的长度。Status ListDelete_Sq(SqList &L, int i, ElemType &e) / 在依次线性表L中删除第i个元素，并用e返回其值。/ i的合法值为1iListLength_Sq(L)if (i < 1) | (i > L.length) return ERROR; / 删除位置不合法p = &(L.elemi-1); / p为被删除元素的位置e = *p; / 被删除元素的值赋给eq = L.elem+L.length-1; / 表尾元素的位置for (+p; p <= q; +p) *(p-1) = *p; / 被删除元素之后的元素左移-L.length; / 表长减1return OK; / ListDelete_Sq平均时间困难度分析：总结： 依次存储构造的优缺点依次构造的优点是构造简洁，对数据元素既可以实现依次访问，又可以实现随机访问；缺点是插入和删除操作须要挪动大量的数据元素。小结：本讲主要介绍了线性表的逻辑构造定义和根本运算，线性表的插入和删除操作在依次存储构造上的实现。小结：总结本讲的主要内容四、作业布置见习题集试验作业见试验指导单元名称：第 三 讲：线性表链式存储一、教学目的 驾驭单链表的表示和实现二、重点与难点单链表的存储构造和根本操作实现。三、教学内容与教学过程 复习线性表的依次存储构造的特点引入另一种表示方法链式存储构造。讲授新课2.3.1线性链表 （1）线性链表线性链表：用一组随意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。线性链表的存储构造：以元素(数据元素的映象)+指针(指示后继元素存储位置)=结点(表示数据元素 或 数据元素的映象)，其中指针域只有一个。举例讲解：教材图2.5线性表中第一个数据元素的存储地址作为线性表的地址，称作线性表的头指针。有时为了操作便利，在第一个结点之前虚加一个“头结点”，以指向头结点的指针为链表的头指针。线性表为空时，头结点的指针域为空。举例如图2.7.线性表的单链表存储构造的C语言描绘：typedef struc LNode / 定义单链表结点 ElemType data; struct LNode *next； / 指向后继的指针域LNode, *LinkList；单链表操作的实现：GetElem(L, i, e) / 取第i个数据元素ListInsert(&L, i, e) / 插入数据元素ListDele CreateList(&L, n) / 生成含 n 个数据元素的链表CreateList(&L, n) / 生成含 n 个数据元素的链表MergeList (&La,&Lb,&Lc) /合并两个有序链表 (1) 建立单链表（要求从头部插入）void CreateList_L(LinkList &L, int n) / 逆位序输入n个元素的值，建立带表头结点的单链线性表L。L = (LinkList) malloc (sizeof (LNode);L->next = NULL; / 先建立一个带头结点的单链表for (i = n; i > 0; -i ) p = (LinkList) malloc (sizeof (LNode); / 生成新结点scanf(&p->data); / 输入元素值p->next = L->next; L->next = p; / 插入到表头 / CreateList_L注：从头部插入元素建立单向链表得到的线性序列为输入序列的逆序列。(2) 建立单链表（要求从尾部插入）void CreateList_L(LinkList &L, int n) /正位序输入n个元素的值，建立带表头结点的单链线性表L。L = (LinkList) malloc (sizeof (LNode); r = L;L->next = NULL; / 先建立一个带头结点的单链表for (i = n; i > 0; -i ) p = (LinkList) malloc (sizeof (LNode); / 生成新结点scanf(&p->data); / 输入元素值p->next=r->next; r->next=p; r = p; / 插入到表尾 / CreateList_L (3) 在带头结点的单链表中插入结点分析：设在结点a和结点b之间插入数据为x的结点，通过图来分析则插入前和插入后的状况。Status ListInsert_L(LinkList L, int i, ElemType e) / 在带头结头的单链表L中第i位置之前插入元素ep = L; j = 0;while (p && j < i-1) p = p->next; +j; / 找寻第i-1个结点if (!p | j > i-1) return ERROR; / i小于1或者大于表长s = (LinkList) malloc ( sizeof (LNode); / 生成新结点s->data = e; s->next = p->next; / 插入L中p->next = s;return OK; / LinstInsert_L(4) 在带头结点的单链表中删除结点Status ListDelete_L(LinkList L, int i, ElemType &e) p = L; j = 0;while (p->next && j < i-1) p = p->next; +j; /找寻第i个结点并令p指向其前趋if (!(p->next) | j > i-1) return ERROR; / 删除位置不合理q = p->next; p->next = q->next; / 删除并释放结点e = q->data; free(q);return OK; / ListDelete_L注：上述两个算法的时间困难度均为O(n)。单链表的优点：它是一种动态构造，整个存储空间为多个链表共用不需预先安排空间插入、删除操作便利单链表的缺点：指针占用额外存储空间不能随机存取，查找速度慢小结：本讲主要介绍了单链表的存储构造，以及的根本操作（建立、插入和删除）的实现。四、作业布置见习题集试验作业见试验指导。 第四讲 循环链表，双向链表，链表应用一、教学目的 1理解循环链表和的根本概念；2驾驭双向链表的插入和删除操作；3驾驭一元多项式的表示及加法在链式存储构造上的实现。二、重点与难点双向链表的存储构造和根本操作实现。三、教学内容与教学过程讲授新课单向循环链表设指针p指向单向链表中最终一个结点，则p->next的值是0，表示该结点是单向链表的最终一个结点。假如将单向链表中的最终一个结点的指针域改为存放单向链表中第一个结点的地址值，使得整个线性链表构成一个环，则称这种线性链表为单向循环链表。设p指向单向循环链表中的最终一个结点，则p->next的值不是0而是等于指向循环链表中的第一个结点head的值。双向链表假如链表中的每个结点都有两个指针域，分别指向其前驱结点和后继结点，则称这种链表为双向链表。双向链表中的结点类型描绘如下：typedef struct DuLNode ElemType data; / 数据域struct DuLNode *prior; / 指向前驱的指针域struct DuLNode *next; / 指向后继的指针域 DuLNode, *DuLinkList;设指针p指向双向链表中的某个结点，则明显有以下的结论：p->prior->next=p=p->next->prior(1) 双向链表的插入操作设指针变量p指向双向链表中的结点A，指针变量q指向被插入的新结点B，则在结点A的后面插入结点B的操作序列为：(1) q->next=p->next； (2) p->next->prior=q；(3) p->next=q；(4) q->prior=p；(2) 双向链表的删除操作设指针变量p指向双向链表中被删除的结点X，则删除结点X的操作序列为：(1) p->prior->next=p->next； (2) p->next->prior=p->prior； (3) free(p)；注：在双向链表或双向循环链表中进展插入和删除操作时，尤其要留意修改有关结点指针域的操作次序，以免丧失链域信息而造成链表中断的错误。链式存储构造的应用：一元多项式的表示及相加一元多项式可按升幂写成：它由n+1个系数唯一确定。在计算机中，可用一个线性表P来表示：每项系数i隐含在系数的序号里。若为一个一元多项式，同样用线性表Q表示：这两个多项式可以相加，结果为，其中设，则用线性表表示R为：我们可以采纳依次存储构造存放P、Q和R，使得多项式相加算法定义非常简介。然而，在通常的应用中，多项式的次数很高且变更很大，使得依次存储构造的最大长度很难确定，特殊是在处理形如S(x)=1+3x10001+2x20000的多项式时，要用长度为20001的线性表来表示。假如对每个元素运用两个数据项，一个为系数项，另一个为指数项，则这样构成的线性表可表示成：因此上式S(x)可表示成(1, 0 ),(3, 1001), (2, 20000 )。明显这样的线性表应采纳链式存储构造。课本 P41 图2.17中两个线性链表分别表示一元多项式A(x)=7+3x+9x8+5x11和一元多项式B(x)=8x+22x7-9x8，由这两个多项式得到的和多项式如图课本 P412.18所示。用链表表示多项式时，链表中的数据类型描绘成：typedef struct polynomialfloat coef;int expn ; struct polynomial *next;ElemType;依据一元多项式相加的运算规则：对于两个一元多项式中全部指数一样的项，对应系数相加，若其和不为零，则构成和多项式中的一项；对于两个一元多项式中全部指数不一样的项则分别抄到和多项式中去。第一步：分别从A表和B表的表头开场，依据比拟pa->expn和pb->expn的比拟结果分三种状况探讨，直到A表或B表全部处理完。(1) pa->expn=pb->expn：则相加此两项的系数，假如相加后该项系数不等于0，则在C表中生成一个新结点存放该项，修改pa和pb使其指向各自的下一个结点。(2) pa->expn > pb->expn：则复制A表中pa所指向的结点到C表中，修改pa使其指向下一个结点。(3) pa->expn < pb->expn：则复制B表中pb所指向的结点到C表中，修改pb使其指向下一个结点。第二步：若B表没有处理完，将B表中剩余结点复制到C表中；反之则将A表中剩余结点复制到C表中。void create_item(LinkList &pc,float coef,int expn)p=(LinkList)malloc(sizeof(LNode);p->coef=coef; p->expn=expn; pc->next=p; pc=p;void ploy_add(LinkList pah,LinkList pbh,LinkList &pch)pa = pah; pb = pbh;pc = pch=(LinkList *)malloc(sizeof(LNode); / 为c链表添加一个头结点while(pa!=0 && pb!=0)if(pa->expn=pb->expn)x=pa->coef+pb->coef;if(x!=0) create_item(pc,x,pa->expn);pa=pa->next; pb=pb->next;else if(pa->expn>pb->expn)create_item(pc,pa->coef,pa->expn); pa=pa->next;else create_item(pc,pb->coef,pb->expn); pb=pb->next;while (pa!=0) create_item(pc,pa->coef,pa->expn); pa=pa->next;while (pb!=0) create_item(pc,pb->coef,pb->expn); pb=pb->next;pc->next=0; pc=pch; pch=pch->next; free(pc); /* 释放c链中的头结点 */小结：本讲主要介绍了循环链表和双向链表的根本概念，双向链表的插入和删除操作，一元多项式的表示及相加在链式存储构造上的实现。四、作业布置见习题集试验作业见试验指导。单元名称：第 五 讲：栈一、教学目的 1理解栈的根本概念和根本操作；2驾驭栈的根本操作在两种存储构造上的实现。二、重点与难点栈的根本操作在两种存储构造上实现。三、教学内容与教学过程首先复习线性表的学问，引入限定性的数据构造栈和队列。讲授新课3.1 栈3.1.1 抽象数据类型栈的定义栈：限定仅在表尾进展插入或删除操作的线性表，表尾栈顶，表头栈底，不含元素的空表称空栈。通过教材P44的图3.1讲解栈顶，栈底以及栈后进先出的特点。栈的抽象数据类型定义：ADT Stack 数据对象：D ai | ai ElemSet, i=1,2,.,n, n0 数据关系：R1 <ai-1, ai >| ai-1, aiD, i=2,.,n 约定an 端为栈顶，a1 端为栈底。 根本操作：InitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(S)StackLength(S)GetTop(S, &e) Push(&S, e)Pop(&S, &e) ADT Stack3.1.2 栈的表示和实现依次栈类似于线性表的依次映象实现，指向表尾的指针可以作为栈顶指针。 栈的依次存储表示： #define STACK_INIT_SIZE 100; #define STACKINCREMENT 10; typedef struct SElemType *base; SElemType *top; int stacksize; SqStack;依次栈的根本操作的算法描绘：初始化，返回栈顶元素，入栈，出栈。(a) 栈空栈满条件栈空条件：top=base栈满条件：base-top=stacksize(b) 入栈操作Status Push (SqStack &S, SElemType e) if(S.top-S.base>=S.stacksize)S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType);if(!S.base ) exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+ = e;return OK; (c) 出栈操作Status Pop (SqStack &S, SElemType &e) if (S.top=S.base) return ERROR;e=*-S.top;return OK;链栈：栈的链式存储构造。栈顶指针就是链表的头指针栈的链式存储构造类似单链表的存储构造，链表中第一个结点表示栈顶，最终一个结点表示栈底。由于链表的长度可以动态增长，因此进展入栈操作时无需考虑栈的上溢，但进展出栈操作时，必需考虑栈的下溢，下溢的条件是top的值为0。链式栈的入栈操作Status Push(LinkList &top, ElemType x)p=(LinkList *)malloc(sizeof(LNode); p->data=x; p->next=top; top=p; return OK;(2) 链式栈的出栈操作Status Pop(LinkStack &top, ElemTye &y)if (top=0) return ERROR;p=top; y=p->data; top=p->next; free(p);return OK;小结；本讲主要介绍了栈的根本概念，栈的根本运算，栈在依次存储构造和链式存储构造上实现根本操作。四、作业布置 见习题集试验作业见试验指导。单元名称：第 六 讲：队列一、教学目的 1理解栈的根本概念和根本操作；2驾驭栈的根本操作在两种存储构造上的实现。二、重点与难点栈的根本操作在两种存储构造上实现。三、教学内容与教学过程讲授新课队列的根本概念队列是一种限制全部插入操作在线性表的一端进展，而全部的删除操作在线性表的另一端进展的特殊线性表。允许插入（入队）操作的一端称为队尾，允许删除（出队）操作的一端称为队头。设队列为，则是队头元素，是队尾元素。队列中的元素依据的依次进入队列的，退出队列也只能依据这个次序依次退出，即只有在都退出队列后，才能退出队列。因此队列也称为先进先出（FIFO）的线性表。2、队列的根本操作InitQueue(&Q)DestroyQueue(&Q)ClearQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q, &e)EnQueue(&Q, e)DeQueue(&Q, &e)3、队列的依次存储构造和循环队列在队列的依次存储构造中，除了用一组地址连续的存储单元依次存放从队头到队尾的元素之外，还须要附设两个指针front和rear。为了在C语言中描绘便利起见，在此我们约定：初始化建立空队列时，令front=rear=0，每当插入新的队尾元素时，尾指针rear增1；每当删除队头元素时，头指针front增1。因此，在非空队列中，头指针始终指向队列头元素，尾指针始终指向队列尾元素的下一个位置。探讨：将数据10，20，30，40，50，60依据入队列、入队列、入队列、出队列、出队列、入队列、入队列、入队列、出队列和出队列的依次，视察队列中队头和队尾指针的变更状态。假设当前为队列安排的最大空间为6，则不行再接着插入新的队尾元素，否则会因数组越界而导致程序代码被破环，然而，此时又不宜如依次栈那样进展存储再安排扩大数组空间，因为队列的实际可用空间并末占满。解决这个问题的奇妙方法是将依次队列的存储空间想象成一个逻辑上首尾相连的环状空间，这种存储构造称为循环队列。分析课本P64图3.14可知，Q.front=Q.rear无法推断队列空间是“满”还是“空”。解决这个问题有两种方法：其一是另设一个标记位以区分队列是“空”还是“满”；其二是少用一个元素空间，约定以队头指针在队尾指针的下一个位置上作为队列“满”的标记。因此，推断队列空的条件为Q.front=Q.rear；推断队列满的条件为Q.front = (Q.rear+1) % MAXQSIZE。(a) 依次循环队列的类型描绘typedef struct