数据结构教案课件

第0章 绪 论 教学目的：1.掌握数据结构的基本概念；2.掌握抽象数据类型的概念和软件构造方法3.了解算法的含义，掌握算法时间复杂度的计算教学重点：1.数据结构的概念2.抽象数据结构的软件构造方法3.时间复杂度的计算教学难点：算法和算法的时间复杂度作业：1-11-31-11（前三道小题）一.基本概念数据：人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所作的抽象描述*数据元素：表示一个事物的一组数据称为一个数据元素*数据项：构成数据元素的数据称为该数据元素的数据项抽象数据元素：没有实际含义的数据元素抽象数据类型：没有确切定义的数据类型叫抽象数据类型，用符号DataType来表示数据的逻辑结构：即为数据元素之间的相互联系方式可分为线性结构、树结构和图结构1.1数据结构的基本概念二本门课程的主要内容数据的存储结构：数据元素在计算机中的存储方式它的基本形式有两种：顺序存储结构，链式存储结构数据的操作：对一种数据类型的数据进行的某种处理数据的操作集合：对一种数据类型的数据所有的操作数据结构课程主要讨论表、堆栈、队列、串、数组、树、二叉树、图等典型的常用数据结构在讨论这些结构时，主要从它们的逻辑结构、存储结构和数据操作三个方面进行分析讨论三.数据元素数据项举例 假设要描述学生的信息，看表1-1学生信息表学号姓名性别年令200001张三男20200002李四男21200003王五女22表中除第一行标题行外，其他每一行为一个数据元素，每一列为一个数据项三举倒关于数据元素、数据项的描述都可以使用某种高级程序设计语言来描述，本书采用C语言描述如上表学生信息可定义为如下结构体：typedefstructstudentcharnumber8;charname10;charsex3;intage;studenttype用C语言描述n 有 了 上 面 的 定 义 后，studenttype 就 可 看 做 与 struct student 含义相同的标识符1线性结构树结构图结构ABCDABDFCEGABCDFEG结构与标识符由图可见，线性结构除第一个和最后一个数据元素外，每个数据元素只有一个前驱数据元素和一个后继数据元素而树结构是除根结点外每个元素只有一个前驱元素，可有零个或若干个后继元素图每个元素可有零或多个前驱或后继元素1.把数据元素存储在一块连续地址空间的内存中，其特点是逻辑上相邻的数据元素在物理上也相邻，数据间的逻辑关系表现在数据元素的存储位置上如下图所示：a0a1a2an-2an-12。顺序存储结构0 1 2 -2 -1使用指针把相互直接关联的结点链接起来，其特点是逻辑上相邻的数据元素在物理上不一定相邻，数据间的逻辑关系表现在结点的链接关系上如下图示3。链式存储结构 数据类型：指一个类型和定义在这个类型上的操作集合.例如，当说计算机中的整数数据类型时，就不仅指计算机所能表示的整数数值的集合，而且指能对这个整数类型进行的+、-、*、和求模（）操作抽象数据类型（Abstract Data Type缩写为ADT）：是指一个逻辑概念上的类型和这个类型上的操作集合数据类型和抽象数据类型的不同之处在于：数据类型指的是高级程序设计语言支持的基本数据类型，而抽象数据类型指的是在基本数据类型支持下用户新设计的数据类型像表、堆栈、队列、串、数组、树、图等就是一个个不同的抽象数据类型12抽象数据类型和软件构造方法13。算法和算法的时间复杂度（1）1.3.1算法算法是描述求解问题方法的操作步骤的集合它主要有三种形式：文字形式伪码形式和程序设计语言形式例1-1设计一个把存储在数组A中的个抽象数据元素0，1，-1逆置的算法，即要求逆置后的数组中数据元素序列为，1，0，并要求原数组中的数据元素值不能被改变设计：这是一个算法设计问题该算法要求有一个表示元素个数的输入参数，一个表示原数组的输入参数和一个表示逆置后数组的输出参数算法设计如下：void Reverse(int n,DataType a,DataType b)int i;for(i=0;in;i+)bi=a n-1-i;算法的时间复杂度（2）该算法的实现方法如图1-3所示b0+3a0b1+3.a1.bn-2an-2bn-1An-1 图1-3例1-1算法实现方法图示该算法的实现方法设计一个把存储在数组A中的个抽象数据元素0，1，-1就地逆置的算法，即要求逆置后数组中数据元素序列为，1，0，并要求原数组中的数据元素值被改变设计：这是另一个算法设计问题该算法要求有一个表示元素个数的输入参数，一个表示原数组的输入参数和一个表示逆置后数组的输出参数由于要求原数组中的数据元素这被改变，所以输出参数必须与输入参数相同，因此，这两个参数应设计为同一个参数，其参数类型设计为输入输出混合型参数例1-2算法设计如下：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算法设计 (1)正确性能 (2)可读性 (3)健壮性 (4)高时间效率 (5)高空间效率13.2算法设计目标.（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算法时间效率的度量例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*/举例说明下面举例说明算法时间复杂度的分析方法：解：设基本语句的执行次数为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)例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顺序表操作的实现 （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）插入数据元素（一）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*/L-size+;/*元素个数加1*/return 1;插入步骤：首先把存储单元size-1至存储单元i中的数据元素依次后移一个存储单元，然后把数据元素x插入到存储单元i中（注意此操作是前插），最后把数据元素个数加1其过程如下图：list01234567MaxSIZE-1插入数据元素（二）1011121314151610111214151613 list0123456 7 MaxSize-1（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)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;)删除和取数据元素（二）（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）取数据元素顺序表上的插入和删除是顺序表中时间复杂度最高的成员函数在顺序表中插入一个数据元素时，最坏情况是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顺序表操作的分析2。2。4顺序表应用举例n请同学们自己分析例题算法2。3线性表的链式表示和实现n指针：指向物理存储单元地址的变量n结点：由数据元素域和一个或若干个指针域组成的一个结构体n链表：链式存储结构的线性表n链表主要有单链表、单循环链表和双向循环链表三种单链表是构成链表的结点只有一个指向直接后继结点的指针域1.单链表的表示方法定义单链表结点的结构体如下：typedef struct Node DataType data;struct Node*next;SLNode;数据域指针域datanext2。3。1单链表的存储结构（1）其中，data域用来存放数据元素，next域用来存放指向下一个结点的指针单链表有带头结点结构和不结点结构两种指向单链表的指针称作头指针，头指针所指的不存放数据元素的第一个结点称为头结点存放第一个数据元素的结点称为第一个数据元素结点符号表示空指针，空指针是一个特殊标识，用来标识链的结束空指针在算法描述中用NULL表示在链式存储结构中，数据元素的逻辑次序是通过链中的指针链接实现的2。3。1（2）(1）带头单链表每个元素的存贮区分为两大部分：head p data next带头和不带头结点单链表的比较a0 a n-1 X 上图是在带头结点单链表第一个数据元素前插入结点前的图示a0a1an-1x上图是在带头结点单链表第一个数据元素前插入结点后的图示也可参考下图：head p s带头和不带头结点单链表的比较（2）plena1ana2headq单链表插入结点P-next=q;q-next=p-next;Head p next a0a1an-1上图是删除带头结点单链表第一个数据元素结点的示意图22）不带头结点的单链表插入删除数据元素结点的示意图如下：在第一个数据元素前插入结点时，头指针head的值将改变为新插入结点的指针s，其插入过程如下：heada0a1an-1x插入删除数据元素结点的示意图在第一个数据元素前插入结点时，头指针head的值将改变为新插入结点的指针s，其插入过程如下：head插入前的示意图 s head s a0上图是在不带头结点的单链表第一个数据元素前插入结点后的示意图a0a1an-1xa0a1an-1x不带头结点的单链表插入删除数据元素示意图在不带头结点的单链表其它数据元素前插入结点的示意图如下：head data next pa0ai-1aian-1Xs插入结点的示意图类似地，删除不带头结点的单链表第一个数据元素结点时，头指针head的值将改变为head-next，即指针head等于原head-next的值head data next a0a1an-1删除不带头结点示意删除不带头结点的单链表其它数据元素结点时的示意图如下：head data next pa0ai-1aiai+1an-1单链表是由一个个结点链接构成的，单链表中每个结点的结构体定义如下：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;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)求当前数据元数个数head p size=0a0a1an-1headpsize=na0a1an-1接上面（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）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）（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）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）（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;取数据元素（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;撤销单链表当在单链表的任何位置上插入数据元素的概率相等时，在单链表中插入一个数据元素时比较数据元素的平均次数为：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单链表操作的效率分析本章结束时，再行分析2。3。4单链表应用举例循环单链表是单链表的另一种形式，其结构特点是链表中最后一个结点的指针域不再是结束标记，而是指向整个链表的第一个结点，从而使链表形成一个环带头结点的循环链表的操作与带头单链表的操作相似，差别在于：1.在初始化函数中，把语句(*head)-next=NULL改为(*head)-next=head2.在其它函数中，循环判断条件p-next!=NULL和p-next-next!=NULL中的NULL改为头指针head 2。3。5循环单链表1.双向链表的存储结构双向链表是每个结点除后继指针域外还有一个前驱指针域这里讨论的是带头结点的双向循环链表在双向链表中，每个结点包括三个域，分别是data域next域prior域双向链表结点的结构体定义如下：prior data nexttypedef struct Node DataType data;struct Node *next;struct Node *prior;DLNode;双向循环链表的后继指针和前驱指针各自构成自己的单循环链表，见图48 2-17双向链表有利于频繁查找当前结点的后继结点和当前结点的前驱结点2。3。6双向链表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 双向链表的指针关系空链表双向链表的操作实现如下：(1)初始化void ListInitiate(DLNode*head)if(*head=(DLNode*)malloc(sizeof(DLNode)=NULL)exit(0);(*head)-prior=*head;/*构成前驱指针循环链*/(*head)-next=*head;/*构成后继指针循环链*/操作实现如下/*在带头结点的双向循环链表的第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）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）循环双向链表的插入过程如下：head p插入过程 aai1aian-1xsintListDelete(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）（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;voidDestroy(DLNode*head)DLNode*p,*p1;inti,n=ListLength(*head);p=*head;for(i=0;inext;free(p1);head=NULL;（4）撤销内存空间Destroy(DLNode*head)2。4静态链表2。5算法设计举例（1）2.5.1顺序表算法设计举例 例2-4构造一个顺序表的删除算法，把顺序表L中数据元素删除 算法思想；此删除问题可通过一个循环比较过程来实现 算法设计如下：int ListDataDelete(SeqList*L,DataType x)int i,j;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）例2-5设头指针为head，并设带头结点单链表中的数据元素递增有序，编写算法将数据元素x插入到带头结点单链表的适当位置，要求插入后保持单链表数据元素的递增有序算法思想；从链表的第一个数据元素结点开始，逐个比较每个结点的data域值和x的值，当data小于等于x时，进行下一个结点的比较；否则，就找到了插入结点的合适位置，此时申请新结点把x存入，然后把新结点插入；当比较到最后一个结点仍有data小于等于x时，则把新结点插入单链表尾2。5。2单链表算法设计举例voidLinListInsert(SLNode*head,DataTypex)SLNode*curr,*pre,*q;/*循环初始化*/curr=head-next;/*curr指向第一个设计元素结点*/pre=head;/*pre指向头结点*/*循环定位插入位置*/while(curr !=NULL&curr -data next;学生分析剩余的例题算法设计如下教学目的：1.掌握堆栈的基本概念 2.了解堆栈抽象数据类型 3.熟练掌握堆栈的表示和实现 4.掌握队列的基本概念 5.掌握顺序循环队列的表示和实现 6.掌握链式队列的存储结构和操作的实现教学重点：1.堆栈的表示和实现2.队列的实现教学难点：堆栈的实现 第三章堆栈和队列3.1.1堆栈的基本概念 堆栈 是一种特殊的线性表其数据元素以及数据元素间的逻辑关系和线性表完全相同，差别在于线性表允许在任意位置插入和删除，而堆堆栈只允许在栈顶进行操作栈只允许在栈顶进行操作堆栈也称作后进先出表它可完成比较复杂的数据元素特定序列的转换任务3。1堆栈数据集合：堆栈的数据集合可以表示为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堆栈抽象数据类型 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堆栈的顺序表示和实现;.(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）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)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）取顶数据元素设上述顺序堆栈的结构体定义和操作的实现函数存放在文 件 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）StackInitiate(&myStack);/*初始化*/for(i=0;i next=NULL;3。链式堆栈的操作的实现（2）非空否StackNotEmpty(LSNode*head)int StackNotEmpty(LSNode*head)/*判断堆栈是否非空，非空返回1，否则返回0*/if(head-next=NULL)return 0;return 1;3。链式堆栈的操作的实现（2）（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）(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）(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）(5)撤销动态申请空间Destroy(LSNode*head)voidDestroy(LSNode*head)LSNode*p,*p1;p=head;while(p!=NULL)p1=p;p=p-next;free(p1);与单链表的操作集合相同，链式堆栈也要增加一个撤销动态申请空间的操作3。链式堆栈的操作的实现（6）3。3队列3.3.13.3.1队列的基本概念队列的基本概念队队列列是是一一种种特特殊殊的的线线性性表表它它允允许许在在其其一一端端进进行行插插入入操作，在其另一端进行删除操作操作，在其另一端进行删除操作队队列列中中允允许许进进行行插插入入操操作作的的一一端端称称为为队队尾尾，允允许许进进行行删删除除操操作作的的一一端端称称为为队队头头插插入入称称为为入入队队列列，删删除除称称为为出出队队列列当当队队列列中中没没有有数数据据元元素素时时称称为为空空队队列列因因队队尾尾插插入入，队队头头删删除除，它它也也称称作作先先进进先先出出表表，即即FIFOFIFO（First First In First OutIn First Out）的结构的结构插入与删除分别称为入队与出队。插入与删除分别称为入队与出队。数据集合：数据集合：队列的数据集合可以表示为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队列抽象数据类型1.顺序队列的存储结构见73图3-7 队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表，和顺序表一样，顺序队列也是必须用一个向量空间来存放当前队列中的元素。由于队列的队头和队尾的位置是变化的，因而要设两个指针以分别指示队头和队尾元素在队列中的位置，它们的初始值地队列初始化时均应置为。入队时将新元素插入所指的位置，然后尾指针将加。出队时，删去所指的元素，然后头指针将加并返回被删元素。由此可见，当头尾指针相等时队列为空。在非空队列里，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一位置。顺序队列的动态示意图见73图3-73。3。3顺序队列 因为在入队和出队的操作中，头尾指针只增加不减小，致使被删除元素的空间永远无法重新利用。因此，尽管队列中实际的元素个数远远小于向量空间的规模，但也可能由于尾指针巳超出向量空间的上界而不能做入队操作。该现象称为假上溢。见教材上的例子 2.顺序队列的“假溢出”问题.1。顺序循环队列的基本原理 为充分利用向量空间。克服上述假上溢现象的方法是将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量，存储在其中的队列称为循环队列（Circular Queue)。在循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界（QueueSize-1）时，其加1操作的结果是指向向量的下界0。因为循环队列元素的空间可以被利用，除非向量空间真的被队列元素全部占用，否则不会上溢。因此，除一些简单的应用外，真正实用的顺序队列是循环队列。真正实用的顺序队列是循环队列。.。2。顺序循环队列的队空和队满判断问题由于入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时头尾指针均相等。因此，我们无法通过front=rear来判断队列“空”还是“满”。3。3。4顺序循环队列的表示和实现1-2。（1）少用一个存储单元：约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：rear所指的单元始终为空）队列满的判断条件为：(rear+1)%MaxQueueSize=front队列空的判断条件仍然为：rear=front解决问题的方法有三种（1）（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）循环队列的类型定义 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。顺序循环队列的实现（2）非空否QueueNotEmpty(SeqCQueueQ)intQueueNotEmpty(SeqCQueueQ)/*判断顺序循环队列Q非空否，非空时返回1，否则返回0*/if(Q.count!=0)return 1;else return 0;3。顺序循环队列实现（2）（3）入队列QueueAppend(SeqCQueue*Q,DataTypex)intQueueAppend(SeqCQueue*Q,DataTypex)/*把数据元素值x插入顺序循环队列Q的队尾，成功返回1，失败返回0*/if(Q-count0&Q-rear=Q-front)/*判断队列满否*/printf(“队列已满无法插入!n”)return0;elseQ-queueQ-rear=x;Q-rear=(Q-rear+1)%MaxQueueSize;Q-count+;return 1;3。顺序循环队列实现（3）（4）出队列QueueDelete(SeqCQueue*Q,DataType*d)intQueueDelete(SeqCQueue*Q,DataType*d)/*删除顺序循环队列Q的队头元素并赋给d，成功返回1，失败返回0*/if(Q-count=0)printf(“队列已空无数据元素出队列!n”);return0;else*d=Q-queueQ-front;Q-front=(Q-front+1)%MaxQueueSize;Q-count-;return 1;3。顺序循环队列实现（4）（5）取队头数据元素QueueGet(SeqCQueueQ,DataType*d)intQueueGet(SeqCQueueQ,DataType*d)/*取顺序循环队列Q的当前队头元素并赋给d，成功返回1，失败返回0*/if(Q.count=0)printf(“队列已空无数据元素可取!n”);return0;else*d=Q.queueQ.front;return1;3。顺序循环队列实现（5）链式存储结构的队列称作链式队列（链式队列没有头结点时更方便）1.链式队列的存储结构Front链式队列中结点的结构体可定义如下：typedef struct qnode DataType data;struct qnode*next;LQNode;为方便参数调用，通常把链式队列的队头指针和队尾指针也定义为如下的结构体类型：typedef struct LQNode*front;/*队头指针*/LQNode*rear;/*队尾指针*/LQueue;a0a1an-2an-1 3。3。5链式队列为方便参数调用，通常把链式队列的队头指针和队尾指针也定义为如下的结构体类型：typedefstructLQNode*front;/*队头指针*/LQNode*rear;/*队尾指针*/LQueue;3.3.5链式队列（2）(1）初始化QueueInitiate(LQueue*Q)void QueueInitiate(LQueue*Q)/*初始化链式队列Q*/Q-rear=NULL;/*定义初始队尾指针下标值*/q -front=NULL /*定义初始队头指针下标值*/（2）非空否QueueNotEmpty(LQueue Q)Int QueueNotEmpty(LQueue Q)/*判断链式队列Q非空否，非空返回1；否则返回0*/if(Q.front=NULL)return 0;else return 1;2。链式队列操作的实现(3)入队列QueueAppend(LQueue*Q,DataType x)int QueueAppend(LQueue*Q,DataType x)/*把数据元素值x插入链式队列Q的队尾，入队列成功返回1，否则返回0*/LQNode*p;if(p=(LQNode*)malloc(sizeof(LQNode)=NULL)printf(“内存空间不足!”);return 0;（3）入队列（1）p-data=x;p-data=x;p-next=NULL;p-next=NULL;if(Q-rear!=NULL)Q-rear-if(Q-rear!=NULL)Q-rear-next=p;next=p;Q-rear=p;Q-rear=p;if(Q-front=NULL)Q-front=p if(Q-front=NULL)Q-front=p;return 1;return 1;（3）入队列（2）int QueueDelete(LQueue*Q,DataType*d)/*删除链式队列Q的队头数据元素值到d，出队列成功返回1，否则返回0*/LQNode*p;if(Q-front=NULL)printf(“队列已空无数据元素出队列!n”);return 0;（4)出队列QueueDelete(LQueue*Q,DataType*d)else *d=Q-front-data;p=Q-front;Q-front=Q-front-next;if(Q-front=NULL)Q-rear=NULL;free(p);return 1;出队列（2）（5）取队头数据元素QueueGet(LQueue*Q,DataType*d)int QueueGet(LQueue*Q,DataType*d)/*取链式队列Q的当前队头数据元素值到d，成功返回1，否则返回0*/if(Q.front=NULL)printf(“队列已空无数据元素出队列!n”);return 0;else *d=Q.front-data;return 1;(5)取队头数据元素（6）撤销动态申请空间Destroy(SLNode*head)与单链表的操作集合相同，链式队列也要增加一个撤销动态申请空间的操作void Destroy(LQueue Q)LQNode*p,*p1;while(p!=NULL)p1=p;p=p-next;free(p1);教学目的：1.掌握串的基本概念 2.了解串抽象数据类型 3.掌握C语言的串函数 4.熟练掌握串的存储结构 5.掌握串的表示和实现 教学重点：1.串的存储结构 2.串的表示和实现 教学难点：串基本操作的实现算法 教学内容：第四章串 串被认为是一种特殊线性表元素为文字符号的线性表。串是由零个或多个字符构成的有限序列，一般记为s=“a0，a1，an-1”(n0)其中，s代表串的名称，用双引号括起来的部分（不含该双引号 本身）为串值（即字符序列），每个ai为一个及其它符号）。串值中字符个数（即n）称为串长，长度为0的串称为空串空串。串中任意个连续字符构成的部分称为该串的子串子串，包含子串的串相对该子串称为主串主串。串中某字符在串中出现的序号为该字符在串中的字符位置，子串中第 1个字符在串中的序号称为该子串在该串中的位置。4.1.1串及其基本概念下面是几个串的例子：s1=ab123/*长度为5的串*/s2=100/*长度为3的串*/s3=/*含两个空格字符的串，长度为2*/s4=/*空串，长度为0*/字符。字符是计算机可识别的任意符号（字母、数字串中的26个字母字符是有大小写之分的，称两个串是相等相等的，当且仅当这 两个串中的所有字符完全相等见例题90注意：串和字符是两个不同的概念串不仅要存储字符，还要存储该串的长度数据；字符只需要存储字符，不需要存储长度数据4。1。1（二）数据集合：数据集合：串的数据集合可以表示为字符序列s s0 0,s,s1 1,s sn n-1-1，每个数据元素的数据类型为每个数据元素的数据类型为字符类型字符类型 操作集合：操作集合：（1）初始化Initiate(S)：初始化串S（2）赋值Assign(S,T)：把串T的值赋给串S （3）求长度Length（S）：求串S的长度S1=”I am a student”,Length(S1)=14（4）比较Compare（S，T）：比较串S和串T的ASC码值的大小，有大于、等于、小于三种情况3。1。2串的抽象数据类型（5）插入Insert（S,pos,T）:若参数满足约束条件0posLength（S），则在串S的第 pos个字符前插入串T，串S的新长度为Length（S）Length（T）；若参数不满足约束条件，则不能插入（6）删除Delete（S，pos，len）：若参数满足约束条件0posLength（S）-1，len1和poslenLength（S）-1，则删除串S中从第pos个字符开始，长度为len个的子串（7）取子串SubString(S,pos,len)：若若参数满足约束条件0posLength（S）-1，len1和poslenLength（S）-1，则取串S中从第pos个字符开始，长度为len个的子串（8）查找子串Search（S，start，T）：在主串S中，从位置start开始查找是否存在子串T，若存在，则查找成功；否则，查找失败（9）替换子串Replace（S，start，T，V）：找到子串后，用子串V替换子串T操作集合（5。6。7。8。9）C语言用字符数组存储串，串的长度是不定的，C语言解决串的长度不定的方法是在串的末尾自动添加一个字符0作为串的结束标志假设已有如下C语言变量定义语句：char s1=”I am a student”;char s220=”teacher”;char s3=”student”;int result;char s420,*p;3.1.3c语言串函数（1）求长度int strlen(char*str):printf(“%dn”,strlen(s2);/*输出7*/（2）拷贝char*strcpy(char*str1,char*str2):strcpy(s4,s2);printf(“%sn”,s4)/*输出teacher*/（3）比较int strcmp(char*str1,char*str2):result=strcmp(s2,s3);/*s2s3*/printf(“%dn”,result);/*输出1*/result=strcmp(s2,s2);/*s2=s3*/printf(“%dn”,result);/*输出0*/result=strcmp(s3,s2)/*s3 length=0;4。3串基本操作的实现算法 /*在串S的pos位置插入子串T*/int i;if(pos length+T.length MaxSize)printf(“数组空间不足无法插入！”);return 0;（2）插入子串操作int Insert(String*S,int pos,String T）（2）插入子串操作（1）else for(i=S-length 1;i=pos;i-)S-str i+T.length =S-str i;/*依次后移数据元素*/for(i=0;i str pos+i =T.str i ;/*插入*/S-length=S-length+T.length;/*产生新的串长度值*/return 1;（2）插入子串操作（2）int Delete(String*S,int pos,int len)/*删除串S从pos位置开始长度为len的子串值*/int i;if(S-length=0)printf(“数组中未存放字符无元素可删！n”);return 0;else if(pos 0 len S-length)（3）删除子串操作（1）printf(“参数pos和len不合法”);return 0;else for(i=pos+len;i length 1;i+)S-str i len =S-str i ;/*依次前移数据元素*/S-length=S-length len;/*产生新的串长度值*/return 1;(3)删除子串操作（2）int SubString(String S,int pos,int len,String*T)/*取串S从pos位置开始长度为len的子串值赋给串T*/int i;if(pos 0 len S.length)printf(“参数pos和len出错”);return 0;else for(i=0;i str i =S.str pos+i ;/*给子串T赋值*/T-length=len;/*给子串T的长度域赋值*/return 1;4.3.(4)取子串操作串的动态数组结构体定义为：typedefstructchar*str;intmaxLength;intlength;DString;.动态数组下串的基本操作要增加初始化操作和撤销操作3.动态数组下串基本操作的实现算法用来建立存储串的动态数组空间以及给相关的数据域赋值voidInitiate(DString*S,intmax,cha