新書推薦：
《
山西寺观艺术壁画精编卷
》
售價：NT$
7650.0
《
中国摄影 中式摄影的独特魅力
》
售價：NT$
4998.0
《
山西寺观艺术彩塑精编卷
》
售價：NT$
7650.0
《
积极心理学
》
售價：NT$
254.0
《
自由，不是放纵
》
售價：NT$
250.0
《
甲骨文丛书·消逝的光明：欧洲国际史，1919—1933年（套装全2册）
》
售價：NT$
1265.0
《
剑桥日本戏剧史（剑桥世界戏剧史译丛）
》
售價：NT$
918.0
《
中国高等艺术院校精品教材大系：材料的时尚表达??服装创意设计
》
售價：NT$
347.0
|
| 編輯推薦： |
|
（1）根据教育部颁发的《高等学校计算机科学与技术专业公共核心知识体系与课程》规范编写。（2）内容涵盖数据结构与算法的基本概念和算法分析的简单方法，以及C语言编程的要点。（3）作者在讨论每一个知识单元时，结合30多年教学的经验和考试辅导的体会，合理安排了教材内容，力求透彻、全面。对学生读书容易忽略的地方和隐藏在书中所讨论问题后面的东西，都有适当的提示。（4）是学习数据结构与算法课程的教材，也可以作为计算机专业考研的辅导教材或其他计算机或软件考试的复习教材。
|
| 內容簡介： |
本书是根据教育部《高等学校计算机科学与技术专业公共核心知识体系与课程》编写的数据结构主教材。全书共8章。第1章介绍数据结构的地位和主要知识点，数据结构和算法的基本概念和算法分析的简单方法，以及C语言编程的要点。第2～8章分别介绍了线性表、栈和队列及其应用、多维数组、特殊矩阵、稀疏矩阵、字符串和广义表、树与二叉树、图、查找、排序，并做了适当延伸。作者在讨论每一个知识单元时，结合30多年教学的经验和考试辅导的体会，合理安排教材内容，力求透彻、全面，对学生读书容易忽略的地方和隐藏在书中所讨论问题后面的东西都有适当的提示。
本书的编写得到清华大学2015年精品教材建设项目的资助。本书既可作为高等学校计算机科学与技术专业和软件工程专业本科生学习数据结构与算法课程的教材，也可以作为计算机专业考研的辅导教材或其他计算机或软件考试的复习教材，还可作为计算机或软件系统开发人员的参考资料。
|
| 目錄：
|
目录
第1章 绪论 1
1.1 数据结构的概念及分类 1
1.1.1
为什么要学习数据结构 1
1.1.2
与数据结构相关的基本术语 2
1.1.3
数据结构的分类 5
1.1.4
数据结构的存储结构 6
1.1.5
定义在数据结构上的操作 7
1.1.6 好数据结构 7
1.2 使用C语言描述数据结构 7
1.2.1
C语言的数据类型 8
1.2.2
算法的控制结构 9
1.2.3
算法的函数结构 10
1.2.4
动态存储分配 12
1.2.5
逻辑和关系运算的约定 12
1.2.6
输入与输出 13
1.3 算法和算法设计 13
1.3.1
算法的定义和特性 13
1.3.2
算法的设计步骤 14
1.3.3
算法设计的基本方法 15
1.4 算法分析与度量 18
1.4.1
算法的评价标准 18
1.4.2
算法的时间和空间复杂度度量 18
1.4.3
算法的渐近分析 21
小结 24
习题 24
第2章 线性表 27
2.1 线性表 27
2.1.1
线性表的定义和特点 27
2.1.2
线性表的主要操作 28
2.2 顺序表 29
2.2.1
顺序表的定义和特点 29
2.2.2
顺序表的结构定义 30
2.2.3
顺序表查找操作的实现 31
2.2.4
顺序表插入和删除操作的实现 32
2.2.5
顺序表的应用：集合运算 34
2.3 单链表 35
2.3.1
单链表的定义和特点 35
2.3.2
单链表的结构定义 36
2.3.3
单链表中的插入与删除 36
2.3.4
带头结点的单链表 40
2.3.5
单链表的遍历与创建 42
2.3.6
单链表的应用：集合运算 44
2.3.7
循环链表 46
2.3.8
双向链表 50
2.3.9
静态链表 53
2.4 顺序表与线性链表的比较 54
2.5 线性表的应用：一元多项式及其运算 56
2.5.1
一元多项式的表示 56
2.5.2
多项式的结构定义 57
2.5.3
多项式的加法 59
2.5.4
扩展阅读：多项式的乘法 60
小结 62
习题 63
第3章 栈和队列 66
3.1 栈 66
3.1.1
栈的概念 66
3.1.2
顺序栈 67
3.1.3
扩展阅读：多栈处理 70
3.1.4
链式栈 73
3.1.5
扩展阅读：栈的混洗 74
3.2 队列 76
3.2.1
队列的概念 76
3.2.2
循环队列 76
3.2.3
链式队列 80
3.3 栈的应用 82
3.3.1
数制转换 82
3.3.2
括号匹配 83
3.3.3
表达式的计算与优先级处理 84
3.3.4
栈与递归的实现 88
3.4 队列的应用 91
3.5 在算法设计中使用递归 92
3.5.1
汉诺塔问题与分治法 92
3.5.2
直接把递归过程改为非递归过程 94
3.5.3
扩展阅读：递归过程的非递归模拟算法 95
3.5.4
迷宫问题与回溯法 98
3.5.5
计算组合数与动态规划 101
3.6 扩展阅读：双端队列 102
3.6.1
双端队列的概念 102
3.6.2
输入受限的双端队列 103
3.6.3
输出受限的双端队列 104
3.6.4
双端队列的存储表示 104
3.7 扩展阅读：优先队列 106
3.7.1
优先队列的概念 106
3.7.2
优先队列的实现 107
小结 108
习题 108
第4章 数组、串和广义表 112
4.1 数组 112
4.1.1
一维数组 112
4.1.2
多维数组 114
4.2 特殊矩阵的压缩存储 116
4.2.1
对称矩阵的压缩存储 117
4.2.2
三对角矩阵的压缩存储 118
4.2.3
扩展阅读：w对角矩阵的压缩存储 119
4.3 稀疏矩阵 120
4.3.1
稀疏矩阵的概念 120
4.3.2
稀疏矩阵的顺序存储表示 121
4.3.3
稀疏矩阵的链表表示 124
4.4 字符串 125
4.4.1
字符串的概念 126
4.4.2
字符串的初始化和赋值 126
4.4.3
自定义字符串的存储表示 128
4.4.4
串的模式匹配 132
4.5 广义表 140
4.5.1
广义表的概念 140
4.5.2
广义表的性质 141
4.5.3
广义表的链接表示 141
4.5.4
扩展阅读：三元多项式的表示 147
小结 148
习题 149
第5章 树与二叉树 152
5.1 树的基本概念 152
5.1.1
树的定义和术语 152
5.1.2
树的基本操作 154
5.2 二叉树及其存储表示 155
5.2.1
二叉树的概念 155
5.2.2
二叉树的性质 156
5.2.3
二叉树的主要操作 158
5.2.4
二叉树的顺序存储表示 159
5.2.5
二叉树的链表存储表示 160
5.3 二叉树的遍历 161
5.3.1
二叉树遍历的递归算法 162
5.3.2
递归遍历算法的应用举例 163
5.3.3
二叉树遍历的非递归算法 166
5.3.4
利用队列实现二叉树的层次序遍历 169
5.3.5
非递归遍历算法的应用举例 170
5.3.6
二叉树的计数 171
5.4 线索二叉树 174
5.4.1
线索二叉树的概念 174
5.4.2
线索二叉树的种类 175
5.4.3
中序线索二叉树的建立和遍历 176
5.4.4
先序与后序线索二叉树 178
5.5 树与森林 180
5.5.1
树的存储表示 180
5.5.2
森林与二叉树的转换 184
5.5.3
树与森林的深度优先遍历 185
5.5.4
树与森林的广度优先遍历 187
5.5.5
树遍历算法的应用举例 188
5.6
Huffman树 190
5.6.1
带权路径长度的概念 190
5.6.2
Huffman树的概念 191
5.6.3
扩展阅读：最优判定树 194
5.6.4
Huffman编码 196
5.7 堆 198
5.7.1
小根堆和大根堆 198
5.7.2
堆的建立 199
5.7.3
堆的插入 201
5.7.4
堆的删除 202
5.8 等价类与并查集 202
5.8.1
等价关系与等价类 202
5.8.2
确定等价类的方法 203
5.8.3
并查集的定义及其实现 203
5.8.4
并查集操作的分析和改进 205
5.9 扩展阅读：八皇后问题与树的剪枝 207
5.9.1
八皇后问题的提出 207
5.9.2
八皇后问题的状态树 208
5.9.3
八皇后问题算法 210
小结 211
习题 212
第6章 图 216
6.1 图的基本概念 216
6.1.1
与图有关的若干概念 216
6.1.2
图的基本操作 219
6.2 图的存储结构 221
6.2.1
图的邻接矩阵表示 221
6.2.2
图的邻接表表示 225
6.2.3
邻接矩阵表示与邻接表表示的比较 229
6.2.4
图的邻接多重表和十字链表表示 230
6.3 图的遍历 231
6.3.1
深度优先搜索 232
6.3.2
广度优先搜索 234
6.3.3
连通分量 235
6.3.4
双连通图 237
6.3.5
有向图的强连通分量 238
6.4 最小生成树 240
6.4.1
最小生成树求解和贪心法 240
6.4.2
Kruskal算法 242
6.4.3
Prim算法 244
6.4.4
扩展阅读：其他建立最小生成树的方法 246
6.5 最短路径 248
6.5.1
非负权值的单源最短路径 248
6.5.2
扩展阅读：边上权值为任意值的单源最短路径问题 252
6.5.3
所有顶点之间的最短路径 254
6.5.4
无权值的最短路径 257
6.6 活动网络 259
6.6.1
AOV网络与拓扑排序 259
6.6.2
AOE网络与关键路径法 262
小结 267
习题 268
第7章 查找 273
7.1 查找的概念及简单查找方法 273
7.1.1
查找的基本概念 273
7.1.2
顺序查找法 274
7.1.3
折半查找法 276
7.1.4
扩展阅读：次优查找树 279
7.1.5
扩展阅读：斐波那契查找和插值查找 282
7.1.6
扩展阅读：跳表 283
7.2 二叉查找树 284
7.2.1
二叉查找树的概念 285
7.2.2
二叉查找树的查找 285
7.2.3
二叉查找树的插入 286
7.2.4
二叉查找树的删除 288
7.2.5
二叉查找树的性能分析 289
7.3
AVL树 292
7.3.1
AVL树的概念 292
7.3.2
平衡化旋转 293
7.3.3
AVL树的插入 295
7.3.4
AVL树的删除 296
7.3.5
AVL树的性能分析 299
7.4
B树 300
7.4.1
索引顺序表与分块查找 300
7.4.2
多级索引结构与m叉查找树 301
7.4.3
B树的概念 302
7.4.4
B树上的查找 304
7.4.5
B树上的插入 305
7.4.6
B树上的删除 306
7.4.7
B树 308
7.5 扩展阅读：其他查找树 311
7.5.1
红黑树 311
7.5.2
伸展树 313
7.5.3
字典树 315
7.6 散列表及其查找 317
7.6.1
散列的概念 318
7.6.2
常见的散列函数 318
7.6.3
解决冲突的开地址法 321
7.6.4
解决冲突的链地址法 327
7.6.5
散列法分析 329
小结 330
习题 330
第8章 排序 335
8.1 排序的概念 335
8.1.1
排序的相关概念 335
8.1.2
排序算法的性能分析 336
8.1.3
数据表的结构定义 337
8.2 插入排序 338
8.2.1
直接插入排序 338
8.2.2
基于静态链表的直接插入排序 339
8.2.3
折半插入排序 341
8.2.4
希尔排序 342
8.3 交换排序 343
8.3.1
起泡排序 344
8.3.2
快速排序 345
8.3.3
快速排序的改进算法 348
8.4 选择排序 350
8.4.1
简单选择排序 350
8.4.2
锦标赛排序 351
8.4.3
堆排序 352
8.5 归并排序 356
8.5.1
二路归并排序的设计思路 356
8.5.2
二路归并排序的递归算法 356
8.5.3
扩展阅读：基于链表的归并排序算法 358
8.5.4
扩展阅读：迭代的归并排序算法 359
8.6 基数排序 361
8.6.1
基数排序 362
8.6.2
MSD基数排序 362
8.6.3
LSD基数排序 364
8.7 内排序算法的分析和比较 367
8.7.1
排序方法的下界 367
8.7.2
各种内排序方法的比较 368
8.8 外排序 371
8.8.1
常用的外存储器与缓冲区 371
8.8.2
基于磁盘的外排序过程 372
8.8.3
m路平衡归并的过程 374
8.8.4
初始归并段的生成 378
8.8.5
最佳归并树 381
8.8.6
磁带归并排序 382
小结 385
习题 386
附录A 实训作业要求与样例 391
A.1 实训作业要求 391
A.2 实训作业样例 392
附录B 词汇索引 397
参考文献 405
|
| 內容試閱：
|
第2版前言本书第2版的初稿完成于2015年12月，作为另一本教材《数据结构精讲与习题详解》（第2版）的写作参照，相互融合，相互补充，首先完成了该书，再回过头来第二次修改本书，所以本书实际上是第2版的修订本。自从1978年美籍华人冀中田第一次在中国讲授数据结构课开始，很多老师对课程的内容和讲授方法做了大量的研究，也可以说是在做中学，总结出许多好的经验，使得课程的教学比当时进步了很多。我本人在这门课程的教学中也积累了一些心得，非常希望与正在学习这门课程的同学们分享，这是我修改这本教材的初衷。既然数据结构与算法相辅相成，密不可分，而算法就是解决问题的过程描述，那么，描述数据结构与算法的语言就应该是过程性的。早期用伪代码描述，实践证明不可持续，因为很多用伪代码描述的算法转换为使用某种编程语言编写的程序后，怎么也通不过。原因是很多人编程语言的实践能力太差，算法的实现细节太粗糙。所以我认为，使用某种过程性语言，如C、C等，对于学习和实现数据结构与算法是合适的。由于数据结构课程学时的限制（多数学校为48～64学时），作为本科生的教材，包含的知识容量应有一定限度。知识点太少，学生在未来的学习和工作中可联想的思考空间狭窄，使解决问题的能力受限；知识点太多，必然沦为百科全书式的阅读，基础不牢靠，同样使得解决问题的能力受限。通过教学实践证明，本书的第1版在内容上取材是恰当的，范围上取材的深度和广度也是恰当的，但联想不够，某些算法的实现上偏向使用伪代码描述，造成部分读者在学习上和实践上的困惑。本书第2版修改部分包括：（1）在结构上从第1版的10章改为8章，虽然章数压缩了，但叙述内容不减反增。增加的知识点大多作为扩展阅读出现，它们不作为考核内容，主要是拓展视野。（2）各章的想想看改为思考题，目的是增加一些互动环节。这些思考题触及的都是可联想的内容，或者是对理解正文有用的知识点拨。所谓学问就是有学还要有问。正面的问有助于理解应该做什么，反面的问有助于理解不该做什么。（3）书中所有使用C语言书写的算法，包括辅助教材《数据结构精讲与习题详解》（第2版）中的800道算法题，都重新使用VC 6.0编译程序调试过，有的还按照软件工程的要求做了边界值测试。因为书中算法的正确运行需要构建运行环境，所以对于书中所涉及的主要数据结构的存储表示，绝大多数都在第2版给出了结构定义、初始化或创建算法、输出算法等，这样可由读者自行搭建运行环境。（4）第3章增加了多栈共享同一存储时的栈浮动技术、递归程序的非递归模拟方法、优先队列的内容；第4章增加了w对角矩阵的压缩存储、稀疏矩阵的链表存储、串的BM模式匹配算法的内容；第5章增加了等价类与并查集的内容；第6章增加了构造最小生成树的破圈法、Dijkstra算法的内容；第7章增加了跳表、红黑树、伸展树、字典树的内容。此外对保留的内容有部分增删。教材现有内容基本覆盖大多数学校的教学大纲和考研大纲。（5）附录增加了词汇索引，书中出现的重要概念都收录在索引中，大大方便了读者查阅相关的词汇。各章所附习题不包括选择题，但精选了许多综合应用题，这些习题的参考解答请参看作者的另一本配套教材《数据结构精讲与习题详解》。因为作者的水平有限，可能在某些方面有考虑不周的地方，书中难免存在疏漏或错误，诚恳希望读者提出宝贵意见。作者的E-mail地址是yinrk@tsinghua.edu.cn或yinrk@sohu.com。
作 者 2016年8月于清华大学
第3章
栈 和 队 列栈和队列在计算机系统中应用极多。Windows操作系统中就用到了9000多个栈。而且栈与队列都是顺序存取结构，比向量更容易使用。这就像结构化编程相对于普通编程，具有更加优良的程序设计风格。3.1 栈栈、队列和双端队列是特殊的线性表，它们的逻辑结构和线性表相同，只是其运算规则较线性表有更多的限制，故又称它们为运算受限的线性表，或限制了存取点的线性表。3.1.1 栈的概念栈是只允许在表的一端进行插入和删除的线性表。允许插入和删除的一端叫做栈顶，而不允许插入和删除的另一端叫做栈底。当栈中没有任何元素时则称为空栈。设给定栈S = a1, a2, , an，则称最后加入栈中的元素an为栈顶。栈中按a1, a2, , an的顺序进栈。而退栈的顺序反过来，an先退出，然后an-1才能退出，最后退出a1。换句话说，后进者先出。因此，栈又叫做后进先出（Last In First Out，LIFO）的线性表。参看图3-1。栈的主要操作如下：（1）void InitStack Stack& S ;先决条件：无。操作结果：为栈S分配存储空间，并对各数据成员赋初值。（2）int Push Stack& S, SElemType x ;先决条件：栈S已存在且未满。操作结果：新元素x进栈S并成为新的栈顶。（3）int Pop Stack& S, SElemType & x ;先决条件：栈S已存在且栈非空。操作结果：若栈S空，则函数返回0，x不可用；否则栈S的栈顶元素退栈，退出元素由x返回，函数返回1。（4）int GetTop Stack& S, SElemType & x ;先决条件：栈S已存在且栈非空。操作结果：若栈S空，则函数返回0，x不可用；否则由引用型参数x返回栈顶元素的值但不退栈，函数返回1。（5）int StackEmpty Stack& S ;先决条件：栈S已存在。操作结果：函数测试栈S空否。若栈空，则函数返回1，否则函数返回0。（6）int StackFull Stack& S ;先决条件：栈S已存在。操作结果：函数测试栈S满否。若栈满，则函数返回1，否则函数返回0。（7）int StackSize Stack& S ;先决条件：栈S已存在。操作结果：函数返回栈S的长度，即栈S中元素个数。【例3-1】 利用栈实现向量A中所有元素的原地逆置。算法的设计思路是：若设向量A 中数据原来的排列是{ a1, a2, , an }，执行此算法时，把向量中的元素依次进栈。再从栈S中依次退栈，存入向量A，从而使得A中元素的排列变成{ an, an-1, , a1 }。所谓原地是指逆转后的结果仍占用原来的空间。参看程序3-1。程序3-1 向量A中所有元素逆置的算法
void Reverse SElemType A[], int n { Stack S; InitStackS; int i;for i = 1; i 栈空间初始大小typedef int SElemType; 栈元素数据类型typedef struct { 顺序栈的结构定义SElemType *elem; 栈元素存储数组int maxSize, top;栈空间最大容量及栈顶指针（下标）} SeqStack;
下面讨论栈的主要操作的实现。1．初始化操作程序3-4给出动态顺序栈的初始化算法。算法的基本思路是：按initSize大小为顺序栈动态分配存储空间，首地址为S.elem，并以initSize作为最初的S.maxSize。程序3-4 动态顺序栈的初始化
void InitStack SeqStack& S {建立一个最大尺寸为initSize的空栈, 若分配不成功则进行错误处理S.elem = SElemType* malloc initSize*sizeof SElemType ; 创建栈空间if S.elem == NULL { printf "存储分配失败！\n" ; exit1; }S.maxSize = initSize; S.top = -1;}
2．进栈操作程序3-5是动态顺序栈的进栈算法。主要步骤如下：（1）先判断栈是否已满。若栈顶指针top == maxSize-1，说明栈中所有位置均已使用，栈已满。这时新元素进栈将发生栈溢出，函数报错并返回0。（2）若栈不满，先让栈顶指针进1，指到当前可加入新元素的位置，再按栈顶指针所指位置将新元素插入。这个新插入的元素将成为新的栈顶元素，最后函数返回1。【例3-2】 顺序栈进栈操作的示例如图3-3所示。栈顶指针指示最后加入元素位置。程序3-5 动态顺序栈进栈操作的实现
图3-3 顺序栈的进栈操作示意图int Push SeqStack& S, DataType x { 进栈操作：若栈不满, 则将元素x插入栈顶, 函数返回1；否则栈溢出，函数返回0 if S.top == S.maxSize-1 return 0;栈满则溢出处理 S.elem[S.top] = x; 栈顶指针先加1, 再进栈 return 1;}
思考题 可否使用void callocn, size函数动态分配存储空间？如何做？3．退栈操作程序3-6是动态顺序栈的退栈算法。算法的基本思路是：先判断是否栈空。若在退栈时发现栈是空的，则执行退栈操作失败，函数返回0；若栈不空，可先将栈顶元素取出，再让栈顶指针减1，让栈顶退回到次栈顶位置，函数返回1，表示退栈成功。【例3-3】 顺序栈退栈操作的示例如图3-4所示。位于栈顶指针上方的栈空间中即使有元素，它们也不是栈的元素了。
图3-4 顺序栈的退栈操作示意图程序3-6 顺序栈退栈操作的实现
int Pop SeqStack& S, SElemType& x {退栈：若栈不空则函数通过引用参数x返回栈顶元素值, 栈顶指针退1，函数返回1否则函数返回0，且x的值不可引用if S.top == -1 return 0; 判栈空否, 若栈空则函数返回0x = S.elem[S.top--];栈顶指针退1return 1;退栈成功，函数返回1};
思考题 有一种说法：退栈时若栈空不是错误，而是表明使用栈的某种处理的结束，执行栈空处理即可。进栈时若栈满则是错误，表明栈溢出，需做溢出处理。这种说法对吗？4．顺序栈其他操作的实现顺序栈其他操作的实现参看程序3-7。需要注意的是，GetTop操作与Pop操作的不同。
程序3-7 顺序栈其他操作的实现int GetTop SeqStack& S, SElemType& x {读取栈顶元素的值：若栈不空则函数返回栈顶元素的值且函数返回1，否则函数返回0if S.top == -1 return 0;判栈空否, 若栈空则函数返回0x = S.elem[S.top];返回栈顶元素的值return 1;};int StackEmpty SeqStack& S {函数测试栈S空否。若栈空，则函数返回1，否则函数返回0return S.top == -1; 函数返回S.top == -1的结果};int StackFull SeqStack& S {函数测试栈S满否。若栈满，则函数返回1，否则函数返回0return S.top == S.maxSize;函数返回S.top == S.maxSize的结果};int StackSize SeqStack& S {函数返回栈S的长度，即栈S中元素个数return S.top 1;};
思考题 为何栈操作只有这几个？表的其他一般操作，如Search、Insert、Remove是否也可以适用于栈？顺序栈是限定了存取位置的线性表，除溢出处理操作外都只能顺序存取，这决定了各主要操作的性能都十分良好。设n是栈最大容量，则各主要操作的性能如表3-1所示。表3-1 顺序栈各操作的性能比较操作名时间复杂度空间复杂度操作名时间复杂度空间复杂度初始化InitStackO1O1判栈空StackEmptyO1O1进栈PushO1O1判栈满StackFullO1O1退栈PopO1O1求栈长StackSizeO1O1读栈顶GetTopO1O1
从表3-1可知，顺序栈所有操作的时间和空间复杂度都很低。因此，顺序栈是一种高效的存储结构。3.1.3 扩展阅读：多栈处理1．双栈共享同一栈空间程序中往往同时存在几个栈，因为各个栈所需的空间在运行中是动态变化着的。如果给几个栈分配同样大小的空间，可能在实际运行时，有的栈膨胀得快，很快就产生了溢出，而其他的栈可能此时还有许多空闲的空间。这时就必须调整栈的空间，防止栈的溢出。【例 3-4】 当程序同时使用两个栈时，可定义一个足够大的栈空间V[m]，并将两个栈设为0号栈和1号栈。在V[m]两端的外侧分设两个栈的栈底，用b[0]（= -1）和b[1]（= m）指示。让两个栈的栈顶t[0]和t[1]都向中间伸展，直到两个栈的栈顶相遇，才认为发生了溢出，如图3-5所示。
图3-5 两个栈共享同一存储空间的情形* 进栈情形：对于0号栈，每次进栈时栈顶指针t[0]加1；对于1号栈，每次进栈时栈顶指针是t[1]减1。当两个栈的栈顶指针相遇，即t[0] 1 == t[1]时，才算栈满。* 退栈情形：对于0号栈，每次退栈时栈顶指针t[0]减1；对于1号栈，每次退栈时栈顶指针t[1]加1。只有当栈顶指针退到栈底才算栈空。两栈的大小不是固定不变的。在实际运算过程中，一个栈有可能进栈元素多而体积大些，另一个则可能小些。两个栈共用一个栈空间，互相调剂，灵活性强。两个栈共享一个栈空间时主要栈操作的实现如程序3-8所示。
程序3-8 两栈共享同一栈空间时主要操作的实现（保存于头文件 DblStack.h 中）
#define m 20栈存储数组的大小typedef int SElemTypetypedef struct { 双栈的结构定义int top[2], bot[2]; 双栈的栈顶指针和栈底指针SElemType V[m]; 栈数组} DblStack;void InitStack DblStack& S {初始化函数：建立一个大小为m的空栈S.top[0] = S.bot[0] = -1; S.top[1] = S.bot[1] = m;}int Push DblStack& S, SElemType x, int i { 进栈运算 if S.top[0] 1 == S.top[1] return 0;栈满则返回0 if i == 0 S.V[S.top[0]] = x;栈0：栈顶指针先加1再进栈 else S.V[--S.top[1]] = x;栈1：栈顶指针先减1再进栈 return 1;}int Pop DblStack& S, int i, SElemType& x {函数通过引用参数x返回退出栈i栈顶元素的元素值，前提是栈不为空if S.top[i] == S.bot[i] return 0;第i个栈栈空，不能退栈if i == 0 x = S.V[S.top[0]--];栈0：先出栈，栈顶指针减1else x = S.V[S.top[1]]; 栈1：先出栈，栈顶指针加1return 1;}
2．多栈共享同一栈空间当程序中同时使用3个或更多的栈时，如果它们共享同一个存储空间V[m]，必须使用所谓的栈浮动技术来处理栈的进栈、退栈和溢出处理。如果n个栈共同使用同一块存储空间V[m]，可定义各栈的栈底指针bot[n]和栈顶指针top[n]，其中，bot[i]表示第i个栈的栈底，top[i]表示第i个栈的栈顶，如图3-6所示。
图3-6 n个顺序栈共享同一个存储空间的示意图假设m可以整除n，各栈的编号从1开始，V[m]平均分配给n个栈。各栈的初始分配将是bot[i] = i-1mn，top[i] = bot[i]-1（1in），bot[n 1] = m。【例3-5】 若m = 16, n = 4，则各栈的初始分配是bot[i] = 0, 4, 8, 12, 16，top[i] = -1, 3, 7, 11。注意，栈底指针比栈顶指针多一个。第i个栈的栈空条件是bot[i]-1 == top[i]，栈满条件是top[i] 1 == bot[i 1]，如图3-7所示。
图3-7 4个栈共享同一个存储空间的示意图* 第i个栈进栈的情形：若top[i] 1==bot[i 1]，则栈满，发生上溢，需要做栈浮动，为第i个栈腾出进栈的空间才能继续进栈；否则置V[top[i]] = x，进栈成功。* 第i个栈退栈的情形：若top[i] == bot[i]-1，则第i个栈空，不能退栈；否则执行退栈操作，置x = D[top[i]--]，从x取得退出的元素。一种较直观的栈浮动的方法是：当第i个栈发生上溢时，先从其右边第i 1个栈起往右边扫描，寻找未满的栈，如果找到，则移动第i栈右边相关栈的存储，为第i个栈腾出空间；否则向第i个栈左边的各栈扫描，寻找未满的栈；如果左边也找不到未满的栈，则说明整个存储区均已占满，报告失败信息。这一算法详述如下：（1）向右寻找满足i＜kn且top[k] 1＜bot[k 1]的最小的k。如果存在这样的k，则执行以下操作：① 对于所有的存储单元j（j = top[k], top[k]-1, , bot[i 1]），执行V[j 1] = V[j]，为第i个栈腾出一个栈顶存储单元，再执行V[top[i]] = x。② 对于所有相关的栈j（i＜jk ，修改栈顶与栈底，置bot[j]，top[j]。（2）如果找不到步骤（1）中的k，但在top[i]的左边找到了满足1k＜i且top[k] 1＜bot[k 1]的最大的k，则执行以下操作：① 对于所有的存储单元j（ j = bot[k 1], , top[i]），执行V[ j-1] = V[ j]，为第i个栈腾出一个栈顶存储单元，再执行V[top[i]] = x。② 对于所有相关的栈j（k＜ji，修改栈顶和栈底，置bot[ j]--，top[ j]--。（3）对于所有的ki，如果均有top[k] 1 == bot[k 1]，则表示存储空间已满，n个栈都不能进栈了。多个顺序栈共享同一个栈空间，使用栈浮动技术处理溢出，会导致大量的时间开销，降低了算法的时间效率。特别是当整个存储空间即将充满时，这个问题更加严重。解决的办法就是采用链接方式作为栈的存储表示。3.1.4 链式栈链式栈是栈的链接存储表示。采用链式栈来表示一个栈，便于结点的插入与删除。在程序中同时使用多个栈的情况下，用链接表示不仅能够提高效率，还可以达到共享存储空间的目的。链式栈的示意图可参看图3-8。
图3-8 链式栈从图3-8可知，链式栈无须附加头结点，栈顶指针在链表的首元结点。因此，新结点的插入和栈顶结点的删除都在链表的首元结点，即栈顶进行。链式栈用单链表作为它的存储表示，其结构定义如程序3-9所示。它使用了一个链表的头指针来表示一个栈。对于需要同时使用多个栈的情形，只要声明一个链表指针向量，就能同时定义和使用多个链式栈，并且无须在运算时做存储空间的移动。程序3-9 链式栈的定义（保存于头文件 LinkStack.h 中）
typedef int SElemType;typedef struct node { SElemType data; struct node *link;} LinkNode, *LinkStack;
链式栈主要操作的实现如程序3-10所示。对于链表结构，有一点需要注意：只要还有可分配的存储空间，就可以申请和分配新的链表结点，使得链表延伸下去，所以理论上讲，链式栈没有栈满问题。但是它有栈空问题。程序3-10 链式栈主要操作的实现
void InitStack LinkStack& S {链式栈初始化：置栈顶指针，即链表头指针为空S = NULL;栈顶置空};int Push LinkStack& S, SElemType x {进栈：将元素x插入到链式栈的栈顶，即链头LinkNode *p = LinkNode* malloc sizeof LinkNode; 创建新结点p-data = x; p-link = S; S = p;新结点插入在链头return 1;}int Pop LinkStack& S, SElemType& x {退栈：若栈空，函数返回0，参数x的值不可用若栈不空，则函数返回1，并通过引用参数x返回被删栈顶元素的值if S == NULL return 0; 栈空，函数返回0LinkNode *p = S; x = p-data; 存栈顶元素S = p-link; free p; return 1;栈顶指针退到新栈顶位置}int GetTop LinkStack& S, SElemType& x {读取栈顶：若栈不空，函数通过引用参数x返回栈顶元素的值if S == NULL return 0;栈空，函数返回0x = S-data; return 1;栈不空则返回1};int StackEmpty LinkStack& S {判断栈是否为空：若栈空，则函数返回1，否则函数返回0return S == NULL;}int StackSize LinkStack& S {求栈的长度：计算栈元素个数LinkNode *p = S; int k = 0;while p != NULL { p = p-link; k; }逐个结点计数return k;}
链式栈主要操作的性能分析如表3-2所示，其中n是链式栈中元素个数。表3-2 链式栈各操作性能的比较操作名时间复杂度空间复杂度操作名时间复杂度空间复杂度初始化InitStackO1O1读取栈顶GetTopO1O1进栈PushO1O1判栈空StackEmptyO1O1退栈PopO1O1计算栈长StackSizeOnO1
除计算栈长操作需要逐个结点处理，时间复杂度达到On以外，其他操作的时间和空间性能都相当好。此外，如果事先无法根据问题要求确定栈空间大小时，使用链式栈更好些，因为它没有事先估计栈空间大小的困扰，也不需要事先分配一块足够大的地址连续的存储空间。但是由于每个结点增加了一个链接指针，导致存储密度较低。如果同时使用n个链式栈，其头指针数组可以用以下方式定义：LinkStack *s = LinkStack* malloc n*sizeof LinkStack ;在多个链式栈的情形中，link域需要一些附加的空间，但其代价并不很大。3.1.5 扩展阅读：栈的混洗设给定一个数据元素的序列，通过控制入栈和退栈的时机，可以得到不同的退栈序列，这就叫做栈的混洗。在用栈辅助解决问题时，需要考虑混洗问题。那么，对于一个有n个元素的序列，如果让各元素按照元素的序号1, 2, , n的顺序进栈，可能的退栈序列有多少种？不可能的退栈序列有多少种？现在来做一讨论。当进栈序列为1, 2时，可能的退栈序列有两种：{1, 2}和{2, 1}；当进栈序列为1, 2, 3时，可能的退栈序列有 5 种：{1, 2, 3}，{1, 3, 2}，{2, 1, 3}，{2, 3, 1}，{3, 2, 1}。注意，{3, 1, 2}是不可能的退栈序列。一般情形又如何呢？若设进栈序列为1, 2, , n，可能的退栈序列有mn种，则：* 当n = 0时：m0 = 1，退栈序列为{}。* 当n = 1时：m1 = 1，退栈序列为{1}。* 当n = 2时：退栈序列中1在首位，1左侧有0个数，右侧有1个数，有m0m1 = 1种退栈序列：{1, 2}；退栈序列中1在末位，1左侧有1个数，右侧有0个数，有m1m0 = 1种退栈序列：{2, 1}。总的可能退栈序列有m2 = m0m1 m1m0 = 2种。* 当n = 3时：退栈序列中1在首位，1左侧有0个数，右侧有2个数，有m0m2 = 2种退栈序列：{1, 2, 3}和{1, 3, 2}；退栈序列中1在第 2 位，1左侧有1个数，右侧有1个数，有m1m1 = 1种退栈序列：{2, 1, 3}；退栈序列中1在第 3 位，1左侧有2个数，右侧有0个数，有m2m0 = 2 种退栈序列：{2, 3, 1}和{3, 2, 1}。总的可能退栈序列有m3 = m0m2 m1m1 m2m0 = 5种。* 当n = 4时：在退栈序列中置1在第 1 位、第2位、第3位和第4位，得到总的可能退栈序列数有m4 = m0m3 m1m2 m2m1 m3m0 = 15 12 21 51 = 14 种。一般地，设有n个元素按序号1, 2, , n 进栈，轮流让1在退栈序列的第1, 2, , n位，则可能的退栈序列数为mn =再看不可能的退栈序列又是什么情况。设对于初始进栈序列1, 2, , n，利用栈得到可能的退栈序列为p1 p2 pi pn，如果进栈时按pi、pj、pk次序，即, pi, , pj, , pk，则, pk, , pi, , pj就是不可能的退栈序列。因为pk在pi和pj之后进栈，按照栈的后进先出的特性，pi压在pj的下面，当pk最先退栈时，pi不可能先于pj退栈，所以, pk, , pi, , pj是不可能的退栈序列。【例3-6】 已知一个进栈序列为abcd，可能的退栈序列有14种，即abcd, abdc, acbd, acdb, adcb, bacd, badc, bcad, cbad, bcda, bdca, cbda, cdba, dcba；不可能的退栈序列有4!-14 = 24-10 = 10种，原因参看表3-3。表3-3 不可能的退栈序列不可能退栈序列不可能的原因adbcb先于c进栈，d退栈时b一定压在c下，不可能b先于c退栈bdaca先于c进栈，d退栈时a一定压在c下，不可能a先于c退栈cabda先于b进栈，c退栈时a一定压在b下，不可能a先于b退栈cadba先于b进栈，c退栈时a一定压在b下，不可能a先于b退栈cdaba先于b进栈，c退栈时a一定压在b下，不可能a先于b退栈dabc按照a, b, c, d顺序进栈，d先退栈，a, b, c一定还在栈内，且a压在最下面，b压在c下面，不可能b先于c或a先于b退栈dacba先于b进栈，d退栈时a一定压在b下，不可能a先于b退栈dcaba先于b进栈，d退栈时a一定压在b下，不可能a先于b退栈dbaca先于c进栈，d退栈时a一定压在c下，不可能a先于c退栈dbcab先于c进栈，d退栈时b一定压在c下，不可能b先于c退栈
3.2 队??列3.2.1 队列的概念队列是另一种限定存取位置的线性表。它只允许在表的一端插入，在另一端删除。允许插入的一端叫做队尾，允许删除的一端叫做队头，参看图3-9。每次在队尾加入新元素，因此元素加入队列的顺序依次为a1, a2, , an。最先进入队列的元素最先退出队列，如同在铁路车站售票口排队买票一样，队列所具有的这种特性就叫做先进先出（First In First Out，FIFO）。队列的主要操作如下：（1）队列的初始化：void InitQueue Queue& Q 。先决条件：无。操作结果：队列Q置空，并对各数据成员赋初值。（2）进队列：int EnQueue Queue& Q, QElemType x 。先决条件：队列Q已存在且未满。操作结果：新元素x进队列Q并成为新的队尾。（3）出队列：int DeQueue Queue& Q, QElemType& x ;先决条件：队列Q已存在且非空。操作结果：若队列Q空，则函数返回0，x不可用；否则队列Q的队头元素退队列, 退出元素由x返回，函数返回1。（4）读取队头：int GetFront Queue& Q, QElemType& x 。先决条件：队列Q已存在且队列非空。操作结果：若队列Q空，则函数返回0，x不可用；否则由引用型参数x返回队列元素的值但不退队列，函数返回1。（5）判队列空否：int QueueEmpty Queue& Q 。先决条件：队列Q已存在。操作结果：判队列Q空否。若队列空，则函数返回1，否则函数返回0。（6）判队列满否：int QueueFull Queue& Q 。先决条件：队列Q已存在。操作结果：判队列Q满否。若队列满，则函数返回1，否则函数返回0。（7）求队列长度：int QueueSize Queue& Q 。先决条件：队列Q已存在。操作结果：函数返回队列Q的长度，即队列Q中元素个数。3.2.2 循环队列队列的存储表示也有两种方式：一种是基于数组的存储表示，另一种是基于链表的存储表示。队列的基于数组的存储表示亦称为顺序队列，它利用一个一维数组elem[maxSize]来存放队列元素，并且设置两个指针front和rear，分别指示队列的队头和队尾位置。【例3-7】 顺序队列的初始化、插入和删除如图3-10所示。maxSize是数组的最大长度。
图3-10 顺序队列的初始化、插入和删除的示意从图3-10中可以看到，在队列刚建立时，需要首先对它初始化，令front = rear = 0。每当加入一个新元素时，先将新元素添加到rear所指位置，再让队尾指针rear进1。因而指针rear指示了实际队尾位置的后一位置，即下一元素应当加入的位置。而队头指针front则不然，它指示真正队头元素所在位置。所以，如果要退出队头元素，应当首先把front所指位置上的元素值记录下来，再让队头指针front进1，指示下一队头元素位置，最后把记录下来的元素值返回。从图3-10中还可以看到，当队列指针front == rear时，队列为空；而当rear == maxSize时，队列满，如果再加入新元素，就会产生溢出。但是，这种溢出可能是假溢出，因为在数组的前端可能还有空位置。为了能够充分地使用数组中的存储空间，把数组的前端和后端连接起来，形成一个环形的表，即把存储队列元素的表从逻辑上看成一个环，成为循环队列。【例3-8】 循环队列的初始化、插入和删除如图3-11所示。循环队列的首尾相接，当队头指针front和队尾指针rear进到maxSize-1后，再前进一个位置就自动到0。这可以利用整数除取余的运算（%）来实现。队头指针进1：front = front 1 % maxSize。队尾指针进1：rear = rear 1 % maxSize。
图3-11 循环队列的初始化、插入和删除的示意循环队列的队头指针front和队尾指针rear初始化时都置为0。在队尾插入新元素和删除队头元素时，两个指针都按顺时针方向进1。当它们进到maxSize-1时，并不表示表的终结，只要有需要，利用 %（取模或取余数）运算可以前进到数组的0号位置。如果循环队列取出元素的速度快于存入元素的速度，队头指针很快追上了队尾指针，一旦到达front == rear，队列变空；反之，如果队列存入元素的速度快于取出元素的速度，队尾指针很快就赶上了队头指针，使得队列变满。为了区别于队空条件，用rear 1 % maxSize == front来判断是否队满，就是说，让rear指到front的前一位置就认为队已满。此时，因队尾指针指示实际队尾的后一位置，所以在队满时实际空了一个元素位置。如果不留这个空位置，让队尾指针一直走到这个位置。必然有rear == front，则队空条件和队满条件就混淆了。除非另加队空∕队满标志，否则无从分辨到底是队空还是队满。思考题 在循环队列中，最多只能存放maxSize-1个元素。在设计队列时，若估计队列需要容纳n个元素，则队列容量至少应设计多大？循环队列还有其他可能的实现方式，例如：（1）使用队头指针front、队尾指针rear加上一个进队出队的标志tag，可以实现循环队列。新元素进队列时置tag = 1，以rear == front和tag == 1作为判断队列是否为满的条件；元素出队列时置tag = 0，以rear == front和tag == 0作为判断队列是否为空的条件。队列的进队列和出队列操作仍然按加1取模来实现。（2）使用队尾指针rear和队列长度length（作为队列的控制变量），也可实现循环队列。思考题 使用队尾指针rear时队头在何处？是在rear 1处，还是在rear - length 1处？是否需要用% maxSize处理一下？循环队列使用了一个容量为maxSize的元素数组elem，还需要两个指针front和rear，这样可定义如程序3-11所示的循环队列的结构。程序3-11 循环队列的结构定义（保存于头文件 CircQueue.h 中）
typedef int QElemType;#define maxSize 20 循环队列的容量typedef struct { QElemType elem[maxSize]; 元素数组 int front, rear;队头指针和队尾指针（数组下标）} CircQueue;
在实际应用时循环队列多采用静态存储分配。例如，作为系统的输入缓冲区，一旦队列满，系统将产生中断，直到队列元素取走为止；作为系统的输出缓冲区，一旦队列空，系统将产生输出中断，直到队列中重新填充元素为止。循环队列主要操作的实现如程序3-12所示。注意，队头和队尾指针都在同一方向进1，不像栈的栈顶指针那样，进栈和退栈是相反的两个方向。程序3-12 循环队列主要操作的实现
void InitQueue CircQueue& Q {循环队列初始化：令队头指针和队尾指针归零 Q.front = Q.rear = 0; };int EnQueue CircQueue& Q, QElemType x {若队列不满, 则将元素x插入到队尾, 函数返回1，否则函数返回0，不能进队列if Q.rear 1 % maxSize == Q.front return 0; 队列满则不能插入,函数返回0Q.elem[Q.rear] = x; 按照队尾指针指示位置插入Q.rear = Q.rear 1 % maxSize; 队尾指针进1return 1;插入成功, 函数返回1};int DeQueue CircQueue& Q, QElemType& x {若队列不空，则函数退掉一个队头元素并通过引用型参数x返回，函数返回1, 否则函数返回0，此时x的值不可引用if Q.front == Q.rear return 0; 队列空则不能删除，函数返回0x = Q.elem[Q.front];Q.front = Q.front 1 % maxSize;队头指针进1return 1;删除成功，函数返回1};int GetFront CircQueue& Q, QElemType& x {若队列不空，则函数通过引用参数x返回队头元素的值，函数返回1，否则函数返回0，此时x的值不可引用if Q.front == Q.rear return 0; 队列空则函数返回0x = Q.elem[Q.front]; 返回队头元素的值return 1;};int QueueEmpty CircQueue& Q {判队列空否。若队列空，则函数返回1；否则返回0return Q.front == Q.rear;返回front==rear的运算结果};int QueueFull CircQueue& Q {判队列满否。若队列满，则函数返回1；否则返回0return Q.rear 1 % maxSize == Q.front;返回布尔式的运算结果};int QueueSize CircQueue& Q {求队列元素个数return Q.rear-Q.front maxSize % maxSize;};
思考题 Q.rear - Q.front的结果在什么情况下是正数，在什么情况下是负数？循环队列主要操作的性能如表3-4所示。表3-4 循环队列各个操作的性能比较操作名时间复杂度空间复杂度操作名时间复杂度空间复杂度初始化initQueueO1O1判队列空否QueueEmptyO1O1进队列EnQueueO1O1判队列满否QueueFullO1O1出队列DeQueueO1O1求队列长度QueueSizeO1O1读取队头GetFrontO1O1
循环队列所有操作的时间复杂度和空间复杂度都为O1，其性能十分良好。注意，空间复杂度是指操作中所使用的附加空间的复杂度，它是常数级的，包括0个附加空间。思考题 在后续章节，如树与二叉树、图、排序等，如果在它们的算法中使用了顺序栈或循环队列，这些栈或队列是那些算法的附加空间。在这种场合，栈或队列涉及的元素数组是否应计入算法的空间复杂度度量内？
3.2.3 链式队列链式队列是队列的基于单链表的存储表示，如图3-12所示。在单链表的每一个结点中有两个域：data域存放队列元素的值，link域存放单链表下一个结点的地址。
图3-12 链式队列在不设头结点的场合，队列的队头指针指向单链表的首元结点，若要从队列中退出一个元素，必须从单链表中删去首元结点。而队列的队尾指针指向单链表的尾结点，存放新元素的结点应插在队列的队尾，即单链表的尾结点后面，这个新结点将成为新的队尾。用单链表表示的链式队列特别适合于数据元素变动比较大，而且不存在队列满而产生溢出的情况。另外，假若程序中要使用多个队列，与多个栈的情形一样，最好使用链式队列，这样不会出现存储分配不合理的问题，也不需要进行存储的移动。思考题 在链式队列中设置头结点与不设置头结点有什么不同？链式队列每个结点的定义与单链表结点相同，队列设置了两个指针：队头指针front指向首元结点，队尾指针rear指向链尾结点。链表中所有结点都必须通过这两个指针才能找到。队列的结构定义如程序3-13所示。程序3-13 链式队列的结构定义（保存于头文件 LinkQueue.h 中）
typedef int QElemType;typedef struct Node {链式队列结点 QElemType data;结点的数据 struct Node *link; 结点的链接指针} LinkNode;typedef struct { 链式队列 LinkNode *front, *rear;队列的队头和队尾指针} LinkQueue;
链式队列主要操作的实现如程序3-14所示，与单链表不同的是，插入和删除仅限于队列的两端：插入（进队列）在队尾，新结点成为新的队尾；删除（出队列）在队头，队列的第二个结点成为新的首元结点。程序3-14 链式队列主要操作的实现
void InitQueue LinkQueue& Q {队列初始化：令队头指针和队尾指针均为NULLQ.front = Q.rear = NULL;队头与队尾指针初始化};int EnQueue LinkQueue& Q, DataType x {进队列：将新元素x插入到队列的队尾（链尾）LinkNode *s = LinkNode* malloc sizeof LinkNode; 创建新结点s-data = x; s-link = NULL;if Q.rear == NULL Q.front = Q.rear = s;空队列时新结点是唯一结点else { Q.rear-link = s; Q.rear = s; } 新结点成为新的队尾return 1;}int DeQueue LinkQueue& Q, QElemType& x {出队列：如果队列空，不能退队，函数返回0，且引用参数x的值不可用如果队列不空，函数返回1，且从引用参数x得到被删元素的值if Q.front == NULL return 0;队列空，不能退队，返回0LinkNode *p = Q.front; x = p-data;存队头元素的值Q.front = p-link; free p;队头修改，释放原队头结点if Q.front == NULL Q.rear = NULL;return 1;}int GetFront LinkQueue& Q, QElemType& x {读取队头元素的值：若队列空，则函数返回0，且引用参数x的值不可用若队列不空，则函数返回1，且从引用参数x可得到退出的队头元素的值if Q.front == NULL return 0; 队列空，不能读，返回0x = Q.front-data;return 1;取队头元素中的数据值}int QueueEmpty LinkQueue& Q {判队列空否：队列空则函数返回1，否则函数返回0 return Q.front == NULL;返回布尔式的计算结果};int QueueSize LinkQueue& Q {求队列元素个数 LinkNode *p = Q.front; int k = 0; while p != NULL { p = p-link; k; } return k;}
链式队列主要操作的性能如表3-5所示。表3-5 链式队列各操作的性能比较操作名时间复杂度空间复杂度操作名时间复杂度空间复杂度初始化InitQueueO1O1判队列空否QueueEmptyO1O1进队列EnQueueO1O1判队列满否QueueFullO1O1出队列DeQueueO1O1求队列长度QueueSizeOnO1读取队头GetFrontO1O1
除求队列长度的操作外，其他链式队列的操作的时间和空间复杂度都很好。求队列长度的操作需要对链式队列所有结点逐个检测，若设链式队列中有n个结点，其时间复杂度达到On。思考题 为何链式队列不采用循环单链表作为其存储表示？
3.3 栈 的 应 用栈在计算机科学与技术领域应用十分广泛，本节所涉及的仅是其中的一小部分。希望通过几个小的实例，让读者学会如何灵活使用栈来解决问题。3.3.1 数制转换在计算机基础课程中已经讲过如何利用除2取余法把一个十进制整数转换为二进制数。例如，一个十进制整数111转换为二进制数1101111的计算过程如图3-13所示。若想把一个十进制整数转换为八进制数也可以使用类似的方法。例如，一个十进制整数1347转换为八进制数2503的计算过程如图3-14所示。
整数N111552713631
整数N1347168212商（N 2）5527136310
商（N 8）1682120余数（N % 2）1111011
余数（N % 8）3052 图3-13 十进制数转换为二进制数的过程 图3-14 十进制数转换为八进制数的过程一般地，可把此方法推广到把十进制整数转换为k进制数。【例3-9】 可以利用栈解决数制转换问题。例如，4910 = 125124 120 = 1100012。其转换规则如下：其中，bi 表示k进制数的第i位上的数字。这样，十进制数N可以用长度为 logkN1位的k进制数表示为 b2 b1 b0。若令j = logkN，则有N = bj kj bj-1 k j-1 ... b1 k1 b0 = bj k j-1 bj-1 kj-2... b1 k b0????bj k j-1 bj-1 kj-2... b1 = bj k j-2 bj-1 kj-3... b2 k因此，可以先通过N % k求出b0，然后令N = N k，再对新的N做除k求模运算可求出b1如此重复，直到算出的N等于零结束。这个计算过程是从低位到高位逐个进行的，但输出过程是从高位到低位逐个打印的，为此需要利用栈来实现。算法如程序3-15所示。程序3-15 使用栈实现数制转换的算法
typedef int SElemType;int BaseTrans int N { int i, result = 0; SeqStack S; InitStack S ; while N != 0 { i = N % k; N = N k; Push S, i ; } while ! StackEmpty S { Pop S, i ; result = result*10 i; } return result;}
在程序中，进栈和退栈都是线性的，这种流水式的处理体现了栈和队列的优越性。与一维数组中使用下标跳来跳去进行处理相比，使用栈和队列辅助算法的实现不仅思路清晰，而且正确性更好。3.3.2 括号匹配【例3-10】 在一个用字符串描述的表达式a*b c-d中，位置0和位置3有左括号，位置7和位置10有右括号。位置0的左括号匹配位置10的右括号，位置3的左括号匹配位置7的右括号。而对于字符串a b，位置5的右括号没有可匹配的左括号，位置6的左括号没有可匹配的右括号。现在要建立一个算法，输入一个字符串，输出匹配的括号和没有匹配的括号。可以观察到，如果从左向右扫描一个字符串，那么每一个右括号将与最近出现的那个未匹配的左括号相匹配。这个观察的结果使我们联想到可以在从左向右的扫描过程中把所遇到的左括号存放到栈中。每当在后续的扫描过程中遇到一个右括号时，就将它与栈顶的左括号（如果存在）相匹配，并删除栈顶的左括号。图3-15是利用栈对字符串a*b c-d进行括号匹配的过程，图3-16是利用栈对字符串a b进行括号匹配的过程。
顺序栈内容当前字符动作剩余字符串顺序栈内容当前字符动作剩余字符串0空''''进栈"a*b c-d"6'''', ''''''c''跳过"c-d"1''''''a''跳过"a*b c-d"7'''', ''''''''退栈"-d"2''''''*''跳过"*b c-d"8''''''-''跳过"-d"3''''''''进栈"b c-d"9''''''d''跳过"d"4'''', ''''''b''跳过"b c-d"10''''''''退栈""5'''', '''''' ''跳过" c-d"11空无结束""图3-15 无错误的括号匹配过程顺序栈内容当前字符动作剩余字符串顺序栈内容当前字符动作剩余字符串0空''''进栈"a b"4''''''''退栈""1''''''a''跳过"a b"5空''''报错""2'''''' ''跳过" b"6空''''进栈""3''''''b''跳过"b"7''''无报错""图3-16 有错误的括号匹配过程程序3-16给出相应的算法。因为括号数目不定，采用了链式栈。其时间复杂度为On，其中n是输入串的长度。程序3-16 判断括号匹配的算法
#include #include #define stkSize 10void PrintMatchedPairs char expr[] {参数expr应是已存在的表达式字符串，算法给出括号匹配的过程int S[stkSize]; int top = -1; 设置栈S并置空int j, i = 0; char ch = expr[i];while ch != ''\0'' { 在表达式中搜索''''和'''' if ch == '''' S[top] = i;左括号, 位置进栈 else if ch == '''' {右括号if top != -1 {如果栈不空，有括号匹配 j = S[top--];退栈 printf "位置%d的左括号与位置%d的右括号匹配！\n", j, i ; } else printf "栈空，没有与位置%d的右括号匹配的左括号！\n", i ; } ch = expr[i];跳过，取下一字符}while top != -1 {串已处理完，但栈中还有左括号 j = S[top--]; 报错次数等于栈中左括号数目 printf "没有与位置%d的左括号相匹配的右括号！\n", j ;}}
算法扫描表达式，只要遇到左括号立即将它进栈。如果遇到右括号，就要看栈顶，如果栈不空，括号可配对；将栈顶退掉；如果栈空，表示右括号无左括号与之配对，报错。如果表达式扫描完，栈不空，表示栈内还有左括号，但再无右括号与之配对，报错。此程序修改一下，使用3个栈，就可以同时解决在文本中的{与}、[与]、与的匹配问题。3.3.3 表达式的计算与优先级处理在计算机中执行算术表达式的计算是通过栈来实现的。如何将表达式翻译成能够正确求值的指令序列，是语言处理程序要解决的基本问题。作为栈的应用事例，下面讨论表达式的求值过程。任何一个表达式都是由操作数、操作符和分界符组成。通常，算术表达式有3种表示：（1）中缀表达式： ，例如A B。（2）前缀表达式： ，例如 AB。（3）后缀表达式： ，例如AB 。后缀表达式也叫做RPN或逆波兰记号。我们日常生活中所使用的表达式都是中缀表达式。如A B*C-D-EF就是中缀表达式。为了正确执行这种中缀表达式的计算，必须明确各个操作符的执行顺序。为此，C语言为每一个操作符都规定了一个优先级。为简单起见，本节只讨论算术运算中的双目操作符。C语言规定一个表达式中相邻的两个操作符的计算次序为：优先级高的先计算；如果优先级相同，则自左向右计算；当使用括号时，从最内层的括号开始计算。对于编译程序来说，一般使用后缀表达式对表达式求值。因为用后缀表达式计算表达式的值，在计算过程中不需考虑操作符的优先级和括号，只需顺序处理表达式的操作符即可。【例3-11】 给出一个中缀表达式A B*C-D-EF，求值的执行顺序如图3-17所示，R1、R2、R3、R4、R5为中间计算结果。与图3-17所示的表达式计算等价的后缀表达式计算过程如图3-18所示。与中缀表达式A B*C-D-EF对应的后缀表达式为ABCD-* EF-。
图3-17 中缀表达式计算顺序图3-18 后缀表达式的计算顺序通过后缀表示计算表达式值的过程为：顺序扫描表达式的每一项，然后根据它的类型做如下相应操作：如果该项是操作数，则进栈；如果是操作符，则连续从栈中退出两个操作数Y和X，形成运算指令X Y，并将计算结果重新进栈。当表达式的所有项都扫描并处理完后，栈顶存放的就是最后的计算结果。【例3-12】 对于后缀表达式ABCD-* EF-的求值过程如图3-19所示。
步扫描项项类型动 作栈中内容 1 置空栈空 2 A操作数进栈A 3 B操作数进栈A B 4 C操作数进栈A B C 5 D操作数进栈A B C D 6 ?操作符D、C退栈，计算C?D，结果R1进栈A B R1 7 *操作符R1、B退栈，计算B*R1，结果R2进栈A R2 8操作符R2、A退栈，计算A R2，结果R3进栈R3 9 E操作数进栈R3 E10 F操作数进栈R3 E F11 操作符F、E退栈，计算EF，结果R4进栈R3 R412 ?操作符R4、R3退栈，计算R3?R4，结果R5进栈R5图3-19 使用操作符栈的后缀表达式的求值过程程序3-17给出简单计算器的模拟。它要求从键盘读入一个字符串后缀表达式，计算表达式的值。该计算器接收的操作符包括 '' ''、''-''、''*''、''''，操作数在''0''～''9''之间。程序3-17 计算后缀表达式的值
#include #include #include #define stkSize 20预设操作数栈的大小int DoOperator int OPND[], int& top, char op {算法：从操作数栈OPND中取两个操作数，根据操作符op形成运算指令并计算 int left, right; if top == -1 检查栈空否？
|
|
購物車/收銀台(0) | 在線留言板
| 付款方式
| 聯絡我們
| 運費計算
| 幫助中心 |
加入書簽
HOME
新書上架
