《数据结构与算法》是计算机专业的必修及主干课程之一,它旨在使读者学会分析研究数据对象的特性,学会数据的组织方法,以便选择合适的数据逻辑结构和存储结构,以及相应的运算(操作),把现实世界中的问题转化为计算机内部的表示和处理,这是一个良好的程序设计技能训练的过程。在整个教学或学习过程中,解题能力和技巧的训练是一个重要的环节。为了帮助教师讲授《数据结构》,满足指导和评价“课程设计”的需要;帮助和指导读者更好地学习《数据结构与算法》这门课程,我们编写了这本《数据结构与算法(C&C#语言描述)》教材,旨在弥补课堂教学和实验中的不足,帮助学生充分理解和巩固所学的基本概念、原理和方法,达到融会贯通、举一反三的目的。
本教材分为三个部分共9章。第一部分是课程概述,包括:第1章绪论;第二部分是基于内存数据结构,包括:第2~4章讨论数据的线性结构,其中有线性表、栈与队列和多维数组及串;第5~6章讨论树型结构,其中有树(森林)和二叉树;第7章是图结构;第三部分可看作是课程内容的高级部分,包括:第8章查找和第9章排序。
实践证明,理解课程内容与较好地解决实际问题之间存在着明显差距,而算法设计完成的质量与基本的程序设计素质的培养是密切相关的。要想理解和巩固所学的基本概念、原理和方法,牢固地掌握所学的基本知识、基本技能,达到融会贯通、举一反三的目的,就必须多做、多练、多见(见多识广)。正是为了达到上述目的,教材中用一些实际的应用,对一些重要的数据结构和算法进行解读。经过循序渐进地训练,就可以使读者掌握更多的程序设计技巧和方法,提高分析、解决问题的能力。
第1章绪论1
1.0本章项目引例:换硬币问题1
1.1数据1
1.1.1数据基本概念1
1.1.2数值型与非数值型数据2
1.2数据项与数据元素3
1.3数据类型与抽象数据类型3
1.3.1数据类型4
1.3.2抽象数据类型4
1.4数据模型与数据结构6
1.4.1数据逻辑结构6
1.4.2数据存储结构7
1.5数据操作与算法9
1.5.1数据运算9
1.5.2算法及其基本特征10
1.5.3算法设计与分析11
1.6C#语言预备知识14
1.6.1接口14
1.6.2泛型编程15
1.7数据结构的地位与内容体系16
1.7.1数据结构的地位16
1.7.2教材内容组织17
1.7.3课程学习建议18
本章小结20
第2章线性表22
2.0本章项目引例:约瑟夫生者死者游戏22
2.1线性表概念22
2.1.1线性表逻辑结构23
2.1.2线性表的ADT描述232.2线性表的顺序存储25
2.2.1顺序存储结构25
2.2.2基于顺序存储基本操作30
2.3线性表的链式存储37
2.3.1单链表概念38
2.3.2单链表的基本操作40
2.3.3循环链表52
2.3.4双向链表56
2.3.5静态链表60
2.3.6单链表应用67
2.4线性表存储结构比较70
本章小结71
第3章栈和队列73
3.0本章项目引例:停车场管理73
3.1栈73
3.1.1栈的基本概念74
3.1.2栈的顺序存储结构75
3.1.3栈的链式存储结构81
3.1.4栈的应用86
3.2队列100
3.2.1队列基本概念100
3.2.2顺序队列与循环队列101
3.2.3队列的链式存储结构108
3.2.4队列的应用115
本章小结118
第4章数组和串120
4.0本章项目引例:身份证号码校验120
4.1数组121
4.1.1二维数组121
4.1.2矩阵的顺序表示与实现121
4.1.3特殊矩阵压缩存储123
4.2串126
4.2.1串及相关概念126
4.2.2串的基本操作126
4.2.3串的存储结构129
4.2.4串的模式匹配131
本章小结141第5章二叉树及应用143
5.0本章项目引例:表达式求值143
5.1二叉树及基本性质144
5.1.1二叉树基本概念144
5.1.2二叉树基本类型和特殊类型145
5.1.3二叉树基本性质147
5.2二叉树的存储148
5.2.1二叉树顺序存储结构149
5.2.2二叉树链式存储结构150
5.3二叉树的遍历156
5.3.1先序、中序和后序遍历156
5.3.2基于递归遍历算法158
5.3.3基于非递归遍历算法163
5.4线索二叉树171
5.4.1线索与线索二叉树172
5.4.2创建线索二叉树173
5.4.3线索二叉树遍历177
5.5Huffman树及其应用178
5.5.1编码分类与Huffman树178
5.5.2Huffman树构建思想180
5.5.3基于顺序存储的Huffman树构造181
5.5.4Huffman编码186
5.5.5电文编码与译码190
本章小结196
第6章树与森林198
6.0本章项目引例:家谱管理198
6.1树的概念与表示198
6.1.1树的基本概念199
6.1.2树的表示方法200
6.1.3树的相关概念201
6.2树的存储结构202
6.2.1父结点表示法存储202
6.2.2子结点表示法存储203
6.2.3左子/右兄弟结点表示法存储209
6.3树的遍历210
6.3.1层次遍历210
6.3.2先序遍历213
6.3.3后序遍历215
6.4森林216
6.4.1森林的存储216
6.4.2森林的遍历216
6.5树与二叉树的转换217
6.5.1树转换为二叉树217
6.5.2二叉树还原为树218
6.5.3森林与二叉树的转换219
本章小结220
第7章图222
7.0本章项目引例:公交线路管理222
7.1基本概念与相关描述222
7.1.1图的基本概念222
7.1.2图的相关概念224
7.2图的存储226
7.2.1基于邻接矩阵存储226
7.2.2基于邻接表存储230
7.3图的遍历235
7.3.1深度优先遍历235
7.3.2广度优先遍历240
7.3.3简单路径与路径长度最小路径244
7.4生成树与最小生成树247
7.4.1图的生成树247
7.4.2最小生成树248
7.5最短路径263
7.5.1单源最短路径264
7.5.2顶点对间最短路径270
7.6有向无环网及应用271
7.6.1拓扑排序271
7.6.2关键路径276
本章小结287
第8章查找289
8.0本章项目引例:电话号码查询系统289
8.1数据查找289
8.2基于线性表查找291
8.2.1顺序查找291
8.2.2二分查找293
8.3基于二叉树查找298
8.3.1二叉查找树概念299
8.3.2基于二叉查找树的查找300
8.3.3二叉查找树插入与生成算法302
8.3.4二叉查找树删除305
8.4基于散列表查找309
8.4.1常用散列函数构建309
8.4.2散列冲突处理311
本章小结316
第9章排序318
9.0本章项目引例:学生成绩排序318
9.1数据排序318
9.1.1排序基本概念318
9.1.2排序算法稳定性319
9.2插入排序320
9.2.1直接插入排序320
9.2.2二分插入排序326
9.2.3Shell排序329
9.3交换排序331
9.3.1冒泡排序331
9.3.2快速排序334
9.4选择排序339
9.4.1直接选择排序339
9.4.2堆排序342
9.5归并排序349
9.6外排序354
9.6.1外排序基本步骤354
9.6.2败者树k路归并算法355
9.6.3k路归并算法实现357
本章小结360
参考文献365
本教材根据《数据结构与算法(C&C#语言描述)》教材中的每个章节的与实际生活结合密切的项目实例,分别使用C和C#语言进行具体分析与实现。本教材依据数据结构课程教学大纲要求,既重视实践应用,又重视理论分析,本教材的主要特点有:
突出主线,从整体上理解相关内容数据逻辑结构是本课程主线,课程所有内容都围绕其展开。既然是主线,就可以在各个层面上都有所体现。在教材开首“绪论”中提出“集合—线性表—树型—图”的基本逻辑结构线索,同时在讲授其后各章具体内容中也不断展开螺旋式上推强化。
强调实例,从具体中把握抽象原理数据结构课程中不少概念和算法都比较抽象,如树和二叉树的递归定义、模式匹配的KMP算法、平衡树算法等。本教材努力做到在保持科学性和逻辑性前提之下,凡是重要的概念、原理和算法都配有相应的直观图解,而难度较高的部分其相应图示都尽量详尽细微。实践证明,这样做教师会感觉“好讲”,同学们会表示“易学”。
注重关联,从逻辑网络中建构知识 数据结构课程涉及概念和算法众多,初看起来似乎内容庞杂。实际上,作为一门经典课程,经过无数专家们的千锤百炼,早已成为一个逻辑脉络清晰与彼此精密套接的科学体系,关键是在教和学的过程当中实时进行把握和梳理,并不断加以强调和体现。各个知识点只有放在整体体系合适的部位才能彰显其意义和作用,才能具有“鲜活”机体部件的价值。
突出细节,由精微处体现关键 课程中许多“细节”是理解和掌握相应问题的关键所在,在理清整体脉络框架的前提之下,讲清有关“精微细节”,不仅可以有效深刻地掌握相应概念算法,同时也可以使得略显“枯燥”的课程能不时闪现出自己特有的魅力,激发学习者的学习热情。
所有实例项目都给出了参考算法和源程序代码并在Visual C++6.0和Visual Stdio 2010及以上环境下运行通过。
教材由广州工程技术职业学院的吴明珠组织统筹,其中第1、2章和第9章由吴明珠编写;第3章和第8章由陈瑛编写;第4章由柴梦竹编写;第5章由卢莉编写;第6章由单家凌编写;第7章由蔡雪莲编写。
由于作者水平有限、时间仓促,教材中难免存在一些缺点,恳请广大读者及同行们批评指正。