“数据结构”是计算机系统专业的一门必修课,是计算机科学的算法理论基础和软件设计的技术基础。本教材以C语言为例,讲授线性表、栈、队列、树、图等各种数据结构及其应用,以及查找和排序的各种实现方法和其综合比较。通过本教材的学习,可以使学生掌握各种数据结构的特性、逻辑结构、存储结构和相应算法,同时训练学生设计复杂程序的能力。本教材具有很强的实践性,通过大量上机训练来加深学生对各种数据结构的理解和提高应用能力。
第1章绪论1
1.1引言1
1.2数据结构的发展简史及其在计算机科学中所处的地位2
1.3什么是数据结构3
1.4基本概念和术语4
1.5算法和算法的描述6
1.5.1算法6
1.5.2算法的描述6
1.5.3算法评价9
1.6实训项目一 验证哥德巴赫猜想10
本章小结12
习题一13
第2章线性表14
2.1线性表的逻辑结构14
2.2 线性表的顺序存储结构16
2.2.1线性表的顺序存储结构16
2.2.2线性表在顺序存储结构下的运算16
2.3线性表的链式存储结构20
2.3.1线性链表21
2.3.2循环链表28
2.3.3双向链表29
2.4一元多项式的表示及相加32
2.5实训项目二 顺序表与链表的应用34
本章小结36
习题二36
第3章栈和队列38
3.1栈38
3.1.1栈的定义及其运算38
3.1.2栈的顺序存储结构39
3.1.3多栈共享邻接空间41
3.1.4栈的链式存储结构42
3.2算术表达式求值44
3.3队列49
3.3.1队列的定义及其运算49
3.3.2队列的顺序存储结构50
3.3.3队列的链式存储结构54
3.3.4其他队列55
3.4实训项目三 栈与队列的应用56
本章小结61
习题三62
第4章串64
4.1串的基本概念64
4.1.1串的定义64
4.1.2主串和子串65
4.2串的存储结构65
4.2.1串值的存储65
4.2.2串名的存储映像67
4.3串的基本运算及其实现68
4.3.1串的基本运算68
4.3.2串的基本运算及其实现68
4.4文本编辑71
4.5实训项目四 成绩管理系统72
本章小结81
习题四82
第5章递归83
5.1递归的定义83
5.2阶乘问题85
5.3背包问题88
5.4汉诺塔问题93
5.5实训项目五 迷宫问题102
本章小结112
习题五112
第6章树114
6.1树的结构定义与基本操作114
6.1.1树的定义及相关术语114
6.1.2树的存储结构115
6.1.3树的基本操作116
6.2二叉树116
6.2.1二叉树的定义与基本操作116
6.2.2二叉树的性质119
6.2.3二叉树的存储结构120
6.2.4树与二叉树的相互转换122
6.3遍历二叉树123
目录6.3.1先序遍历123
6.3.2中序遍历124
6.3.3后序遍历124
6.3.4层次遍历125
6.3.5遍历算法的应用126
6.4线索二叉树128
6.4.1中序次序线索化算法130
6.4.2在中根线索树上检索某结点的前驱算法131
6.4.3在中根线索树上检索某结点的后继算法131
6.5二叉排序树132
6.5.1二叉排序树的定义132
6.5.2二叉排序树的生成132
6.5.3删除二叉排序树上的结点133
6.6哈夫曼树和哈夫曼算法135
6.6.1哈夫曼树的定义135
6.6.2构造哈夫曼树——哈夫曼算法136
6.6.3哈夫曼树的应用137
6.7实训项目六 哈夫曼编码应用139
本章小结143
习题六143
第7章图145
7.1基本定义和术语145
7.2图的存储结构148
7.2.1邻接矩阵148
7.2.2邻接表150
7.3图的遍历153
7.3.1深度优先遍历153
7.3.2广度优先遍历法156
7.4最小生成树158
7.5最短路径163
7.5.1单源点最短路径164
7.5.2所有顶点对之间的最短路径167
7.6拓扑排序169
7.7实训项目七 无向图的遍历171
本章小结175
习题七176
第8章查找178
8.1顺序查找178
8.2折半查找180
8.3分块查找183
8.4哈希表185
8.4.1哈希表和哈希函数的概念185
8.4.2哈希函数的构造方法186
8.4.3冲突处理188
8.5实训项目八 学生成绩修改系统192
本章小结198
习题八199
第9章排序200
9.1插入排序200
9.1.1线性插入排序200
9.1.2折半插入排序202
9.2希尔排序203
9.3选择排序205
9.4堆排序207
9.5快速排序212
9.6归并排序214
9.7基数排序217
9.8外部排序220
9.9各种排序方法的比较221
9.10实训项目九 排序系统222
本章小结230
习题九230
参考文献231
1.承担专业理论知识体系的构建任务
强调专业理论知识体系的完整性与系统性,不强调专业理论知识的深度和难度;追求学生对专业理论知识整体框架的把握,不追求学生只掌握某些局部内容的深度和难度。
2.承担专业技术框架体系的构建任务
注重让学生了解这种技术的产生与演变过程,培养学生的技术创新意识;注重让学生把握这种技术的整体框架,培养学生对新技术的学习能力;注重让学生在技术应用过程中掌握这种技术的操作,培养学生的技术应用能力;注重让学生区别同种用途的其他技术的特点,培养学生职业活动过程中的技术比较与选择能力。
3.承担职业活动体系的构建任务
依据不同职业活动对所从事者特质的要求,分别采用了项目驱动、情景驱动、效果驱动的方式,形成了“做中学”一体的系列教材结构与体例,诸如项目导引、项目分析、项目实
施等。项目驱动培养所从事者的程序逻辑思维;情景驱动培养所从事者的情景敏感特质;效果驱动培养所从事者的发散思维。本系列教材无论从课程标准的开发、教材体系的建立、教材内容的筛选、教材结构的设计还是教材素材的选择,都得到了国内知名职业教育专家和一百多所高职高专院校及相关企业专家的大力支持,并给予了十分有益的建议,从而对高职高专计算机类专业教学提供了丰富的素材和鲜活的教学经验。
