描述
开 本: 16开纸 张: 胶版纸包 装: 平装-胶订是否套装: 否国际标准书号ISBN: 9787302499534丛书名: 计算机系列教材
编辑推荐
本书系统地介绍了各种数据结构的特点、存储结构及相关算法。书中采用C语言描述算法。主要内容包括：数据结构的基本概念、算法描述和算法分析初步；线性表、堆栈、队列、串、数组、树、图等结构；查找、排序等。每章后面配有小节、习题、讨论题。有配套的完整的习题与实验指导书，每一章节都给出了完整C语言和C 源程序示例。本书叙述清晰、深入浅出、注意实践、便于教学与实践。本书可作为高等院校计算机专业的教材，也可供从事计算机应用与工程工作的科技工作者自学参考。
内容简介
本书系统地介绍了各种数据结构的特点、存储结构及相关算法。书中采用C语言描述算法。主要内容包括数据结构的基本概念、算法描述和算法分析初步；线性表、堆栈、队列、串、数组、树、图等结构；查找、排序等。每章后面配有小结、习题、讨论题。本书有配套的完整的习题与实验指导书，每一章节都给出了完整的C语言和C 源程序示例。
本书叙述清晰，深入浅出，注意实践，便于教学与实践。
本书既可作为高等院校计算机专业的教材，也可供从事计算机应用与工程工作的科技工作者自学参考。
本书叙述清晰，深入浅出，注意实践，便于教学与实践。
本书既可作为高等院校计算机专业的教材，也可供从事计算机应用与工程工作的科技工作者自学参考。
目 录
目录
第1章绪论 1
1.1数据结构的概念 2
1.1.1引言 2
1.1.2数据结构的有关概念与术语 5
1.2抽象数据类型 7
1.3算法描述与分析 11
1.3.1什么是算法 11
1.3.2算法分析技术初步 13
1.4基本的算法策略 17
1.4.1穷举法 17
1.4.2递推法与迭代法 18
1.4.3分治法 20
1.4.4贪心算法 22
1.4.5动态规划 22
1.5案例分析 25
1.6小结 26
讨论小课堂1 27
习题1 28第2章线性表 30
2.1线性表的定义及其运算 30
2.1.1线性表的定义 30
2.1.2线性表的抽象数据类型 31
2.2线性表的顺序存储结构及实现 32
2.2.1顺序存储结构 32
2.2.2线性表在向量中基本运算的实现 34
2.3线性表的链表存储结构 39
2.3.1单链表 39
2.3.2线性链表基本运算的实现 42
2.4循环链表和双向链表 49
2.4.1循环链表 49
2.4.2双向链表 50
2.4.3顺序存储结构与链表存储结构的综合分析与比较
51
2.5单链表的应用 52
2.5.1多项式相加的链表存储结点 52
2.5.2多项式相加的算法实现 53
2.6小结 54
讨论小课堂2 55
习题2 55第3章栈和队列 57
3.1栈 57
3.1.1栈的定义 57
3.1.2栈的抽象数据类型 58
3.2栈的顺序存储结构及实现 59
3.2.1栈的顺序存储结构 59
3.2.2顺序栈的定义 60
3.3栈的链表存储结构及实现 62
3.4栈的应用 65
3.4.1表达式的计算 65
3.4.2子程序的嵌套调用 67
3.4.3递归调用 68
3.5队列 69
3.5.1队列的定义及运算 69
3.5.2队列的抽象数据类型 70
3.6队列的顺序存储结构及实现 70
3.7队列的链表存储结构及实现 74
3.8队列的应用 77
3.9算法实例——Hanoi塔问题 78
3.10小结 79
讨论小课堂3 80
习题3 81第4章串 83
4.1串的基本概念 83
4.1.1串的定义 83
4.1.2串的抽象数据类型 84
4.2串的存储与基本操作的实现 85
4.2.1定长顺序串 86
4.2.2堆串 86
4.2.3块链串 87
4.2.4串操作的实现 88
4.3串的模式匹配 91
4.3.1朴素模式匹配算法 92
4.3.2模式匹配的KMP算法 92
4.4串的应用举例： 文本编辑 97
4.5小结 99
讨论小课堂4 99
习题4 100第5章数组和广义表 101
5.1数组 102
5.1.1数组的基本概念 102
5.1.2二维数组 102
5.1.3数组的顺序存储方式 103
5.2矩阵的压缩存储 104
5.2.1特殊矩阵 104
5.2.2稀疏矩阵 107
5.3广义表 112
5.3.1广义表的定义 112
5.3.2广义表的存储结构 113
5.4案例分析 116
5.4.1概述和方法 116
5.4.2算法和程序 118
5.5小结 120
讨论小课堂5 120
习题5 120第6章树与二叉树 122
6.1树的概念及术语 123
6.1.1树的定义 123
6.1.2树的抽象数据类型 124
6.1.3树的表示方式 125
6.2二叉树 125
6.2.1二叉树的定义 125
6.2.2二叉树的抽象数据类型 126
6.2.3二叉树的重要性质 127
6.2.4二叉树的存储结构 128
6.3二叉树的遍历 130
6.3.1先序遍历 131
6.3.2中序遍历 131
6.3.3后根遍历 132
6.3.4按层遍历 133
6.3.5非递归遍历算法 133
6.3.6二叉树的建立 136
6.3.7二叉树遍历的应用举例 137
6.4二叉树与树、森林的转换 139
6.4.1树与二叉树的转换 139
6.4.2森林与二叉树的转换 140
6.5树的存储结构 141
6.5.1树的双亲表示法 142
6.5.2孩子表示法 142
6.5.3孩子兄弟表示法 143
6.6树的遍历 144
6.6.1一般树的遍历 144
6.6.2森林的遍历 145
6.7二叉树的应用 146
6.7.1哈夫曼树 146
6.7.2哈夫曼树的构造 146
6.7.3哈夫曼树的实现算法 148
6.7.4哈夫曼编码 149
6.8小结 150
讨论小课堂6 150
习题6 150第7章图 153
7.1图的基本概念 153
7.1.1图的定义 153
7.1.2图的术语 155
7.1.3图的抽象数据类型 156
7.2图的存储结构 157
7.2.1图的邻接矩阵 157
7.2.2邻接矩阵表示法的描述 159
7.2.3邻接矩阵表示下的基本操作的实现 160
7.2.4图的邻接链表 161
7.2.5图的邻接表表示法的描述 162
7.2.6邻接表表示下基本操作的实现 163
7.3图的遍历与图的连通性 165
7.3.1图的深度优先遍历 166
7.3.2图的广度优先遍历 168
7.3.3非连通图和连通分量 170
7.4图的最小生成树 170
7.4.1最小生成树的基本概念 170
7.4.2普里姆(Prim)算法 171
7.4.3克鲁斯卡尔（Kruskal）算法 174
7.5最短路径 175
7.5.1从某顶点到其余各顶点的最短路径 175
7.5.2每对顶点之间的最短路径 178
7.6拓扑排序与关键路径 180
7.6.1拓扑排序 180
7.6.2关键路径 183
7.7图的应用 189
7.7.1图在路由器寻径中的应用 189
7.7.2图在物流信息系统中应用 190
7.8小结 190
讨论题7 191
习题7 191第8章查找 193
8.1查找的基本概念 194
8.2静态查找表 195
8.2.1顺序表的查找 195
8.2.2有序表的折半查找 196
8.2.3索引顺序表查找 200
8.3动态查找表 201
8.3.1二叉排序树 201
8.3.2平衡二叉树 210
8.4案例分析 214
8.4.1直方图问题 214
8.4.2箱子装载问题 216
8.5小结 218
讨论小课堂8 218
习题8 219第9章排序 220
9.1排序的基本概念 220
9.2插入排序 221
9.2.1直接插入排序 221
9.2.2折半插入排序 222
9.2.3希尔排序 222
9.3交换排序 224
9.3.1冒泡排序 224
9.3.2快速排序 225
9.4选择排序 229
9.4.1简单选择排序 229
9.4.2堆排序 230
9.5归并排序 233
9.6基数排序 235
9.7小结 239
讨论小课堂9 240
习题9 240第10章索引结构与哈希 242
10.1静态索引结构 242
10.1.1索引表 242
10.1.2索引表查找 242
10.2动态索引结构（B-树和B 树） 245
10.2.1B-树的定义 245
10.2.2B-树的运算 246
10.2.3B 树 249
10.3键树及Trie树 250
10.3.1键树的定义 250
10.3.2双链树 251
10.3.3Trie树 252
10.4哈希表及其查找 253
10.4.1哈希表与哈希函数 253
10.4.2构造哈希函数的常用方法 254
10.4.3解决冲突的主要方法 256
10.4.4哈希查找的性能分析 260
10.5小结 261
讨论小课堂10 262
习题10 262参考文献 265
前 言
前言数据结构与算法是计算机专业重要的专业基础课程与核心课程之一。从理论上讲，通过学习数据结构可以使学生掌握对不同数据结构的组织方法和对具体数据结构所实施的若干算法，并能分析算法的优劣。学习数据结构与算法的最终目的是提高学生的程序设计水平和能力。对于应用型人才培养应该注重能力的培养，而不是只满足于理论的掌握。因此，在本书的编写过程中遵循谭浩强教授提出的新三部曲“提出问题—解决问题—归纳分析”的写法，强调从实践中获取知识。本书给出了能够解决实际问题的大量算法，希望学生在阅读和总结这些算法的基础上提高程序设计的水平。因此，本书的大部分算法只要经过简单的修改就能上机运行，具有很好的实用价值，也给学习者带来了方便。（1） 深入浅出，通俗易懂。对数据结构的基本概念、基本理论的阐述注重科学严谨。同时从应用出发，对新概念的引入从实例着手。对各种基本算法描述尽量详细，叙述清楚。本书在讲解数据的存储结构时，使用了大量的图示和表格，有助于学生对数据结构的理解。（2） 理论联系实际。为了巩固所学的理论知识，每章都附有练习题和讨论题，供学生进行书面练习、上机作业时选用和讨论。针对学生中普遍存在的“只懂概念不懂编程”的问题，配套有完整的习题与实验指导书，每一章节都给出了完整的C语言和C 源程序示例，供学生参考模拟，从而提高学生的程序设计能力。数据结构课程的一个重要任务是培养学生进行复杂程序设计的能力，目的在于提高学生的程序设计能力和进行规范化程序设计的素养。（3） 循序渐进，逐步加深。由于采用了C语言和C 语言面向对象的方法描述数据结构，对于低年级学生来说存在一定难度。为了使读者更好地学习数据结构自身的知识内容，克服描述工具所带来的困难，本书对此做了独特处理。本书可以作为普通高等院校计算机专业本科和专升本的教材。由于资源翔实、通俗易懂，对书中内容适当取舍之后，也可作为高等职业技术和专科教育的计算机专业教材。同时，本书还可作为研究生考试和各类认证考试的复习参考书，以及计算机应用工作者和工程技术人员的参考书。本书由汪沁、奚李峰主编。其中，第1～3章、第9章和实验指导由汪沁、奚李峰编写；第6章、第10章由邓芳编写；第4章、第7章由刘晓利编写；第5章、第8章由金冉、陈慧编写。全书由汪沁、奚李峰统编。考虑到在数据结构与算法的学习中，教师需要在课堂上对大量的算法进行讲解，而学生应该在此基础上大量阅读并理解数据结构经典算法，因此本书对算法都进行了较为详细的注释。对一些难度比较大的算法，在用语言描述之前，还对算法进行了分析。由于编者水平有限，疏漏在所难免，欢迎广大读者批评指正并提出宝贵意见。
编者2018年5月
编者2018年5月
免费在线读
第3章栈 和 队 列栈和队列是使用频率最高的数据结构。栈和队列是两种特殊的线性结构。它们都与第2章中的线性表有密切的联系（经过某种限制以后）。一方面，栈和队列的逻辑结构与线性表相同；另一方面，栈和队列的基本运算与线性表的基本运算十分类似，可以看成线性表运算的子集。因此，可将栈和队列看成两种特殊的线性表。【案例引入】在日常生活中经常会遇到栈或队列的实例。例如，单车道的死胡同，铁路调度等都是栈的例子。比如，可以把放在桌上的一叠书看成一个栈，并约定不能把书插入中间，或从中间把书抽出，只能从上面取书或放书。等待购物的顾客和民航机票订购中都用到队列。栈和队列还广泛应用于各种软件系统之中。3.1栈〖*4/5〗3.1.1栈的定义栈可以看成一种“特殊的”线性表，这种线性表上的插入和删除运算限定在表的某一端进行。允许进行插入和删除的这一端称为栈顶，另一端称为栈底。处于栈顶位置的数据元素称为栈顶元素。在如图3.1(b)所示的栈中，元素是以a1,a2，…，an的顺序进栈，因此栈底元素是a1,栈顶元素是an。不含任何数据元素的栈称为空栈。图3.1羊肉串和栈可以用一个例子说明栈结构的特征。我们经常吃的羊肉串，假设是图3.1(a)中的，铁签子可以穿上若干羊肉块。现有五小块羊肉，分别编号为①～⑤，按编号的顺序穿进铁签子上，如图3.1(a)所示。此时若吃第④块羊肉，必须先拿掉或者吃掉第⑤块后才有可能（当然此处排除直接从中间咬的可能性）。若要吃第①块羊肉，则必须等到⑤④③②依次都退出后才行。这里，吃羊肉的原则是后穿上去的先吃到。换句话说，先穿上去的后吃到。问题： 你还能举出在我们生活中和栈相关的实例吗？栈可以比作这里的死胡同，栈顶相当于胡同口，栈底相当于胡同的另一端，进、出胡同可看作栈的插入、删除操作，也称为进栈、出栈操作。进栈、出栈都在栈顶进行，进出都经过胡同口。这表明栈的操作原则是先进后出（First In Last Out，FILO）或称后进先出（Last In First Out，LIFO）。因此，栈又称为后进先出线性表。栈的基本操作除了进栈、出栈外，还有初始化、判空和取栈顶元素等。3.1.2栈的抽象数据类型〖*4/5〗1. 栈的抽象数据类型ADT Stack{ 数据对象: D={ai| ai∈ElemSet,i=1,2,…,nn≥0;} 数据关系: R={|,ai, ai＋1∈D, i=1,2,…,n; a1 无前驱,an无后继;} 约定a1 端为栈底,an端为栈顶。 基本操作: (1) 初始化一个空栈;(2) 判栈空,空栈返回True,否则返回False;(3) 入栈,在栈顶插入一个元素;(4) 出栈,在栈顶删除一个元素;(5) 取栈顶元素值;(6) 置栈为空状态;(7) 求栈中数据元素的个数;(8) 销毁栈; 等等} ADTStack;2. 下面先举一个简单例子来说明栈的应用例3.1程序员在终端输入程序时，不能保证不出差错，但可以在发现敲错时及时纠正。例如，每当敲错了一个键的时候，可以补敲一个退格符’#’，以表示前一个字符无效；如果发现当前一行有错，可以敲入一个退行符’@’,以表示’@’与前一个换行符之间的字符全部无效。例如，假设在终端上输入了这样两行字符:BGE##EGIM#NRAD(A@READ(A)则实际有效的是下面两行字符:BEGINREAD(A)为此，需要一个简单的输入处理程序来完成上述修改。程序中设一个栈来逐行处理从终端输入的字符串。每次从终端接收一个字符后先做如下判别： 如果它既不是退格符也不是退行符，则将该字符压入栈顶；如果是退格符，则从栈顶删去一个字符；如果它是退行符，就把字符栈清为空栈。上述处理过程可用类C的算法如下。void LineEdit() { /利用字符栈S,从终端接收一行并传送至调用过程的数据区/InitStack(S);/构造空栈S/ch=getchar(); /从终端接收第一个字符/while(ch!=EOF) /EOF为全文结束符/{ while(ch!=EOF && ch!=’\n’){switch(ch){ case ‘#’: Pop(S,ch); break; /仅当栈非空时退栈/case ‘@’: InitStack(S);break;/重置S为空栈/default: Push(S,ch); /有效字符进栈,未考虑栈满的情况/}ch=getchar(); /从终端接收下一个字符/}/将从栈底到栈顶的栈内字符传送至调用过程的数据区/ClearStack(S);/重置S为空栈/if(ch!=EOF) ch=getchar();}DestroyStack(S);/释放栈空间/}/LineEdit/本算法并不是C语言源代码，而是一种方法和思路的示意。栈在计算机内究竟怎样存储、怎样进栈和出栈，将在下面做详细介绍。问题： 栈和线性表有什么不同？3.2栈的顺序存储结构及实现与线性表类似栈也有两种存储结构，即顺序存储和链表存储结构。本节介绍栈的顺序存储结构。栈的顺序存储结构亦称顺序栈。3.2.1栈的顺序存储结构栈的顺序存储结是利用一批地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时设指针top指向栈顶元素的当前位置。通常用一维数组来实现栈的顺栈存储，习惯上以数组小下标的一端做栈底，当top=0时为空栈。在数据元素不断进栈时，栈顶指针top不断地加1，当top达到数组的最大下标值时为栈满。栈的顺序存储结构描述为：#define MAXSIZE 100typedef int ElemType;typedef struct { ElemType elem［MAXSIZE］;int top;}SqStack;/顺序栈的类型标识符/SqStackS;/说明S是栈变量/其中SqStack是顺序栈的类型标识符，S是一个栈。假设MAXSIZE取值为６，图3.2展示了顺序栈S中数据元素和栈顶指针top的关系。为了与前面所述top=0为空栈相一致，图中未画出S.elem［0］。逻辑上可利用有效空间为S.elem［1］,…,S.elem［5］。图3.2栈的顺序存储结构其中图3.2(a)是空栈状态；图3.2(b)是进栈一个元素Ａ之后的状态；图3.2(c)是在图3.2(b)状态基础上连续将元素Ｂ、Ｃ、Ｄ、Ｅ进栈之后的状态，显然已经达到栈满状态，此时不允许任何元素进栈。图3.2(d)是在图3.2(c)状态基础上，出栈一个元素后的栈状态。在面向对象的程序设计中，通常将数据元素的存储和对数据的操作封装在一个类之中。在各种版本的使用C数据结构教材中，对于顺序存储结构描述在具体实现形式有所不同，但是本质上是相同的。3.2.2顺序栈的定义栈采用的顺序存储结构，可以作为类的数据成员。栈的各种操作的处理，可以作为类的函数成员。本节介绍顺序栈的类的定义，重点讨论栈的各种操作的算法。1. 初始化栈void InitStack(SqStack S)/构造一个空栈/{ S->top=-1;} /InitStack/2.进栈操作void Push(SqStack S, DataType x) /插入元素x为新的栈顶元素/{if(S->toptop ;S->elem[S->top]=x;}else printf(“Overflow ! \n”); /栈满/}/Push/3. 出栈操作/若栈不空,则删除栈顶元素,元素值由函数名返回。/ElemType Pop(SqStack p){if(S->top==-1){ printf(“Underflow!\n”); return -1;}/栈空,返回-1/else {x=S->elem［S->top］;S->top–;return x;}
} /Pop/以上算法中需注意的是在进栈时栈满的判断和出栈时栈空的判断。取栈顶元素的算法GetTop与出栈算法Pop相似，仅有一点不同，即前者不改变栈顶指针值。顺序存储结构条件下的多栈操作也是数据结构课程所讨论的内容。在计算机系统软件中，诸如各种高级语言的编译软件都离不开栈的操作，且往往是同时使用和管理多个栈。若让多个栈共用一个向量，其管理和运算都很复杂，这里仅介绍两个栈共用一个向量的问题。两个栈共用一个向量又有不同的分配方法，如图3.3所示。 图3.3两栈共用同一向量示意图图3.3(a)的方法是将向量平均分配给两个栈（设向量有n个元素），它们的栈底分别在下标为0和下标为(n-1)/2 1处，栈顶指针在进栈时作加1操作。如果其中一个栈已满，若还要进此栈，则此栈产生溢出，即使另一个栈仍有空间，也不能利用，这是它的局限性。如果让第二个栈底可以浮动，则实现的算法太麻烦。图3.3(b)所示的方法是两个栈底安排在向量的两端，一个在下标为0 处，另一个在下标为n-1处。两个栈顶指针可以向中间浮动，左栈进栈时，栈顶指针加1，右栈进栈时，栈顶指针减1。显然，这种方法向量空间利用率高。对于图3.3(b)的存储结构：typedef struct { DataType elem［n］;int top［2］;}DupSqStack;另外，还必须预先设置：int d［2］,z［2］;d［0］=-1; d［1］=n;/左、右栈判断栈空的条件/z［0］=1; z［1］=-1;/左、右栈进栈时栈顶指针的增量/在进行栈操作时，需要指定栈号： i=0为左栈，i=1为右栈；判断栈满的条件为：S->top［0］ 1==S->top［1］;进栈操作的算法为：void Push2(DupSqStack S; int i; ElemType x){if(S->top［0］ 1==S->top［1］) printf(“Stack Overflow!\n”) else {S->top［i］=S->top［i］ z［i］;S->elem［S->top［i］］=x;}}/Push2/出栈操作的算法为：ElemType Pop2(DupSqStack S; int i) { if(S->top［i］==d［i］) {printf(“Stack Underflow\n”);return -1;}else {x=S->elem［S->top［i］］;S->top［i］=S->top［］-z［i］;return x;}}/Pop2/3.3栈的链表存储结构及实现栈可以用单链表作为存储结构，链表中数据元素结点描述如下：typedef char ElemType;typedef struct Lsnode{ DataType data;struct Lsnode next;} Lsnode; /结点的类型标识符/Lsnode top;这里的栈顶指针top是用于存放结点首地址的指针类型的变量。图3.4展示了单链表栈的数据元素与栈顶指针top的关系。图3.4(a)是含有３个数据元素A、B、C的栈，Ａ是栈底元素，指针型变量top指向栈顶元素C上边的头结点；图3.4(b)是在图3.4(a)的基础之上出栈一个元素后的状态；图3.4(c)是在图3.4(b)的基础上又进栈一个元素Ｘ后的状态。需要指明的是，一个链表栈由栈顶指针top唯一确定。当top->next为NULL时是一个空栈。图3.4栈的链表存储结构如图3.4所示，每当进栈或出栈时栈顶指针top都要发生变化。由于top本身就是动态指针类型Lsnode top,如果要使进栈函数返回变化后的栈顶指针，就应写成两级指针： void Push(Lsnode top)，这样会使函数变得复杂难懂。解决问题的办法就是模仿单链表，设置一个头结点不存放数据，即使是一个空栈，该头结点也仍然存在。问题： 能否将链栈中的指针方向反过来，从栈底到栈顶？不行，如果反过来的话，删除栈顶元素时，为修改其前驱指针，需要从栈底一直找到栈顶。1. 单链表栈的主要算法1） 初始化空栈void InitStack(Lsnode top){ top->next=NULL; }调用此函数之前，在主调函数中（例如main()）说明一个指针变量后，先为它申请分配一个结点，然后调用初始化函数。例如:void main(){ Lsnode top1;top1=(Lsnode )malloc(sizeof(Lsnode));/这很重要/InitStack(top1);…;}2） 进栈操作 void Push(Lsnode top; ElemType x){p=(Lsnode )malloc(sizeof(Lsnode)); p->data=x; p->next=top->next;top->next=p;}/Push/ 3） 出栈操作 ElemType Pop(Lsnode top) { if(top->next!=NULL){ p=top->next; top->next=p->next;x=p->data; free(p); return x;}else {printf(“Stack null! \n”);return ‘#’;}}/Pop/由上述算法可看出，栈在链表存储结构条件下进栈一个元素时一般不考虑栈满上溢出问题，而出栈时必须考虑栈空问题。2. 多个链表栈的运算有时需要同时使用两个以上的栈，若用一个向量来处理是极不方便的，最好采用多个单链表做存储结构。将多个链表的指针放入一个一维数组之中：Lsnode top［n］;让top［0］,top［1］,…，top［n-1］指向n个不同的单链表。请注意，这里的每个链表都有附加头结点。操作时需先确定栈号i，然后以top［i］为栈顶指针进行栈操作极为方便。算法如下：1） 第i号栈进栈操作void Pushn(Lsnode top［n］; int i; ElemType x) {/已知元素x,进入第i个栈/p=(struct Lsnode)malloc(sizeof(struct Lsnode));/申请结点/p->data=x;p->next=top［i］->next;top［i］->next=p;}/Pushn/2） 第i号栈出栈一个元素ElemType Popn(Lsnode top［n］; int i) { if(top［i］->next!=NULL){ p=top［i］->next; top［i］->next=p->next;x=p->data; free(p);return x;}else {printf(“\nStack NULL!\n”); return#’; }}/Popn/在上述算法中，当指定了栈号i(0≤i≤n-1)之后，就仅对第i个栈链表进行操作。例如，设i=3,将x进栈，x元素就进入了第3号栈链表，同时，把top［3］重新指向新的栈顶元素，而其他栈链表不会产生变动。3.4栈的应用栈的应用十分广泛，栈在计算机系统软件中的作用十分重要。下面就表达式计算、子程序嵌套调用、递归调用和汉诺塔几个问题，讨论栈的应用。3.4.1表达式的计算对表达式进行处理计算是程序设计语言编译中的一个基本问题。要把一个表达式翻译成正确求值的一个机器指令序列，或者直接对表达式求值，首先要能够正确解释表达式。例如，要对下面的算术表达式求值：（5-3）×6 10/5首先要了解算术四则运算的规则。即：（1） 先乘除，后加减；（2） 同一个优先级，先左后右；（3） 先括号内，后括号外。由此，这个算术表达式的计算顺序应为：（5-3）×6 10/5=2×6 10/5=12 10/5=12 2=14任何一个表达式都是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。我们把运算符和界限符统称为算符，它们构成的集合命名为OP。根据上述三条运算规则，在运算的每一步中，任意两个相继出现的算符θ1和θ2之间的优先关系至多是下面三种关系之一： θ1θ2，θ1的优先权高于θ2。表3.1定义了算符之间的这种优先关系。表3.1算符之间的优先关系θ2
θ1 -*/（）# >><< <> > – >><< <> > >>>> <> > / >>>> <> > ( <<<< <= ) >>>> > > # <<<< < =由运算规则（3）结合表3.1，可得 、-、和/为θ1时的优先性均低于'(‘，但高于’)’。由规则（2）可知，当 θ1=θ2时，令θ1>θ2 ，在表3.1中作为θ1的’ ‘大于作为θ2的’ ‘。另外’#’是表达式的结束符。为了算法简洁，在表达式的最左边也虚设一个’#’构成整个表达式的一对括号。表3.1中有'(‘=’)’，这表示当左右括号相遇时，括号内的运算已经完成。同理表中’#’=’#’表示整个表达式求值完毕。在表3.1中，’)’与'(‘、’#’与’)’以及'(‘与’#’之间无优先关系，这是因为表达式中不允许它们相继出现，一旦遇到这种情况，则可以认为出了语法错误。在下面的讨论中，假定所输入的表达式不会出现语法错误。为了求解表达式，可以使用两个工作栈： 一个称作OPTR，用来存放运算符；另一个称作OPND，用来存放操作数或运算结果。算法的基本思想是：首先置操作数栈OPND为空，表达式起始符’#’为运算符栈OPTR的栈底元素；然后依次读入表达式中每一个字符，若是操作数则进OPND栈；若是运算符，则和OPTR的栈顶运算符比较优先权，然后做相应的操作，直至整个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为’#’）。下列算法采用类似C 的方式描述了这个求值过程。OperandType EvaluateExpression() {//求解算术表达式。设OPTR和OPND分别为运算符栈和运算数栈,OP为运算符集合SqStack OPTR,OPND;/初始化两个空栈/OPTR.Push(‘#’);/’#’进算符栈/c=getchar(); /读入一个字符/while(c!=’#’ || OPTR.GetTop()!=’#’)/GetTop()取栈顶元素,不出栈/{ if(!In(c,OP)) { OPND.Push(c); c=getchar();} /c是操作数,进栈。接收下一字符/else /c是算符的情况/switch(Precede(OPTR.GetTop(),c)/比较优先权/{ case ”: theta=OPTR.Pop(); /出栈一个算符theta/b=OPND.Pop(); a=OPND.Pop();/出栈两个操作数a,b/OPND.Push(Operate(a,theta,b));/计算中间结果,入栈/break;}/switch/}Return OPND.GetTop(); /最终结果在OPND栈顶,为函数返回结果/算法中还调用了两个函数。其中Precede是判定运算符栈的栈顶运算符θ1与读入的运算符θ2之间优先关系的函数；Operate为进行二元运算aθb的函数。例3.2利用算法EvaluteExpression对算术表达式3×(7-2)求值。在表达式两端先增加’#’改写为：#3(7-2)#具体操作过程如表3.2所示。表3.2表达式求值过程步骤OPTR栈OPND栈输入字符判别式主 要 操 作1#3(7-2)#是数据OPND.Push(‘3’)2#3(7-2)#’#”）’OPTR.Pop() 得 ‘-‘OPND.Pop() 得 ‘7’ OPND.Pop() 得 ‘2’Operate(‘7′,’-‘,’2’)OPND.Push(‘5’)8#（3 5)#'(‘=’)’OPTR.Pop() 消去一对括号9#3 5#’’>’#’OPTR.Pop() 得 ‘’OPND.Pop() 得 ‘5’ OPND.Pop() 得 ‘3’Operate(‘5′,’’,’3′)OPND.Push(’15’)10#15’#’=’#’OPTR.Pop()消去一对#号11空15 return 15所要计算的表达式在表3.2的中间部位，带下画线阴影的字符是当前读入的字符。当前读入的是操作数就进入OPND栈。当前读入的是运算符就与OPTR栈顶算符进行比较，结合上述算法对照表3.2读者可以自行分析，分三种情况处理。最后，当读入字符为’#’且OPTR栈顶元素也为’#’，不仅脱一对’#’，且将在OPND栈里的最终结果返回，至此算法结束。3.4.2子程序的嵌套调用在各种程序设计语言中都有子程序（或称函数、过程）调用功能。一个子程序还可以调用另一子程序。图3.5(a)展示的是由主程序开始的三层嵌套调用关系。图3.5子程序嵌套调用主函数main调函数func1时需记下返回地址R，func1调用func2需记下返回地址S，func2调用func3时需记下返回地址T。func3执行结束时返回到func2的地址T，依次返回到func1的地址S，最终返回到main的地址R。在编译软件内就设立一个栈专用于存放返回地址，在嵌套调用时返回地址一一入栈，调用结束时返回地址一一出栈，如图3.5(b)所示。这是一个典型的先进后出结构。3.4.3递归调用一个子程序可以直接或间接地调用自身。在一层层递归调用时，其返回地址和处在每一调用层的变量数据都需一一记下并进栈。返回时，它们一一出栈并且被采用。现以求阶乘的递归方法为例分析栈在递归中的应用。这样可以加深对递归调用的理解，提高运用递归方法进行程序设计的能力。求n!的递归方法思路是：n!=1n=0n×(n-1)n≥1与之相应的Ｃ函数框架是：int fac(int n){float p;if(n==0 || n==1)p=1;else p=nfac(n-1);return p;}在此函数中可理解为用fac(n)来求n!，那么用fac(n-1)就可以表示求(n-1)!。图3.6(a)展示了递归调用中执行情况。从图3.6(a)可以看到fac函数共被调用5次，它们依次是fac(5)、fac(4)、fac(3)、fac(2)、fac(1)。其中fac(5)是由main函数调用的，其余4次是在各层的fac函数中调用的。在某一层递归调用时，并未立即得到结果，而是进一步向深度递归调用。直到最内层函数执行n=1或n=0时，fac(n)才有结果。然后再一一返回，不断得到中间结果，直到返回主程序为止，可得到n!的最终结果。图3.6递归调用调用时把处在不同调用层的不同n值入栈，返回时再一一出栈参加计算。存放不同n值的栈如图3.6(b)所示。当然这里也用到了返回地址栈，在此不再重复。栈是一个基本的重要的数据结构。它有一重要参数就是栈顶指针top。top为零（对于顺序结构）或为NULL（对于链表）均表明是空栈。在进栈、出栈时，应注意栈满或栈空的判断处理。3.5队列〖*4/5〗3.5.1队列的定义及运算队列(queue)也是一种特殊的线性表。在现实生活中队列的例子很多，例如客户到银行办理业务往往需要排队，先来的先办理，晚来的则排在队尾等待，如图3.7(a)所示。抽象成逻辑图，如图3.7(b)所示。另外，队列在程序设计中也经常出现，一个典型的例子就是操作系统中的作业排队。在允许多道程序运行的计算机系统中，同时有几个作业运行。如果运行的结果都需要通过通道输出，那就按请示输出的先后次序排队。每当通道传输完毕可以接受新的输出任务时，队头的作业先从队列中出来进行输出操作。凡是申请输出的作业都从队尾进入队列。图3.7队列队列与栈不同,其所有的插入均限定在表的一端进行,而所有的删除则限定在表的另一端进行。允许插入的一端称队尾(rear),允许删除的一端称队头(front)。队列的结构特点是，先进入队的数据元素先出队。假设有队列Q=(a1,a2,…,an),则队列Q中的元素是按a1,a2,…,an的次序进队。第一个出队的应该是a1,第二个出队的应该是a2,只有在an-1出队后,an才可以出队,详见图3.7（b）。通常又把队列叫作先进先出(First In First Out，FIFO）表。在日常生活中,队列的例子到处皆是,如等待购物的顾客总是按先来后到的次序排成队列,先得到服务的顾客是站在队头的先来者,而后到的人总是排在队的末尾。在软件系统中，队列也是重要的数据结构。例如在实现树（参见第6章）或图（参见第7章）的广度遍历时，必须以队列为辅助存储结构。3.5.2队列的抽象数据类型（1） 与栈结构相似, 队列的抽象数据类型的描述如下：ADT Queue{ 数据对象: D={ai| ai∈ElemSet,i=1,2,…,nn≥0;} 数据关系: R={|,ai, ai＋1∈D, i=1,2,…,n; a1 无前驱,an无后继;} 约定 a1 端为队头, an端为队尾。 基本操作: (1) 初始化一个空队列; (2) 判队空,空队返回True,否则返回False; (3) 入队,在队尾插入一个元素; (4) 出队,在队头删除一个元素; (5) 取队头数据元素值; (6) 置队列为空状态; (7) 销毁队列;等等}ADT Linear_list;（2） 队列的实例。在日常生活中经常会遇到为了维护社会正常秩序而需要排队的情境，在计算机程序设计中也经常出现类似问题。数据结构“队列”与生活中的“排队”极为相似，也是按“先到先办”的原则行事的，并且严格限定： 既不允许“插队”，也不允许“中途离队”。3.6队列的顺序存储结构及实现队列的顺序存储结构,在计算机中常借助于一维数组来存储队列中的元素。为了指示队首和队尾的位置,尚需设置队头front和队尾rear两个指针,并约定头指针front总是指向队列中实际队头元素的前面一个位置,而尾指针rear总是指向队尾元素，如图3.8所示。图3.8队列顺序存储结构队列的顺序存储结构可描述为:typedef struct { ElemType elem［MAXSIZE］; /一维数组/int front,rear; /头、尾指针/} SeQueue;SeQueue Q;有一个能容纳6个元素的队列，图3.9是在进出队列时头、尾指针的变化示意图。图3.9(a)表示该队列的初始状态为空, rear=front=-1;图3.9(b)表示有3个元素a1、a2、a3相继入队列,所以尾指针rear从-1变化到2,而头指针front不变;图3.9(c)表示a1、a2、a3先后出队,头指针front的值从-1变化到2，队列成为空状态,此时rear=front=2;图3.9(d)表示3个元素a4、a5、a6依次进入队列,尾指针rear从2变化到5，头指针front不变仍然停留在位置2。这里有一现象，在队列为空时均有： rear=front。图3.9队列中元素和头尾指针的关系假若还有元素a7请求进入队列,由于队尾指针已经指向了队列的最后一个位置,因而插入a7就会发生“溢出”。但是,这时的队列并非真正满了,事实上队列中尚有3个空位。也就是说,系统作为队列用的存储区还没有满,但队列却发生了溢出,把这图3.10用平移元素的方法克服假溢出种现象称为“假溢出”。解决“假溢出”的方法有两种:(1) 采用平移元素的方法。即一旦发生“假溢出”就把整个队列的元素平移到存储区的首部。如图3.10所示,将a4、a5、a6平移到elem［0］～elem［2］,而将a7插到第3个位置上。显然平移元素的方法效率是很低的。(2) 将整个队列作为循环队列来处理。可以设想elem［0］接在elem［5］之后,如图3.11(a)所示。当发生假溢出时,可以把a7插入到第0个位置上。这样,虽然物理上队尾在队首之前,但逻辑上队首仍然在队尾前,作插入和删除运算时仍按“先进先出”的原则。图3.11(b)展示了元素a8和a9进入队列后的情形。此时队列已满,如果还要插入元素就会发生上溢。而它与图3.11(c)所示队列为空的情形一样,均有front==rear。这是一矛盾现象。在这种情况下,在循环队列中只凭等式rear==front无法判别队空还是队满。因此,可再设置一个布尔变量来区分队空和队满。或者不设布尔变量,而把尾指针rear加1后等于头指针front作为队满的标志，这意味着需要损失一个空间。或者反过来说,拥有MAXSIZE个数组元素的数组仅能表示一个长度为MAXSIZE-1的循环队列。以上两种方法都要多占存储空间,但后者循环队列比较方便。下面的讨论均是以循环队列为基础。此时判断队列为空的条件仍然是：front==rear问题： 由于顺序存储结构是一次性地分配空间，因此在入队列的操作中首先应该判别当前队列是否已经“满”了，那么队列满的判别条件又是什么呢？判断队列为满的条件则是：(rear 1)%MAXSIZE==front请注意，图3.11(c)就是循环队列为空状态的图示。图3.11(d)就是循环队列为满状态的图示。由于是循环队列，只要front==rear而不论它们具体等于什么下标值，均为空队。只要(rear 1)%MAXSIZE==front而不论它们具体等于什么下标值，均为满队。图3.11用循环队列的方法解决假溢出问题在队列循环中,每插入一个新元素,就把尾指针沿顺时针方向移动，即rear 1。由于本身是循环队列，当rear达到最大下标（MAXSIZE-1）时，再加1它就会越界，rear应该变为零值。所以需要将rear加1再对MAXSIZE取余，可得正确结果。进队操作的语句如下:rear=(rear 1)% MAXSIZE;elem［rear］=x;结合图3.11（a），MAXSIZE=6,假设原来rear=5已达到最大下标值。为使a7 进队，让rea 1=6再对6取余得零。rear=0,正好在elem［0］处插入元素a7。每删除一个新元素,就把头指针front沿顺时针方向移动一个位置,即front 1。同理，需要将front加1再对MAXSIZE取余。出队操作的语句如下:front=(front 1)% MAXSIZE;请特别注意，在循环队列出队或进队时，头、尾指针都要做加1后取余运算。下面给出循环队列主要操作的算法。(1) 将循环队列置为空的算法。void SetNULL(SeQueue Q){Q->front=-1; Q->rear=-1;}(2) 判断循环队列是否为空。int Empty(SeQueue Q){ if(Q.rear==Q.front)return(1);elsereturn(0);}(3) 进队。在循环队列中插入新的元素x。进队操作实质上是在队列尾指针处插入一个新的队尾元素x。进队操作首先要判断当前循环队列是否已满，如果队列已满，则输出提示信息；否则让尾指针加1对MAXSIZE取模后，x进队，存放在尾指针所指的位置。算法如下:void AddQ(SeQueueQ,ElemType x){if((Q->rear 1)% MAXSIZE==Q->front)printf(“Queue is FULL! \n”)else{Q->rear=(Q->rear 1)% MAXSIZE;Q->elem［Q->rear］=x;}}(4) 出队。出队操作实质上是删除队列中队首元素的操作。ElemType DelQ(SeQueueQ){ if(Q->front==Q->rear){ printf(“Queue is EMPTY! \n”);return -1;else { Q->front=(Q->front 1)% MAXSIZE;return(Q->elem［Q->front］);}}(5) 取队列中的队首元素。ElemType Front(SeQueueQ){ElemType x;if(Q->front==Q->rear){printf(“Queue is EMPTY! \n”);return(-1);}elsex=Q->elem［(Q->front 1)%MAXSIZE］;return (x);}问题： 判别循环队列为“空”的条件应该是什么？在队列初始化的函数中，设置队头和队尾指针均为0，那么能否由“队头指针为0”来作为队列空的判别条件呢？显然是不对的，由上页两个插图的例子就可见，由于队头指针和队尾指针都是“单方向”移动的，因此当队头指针“追上”队尾指针时，说明所有曾经插入队列的元素都已经出列，所以队列变空的条件应该是“两个指针指向循环队列中的同一位置”。3.7队列的链表存储结构及实现队列不仅可以采用顺序存储结构，也可以采用链表存储结构。用链表表示的队列简称为链队列，如图3.12所示。图3.12链队列示意图一个链队列显然需要两个指针才能唯一确定，它们分别指示队头和队尾，分别称为头指针front和尾指针rear。与线性表的单链表一样,为了操作方便起见,也给链队列添加了一个附加头结点,并令头指针指向front头结点,正好指向队列第一个数据结点的前一位置。由此,空的链队列的判别条件为头指针和尾指针均指向附加头结点,满足条件：front==rear详见图3.13(a)。链队列的进队和出队操作，属于链表的插入和删除操作的特殊情况,只是尚需修改尾指针或头指针。图3.13队列运算指针变化状况图3.13(b)是在(a)的基础上进队元素x后的情况。虽然，看上去链表有两个结点，其实是仅有一个数据元素的队列。图3.13(c)是在(b)的基础上再进队元素y后的情况。图3.13(d)是在(c)的基础上出队一个元素后的情况。出队在队头进行，队列中只剩下数据y的结点。除去空队情况外，头指针front总是指向队头元素前一位置，队尾指针rear总是指向队尾元素自身。链队列结点的结构可描述为:typedefstruct NodeType/数据元素结点的结构/{ElemType data;struct NodeType next;} NodeType;typedefstruct/队列头尾指针结构体/{NodeType front,rear;} LinkQueue;其中front和rear分别为队列的头指针和尾指针。下面给出实现链队列5种运算的具体算法。（1） 队列初始化/生成链队列的头结点,并令头指针和尾指针指向该结点,表示此队列为空/void SetNULL(LinkQueue Q){NodeType p;p=(NodeType )malloc(sizeof(NodeType));/分配一头结点/p->next=NULL;Q->front=p;Q->rear=p;}在主函数中应该这样处理：voidmain(){LinkQueue q1;SetNULL(&q1);/调用初始化函数,实参是地址/…;}结果如图3.13(a)所示。（2） 判队列是否为空。由于队列经过初始化之后，即使是空队也至少有一个头结点。在判断队列是否为空的函数中不会改变头尾指针，所以形参不必使用（LinkQueue Q）。int Empty(LinkQueue Q){if(Q.front==Q.rear) return(1); elsereturn(0);}（3） 进队，在队尾结点之后插入一个元素。void AddQ(LinkQueue Q,ElemType x){NodeType p;p=(NodeType )malloc(sizeof(NodeType));p->data=x;p->next=NULL;Q->rear->next=p;Q->rear=p;}（4） 出队，删除队头元素。在链表队列中删除队头元素，首先要判断队列是否已空，图3.13(a)就是一个空队状态。因此，判断链队列是否已空就是判断头、尾指针是否相等。如果二者相等，则表明队列已空，输出提示信息；否则删除队列首部第一个有效元素，注意，这里不是指附加队头结点，在这个结点中没有队列的有效元素。在删除队头元素时，若队列中仅有一个有效元素，就会把尾指针一同删去。因此要注意防止尾指针丢失，具体算法如下：ElemType DelQ(LinkQueue Q) {NodeType p; ElemType x;if(Q->front==Q->rear) {printf(“QUEUE IS EMPTY\n”);x=-1;}else{p=Q->front->next;Q->front->next=p->next;if(p->next==NULL) Q->rear=Q->front;x=p->data; free(p)}return x;}问题： 你是否注意到算法中那个带有下画线的语句？它是否多余？能否删去？你一定看出问题来了吧!由于一般情况下，出队列的操作只涉及队头元素，因此不需要修改队尾指针，但当链队列中只有一个数据元素时，队头元素恰好也是队尾元素，当它被删除之后，队尾指针就“悬空”了，待下次再做入队操作时，就要产生指针的“悬空访问”的错误，因此在这种情况下必须同时修改尾指针。(5) 取队列首元素。由于在函数中不会改变头尾指针，所以形参不必使用（LinkQueue Q）。ElemType Front(LinkQueue Q){NodeType p;if(Q.front==Q.rear) {printf(“QUEUE IS EMPTY\n”); return -1;}else{p=Q.front->next;return p->data;
} /Pop/以上算法中需注意的是在进栈时栈满的判断和出栈时栈空的判断。取栈顶元素的算法GetTop与出栈算法Pop相似，仅有一点不同，即前者不改变栈顶指针值。顺序存储结构条件下的多栈操作也是数据结构课程所讨论的内容。在计算机系统软件中，诸如各种高级语言的编译软件都离不开栈的操作，且往往是同时使用和管理多个栈。若让多个栈共用一个向量，其管理和运算都很复杂，这里仅介绍两个栈共用一个向量的问题。两个栈共用一个向量又有不同的分配方法，如图3.3所示。 图3.3两栈共用同一向量示意图图3.3(a)的方法是将向量平均分配给两个栈（设向量有n个元素），它们的栈底分别在下标为0和下标为(n-1)/2 1处，栈顶指针在进栈时作加1操作。如果其中一个栈已满，若还要进此栈，则此栈产生溢出，即使另一个栈仍有空间，也不能利用，这是它的局限性。如果让第二个栈底可以浮动，则实现的算法太麻烦。图3.3(b)所示的方法是两个栈底安排在向量的两端，一个在下标为0 处，另一个在下标为n-1处。两个栈顶指针可以向中间浮动，左栈进栈时，栈顶指针加1，右栈进栈时，栈顶指针减1。显然，这种方法向量空间利用率高。对于图3.3(b)的存储结构：typedef struct { DataType elem［n］;int top［2］;}DupSqStack;另外，还必须预先设置：int d［2］,z［2］;d［0］=-1; d［1］=n;/左、右栈判断栈空的条件/z［0］=1; z［1］=-1;/左、右栈进栈时栈顶指针的增量/在进行栈操作时，需要指定栈号： i=0为左栈，i=1为右栈；判断栈满的条件为：S->top［0］ 1==S->top［1］;进栈操作的算法为：void Push2(DupSqStack S; int i; ElemType x){if(S->top［0］ 1==S->top［1］) printf(“Stack Overflow!\n”) else {S->top［i］=S->top［i］ z［i］;S->elem［S->top［i］］=x;}}/Push2/出栈操作的算法为：ElemType Pop2(DupSqStack S; int i) { if(S->top［i］==d［i］) {printf(“Stack Underflow\n”);return -1;}else {x=S->elem［S->top［i］］;S->top［i］=S->top［］-z［i］;return x;}}/Pop2/3.3栈的链表存储结构及实现栈可以用单链表作为存储结构，链表中数据元素结点描述如下：typedef char ElemType;typedef struct Lsnode{ DataType data;struct Lsnode next;} Lsnode; /结点的类型标识符/Lsnode top;这里的栈顶指针top是用于存放结点首地址的指针类型的变量。图3.4展示了单链表栈的数据元素与栈顶指针top的关系。图3.4(a)是含有３个数据元素A、B、C的栈，Ａ是栈底元素，指针型变量top指向栈顶元素C上边的头结点；图3.4(b)是在图3.4(a)的基础之上出栈一个元素后的状态；图3.4(c)是在图3.4(b)的基础上又进栈一个元素Ｘ后的状态。需要指明的是，一个链表栈由栈顶指针top唯一确定。当top->next为NULL时是一个空栈。图3.4栈的链表存储结构如图3.4所示，每当进栈或出栈时栈顶指针top都要发生变化。由于top本身就是动态指针类型Lsnode top,如果要使进栈函数返回变化后的栈顶指针，就应写成两级指针： void Push(Lsnode top)，这样会使函数变得复杂难懂。解决问题的办法就是模仿单链表，设置一个头结点不存放数据，即使是一个空栈，该头结点也仍然存在。问题： 能否将链栈中的指针方向反过来，从栈底到栈顶？不行，如果反过来的话，删除栈顶元素时，为修改其前驱指针，需要从栈底一直找到栈顶。1. 单链表栈的主要算法1） 初始化空栈void InitStack(Lsnode top){ top->next=NULL; }调用此函数之前，在主调函数中（例如main()）说明一个指针变量后，先为它申请分配一个结点，然后调用初始化函数。例如:void main(){ Lsnode top1;top1=(Lsnode )malloc(sizeof(Lsnode));/这很重要/InitStack(top1);…;}2） 进栈操作 void Push(Lsnode top; ElemType x){p=(Lsnode )malloc(sizeof(Lsnode)); p->data=x; p->next=top->next;top->next=p;}/Push/ 3） 出栈操作 ElemType Pop(Lsnode top) { if(top->next!=NULL){ p=top->next; top->next=p->next;x=p->data; free(p); return x;}else {printf(“Stack null! \n”);return ‘#’;}}/Pop/由上述算法可看出，栈在链表存储结构条件下进栈一个元素时一般不考虑栈满上溢出问题，而出栈时必须考虑栈空问题。2. 多个链表栈的运算有时需要同时使用两个以上的栈，若用一个向量来处理是极不方便的，最好采用多个单链表做存储结构。将多个链表的指针放入一个一维数组之中：Lsnode top［n］;让top［0］,top［1］,…，top［n-1］指向n个不同的单链表。请注意，这里的每个链表都有附加头结点。操作时需先确定栈号i，然后以top［i］为栈顶指针进行栈操作极为方便。算法如下：1） 第i号栈进栈操作void Pushn(Lsnode top［n］; int i; ElemType x) {/已知元素x,进入第i个栈/p=(struct Lsnode)malloc(sizeof(struct Lsnode));/申请结点/p->data=x;p->next=top［i］->next;top［i］->next=p;}/Pushn/2） 第i号栈出栈一个元素ElemType Popn(Lsnode top［n］; int i) { if(top［i］->next!=NULL){ p=top［i］->next; top［i］->next=p->next;x=p->data; free(p);return x;}else {printf(“\nStack NULL!\n”); return#’; }}/Popn/在上述算法中，当指定了栈号i(0≤i≤n-1)之后，就仅对第i个栈链表进行操作。例如，设i=3,将x进栈，x元素就进入了第3号栈链表，同时，把top［3］重新指向新的栈顶元素，而其他栈链表不会产生变动。3.4栈的应用栈的应用十分广泛，栈在计算机系统软件中的作用十分重要。下面就表达式计算、子程序嵌套调用、递归调用和汉诺塔几个问题，讨论栈的应用。3.4.1表达式的计算对表达式进行处理计算是程序设计语言编译中的一个基本问题。要把一个表达式翻译成正确求值的一个机器指令序列，或者直接对表达式求值，首先要能够正确解释表达式。例如，要对下面的算术表达式求值：（5-3）×6 10/5首先要了解算术四则运算的规则。即：（1） 先乘除，后加减；（2） 同一个优先级，先左后右；（3） 先括号内，后括号外。由此，这个算术表达式的计算顺序应为：（5-3）×6 10/5=2×6 10/5=12 10/5=12 2=14任何一个表达式都是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。我们把运算符和界限符统称为算符，它们构成的集合命名为OP。根据上述三条运算规则，在运算的每一步中，任意两个相继出现的算符θ1和θ2之间的优先关系至多是下面三种关系之一： θ1θ2，θ1的优先权高于θ2。表3.1定义了算符之间的这种优先关系。表3.1算符之间的优先关系θ2
θ1 -*/（）# >><< <> > – >><< <> > >>>> <> > / >>>> <> > ( <<<< <= ) >>>> > > # <<<< < =由运算规则（3）结合表3.1，可得 、-、和/为θ1时的优先性均低于'(‘，但高于’)’。由规则（2）可知，当 θ1=θ2时，令θ1>θ2 ，在表3.1中作为θ1的’ ‘大于作为θ2的’ ‘。另外’#’是表达式的结束符。为了算法简洁，在表达式的最左边也虚设一个’#’构成整个表达式的一对括号。表3.1中有'(‘=’)’，这表示当左右括号相遇时，括号内的运算已经完成。同理表中’#’=’#’表示整个表达式求值完毕。在表3.1中，’)’与'(‘、’#’与’)’以及'(‘与’#’之间无优先关系，这是因为表达式中不允许它们相继出现，一旦遇到这种情况，则可以认为出了语法错误。在下面的讨论中，假定所输入的表达式不会出现语法错误。为了求解表达式，可以使用两个工作栈： 一个称作OPTR，用来存放运算符；另一个称作OPND，用来存放操作数或运算结果。算法的基本思想是：首先置操作数栈OPND为空，表达式起始符’#’为运算符栈OPTR的栈底元素；然后依次读入表达式中每一个字符，若是操作数则进OPND栈；若是运算符，则和OPTR的栈顶运算符比较优先权，然后做相应的操作，直至整个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为’#’）。下列算法采用类似C 的方式描述了这个求值过程。OperandType EvaluateExpression() {//求解算术表达式。设OPTR和OPND分别为运算符栈和运算数栈,OP为运算符集合SqStack OPTR,OPND;/初始化两个空栈/OPTR.Push(‘#’);/’#’进算符栈/c=getchar(); /读入一个字符/while(c!=’#’ || OPTR.GetTop()!=’#’)/GetTop()取栈顶元素,不出栈/{ if(!In(c,OP)) { OPND.Push(c); c=getchar();} /c是操作数,进栈。接收下一字符/else /c是算符的情况/switch(Precede(OPTR.GetTop(),c)/比较优先权/{ case ”: theta=OPTR.Pop(); /出栈一个算符theta/b=OPND.Pop(); a=OPND.Pop();/出栈两个操作数a,b/OPND.Push(Operate(a,theta,b));/计算中间结果,入栈/break;}/switch/}Return OPND.GetTop(); /最终结果在OPND栈顶,为函数返回结果/算法中还调用了两个函数。其中Precede是判定运算符栈的栈顶运算符θ1与读入的运算符θ2之间优先关系的函数；Operate为进行二元运算aθb的函数。例3.2利用算法EvaluteExpression对算术表达式3×(7-2)求值。在表达式两端先增加’#’改写为：#3(7-2)#具体操作过程如表3.2所示。表3.2表达式求值过程步骤OPTR栈OPND栈输入字符判别式主 要 操 作1#3(7-2)#是数据OPND.Push(‘3’)2#3(7-2)#’#”）’OPTR.Pop() 得 ‘-‘OPND.Pop() 得 ‘7’ OPND.Pop() 得 ‘2’Operate(‘7′,’-‘,’2’)OPND.Push(‘5’)8#（3 5)#'(‘=’)’OPTR.Pop() 消去一对括号9#3 5#’’>’#’OPTR.Pop() 得 ‘’OPND.Pop() 得 ‘5’ OPND.Pop() 得 ‘3’Operate(‘5′,’’,’3′)OPND.Push(’15’)10#15’#’=’#’OPTR.Pop()消去一对#号11空15 return 15所要计算的表达式在表3.2的中间部位，带下画线阴影的字符是当前读入的字符。当前读入的是操作数就进入OPND栈。当前读入的是运算符就与OPTR栈顶算符进行比较，结合上述算法对照表3.2读者可以自行分析，分三种情况处理。最后，当读入字符为’#’且OPTR栈顶元素也为’#’，不仅脱一对’#’，且将在OPND栈里的最终结果返回，至此算法结束。3.4.2子程序的嵌套调用在各种程序设计语言中都有子程序（或称函数、过程）调用功能。一个子程序还可以调用另一子程序。图3.5(a)展示的是由主程序开始的三层嵌套调用关系。图3.5子程序嵌套调用主函数main调函数func1时需记下返回地址R，func1调用func2需记下返回地址S，func2调用func3时需记下返回地址T。func3执行结束时返回到func2的地址T，依次返回到func1的地址S，最终返回到main的地址R。在编译软件内就设立一个栈专用于存放返回地址，在嵌套调用时返回地址一一入栈，调用结束时返回地址一一出栈，如图3.5(b)所示。这是一个典型的先进后出结构。3.4.3递归调用一个子程序可以直接或间接地调用自身。在一层层递归调用时，其返回地址和处在每一调用层的变量数据都需一一记下并进栈。返回时，它们一一出栈并且被采用。现以求阶乘的递归方法为例分析栈在递归中的应用。这样可以加深对递归调用的理解，提高运用递归方法进行程序设计的能力。求n!的递归方法思路是：n!=1n=0n×(n-1)n≥1与之相应的Ｃ函数框架是：int fac(int n){float p;if(n==0 || n==1)p=1;else p=nfac(n-1);return p;}在此函数中可理解为用fac(n)来求n!，那么用fac(n-1)就可以表示求(n-1)!。图3.6(a)展示了递归调用中执行情况。从图3.6(a)可以看到fac函数共被调用5次，它们依次是fac(5)、fac(4)、fac(3)、fac(2)、fac(1)。其中fac(5)是由main函数调用的，其余4次是在各层的fac函数中调用的。在某一层递归调用时，并未立即得到结果，而是进一步向深度递归调用。直到最内层函数执行n=1或n=0时，fac(n)才有结果。然后再一一返回，不断得到中间结果，直到返回主程序为止，可得到n!的最终结果。图3.6递归调用调用时把处在不同调用层的不同n值入栈，返回时再一一出栈参加计算。存放不同n值的栈如图3.6(b)所示。当然这里也用到了返回地址栈，在此不再重复。栈是一个基本的重要的数据结构。它有一重要参数就是栈顶指针top。top为零（对于顺序结构）或为NULL（对于链表）均表明是空栈。在进栈、出栈时，应注意栈满或栈空的判断处理。3.5队列〖*4/5〗3.5.1队列的定义及运算队列(queue)也是一种特殊的线性表。在现实生活中队列的例子很多，例如客户到银行办理业务往往需要排队，先来的先办理，晚来的则排在队尾等待，如图3.7(a)所示。抽象成逻辑图，如图3.7(b)所示。另外，队列在程序设计中也经常出现，一个典型的例子就是操作系统中的作业排队。在允许多道程序运行的计算机系统中，同时有几个作业运行。如果运行的结果都需要通过通道输出，那就按请示输出的先后次序排队。每当通道传输完毕可以接受新的输出任务时，队头的作业先从队列中出来进行输出操作。凡是申请输出的作业都从队尾进入队列。图3.7队列队列与栈不同,其所有的插入均限定在表的一端进行,而所有的删除则限定在表的另一端进行。允许插入的一端称队尾(rear),允许删除的一端称队头(front)。队列的结构特点是，先进入队的数据元素先出队。假设有队列Q=(a1,a2,…,an),则队列Q中的元素是按a1,a2,…,an的次序进队。第一个出队的应该是a1,第二个出队的应该是a2,只有在an-1出队后,an才可以出队,详见图3.7（b）。通常又把队列叫作先进先出(First In First Out，FIFO）表。在日常生活中,队列的例子到处皆是,如等待购物的顾客总是按先来后到的次序排成队列,先得到服务的顾客是站在队头的先来者,而后到的人总是排在队的末尾。在软件系统中，队列也是重要的数据结构。例如在实现树（参见第6章）或图（参见第7章）的广度遍历时，必须以队列为辅助存储结构。3.5.2队列的抽象数据类型（1） 与栈结构相似, 队列的抽象数据类型的描述如下：ADT Queue{ 数据对象: D={ai| ai∈ElemSet,i=1,2,…,nn≥0;} 数据关系: R={|,ai, ai＋1∈D, i=1,2,…,n; a1 无前驱,an无后继;} 约定 a1 端为队头, an端为队尾。 基本操作: (1) 初始化一个空队列; (2) 判队空,空队返回True,否则返回False; (3) 入队,在队尾插入一个元素; (4) 出队,在队头删除一个元素; (5) 取队头数据元素值; (6) 置队列为空状态; (7) 销毁队列;等等}ADT Linear_list;（2） 队列的实例。在日常生活中经常会遇到为了维护社会正常秩序而需要排队的情境，在计算机程序设计中也经常出现类似问题。数据结构“队列”与生活中的“排队”极为相似，也是按“先到先办”的原则行事的，并且严格限定： 既不允许“插队”，也不允许“中途离队”。3.6队列的顺序存储结构及实现队列的顺序存储结构,在计算机中常借助于一维数组来存储队列中的元素。为了指示队首和队尾的位置,尚需设置队头front和队尾rear两个指针,并约定头指针front总是指向队列中实际队头元素的前面一个位置,而尾指针rear总是指向队尾元素，如图3.8所示。图3.8队列顺序存储结构队列的顺序存储结构可描述为:typedef struct { ElemType elem［MAXSIZE］; /一维数组/int front,rear; /头、尾指针/} SeQueue;SeQueue Q;有一个能容纳6个元素的队列，图3.9是在进出队列时头、尾指针的变化示意图。图3.9(a)表示该队列的初始状态为空, rear=front=-1;图3.9(b)表示有3个元素a1、a2、a3相继入队列,所以尾指针rear从-1变化到2,而头指针front不变;图3.9(c)表示a1、a2、a3先后出队,头指针front的值从-1变化到2，队列成为空状态,此时rear=front=2;图3.9(d)表示3个元素a4、a5、a6依次进入队列,尾指针rear从2变化到5，头指针front不变仍然停留在位置2。这里有一现象，在队列为空时均有： rear=front。图3.9队列中元素和头尾指针的关系假若还有元素a7请求进入队列,由于队尾指针已经指向了队列的最后一个位置,因而插入a7就会发生“溢出”。但是,这时的队列并非真正满了,事实上队列中尚有3个空位。也就是说,系统作为队列用的存储区还没有满,但队列却发生了溢出,把这图3.10用平移元素的方法克服假溢出种现象称为“假溢出”。解决“假溢出”的方法有两种:(1) 采用平移元素的方法。即一旦发生“假溢出”就把整个队列的元素平移到存储区的首部。如图3.10所示,将a4、a5、a6平移到elem［0］～elem［2］,而将a7插到第3个位置上。显然平移元素的方法效率是很低的。(2) 将整个队列作为循环队列来处理。可以设想elem［0］接在elem［5］之后,如图3.11(a)所示。当发生假溢出时,可以把a7插入到第0个位置上。这样,虽然物理上队尾在队首之前,但逻辑上队首仍然在队尾前,作插入和删除运算时仍按“先进先出”的原则。图3.11(b)展示了元素a8和a9进入队列后的情形。此时队列已满,如果还要插入元素就会发生上溢。而它与图3.11(c)所示队列为空的情形一样,均有front==rear。这是一矛盾现象。在这种情况下,在循环队列中只凭等式rear==front无法判别队空还是队满。因此,可再设置一个布尔变量来区分队空和队满。或者不设布尔变量,而把尾指针rear加1后等于头指针front作为队满的标志，这意味着需要损失一个空间。或者反过来说,拥有MAXSIZE个数组元素的数组仅能表示一个长度为MAXSIZE-1的循环队列。以上两种方法都要多占存储空间,但后者循环队列比较方便。下面的讨论均是以循环队列为基础。此时判断队列为空的条件仍然是：front==rear问题： 由于顺序存储结构是一次性地分配空间，因此在入队列的操作中首先应该判别当前队列是否已经“满”了，那么队列满的判别条件又是什么呢？判断队列为满的条件则是：(rear 1)%MAXSIZE==front请注意，图3.11(c)就是循环队列为空状态的图示。图3.11(d)就是循环队列为满状态的图示。由于是循环队列，只要front==rear而不论它们具体等于什么下标值，均为空队。只要(rear 1)%MAXSIZE==front而不论它们具体等于什么下标值，均为满队。图3.11用循环队列的方法解决假溢出问题在队列循环中,每插入一个新元素,就把尾指针沿顺时针方向移动，即rear 1。由于本身是循环队列，当rear达到最大下标（MAXSIZE-1）时，再加1它就会越界，rear应该变为零值。所以需要将rear加1再对MAXSIZE取余，可得正确结果。进队操作的语句如下:rear=(rear 1)% MAXSIZE;elem［rear］=x;结合图3.11（a），MAXSIZE=6,假设原来rear=5已达到最大下标值。为使a7 进队，让rea 1=6再对6取余得零。rear=0,正好在elem［0］处插入元素a7。每删除一个新元素,就把头指针front沿顺时针方向移动一个位置,即front 1。同理，需要将front加1再对MAXSIZE取余。出队操作的语句如下:front=(front 1)% MAXSIZE;请特别注意，在循环队列出队或进队时，头、尾指针都要做加1后取余运算。下面给出循环队列主要操作的算法。(1) 将循环队列置为空的算法。void SetNULL(SeQueue Q){Q->front=-1; Q->rear=-1;}(2) 判断循环队列是否为空。int Empty(SeQueue Q){ if(Q.rear==Q.front)return(1);elsereturn(0);}(3) 进队。在循环队列中插入新的元素x。进队操作实质上是在队列尾指针处插入一个新的队尾元素x。进队操作首先要判断当前循环队列是否已满，如果队列已满，则输出提示信息；否则让尾指针加1对MAXSIZE取模后，x进队，存放在尾指针所指的位置。算法如下:void AddQ(SeQueueQ,ElemType x){if((Q->rear 1)% MAXSIZE==Q->front)printf(“Queue is FULL! \n”)else{Q->rear=(Q->rear 1)% MAXSIZE;Q->elem［Q->rear］=x;}}(4) 出队。出队操作实质上是删除队列中队首元素的操作。ElemType DelQ(SeQueueQ){ if(Q->front==Q->rear){ printf(“Queue is EMPTY! \n”);return -1;else { Q->front=(Q->front 1)% MAXSIZE;return(Q->elem［Q->front］);}}(5) 取队列中的队首元素。ElemType Front(SeQueueQ){ElemType x;if(Q->front==Q->rear){printf(“Queue is EMPTY! \n”);return(-1);}elsex=Q->elem［(Q->front 1)%MAXSIZE］;return (x);}问题： 判别循环队列为“空”的条件应该是什么？在队列初始化的函数中，设置队头和队尾指针均为0，那么能否由“队头指针为0”来作为队列空的判别条件呢？显然是不对的，由上页两个插图的例子就可见，由于队头指针和队尾指针都是“单方向”移动的，因此当队头指针“追上”队尾指针时，说明所有曾经插入队列的元素都已经出列，所以队列变空的条件应该是“两个指针指向循环队列中的同一位置”。3.7队列的链表存储结构及实现队列不仅可以采用顺序存储结构，也可以采用链表存储结构。用链表表示的队列简称为链队列，如图3.12所示。图3.12链队列示意图一个链队列显然需要两个指针才能唯一确定，它们分别指示队头和队尾，分别称为头指针front和尾指针rear。与线性表的单链表一样,为了操作方便起见,也给链队列添加了一个附加头结点,并令头指针指向front头结点,正好指向队列第一个数据结点的前一位置。由此,空的链队列的判别条件为头指针和尾指针均指向附加头结点,满足条件：front==rear详见图3.13(a)。链队列的进队和出队操作，属于链表的插入和删除操作的特殊情况,只是尚需修改尾指针或头指针。图3.13队列运算指针变化状况图3.13(b)是在(a)的基础上进队元素x后的情况。虽然，看上去链表有两个结点，其实是仅有一个数据元素的队列。图3.13(c)是在(b)的基础上再进队元素y后的情况。图3.13(d)是在(c)的基础上出队一个元素后的情况。出队在队头进行，队列中只剩下数据y的结点。除去空队情况外，头指针front总是指向队头元素前一位置，队尾指针rear总是指向队尾元素自身。链队列结点的结构可描述为:typedefstruct NodeType/数据元素结点的结构/{ElemType data;struct NodeType next;} NodeType;typedefstruct/队列头尾指针结构体/{NodeType front,rear;} LinkQueue;其中front和rear分别为队列的头指针和尾指针。下面给出实现链队列5种运算的具体算法。（1） 队列初始化/生成链队列的头结点,并令头指针和尾指针指向该结点,表示此队列为空/void SetNULL(LinkQueue Q){NodeType p;p=(NodeType )malloc(sizeof(NodeType));/分配一头结点/p->next=NULL;Q->front=p;Q->rear=p;}在主函数中应该这样处理：voidmain(){LinkQueue q1;SetNULL(&q1);/调用初始化函数,实参是地址/…;}结果如图3.13(a)所示。（2） 判队列是否为空。由于队列经过初始化之后，即使是空队也至少有一个头结点。在判断队列是否为空的函数中不会改变头尾指针，所以形参不必使用（LinkQueue Q）。int Empty(LinkQueue Q){if(Q.front==Q.rear) return(1); elsereturn(0);}（3） 进队，在队尾结点之后插入一个元素。void AddQ(LinkQueue Q,ElemType x){NodeType p;p=(NodeType )malloc(sizeof(NodeType));p->data=x;p->next=NULL;Q->rear->next=p;Q->rear=p;}（4） 出队，删除队头元素。在链表队列中删除队头元素，首先要判断队列是否已空，图3.13(a)就是一个空队状态。因此，判断链队列是否已空就是判断头、尾指针是否相等。如果二者相等，则表明队列已空，输出提示信息；否则删除队列首部第一个有效元素，注意，这里不是指附加队头结点，在这个结点中没有队列的有效元素。在删除队头元素时，若队列中仅有一个有效元素，就会把尾指针一同删去。因此要注意防止尾指针丢失，具体算法如下：ElemType DelQ(LinkQueue Q) {NodeType p; ElemType x;if(Q->front==Q->rear) {printf(“QUEUE IS EMPTY\n”);x=-1;}else{p=Q->front->next;Q->front->next=p->next;if(p->next==NULL) Q->rear=Q->front;x=p->data; free(p)}return x;}问题： 你是否注意到算法中那个带有下画线的语句？它是否多余？能否删去？你一定看出问题来了吧!由于一般情况下，出队列的操作只涉及队头元素，因此不需要修改队尾指针，但当链队列中只有一个数据元素时，队头元素恰好也是队尾元素，当它被删除之后，队尾指针就“悬空”了，待下次再做入队操作时，就要产生指针的“悬空访问”的错误，因此在这种情况下必须同时修改尾指针。(5) 取队列首元素。由于在函数中不会改变头尾指针，所以形参不必使用（LinkQueue Q）。ElemType Front(LinkQueue Q){NodeType p;if(Q.front==Q.rear) {printf(“QUEUE IS EMPTY\n”); return -1;}else{p=Q.front->next;return p->data;
书摘插画
评论
还没有评论。