数据结构教程（第5版）

本书配套20小时的教学视频，本教程突出上机实习内容，书中给出大量的上机实验题（分为验证、设计和综合型实验），供教师和学生选用。为了方便教师教学和学生学习，本书提供了全面而丰富的教学资源，其中包括教学PPT、源程序代码和练习题参考答案等 

本书在前4版的基础上针对教育部新的考研大纲和大量读者来信提出的要求进行了修订。本书共13章，内容包括绪论、线性表、栈和队列、串、递归、数组和广义表、树和二叉树、图、查找、内排序、外排序和文件等，书中给出了大量练习题和各类上机实验题，每个知识点都配有视频讲解。
本书内容全面，知识点翔实，条理清晰，讲解透彻，实例丰富，实用性强，适合高等院校计算机和相关专业的本科生及研究生使用。

目录

 

第1章绪论

 

1.1什么是数据结构

 

1.1.1数据结构的定义

 

1.1.2逻辑结构

 

1.1.3存储结构

 

1.1.4数据运算

 

1.1.5数据类型和抽象数据类型

 

1.2算法及其描述

 

1.2.1什么是算法

 

1.2.2算法设计的目标

 

1.2.3算法描述

 

1.3算法分析

 

1.3.1算法分析概述

 

1.3.2算法时间性能分析

 

1.3.3算法空间性能分析

 

1.4数据结构 算法=程序

 

1.4.1程序和数据结构

 

1.4.2算法和程序

 

1.4.3算法和数据结构

 

1.4.4数据结构的发展

 

本章小结

 

练习题1

 

上机实验题1

 

验证性实验

 

设计性实验

 

第2章线性表

 

2.1线性表及其逻辑结构

 

2.1.1线性表的定义

 

2.1.2线性表的抽象数据类型描述

 

2.2线性表的顺序存储结构

 

2.2.1线性表的顺序存储结构——顺序表

 

2.2.2顺序表基本运算的实现

 

2.3线性表的链式存储结构

 

2.3.1线性表的链式存储结构——链表

 

2.3.2单链表

 

2.3.3双链表

 

2.3.4循环链表

 

2.4线性表的应用

 

2.5有序表

 

2.5.1有序表的抽象数据类型描述

 

2.5.2有序表的存储结构及其基本运算算法

 

2.5.3有序表的归并算法

 

2.5.4有序表的应用

 

本章小结

 

练习题2

 

上机实验题2

 

验证性实验

 

设计性实验

 

综合性实验

 

第3章栈和队列

 

3.1栈

 

3.1.1栈的定义

 

3.1.2栈的顺序存储结构及其基本运算的实现

 

3.1.3栈的链式存储结构及其基本运算的实现

 

3.1.4栈的应用

 

3.2队列

 

3.2.1队列的定义

 

3.2.2队列的顺序存储结构及其基本运算的实现

 

3.2.3队列的链式存储结构及其基本运算的实现

 

3.2.4队列的应用举例

 

3.2.5双端队列

 

本章小结

 

练习题3

 

上机实验题3

 

验证性实验

 

设计性实验

 

综合性实验

 

第4章串

 

4.1串的基本概念

 

4.2串的存储结构

 

4.2.1串的顺序存储结构——顺序串

 

4.2.2串的链式存储结构——链串

 

4.3串的模式匹配

 

4.3.1BruteForce算法

 

4.3.2KMP算法

 

本章小结

 

练习题4

 

上机实验题4

 

验证性实验

 

设计性实验

 

综合性实验

 

第5章递归

 

5.1什么是递归

 

5.1.1递归的定义

 

5.1.2何时使用递归

 

5.1.3递归模型

 

5.1.4递归与数学归纳法

 

5.2栈和递归

 

5.2.1函数调用栈

 

5.2.2递归调用的实现

 

5.2.3递归到非递归的转换

 

5.3递归算法的设计

 

5.3.1递归算法设计的步骤

 

5.3.2基于递归数据结构的递归算法设计

 

5.3.3基于递归求解方法的递归算法设计

 

本章小结

 

练习题5

 

上机实验题5

 

验证性实验

 

设计性实验

 

综合性实验

 

第6章数组和广义表

 

6.1数组

 

6.1.1数组的基本概念

 

6.1.2数组的存储结构

 

6.1.3特殊矩阵的压缩存储

 

6.2稀疏矩阵

 

6.2.1稀疏矩阵的三元组表示

 

6.2.2稀疏矩阵的十字链表表示

 

6.3广义表

 

6.3.1广义表的定义

 

6.3.2广义表的存储结构

 

6.3.3广义表的运算

 

本章小结

 

练习题6

 

上机实验题6

 

验证性实验

 

设计性实验

 

综合性实验

 

第7章树和二叉树

 

7.1树的基本概念

 

7.1.1树的定义

 

7.1.2树的逻辑表示方法

 

7.1.3树的基本术语

 

7.1.4树的性质

 

7.1.5树的基本运算

 

7.1.6树的存储结构

 

7.2二叉树的概念和性质

 

7.2.1二叉树的定义

 

7.2.2二叉树的性质

 

7.2.3二叉树与树、森林之间的转换

 

7.3二叉树的存储结构

 

7.3.1二叉树的顺序存储结构

 

7.3.2二叉树的链式存储结构

 

7.4二叉树的基本运算及其实现

 

7.4.1二叉树的基本运算概述

 

7.4.2二叉树的基本运算算法实现

 

7.5二叉树的遍历

 

7.5.1二叉树遍历的概念

 

7.5.2先序、中序和后序遍历递归算法

 

7.5.3先序、中序和后序遍历非递归算法

 

7.5.4层次遍历算法

 

7.6二叉树的构造

 

7.7线索二叉树

 

7.7.1线索二叉树的概念

 

7.7.2线索化二叉树

 

7.7.3遍历线索化二叉树

 

7.8哈夫曼树

 

7.8.1哈夫曼树概述

 

7.8.2哈夫曼树的构造算法

 

7.8.3哈夫曼编码

 

7.9用并查集求解等价问题

 

7.9.1什么叫并查集

 

7.9.2并查集的算法实现

 

本章小结

 

练习题7

 

上机实验题7

 

验证性实验

 

设计性实验

 

综合性实验

 

第8章图

 

8.1图的基本概念

 

8.1.1图的定义

 

8.1.2图的基本术语

 

8.2图的存储结构和基本运算算法

 

8.2.1邻接矩阵存储方法

 

8.2.2邻接表存储方法

 

8.2.3图基本运算算法设计

 

8.2.4其他存储方法

 

8.3图的遍历

 

8.3.1图的遍历的概念

 

8.3.2深度优先遍历

 

8.3.3广度优先遍历

 

8.3.4非连通图的遍历

 

8.3.5图遍历算法的应用

 

8.4生成树和最小生成树

 

8.4.1生成树的概念

 

8.4.2无向图的连通分量和生成树

 

8.4.3普里姆算法

 

8.4.4克鲁斯卡尔算法

 

8.5最短路径

 

8.5.1路径的概念

 

8.5.2从一个顶点到其余各顶点的最短路径

 

8.5.3每对顶点之间的最短路径

 

8.6拓扑排序

 

8.7AOE网与关键路径

 

8.7.1相关概念

 

8.7.2求AOE网的关键活动

 

本章小结

 

练习题8

 

上机实验题8

 

验证性实验

 

设计性实验

 

综合性实验

 

第9章查找

 

9.1查找的基本概念

 

9.2线性表的查找

 

9.2.1顺序查找

 

9.2.2折半查找

 

9.2.3索引存储结构和分块查找

 

9.3树表的查找

 

9.3.1二叉排序树

 

9.3.2平衡二叉树

 

9.3.3B-树

 

9.3.4B 树

 

9.4哈希表的查找

 

9.4.1哈希表的基本概念

 

9.4.2哈希函数的构造方法

 

9.4.3哈希冲突的解决方法

 

9.4.4哈希表的运算算法

 

本章小结

 

练习题9

 

上机实验题9

 

验证性实验

 

设计性实验

 

综合性实验

 

第10章内排序

 

10.1排序的基本概念

 

10.2插入排序

 

10.2.1直接插入排序

 

10.2.2折半插入排序

 

10.2.3希尔排序

 

10.3交换排序

 

10.3.1冒泡排序

 

10.3.2快速排序

 

10.4选择排序

 

10.4.1简单选择排序

 

10.4.2堆排序

 

10.5归并排序

 

10.6基数排序

 

10.7各种内排序方法的比较和选择

 

本章小结

 

练习题10

 

上机实验题10

 

验证性实验

 

设计性实验

 

综合性实验

 

第11章外排序

 

11.1外排序概述

 

11.2磁盘排序

 

11.2.1磁盘排序概述

 

11.2.2生成初始归并段

 

11.2.3多路平衡归并

 

11.2.4最佳归并树

 

11.3磁带排序

 

11.3.1多路平衡归并排序

 

11.3.2多阶段归并排序

 

本章小结

 

练习题11

 

上机实验题11

 

验证性实验

 

设计性实验

 

第12章文件

 

12.1文件的基本概念

 

12.1.1什么是文件

 

12.1.2文件的逻辑结构及操作

 

12.1.3文件的存储结构

 

12.2顺序文件

 

12.3索引文件

 

12.3.1ISAM文件

 

12.3.2VSAM文件

 

12.4哈希文件

 

12.5多关键字文件

 

12.5.1多重表文件

 

12.5.2倒排文件

 

本章小结

 

练习题12

 

上机实验题12

 

验证性实验

 

设计性实验

 

第13章采用面向对象的方法描述算法

 

13.1面向对象的概念

 

13.2用C 描述面向对象的程序

 

13.2.1类

 

13.2.2类对象

 

13.2.3构造函数和析构函数

 

13.2.4模板类

 

13.3用C 描述数据结构算法

 

13.3.1顺序表类模板

 

13.3.2链栈类模板

 

13.4使用STL设计数据结构算法

 

 

附录A实验报告格式

 

一、
设计人员相关信息

 

二、
程序设计相关信息

 

三、
实验提交内容

 

附录B引用型参数和指针引用型参数的说明

 

附录C算法索引

 

附录D名词索引

 

附录E全国计算机专业数据结构2016年

联考大纲

 

参考文献

 

前言

数据结构是研究计算机科学和工程的基础，数据结构课程是计算机科学与技术专业及相关专业的核心课程之一，学好该课程不仅对后续课程的学习有很大帮助，而且对开发有效利用计算机资源的程序极为有益。计算机是进行数据处理的工具，数据结构主要研究数据的各种组织形式以及建立在这些结构之上的各种运算算法的实现，它不仅为用计算机语言进行程序设计提供了方法性的理论指导，还在更高的层次上总结了程序设计的常用方法和常用技巧。本教程是作者针对数据结构课程概念多、算法灵活和抽象性强等特点，在总结长期教学经验的基础上编写的。全书分为13章和5个附录，第1章为绪论，介绍数据结构的基本概念，特别强调算法分析的方法； 第2章为线性表，介绍线性表的两种存储结构——顺序表和链表，以及基本运算算法的实现过程； 第3章为栈和队列，介绍这两种特殊的线性结构的概念与应用； 第4章为串，介绍串的概念与模式匹配算法； 第5章为递归，讨论计算机学科中递归算法的设计方法； 第6章为数组和广义表，介绍数组、稀疏矩阵和广义表的概念与相关运算算法的实现过程； 第7章为树和二叉树，介绍树和二叉树的概念与各种运算算法的实现过程，其中特别介绍二叉树的各种递归算法方法； 第8章为图，介绍图的概念和图的各种运算算法的实现过程； 第9章为查找，介绍各种查找算法的实现过程； 第10章为内排序，介绍各种内排序算法的实现过程； 第11章为外排序，介绍各种外排序算法的实现过程； 第12章为文件，介绍各类文件的组织结构； 第13章为采用面向对象的方法描述算法，介绍面向对象的概念和采用C 语言描述数据结构算法的方法。附录A给出了实验报告格式，附录B是引用型参数和指针引用型参数的说明，附录C给出了书中全部算法的索引，附录D给出了书中相关名词的索引，附录E为教育部颁布的2016年全国计算机专业硕士研究生入学考试专业课中的数据结构部分考试大纲。数据结构是一门应用实践性非常强的课程，学生在掌握各种数据结构（特别是存储结构）的基础上一定要尽可能多地上机实习，通过较多的实验把难以理解的抽象概念转化为实实在在的能够在计算机上执行的程序，这样才能将所学知识和实际应用结合起来，吸取算法的设计思想和精髓，提高运用这些知识解决实际问题的能力。因此，本教程突出上机实习内容，书中给出了大量的上机实验题(分为验证性实验、设计性实验和综合性实验)供教师和学生选用。为了便于学生学习和上机实验，我们还编写了与本教程配套的《数据结构教程学习指导》和《数据结构教程上机实验指导》两书，构成一个完整的教学系列。本系列教程中的所有程序均在Visual C 6．0和Dev C 5环境下调试通过。本教程和配套的上机实验指导、学习指导的编写得到武汉大学“弘毅学堂”数据结构荣誉课程教学项目和湖北省“计算机科学与技术专业课程体系改革”项目的支助，聚集了课程组许多教师多年来在数据结构课程教学研究和教学改革中的经验与成果。本书在编写过程中得到王丽娜、黄传河和吴黎兵等多位教授、博导的大力支持，陈国良院士提供了富有建设性的指导，很多使用本书的老师和同学给予了热心帮助，清华大学出版社的魏江江主任和王冰飞编辑给予了愉快的合作，作者在此一并表示衷心的感谢。为了方便教师教学和学生学习，本书提供了全面而丰富的教学资源，其中包括教学PPT、教学视频、源程序代码和练习题参考答案等，均可从清华大学出版社网站免费下载。由于水平所限，尽管作者不遗余力，本书仍可能存在错误和不足之处，敬请读者批评指正，特别希望使用本书的教师与作者探讨，共同提高我国计算机专业数据结构课程的教学水平。作者
2017年1月

评论

第3章栈和队列

从组成元素的逻辑关系看，栈和队列都属于线性结构。栈和队列与线性表的不同之处在于它们的相关运算具有一些特殊性。更准确地说，一般线性表上的插入、删除运算不受限制，而栈和队列上的插入、删除运算均受某种特殊限制，因此栈和队列也称为操作受限的线性表。本章介绍栈和队列的基本概念、存储结构、基本运算算法设计和应用实例。

3.1栈栈是一种常用而且重要的数据结构之一，如用于保存函数调用时所需要的信息，通常在将递归算法转换成非递归算法时需要使用到栈。本节主要讨论栈及其应用。3.1.1栈的定义栈(stack)是一种只能在一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶(top)，表的另一端称为栈底(bottom)，如图3.1所示。栈顶的当前位置是动态的，栈顶的当前位置由一个被称为栈顶指针的位置指示器来指示。当栈中没有数据元素时称为空栈。栈的插入操作通常称为进栈或入栈(push)，

图3.1栈示意图
栈的删除操作通常称为出栈或退栈(pop)。栈的主要特点是“后进先出”(Last In First Out，LIFO)，即后进栈的元素先出栈。每次进栈的数据元素都放在原来栈顶元素之前成为新的栈顶元素，每次出栈的数据元素都是当前栈顶元素。栈也称为后进先出表。例如，若干个人走进一个死胡同，假设该死胡同的宽度恰好只够一个人进出，那么走出死胡同的顺序和走进的顺序正好相反。这个死胡同就是一个栈。栈抽象数据类型的定义如下： 

ADT Stack
{数据对象： 
D={ ai | 1≤i≤n，n≥0，ai为ElemType类型}//ElemType是自定义类型标识符
数据关系： 
R={ai，ai 1 | ai、ai 1∈ D，i=1，…，n-1}
基本运算： 
InitStack(&s)： 初始化栈，构造一个空栈s。
DestroyStack(&s)： 销毁栈，释放栈s占用的存储空间。
StackEmpty(s)： 判断栈是否为空，若栈s为空，则返回真； 否则返回假。
Push(&s，e)： 进栈，将元素e插入到栈s中作为栈顶元素。
Pop(&s，&e)： 出栈，从栈s中删除栈顶元素，并将其值赋给e。
GetTop(s，&e)： 取栈顶元素，返回当前的栈顶元素，并将其值赋给e。
}

【例3.1】若元素的进栈序列为1234，能否得到3142的出栈序列？解为了让3作为第一个出栈元素，1、2先进栈，此时要么2出栈，要么4进栈后出栈，出栈的第2个元素不可能是1，所以得不到3142的出栈序列。【例3.2】用S表示进栈操作、X表示出栈操作，若元素的进栈顺序为1234，为了得到1342的出栈序列，给出相应的S和X操作串。解为了得到1342的出栈序列，其操作过程是1进栈，1出栈，2进栈，3进栈，3出栈，4进栈，4出栈，2出栈。因此相应的S和X操作串为SXSSXSXX。说明： n个不同的元素通过一个栈产生的出栈序列的个数为1n 1Cn2n。例如n=4时，出栈序列的个数等于14。

图3.2栈操作的一个时刻
【例3.3】一个栈的进栈序列为1，2，…，n，通过一个栈得到出栈序列p1，p2，…，pn(p1，p2，…，pn是1，2，…，n的一种排列)。若p1=3，则p2可能取值的个数是多少？解为了让3作为第一个出栈元素，将1、2、3依次进栈，3出栈，此时如图3.2所示。之后可以让2出栈，p2=2，也可以让4进栈再出栈，p2=4，也可以让4、5进栈再出栈，p2=5，…，所以p2可以是2，4，5，…，n，不可能是1和3，即p2可能取值的个数是n-2。3.1.2栈的顺序存储结构及其基本运算的实现栈中数据元素的逻辑关系呈线性关系，所以栈可以像线性表一样采用顺序存储结构进行存储，即分配一块连续的存储空间来存放栈中元素，并用一个变量（如top）指向当前的栈顶元素以反映栈中元素的变化。采用顺序存储结构的栈称为顺序栈(sequential stack)。假设栈的元素个数最大不超过正整数MaxSize，所有的元素都具有同一数据类型，即ElemType，可用下列方式来声明顺序栈的类型SqStack： 

typedef struct 
{ElemType data［MaxSize］;//存放栈中的数据元素
int top; 　　//栈顶指针，即存放栈顶元素在data数组中的下标
} SqStack; 　　//顺序栈类型

栈到顺序栈的映射过程如图3.3所示。本节采用栈指针s(不同于栈顶指针top)的方式创建和使用顺序栈，如图3.4所示。

图3.3栈到顺序栈的映射

图3.4顺序栈指针s

图3.5是一个顺序栈操作示意图。图3.5(a)是初始情况，它是一个空栈； 图3.5(b)表示元素a进栈以后的状态； 图3.5(c)表示元素b、c、d进栈以后的状态； 图3.5(d)表示元素d出栈以后的状态。综上所述，对于s所指的顺序栈(即顺序栈s)，初始时设置s->top=-1，可以归纳出对后面算法设计来说非常重要的4个要素。

图3.5栈操作示意图

 栈空的条件： s-top==-1。 栈满的条件： s-top==MaxSize-1(data数组的最大下标)。 元素e的进栈操作： 先将栈顶指针top增1，然后将元素e放在栈顶指针处。 出栈操作： 先将栈顶指针top处的元素取出放在e中，然后将栈顶指针减1。在顺序栈上对应栈的基本运算算法设计如下。1) 初始化栈initStack(&s)该运算创建一个空栈，由s指向它。实际上就是分配一个顺序栈空间，并将栈顶指针设置为-1。算法如下： 

void InitStack(SqStack *&s)
{s=(SqStack *)malloc(sizeof(SqStack));//分配一个顺序栈空间，首地址存放在s中
stop=-1; 　　//栈顶指针置为-1
}

2) 销毁栈DestroyStack(&s)该运算释放顺序栈s占用的存储空间。算法如下： 

void DestroyStack(SqStack *&s)
{
free(s);
}

3) 判断栈是否为空StackEmpty(s)该运算实际上用于判断条件s->top==-1是否成立。算法如下： 

bool StackEmpty(SqStack *s)
{
return(stop==-1);
}

4) 进栈Push(&s，e)该运算的执行过程是，在栈不满的条件下先将栈顶指针增1，然后在该位置上插入元素e，并返回真； 否则返回假。算法如下： 

bool Push(SqStack *&s,ElemType e)
{if (stop==MaxSize-1)//栈满的情况，即栈上溢出
return false;

stop ; 　　//栈顶指针增1
sdata［stop］=e; 　　//元素e放在栈顶指针处
return true;
}

5) 出栈Pop(&s，&e)该运算的执行过程是，在栈不为空的条件下先将栈顶元素赋给e，然后将栈顶指针减1，并返回真； 否则返回假。算法如下： 

bool Pop(SqStack *&s,ElemType &e)
{if (stop==-1)//栈为空的情况，即栈下溢出
return false;
e=sdata［stop］; 　　//取栈顶元素
stop–; 　　//栈顶指针减1
return true;
}

6) 取栈顶元素GetTop(s，&e)该运算在栈不为空的条件下将栈顶元素赋给e并返回真； 否则返回假。算法如下： 

bool GetTop(SqStack *s,ElemType &e)
{if (stop==-1)//栈为空的情况，即栈下溢出
return false;
e=sdata［stop］; 　　//取栈顶元素
return true;
}

和出栈运算相比，本算法只是没有移动栈顶指针。上述6个基本运算算法的时间复杂度均为O(1)，说明这是一种非常高效的设计。【例3.4】设计一个算法利用顺序栈判断一个字符串是否为对称串。所谓对称串指从左向右读和从右向左读的序列相同。

解n个元素连续进栈，产生的连续出栈序列和输入序列正好相反，本算法就是利用这个特点设计的。对于字符串str，从头到尾将其所有元素连续进栈，如果所有元素连续出栈产生的序列和str从头到尾的字符依次相同，表示str是一个对称串，返回真； 否则表示str不是对称串，返回假。算法如下： 

bool symmetry(ElemType str［］)//判断str是否为对称串
{int i; ElemType e;
SqStack *st; 　　//定义顺序栈指针
InitStack(st); 　　//初始化栈
for (i=0;str［i］!=’＼0′;i ) 　　//将str的所有元素进栈
Push(st,str［i］);
for (i=0;str［i］!=’＼0′;i ) 　　//处理str的所有字符
{Pop(st,e); 　　//退栈元素e
if (str［i］!=e) 　　//若e与当前串字符不同表示不是对称串

{DestroyStack(st);//销毁栈
return false; 　　//返回假
}
}
DestroyStack(st); 　　//销毁栈
return true; 　　//返回真
}

顺序栈采用一个数组存放栈中的元素。如果需要用到两个相同类型的栈，这时若为它们各自开辟一个数组空间，极有可能出现这样的情况： 第一个栈已满，再进栈就溢出了，而另一个栈还有很多空闲存储空间。解决这个问题的方法是将两个栈合起来，如图3.6所示，用一个数组来实现这两个栈，这称为共享栈(share stack)。

图3.6共享栈

在设计共享栈时，由于一个数组(大小为MaxSize)有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的始端，即下标为0处，另一个栈的栈底为数组的末端，即下标为MaxSize-1，这样在两个栈中进栈元素时栈顶向中间伸展。共享栈的4个要素如下。 栈空条件： 栈1空为top1==-1； 栈2空为top2==MaxSize。 栈满条件： top1==top2-1。 元素x进栈操作： 进栈1操作为top1 ;data［top1］=x； 进栈2操作为top2–;data［top2］=x。 出栈x操作： 出栈1操作为x=data［top1］;top1–； 出栈2操作为x=data［top2］;top2 。在上述设置中，data数组表示共享栈的存储空间，top1和top2分别为两个栈的栈顶指针，这样该共享栈通过data、top1和top2来标识，也可以将它们设计为一个结构体类型： 

typedef struct
{ElemType data［MaxSize］;//存放共享栈中的元素
int top1,top2; 　　//两个栈的栈顶指针
} DStack; 　　//共享栈的类型

在实现共享栈的基本运算算法时需要增加一个形参i，指出是对哪个栈进行操作，如i=1表示对栈1进行操作，i=2表示对栈2进行操作。3.1.3栈的链式存储结构及其基本运算的实现栈中数据元素的逻辑关系呈线性关系，所以栈可以像线性表一样采用链式存储结构。采用链式存储结构的栈称为链栈(linked stack)。链表有多种，这里采用带头结点的单链表来实现链栈。链栈的优点是不存在栈满上溢出的情况。规定栈的所有操作都是在单链表的表头进行的(因为给定链栈后，已知头结点地址，在其后面插入一个新结点和删除首结点都十分方便，对应算法的时间复杂度均为O(1))。图3.7所示为头结点指针为s的链栈，首结点是栈顶结点，尾结点是栈底结点。栈中元素自栈底到栈顶依次是a1，a2，…，an。

图3.7栈到链栈的映射

链栈中结点类型LinkStNode的声明如下： 

typedef struct linknode
{ElemType data;//数据域
struct linknode *next; 　　//指针域
} LinkStNode; 　　//链栈结点类型

在以s为头结点指针的链栈(简称链栈s)中，可以归纳出对后面算法设计来说非常重要的4个要素。 栈空的条件： s->next==NULL。 栈满的条件： 由于只有内存溢出时才出现栈满，通常不考虑这样的情况，所以在链栈中可以看成不存在栈满。 元素e的进栈操作： 新建一个结点存放元素e(由p指向它)，将结点p插入到头结点之后。 出栈操作： 取出首结点的data值并将其删除。

图3.8创建一个空栈

在链栈上对应栈的基本运算算法设计如下。1) 初始化栈initStack(&s)该运算创建一个空链栈s，如图3.8所示。实际上是创建链栈的头结点，并将其next域置为NULL。算法如下： 

void InitStack(LinkStNode *&s)
{s=(LinkStNode *)malloc(sizeof(LinkStNode));
snext=NULL;
}

本算法的时间复杂度为O(1)。2) 销毁栈DestroyStack(&s)该运算释放链栈s占用的全部结点空间，和单链表的销毁算法完全相同。算法如下： 

void DestroyStack(LinkStNode *&s)
{LinkStNode *pre=s,*p=snext;//pre指向头结点，p指向首结点
while (p!=NULL) 　　//循环到p为空
{free(pre); 　　//释放pre结点
pre=p; 　　//pre、p同步后移
p=prenext;
}
free(pre); 　　//此时pre指向尾结点,释放其空间
}

本算法的时间复杂度为O(n)，其中n为链栈中的数据结点个数。3) 判断栈是否为空StackEmpty(s)该运算判断s->next=NULL的条件是否成立。算法如下： 

bool StackEmpty(LinkStNode *s)
{
return(snext==NULL);
}

本算法的时间复杂度为O(1)。4) 进栈Push(&s，e)该运算新建一个结点，用于存放元素e(由p指向它)，然后将其插入到头结点之后作为新的首结点。算法如下： 

void Push(LinkStNode *&s,ElemType e)
{LinkStNode *p;
p=(LinkStNode *)malloc(sizeof(LinkStNode));//新建结点p
pdata=e; 　　//存放元素e
pnext=snext; 　　//将p结点插入作为首结点
snext=p;
}

本算法的时间复杂度为O(1)。5) 出栈Pop(&s，&e)该运算在栈不为空的条件下提取首结点的数据域赋给引用型参数e，然后将其删除。算法如下： 

bool Pop(LinkStNode *&s,ElemType &e)
{LinkStNode *p;
if (snext==NULL)//栈空的情况
return false; 　　//返回假
p=snext; 　　//p指向首结点
e=pdata; 　　//提取首结点值
snext=pnext; 　　//删除首结点