计算机系---数据结构与算法设计

《计算机系---数据结构与算法设计》由会员分享，可在线阅读，更多相关《计算机系---数据结构与算法设计（241页珍藏版）》请在装配图网上搜索。

1、计算机系1.1 什么是数据结构1.2 基本概念和术语1.3 抽象数据类型的表示与实现1.4 算法和算法分 1.4.1 算法 1.4.2 算法设计的要求 1.4.3 算法效率的度量 1.4.4 算法的存储空间的需求l计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题：l 信息的表示 信息的处理 而信息的表示和组又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。l 1.1什么是

2、数据结构l 众所周知，计算机的程序是对信息进行加工处理。在大多数情况下，这些信息并不是没有组织，信息（数据）之间往往具有重要的结构关系，这就是数据结构的内容。那么，什么是数据结构呢？先看以下几个例子。l 例1、电话号码查询系统l 设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式安排：l (a1，b1)(a2，b2)(an，bn)l其中ai，bi(i=1，2n)分别表示某人的名字和对应的电话号码要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的标志。l 算法的设计，依赖于计算机如何存

3、储人的名字和对应的电话号码，或者说依赖于名字和其电话号码的结构。l 数据的结构，直接影响算法的选择和效率。l 上述的问题是一种数据结构问题。可将名字和对应的电话号码设计成：二维数组、表结构、向量。假定名字和其电话号码逻辑上已安排成N元向量的形式，它的每个元素是一个数对(ai，bi)，1in 数据结构还要提供每种结构类型所定义的各种运算的算法。例2、图书馆的书目检索系统自动化问题例3、教师资料档案管理系统例4、多叉路口交通灯的管理问题 P3 通过以上几例可以直接地认为：数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构仍

4、然是原来的结构类型。l 1.2 基本概念和术语l数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。l数据元素(Data Element):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。l 一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。l数据对象(Data Object)：是性质相同的数据元素的集合。是数据的一个子集。l数据结构(Data Structure)：是相互之间存在一种或多种特定关系的数据元素的集合。l数据结构主要指逻辑结构和物理结构l 数据之间的相互关系称为逻辑结构。通常分为四类基本

5、结构：l一、集合 结构中的数据元素除了同属于一种类型外，别无其它关系。l二、线性结构 结构中的数据元素之间存在一对一的关系。l三、树型结构 结构中的数据元素之间存在一对多的关系。l四、图状结构或网状结构 结构中的数据元素之间存在多对多的关系。l 数据结构的形式定义为：数据结构是一个二元组：Data-Structure=(D，S)其中：D是数据元素的有限集，S是D上关系的有限集。例 复数的数据结构定义如下：Complex=(C，R)其中：C是含两个实数的集合C1，C2，分别表示复数的实部和虚部。R=P，P是定义在集合上的一种关系C1，C2。数据结构在计算机中的表示称为数据的物理结构，又称为存储结

6、构。l 数据对象可以是有限的，也可以是无限的。l数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。l抽象数据类型：一个数学模型以及定义在该模型上的一组操作。l抽象数据类型实际上就是对该数据结构的定义。因为它定义了一个数据的逻辑结构以及在此结构上的一组算法。l用三元组描述如下：l（，）l数据结构在计算机中有两种不同的表示方法：l 顺序表示和非顺序表示l由此得出两种不同的存储结构：顺序存储结构和链式存储结构l顺序存储结构:用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。l链式存储结构：在每一个数据元素中增加一个存放地址的指

7、针（），用此指针来表示数据元素之间的逻辑关系。l数据类型：在一种程序设计语言中，变量所具有的数据种类。l例1、在FORTRAN语言中，变量的数据类型有整型、实型、和复数型 l例2、在C语言中l数据类型：基本类型和构造类型l基本类型：整型、浮点型、字符型l构造类型：数组、结构、联合、指针、枚举型、自定义l数据对象：某种数据类型元素的集合。l例3、整数的数据对象是-3，-2，-1，0，1，2，3，l英文字符类型的数据对象是A，B，C，D，E，F，l 1.3 抽象数据类型的表示和实现lP11l 1.4 算法和算法分析l算法：是对特定问题求解步骤的一种描述l 算法是指令的有限序列，其中每一条指令表示一

8、个或多个操作。l 算法具有以下五个特性：l（1）有穷性 一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。l（2）确定性 算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。l（3）可行性 一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。l4）输入 一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。l5）输出 一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。l1.4.2 算法设计的要求l评价一个好的算法有以下几个标准:l(1)正确性(Correctness)算法应满足具体问题的需求。l(2)

9、可读性(Readability)算法应该好读。以有利于阅读者对程序的理解。(3)健状性(Robustness)算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产年莫名其妙的输出结果。l(4)效率与存储量需求 效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。l1.4.3 算法效率的度量l 对一个算法要作出全面的分析可分成两用人才个阶段进行，即事先分析和事后测试l事先分析 求出该算法的一个时间界限函数l事后测试 收集此算法的执行时间和实际占用空间的统计资料。l定义：如果存在两个正常数c和n0，对于所有的nn0，有f(n)cg(

10、n)l则记作 f(n)=O(g(n)一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，算法的时间量度记作 T(n)=O(f(n)称作算法的渐近时间复杂度。例、for(I=1，I=n;+I)for(j=1;j=n;+j)cIj=0;for(k=1;k=n;+k)cIj+=aIk*bkj;l由于是一个三重循环，每个循环从1到n，则总次数为:nnn=n3l时间复杂度为T(n)=O(n3)l频度：是指该语句重复执行的次数l例+x;s=0;l将x自增看成是基本操作，则语句频度为，即时间复杂度为(1)l如果将s=0也看成是基本操作，则语句频度为，其时间复杂度仍为(1)，即常量阶。l例、for

11、(I=1;I=n;+I)l +x;s+=x;l 语句频度为：2n其时间复杂度为：O(n)l 即时间复杂度为线性阶。l例、for(I=1;I=n;+I)lfor(j=1;j=n;+j)l +x;s+=x;l 语句频度为：2n2l其时间复杂度为：O(n2)l 即时间复杂度为平方阶。l定理：若A(n)=a m n m+a m-1 n m-1+a1n+a0是一个m次多项式，则A(n)=O(n m)证略。例for(i=2;i=n;+I)for(j=2;j=i-1;+j)+x;ai，j=x;l语句频度为：l 1+2+3+n-2=(1+n-2)(n-2)/2l =(n-1)(n-2)/2l =n2-3n+2

12、l 时间复杂度为O(n2)l 即此算法的时间复杂度为平方阶.l 一个算法时间为O(1)的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数（即零次多项式）来限界。而一个时间为O(n2)的算法则由一个二次多项式来限界。l l以下六种计算算法时间的多项式是最常用的。其关系为：l O(1)O(logn)O(n)O(nlogn)l O(n2)O(n3)l指数时间的关系为：l O(2n)O(n!)1&change;-I)l l change=false;l for(j=0;jaj+1)l aj aj+1;l change=TUREl l 最好情况：0次l l l最坏情况：1+2+3+n-1l

13、 =n(n-1)/2l 平均时间复杂度为:O(n2)l1.4.4算法的存储空间需求l空间复杂度:算法所需存储空间的度量，记作:l S(n)=O(f(n)l其中n为问题的规模(或大小)l2.1 线性表的类型定义l2.2 线性表的顺序表示和实现l2.3 线性表的链式表示和实现l 2.3.1 线性链表 2.3.2 循环链表 2.3.3 双向链表 2.4 一元多项式的表示及相加l2.1 线性表的逻辑结构l线性表(Linear List)：由n(n)个数据元素(结点)a1，a2，an组成的有限序列。其中数据元素的个数n定义为表的长度。当n=0时称为空表，常常将非空的线性表(n0)记作：l (a1，a2，

14、an)l这里的数据元素ai(1in)只是一个抽象的符号，其具体含义在不同的情况下可以不同。l例1、26个英文字母组成的字母表l （A，B，C、Z）l例2、某校从1978年到1983年各种型号的计算机拥有量的变化情况。l （6，17，28，50，92，188）姓 名学 号性 别年龄 健康情况王小林790631 男 18 健康陈 红790632 女 20 一般刘建平790633 男 21 健康张立立790634 男 17 神经衰弱.l例4、一副扑克的点数l （2，3，4，J，Q，K，A）从以上例子可看出线性表的逻辑特征是：l在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后

15、继a2；l有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋a n-1；l其余的内部结点ai(2in-1)都有且仅有一个直接前趋a i-1和一个直接后继a i+1。线性表是一种典型的线性结构。l数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。l抽象数据类型的定义为：P19 算法2.1l例2-1 利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=AB。void union(List&La，List Lb)La-len=listlength(La);Lb-len=listlength(Lb);for(I=1;I=lb-len;I+)getele

16、m(lb，I，e);if(!locateelem(la，e，equal)listinsert(la，+la-en，e)l l 算法2.2l例2-2 巳知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。l 此问题的算法如下：void mergelist(list la，list lb，list&lc)initlist(lc);I=j=1;k=0;la-len=listlength(la);lb-len=listlength(lb);while(I=la-len)&(j=lb-len)l getelem(la，I

17、，ai);getelem(lb，j，bj);l if(ai=bj)listinsert(lc，+k，ai);+I;elselistinsert(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);l 2.2 线性表的顺序存储结构l2.2.1 线性表 把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。假设线性表的每个元素需占用l个存储单元，并以所占的第一个单元的存储

18、地址作为数据元素的存储位置。则线性表中第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 l由于C语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。又因为除了用数组来存储线性表的元素之外，顺序表还应该用一个变量来表示线性表的长度属性，所以我们用结构类型来定义顺序表类型。l#define ListSize 100l typedef int DataType;l typedef strucl

19、DataType dataListSize;l int length;l Sqlist;l2.2.2 顺序表上实现的基本操作 在顺序表存储结构中，很容易实现线性表的一些操作，如线性表的构造、第i个元素的访问。注意：C语言中的数组下标从“0”开始，因此，若L是Sqlist类型的顺序表，则表中第i个元素是l.dataI-1。以下主要讨论线性表的插入和删除两种运算。1、插入 线性表的插入运算是指在表的第I(1in+1个位置上，插入一个新结点x，使长度为n的线性表 (a1，a i-1，ai，an)变成长度为n+1的线性表 (a1，a i-1，x，ai，an)算法2.3lVoid InsertList(

20、Sqlist*L，DataType x，int I)l l int j;l if(Il.length+1)l printf(“Position error”);l return ERRORl l if(l.length=ListSize)l printf(“overflow”);l exit(overflow);l for(j=l.length-1;j=I-1;j-)l l.dataj+1=l.dataj;l l.dataI-1=x;l l.length+;ll 现在分析算法的复杂度。l 这里的问题规模是表的长度，设它的值为。该算法的时间主要化费在循环的结点后移语句上，该语句的执行次数（即移动

21、结点的次数）是。由此可看出，所需移动结点的次数不仅依赖于表的长度，而且还与插入位置有关。l当时，由于循环变量的终值大于初值，结点后移语句将不进行；这是最好情况，其时间复杂度O（1）；l当=1时，结点后移语句将循环执行n次，需移动表中所有结点，这是最坏情况，l其时间复杂度为O（n）。l 由于插入可能在表中任何位置上进行，因此需分析算法的平均复杂度 在长度为n的线性表中第i个位置上插入一个结点，令Eis(n)表示移动结点的期望值（即移动的平均次数），则在第i个位置上插入一个结点的移动次数为n-I+1。故 Eis(n)=pi(n-I+1)不失一般性，假设在表中任何位置(1in+1)上插入结点的机会是

22、均等的，则 p1=p2=p3=p n+1=1/(n+1)因此，在等概率插入的情况下，Eis(n)=(n-I+1)/(n+1)=n/2 也就是说，在顺序表上做插入运算，平均要移动表上一半结点。当表长 n较大时，算法的效率相当低。虽然Eis(n)中n的的系数较小，但就数量级而言，它仍然是线性阶的。因此算法的平均时间复杂度为O(n)。2、删除 线性表的删除运算是指将表的第i(1in)结点删除，使长度为n的线性表：(a1，a i-1，ai，a i+1，an)变成长度为n-1的线性表 (a1，a i-1，a i+1，an)Void deleteList(Sqlist*L，int I)int j;if(I

23、l.length)printf(“Position error”);return ERROR for(j=i;jdata=ch;pnext=head;head=p;ch=getchar();return(head);listlink createlist(int n)int data;linklist head;listnode*p head=null;for(i=n;i0;-i)p=(listnode*)malloc(sizeof(listnode);scanf(%d，&pdata);pnext=head;head=p;return(head);2、尾插法建表 头插法建立链表虽然算法简单，但

24、生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。例：linklist creater()char ch;linklist head;listnode *p，*r;/(，*head;)head=NULL;r=NULL;while(ch=getchar()!=n)p=(listnode*)malloc(sizeof(listnode);pdata=ch;if(head=NULL)head=p;else rnext=p;r=p;if(r!=NULL)rnext=NULL;re

25、turn(head);说明：第一个生成的结点是开始结点，将开始结点插入到空表中，是在当前链表的第一个位置上插入，该位置上的插入操作和链表中其它位置上的插入操作处理是不一样的，原因是开始结点的位置是存放在头指针（指针变量）中，而其余结点的位置是在其前趋结点的指针域中。算法中的第一个if语句就是用来对第一个位置上的插入操作做特殊处理。算法中的第二个if语句的作用是为了分别处理空表和非空表两种不同的情况，若读入的第一个字符就是结束标志符，则链表head是空表，尾指针r亦为空，结点*r不存在；否则链表head非空，最后一个尾结点*r是终端结点，应将其指针域置空。如果我们在链表的开始结点之前附加一个结点

26、，并称它为头结点，那么会带来以下两个优点：a、由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就 和在表的其它位置上的操作一致，无需进行特殊处理；b、无论链表是否为空，其头指针是指向头结点 在的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就统一了。其算法如下：linklist createlistr1()char ch;linklist head=(linklist)malloc(sizeof(listnode);listnode *p，*r r=head;while(ch=getchar()!=n p=(listnode*)malloc(sizeo

27、f(listnode);pdata=ch;pnext=p;r=p;rnext=NULL;return(head);上述算法里动态申请新结点空间时未加错误处理，可作下列处理：p=(listnode*)malloc(sizeof(listnode)if(p=NULL)error(No space for node can be obtained);return ERROR;以上算法的时间复杂度均为O(n)。二、查找运算 1、按序号查找 在链表中，即使知道被访问结点的序号i，也不能象顺序表中那样直接按序号i访问结点，而只能从链表的头指针出发，顺链域next逐个结点往下搜索，直到搜索到第i个结点为止。

28、因此，链表不是随机存取结构。设单链表的长度为n，要查找表中第i个结点，仅当1in时，i的值是合法的。但有时需要找头结点的位置，故我们将头结点看做是第0 个结点，其算法如下：Listnode*getnode(linklist head，int i)int j;listnode*p;p=head;j=0;while(pnext&jnext;j+;if(i=j)return p;else return NULL;2、按值查找 按值查找是在链表中，查找是否有结点值等于给定值key的结点，若有的话，则返回首次找到的其值为key的结点的存储位置；否则返回NULL。查找过程从开始结点出发，顺着链表逐个将结点

29、的值和给定值key作比较。其算法如下：Listnode*locatenode(linklist head，int key)listnode*p=headnext;while(p&pdata!=key)p=pnext;return p;该算法的执行时间亦与输入实例中的的取值key有关，其平均时间复杂度的分析类似于按序号查找，也为O(n)。三、插入运算 插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，我们必须首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点*p，并令结点*p的指针域指向新结点，新结点的指针域指向结点ai。从而实现三个结点ai-1

30、，x和ai之间的逻辑关系的变化，插入过程如：具体算法如下：void insertnode(linklist head，datetype x，int i)listnode *p，*q;p=getnode(head，i-1);if(p=NULL)error(position error);q=(listnode*)malloc(sizeof(listnode);qdata=x;qnext=pnext;pnext=q;设链表的长度为n，合法的插入位置是1in+1。注意当i=1时，getnode找到的是头结点，当 i=n+1时，getnode找到的是结点an。因此，用i-1做实参调用getnode时可

31、完成插入位置的合法性检查。算法的时间主要耗费在查找操作getnode上，故时间复杂度亦为O(n)。四、删除运算 删除运算是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在其直接前趋结点a a i-1的指针域next中，所以我们必须首先找到 a i-1的存储位置p。然后令pnext指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间，将其归还给“存储池”。此过程为：具体算法如下：void deletelist(linklist head，int i)listnode*p，*r;p=getnode(head，i-1);if(p=NULL|pnext=NULL)return

32、ERROR;r=pnext;pnext=rnext;free(r);设单链表的长度为n，则删去第i个结点仅当1in时是合法的。注意，当i=n+1时，虽然被删结点不存在，但其前趋结点却存在，它是终端结点。因此被删结点的直接前趋*p存在并不意味着被删结点就一定存在，仅当*p存在（即p!=NULL）且*p不是终端结点（即pnext!=NULL）时，才能确定被删结点存在。显然此算法的时间复杂度也是O(n)。从上面的讨论可以看出，链表上实现插入和删除运算，无须移动结点，仅需修改指针。2.3.2 循环链表 循环链表时一种头尾相接的链表。其特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方

33、便灵活。单循环链表：在单链表中，将终端结点的指针域NULL改为指向表头结点的或开始结点，就得到了单链形式的循环链表，并简单称为单循环链表。为了使空表和非空表的处理一致，循环链表中也可设置一个头结点。这样，空循环链表仅有一个自成循环的头结点表示。如下图所示：a1 an .head 非空表 空表 在用头指针表示的单链表中，找开始结点a1的时间是O(1)，然而要找到终端结点an，则需从头指针开始遍历整个链表，其时间是O(n)在很多实际问题中，表的操作常常是在表的首尾位置上进行，此时头指针表示的单循环链表就显得不够方便.如果改用尾指针rear来表示单循环链表，则查找开始结点a1和终端结点an都很方便，

34、它们的存储位置分别是(rearnext)next和rear，显然，查找时间都是O(1)。因此，实际中多采用尾指针表示单循环链表。由于循环链表中没有NULL指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断p或pnext是否为空，而是判断它们是否等于某一指定指针，如头指什或尾指针等。例、在链表上实现将两个线性表(a1，a2，a3，an)和(b1，b2，b3，bn)链接成一个线性表的运算。linklist connect(linklist heada，linklist headb)linklist p=headanext;headanext=(headbnext)next free(he

35、adbnext);headbnext=p;return(headb);2.3.3双链表 双向链表(Double linked list):在单链表的每个结点里再增加一个指向其直接前趋的指针域prior。这样就形成的链表中有两个方向不同的链，故称为双向链表。形式描述为：typedef struct dlistnode datatype data;struc dlistnode*prior，*next;dlistnode;typedef dlistnode*dlinklist;dlinklist head;和单链表类似，双链表一般也是由头指针唯一确定的，增加头指针也能使双链表上的某些运算变得方便，

36、将头结点和尾结点链接起来也能构成循环链表，并称之为双向链表。设指针p指向某一结点，则双向链表结构的对称性可用下式描述：(pprior)next=p=(pnext)prior 即结点*p的存储位置既存放在其前趋结点*(pprior)的直接后继指针域中，也存放 在它的后继结点*(pnext)的直接前趋指针域中。双向链表的前插操作算法如下：void dinsertbefor(dlistnode*p，datatype x)dlistnode*q=malloc(sizeof(dlistnode);qdata=x;qprior=pprior;qnext=p;ppriornext=q;pprior=q;vo

37、id ddeletenode(dlistnode*p)ppriornext=pnext;pnextprior=pprior;free(p);注意：与单链表的插入和删除操作不同的是，在双链表中插入和删除必须同时修改两个方向上的指针。上述两个算是法的时间复杂度均为O(1)。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.1 栈3.1.1 栈的定义及基本运算 栈(Stack)是限制在表的一端进行插入和删除运算的线性表，通常称插入

38、、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当表中没有元素时称为空栈。假设栈S=(a1，a2，a3，an)，则a1称为栈底元素，an为栈顶元素。栈中元素按a1，a2，a3，an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表（LIFO）。3.1.2 顺序栈 由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。因此，可用数组来实现顺序栈。因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，故需用一个整

39、型变量top例、一叠书或一叠盘子。栈的抽象数据类型的定义如下：P44 a n a n-1 a2 a1栈顶 栈底top7 6 5 4 3 2 1 -1来指示当前栈顶的位置，通常称top为栈顶指针。因此，顺序栈的类型定义只需将顺序表的类型定义中的长度属性改为top即可。顺序栈的类型定义如下：#define StackSize 100 typedef char datatype;typedef struct datatype datastacksize;int top;seqstack;设S是SeqStack类型的指针变量。若栈底位置在向量的低端，即sdata0是栈底元素，那么栈顶指针stop是正向

40、增加的，即进栈时需将stop加1，退栈时需将stop 减1。因此，stoptop=stacksize-1表示栈满。当栈满时再做进栈运算必定产生空间溢出，简称“上溢”;当栈空时再做退栈运算也将产生溢出，简称“下溢”。上溢是一种出错状态，应该设法避免之；下溢则可能是正常现象，因为栈在程序中使用时，其初态或终态都是空栈，所以下溢常常用来作为程序控制转移的条件。3、判断栈满 int stackfull(seqstack *s)return(stop=stacksize-1);4、进栈 void push(seqstack *s，datatype x)if(stackfull(s)error(“stac

41、k overflow”);sdata+stop=x;1、置空栈 void initstack(seqstack*s)stop=-1;2、判断栈空 int stackempty(seqstack*s)return(stop=-1);5、退栈 datatype pop(seqstack*s)if(stackempty(s)error(“stack underflow”);x=sdatatop;stop-;return(x)/return(sdatastop-);6、取栈顶元素 Datatype stacktop(seqstack *s)if(stackempty(s)error(“stack is

42、 enpty”);return sdatastop;3.1.3 链栈 栈的链式存储结构称为链栈，它是运算是受限的单链表，克插入和删除操作仅限制在表头位置上进行.由于只能在链表头部进行操作，故链表没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。链栈的类型说明如下：typedef struct stacknode datatype data struct stacknode*next stacknode;Void initstack(seqstack*p)ptop=null;int stackempty(linkstack*p)return ptop=null;lVoid push(li

43、nkstack*p,datatype x)stacknode*q q=(stacknode*)malloc(sizeof(stacknode);qdata=x;qnext=ptop;ptop=p;Datatype pop(linkstack *p)datatype x;stacknode *q=ptop;if(stackempty(p)error(“stack underflow.”);x=qdata;ptop=qnext;free(q);return x;datatype stack top(linkstack *p)if(stackempty(p)error(“stack is empty

44、.”);return ptopdata;3.2 栈的应用举例 由于栈结构具有的后进先出的固有特性，致使栈成为程序设计中常用的工具。以下是几个栈应用的例子。3.2.1 数制转换 十进制N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理:N=(n div d)*d+n mod d (其中:div为整除运算,mod为求余运算)例如(1348)10=(2504)8，其运算过程如下：n n div 8 n mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 void conversion()initstack(s);scanf(“%”,

45、n);while(n)push(s,n%8);n=n/8;while(!Stackempty(s)pop(s,e);printf(“%d”,e);3.2.2 括号匹配的检验 假设表达式中充许括号嵌套,则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。例：（）（）（）3.2.3 行编辑程序 在编辑程序中，设立一个输入缓冲区，用于接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入错误，并在发现有误时可以及时更正。行编辑程序算法如下:void lineedit()initstack(s);ch=gether();while(ch!=eof)while(ch!=eof&ch!=n

46、)switch(ch)case#:pop(s,c);case :clearstack(s);default:push(s,ch);ch=getchar();clearstack(s);if(ch!=eof)ch=gethar();destroystack(s);3.2.4 迷宫求解 入口出口3.4 队列3.4.1 抽象数据类型队列的定义 队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦称作先进先出(

47、First In First Out)的线性表，简称FIFO表。当队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,an之后，a1是队头元素，an是队尾元素。显然退出队列的次序也只能是a1,a2,an，也就是说队列的修改是依先进先出的原则进行的。下图是队列的示意图：a1a2an出队入队队头队尾队列的抽象数据定义见书593.4.2 循环队列队列的顺序表示和实现队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表，和顺序表一样，顺序队列也是必须用一个向量空间来存放当前队列中的元素。由于队列的队头和队尾的位置是变化的，因而要设两个指针和分别指示队头和队尾元素在队列中的位置，它

48、们的初始值地队列初始化时均应置为。入队时将新元素插入所指的位置，然后将加。出队时，删去所指的元素，然后将加并返回被删元素。由此可见，当头尾指针相等时队列为空。在非空队列里，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一位置。0 1 2 3FrontrearabcFront rear(a)队列初始为空（b）A,B,C入队 b c front rear front rear （c)a出队 (d)b,c出队，队为空和栈类似，队列中亦有上溢和下溢现象。此外，顺序队列中还存在“假上溢”现象。因为在入队和出队的操作中，头尾指针只增加不减小，致使被删除元素的空间永远无法重新利用。因此，尽管队列中实际

49、的元素个数远远小于向量空间的规模，但也可能由于尾指针巳超出向量空间的上界而不能做入队操作。该现象称为假上溢。为充分利用向量空间。克服上述假上溢现象的方法是将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量，存储在其中的队列称为循环队列（Circular Queue)。在循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界（QueueSize-1）时，其加1操作的结果是指向向量的下界0。这种循环意义下的加1操作可以描述为：if(I+1=QueueSize)i=0;else i+;利用模运算可简化为：i=(i+1)%QueueSize 显然，因为循环队列

50、元素的空间可以被利用，除非向量空间真的被队列元素全部占用，否则不会上溢。因此，除一些简单的应用外，真正实用的顺序队列是循环队列。如图所示：由于入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时头尾指针均相等。因此，我们无法通过front=rear来判断队列“空”还是“满”。解决此问题的方法至少有三种：其一是另设一个布尔变量以匹别队列的空和满；其二是少用一个元素的空间，约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：rear所指的单元始终为空）；其三是使用一个计数器记录队列中元素的总数（实际上是队列长度）。下面我们用第三种方法实现循环队列上的六

51、种基本操作，为此先给出循环队列的类型定义。l#define QueueSize 100l typedef char DataType;l typedef Structl int front;l int rear;l int count;l datatype dataqueuesizel cirqueue;（1）置空队 void initqueue(cirqueue*q)qfront=qrear=0;qcount=0;（2）判断队空 int queueempty(cirqueue*q)return qcount=0;（3）判断队满 int queuefull(cirqueue*q)return

52、qcount=queuesize;（4）入队 void enqueue(cirqueue*q,datatype x)if(queuefull(q)error(“queue overflow”);qcount+;qdataqrear=x;qrear=(qrear+1)%queuesize;（5）出队 datatype dequeue(cirqueue *q)datatype temp;if(queueempty(q)error(“queue underflow”);temp=qdataqfront;qcount-;qfront=(qfront+1)%queuesize;return temp;（

53、6）取头指针 datatype queuefront(cirqueue*q)if(queueempty(q)error(“queue is empty.”);return qdataqfront;l3.4.3 链队列l 队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。显然仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表的最后一个结点。于是，一个链队列由一个头指针唯一确定。和顺序队列类似，我们也是将这两个指针封装在一起，将链队列的类型LinkQueue定义为一个结构类型：l typedef struct queuenodel datatype da

54、ta;l struct queuenode*next;l queuenode;typedef struct queuenode *front;queuenode *rear;linkqueue;下面给出链队列上实现的基本运算：void initqueue(linkqueue *q)qfront=qrear=null;int queueempty(linkqueue *q)return qfront=null&qrear=null;void enqueue(linkqueue *q,datatype x)queuenode*p p=(queuenode*)malloc(sizeof(queuen

55、ode);pdata=x;pnext=null;if(queueempty(q)qfront=qrear=p;else qrearnext=p;qrear=p;Datatype dequeue(linkqueue*q)datatype x;queuenode *p if(queueempty(q)error(“queue underflow”);p=qfront;x=pdata;qfront=pnext;if(qrear=p)qrear=null;free(p);return x;datatype queuefront(linkqueue*q)if(queueempty(q)error(“qu

56、eue is empty.”);return qfrontdata;注意：在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。习题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

57、种排列中，哪些序列可以通过相应的入出栈得到。2、链栈中为何不设头指针？3、循环队列的优点是什么？如何判断它的空和满？4、设长度为n的链队列用单循环链表表示，若只设头指针，则怎样进行入队和出队操作；若只设尾指针呢？5、利用栈的基本操作，写一个返回栈s中结点个数的算法int stacksize(seqstack s)，并说明s为何不用作为指针参数？6、利用栈的基本操作，写一个将栈中所有结点均删除算法，并说明S为何要作为指针参数？7、用第二种方法，即少用一个元素空间的方法来区别循环队列的队空和队满，试设计置空队、判队空、判队满、出队、入队及取队头元素等六个基本操作。8、假设循环队列只设rear和qu

58、elen来分别指示队尾元素的位置和队中元素的个数，试给出判断此循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头指针。9、指出下列程序段的功能是什么？(1)void demo1(seqstack*s)int I;arr64;n=0;while(!stackempty(s)arrn+=pos(s);for(I=0;n;I+)push(s,arrI);(2)void demo2(seqstack*s,int m)seqstack t;int i;initstack(t);while(!Stackempty(s)if(I=pop(s)!=m)push(t,I);While(!Sta

59、ckempty(t)i=pop(t);push(s,I);l4.1 串类型的定义l4.2 串的表示和实现 4.2.1 定长顺序存储表示 4.2.2 堆分配存储表示 4.2.3 串的块链存储表示 4.1 串类型的定义一、串和基本概念 串(String)是零个或多个字符组成的有限序列。一般记作S=“a1a2a3an”，其中S 是串名，双引号括起来的字符序列是串值；ai(1in)可以是字母、数字或其它字符；串中所包含的字符个数称为该串的长度。长度为零的串称为空串(Empty String)，它不包含任何字符。通常将仅由一个或多个空格组成的串称为空白串(Blank String)注意：空串和空白串的不

60、同，例如“”和“”分别表示长度为1的空白串和长度为0的空串。串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。通常将子串在主串中首次出现时的该子串的首字符对应的主串中的序号，定义为子串在主串中的序号（或位置）。例如，设A和B分别为 A=“This is a string”B=“is”则B是A的子串，A为主串。B在A中出现了两次，其中首次出现所对应的主串位置是3。因此，称B在A中的序号（或位置）为3 特别地，空串是任意串的子串，任意串是其自身的子串。通常在程序中使用的串可分为两种：串变量和串常量。串常量和整常数、实常数一样，在程序中只能被引用但不能不能改变其值，即只能读不

61、能写。通常串常量是由直接量来表示的，例如语句Error(“overflow”)中“overflow”是直接量。但有的语言允许对串常量命名，以使程序易读、易写。如C+中，可定义 const char path=“dir/bin/appl”;这里path是一个串常量，对它只能读不能写。串变量和其它类型的变量一样，其取值是可以改变的。二、串的抽象数据定义 串的抽象数据类型定义台书P71三、串的基本操作 对于串的基本操作，许多高级语言均提供了相应的运算或标准库函数来实现。下面仅介绍几种在C语言中常用的串运算，其它的串操作见的文件。定义下列几个变量：char s120=“dirtreeformat”,s

62、220=“file.mem”;char s330,*p;int result;(1)求串长(length)(2)int strlen(char s);/求串的长度(3)例如：printf(“%d”,strlen(s1);输出13（2）串复制(copy)char*strcpy(char to,char from);该函数将串from复制到串to中，并且返回一个指向串to的开始处的指针。例如：strcpy(s3,s1);/s3=“dirtreeformat”(3)联接(concatenation)char strcat(char to,char from)该函数将串from复制到串to的末尾，并且

63、返回一个指向串to的开始处的指针。例如：strcat(s3,”/”)strcat(s3,s2);/s3=“dirtreeformat/file.mem”(4)串比较（compare)int strcmp(chars1,char s2);该函数比较串s1和串s2的大小，当返回值小于0，等于0或大于0时分别表示s1s2 例如：result=strcmp(“baker”,”Baker”)result0 result=strcmp(“12”,”12”);result=0 result=strcmp(“Joe”,”Joseph”);result0（5）字符定位(index)char strchr(cha

64、r s,char c);该函数是找c在字符串中第一次出现的位置，若找到则返回该位置，否则返回NULL。例如：p=strchr(s2,”.”);p 指向“file”之后的位置 if(p)strcpy(p,”.cpp”);s2=“file.cpp”上述串的操作是最基本的，其中后四个还有变种形式：strncpy，strncat，strncmp，strnchr。串的其余操作可由这些基本操作组合而成。例1、求子串 求子串的过程即为复制字符序列的过程，将串S中的第pos个字符开始长度为len的字符复制到串T中。void substr(string sub,string s,int pos,int len)

65、if(posstrlen(s)-1|len0)n=strlen(s);m=strlen(t);i=pos;while(in-m+1)substr(sub,s,i,m);if(strcmp(sub,t)!=0)+i;else return(i);return(0);4.2 串的表现和实现 因为串是特殊的线性表，故其存储结构与线性表的存储结构类似。只不过由于组成串的结点是单个字符。串有三种机内表示方法，下面分别介绍。4.2.1定长顺序存储表示 定长顺序存储表示,也称为静态存储分配的顺应表。它是用一组连续的存储单元来存放串中的字符序列。所谓定长顺序存储结构，是直接使用定长的字符数组来定义，数组的上界

66、预先给出：#define maxstrlen 256 typedef char sstringmaxstrlen;sstring s;/s是一个可容纳255个字符的顺序串。一般可使用一个不会出现在串中的特殊字符在串值的尾部来表示串的结束。例如，C语言中以字符0表示串值的终结，这就是为什么在上述定义中，串空间最大值maxstrlen为256，但最多只能存放255个字符的原因，因为必须留一个字节来存放0字符。若不设终结符，可用一个整数来表示串的长度，那么该长度减1的位置就是串值的最后一个字符的位置。此时顺序串的类型定义和顺序表类似：typedef struct char chmaxstrlen;int length;sstring;/其优点是涉及到串长操作时速度快。4.2.2堆分配存储表示 这种存储表示的特点是，仍以一组地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配而得。所以也称为动态存储分配的顺序表。在C语言中，利用和等动态存储管理函数，来根据实际需要动态分配和释放字符数组空间。这样定义的顺序串类型也有两种形式。typedef char*string;/c