1、 计算机是一门研究用计算机进行信息表示和处理 的科学。这里面涉及到两个问题： 信息的表示 信息的处理 而信息的表示和组又直接关系到处理信息的程 序的效率。随着计算机的普及，信息量的增加， 信息范围的拓宽，使许多系统程序和应用程序的 规模很大，结构又相当复杂。因此，为了编写出 一个“好”的程序，必须分析待处理的对象的特 征及各对象之间存在的关系，这就是数据结构这 门课所要研究的问题。 1.1什么是数据结构 众所周知，计算机的程序是对信息进行加工处理。 在大多数情况下，这些信息并不是没有组织，信息 （数据）之间往往具有重要的结构关系，这就是数据 结构的内容。那么，什么是数据结构呢？先看以下几 个例
2、子。 例1、电话号码查询系统 设有一个电话号码薄，它记录了N个人的名字和 其相应的电话号码，假定按如下形式安排： (a1，b1)(a2，b2)(an，bn) 其中ai，bi(i=1，2n) 分别表示某人的名字和对应 的电话号码要求设计一个算法，当给定任何一个人的 名字时，该算法能够打印出此人的电话号码，如果该 电话簿中根本就没有这个人，则该算法也能够报告没 有这个人的标志。 算法的设计，依赖于计算机如何存储人的 名字和对应的电话号码，或者说依赖于名字和其 电话号码的结构。 数据的结构，直接影响算法的选择和效率。 上述的问题是一种数据结构问题。可将名字 和对应的电话号码设计成：二维数组、表结构、
3、 向量。 假定名字和其电话号码逻辑上已安排成N元 向量的形式，它的每个元素是一个数对(ai，bi)， 1in 数据结构还要提供每种结构类型所定义的 各种运算的算法。 例2、图书馆的书目检索系统自动化问题 例3、教师资料档案管理系统 例4、多叉路口交通灯的管理问题 P3 通过以上几例可以直接地认为：数据结构 就是研究数据的逻辑结构和物理结构以及它们 之间相互关系，并对这种结构定义相应的运算， 而且确保经过这些运算后所得到的新结构仍然 是原来的结构类型。 1.2 基本概念和术语 数据(Data):是对信息的一种符号表示。在计算 机科学中是指所有能输入到计算机中并被计算机 程序处理的符号的总称。 数
4、据元素(Data Element):是数据的基本单位， 在计算机程序中通常作为一个整体进行考虑和处 理。 一个数据元素可由若干个数据项组成。数据 项是数据的不可分割的最小单位。 数据对象(Data Object)：是性质相同的数据元 素的集合。是数据的一个子集。 数据结构(Data Structure)：是相互之间存在 一种或多种特定关系的数据元素的集合。 数据结构主要指逻辑结构和物理结构 数据之间的相互关系称为逻辑结构。通常分为 四类基本结构： 一、集合 结构中的数据元素除了同属于一种类 型外，别无其它关系。 二、线性结构 结构中的数据元素之间存在一对 一的关系。 三、树型结构 结构中的数据
5、元素之间存在一 对多的关系。 四、图状结构或网状结构 结构中的数据元素之 间存在多对多的关系。 数据结构的形式定义为：数据结构是一个二元组： Data-Structure=(D，S) 其中：D是数据元素的有限集，S是D上关系的有 限集。 例 复数的数据结构定义如下： Complex=(C，R) 其中：C是含两个实数的集合C1，C2，分别 表示复数的实部和虚部。R=P，P是定义在集 合上的一种关系C1，C2。 数据结构在计算机中的表示称为数据的物理结构， 又称为存储结构。 数据对象可以是有限的，也可以是无限的。 数据结构不同于数据类型，也不同于数据对象， 它不仅要描述数据类型的数据对象，而且要描
6、述 数据对象各元素之间的相互关系。 抽象数据类型：一个数学模型以及定义在该模型 上的一组操作。 抽象数据类型实际上就是对该数据结构的定 义。因为它定义了一个数据的逻辑结构以及在此 结构上的一组算法。 用三元组描述如下： （，） 数据结构在计算机中有两种不同的表示方法： 顺序表示和非顺序表示 由此得出两种不同的存储结构：顺序存储结构 和链式存储结构 顺序存储结构:用数据元素在存储器中的相对位 置来表示数据元素之间的逻辑关系。 链式存储结构：在每一个数据元素中增加一个 存放地址的指针（ ），用此指针来表示数据元素 之间的逻辑关系。 数据类型：在一种程序设计语言中，变量所具有 的数据种类。 例1、
7、在FORTRAN语言中，变量的数据类型有 整型、实型、和复数型 例2、在C语言中 数据类型：基本类型和构造类型 基本类型：整型、浮点型、字符型 构造类型：数组、结构、联合、指针、枚举型、 自定义 数据对象：某种数据类型元素的集合。 例3、整数的数据对象是-3，-2，-1，0，1， 2，3， 英文字符类型的数据对象是A，B，C，D，E， F， 1.3 抽象数据类型的表示和实现 P11 1.4 算法和算法分析 算法：是对特定问题求解步骤的一种描述 算法是指令的有限序列，其中每一条指令表 示一个或多个操作。 算法具有以下五个特性： （1）有穷性 一个算法必须总是在执行有穷步之 后结束，且每一步都在有
8、穷时间内完成。 （2）确定性 算法中每一条指令必须有确切的含 义。不存在二义性。且算法只有一个入口和一个 出口。 （3）可行性 一个算法是可行的。即算法描述的 操作都是可以通过已经实现的基本运算执行有限 次来实现的。 4）输入 一个算法有零个或多个输入，这些输入 取自于某个特定的对象集合。 5）输出 一个算法有一个或多个输出，这些输出 是同输入有着某些特定关系的量。 1.4.2 算法设计的要求 评价一个好的算法有以下几个标准: (1) 正确性(Correctness ) 算法应满足具体问 题的需求。 (2)可读性(Readability) 算法应该好读。以有 利于阅读者对程序的理解。 (3)健
9、状性(Robustness) 算法应具有容错处理。 当输入非法数据时，算法应对其作出反应，而不 是产年莫名其妙的输出结果。 (4)效率与存储量需求 效率指的是算法执行的时 间；存储量需求指算法执行过程中所需要的最大 存储空间。一般，这两者与问题的规模有关。 1.4.3 算法效率的度量 对一个算法要作出全面的分析可分成两用人才 个阶段进行，即事先分析和事后测试 事先分析 求出该算法的一个时间界限函数 事后测试 收集此算法的执行时间和实际占用空 间的统计资料。 定义：如果存在两个正常数c和n0，对于所有的 nn0，有f(n) cg(n) 则记作 f(n)=O(g(n) 一般情况下，算法中基本操作重
10、复执行的次 数是问题规模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; 由于是一个三重循环，每个循环从1到n，则总次 数为: nnn=n3 时间复杂度为T(n)=O(n3) 频度：是指该语句重复执行的次数 例 +x;s=0; 将x自增看成是基本操作，则语句频度为，即时 间复杂度为(1) 如果将s=0也看成是基本操作，则语句频度为， 其时间复杂度仍为(1)，即常量阶。 例、for(I=1;I=n;+I) +x;s+=
11、x; 语句频度为：2n其时间复杂度为：O(n) 即时间复杂度为线性阶。 例、for(I=1;I=n;+I) for(j=1;j=n;+j) +x;s+=x; 语句频度为：2n2 其时间复杂度为：O(n2) 即时间复杂度为平方阶。 定理：若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; 语句频度为： 1+2+3+n-2=(1+n-2) (n- 2)/2 =(n-1)(n-2)/2 =n2-3n+2 时间复杂度为O(n2) 即此算法的时间
12、复杂度为平方阶. 一个算法时间为O(1)的算法，它的 基本运算执行的次数是固定的。因此，总 的时间由一个常数（即零次多项式）来限 界。而一个时间为O(n2)的算法则由一个二 次多项式来限界。 以下六种计算算法时间的多项式是最常用 的。其关系为： O(1)O(logn)O(n)O(nlogn) O(n2)O(n3) 指数时间的关系为： O(2n)O(n!)1 -I) change=false; for(j=0;jaj+1) aj aj+1; change=TURE 最好情况：0次 最坏情况：1+2+3+n-1 =n(n-1)/2 平均时间复杂度为:O(n2) 1.4.4算法的存储空间需求 空间复
13、杂度:算法所需存储空间的度量，记 作: S(n)=O(f(n) 其中n为问题的规模(或大小) 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.3.1 线性链表 2.3.2 循环链表 2.3.3 双向链表 2.4 一元多项式的表示及相加 2.1 线性表的逻辑结构 线性表(Linear List) ：由n(n)个数据元素(结 点)a1，a2， an组成的有限序列。其中数据元 素的个数n定义为表的长度。当n=0时称为空表， 常常将非空的线性表(n0)记作： (a1，a2，an) 这里的数据元素ai(1in)只是一个抽象的符号， 其具体含义在不同的情况下可
14、以不同。 例1、26个英文字母组成的字母表 （A，B，C、Z） 例2、某校从1978年到1983年各种型号的计算 机拥有量的变化情况。 （6，17，28，50，92，188） 姓 名学 号性 别年龄 健康情况 王小林790631 男 18 健康 陈 红790632 女 20 一般 刘建平790633 男 21 健康 张立立790634 男 17 神经衰弱 . . . 例4、一副扑克的点数 （2，3，4，J，Q，K，A） 从以上例子可看出线性表的逻辑特征是： 在非空的线性表，有且仅有一个开始结点a1， 它没有直接前趋，而仅有一个直接后继a2； 有且仅有一个终端结点an，它没有直接后继， 而仅有一
15、个直接前趋a n-1； 其余的内部结点ai(2in-1)都有且仅有一个 直接前趋a i-1和一个直接后继a i+1。 线性表是一种典型的线性结构。 数据的运算是定义在逻辑结构上的，而运算的 具体实现则是在存储结构上进行的。 抽象数据类型的定义为：P19 算法2.1 例2-1 利用两个线性表LA和LB分别表示两个集合 A和B，现要求一个新的集合A=AB。 void union(List Lb-len=listlength(Lb); for(I=1;I=lb-len;I+) getelem(lb，I，e); if(!locateelem(la，e， equal)listinsert(la，+la-
16、en，e) 算法2.2 例2-2 巳知线性表LA和线性表LB中的数据 元素按值非递减有序排列，现要求将LA和 LB归并为一个新的线性表LC，且LC中的元 素仍按值非递减有序排列。 此问题的算法如下： void mergelist(list la，list lb，list I=j=1;k=0; la-len=listlength(la); lb-len=listlength(lb); while(I=la-len)getelem(lb，j， bj); if(ai=bj)listinsert(lc，+k， ai);+I; elselistinsert(lc，+k，bj);+j; while(I=l
17、a-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( a i+1)和第i个数据元素的存储位置 LOC(a I )之间满足下列关系： LOC(a i
18、+1)=LOC(a i)+l 线性表的第i个数据元素ai的存储位置为： LOC(ai)=LOC(a1)+(I-1)*l 由于C语言中的一维数组也是采用顺序存储 表示，故可以用数组类型来描述顺序表。 又因为除了用数组来存储线性表的元素之 外，顺序表还应该用一个变量来表示线性 表的长度属性，所以我们用结构类型来定 义顺序表类型。 # define ListSize 100 typedef int DataType; typedef struc DataType dataListSize; int length; Sqlist; 2.2.2 顺序表上实现的基本操作 在顺序表存储结构中，很容易实现线
19、性表的一些操作，如线性表的构造、第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.3 Void InsertList(Sqlist*L，DataType x，int I) int j; if(Il.length+1) printf(“Position e
20、rror”); return ERROR if(l.length=ListSize) printf(“overflow”); exit(overflow); for(j=l.length-1;j=I-1;j-) l.dataj+1=l.dataj; l.dataI-1=x; l.length+; 现在分析算法的复杂度。 这里的问题规模是表的长度，设它的值 为。该算法的时间主要化费在循环的结点 后移语句上，该语句的执行次数（即移动 结点的次数）是。由此可看出，所需移动 结点的次数不仅依赖于表的长度，而且还 与插入位置有关。 当时，由于循环变量的终值大于初值，结 点后移语句将不进行；这是最好情况，
21、其 时间复杂度O（1）； 当=1时，结点后移语句将循环执行n次， 需移动表中所有结点，这是最坏情况， 其时间复杂度为O（n）。 由于插入可能在表中任何位置上进行，因 此需分析算法的平均复杂度 在长度为n的线性表中第i个位置上插入一 个结点，令Eis(n)表示移动结点的期望值（即移动 的平均次数），则在第i个位置上插入一个结点的 移动次数为n-I+1。故 Eis(n)= pi(n-I+1) 不失一般性，假设在表中任何位置(1in+1) 上插入结点的机会是均等的，则 p1=p2=p3=p n+1=1/(n+1) 因此，在等概率插入的情况下， Eis(n)= (n-I+1)/(n+1)=n/2 也就
22、是说，在顺序表上做插入运算，平均要移动 表上一半结点。当表长 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(Il.length) printf(“Position error”); return ERROR for(j=i;j
23、data=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， 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; return(head); 说明：第一个生成
25、的结点是开始结点，将开始结点 插入到空表中，是在当前链表的第一个位置上插 入，该位置上的插入操作和链表中其它位置上的 插入操作处理是不一样的，原因是开始结点的位 置是存放在头指针（指针变量）中， 而其余结点的位置是在其前趋结点的指针域中。 算法中的第一个if语句就是用来对第一个位置上的 插入操作做特殊处理。算法中的第二个if语句的作 用是为了分别处理空表和非空表两种不同的情况， 若读入的第一个字符就是结束标志符，则链表 head是空表，尾指针r亦为空，结点*r不存在； 否则链表head非空，最后一个尾结点*r是终端结 点，应将其指针域置空。 如果我们在链表的开始结点之前附加一个 结点，并称它为
26、头结点，那么会带来以下两个优 点： a、由于开始结点的位置被存放在头结点的指 针域中，所以在链表的第一个位置上的操作就 和在表的其它位置上的操作一致，无需进行特殊 处理； b、无论链表是否为空，其头指针是指向头结点 在的非空指针（空表中头结点的指针域为空）， 因此空表和非空表的处理也就统一了。 其算法如下： linklist createlistr1( ) char ch; linklist head=(linklist)malloc(sizeof(listn ode); listnode *p，*r r=head; while(ch=getchar( )!= n p=(listnode*)m
27、alloc(sizeof(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访问结点， 而只能从链表的头指针出发，顺链域
28、next逐个 结点往下搜索，直到搜索到第i个结点为止。 因此，链表不是随机存取结构。 设单链表的长度为n，要查找表中第i个结 点，仅当1in时，i的值是合法的。但有时 需要找头结点的位置，故我们将头结点看做是 第0 个结点，其算法如下： Listnode * getnode(linklist head ， int i) int j; listnode * p; p=head;j=0; while(pnext j+; if (i=j) return p; else return NULL; 2、按值查找 按值查找是在链表中，查找是否有结点值等于 给定值key的结点，若有的话，则返回首次找到的 其
29、值为key的结点的存储位置；否则返回NULL。查 找过程从开始结点出发，顺着链表逐个将结点的 值和给定值key作比较。其算法如下： Listnode * locatenode(linklist head，int key) listnode * p=headnext; while( p return p; 该算法的执行时间亦与输入实例中的的取值key 有关，其平均时间复杂度的分析类似于按序号查 找，也为O(n)。 三、插入运算 插入运算是将值为x的新结点插入到 表的第i个结点的位置上，即插入到ai-1与ai 之间。因此，我们必须首先找到ai-1的存储 位置p，然后生成一个数据域为x的新结点 *p
30、，并令结点*p的指针域指向新结点，新 结点的指针域指向结点ai。从而实现三个结 点ai-1，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时，g
31、etnode找到的是头结点，当 i=n+1时，getnode找到的是结点an。因此，用 i-1做实参调用getnode时可完成插入位置的合法 性检查。算法的时间主要耗费在查找操作 getnode上，故时间复杂度亦为O(n)。 四、删除运算 删除运算是将表的第i个结点删去。因为在单 链表中结点ai的存储地址是在其直接前趋结点a a i-1的指针域next中，所以我们必须首先找到 a i-1的存储位置p。然后令pnext指向ai的直 接后继结点，即把ai从链上摘下。最后释放结点ai 的空间，将其归还给“存储池”。此过程为： 具体算法如下： void deletelist(linklist head
32、， int i) listnode * p， *r; p=getnode(head，i-1); if(p= =NULL | pnext= =NULL) return ERROR; r=pnext; pnext=rnext; free( r ) ; 设单链表的长度为n，则删去第i个结点仅 当1in时是合法的。注意，当i=n+1时， 虽然被删结点不存在，但其前趋结点却存在， 它是终端结点。因此被删结点的直接前趋*p 存在并不意味着被删结点就一定存在，仅当 *p存在（即p!=NULL）且*p不是终端结点 （即pnext!=NULL）时，才能确定被删结 点存在。 显然此算法的时间复杂度也是O(n)。
33、从上面的讨论可以看出，链表上实现插入 和删除运算，无须移动结点，仅需修改指针。 2.3.2 循环链表 循环链表时一种头尾相接的链表。其特 点是无须增加存储量，仅对表的链接方式 稍作改变，即可使得表处理更加方便灵活。 单循环链表：在单链表中，将终端结点的指 针域NULL改为指向表头结点的或开始结 点，就得到了单链形式的循环链表，并简 单称为单循环链表。 为了使空表和非空表的处理一致，循 环链表中也可设置一个头结点。这样，空 循环链表仅有一个自成循环的头结点表示。 如下图所示： a1 an . head 非空表 空表 在用头指针表示的单链表中，找开始结点a1 的时间是O(1)，然而要找到终端结点a
34、n，则需 从头指针开始遍历整个链表，其时间是O(n) 在很多实际问题中，表的操作常常 是在表的首尾位置上进行，此时头指针表 示的单循环链表就显得不够方便.如果改用 尾指针rear来表示单循环链表，则查找开 始结点a1和终端结点an都很方便，它们的 存储位置分别是(rearnext) next和 rear，显然，查找时间都是O(1)。因此， 实际中多采用尾指针表示单循环链表。 由于循环链表中没有NULL指针，故涉 及遍历操作时，其终止条件就不再像非循 环链表那样判断p或pnext是否为空， 而是判断它们是否等于某一指定指针，如 头指什或尾指针等。 例、在链表上实现将两个线性表(a1，a2， a3
35、，an)和(b1，b2，b3，bn)链接成一 个线性表的运算。 linklist connect(linklist heada，linklist headb) linklist p=headanext; headanext=(headbnext) next free(headbnext); headbnext=p; return(headb); 2.3.3双链表 双向链表(Double linked list):在单链表 的每个结点里再增加一个指向其直接前趋 的指针域prior。这样就形成的链表中有两 个方向不同的链，故称为双向链表。形式 描述为： typedef struct dlistno
36、de datatype data; struc dlistnode *prior，*next; dlistnode; typedef dlistnode * dlinklist; dlinklist head; 和单链表类似，双链表一般也是由头 指针唯一确定的，增加头指针也能使双链 表上的某些运算变得方便，将头结点和尾 结点链接起来也能构成循环链表，并称之 为双向链表。 设指针p指向某一结点，则双向链表结 构的对称性可用下式描述： (pprior)next=p=(p next)prior 即结点*p的存储位置既存放在其前趋结 点*(pprior)的直接后继指针域中，也 存放 在它的后继结点*(
37、pnext)的直接 前趋指针域中。 双向链表的前插操作算法如下： void dinsertbefor(dlistnode *p， datatype x) dlistnode *q=malloc(sizeof(dlistnode); qdata=x; qprior=pprior; qnext=p; ppriornext=q; pprior=q; void ddeletenode(dlistnode *p) ppriornext=pnext; pnextprior=pprior; free(p); 注意：与单链表的插入和删除操作不同的 是，在双链表中插入和删除必须同时修改 两个方向上的指针。上述两
38、个算是法的时 间复杂度均为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)是限制在表的一端进行插入和 删除运算的线性表，通常称插入、删除的这 一端为栈顶(Top)，另一端为栈底(Bottom)。 当表中没有元素时称为空栈。 假设栈S=(a1，a2，a3，an)，则a1称 为栈底元素，an为栈顶元素。栈中元素按a1， a2，a3，an的次序进栈，退栈的第一
39、个元 素应为栈顶元素。换句话说，栈的修改是按 后进先出的原则进行的。因此，栈称为后进 先出表（LIFO）。 3.1.2 顺序栈 由于栈是运算受限的线性表，因此线 性表的存储结构对栈也适应。 栈的顺序存储结构简称为顺序栈，它 是运算受限的线性表。因此，可用数组来 实现顺序栈。因为栈底位置是固定不变的， 所以可以将栈底位置设置在数组的两端的 任何一个端点；栈顶位置是随着进栈和退 栈操作而变化的，故需用一个整型变量top 例、一叠书或一叠盘子。 栈的抽象数据类型的定义如下：P44 a n a n-1 a2 a1 栈顶 栈底 top 7 6 5 4 3 2 1 -1 来指示当前栈顶的位置，通常称top
40、为栈顶指 针。因此，顺序栈的类型定义只需将顺序 表的类型定义中的长度属性改为top即可。 顺序栈的类型定义如下： # define StackSize 100 typedef char datatype; typedef struct datatype datastacksize; int top; seqstack; 设S是SeqStack类型的指针变量。若栈 底位置在向量的低端，即sdata0是栈 底元素，那么栈顶指针stop是正向增加 的，即进栈时需将stop加1，退栈时需 将stop 减1。因此，stoptop =stacksize-1表示栈满。当 栈满时再做进栈运算必定产生空间溢出，
41、 简称“上溢”;当栈空时再做退栈运算也将 产生溢出，简称“下溢”。上溢是一种出 错状态，应该设法避免之；下溢则可能是 正常现象，因为栈在程序中使用时，其初 态或终态都是空栈，所以下溢常常用来作 为程序控制转移的条件。 3、判断栈满 int stackfull(seqstack *s) return(stop=stacksize-1); 4、进栈 void push(seqstack *s，datatype x) if (stackfull(s) error(“stack overflow”); sdata+stop=x; 1、置空栈 void initstack(seqstack *s) st
42、op=-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 enpty”); return sdatastop; 3.1.3 链栈 栈的链式存储结构称
43、为链栈，它是运算 是受限的单链表，克插入和删除操作仅限 制在表头位置上进行.由于只能在链表头部 进行操作，故链表没有必要像单链表那样 附加头结点。栈顶指针就是链表的头指针。 链栈的类型说明如下： typedef struct stacknode datatype data struct stacknode *next stacknode; Void initstack(seqstack *p) ptop=null; int stackempty(linkstack *p) return ptop=null; Void push(linkstack *p,datatype x) stacknod
44、e *q q=(stacknode*)malloc(sizeof(stackn ode); 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.”); return
45、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
46、 (“%”,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( ); whil
47、e(ch!=eof) while(ch!=eof 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)。 例如：排队购物。操作系统中的作业排队。先进 入队列的成员
48、总是先离开队列。因此队列亦称作先 进先出(First In First Out)的线性表，简称FIFO 表。 当队列中没有元素时称为空队列。在空队列中依 次加入元素a1,a2,an之后，a1是队头元素，an是队 尾元素。显然退出队列的次序也只能是a1,a2,an ， 也就是说队列的修改是依先进先出的原则进行的。 下图是队列的示意图： a1a2an 出队入队 队头 队尾 队列的抽象数据定义见书59 3.4.2 循环队列队列的顺序表示和实现 队列的顺序存储结构称为顺序队列，顺序队 列实际上是运算受限的顺序表，和顺序表一样， 顺序队列也是必须用一个向量空间来存放当前队 列中的元素。由于队列的队头和队
49、尾的位置是变 化的，因而要设两个指针和分别指示队头和队尾 元素在队列中的位置，它们的初始值地队列初始 化时均应置为。入队时将新元素插入所指的位 置，然后将加。出队时，删去所指的元素，然 后将加并返回被删元素。由此可见，当头尾指 针相等时队列为空。在非空队列里，头指针始终 指向队头元素，而尾指针始终指向队尾元素的下 一位置。 0 1 2 3 Front rear abc Front rear (a)队列初始为空（b）A,B,C入队 b c front rear front rear （c) a出队 (d) b,c出队，队为空 和栈类似，队列中亦有上溢和下溢现象。此外， 顺序队列中还存在“假上溢”
50、现象。因为在入队 和出队的操作中，头尾指针只增加不减小，致使 被删除元素的空间永远无法重新利用。因此，尽 管队列中实际的元素个数远远小于向量空间的规 模，但也可能由于尾指针巳超出向量空间的上界 而不能做入队操作。该现象称为假上溢。 为充分利用向量空间。克服上述假上溢现象的方法 是将向量空间想象为一个首尾相接的圆环，并称 这种向量为循环向量，存储在其中的队列称为循 环队列（Circular Queue)。在循环队列中进行 出队、入队操作时，头尾指针仍要加1，朝前移 动。只不过当头尾指针指向向量上界 （QueueSize-1）时，其加1操作的结果是指向 向量的下界0。 这种循环意义下的加1操作可以
