数据结构

本书全面系统地介绍了数据结构的基本概念和知识，既注重理论知识，又注重算法设计的训练。在重点章节中，结合精心编写的应用实例，介绍了应用数据结构和算法解决实际问题和进行程序设计的方法，增强了读者对基本知识的理解与掌握，更有利于分析问题能力和程序设计能力的提高。 

本书结合编者多年教学经验，全面系统地介绍了数据结构的基本概念和知识，条理清晰、重点突出，内容循序渐进、深入浅出，既注重理论知识的讲解，又注重算法设计的训练，突出了理论性与实用性。全书共分9章，第1章作为全书的综述和基础，介绍了数据结构、算法的相关概念和算法分析方法等，其后各章分别讨论了线性表、栈和队列、串、多维数组和广义表、树和二叉树、图、数据结构的定义、表示和实现，*后两章介绍了查找和内部排序的各种方法。在重点章节中，还结合精心编写的应用实例，介绍了应用数据结构和算法解决实际问题及进行程序设计的方法，增强了读者对基本知识的理解与掌握，有利于提高分析问题的能力和程序设计的能力。全书采用C语言作为数据结构和算法的描述语言。
本书可作为高等学校计算机类、信息类及相近专业本科生的数据结构课程教材，也可供从事计算机软件开发和工程应用的人员学习和参考。

第1章概论1
1.1什么是数据结构1
1.1.1数据和数据元素1
1.1.2数据对象与数据类型2
1.1.3数据结构2
1.2为什么要学习数据结构5
1.2.1学习数据结构的重要性5
1.2.2数据结构的应用举例5
1.3算法和算法分析7
1.3.1什么是算法7
1.3.2算法的描述和设计7
1.3.3算法分析8
本章小结10
习题10
第2章线性表12
2.1线性表的基本概念12
2.1.1线性表的定义12
2.1.2线性表的基本操作13
2.2线性表的顺序存储13
2.2.1顺序表13
2.2.2顺序表的基本操作14
2.2.3顺序存储方式举例17
2.3线性表的链式存储20
2.3.1单链表的基本概念20
2.3.2单链表的基本操作22
2.3.3链式存储举例25
2.3.4循环链表28
2.3.5双向链表30
2.3.6双向循环链表332.3.7静态链表34
2.4线性表顺序存储与链式存储的比较35
2.5线性表的应用36
2.5.1约瑟夫问题36
2.5.2多项式加法38
2.5.3电文加密40
本章小结42
习题43
第3章栈和队列45
3.1栈45
3.1.1栈的定义与基本操作45
3.1.2顺序栈的存储结构和操作的实现47
3.1.3链栈的存储结构和操作的实现50
3.2栈的应用52
3.2.1数制转换52
3.2.2括号匹配问题54
3.2.3子程序的调用55
3.2.4利用一个顺序栈逆置一个带头节点的单链表56
3.2.5后缀表达式59
3.3队列61
3.3.1队列的定义与基本操作61
3.3.2链队列的存储结构和操作的实现62
3.3.3顺序队列的存储结构和操作的实现64
3.4队列的应用68
3.4.1打印杨辉三角形68
3.4.2迷宫问题： 寻找一条从迷宫入口到出口的短路径71
3.5递归74
3.5.1递归的定义与实现74
3.5.2递归消除77
本章小结81
习题81
第4章串85
4.1串的定义和基本操作85
4.1.1串的定义85
4.1.2串的基本操作87
4.2串的表示和实现88
4.2.1串的定长顺序存储88
4.2.2串的堆存储结构91
4.2.3串的块链存储结构93
4.3串的模式匹配算法97
4.3.1基本的模式匹配算法97
4.3.2模式匹配的改进算法——KMP算法100
本章小结102
习题102
第5章多维数组和广义表104
5.1多维数组104
5.1.1多维数组的定义104
5.1.2数组的存储结构105
5.2矩阵的压缩存储 106
5.2.1特殊矩阵106
5.2.2稀疏矩阵108
5.3广义表 114
本章小结116
习题117
第6章树和二叉树118
6.1树的概念与基本操作118
6.1.1树的定义118
6.1.2树的一些基本概念119
6.1.3树的基本操作120
6.2二叉树120
6.2.1二叉树的定义和基本操作120
6.2.2二叉树的性质121
6.2.3二叉树的存储结构123
6.3二叉树的遍历与线索化124
6.3.1二叉树的遍历124
6.3.2线索二叉树127
6.3.3基于遍历的应用与线索二叉树的应用129
6.3.4标识符树134
6.4树和森林134
6.4.1树的存储结构134
6.4.2树、森林和二叉树之间的转换137
6.4.3树和森林的遍历140
6.5哈夫曼树及其应用142
6.5.1与哈夫曼树相关的基本概念142
6.5.2哈夫曼树的应用144
6.5.3哈夫曼编码算法的实现146
*6.6树的计数147
本章小结150
习题151
第7章图154
7.1图的基本概念154
7.1.1图的定义154
7.1.2图的相关术语155
7.2图的存储结构157
7.2.1邻接矩阵表示法157
7.2.2邻接表表示法159
7.3图的遍历163
7.3.1深度优先搜索法163
7.3.2广度优先搜索法165
7.3.3非连通图的遍历167
7.4生成树与小生成树167
7.4.1生成树的概念167
7.4.2构造小生成树的普里姆(Prim)算法168
7.4.3构造小生成树的克鲁斯卡尔(Kruskal)算法171
7.5短路径173
7.5.1从某个源点到其余各顶点的短路径174
7.5.2每一对顶点之间的短路径178
7.6拓扑排序181
7.7关键路径184
本章小结190
习题190
第8章查找195
8.1查找的基本概念195
8.1.1查找表和查找195
8.1.2查找表的数据结构表示196
8.1.3平均查找长度ASL196
8.2线性表的查找196
8.2.1顺序查找 196
8.2.2二分查找198
8.2.3分块查找201
8.3树表的查找203
8.3.1二叉排序树203
*8.3.2平衡二叉树208
*8.3.3B-树212
8.4散列表的查找221
8.4.1散列表的概念221
8.4.2散列函数的构造方法222
8.4.3处理冲突的方法 223
8.4.4散列表上的运算 227
本章小结230
习题230
第9章排序232
9.1排序的基本概念232
9.1.1关键字与排序232
9.1.2排序的稳定性233
9.1.3排序方法的分类233
9.1.4排序算法性能评价233
9.1.5不同存储方式的排序过程233
9.2插入排序234
9.2.1直接插入排序234
9.2.2希尔排序237
9.3交换排序239
9.3.1冒泡排序239
9.3.2快速排序(霍尔排序)240
9.4选择排序244
9.4.1直接选择排序244
9.4.2堆排序245
9.5归并排序250
9.6基数排序253
9.6.1桶排序253
9.6.2多关键字的排序253
9.6.3链式基数排序254
9.7内部排序算法比较257
9.8外部排序简介259
本章小结259
习题260
参考文献263

数据结构是计算机程序设计的重要理论基础，是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。数据结构的内容不仅是一般程序设计（特别是非数值性程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。它不仅是计算机专业的核心课程，也是其他理工专业的热门选修课。在计算机的应用领域中，数据结构有着广泛的应用。
计算机的程序是对信息进行加工处理，而信息的表示和组织又直接关系到处理信息程序的效率。随着计算机的普及、信息量的增加、信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂，因此，为了编写出一个“好”的程序，必须分析待处理对象的特征及各对象之间存在的关系。这就是数据结构这门课所要研究的问题。数据的结构，直接影响算法的选择和效率。
本书共分9章，第1章介绍了数据结构的基本概念和算法分析的初步知识；第2章到第5章介绍了线性表、栈和队列、串、多维数组和广义表等线性结构的基本概念及常用算法的实现；第6章和第7章介绍了非线性结构的树、二叉树、图等数据结构的存储结构和不同存储结构上的一些操作的实现；第8章介绍了各种查找表及查找方法；第9章介绍了各种排序算法。本书计划学时为64学时左右，其中上机实习为12学时左右。教师可根据专业情况，选讲或不讲目录中带*的章节。
本书是作者根据自己的教学经验总结，为地方本科院校计算机类学生编写的教材。作者在教学过程中发现，大多数学生在初学数据结构时，容易误解算法与程序之间的关系，经常会把书中的算法当作程序直接在编译器上进行运行测试。为了解决这个问题，本书采用C语言作为数据结构和算法的描述语言，并且对关键的算法都安排了比较完整的C语言程序供学生上机实习参考，只要添加上主函数，程序即可运行。本书力求做到选材精练、叙述简洁、通俗易懂，尽量避免抽象理论的介绍和复杂公式的推导。对各种数据结构均从实际出发，通过对实例的分析，使学生理解数据结构的基本概念。在每章后面带有适量的习题，习题中编排了较多的选择题和填空题，并配有习题答案，方便学生自学参考。
由于作者水平有限，书中难免会有不足之处，敬请广大读者批评指正。
编著者

第
3
章

栈 和 队 列
第3章栈 和 队 列本章要点
  栈
  栈的应用举例
  队列
  队列的应用举例
本章学习目标
  理解栈的定义及其基本运算。
  掌握顺序栈和链栈的各种操作实现。
  理解队列的定义及其基本运算。
  掌握循环队列和链队列的各种操作实现。
  学会利用栈和队列解决一些问题。
3.1栈
栈和队列是在程序设计中被广泛使用的两种重要的数据结构。由于从数据结构角度看，栈和队列是操作受限的线性表，因此，也可以将它们称为限定性的线性表结构。
3.1.1栈的定义与基本操作
在日常生活中，我们会发现有许多这样的趣事，如把许多书籍依次放进一个大小相当的箱子中，当我们在取书时，就得先把后放进去的书取走，才能拿到先放入的被压在底层的书；又如一叠洗净的盘子，洗的时候总是将盘子逐个叠放在已洗好的盘子上面，而用的时候则是从上往下逐个取用，即后洗好的盘子比先洗好的盘子先被使用。这种后进先出的结构称为栈。
1. 栈的定义
栈(Stack)是一种仅允许在一端进行插入和删除运算的线性表。栈中允许进行插入和删除的那一端，称为栈顶(Top)。栈顶的个元素被称为栈顶元素。栈中不可以进行插入和删除的那一端(即线性表的表头)，称为栈底(Bottom)。在一个栈中插入新元素，即把新元素放到当前栈顶元素的上面，使其成为新的栈顶元素，这一操作称为进栈、入栈或压栈(Push)。从一个栈中删除一个元素，即把栈顶元素删除，使其下面的元素成为[1][1]新的栈顶元素，称为出栈或退栈(Pop)。例如:

注： 遵循“后进先出”的原则。
进栈顺序为a1，a2，…，an，如图31(a)所示，而出栈顺序为an，an-1，…，a2，a1。
注意： 插入和删除都只能在栈顶一端进行。
由于栈的插入和删除操作只能在栈顶一端进行，后进栈的元素必定先出栈，所以栈又称为后进先出(Last In First Out)的线性表(简称LIFO结构)，它的这个特点可用图31(b)所示的铁路调度站形象地表示。
图31栈的图示
思考：
① 栈是什么？它与一般线性表有何不同？
②  一个栈的输入序列是12345，若在入栈的过程中允许出栈，则栈的输出序列43512可能实现吗？12345的输出呢？
讨论： 有无通用的判别原则？
答: 有!若输入序列是   …Pj…Pk…Pi …(Pj2. 栈的基本操作
定义在栈上的基本操作有以下几种。  
(1) InitStack(S)：  构造一个空栈S。
(2) ClearStack(S)：  清除栈S中的所有元素。
(3) StackEmpty(S)： 判断栈S是否为空，若为空，则返回TRUE；否则返回FALSE。
(4) GetTop(S)：  返回S的栈顶元素，但不移动栈顶指针。
(5) Push(S,x)： 插入元素x为新的栈顶元素(入栈操作)。
(6) Pop(S)：  删除S的栈顶元素并返回其值(出栈操作)。
由于栈是运算受限的线性表，因此线性表的存储结构对栈也同样适用。与线性表相似，栈也有两种存储表示方法，即顺序存储和链式存储两种结构，顺序存储的栈称为顺序栈，链式存储的栈称为链栈。
3.1.2顺序栈的存储结构和操作的实现
1. 顺序栈存储结构的定义
顺序栈是利用一组地址连续的存储单元依次存放从栈底到栈顶的数据元素。在C语言中，可以用一维数组描述顺序栈中数据元素的存储区域，并预设一个数组的空间。栈底设置在0下标端，栈顶随着插入和删除元素而变化，可用一个整型变量top来指示栈顶的位置。为此，顺序栈存储结构的描述如下： #define Maxsize 100/设顺序栈的长度为100,可依实现情况而修改/
typedef int datatype;
typedef struct
{
datatype stack[Maxsize];
int top;/栈顶指针/
}SeqStack;/顺序栈类型定义/
SeqStack S;/S为顺序栈类型变量的指针/由于C语言中数组下标是从0开始的，即S->stack[0]是栈底元素，而栈顶指针S->top是正向增长的，即进栈时栈顶指针S->top加1，然后把新元素放在top所指的空单元内；退栈时S->top减1，因此S->top等于-1(或S->top小于0)表示栈空，S->top等于Maxsize-1表示栈满。由此可知： 对顺序栈插入和删除运算相当于是在顺序表的表尾进行的，其时间复杂度为O(1)。一个栈的几种状态以及在这些状态下栈顶指针top和栈中节点的关系如图32所示。
图32栈顶指针和栈中元素之间的关系
通过分析，我们可以得出结论：
(1) 若top=-1，则表示栈空；
(2) 若top=Maxsize-1，则表示栈满。
2. 顺序栈的基本操作
由于顺序栈的插入和删除只在栈顶进行，因此顺序栈的基本操作比顺序表要简单得多。值得一提的是： 在入栈操作前，首先要判定栈是否满；在出栈操作前，又要先判定栈是否空。
(1) 构造一个空栈。SeqStack InitStack()
{SeqStack S;
S=(SeqStack )malloc(sizeof(SeqStack));
if(!S)
{printf(“空间不足”);
return NULL;}
else
{S->top=-1;
return S;}
}(2) 取栈顶元素。datatype GetTop(SeqStack S)
{if(S->top==-1)
{printf(“\n栈是空的!”);
return FALSE;}
else
return S->stack[S->top];
 } (3) 入栈。SeqStack Push(SeqStack S,datatype x)
{  if(S->top==Maxsize-1)
{printf(“\n栈是满的!”);
return NULL; }
else
{S->top ;
S->stack[S->top]=x;
return s;}
} (4) 出栈。datatype Pop(SeqStack S)
{if(S->top==-1)
{printf(“\nThe sequence stack is empty!”);
return FALSE;}
S->top–;
return S->stack[S->top 1];
}(5) 判别空栈。intStackEmpty(SeqStackS)
{if(S->top==-1)
return TRUE;
else
return FALSE;
 }例31若增加main()函数以及display()函数，则可以调试上述各种栈的基本操作算法。#define Maxsize 50
typedef int datatype;
typedef struct
{datatype stack[Maxsize];
int top;
}SeqStack;
void display(SeqStack s)
{int t;
t=s->top;
if(s->top==-1)
printf(“the stack is empty!\n”);
else
while(t!=-1)
{t–;
printf(“%d->”,s->stack[t]);}
}
main()
{int a[6]={3,7,4,12,31,15},i;
SeqStack p;
p=InitStack();
for(i=0;i<6;i )Push(p,a[i]);
printf(“output the stack values: “);
display(p);
printf(“\n”);
printf(“the stacktop value is:%d\n”,GetTop(p));
Push(p,100);
printf(“output the stack values:”);
display(p);
printf(“\n”);
printf(“the stacktop value is:%d\n”,GetTop(p));
Pop(p);
printf(“the stacktop value is:%d\n”,GetTop(p));
printf(“Pop the stack value :”);
while(!StackEmpty(p))
printf(“%4d”,Pop(p));
printf(“\n”);
}运行结果如下： output the stack values: 15->31->12->4->7->3->
the stacktop value is: 15
output the stack values: 100->15->31->12->4->7->3->