数据结构(C语言版)

    《数据结构》（C语言版）是为“数据结构”课程编写的教材，也可作为学习数据结构及其算法的C程序设计参考教材。 本书的前半部分从抽象数据类型的角度讨论各种基本类型的数据结构及其应用；后半部分主要讨论查找和排序的各种实现方法及其综合分析比较。其内容和章节编排与1992年4月出版的《数据结构》（第二版）基本一致，但在本书中更突出了抽象数据类型的概念。全书采用类C语言作为数据结构和算法的描述语言。 本书概念表述严谨，逻辑推理严密，语言精炼，用词达意。并有配套出版的《数据结构题集》（C语言版）。既便于教学，又便于自学。 本书可作为计算机类专业或信息类相关专业的本科或专科教材，也可供从事计算机工程与应用工作的科技工作者参考。

    本书的前半部分从抽象数据类型的角度讨论各种基本类型的数据结构及其应用；后半部分主要讨论查找和排序的各种实现方法及其综合分析比较。其内容和章节编排与1992年4月出版的《数据结构》（第二版）基本一致，但在本书中更突出了抽象数据类型的概念。

    

第1章　结论br>br>1.1　什么是数据结构br>1.2　基本概念br>1.3　抽象数据类型的表示与实现br>1.4　算法和算法分析br>1.4.1　算法br>1.4.2　算法设计的要求br>1.4.3　算法效率的度量br>1.4.4　算法的存储空间需求br>br>第2章　线性表br>br>2.1　线性表的类型定义br>2.2　线性表的顺序表示和实现br>2.3　线性表的链式表示和实现br>2.3.1　线性链表br>2.3.2　循环链表br>2.3.3　双向链表br>2.4　一元多项式的表示及相加br>br>第3章　栈和队列br>br>3.1　栈br>3.1.1　抽象数据类型栈的定义br>3.1.2　栈的表示和实现br>3.2　栈的应用举例br>3.2.1　数制转换br>3.2.2　括号匹配的检验br>3.2.3　行编辑程序br>3.2.4　迷宫求解br>3.2.5　表达式求值br>3.3　栈与递归的实现br>3.4　队列br>3.4.1　抽象数据类型队列的定义br>3.4.2　链队列——队列的链式表示和实现br>3.4.3　循环队列——队列的顺序表示和实现br>3.5　离散事件模拟br>br>第4章　串br>br>4.1　串类型的定义br>4.2　串的表示和实现br>4.2.1　定长顺序存储表示br>4.2.2　堆分配存储表示br>4.2.3　串的模式匹配算法br>4.3　串的模式匹配算法br>4.3.1　求子串位置的定位函数Indexbr>4.3.2　模式匹配的一种改进算法br>4.4　串操作应用举例br>4.4.1　文本编辑br>4.4.2　建立词索引表br>br>第5章　数组和广义表br>br>5.1　数组的定义br>5.2　数组的顺序表示和实现br>5.3　矩阵的压缩存储br>5.3.1　特殊矩阵br>5.3.2稀疏矩阵br>5.4　广义表的定义br>5.5　广义表的存储结构br>5.6　m元多项式的表示br>5.7　广义表的递归算法br>5.7.1　求广义表br>5.7.2  复制广义表br>5.7.3　建立广义表的存储结构br>br>第6章　树和叉树br>br>6.1　树的定义和基本术语br>6.2　二叉树br>6.2.1　二叉树的定义br>6.2.2　二叉树的性质br>6.2.3　二叉树的存储结构br>6.3　遍历二叉树和线索二叉树br>6.3.1　遍历二叉树br>6.3.2　线索二叉树br>6.4　树和森林br>6.4.1　树的存储结构br>6.4.2　森林与二叉树的转换br>6.4.3　树和森林的遍历br>6.5　树与等价问题br>6.6　赫夫曼树及其应用br>6.6.1　最优二叉树br>6.6.2　赫夫曼编码br>6.7　回溯法与树的遍楞br>6.8　树的计数br>br>第7章　图br>br>7.1　图的定义和术语br>7.2　图的存储结构　br>7.2.1　数组表示法　br>7.2.2　邻接表br>7.2.3　十字链表br>7.2.4　邻接多重表br>7.3　图的遍历br>7.3.1　深度优先搜索br>7.3.2　广度优先搜索br>7.4　图的连通性问题br>7.4.1　无向图的连通分量和生成树br>7.4.2　有向图的强连通分量br>7.4.3　最小生成树br>7.4.4　关节点和重连通分量br>7.5　有向无环图及其应用br>7.5.1　拓朴排序br>7.5.2　关键路径br>7.6　最短路径br>7.6.1　从某个源点到其余各顶点的最短路径br>7.6.2　每一对顶之间的最短路径br>br>第8章　动态存储管理br>br>8.1　概述br>8.2　可利用空间表及分配方法br>8.3　边界标识法br>8.3.1　可利用空间表的结构br>8.3.2　分配算法br>8.3.3　回收算法br>8.4　伙伴系统br>8.4.1　可利用空间表的结构br>8.4.2　分配算法br>8.4.3　回收算法br>8.5　无用单元收集br>8.6　存储紧缩br>br>第9章　查找br>br>9.1　静态表的查找br>9.1.1　有序表的查找br>9.1.2　静态树表的查找br>9.1.3　静态树表的查找br>9.1.4　索引顺序表的查找br>9.2　动态查找表br>9.2.1　二叉排序树和平衡二叉树br>9.2.2　B_树和B+树br>9.2.3　键树br>9.3　哈希表br>9.3.1　什么是哈希表br>9.3.2　哈希函数的构造方法br>9.3.3　处理冲突的方法br>9.3.4　哈希表的查找及其分析br>br>第10章　内部排序br>br>10.1　概述br>10.2　插入排序br>10.2.1　直接插入排序br>10.2.2　其它插入排序br>10.2.3　希尔排序br>10.3　快速排序br>10.4　选择排序br>10.4.1　简单选择排序br>10.4.2　树形选择排序br>10.4.3　堆排序br>10.5　归并排序br>10.6　基数排序br>10.6.1　多关键字的排序br>10.6.2　链式基数排序br>10.7　各种内部排序方法的比较讨论br>br>第11章　外部排序br>br>11.1　外存信息的存取br>11.2　外部排序的方法br>11.3　多路平衡归并的实现br>11.4　置换-选择排序br>11.5　最佳归并树br>br>第12章　文件br>br>12.1　有关文件的基本概念br>12.2　顺序文件br>12.3　索引文件br>12.4　ISAM文件和VSAMbr>12.4.1　ISAM文件br>12.4.2　VSAM文件br>12.5　直接存取文件br>12.6　多关键字文件br>12.6.1　多重表文件br>12.6.2　倒排文件br>br>附录A　名词索引br>附录B　函数索引br>参考书目<