数据结构实例教程（C语言版）

目　录

第1章　绪论及C语言介绍　1
1.1　基本概念与术语　1
1.2　学习数据结构的意义　3
1.3　算法的描述和分析　5
1.4　C语言相关知识介绍　6
知识实践一　学生管理系统登录模块设计　9
习题　10

第2章　线性表的结构分析与应用　12
2.1　线性表的逻辑结构　12
2.2　线性表的顺序存储结构　13
2.2.1　顺序表定义及地址计算　13
2.2.2　顺序表基本运算　13
2.3　线性表的链式存储结构　16
2.3.1　单链表　16
2.3.2　循环链表　18
2.4　顺序表和链表的比较　19
知识实践二　学生管理系统成绩插入、删除模块设计　20
知识实践三　嵌入式系统中任务的创建和删除模拟设计　23
习题　25

第3章　栈和队列的结构分析与应用　27
3.1　栈　27
3.1.1　栈的定义及基本运算　27
3.1.2　顺序栈及操作实现　28
3.1.3　链栈及操作实现　30
3.2　队列　32
3.2.1　队列的定义及基本运算　32
3.2.2　顺序队列及操作实现　32
3.2.3　链队列及操作实现　35
知识实践四　计算器中进制转换模块设计　37
知识实践五　单片机或者嵌入式系统中断模拟设计　39
知识实践六　学生舞会舞伴配对系统设计　42
习题　44

第4章　字符串的结构分析与应用　46
4.1　串的定义及其运算　46
4.1.1　串的基本概念　46
4.1.2　串的基本运算　47
4.2　串的存储结构　47
4.2.1　串的顺序存储结构　47
4.2.2　串的链式存储结构　48
4.2.3　子串的定位运算　48
知识实践七　学生管理系统家庭情况模块设计　49
习题　50

第5章　二维数组及广义表的结构分析　51
5.1　二维数组的存储结构及求址方法　51
5.2　矩阵的压缩存储　52
5.2.1　特殊矩阵　52
5.2.2　稀疏矩阵　53
5.3　广义表的概念　54
知识实践八　求二维数组元素在内存中的存储位置　55
习题　56

第6章　树和二叉树的结构分析与应用　57
6.1　树的概念　57
6.2　二叉树　59
6.2.1　二叉树的定义　59
6.2.2　二叉树的性质　60
6.2.3　二叉树的存储结构　60
6.3　 二叉树的遍历　64
6.4　线索二叉树　66
6.5　树和森林　67
6.5.1　树、森林与二叉树的相互转换　67
6.5.2　树的存储结构　69
6.5.3　树和森林的遍历　71
6.6　哈夫曼树及其应用　72
6.6.1　哈夫曼树的定义　72
6.6.2　哈夫曼树的构造　73
6.6.3　哈夫曼树编码　74
知识实践九　利用二叉树遍历实现学生成绩排序模块设计　74
习题　76

第7章　图的结构分析与应用　80
7.1　图的概念及相关术语　80
7.1.1　图的概念　80
7.1.2 图的相关术语　81
7.2　图的存储结构　83
7.2.1　邻接矩阵表示法　83
7.2.2　邻接表表示法　84
7.3　图的遍历　86
7.3.1　深度优先遍历　87
7.3.2　广度优先遍历　89
7.4　最小生成树　90
7.4.1　普里姆算法　91
7.4.2　克鲁斯卡尔算法　91
7.5　最短路径　92
7.5.1　单源最短路径　92
7.5.2　每一对顶点之间的最短路径　93
知识实践十　江苏省地级市组成的地图遍历　96
习题　98

第8章　查找的分析与应用　101
8.1　基本概念　101
8.2　线性表查找　102
8.2.1　顺序查找　102
8.2.2　二分查找　103
8.2.3　分块查找　105
8.3　二叉排序树　106
8.3.1　二叉排序树定义　106
8.3.2　二叉排序树的插入和生成　107
8.3.3　二叉排序树的删除　108
8.3.4　二叉排序树的查找　109
8.4　散列技术　109
8.4.1　散列表的概念　109
8.4.2　散列函数的构造方法　110
8.4.3　处理冲突的方法　110
知识实践十一　利用二分法查找实现学生信息查询模块设计　111
习题　113

第9章　排序的分析与应用　114
9.1　排序的基本概念　114
9.1.1　排序的定义　114
9.1.2　相关概念　115
9.2　插入排序　116
9.2.1　直接插入排序　117
9.2.2　希尔排序　120
9.3　交换排序　121
9.3.1　冒泡排序　121
9.3.2　快速排序　123
9.4　选择排序　126
9.4.1　直接选择排序　126
9.4.2　堆排序　128
9.5　归并排序　131
9.6　各种内部排序算法的比较　133
知识实践十二　学生总成绩排序模块设计　134
习题　136

第10章　文件　138
10.1　文件的概念　138
10.1.1　文件的基本概念　138
10.1.2　文件的逻辑结构和物理结构　139
10.1.3　文件的操作　139
10.2　顺序文件　140
10.2.1　存储在顺序存储器上的顺序文件　140
10.2.2　存储在直接存储器上的顺序文件　140
10.3　索引文件　140
10.4　索引顺序文件　141
10.4.1　索引顺序文件的特点　141
10.4.2　VSAM文件的组织方法　141
10.5　散列文件　142
10.5.1　散列文件的组织方式　142
10.5.2　散列文件的操作　142
10.6　多关键字文件　143
10.6.1　多关键字文件概念　143
10.6.2　倒排文件　144
10.6.3　多重表文件　144
习题　146

第11章　数据结构综合应用　147
11.1　综合应用一：新生报到信息注册系统设计　147
11.1.1　案例需求分析　147
11.1.2　案例知识目标　148
11.1.3　案例核心算法及实现　148
11.1.4　其他参考代码　151
11.2　综合应用二：万达停车场管理系统设计　152
11.2.1　案例需求分析　152
11.2.2　案例知识目标　154
11.2.3　案例核心算法及实现　154
11.2.4　其他参考代码　158
11.3　综合应用三：最短时间旅游路线查询系统设计　158
11.3.1　案例需求分析　158
11.3.2　案例知识目标　159
11.3.3　案例核心算法及实现　160
11.3.4　其他参考代码　162