数据结构教案市公开课金奖市赛课一等奖课件.pptx

第0章 绪 论 教学目的：1.掌握数据结构基本概念；2.掌握抽象数据类型概念和软件结构办法3.理解算法含义，掌握算法时间复杂度计算教学重点：1.数据结构概念2.抽象数据结构软件结构办法3.时间复杂度计算教学难点：算法和算法时间复杂度作业：1-11-31-11（前三道小题）第1页第1页一.基本概念数据：人们利用文字符号、数字符号以及其它要求符号对现实世界事物及其活动所作抽象描述*数据元素：表示一个事物一组数据称为一个数据元素*数据项：构成数据元素数据称为该数据元素数据项抽象数据元素：没有实际含义数据元素抽象数据类型：没有确切定义数据类型叫抽象数据类型，用符号DataType来表示数据逻辑结构：即为数据元素之间互相联系方式可分为线性结构、树结构和图结构1.1数据结构基本概念第2页第2页二本门课程主要内容数据存储结构：数据元素在计算机中存储方式它基本形式有两种：顺序存储结构，链式存储结构数据操作：对一个数据类型数据进行某种处理数据操作集合：对一个数据类型数据所有操作数据结构课程主要讨论表、堆栈、队列、串、数组、树、二叉树、图等典型惯用数据结构在讨论这些结构时，主要从它们逻辑结构、存储结构和数据操作三个方面进行分析讨论第3页第3页三.数据元素数据项举例 假设要描述学生信息，看表1-1学生信息表学号姓名性别年令01张三男2002李四男2103王五女22表中除第一行标题行外，其它每一行为一个数据元素，每一列为一个数据项三举倒第4页第4页关于数据元素、数据项描述都能够使用某种高级程序设计语言来描述，本书采用C语言描述如上表学生信息可定义为下列结构体：typedefstructstudentcharnumber8;charname10;charsex3;intage;studenttype用C语言描述n第5页第5页 有 了 上 面 定 义 后，studenttype 就 可 看 做 与 struct student 含义相同标识符1线性结构树结构图结构ABCDABDFCEGABCDFEG结构与标识符由图可见，线性结构除第一个和最后一个数据元素外，每个数据元素只有一个前驱数据元素和一个后继数据元素而树结构是除根结点外每个元素只有一个前驱元素，可有零个或若干个后继元素图每个元素可有零或多个前驱或后继元素第6页第6页1.把数据元素存放在一块连续地址空间内存中，其特点是逻辑上相邻数据元素在物理上也相邻，数据间逻辑关系表现在数据元素存放位置上以下图所表示：a0a1a2an-2an-12。顺序存储结构0 1 2 -2 -1第7页第7页使用指针把相互直接关联结点链接起来，其特点是逻辑上相邻数据元素在物理上不一定相邻，数据间逻辑关系表现在结点链接关系上以下图示3。链式存储结构第8页第8页数据类型：指一个类型和定义在这个类型上操作集合.比如，当说计算机中整数数据类型时，就不但指计算机所能表示整数数值集合，而且指能对这个整数类型进行+、-、*、和求模（）操作抽象数据类型（AbstractDataType缩写为ADT）：是指一个逻辑概念上类型和这个类型上操作集合数据类型和抽象数据类型不同之处于于：数据类型指是高级程序设计语言支持基本数据类型，而抽象数据类型指是在基本数据类型支持下用户新设计数据类型像表、堆栈、队列、串、数组、树、图等就是一个个不同抽象数据类型12抽象数据类型和软件结构办法第9页第9页13。算法和算法时间复杂度（1）1.3.1算法算法是描述求解问题办法操作环节集合它主要有三种形式：文字形式伪码形式和程序设计语言形式例1-1设计一个把存储在数组A中个抽象数据元素0，1，-1逆置算法，即要求逆置后数组中数据元素序列为，1，0，并要求原数组中数据元素值不能被改变设计：这是一个算法设计问题该算法要求有一个表示元素个数输入参数，一个表示原数组输入参数和一个表示逆置后数组输出参数第10页第10页算法设计下列：void Reverse(int n,DataType a,DataType b)int i;for(i=0;in;i+)bi=a n-1-i;算法时间复杂度（2）第11页第11页 该算法实现办法如图1-3所表示b0+3a0b1+3.a1.bn-2an-2bn-1An-1 图1-3例1-1算法实现办法图示该算法实现办法第12页第12页设计一个把存储在数组A中个抽象数据元素0，1，-1就地逆置算法，即要求逆置后数组中数据元素序列为，1，0，并要求原数组中数据元素值被改变设计：这是另一个算法设计问题该算法要求有一个表示元素个数输入参数，一个表示原数组输入参数和一个表示逆置后数组输出参数由于要求原数组中数据元素这被改变，因此输出参数必须与输入参数相同，因此，这两个参数应设计为同一个参数，其参数类型设计为输入输出混合型参数例1-2第13页第13页算法设计下列：void Reverse(int n,DataType a)int i,m=n/2;DataType temp;for(i=0;i m;i+)temp=a i ;a i =a n 1 i ;a n 1 i =temp;该算法实现办法如图14所表示p20算法设计第14页第14页 (1)正确性能 (2)可读性 (3)健壮性 (4)高时间效率 (5)高空间效率13.2算法设计目的第15页第15页.（1）事后统计办法 （2）事前分析办法 事前分析办法主要分析算法时间效率与算法所处理数据个数函数关系定义1-1T(n)=O(f(n)当且仅当存在正常数c和n0对所有n(n n0)满足T(n)c*f(n).即：当算法时间复杂度T(n)与数据个数n无关系时，T(n)c 1，因此此时算法时间复杂度T(n)=O(1)；当算法时间复杂度T(n)与数据个数n为线性关系时，因此此时算法时间复杂度T(n)=O()；依次类推分析一个算法中基本语句执行次数与数据个数函数关系，就可求出该算法时间复杂度13.3算法时间效率度量第16页第16页例1-3设数组和在前边部分已赋值，求下列两个阶矩阵相乘运算算法时间复杂度for (i=0;i n;i+)for(j=0;j n;j+)c i j =0;*基本语句1*for(k=0;k n;k+)c i j =c i j +a i j b k j ;/*基本语句2*/举例阐明下面举例阐明算法时间复杂度分析办法：第17页第17页解：设基本语句执行次数为f(n)，有f(n)=c1*n2+c2*n3因T(n)=f(n)=c1*n2+c2*n3=c*n3，其中c1,c2,c可为任意常数，因此该算法时间复杂度为T(n)=O(n3)第18页第18页例1-6下边算法是在一个有个数据元素数组中删除第个位置数组元素，要求当删除成功时数组元素个数减1，求该算法时间复杂度其中，数组下标为0-1intDelete(inta,int*n,inti)intj;f(i=*n)return 0;/*删除位置错误，失败返回*/ifor(j=i+1;jsize=0;/*定义初始数据元素个数*/（2）求当前数据元素个数(ListLength(L)int ListLength(SeqList L)/*返回顺序表L当前数据元素个数*/return L.size;2.2.2顺序表操作实现第28页第28页 （3）插入数据元素ListInsert(L,i,x)intListInsert(SeqList*L,inti,DataTypex)/*在顺序表L第i（0isize）个位置前插入数据元素 x*/*插入成功返回1，插入失败返回0*/intj;if(L-size=MaxSize)printf(“顺序表已满无法插入！n”);return0;else if(iL-size)2。2。2顺序表操作实现（2）第29页第29页插入数据元素（一）printf(“参数i 不合法！n”);return 0;return 0;else /*为插入做准备*/for(j=L-size;ji;j-)L-list j=L-list j-1;L-list i =x;/*插入x*/第30页第30页L-size+;/*元素个数加1*/return1;插入步骤：首先把存放单元size-1至存放单元i中数据元素依次后移一个存放单元，然后把数据元素x插入到存放单元i中（注意此操作是前插），最终把数据元素个数加1其过程以下图：list01234567MaxSIZE-1插入数据元素（二）1011121314151610111214151613 list0123456 7 MaxSize-1第31页第31页（1）（intint ListDelete(SeqList*L,int i,DataType*x)/*删除顺序表L中位置为i（0isize-1）数据元素并存储到x中*/*/*删除成功返回1，删除失败返回0*/)int j;if(L-size=0)printf(“顺序表已空无法删除！n”);return 0;（4）删除数据元素取数据元素ListDelete(L,i,x)第32页第32页elseif(iL-size)printf(“参数i不合法！n”);return0;Else*x=L-listi;/*保留删除元素到x中*/*依次前移*/for(j=i+1;jsize-1;j+)L-listj-1=L-listj;L-size-;/*数据元素个数减1*/return1;)删除和取数据元素（二）第33页第33页（5）取数据元素ListGet(L,i,x)int ListGet(SeqList L,int i,DataType*x)/*取顺序表L中第i个数据元素存于x中成功返回1失败返回0*/if(i L.size-1)printf(“参数i不合法n”);return 0;else x=L.list i ;return 1）;（5）取数据元素第34页第34页顺序表上插入和删除是顺序表中时间复杂度最高组员函数在顺序表中插入一个数据元素时，最坏情况是pos0，需移动size个数据元素；最好情况是possize，需移动0个数据元素设pi是在第i个存储位置上插入一个数据元素概率，设顺序表中数据元素个数为n，当在顺序表任何位置上插入数据元素概率相等时，有pi1/（n+1），则向顺序表插入一个数据元素需移动数据元素平均次数为：Eis=0 npi(n-i)=0n(n-i)=n/2删除操作时间复杂度计算见教材33顺序表中其余操作都与数据元素个数n无关，在顺序表中插入和删除一个数据元素时间复杂度为 O(n)，其余操作时间复杂度为 O(1)2。2。3顺序表操作分析第35页第35页2。2。4顺序表应用举例n请同窗们自己分析例题算法第36页第36页2。3线性表链式表示和实现n指针：指向物理存储单元地址变量n结点：由数据元素域和一个或若干个指针域构成一个结构体n链表：链式存储结构线性表n链表主要有单链表、单循环链表和双向循环链表三种第37页第37页单链表是构成链表结点只有一个指向直接后继结点指针域1.单链表表示办法定义单链表结点结构体下列：typedef struct Node DataType data;struct Node*next;SLNode;数据域指针域datanext2。3。1单链表存储结构（1）第38页第38页其中，data域用来存储数据元素，next域用来存储指向下一个结点指针单链表有带头结点结构和不结点结构两种指向单链表指针称作头指针，头指针所指不存储数据元素第一个结点称为头结点存储第一个数据元素结点称为第一个数据元素结点符号表示空指针，空指针是一个特殊标识，用来标识链结束空指针在算法描述中用NULL表示在链式存储结构中，数据元素逻辑顺序是通过链中指针链接实现2。3。1（2）第39页第39页(1）带头单链表每个元素存贮区别为两大部分：head p data next带头和不带头结点单链表比较a0 a n-1 X 上图是在带头结点单链表第一个数据元素前插入结点前图示第40页第40页a0a1an-1x上图是在带头结点单链表第一个数据元素前插入结点后图示也可参考下图：head p s带头和不带头结点单链表比较（2）第41页第41页plena1ana2headq单链表插入结点P-next=q;q-next=p-next;第42页第42页Head p next a0a1an-1上图是删除带头结点单链表第一个数据元素结点示意图第43页第43页22）不带头结点单链表插入删除数据元素结点示意图下列：在第一个数据元素前插入结点时，头指针head值将改变为新插入结点指针s，其插入过程下列：heada0a1an-1x插入删除数据元素结点示意图第44页第44页在第一个数据元素前插入结点时，头指针head值将改变为新插入结点指针s，其插入过程下列：head插入前示意图 s head s a0上图是在不带头结点单链表第一个数据元素前插入结点后示意图a0a1an-1xa0a1an-1x不带头结点单链表插入删除数据元素示意图第45页第45页在不带头结点单链表其它数据元素前插入结点示意图下列：head data next pa0ai-1aian-1Xs插入结点示意图第46页第46页类似地，删除不带头结点单链表第一个数据元素结点时，头指针head值将改变为head-next，即指针head等于原head-next值head data next a0a1an-1删除不带头结点示意第47页第47页删除不带头结点单链表其它数据元素结点时示意图下列：head data next pa0ai-1aiai+1an-1第48页第48页单链表是由一个个结点链接构成，单链表中每个结点结构体定义下列：typedef struct Node DataType data;struct Node*next;SLNode;在带头结点单链存储结构下，线性表抽象数据类型操作集合中各个操作详细实现办法下列：（1）初始化ListInitiate(SLNode*head)void ListInitiate(SLNode*head)/*初始化*/*假如有内存空间，申请头结点空间并使头指针head指向头结点*/if(*head=(SLNode*)malloc(sizeof(SLNode)=NULL)exit(1)(*head)-next=NULL;第49页第49页int ListLength(SLNode *head)SLNode*p=head;/*指向头结点*/int size=0;/*size初始为0*/while(p-next!=NULL)/*循环计数*/p=p-next;size+;return size;（2）求当前数据元素个数ListLength(SLNode *head)求当前数据元数个数第50页第50页head p size=0a0a1an-1headpsize=na0a1an-1接上面第51页第51页（1）（3）插入ListInsert(SLNode *head,int i,DataType x)int ListInsert(SLNode *head,int i,DataType x)/*在带头结点单链表head 第i(0isize)个结点前*/*插入一个存储数据元素x结点插入成功时返回1，失败返回0*/SLNode *p,*q;int j;while(p-next!=NULL&j next;j+;插入存储数据元素结点（1）第52页第52页if(j!=i-1)printf(“插入位置参数错!”);return 0;/*生成新结点由指针q批示*/if(q=(SLNode*)malloc(sizeof(SLNode)=NULL)exit(1)q-data=x;q-next=p-next;/*插入环节1*/p-next=q;/*插入环节2*/return 1;插入存储数据元素结点（2）第53页第53页（4）删除取数据元素 ListDelete(SLNode *head,int i,DataType x)int ListDelete(SLNode *head,int i,DataType x)/*删除带头结点单链表head第i（0isize-1）个结点*/*被删除结点数据元素域值由x带回删除成功时返回1，失败返回0*/SLNode*p,*s;int j;p=head;j=-1;删除取数据元素（1）第54页第54页 while(p-next!=NULL&p-next-next!=NULL&j next;j+;if(j!=i-1)printf(“删除位置参数错!”);return 0;s=p-next;/*指针指向ai结点*/*x=s-data;/*把指针所指向结点数据元素域值赋予x*/p-next=p-next-next;/*删除*/free(s);/*释放指针所指向结点内存空间*/return 1;删除取数据元素（2）第55页第55页（5）取数据元素ListGet(SLNode *head,int i,DataType x)int ListGet(SLNode *head,int i,DataType x)SLNode*p;int j;p=head;j=-1;while(p-next!=NULL&j next;j+;if(j!=i)printf(“取元素位置参数错！”);return 0;x=p-data;return 1;取数据元素第56页第56页（6）撤消单链表Destroy(SLNode*head)void Destroy(SLNode*head)SLNode*p,*p1;p=*head;while(p!=NULL)p1=p;p=p-next;free(p1);head=NULL;撤消单链表第57页第57页当在单链表任何位置上插入数据元素概率相等时，在单链表中插入一个数据元素时比较数据元素平均次数为：Eis=0n pi(n-i)=1/(n+1)0n(n-i)=n/2删除单链表一个数据元素时比较数据元素平均次数为：Edl=0n-1 qi(n-i)=1/n0n-1(n-i)=(n-1)/2单链表数据元素个数操作时间复杂度为T（n）=O（n）单链表主要长处是不需要预先拟定数据元素最大个数，插入和删除操作时不需要移动数据元素；主要缺点是每个结点中要有一个指针域，因此，空间单元利用效率不高另外，单链表操作算法较复杂2。3。3单链表操作效率分析第58页第58页本章结束时，再行分析2。3。4单链表应用举例第59页第59页循环单链表是单链表另一个形式，其结构特点是链表中最后一个结点指针域不再是结束标识，而是指向整个链表第一个结点，从而使链表形成一个环带头结点循环链表操作与带头单链表操作相同，差别在于：1.在初始化函数中，把语句(*head)-next=NULL改为(*head)-next=head2.在其它函数中，循环判断条件p-next!=NULL和p-next-next!=NULL中NULL改为头指针head 2。3。5循环单链表第60页第60页1.双向链表存储结构双向链表是每个结点除后继指针域外尚有一个前驱指针域这里讨论是带头结点双向循环链表在双向链表中，每个结点包括三个域，分别是data域next域prior域双向链表结点结构体定义下列：prior data nexttypedef struct Node DataType data;struct Node *next;struct Node *prior;DLNode;双向循环链表后继指针和前驱指针各自构成自己单循环链表，见图48 2-17双向链表有助于频繁查找当前结点后继结点和当前结点前驱结点2。3。6双向链表第61页第61页3.双向链表操作实例ai1aiai+1设指针指向双向链表中第i个结点，则p-next指向第i+1个结点，p-next-prior 仍指向第i个结点，即p-next-prior=p；同样地，p-prior指向第i-1个结点，p-prior-next仍指向第i个结点，即p-prior-next=p p head 双向链表指针关系空链表第62页第62页双向链表操作实现下列：(1)初始化void ListInitiate(DLNode*head)if(*head=(DLNode*)malloc(sizeof(DLNode)=NULL)exit(0);(*head)-prior=*head;/*构成前驱指针循环链*/(*head)-next=*head;/*构成后继指针循环链*/操作实现下列第63页第63页/*在带头结点双向循环链表第i个结点前*/*插入一个存储数据元素x结点插入成功返回1，失败返回0*/int ListInsert(DLNode*head,int i,DataType x)DLNode*p,*s;int j;p=head-next;j=0;while(p!=head&j next;j+;if(j!=i)printf(“插入位置参数犯错！”)return 0;(2)插入数据元素（1）第64页第64页if(s=(DLNode*)malloc(sizeof(DLNode)=NULL)exit(0);s-data=x;s-prior=p-prior;/*插入环节1*/p-prior-next=s;/*插入环节2*/s-next=p;/*插入环节3*/p-prior=s;/*插入环节4*/return 1;(2)插入数据单元（2）第65页第65页循环双向链表插入过程下列：head p插入过程 aai1aian-1xs第66页第66页intListDelete(DLNode*head,inti,DataType*x)/*删除带头结点双向循环链表head第i(0isize-1)个结点*/*被删除结点数据元素域值由x带回，删除成功时返回1，失败返回0*/DLNode*p;intj;p=head-next;j=0;while(p-next!=head&jnext;j+;（3）删除数据无数（1）第67页第67页（3）删除数据元素（2）if(j!=i)printf(“删除位置参数犯错！”);return 0;p-prior-next=p-next;/*删除环节1*/p-next-prior=p-prior;/*删除环节2*/*x=p-data;free(p);return 1;第68页第68页voidDestroy(DLNode*head)DLNode*p,*p1;inti,n=ListLength(*head);p=*head;for(i=0;inext;free(p1);head=NULL;（4）撤消内存空间Destroy(DLNode*head)第69页第69页2。4静态链表2。5算法设计举例（1）2.5.1顺序表算法设计举例 例2-4结构一个顺序表删除算法，把顺序表L中数据元素删除 算法思想；此删除问题可通过一个循环比较过程来实现 算法设计下列：int ListDataDelete(SeqList*L,DataType x)int i,j;第70页第70页 for(i=0;i size;i+)/*寻找元素x*/if(x=L-list i)break;if(i=L-size)return 0;/*未寻找到元素x*/else/*寻找到元素*/for(j=i;j size;j+)/*元素依次前移*/L-listj=L-listj+1;L-size-;/*元素个数减1*/return 1;算法设计举例（2）第71页第71页例2-5设头指针为head，并设带头结点单链表中数据元素递增有序，编写算法将数据元素x插入到带头结点单链表适当位置，要求插入后保持单链表数据元素递增有序算法思想；从链表第一个数据元素结点开始，逐一比较每个结点data域值和x值，当data小于等于x时，进行下一个结点比较；不然，就找到了插入结点适当位置，此时申请新结点把x存入，然后把新结点插入；当比较到最后一个结点仍有data小于等于x时，则把新结点插入单链表尾2。5。2单链表算法设计举例第72页第72页voidLinListInsert(SLNode*head,DataTypex)SLNode*curr,*pre,*q;/*循环初始化*/curr=head-next;/*curr指向第一个设计元素结点*/pre=head;/*pre指向头结点*/*循环定位插入位置*/while(curr !=NULL&curr -data next;学生分析剩余例题算法设计下列第73页第73页教学目的：1.掌握堆栈基本概念 2.理解堆栈抽象数据类型 3.纯熟掌握堆栈表示和实现 4.掌握队列基本概念 5.掌握顺序循环队列表示和实现 6.掌握链式队列存储结构和操作实现教学重点：1.堆栈表示和实现2.队列实现教学难点：堆栈实现 第三章堆栈和队列第74页第74页3.1.1堆栈基本概念 堆栈 是一个特殊线性表其数据元素以及数据元素间逻辑关系和线性表完全相同，差别在于线性表允许在任意位置插入和删除，而堆栈只堆栈只允许在栈顶进行操作允许在栈顶进行操作堆栈也称作后进先出表它可完毕比较复杂数据元素特定序列转换任务3。1堆栈第75页第75页数 据 集 合：堆 栈 数 据 集 合 能 够 表 示 为a0,a1,an-1每个数据元素数据类型为DataType.操作集合：1.初始化StackInitiate(S)：初始化堆栈S2.非空否StackNotEmpty(S)：堆栈S非空否若堆栈非空，则函数返回1；不然，返回03.入栈StackPush(S,x)：在堆栈当前栈顶插入数据元素x4.出栈StackPop(S,d)：把堆栈S当前栈顶数据元素删除并由参数d带回5.取栈顶数据元素StackTop(S,d)：取堆栈S当前栈顶数据元素并由参数d带回以上3.4.5均为成功返回1；不然，返回03。1。2堆栈抽象数类型3。1。2堆栈抽象数据类型第76页第76页 1.1.顺序堆栈存储结构 顺序堆栈存储结构示意图下列：Stack 栈底 栈顶 0 1 2 3 4 5 MaxStackSize-1 top用C语言定义上述顺序堆栈结构体SeqStack下列：typedef structDataType stack MaxStackSize ;int top;SeqStack;a 0 a1 a2 a3 a4 3。1。3堆栈顺序表示和实现第77页第77页;.(1)初始化StackInitiate(S)voidStackInitiate(SeqStack*S)/*初始化顺序堆栈S*/S-top=0;/*定义初始栈顶下标值*/（2）非空否StackNotEmpty(S)int StackNotEmpty(SeqStack S)/*判断顺序堆栈S非空否，非空返回1，不然返回0*/if(S.top top=MaxStackSize)printf(“堆栈已满无法插入！n”);return 0;else S-stack S-top =x;S-top+;return 1;(3)入栈StackPush(SeqStack*Sz,DataType x)操作实现（2）第79页第79页int StackPop(SeqStack*S,DataType*d)/*弹出顺序堆栈S栈顶数据元素值到参数d，出栈成功返回1，不然返回0*/if(S-top top-;*d=S-stack S-top ;return 1;操作实现（3）（4）出栈StackPop(SeqStack*S,DataType*d)第80页第80页StackTop(SeqStack S,DataType*d)int StackTop(SeqStack S,DataType*d)/*取顺序堆栈S当前栈顶数据元素值到参数d，成功返回1，不然返回0*/if(S.top=0)printf(“堆栈已空！n”);return 0;else*d=S.stack S.top-1 ;return 1;（5）取顶数据元素第81页第81页设上述顺序堆栈结构体定义和操作实现函数存储在文 件 SS中，设计下列测试主函数进行测试：include /*该文献包括printf()函数*/include /*该文献包括exit()函数*/define MaxStackSize 100 /*定义MaxStackSize为 100*/typedef int DataType;/*定义DataType为int数据类型*/include“SeqStack.h”void main(void)SeqStack myStack;int i,x;3。顺序堆栈测试（1）第82页第82页StackInitiate(&myStack);/*初始化*/for(i=0;i next=NULL;3。链式堆栈操作实现第87页第87页（2）非空否StackNotEmpty(LSNode*head)int StackNotEmpty(LSNode*head)/*判断堆栈是否非空，非空返回1，不然返回0*/if(head-next=NULL)return 0;return 1;3。链式堆栈操作实现（2）第88页第88页（3）入栈StackPush(LSNode*head,DataType x)/*把数据元素x插入链式堆栈栈顶head作为新栈顶*/int StackPush(LSNode*head,DataType x)LSNode*p;if(p=(LSNode*)malloc(sizeof(LSNode)=NULL)printf(“内存空间不足无法插入！n”);return 0;p-data=x;p-next=head-next;/*新结点链入栈顶*/head-next=p;/*新结点成为新栈顶*/return 1;3。链式堆栈操作实现（3）第89页第89页(4)出栈StackPop(LSNode*head,DataType*d)int StackPop(LSNode*head,DataType*d)/*出栈并把栈顶元素由参数d带回*/LSNode*p=head-next;if(p=NULL)printf(“堆栈已空犯错!”);return 0;head-next=p-next;/*删除原栈顶结点*/*d=p-data;/*原栈顶结点元素赋予d*/free(p);/*释放原栈顶结点内存空间*/return 1;3。链式堆栈操作实现（4）第90页第90页(5 取栈顶数据元素StackTop(LSNode*head,DataType*d)int StackTop(LSNode*head,DataType*d)/*取栈顶元素并把栈顶元素由参数d带回*/LSNode*p=head-next;if(p=NULL)printf(“堆栈已空犯错!”);return 0;d=p-data;return 1;3。链式堆栈操作实现（5）第91页第91页(5)撤消动态申请空间Destroy(LSNode*head)voidDestroy(LSNode*head)LSNode*p,*p1;p=head;while(p!=NULL)p1=p;p=p-next;free(p1);与单链表操作集合相同，链式堆栈也要增长一个撤消动态申请空间操作3。链式堆栈操作实现（6）第92页第92页3。3队列3.3.13.3.1队列基本概念队列基本概念队队列列是是一一个个特特殊殊线线性性表表它它允允许许在在其其一一端端进进行行插插入入操操作，在其另一端进行删除操作作，在其另一端进行删除操作队队列列中中允允许许进进行行插插入入操操作作一一端端称称为为队队尾尾，允允许许进进行行删删除除操操作作一一端端称称为为队队头头插插入入称称为为入入队队列列，删删除除称称为为出出队队列列当当队队列列中中没没有有数数据据元元素素时时称称为为空空队队列列因因队队尾尾插插入入，队队头头删删除除，它它也也称称作作先先进进先先出出表表，即即FIFOFIFO（First First In In First OutFirst Out）结构）结构插入与删除分别称为入队与出队。插入与删除分别称为入队与出队。第93页第93页 数据集合：数据集合：队列数据集合能够表示为a0,a1,an-1，每个数 据元素数据类型为DataType 操作集合：操作集合：（1）初始化QueueInitiate(Q)：初始化队列Q.（2）非空否QueueNotEmpty(Q)：队列Q非空否 若队列非空，函数返回1，不然，函数返回0（3）入队列QueueAppend(Q,x):在队列Q队尾插入数据元素x如入队列成功，返回1；不然，返回0 （4）出队列QueueDelete(Q,d)：把队列Q队头数据元素删除并由参数d带回如出队列成功，返回1；失败，则返回0 （5）取队头数据元素QueueGet(Q,d)：取队头数据元素并由参数d带回如取到数据元素返回1；不然，返回0.3。3。2队列抽象数据类型第94页第94页1.顺序队列存储结构见73图3-7 队列顺序存储结构称为顺序队列，顺序队列事实上是运算受限顺序表，和顺序表同样，顺序队列也是必须用一个向量空间来存储当前队列中元素。由于队列队头和队尾位置是改变，因而要设两个指针以分别批示队头和队尾元素在队列中位置，它们初始值地队列初始化时均应置为。入队时将新元素插入所指位置，然后尾指针将加。出队时，删去所指元素，然后头指针将加并返回被删元素。由此可见，当头尾指针相等时队列为空。在非空队列里，头指针始终指向队头元素，而尾指针始终指向队尾元素下一位置。顺序队列动态示意图见73图3-73。3。3顺序队列第95页第95页 由于在入队和出队操作中，头尾指针只增长不减小，致使被删除元素空间永远无法重新利用。因此，尽管队列中实际元素个数远远小于向量空间规模，但也也许由于尾指针巳超出向量空间上界而不能做入队操作。该现象称为假上溢。见教材上例子 2.顺序队列“假溢出”问题第96页第96页.1。顺序循环队列基本原理 为充足利用向量空间。克服上述假上溢现象办法是将向量空间想象为一个首尾相接圆环，并称这种向量为循环向量，存储在其中队列称为循环队列（Circular Queue)。在循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只但是当头尾指针指向向量上界（QueueSize-1）时，其加1操作结果是指向向量下界0。由于循环队列元素空间能够被利用，除非向量空间真被队列元素所有占用，不然不会上溢。因此，除一些简朴应用外，真正真正实用顺序队列是循环队列。实用顺序队列是循环队列。.。2。顺序循环队列队空和队满判断问题由于入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时头尾指针均相等。因此，我们无法通过front=rear来判断队列“空”还是“满”。3。3。4顺序循环队列表示和实现1-2。第97页第97页（1）少用一个存储单元：商定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：rear所指单元始终为空）队列满判断条件为：(rear+1)%MaxQueueSize=front队列空判断条件仍然为：rear=front处理问题办法有三种（1）第98页第98页（2）设置一个标志位设标志位为tag，初始时置tag=0；每当入队列成功就置tag=1；每当出队列操作成功就置tag=0则队列空判断条件为：rear=front&tag=0队列满判断条件为:rear=front&tag=1 （3）设置一个计数器（此办法最为简朴）设计数器为count，初始时置count=0；每当入队列操作成功就使count加1；每当出队列操作成功就使count减1这样，队列空判断条件为：count=0队列满判断条件为：count 0&rear=front 处理问题办法有三种（2-3）第99页第99页 循环队列类型定义 typedef Struct DataType queueMaxQqueueSize int rear;/*队尾指针*/int front;/*队头指针*/int count;/*计数器*/SeqCQueue;用上述第三种办法（计数器法）实现循环队列上六种基本操作（1）初始化QueueInitiate(SeqCQueue*Q)void QueueInitiate(SeqCQueue*Q)/*初始化顺序循环