数据结构教案市公开课一等奖百校联赛特等奖课件.pptx

第0章 绪 论 教学目标：1.掌握数据结构基本概念；2.掌握抽象数据类型概念和软件结构方法3.了解算法含义，掌握算法时间复杂度计算教学重点：1.数据结构概念2.抽象数据结构软件结构方法3.时间复杂度计算教学难点：算法和算法时间复杂度作业：1-11-31-11（前三道小题）第1页一.基本概念数据：人们利用文字符号、数字符号以及其它要求符号对现实世界事物及其活动所作抽象描述*数据元素：表示一个事物一组数据称为一个数据元素*数据项：组成数据元素数据称为该数据元素数据项抽象数据元素：没有实际含义数据元素抽象数据类型：没有确切定义数据类型叫抽象数据类型，用符号DataType来表示数据逻辑结构：即为数据元素之间相互联络方式可分为线性结构、树结构和图结构1.1数据结构基本概念第2页二本门课程主要内容数据存放结构：数据元素在计算机中存放方式它基本形式有两种：次序存放结构，链式存放结构数据操作：对一个数据类型数据进行某种处理数据操作集合：对一个数据类型数据全部操作数据结构课程主要讨论表、堆栈、队列、串、数组、树、二叉树、图等经典惯用数据结构在讨论这些结构时，主要从它们逻辑结构、存放结构和数据操作三个方面进行分析讨论第3页三.数据元素数据项举例 假设要描述学生信息，看表1-1学生信息表学号姓名性别年令01张三男2002李四男2103王五女22表中除第一行标题行外，其它每一行为一个数据元素，每一列为一个数据项三举倒第4页关于数据元素、数据项描述都能够使用某种高级程序设计语言来描述，本书采取C语言描述如上表学生信息可定义为以下结构体：typedefstructstudentcharnumber8;charname10;charsex3;intage;studenttype用C语言描述n第5页 有 了 上 面 定 义 后，studenttype 就 可 看 做 与 struct student 含义相同标识符1线性结构树结构图结构ABCDABDFCEGABCDFEG结构与标识符由图可见，线性结构除第一个和最终一个数据元素外，每个数据元素只有一个前驱数据元素和一个后继数据元素而树结构是除根结点外每个元素只有一个前驱元素，可有零个或若干个后继元素图每个元素可有零或多个前驱或后继元素第6页1.把数据元素存放在一块连续地址空间内存中，其特点是逻辑上相邻数据元素在物理上也相邻，数据间逻辑关系表现在数据元素存放位置上以下列图所表示：a0a1a2an-2an-12。次序存放结构0 1 2 -2 -1第7页使用指针把相互直接关联结点链接起来，其特点是逻辑上相邻数据元素在物理上不一定相邻，数据间逻辑关系表现在结点链接关系上以下列图示3。链式存放结构第8页 数据类型：指一个类型和定义在这个类型上操作集合.比如，当说计算机中整数数据类型时，就不但指计算机所能表示整数数值集合，而且指能对这个整数类型进行+、-、*、和求模（）操作抽象数据类型（Abstract Data Type缩写为ADT）：是指一个逻辑概念上类型和这个类型上操作集合数据类型和抽象数据类型不一样之处于于：数据类型指是高级程序设计语言支持基本数据类型，而抽象数据类型指是在基本数据类型支持下用户新设计数据类型像表、堆栈、队列、串、数组、树、图等就是一个个不一样抽象数据类型12抽象数据类型和软件结构方法第9页13。算法和算法时间复杂度（1）1.3.1算法算法是描述求解问题方法操作步骤集合它主要有三种形式：文字形式伪码形式和程序设计语言形式例1-1设计一个把存放在数组A中个抽象数据元素0，1，-1逆置算法，即要求逆置后数组中数据元素序列为，1，0，并要求原数组中数据元素值不能被改变设计：这是一个算法设计问题该算法要求有一个表示元素个数输入参数，一个表示原数组输入参数和一个表示逆置后数组输出参数第10页算法设计以下：void Reverse(int n,DataType a,DataType b)int i;for(i=0;in;i+)bi=a n-1-i;算法时间复杂度（2）第11页 该算法实现方法如图1-3所表示b0+3a0b1+3.a1.bn-2an-2bn-1An-1 图1-3例1-1算法实现方法图示该算法实现方法第12页设计一个把存放在数组A中个抽象数据元素0，1，-1就地逆置算法，即要求逆置后数组中数据元素序列为，1，0，并要求原数组中数据元素值被改变设计：这是另一个算法设计问题该算法要求有一个表示元素个数输入参数，一个表示原数组输入参数和一个表示逆置后数组输出参数因为要求原数组中数据元素这被改变，所以输出参数必须与输入参数相同，所以，这两个参数应设计为同一个参数，其参数类型设计为输入输出混合型参数例1-2第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页 (1)正确性能 (2)可读性 (3)健壮性 (4)高时间效率 (5)高空间效率13.2算法设计目标第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页例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页解：设基本语句执行次数为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页例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页 （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页插入数据元素（一）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页L-size+;/*元素个数加1*/return 1;插入步骤：首先把存放单元size-1至存放单元i中数据元素依次后移一个存放单元，然后把数据元素x插入到存放单元i中（注意此操作是前插），最终把数据元素个数加1其过程以下列图：list01234567MaxSIZE-1插入数据元素（二）1011121314151610111214151613 list0123456 7 MaxSize-1第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页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页（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页次序表上插入和删除是次序表中时间复杂度最高组员函数在次序表中插入一个数据元素时，最坏情况是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页2。2。4次序表应用举例n请同学们自己分析例题算法第36页2。3线性表链式表示和实现n指针：指向物理存放单元地址变量n结点：由数据元素域和一个或若干个指针域组成一个结构体n链表：链式存放结构线性表n链表主要有单链表、单循环链表和双向循环链表三种第37页单链表是组成链表结点只有一个指向直接后继结点指针域1.单链表表示方法定义单链表结点结构体以下：typedef struct Node DataType data;struct Node*next;SLNode;数据域指针域datanext2。3。1单链表存放结构（1）第38页其中，data域用来存放数据元素，next域用来存放指向下一个结点指针单链表有带头结点结构和不结点结构两种指向单链表指针称作头指针，头指针所指不存放数据元素第一个结点称为头结点存放第一个数据元素结点称为第一个数据元素结点符号表示空指针，空指针是一个特殊标识，用来标识链结束空指针在算法描述中用NULL表示在链式存放结构中，数据元素逻辑次序是经过链中指针链接实现2。3。1（2）第39页(1）带头单链表每个元素存贮区分为两大部分：head p data next带头和不带头结点单链表比较a0 a n-1 X 上图是在带头结点单链表第一个数据元素前插入结点前图示第40页a0a1an-1x上图是在带头结点单链表第一个数据元素前插入结点后图示也可参考下列图：head p s带头和不带头结点单链表比较（2）第41页plena1ana2headq单链表插入结点P-next=q;q-next=p-next;第42页Head p next a0a1an-1上图是删除带头结点单链表第一个数据元素结点示意图第43页22）不带头结点单链表插入删除数据元素结点示意图以下：在第一个数据元素前插入结点时，头指针head值将改变为新插入结点指针s，其插入过程以下：heada0a1an-1x插入删除数据元素结点示意图第44页在第一个数据元素前插入结点时，头指针head值将改变为新插入结点指针s，其插入过程以下：head插入前示意图 s head s a0上图是在不带头结点单链表第一个数据元素前插入结点后示意图a0a1an-1xa0a1an-1x不带头结点单链表插入删除数据元素示意图第45页在不带头结点单链表其它数据元素前插入结点示意图以下：head data next pa0ai-1aian-1Xs插入结点示意图第46页类似地，删除不带头结点单链表第一个数据元素结点时，头指针head值将改变为head-next，即指针head等于原head-next值head data next a0a1an-1删除不带头结点示意第47页删除不带头结点单链表其它数据元素结点时示意图以下：head data next pa0ai-1aiai+1an-1第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页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页head p size=0a0a1an-1headpsize=na0a1an-1接上面第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页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页（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页 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页（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页（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页当在单链表任何位置上插入数据元素概率相等时，在单链表中插入一个数据元素时比较数据元素平均次数为：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页本章结束时，再行分析2。3。4单链表应用举例第59页循环单链表是单链表另一个形式，其结构特点是链表中最终一个结点指针域不再是结束标识，而是指向整个链表第一个结点，从而使链表形成一个环带头结点循环链表操作与带头单链表操作相同，差异在于：1.在初始化函数中，把语句(*head)-next=NULL改为(*head)-next=head2.在其它函数中，循环判断条件p-next!=NULL和p-next-next!=NULL中NULL改为头指针head 2。3。5循环单链表第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页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页双向链表操作实现以下：(1)初始化void ListInitiate(DLNode*head)if(*head=(DLNode*)malloc(sizeof(DLNode)=NULL)exit(0);(*head)-prior=*head;/*组成前驱指针循环链*/(*head)-next=*head;/*组成后继指针循环链*/操作实现以下第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页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页循环双向链表插入过程以下：head p插入过程 aai1aian-1xs第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页（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页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页2。4静态链表2。5算法设计举例（1）2.5.1次序表算法设计举例 例2-4结构一个次序表删除算法，把次序表L中数据元素删除 算法思想；此删除问题可经过一个循环比较过程来实现 算法设计以下：int ListDataDelete(SeqList*L,DataType x)int i,j;第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页例2-5设头指针为head，并设带头结点单链表中数据元素递增有序，编写算法将数据元素x插入到带头结点单链表适当位置，要求插入后保持单链表数据元素递增有序算法思想；从链表第一个数据元素结点开始，逐一比较每个结点data域值和x值，当data小于等于x时，进行下一个结点比较；不然，就找到了插入结点适当位置，此时申请新结点把x存入，然后把新结点插入；当比较到最终一个结点仍有data小于等于x时，则把新结点插入单链表尾2。5。2单链表算法设计举例第72页voidLinListInsert(SLNode*head,DataTypex)SLNode*curr,*pre,*q;/*循环初始化*/curr=head-next;/*curr指向第一个设计元素结点*/pre=head;/*pre指向头结点*/*循环定位插入位置*/while(curr !=NULL&curr -data next;学生分析剩下例题算法设计以下第73页教学目标：1.掌握堆栈基本概念 2.了解堆栈抽象数据类型 3.熟练掌握堆栈表示和实现 4.掌握队列基本概念 5.掌握次序循环队列表示和实现 6.掌握链式队列存放结构和操作实现教学重点：1.堆栈表示和实现2.队列实现教学难点：堆栈实现 第三章堆栈和队列第74页3.1.1堆栈基本概念 堆栈 是一个特殊线性表其数据元素以及数据元素间逻辑关系和线性表完全相同，差异在于线性表允许在任意位置插入和删除，而堆栈只堆栈只允许在栈顶进行操作允许在栈顶进行操作堆栈也称作后进先出表它可完成比较复杂数据元素特定序列转换任务3。1堆栈第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页 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页;.(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页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页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页设上述次序堆栈结构体定义和操作实现函数存放在文 件 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页StackInitiate(&myStack);/*初始化*/for(i=0;i next=NULL;3。链式堆栈操作实现第87页（2）非空否StackNotEmpty(LSNode*head)int StackNotEmpty(LSNode*head)/*判断堆栈是否非空，非空返回1，不然返回0*/if(head-next=NULL)return 0;return 1;3。链式堆栈操作实现（2）第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页(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页(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页(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页3。3队列3.3.13.3.1队列基本概念队列基本概念队队列列是是一一个个特特殊殊线线性性表表它它允允许许在在其其一一端端进进行行插插入入操操作，在其另一端进行删除操作作，在其另一端进行删除操作队队列列中中允允许许进进行行插插入入操操作作一一端端称称为为队队尾尾，允允许许进进行行删删除除操操作作一一端端称称为为队队头头插插入入称称为为入入队队列列，删删除除称称为为出出队队列列当当队队列列中中没没有有数数据据元元素素时时称称为为空空队队列列因因队队尾尾插插入入，队队头头删删除除，它它也也称称作作先先进进先先出出表表，即即FIFOFIFO（First First In In First OutFirst Out）结构）结构插入与删除分别称为入队与出队。插入与删除分别称为入队与出队。第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页1.次序队列存放结构见73图3-7 队列次序存放结构称为次序队列，次序队列实际上是运算受限次序表，和次序表一样，次序队列也是必须用一个向量空间来存放当前队列中元素。因为队列队头和队尾位置是改变，因而要设两个指针以分别指示队头和队尾元素在队列中位置，它们初始值地队列初始化时均应置为。入队时将新元素插入所指位置，然后尾指针将加。出队时，删去所指元素，然后头指针将加并返回被删元素。由此可见，当头尾指针相等时队列为空。在非空队列里，头指针一直指向队头元素，而尾指针一直指向队尾元素下一位置。次序队列动态示意图见73图3-73。3。3次序队列第95页 因为在入队和出队操作中，头尾指针只增加不减小，致使被删除元素空间永远无法重新利用。所以，尽管队列中实际元素个数远远小于向量空间规模，但也可能因为尾指针巳超出向量空间上界而不能做入队操作。该现象称为假上溢。见教材上例子 2.次序队列“假溢出”问题第96页.1。次序循环队列基本原理 为充分利用向量空间。克服上述假上溢现象方法是将向量空间想象为一个首尾相接圆环，并称这种向量为循环向量，存放在其中队列称为循环队列（Circular Queue)。在循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界（QueueSize-1）时，其加1操作结果是指向向量下界0。因为循环队列元素空间能够被利用，除非向量空间真被队列元素全部占用，不然不会上溢。所以，除一些简单应用外，真正真正实用次序队列是循环队列。实用次序队列是循环队列。.。2。次序循环队列队空和队满判断问题因为入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时头尾指针均相等。所以，我们无法经过front=rear来判断队列“空”还是“满”。3。3。4次序循环队列表示和实现1-2。第97页（1）少用一个存放单元：约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：rear所指单元一直为空）队列满判断条件为：(rear+1)%MaxQueueSize=front队列空判断条件依然为：rear=front处理问题方法有三种（1）第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页 循环队列类型定义 typedef Struct DataType queueMaxQqueueSize int rear;/*队尾指针*/int front;/*队头指针*/int count;/*计数器*/SeqCQueue;用上述第三种方法（计数器法）实现循环队列上六种基本操作（1）初始化QueueInitiate(SeqCQueue*Q)void QueueInitiate(SeqCQueue*Q)/*初始化次序循环 队列Q*/Q-rear=0;/*定义初始队尾指 针下标值*/Q-front=0;/*定义初始队头指针下 标值*/Q-count=0;/*定义初始计数器值*/3。次序循环队列实现第100页（2）非空否QueueNotEmpty(SeqCQueueQ)intQueueNotEmpty(SeqCQueueQ)/*判断次序循环队列Q非空否，非空时返回1，不然返回0*/if(Q.count!=0)return 1;else return 0;3。次序循环队列实现（2）第101页（3）入队列QueueAppend(SeqCQueue*Q,DataTypex)intQueueAppend(SeqCQueue*Q,DataTypex)/*把数据元素值