清华大学数据结构讲义(修改)

数据结构计算机系第一章绪论1.1什么是数据结构1.2根本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分1.4.1算法1.4.2算法设计的要求1.4.3算法效率的度量1.4.4算法的存储空间的需求第一章绪论1.1数据结构讨论的范畴1.2根本概念1.3算法及其量度NiklausWirthAlgorithm+Datastructures=programs程序设计：为计算机处理问题编制一组指令集算法：处理问题的策略数据结构：问题的数学模型例如：数值计算的程序设计问题结构静力分析计算：线性方程组全球天气预报：环流模式方程

1.1数据结构讨论的范畴非数值计算的程序设计问题例1。求一组〔N个〕整数中的最大值算法：通过两两比较求出最大值模型：？例2。计算机对弈算法：对弈的规那么和策略模型：？例3。足协的数据库管理算法：需要的管理工程，管理界面，用户界面模型：？通过上述例子概括地说：数据结构描述现实世界实体的数学模型〔非数值计算〕及其上的操作在计算机中的表示和实现。

1.1数据结构讨论的范畴一、数据与数据结构数据：所有能被输入到计算机中，且被计算机处理的符号的集合.是计算机操作对象的总称.数据元素：数据中的一个“个体〞，数据结构中讨论的根本单位.数据项：数据结构中讨论的最小单位，数据元素是数据项的集合.例如：运发动〔数据元素〕

姓名俱乐部名称出生日期参加日期职务业绩1.2数据结构的根本概念数据结构：带结构的数据元素的集合例如1：一个含12位数的十进制数可以用三个4位的十进制表示。3212，3456，9876a1(3212),a2(3456),a3(9876)在a1,a2,a3之间存在“次序〞关系<a1,a2>,<a2,a3>3212,3456,9876345632129876a1a2a3a2a1a3例如2：2行3列的二维数组{a1,a2,a3,a4,a5,a6}

行的次序关系：Row={<a1,a2>,<a2,a3>,<a4,a5>,<a5,a6>}列的次序关系：Col={<a1,a4>,<a2,a5>,<a3,a6>}a1a3a5a1a2a3a2a4a6a4a5a6又如：一维数组{a1,a2,a3,a4,a5,a6}中存在次序关系：{<a(i),a(i+1)>|i=1,2,3,4,5}a1a2a3a4a5a6数据的逻辑结构可归结为以下四类：线性结构：一对一的关系树形结构：一对多的关系图状结构：多对多的关系集合结构：同属于一个类型，无其他关系数据结构的形式定义为：数据结构是一个二元组Data_Structures=(D,S)其中：D是数据元素的有限集，S是D上关系的有限集〔强调数据逻辑上的关系〕二.数据的存储结构：逻辑结构在计算机中的表示〔在存储器中的映象〕1.数据元素的映象方法：用二进制位〔BIT〕的位串表示数据元素〔321)10=(501)8=〔101000001)2A=0101=〔001000001〕2.关系的映象方法：〔<x,y>表示〕〔1〕顺序映象：以存储位置的相邻表示后继关系y的存储位置和x的存储位置之间差一个常量C，C是一个隐含值，整个存储结构中只含数据元素本身的信息。

XY〔2〕链式映象：以附加信息〔指针〕表示后继关系需要用一个和X在一起的附加信息指示Y的存储位置

三.数据类型：在用高级程序语言编写的程序中，必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。是一个值的集合和定义在此集合上的一组操作的总称也可以看成是一个数据结构和定义在这个数据结构上操作的总称。YX四.抽象数据类型一个数据模型及定义在这个模型上的一组操作。2个重要的特点：〔1〕数据抽象：处理实体时，强调其本质特征，其所能完成功能以及它和外部用户的接口。〔2〕数据封装：将实体的外部特性和其内部实现细节别离，并对外部用户隐藏其内部细节。例如：抽象数据类型复数的定义：ADTCOMPLEX{数据对象：D={e1,e2|e1,e2属于实数}数据关系：R1={<e1,e2>|e1是复数的实数局部e2是复数的虚数局部}

根本操作：1。Initcomplex(&z,v1,v2)操作结果：构造复数Z，其实部和虚局部别赋以参数V1，V2的值。2。DESTROYCOMPLEX〔&z〕操作结果：复数Z被销毁。3。GETREAL〔Z，&realpart〕初始条件：复数已存在操作结果：用realpart返回复数Z的实部值.4.Getimag(z,&imagpart)初始条件：复数已存在操作结果：用imagpart返回复数Z的虚部值5.Add(z1,z2,&sum)初始条件：z1,z2是复数操作结果：用sum返回两个复数z1,z2的和值。}抽象数据〔ADT〕两个重要特征：1。数据抽象2。数据封装抽象数据类型的描述方法：可用〔D，S，P〕三元组表示其中：D是数据对象S是D上的关系集P是对D的根本操作集1.3算法和算法的衡量一、算法算法是为了解决某类问题而规定的一个有限长的操作序列。一个算法必须满足以下5个重要特性：1.有穷性:对任一组合法输入值，执行有穷步骤之后一定能结束。2.确定性：不管何种情况下，不管执行多少遍得到同样的结果。3.可行性：算法中的所有操作都必须足够根本，可以通过已经实现的根本操作运算实现之。4.有输入：作为算法加工的对象的量值，通常表达为算法中的一组变量。5.有输出：与输入有确切对应关系的量值。1.3算法和算法的衡量二、算法设计的原那么设计算法时，考虑以下目标：1。正确性：不含语法错误，能得到满足要求的结果。2。可读性3。健壮性：当输入的数据非法时，算法应当恰当地作出反映，或相应进行处理，而不是莫名其妙输出结果。4。高效率与低存储量的要求1.3算法和算法的衡量三、算法效率的衡量方法和准那么主要讨论：两种衡量算法效率的方法：〔1〕事后统计法缺点：1。必须执行程序2。其他因素掩盖其本质〔2〕事前分析估算法和算法执行时间相关的因素：1。算法选用的策略2。问题的规模3。编写程序的语言4。编译程序产生的机器代码的质量5。计算机执行指令的速度

一般情况下，算法中根本操作重复执行的次数是问题规模n的某个函数，算法的时间量度记作T(n)=O(f(n))称作算法的渐近时间复杂度。算法=控制结构+原操作〔固有数据类型的操作〕算法的执行时间=〔求和〕原操作i的执行次数*原操作i的执行时间算法的执行时间与原操作执行次数之和成正比。例1。For(i=1;i<=n;++i)for(j=1;j<=n;++j)c[i][j]=0;for(k=1;k<=n;++k)c[i][j]+=a[i][j]*b[i][j];根本操作：乘法操作时间复杂度：O〔n3〕频度：是指该语句重复执行的次数例２{++x;s=0;}将x自增看成是根本操作，那么语句频度为１，即时间复杂度为Ｏ(1)如果将s=0也看成是根本操作，那么语句频度为２，其时间复杂度仍为Ｏ(1)，即常量阶。例３、for(i=1;i<=n;++i){++x;s+=x;}语句频度为：2n其时间复杂度为：O(n)即时间复杂度为线性阶。例４、for(i=1;i<=n;++i)for(j=1;j<=n;++j){++x;s+=x;}语句频度为：2n2其时间复杂度为：O(n2)即时间复杂度为平方阶。定理：假设A(n)=amnm+am-1nm-1+…+a1n+a0是一个m次多项式，那么A(n)=O(nm)证略.例５.for(i=2;i<=n;++i)for(j=2;j<=i-1;++j){++x;a[i][j]=x;}1+2+3+…+n-2=(1+n-2)×(n-2)/2=(n-1)(n-2)/2=n2-3n+2∴时间复杂度为O(n2)即此算法的时间复杂度为平方阶.一个算法时间为O(1)的算法，它的根本运算执行的次数是固定的。以下六种计算算法时间的多项式是最常用的。其关系为：O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)指数时间的关系为：O(2n)<O(n!)<O(nn)

当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。有的情况下，算法中根本操作重复执行的次数还随问题的输入数据集不同而不同。例如：Voidbubble-sort(inta[]，intn)for(I=n-1;change=TURE;I>1&&change;--I){change=false;for(j=0;j<I;++j)if(a[j]>a[j+1]){a[j]←→a[j+1];change=TURE}}最好情况：0次最坏情况：1+2+3+…+n-1=n(n-1)/2平均时间复杂度为:O(n2)

1.4算法的存储空间需求空间复杂度:算法所需存储空间的度量，记作:S(n)=O(g(n))其中n为问题的规模(或大小)算法的存储量包括：1.输入数据所占空间2.程序本身所占空间3.辅助变量所占空间假设输入数据所占空间只取决于问题本身，和算法无关，那么只需要分析除输入和程序之外的辅助变量所占额外空间。假设所需额外空间相对于输入数据量来说是常数，此算法为原地工作，假设所需存储量依赖于特定的输入，那么按最坏情况考虑.例1、分析以下程序段的时间复杂度for(i=1;i<n;i++){y=y+1;for(j=0;j<=(2*n);j++)x++;}时间复杂度为T〔n〕=2n2-n-1=O(n2)例2、分析以下程序段的时间复杂度I=1;while(I<=n)I=I*2;例3、分析以下程序段的时间复杂度a=0;b=1;For(i=1;i<=n;i++){s=a+b;b=a;a=s;}

第二章线性表2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.3.1线性链表2.3.2循环链表2.3.3双向链表2.4一元多项式的表示及相加抽象数据类型线性表见P19页2.1线性表的逻辑结构线性表(LinearList)：由n(n≧)个数据元素(结点)a1，a2，…an组成的有限序列。其中数据元素的个数n定义为表的长度。当n=0时称为空表，常常将非空的线性表(n>0)记作：(a1，a2，…an)这里的数据元素ai(1≦i≦n)只是一个抽象的符号，其具体含义在不同的情况下可以不同。例1、26个英文字母组成的字母表〔A，B，C、…、Z〕例2、某校从1978年到1983年各种型号的计算机拥有量的变化情况。〔6，17，28，50，92，188〕例3、学生健康情况登记表如下：姓名学号性别年龄健康情况王小林790631男18健康陈红790632女20一般刘建平790633男21健康张立立790634男17神经衰弱……..……..…….…….…….例4、一副扑克的点数〔2，3，4，…，J，Q，K，A〕从以上例子可看出线性表的逻辑特征是：在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2；有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋an-1；其余的内部结点ai(2≦i≦n-1)都有且仅有一个直接前趋ai-1和一个直接后继ai+1。线性表是一种典型的线性结构。数据的运算是定义在逻辑结构上的，而运算的具体实现那么是在存储结构上进行的。抽象数据类型的定义为：P19

算法2.1例2-1利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=A∪B。voidunion(List&La，ListLb){La-len=listlength(La);Lb-len=listlength(Lb);for(I=1;I<=lb-len;I++){getelem(lb，I，e);if(!locateelem(la，e，equal))listinsert(la，++la-en，e)}}

例2-2巳知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。此问题的算法如下：voidmergelist(listla，listlb，list&lc)initlist(lc);I=j=1;k=0;la-len=listlength(la);lb-len=listlength(lb);while((I<=la-len)&&(j<=lb-len)){

getelem(la，I，ai);getelem(lb，j，bj);if(ai<=bj){listinsert(lc，++k，ai);++I;}else{listinsert(lc，++k，bj);++j;}}while(I<=la-len){getelem((la，I++，ai);listinsert(lc，++k，ai);}while(j<=lb-len){getelem((lb，j++，bj);listinsert(lc，++k，bi);}}2.2线性表的顺序存储结构2.2.1线性表把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。假设线性表的每个元素需占用l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。那么线性表中第I+1个数据元素的存储位置LOC(ai+1)和第i个数据元素的存储位置LOC(aI)之间满足以下关系：LOC(ai+1)=LOC(ai)+c线性表的第i个数据元素ai的存储位置为：LOC(ai)=LOC(a1)+(I-1)*c

由于C语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。又因为除了用数组来存储线性表的元素之外，顺序表还应该用一个变量来表示线性表的长度属性，所以我们用结构类型来定义顺序表类型。

#defineListSize100#definelistincrement10typedefstruc{elemtype*elem;/*数组指针elem指示线性表的基地址*/intlength;//当前长度intlistsize//当前分配的存储容量}Sqlist;(称为线性表)2.2.2顺序表上实现的根本操作在顺序表存储结构中，很容易实现线性表的一些操作，如线性表的构造、第i个元素的访问。注意：C语言中的数组下标从“0〞开始，因此，假设L是Sqlist类型的顺序表，那么表中第i个元素是L.elem[i-1]。以下主要讨论线性表的插入和删除两种运算。1、插入线性表的插入运算是指在表的第i(1≦i≦n+1个位置上，插入一个新结点e，使长度为n的线性表(a1，…ai-1，ai，…，an)变成长度为n+1的线性表(a1，…ai-1，x，ai，…，an)算法2.3VoidInsertList(Sqlist*L，elemTypex，inti){intj;if(i<1||i>L.length+1)printf(“Positionerror〞);returnERRORif(L.length>=ListSize){newbase=(elemtype*)realloc(L.elem,(L.listsize+listincrement)*sizeof(elemtype));if(!newbase)exit(overflow);L.elem=newbase;L.listsize+=listincrement;}q=&(L.elem[i-1]);for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;*q=e;++L.length;returnOK;}

现在分析算法的复杂度。这里的问题规模是表的长度，设它的值为。该算法的时间主要化费在循环的结点后移语句上，该语句的执行次数〔即移动结点的次数〕是。由此可看出，所需移动结点的次数不仅依赖于表的长度，而且还与插入位置有关。当时，由于循环变量的终值大于初值，结点后移语句将不进行；这是最好情况，其时间复杂度O〔1〕；当=1时，结点后移语句将循环执行n次，需移动表中所有结点，这是最坏情况，其时间复杂度为O〔n〕。由于插入可能在表中任何位置上进行，因此需分析算法的平均复杂度假设在第i个元素之前插入的概率为Pi，那么在长度为n的线性表中插入一个元素所需移动元素次数的期望值为：

假设假定在线性表中任何一个位置上进行插入的概率是相等的，那么移动元素的期望值为：

2、删除线性表的删除运算是指将表的第i(1≦i≦n)结点删除，使长度为n的线性表：(a1，…ai-1，ai，ai+1…，an)，变成长度为n-1的线性表(a1，…ai-1，ai+1，…，an)VoiddeleteList(Sqlist&L，intI,elemtype&e){intj;if(i<1||i>l.length)printf(“Positionerror〞);returnERROR;p=&(L.elem[i-1]);e=*p;q=L.elem+L.length-1;for(++p;p<=q;++p)*(p-1)=*p;--L.length;returnok;}

考虑平均的情况：假设删除第I个元素的概率为QI；那么在长度为N的线性表中删除一个元素所需移动元素次数的期望值为：假设假定在线性表中任何一个位置上进行删除的概率都是相等的，那么移动元素的期望值为：

2.3线性表的链式表示和实现一、单链表用一组地址任意的存储单元存放线性表中的数据元素。以元素〔数据元素的映象〕+指针〔指示后继元素存储位置〕=结点〔表示数据元素〕以“结点的序列〞表示线性表---------称做链表

………

a1a2

an以线性表中第一个数据元素AI的存储地址作为线性表的地址。称作线性表的头指针。

二、结点和单链表的C语言描述typedefstructLnode{Elemtypedata;//数据域structLnode*next;//指针域}Lnode,*linklist;三、单链表操作的实现线性表的操作GetElem(L,i,&e)在链表中的实现：根本操作为：使指针P始终指向线性表中第j个数据元素.

StatusGetElem_L(LinklistL,inti,elemtype&e){p=L->next;j=1;while(p&&j<i){p=p->next;++j;}if(!p||j>i)returnerror;e=p->data;returnok;}//GetElem_L算法的时间复杂度为：O(Listlength(L))线性表的操作ListInsert(&L,i,e)在链表中的实现：根本操作作为：找到线性表中第i-1个结点，修改其指向后继的指针statusListInsert_L(LinkListL,inti,ElemTypee){p=L;j=0;while(p&&j<i-1){p=p->next;++j}if(!p||j>i-1)returnerror;s=(LinkList)malloc(sizeof(LNode));s->data=e;s->next=p->next;p->next=s;returnok;}算法的时间复杂度为：O(Listlength(L))线性表的操作ListDelete(&L,i,&e)在链表中的实现：根本操作为：找到线性表中第i-1个结点，修改其指向后继的指针statusListDelete_L(LinkListL,inti,ElemTypee){p=L;j=0;while(p->next&&j<i-1){p=p->next;++j}if(!(p->next)||j>i-1)returnerror;q=p->next;p->next=q->next;e=q->data;free(q);returnok;}算法的时间复杂度为：O(Listlength(L))链表的建立：VoidCreatelist_L(LinkList&L,intn){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;}}算法的时间复杂度为：O(Listlength(L))2.3.2循环链表循环链表时一种头尾相接的链表。其特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。单循环链表：在单链表中，将终端结点的指针域NULL改为指向表头结点的或开始结点，就得到了单链形式的循环链表，并简单称为单循环链表。为了使空表和非空表的处理一致，循环链表中也可设置一个头结点。这样，空循环链表仅有一个自成循环的头结点表示。如以下图所示：

a1an

….head⑴非空表⑵空表在用头指针表示的单链表中，找开始结点a1的时间是O(1)，然而要找到终端结点an，那么需从头指针开始遍历整个链表，其时间是O(n)在很多实际问题中，表的操作常常是在表的首尾位置上进行，此时头指针表示的单循环链表就显得不够方便.如果改用尾指针rear来表示单循环链表，那么查找开始结点a1和终端结点an都很方便，它们的存储位置分别是(rear–>next)—>next和rear，显然，查找时间都是O(1)。因此，实际中多采用尾指针表示单循环链表。由于循环链表中没有NULL指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断p或p—>next是否为空，而是判断它们是否等于某一指定指针，如头指什或尾指针等。例、在链表上实现将两个线性表(a1，a2，a3，…an)和(b1，b2，b3，…bn)链接成一个线性表的运算。linklistconnect(linklistheada，linklistheadb){linklistp=heada—>next;heada—>next=(headb—next)—>nextfree(headb—>next);headb—>next=p;return(headb);}2.3.3双链表双向链表(Doublelinkedlist):在单链表的每个结点里再增加一个指向其直接前趋的指针域prior。这样就形成的链表中有两个方向不同的链，故称为双向链表。形式描述为：

typedefstructdlistnode{datatypedata;strucdlistnode*prior，*next;}dlistnode;typedefdlistnode*dlinklist;dlinklisthead;和单链表类似，双链表一般也是由头指针唯一确定的，增加头指针也能使双链表上的某些运算变得方便，将头结点和尾结点链接起来也能构成循环链表，并称之为双向链表。设指针p指向某一结点，那么双向链表结构的对称性可用下式描述：(p—>prior)—>next=p=(p—>next)—>prior即结点*p的存储位置既存放在其前趋结点*(p—>prior)的直接后继指针域中，也存放在它的后继结点*(p—>next)的直接前趋指针域中。双向链表的前插操作算法如下：voiddinsertbefor(dlistnode*p，datatypex){dlistnode*q=malloc(sizeof(dlistnode));q—>data=x;q—>prior=p—>prior;q—>next=p;p—>prior—>next=q;p—>prior=q;}voidddeletenode(dlistnode*p){p–>prior–>next=p–>next;p–>next–>prior=p–>prior;free(p);}

注意：与单链表的插入和删除操作不同的是，在双链表中插入和删除必须同时修改两个方向上的指针。上述两个算是法的时间复杂度均为O(1)。顺序存储的三个优点：(1)方法简单，各种高级语言中都有数组，容易实现。(2)不用为表示结点间的逻辑关系而增加额外的存储开销。(3)顺序表具有按元素序号随机访问的特点。两个缺点：(1)

在顺序表中做插入删除操作时，平均移动大约表中一半的元素，因此对n较大的顺序表效率低。(2)需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。链表的优缺点１．基于存储的考虑:链表不用事先估计存储规模，但链表的存储密度较低。２．基于运算的考虑：链表中按序号访问的时间性能O(n)３．基于环境的考虑：顺序表容易实现，任何高级语言中都有数组类型，链表的操作是基于指针的 通常“较稳定〞的线性表选择顺序存储，而频繁做插入删除的即动态性较强的线性表宜选择链式存储。用单链表表示一元多项式

将单链表的每个结点对应着一元多项式中的一个非零项，它由三个域组成，分别表示非零项的系数、指数和指向下一个结点的指针。 设两个一元多项式为:求此两一元多项式之和C(x)=A(x)+B(x)。运算规那么将二个一元多项式中所有指数相同项的系数相加，相加后，假设和不为零，那么构成“和一元多项式〞中的一项;假设和为零，那么“和一元多项式〞中无此项；所有指数不相同的项均抄到“和一元多项式〞中。

第三章栈和队列3.1栈3.1.1抽象数据类型栈的定义3.1.2栈的表示和实现3.2栈的应用举例3.2.1数制转换3.2.2括号匹配的检验3.2.4行编辑程序3.2.5迷宫求解3.2.5表达式求值3.1栈3.1.1栈(stack) 栈〔stack〕是一种只允许在一端进行插入和删除的线性表，它是一种操作受限的线性表。在表中只允许进行插入和删除的一端称为栈顶〔top〕，另一固定端称为栈底(bottom)。栈的插入操作通常称为入栈或进栈(push)，而栈的删除操作那么称为出栈或退栈(pop)。 按照后进先出〔LIFO，lastinfirstout〕的原那么组织数据，因此栈也被称为“后进先出〞的线性表。栈的根本操作：1.initstack(&s)操作结果：初始化一个空栈2.destroystack(&s)初始条件：栈S已存在操作结果：栈S被销毁3.stackempty(s)初始条件：栈S已存在操作结果：假设栈S为空栈那么返回TRUE，否那么FALSE4.Stacklength(S)初始条件：栈S已存在操作结果：返回S的元素个数，即栈的长度5.GetTop(S,&e)初始条件：栈S已存在且非空操作结果：用e返回S的栈顶元素6.ClearStack(&S)初始条件：栈S已存在操作结果：将S清为空栈7。Push(&S,e)初始条件：栈S已存在操作结果：插入元素e为新的栈顶元素8.Pop(&s,&e)初始条件：栈S已存在且非空操作结果：删除S的栈顶元素，并用e返回其值3.1.2顺序栈由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。因此，可用数组来实现顺序栈。因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，故需用一个整型变量top来指示当前栈顶的位置，通常称top为栈顶指针。因此，顺序栈的类型定义只需将顺序表的类型定义中的长度属性改为top即可。顺序栈的类型定义如下：#defineStackSize100#definestackincrement10typedefstruct{selemtype*base;selemtype*top;intstacksize;}sqstack;例、一叠书或一叠盘子。

栈的抽象数据类型的定义如下：P44

anan-1a2a1……栈顶栈底3、判断栈满intstackfull(seqstack*s){return(s–>top==stacksize-1);}4、进栈voidpush(seqstack*s，datatypex){if(stackfull(s))error(“stackoverflow〞);s–>data[++s–>top]=x;}1、置空栈voidinitstack(seqstack*s){s–>top=-1;}2、判断栈空intstackempty(seqstack*s){return(s–>top==-1);}5、退栈datatypepop(seqstack*s){if(stackempty(s))error(“stackunderflow〞);x=s–>data[top];s–>top--;return(x)//return(s–>data[s–>top--]);}

6、取栈顶元素Datatypestacktop(seqstack*s){if(stackempty(s)error(“stackisenpty〞);returns–>data[s–>top];}

3.1.3链栈栈的链式存储结构称为链栈，它是运算是受限的单链表，克插入和删除操作仅限制在表头位置上进行.由于只能在链表头部进行操作，故链表没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。链栈的类型说明如下：typedefstructstacknode{datatypedatastructstacknode*next}stacknode;3.2栈的应用举例由于栈结构具有的后进先出的固有特性，致使栈成为程序设计中常用的工具。以下是几个栈应用的例子。3.2.1数制转换十进制N和其它进制数的转换是计算机实现计算的根本问题,其解决方法很多,其中一个简单算法基于以下原理:N=(ndivd)*d+nmodd(其中:div为整除运算,mod为求余运算)例如(1348)10=(2504)8，其运算过程如下：nndiv8nmod8134816841682102125202voidconversion(){initstack(s);scanf(“%〞,n);while(n){push(s,n%8);n=n/8;}while(!Stackempty(s)){pop(s,e);printf(“%d〞,e);}}3.2.2括号匹配的检验假设表达式中充许括号嵌套,那么检验括号是否匹配的方法可用“期待的急迫程度〞这个概念来描述。例：〔[]〔〕〔[][]〕〕以下为不正确的格式：[〔]〕或者〔[〔〕〕或者〔〔〕]〕例如：考虑以下括号序列：[〔[][]〕]算法的设计思想：〔1〕凡出现左括弧，那么进栈；〔2〕凡出现右括弧，首先检查栈是否空，假设栈空，那么说明“右括弧〞多了，否那么和栈顶元素比较，假设匹配，那么“左括弧出栈〞，否那么不匹配。〔3〕表达式检验结束时，假设栈空，那么匹配正确，否那么说明“左括弧〞多了。

Statusmatching(string&exp)Intstate=1;While(i<=length(exp)&&state){switchofexp[i]{case“(〞:{push(S,exp[i]);i++;break;}case“)〞:{if(notstackempty(S)&&GetTop(S)=“(〞){Pop(S,e);i++;}elsestate=0;break;}……}

3.2.3行编辑程序在编辑程序中，设立一个输入缓冲区，用于接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入错误，并在发现有误时可以及时更正。假设从终端接受了这样两行字符：whli##ilr#e(s#*s)outcha@putchar(*s=#++)实际有效的是以下两行：while(*s);putchar(*s++);

行编辑程序算法如下:voidlineedit(){initstack(s);ch=gether();while(ch!=eof){while(ch!=eof&&ch!=‘\n’){switch(ch){case‘#’:pop(s,c);break;case‘@’:clearstack(s);break;default:push(s,ch);break;}ch=getchar();}将从栈底到栈顶的字符传送至调用过程的数据区；clearstack(s);if(ch!=eof)ch=gethar();}destroystack(s);}3.2.4迷宫求解

入口出口3.2.5表达式求值问题假设求4+2*3-10/2用栈实现从原表达式求解的规律为：1。设立操作数栈；运算符栈；2。设表达式的结束符为“#〞，设运算符栈的栈底为“#〞；3。假设当前字符是操作数，那么直接发送给操作数栈；4。假设当前运算符的优先数高于栈顶运算符，那么进栈；5。否那么，退出栈顶运算符发送给操作数栈；见书P54页3。3实现递归当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成3件事情：1。将所有的实际参数、返回地址等信息传递给被调用函数保存2。为被调用函数的局部变量分配存储区3。将控制转移到被调用函数的入口从被调用函数返回调用函数之前，应该完成：1。保存被调函数的计算结果；2。释放被调函数的数据区；3。依照被调函数保存的返回地址将控制转移到调用函数；3.4队列3.4.1抽象数据类型队列的定义队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦称作先进先出(FirstInFirstOut)的线性表，简称FIFO表。当队列中没有元素时称为空队列。在空队列中依次参加元素a1,a2,…an之后，a1是队头元素，an是队尾元素。显然退出队列的次序也只能是a1,a2,…an，也就是说队列的修改是依先进先出的原那么进行的。以下图是队列的示意图：

a1a2…an

出队入队队头队尾队列的抽象数据定义见书Ｐ593.4.2

顺序队列

顺序存储的队列称为顺序队列。因为队的队头和队尾都是活动的，因此，除了队列的数据区外还有队头、队尾两个指针。 顺序队列的类型定义如下：defineMAXSIZE1024/*队列的最大容量*/typedefstruct{datatypedata[MAXSIZE];/*队员的存储空间*/intrear,front;/*队头队尾指针*/}sequeue;sequeue*sq;/*定义一个指向队的指针变量：*/front=rear=-1front=-1rear=2front=5rear=8front=5rear=9(a)空队(b)有3个元素(c)一般情况(d)假溢出现象队列操作示意图 队头指针指向队头元素前面一个位置，队尾指针指向队尾元素。1、 置空队列那么为：sq->front=sq->rear=-1;2、 入队操作：在不考虑溢出的情况下，队尾指针加1，指向新位置后，元素入队。 操作如下： sq->rear++; sq->data[sq->rear]=x;3、 出队操作：在不考虑队空的情况下，队头指针加1，表明队头元素出队。 操作如下：sq->front++; x=sq->data[sq->front];/*原队头元素送x中*/4、 队中元素的个数：m=(sq->rear)-(q->front); 队满时：m=MAXSIZE；队空时：m=0。 解决假溢出的方法之一是将队列的数据区data[0..MAXSIZE-1]看成头尾相接的循环结构，头尾指针的关系不变，将其称为“循环队列〞。 尾相接的循环结构，入队时的队尾指针加1操作修改为：

sq->rear=(sq->rear+1)%MAXSIZE;

出队时的队头指针加1操作修改为：

sq->front=(sq->front+1)%MAXSIZE;front=4rear=8front=-1rear=2front=5rear=8front=5rear=9(a)有4个元素(b)队满(c)队空(d)队满循环队列操作示意图新问题：“队满〞和“队空〞的条件是相同的设MAXSIZE=10，循环队列操作示意图新问题：“队满〞和“队空〞的条件是相同的解决： 方法一：附设一个存储队列元素个数的变量如num，当num==0时队空，当num==MAXSIZE时为队满。 方法二：少用一个元素空间，把图〔d〕所示的情况就视为队满，此时的状态是队尾指针加1就会从后面赶上队头指针。这种情况下队满的条件是：(rear+1)%MAXSIZE==front，也能和空队区别开。循环队列的类型定义及根本运算(少用一个元素空间)⑴置空队Setnull(sq)Sequeue*sq;{sq->front=MAXSIZE-1;q->rear=MAXSIZE-1;}(2)判队空intEMPTY(sequeue*sq){if(sq->rear==sq->front) return1;else return0;}DatatypeFRONT(sequeue*sq){ifEMPTY(sq){print(“队列是空〞)；return0;}elsereturn(sq->front+1)%MAXSIZE}(3)取队头元素intENQUEUE(Sequeue*q,datatypex){if(sq->front==(sq->rear+1)%MAXSIZE){printf(＂队满＂);return0;/*队满不能入队*/}else {sq->rear=(sq->rear+1)%MAXSIZE; sq->data[sq->rear]=x; return1;/*入队完成*/ }}(4)入队DatatypeDEQUEUE(sequeue*q){if(EMPTY(sq)){printf(＂队空＂)；return–1;/*队空不能出队*/}else{sq->front=(sq->front+1)%MAXSIZE;return(sq->data[sq->front]);/*返回队头元素*/}}(5)出队c_SeQueue*Init_SeQueue(){q=malloc(sizeof(c_SeQueue));q->front=q->rear=MAXSIZE-1;q->num=0;returnq;}循环队列的类型定义及根本运算(附设一个存储队中元素个数的变量)typedefstruct{datatypedata[MAXSIZE];/*数据的存储区*/intfront,rear;/*队头队尾指针*/intnum;/*队中元素的个数*/}c_SeQueue;/*循环队*/⑴置空队

intIn_SeQueue(c_SeQueue*q,datatypex){ if(num==MAXSIZE) { printf(＂队满＂); return–1;/*队满不能入队*/ } else { q->rear=(q->rear+1)%MAXSIZE; q->data[q->rear]=x; num++; return1;/*入队完成*/ }}⑵

入队intOut_SeQueue(c_SeQueue*q,datatype*x){if(num==0){ printf(＂队空＂)； return–1;/*队空不能出队*/}else{ q->front=(q->front+1)%MAXSIZE; *x=q->data[q->front];/*读出队头元素*/ num--; return1;/*出队完成*/ }}⑶

出队intEmpty_SeQueue(c_SeQueue*q){if(num==0) return1;else return0;}⑷判队空3.4.3链队列队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。显然仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表的最后一个结点。于是，一个链队列由一个头指针唯一确定。和顺序队列类似，我们也是将这两个指针封装在一起，将链队列的类型LinkQueue定义为一个结构类型：typedefstructQNode{QElemTypedata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;3.3.3链队列 链式存储的队列称为链队列。用单链表来实现链队列，根据队的FIFO原那么，为了操作上的方便，我们分别需要一个头指针和尾指针，typedefintdatatype;typedefstructnode{ datatypedata;structnode*next;}linklist;typedefstruct{linklist*front,*rear;}linkqueue;linkqueue*q；

intempty(q)linkqueue*q;{if(q->front==q->rear)return(TRUE);elsereturn(FALSE);}1、置空队SETNULL(q)linkqueue*q;{q->front=malloc(sizeof(linklist));q->front->next=NULL;q->rear=q->front;}2、判队空datatypeFRONT(q)linkqueue*q;{if(empty(q)){print(“queueisempty〞);return0;}elsereturn(q->front->next->data);}3、取队头结点数据

enqueue(q,x)linkqueue*q;datatypex;{q->rear->next=malloc(sizeof(linklist));q->rear=q->rear->next;q->rear->data=x;q->rear->next=NULL;}4、入队5、出队一般思路：Ss=q->front->next;q->front->next=s->next;free(s);

S改进算法s=q->front;q->front=q->front->next;free(s);return(q->front->data);datatypedequeue(q)linkqueue*q;{if(empty(q)){print(“queueisempty〞);return0;}else{s=q->front;q->front=q->front->next;free(s);return(q->front->data);}}出队算法实现习题1、设将整数以万计、2、3、4依次进栈，但只要出栈时栈非空，那么可将出栈操作按任何次序夹入其中，请答复下有问题：〔1〕假设入栈次序为push(1)，pop()，push(2，push(3)，pop()，pop()，push(4)，pop()，那么出栈的数字序列为什么？〔2〕能否得到出栈序列车员423和平共处五项原那么432？并说明为什么不能得到或如何得到。〔3〕请分析1、2、3、4的24种排列中，哪些序列可以通过相应的入出栈得到。2、链栈中为何不设头指针？3、循环队列的优点是什么？如何判断它的空和满？4、设长度为n的链队列用单循环链表表示，假设只设头指针，那么怎样进行入队和出队操作；假设只设尾指针呢？5、利用栈的根本操作，写一个返回栈s中结点个数的算法intstacksize(seqstacks)，并说明s为何不用作为指针参数？6、利用栈的根本操作，写一个将栈中所有结点均删除算法，并说明S为何要作为指针参数？7、用第二种方法，即少用一个元素空间的方法来区别循环队列的队空和队满，试设计置空队、判队空、判队满、出队、入队及取队头元素等六个根本操作。8、假设循环队列只设rear和quelen来分别指示队尾元素的位置和队中元素的个数，试给出判断此循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头指针。9、指出以下程序段的功能是什么？(1)voiddemo1(seqstack*s){intI;arr[64];n=0;while(!stackempty(s))arr[n++]=pos(s);for(I=0;<n;I++)push(s,arr[I]);}(2)voiddemo2(seqstack*s,intm){seqstackt;inti;initstack(t);while(!Stackempty(s))if(I=pop(s)!=m)push(t,I);While(!Stackempty(t)){i=pop(t);push(s,I);}}

第四章串4.1串类型的定义4.2串的表示和实现4.2.1定长顺序存储表示4.2.2堆分配存储表示4.2.3串的块链存储表示4.1串类型的定义一、串和根本概念串(String)是零个或多个字符组成的有限序列。一般记作S=“a