高等学校教材·数据结构算法解析

《高等学校教材·数据结构算法解析》为严蔚敏、吴伟民编著的《数据结构(C语言版)》的学习辅导书。主要内容包括教科书中各主要数据存储结构执原吸方本使只考钱的基本操作函数、调用这些基本操作的主来自要程序和程序运行结果以及教科书中各主要数据存储结构的图示。

• 中文名 数据结构算法解析
• 定价 29.5元
• 出版社 清华大学出版社
• 作者 高一凡
• 出版时间 2013-5-29

图书前言

　　作者多年讲授"数据结构"课程,所用教材为清华大学占点止是示任特急业松路出版社出版,严蔚差件我门聚黑怕刑敏、吴伟民编著的《数据结构(C语言版)》(以下简称为教科书)。根据多年来自的授课经验,作者深知学习"数360百科据结构"的关键点:

　今判证收杆弦吃承读洋除　首先,要产生兴趣,兴趣是求知的动力。

　　其次,要加强形象思维训练,用形象为点林常封末蒸路官开思维帮助建立抽象思维。

　　最后,要使众范初告算法活起来,使算法不再是抽象的、枯燥的、孤立的杆陈真、晦涩的,而是具体的、生动的、互相有联系的、易于理解的。

　　本书是作者多年来潜心研究的成果,其中有许多独到之处:

　　一、 本书不仅种投拿感还结场包括教科书中绝大多数算法的实现,对于许多主要的存储结构,也包括了美状额参丰磁护它们的基本操作的实现致海磁胶技妈校减济车聚。这些基本操作构成了存储结构的完整体系,使得该存储结构可以直接使用在需要的地方。如在第7章的拓扑排序中就用到了第3章顺序栈抗孩赵数后更阶办的存储结构和基本操作。作者也经常直接将本书的存储结构和基本操作用在自己的科研课题程序中,效果都很好。读者如果急因蒸钱胞叶测需要了解少数教科书中提及而本书中未提及的算法径降被兴船目留病应帝、存储结构和基本操作,可以参考阅读本书后面的参考文献[3]。

　　二、 为了加强形象思维训练,作者绘制了各种数据存储结构、算法、程序对终运行过程的示意图,共计281幅(有些图本身又由一系列小图组成)。这些图清楚地说明了数据的存储结构和算法。

　　城分创三、 通过将算法编写到计算机可运行的程序中的方法,使算法活太美核还状科际玉起来。对于可运行的轻算法,输出变量、单步执行、设置断点、修改算法、抓呢也讲沉延首吃一尝试各种输入数据等都是轻而易举的,这些做法都有助于深刻地理解算尽太族落黑法。

　　四、 对于较难理解的算法都有详细的、图文并茂的解析,有些解析(如平衡二叉树)还包含作者自己的研究。较为简单的算法,也尽量利用程序中的空白处,多加注释。对于相应于教科书算法中须说明的新增行与修改行,在注释行中也分别注以"新增"与"修改"。

　　五、 本书第7章以后的许多程序中的数据来自文本格式的数据文件,避免了人工键盘输入的麻烦,也有利于掌握使用文件输入输出的方法(这是很多学生不熟悉,却又很重要的方法)。根据程序所用文件的格式,读者很容易编写出自己需要的数据文件。

　　六、 本书除了实现教科书中已有的算法,还实现了克鲁斯卡尔、2路插入排序(包括改进的2路插入排序)、树形选择排序等教科书中没有写出的算法。

　　七、 本书还包含了许多编程的技巧和小窍门,这些是作者多年编程所积累的经验。

　　有教科书和本书对算法和数据结构的详细讲解,又有可执行的程序,还有程序的运行结果,加上读者自己的思考和努力,还有什么学不会的呢?甚至会觉得,数据结构是简单的,又是有趣的,还是有用的。其中的许多算法是巧妙的、启迪心智的,徜徉其中,其乐无穷。

　　本书紧密配合教科书,故在章节编排上尽量与教科书保持一致,以便读者对照查找。教科书的第8章和第12章由于内容较为独立,并应用较少,故没有收进本书。因此,教科书的第9、10、11章在本书中相应地成为第8、9、10章。同样,教科书中有些节的内容没有收进本书,后面节的编号随之减小。但各章节的名称与教科书保持一致。

　　本书所有程序都在Borland C++ 3.1和Microsoft Visual C++ 6.0下运行通过。这些程序都可通过清华大学出版社的网站下载。

目录

　　第1章绪论

　　1.1抽象数据类型的表示与实现

　　1.2算法和算法分析

　　第2章线性表

　　2.1线性表的类型定义

　　2.2线性表的顺序表示和实现

　　2.3线性表的链式表示和实现

　　2.3.1线性链表

　　2.3.2循环链表

　　2.3.3双向链表

　　第3章栈和队列

　　3.1栈

　　3.2栈的应用举例

　　3.2.1数制转换

　　3.2.2行编辑程序

　　3.2.3迷宫求解

　　3.2.4表达式求值

　　3.3栈与递归的实现

　　3.4队列

　　3.4.1链队列--队列的链式表示和实现

　　3.4.2循环队列--队列的顺序表示和实现

　　第4章串

　　4.1串类型的定义

　　4.2串的表示和实现

　　4.2.1定长顺序存储表示

　　4.2.2堆分配存储表示

　　4.3串的模式匹配算法

　　4.3.1求子串位置的定位函数Index(S,T,pos)

　　4.3.2模式匹配的一种改进算法

　　第5章数组和广义表

　　5.1数组的顺序表示和实现

　　5.2矩阵的压缩存储

　　5.3广义表的定义

　　5.4广义表的存储结构

　　5.5广义表的递归算法

　　第6章树和二叉树

　　6.1二叉树

　　6.2遍历二叉树和线索二叉树

　　6.2.1遍历二叉树

　　6.2.2线索二叉树

　　6.3树和森林

　　6.4赫夫曼树及其应用

　　6.4.1最优二叉树(赫夫曼树)

　　6.4.2赫夫曼编码

　　第7章图

　　7.1图的存储结构

　　7.1.1数组表示法

　　7.1.2邻接表

　　7.2图的遍历

　　7.2.1深度优先搜索

　　7.2.2广度优先搜索

　　7.3图的连通性问题

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

　　7.3.2最小生成树

　　7.3.3关节点和重连通分量

　　7.4有向无环图及其应用

　　7.4.1拓扑排序

　　7.4.2关键路径

　　7.5最短路径

　　7.5.1从某个源点到其余各顶点的最短路径

　　7.5.2每一对顶点之间的最短路径

　　第8章查找

　　8.1静态查找表

　　8.1.1顺序表的查找

　　8.1.2有序表的查找

　　8.1.3静态树表的查找

　　8.2动态查找表

　　8.2.1二叉排序树和平衡二叉树

　　8.2.2B_树和B+树

　　8.2.3键树

　　8.3哈希表

　　8.3.1处理冲突的方法

　　8.3.2哈希表的查找及其分析

　　第9章内部排序

　　9.1概述

　　9.2插入排序

　　9.2.1直接插入排序

　　9.2.2其他插入排序

　　9.2.3希尔排序

　　9.3快速排序

　　9.4选择排序

　　9.5归并排序

　　9.6基数排序

　　9.7各种内部排序方法的比较讨论

　　第10章外部排序

　　10.1外部排序的方法

　　10.2多路平衡归并的实现

　　10.3置换选择排序

　　附录A关于标准C程序

　　参考文献