数据结构（C语言版）（第2版）

　　本书是《数据结构（C语言版）》的第2版，对常用的数据结构做了系统的介绍，力求概念清晰，注重实际应用。主要内容包括：数据结构的基本概念，算法描述和算法分析初步，线性表、链表、栈、队列、串、广义表、树、图等结构，查找和排序的各种方法，另外还用一章的篇幅详细介绍了链式存储结构以加深读者的理解。每章均列举了典型应用实例，并配有算法和程序以供教学和实践使用。

目 录
第1章 绪论
1.1 什么是数据结构
1.1.1 数据结构的起源
1.1.2 数据结构研究的内容
1.1.3 学习数据结构的必要性
1.1.4 如何学好数据结构
1.2 数据的逻辑结构
1.2.1 基本概念
1.2.2 逻辑结构的描述
1.3 数据的存储结构
1.4 算法和算法效率分析
1.4.1 算法
1.4.2 影响算法效率的因素
1.4.3 算法效率的评价
上机实训
习题
第2章 线性表
2.1 内存静态分配
2.2 线性表的定义与基本操作
2.2.1 线性表的定义
2.2.2 线性表的基本操作
2.3 线性表的顺序存储结构
2.3.1 顺序表
2.3.2 顺序表上基本运算的实现
2.4 应用举例及分析
上机实训
习题
第3章 链表
3.1 内存动态分配
3.1.1 函数malloc()
3.1.2 函数free()
3.2 线性表的链式存储
3.2.1 线性链表
3.2.2 单链表上的基本运算
3.2.3 循环链表
3.2.4 双向链表
3.3 顺序表和链表的比较
3.4 应用举例及分析
上机实训
习题
第4章 栈和队列
4.1 栈
4.1.1 栈的定义及基本操作
4.1.2 栈的顺序存储结构
4.1.3 栈的链式存储结构
4.2 队列
4.2.1 队列的定义及基本操作
4.2.2 队列的顺序存储结构
4.2.3 队列的链式存储结构
4.3 应用举例及分析
上机实训
习题
第5章 串和广义表
5.1 串的定义和基本运算
5.1.1 串的定义
5.1.2 串的基本运算
5.2 串的表示和实现
5.2.1 定长顺序存储
5.2.2 链式存储
5.2.3 堆分配存储
5.3 串基本运算的实现
5.4 广义表
5.4.1 广义表的定义和性质
5.4.2 广义表的存储
5.5 应用举例及分析
上机实训
习题
第6章 树和二叉树
6.1 树
6.1.1 树的定义
6.1.2 树的基本术语
6.1.3 树的存储
6.2 二叉树
6.2.1 二叉树的定义
6.2.2 二叉树的性质
6.2.3 二叉树的存储
6.2.4 二叉树的建立
6.3 遍历和恢复二叉树
6.3.1 遍历二叉树
6.3.2 恢复二叉树
6.4 树、森林与二叉树的转换
6.4.1 一般树转换为二叉树
6.4.2 森林转换为二叉树
6.4.3 二叉树转换为树和森林
6.5 二叉树的应用举例
6.6 哈夫曼树及其应用
6.6.1 哈夫曼树的引入
6.6.2 哈夫曼树的建立
6.6.3 哈夫曼编码
上机实训
习题
第7章 图
7.1 图的定义和术语
7.1.1 图的定义
7.1.2 图的相关术语
7.1.3 图的基本操作
7.2 图的存储表示
7.2.1 邻接矩阵
7.2.2 邻接表
7.2.3 边集数组
7.3 图的遍历
7.3.1 深度优先搜索
7.3.2 广度优先搜索
7.4 生成树和小生成树
7.4.1 生成树和生成森林
7.4.2 小生成树
7.4.3 普里姆算法
7.4.4 克鲁斯卡尔算法
7.5 单源短路径
7.5.1 单源短路径的概念
7.5.2 求单源短路径的方法
7.6 AOV网与拓扑排序、拓扑排序的实现
7.6.1 AOV网与拓扑排序
7.6.2 拓扑排序的实现
7.7 AOE网与关键路径、关键路径的确定
7.7.1 AOE网与关键路径
7.7.2 关键路径的确定
上机实训
习题
第8章 查找
8.1 查找的基本概念
8.2 静态查找表
8.2.1 顺序查找
8.2.2 二分查找
8.2.3 索引顺序查找
8.3 动态查找表
8.3.1 二叉排序树定义
8.3.2 二叉排序树的插入和生成
8.3.3 二叉排序树的删除
8.3.4 二叉排序树上的查找
8.4 散列表
8.4.1 散列表与散列函数
8.4.2 散列函数的构造方法
8.4.3 处理冲突的方法
8.4.4 散列表的查找及分析
上机实训
习题
第9章 排序
9.1 基本概念
9.2 插入排序
9.2.1 直接插入排序
9.2.2 二分插入排序
9.2.3 希尔排序
9.3 交换排序
9.3.1 冒泡排序
9.3.2 快速排序
9.4 选择排序
9.4.1 简单选择排序
9.4.2 堆排序
9.5 归并排序
9.6 各种排序方法的比较
上机实训
习题
附录A 设计性上机实训
课程设计指导
课程设计参考题目
课程设计（实训）报告参考格式
参考文献

　　前 言
　　随着社会经济的高速发展，我国的高等教育已从精英教育走向大众化教育的发展阶段。国际高等教育的历史说明高等职业教育必将成为这一发展过程的主力军。对于我国这种从专科转型的高等职业教育，现今还处于探索阶段，教材建设是这一时期教育改革的重要方面。
　　高等职业教育是高等教育的一个新的类型，它与传统的普通高等教育既有紧密的联系，又有本质的区别。高等职业教育强调面向社会、生产、管理、服务线，培养技术应用型人才，学生毕业后，即可发挥其所学专长。所以，根据我国*的规定，高等职业教育需根据其自身的特点，建立自己的教材体系。
　　本教材第2版列入“21世纪计算机系列规划教材”，主要面向应用型本科及高等职业院校计算机类专业的学生，教材内容的构造力求体现“以应用为主体”，强调理论知识的理解和运用，实现高校应用型本科及高等职业教育教学以实践体系、技术应用能力培养为主的目标，符合现代高等职业教育对教材的需求。
　　“数据结构”是计算机程序设计的重要理论基础，是计算机及其应用专业的一门重要基础课程和核心课程。它不仅是学习后继软件专业课程的先导，而且已成为其他工科类专业的热门选修课程。
　　本书共9章。第1章阐述数据、数据结构和算法等基本概念。第2～7章分别讨论线性表、链表、栈、队列、串、广义表、树和二叉树以及图等基本数据结构及其应用，其中，第3章专门总结了链式存储结构的基本概念和应用，为学好后面的各类数据结构打好扎实的基础。第8～9章讨论查找和排序的各种实现方法和实用分析。
　　第2版教材进行了大量实用例子的补充和调整，对大量抽象、难懂的概念进行深入浅出的分析和讲解。将第1版教材中每章的实验子系统变更为验证性上机实训，并在附录里增加了设计性上机实训题供教师和学生在课程设计阶段选用。
　　长期以来，由于数据结构课程自身的抽象性和严密性，教师大都感觉数据结构课程难教，学生普遍反映数据结构课程难学，学生很难独立完成算法的实现。基于上述问题，我们在编写本教材时充分考虑了学生的知识结构和教师的教学方法。本教材的编写宗旨是，既注重原理又注重实践，既注重抽象思维又注重形象思维，既方便自学又方便教学。
　　本书的特点如下。
　　（1）对基础理论知识的阐述由浅入深、通俗易懂。内容组织和编排以应用为主线，略去了一些理论推导和数学证明的过程，淡化算法的设计分析和复杂的时空分析。
　　（2）各章都列举分析了很多实用的例子，这有助于学生加深对基础理论知识的理解和实际应用的能力培养。
　　（3）考虑到此课程的先导课程是“C语言程序设计”，书中算法均采用可在计算机上运行的C语言程序来描述。这样，降低了算法设计的难度，使学生能更直观形象地理解这些算法。鉴于微软对于VC++6.0早已停止维护升级，对于出现的不兼容问题已不再解决，本书提供的实现代码均在简单易用的Dev-C++平台上编译通过，并给出了所有程序的运行结果。若教师教学采用TC环境，只需在相应实现代码中加上相关头文件即可（Dev-C++平台安装包及使用说明书在教学资源包中下载）。
　　（4）为配合本书的教学，特编制了多媒体课件，对学生加深理解基本概念起到更直观的效果。本书配套的多媒体课件、书中所有算法及上机实训源代码和习题答案可在华信教育资源网（）下载，或通过E-mail向编者索取：。
　　（5）在教材中使用“▲思考”标志，提出问题拓展学生思维。在教学中可恰到好处地启发学生的思维。
　　（6）为避免C语言中数组的个元素的下标为0给学习和讲授带来的不便，本书在没有特别声明的地方均不使用C语言中数组下标为0 的元素。
　　本书由肖宏启整体构思、统稿和修改，在多位教师长期从事数据结构课程教学的经验基础上，经多次反复磋商和共同讨论定稿，是多位作者共同合作的产物。具体分工如下：第1、3、8、9章由贵州航天职业技术学院肖宏启编写；第2、4章由中国人民解放军国防大学陈锐编写；第6章由江西渝州科技职业学院廖银花编写；第7章及附录部分由重庆电子工程职业学院刘昌明编写；魏怀明副教授编写了第5章并详细审阅了全书；陈美成副教授、韦军博士审阅了该书并提供了许多宝贵的意见，陈元春副教授提供了本书的大部分习题。
　　本书编写过程中参考了许多作者的大量文献资料和国内外优秀教材，电子工业出版社对本书的出版给予了大力支持和帮助，作者谨此一并致以诚挚的谢意。
　　本教材讲课时数可为60～72学时，上机时数可灵活安排。教师可根据学时数、专业和学生的实际情况，选讲应用举例及分析中一些较难的例子。
　　由于编写教材的时间紧张，难免存在疏漏，敬请读者批评指正。
　　编 者
　　2013年8月