第1章 绪 论（1）
1.1 数据结构（1）
1.1.1 基本概念和术语（1）
1.1.2 数据结构的定义（2）
1.2 算法（5）
1.2.1 算法的概念及描述（5）
1.2.2 算法的性能分析（6）
习 题（9）
第2章 线性表（12）
2.1 线性表的定义及基本操作（12）
2.1.1 线性表的定义（12）
2.1.2 线性表的基本操作（13）
2.2 线性表的顺序存储结构（13）
2.2.1 线性表的顺序存储结构———顺序表（13）
2.2.2 顺序存储结构的特点（14）
2.2.3 顺序表的基本操作（15）
2.2.4 顺序表的应用举例（17）
2.3 线性表的链式存储结构（19）
2.3.1 线性表的链式存储结构———链表（19）
2.3.2 单链表的基本操作（21）
2.3.3 双向链表（24）
2.3.4 循环链表（27）
2.3.5 单链表的应用举例（28）
2.3.6 链式存储结构的特点（32）
2.4 数组（33）
2.4.1 数组的定义（33）
2.4.2 数组的顺序表示和实现（33）
2.5 稀疏矩阵（35）
2.5.1 稀疏矩阵的定义（35）
2.5.2 稀疏矩阵的顺序存储（35）
2.5.3 稀疏矩阵的链式存储（38）
习 题（40）
第3章 栈和队列（42）
3.1 栈（42）
ⅰ 3.1.1 栈的定义和基本操作（42）
3.1.2 栈的顺序存储结构（43）
3.1.3 栈的链式存储结构（45）
3.1.4 递归（47）
3.2 队列（50）
3.2.1 队列的定义及基本操作（50）
3.2.2 队列的顺序存储（50）
3.2.3 队列的链式存储（57）
3.3 栈和队列操作应用举例（62）
3.3.1 栈的应用（62）
3.3.2 队列的应用（65）
习 题（68）
第4章 串（69）
4.1 串的定义及基本操作（69）
4.2 串的存储结构（70）
4.2.1 串的静态存储（71）
4.2.2 串的动态存储（72）
4.2.3 串的基本操作的实现（73）
习 题（77）
第5章 树和二叉树（78）
5.1 树的基本概念（78）
5.1.1 树的定义（78）
5.1.2 树的逻辑表示（79）
5.1.3 树的基本术语（80）
5.2 树的存储结构和基本操作（81）
5.2.1 树的存储结构（81）
5.2.2 树的基本操作（84）
5.3 二叉树的基本概念和基本性质（85）
5.3.1 二叉树的定义（85）
5.3.2 二叉树的基本性质（86）
5.4 二叉树的存储结构和基本操作（87）
5.4.1 顺序存储结构（87）
5.4.2 链式存储结构（88）
5.4.3 基本操作（90）
5.5 二叉树的遍历（91）
5.5.1 前序遍历（91）
5.5.2 中序遍历（92）
5.5.3 后序遍历（92）
5.5.4 层次遍历（93）
5.6 树和森林与二叉树之间的关系（94）
5.6.1 树转换成二叉树（94）
5.6.2 森林转换成二叉树（94）
5.6.3 二叉树转换成森林（95）
5.6.4 树与二叉树之间的存储结构转换关系（96）
5.7 哈夫曼树及其应用（97）
5.7.1 基本概念（97）
5.7.2 哈夫曼树（最优二叉树）（98）
5.7.3 哈夫曼编码（99）
5.7.4 哈夫曼（Huffman）算法（101）
5.8 二叉排序树（103）
5.8.1 二叉排序树定义（103）
5.8.2 二叉排序树上的操作（103）
5.8.3 性能分析（107）
习 题（108）
第6章 图（110）
6.1 图的基本概念（110）
6.1.1 图的定义（110）
6.1.2 图的基本术语（111）
6.2 图的存储结构（114）
6.2.1 邻接矩阵（114）
6.2.2 邻接表（116）
6.3 图的遍历（119）
6.3.1 深度优先搜索（119）
6.3.2 广度优先搜索（121）
6.4 连通网的最小生成树（123）
6.4.1 生成树及最小生成树的相关概念（123）
6.4.2 最小生成树的构造方法（123）
6.4.3 普里姆（Prim）算法（123）
6.4.4 克鲁斯卡尔（Kruskal）算法（126）
6.5 最短路径（127）
6.6 拓扑排序（129）
习 题（132）
第7章 查 找（135）
7.1 查找的基本概念（135）
7.2 顺序查找（136）
7.2.1 顺序存储的顺序查找（137）
7.2.2 链式存储的顺序查找（137）
7.3 折半查找（138）
7.4 哈希（Hash）表查找（141）
7.4.1 什么是哈希表查找（141）
7.4.2 哈希函数的构造方法（142）
7.4.3 处理冲突的方法（143）
习 题（146）
第8章 排 序（148）
8.1 排序的基本概念（148）
8.2 插入排序（150）
8.2.1 直接插入排序（150）
8.2.2 希尔排序（152）
8.3 选择排序（154）
8.3.1 直接选择排序（154）
8.3.2 堆排序（155）
8.4 交换排序（159）
8.4.1 冒泡排序（159）
8.4.2 快速排序（161）
8.5 归并排序（163）
8.6 基数排序（166）
8.7 常用排序方法的比较（166）
8.7.1 常用排序方法的比较（166）
8.7.2 排序方法的选择（167）
习 题（167）
附录一（169）
实验一 一元多项式的乘法运算（169）
实验二 栈的应用———表达式的求值（174）
实验三 简单的串的模式匹配算法（181）
实验四 二叉树的遍历（182）
实验五 图的应用（187）
实验六 分块查找（189）
实验七 内部排序算法比较（191）
附录二 部分习题参考答案（193）
附录三 历年计算机水平与资格考试的数据结构试题（204）
数据结构是计算机专业的一门专业基础课，也是一门核心课程，在计算机专业课程中起着承前启后的作用，数据结构为操作系统、编译原理、数据库系统、计算机图形学、人工智能等后续课程奠定基础。本书分为8章：第1章为绪论，讨论数据结构和算法的基本概念，以及时间复杂度的估算方法；第2章为线性表，讨论线性表的逻辑结构、线性表的顺序存储结构和链式存储结构、数组和稀疏矩阵的存储结构及其基本操作的实现；第3章为栈和队列，讨论栈和队列的特点及其各种存储结构与基本操作的实现，并给出了相应的应用实例；第4章为串，讨论串的各种存储结构及其基本操作的实现；第5章为树和二叉树，讨论树和二叉树的定义、性质、表示、存储结构以及二叉树的基本操作，讨论哈夫曼树的基本概念及其应用，讨论二叉排序树的概念及基本操作；第6章为图，讨论图的各种存储结构和遍历的实现；第7章为线性表的查找，讨论各种常用的查找方法及其实现；第8章为排序，讨论各种排序方法及其实现。本书有3个附录，附录一提供了7个实验，附录二给出了各章习题的部分参考答案，附录三提供了历年计算机水平与资格考试的数据结构试题及参考答案。本书所有的数据结构和算法都采用 C语言描述，全部算法都通过了上机调试。对附录一的每个实验都给出了用C语言编写的源程序。对习题中较复杂的算法在附录二中给出了用C语言编写的源程序。本书在内容的选取、概念的引入、文字的叙述以及例题、习题和实验的选择等方面充分考虑了目前高职高专学生的知识结构、能力结构和素质结构，较好地落实了教育部《关于加强高职高专教育教材建设的若干意见》和《高职高专教育专业人才培养目标及规格》等文件精神，编写时力求做到由浅入深、深入浅出和循序渐进，突出其实用性和应用性，注重培养读者分析问题和解决问题的能力。本书为高职高专计算机专业教材，也可作为计算机专业的成人教育、自学考试和各类培训班的教材，对从事计算机应用的工程技术人员也是一本十分有价值的参考书。本书由余绍军任主编，刘佳、陈畅任副主编，其中第1、2章由余绍军编写，第3、4章由刘佳编写，第5章由陈文辉编写，第6章由姜瑜编写，第7、8章由陈畅编写，刘佳对第1～8章中的所有算法进行了统稿，陈畅对各章的习题及附录进行了统稿，全书由余绍军统稿、修改和定稿，姜瑜、陈文辉参加了部分内容的统稿和修改。由于编者水平有限，书中难免有错误或不当之处，恳请专家和广大读者批评指正。
编 者
2004年7月
公安网备 43010402000836 湘ICP备09001153号 新出网证(湘)字005号