数据结构教程

书籍目录

第1章  绪论1．1什么是数据结构1．2数据结构的发展简史及其在计算机科学中的地位1．3算法1．3．1算法及其性质1．3．2基本算法1．3．3算法的描述1．4算法分析1．4．1时间复杂度1．4．2空间复杂度1．4．3其他方面习题第2章  线性表2．1线性表的定义及其基本操作2．1．1线性表的定义2．1．2线性表的基本操作2．2线性表的顺序存储结构2．2．1顺序存储结构的构造2．2．2几种常见操作的实现2．2．3顺序存储结构小结2．3线性链表及其操作2．3．1线性链表的构造2．3．2线性链表的基本算法2．4循环链表及其操作2．5双向链表及其操作2．5．1双向链表的构造2．5．2双向链表的插入与删除算法2．6链表的应用举例2．6．1链式存储结构下的一元多项式相加2．6．2打印文本文件的最后n行习题第3章  数组3．1数组的概念3．2数组的存储结构3．3矩阵的压缩存储3．3．1对称矩阵的压缩存储3．3．2对角矩阵的压缩存储3．4稀疏矩阵的三元组表表示3．4．1稀疏矩阵的三元组表存储方法3．4．2稀疏矩阵的转置算法3．4．3稀疏矩阵的相加算法3．4．4稀疏矩阵的相乘算法3．5稀疏矩阵的链表表示3．5．1线性链表存储方法3．5．2带行指针向量的链表存储方法3．5．3十字链表存储方法3．6数组的应用举例3．6．1一元多项式的数组表示3．6．2n阶魔方习题第4章  堆栈和队列4．1堆栈的概念及其操作4．1．1堆栈的定义4．1．2堆栈的基本操作4．2堆栈的顺序存储结构4．2．1顺序堆栈的构造4．2．2顺序堆栈的基本算法4．2．3多个堆栈共享连续空间4．3堆栈的链式存储结构4．3．1链接堆栈的构造4．3．2链接堆栈的基本算法4．4堆栈的应用举例4．4．1符号匹配检查4．4．2数制转换4．4．3堆栈在递归中的应用4．4．4表达式的计算4．4．5又一个趣味游戏——迷宫4．5队列的概念及其操作4．5．1队列的定义4．5．2队列的基本操作4．6队列的顺序存储结构4．6．1顺序队列的构造4．6．2顺序队列的基本算法4．6．3循环队列4．7队列的链式存储结构4．7．1链接队列的构造4．7．2链接队列的基本算法习题第5章  广义表5．1广义表的基本概念5．2广义表的存储结构5．3多元多项式的表示习题第6章  串6．1串的基本概念6．1．1串的定义6．1．2串的几个概念6．2串的基本操作6．3串的存储结构6．3．1串的顺序存储结构6．3．2串的链式存储结构6．4串的几个操作-习题第7章  树与二叉树7．1树的基本概念7．1．1树的定义7．1．2树的逻辑表示方法7．1．3基本术语7．1．4树的性质7．1．5树的基本操作7．2树的存储结构7．2．1多重链表表示法7．2．2三重链表表示法7．3二叉树7．3．1二叉树的定义7．3．2二叉树的基本操作7．3．3两种特殊形态的二叉树7．3．4二叉树的性质7．3．5二叉树与树、树林之间的转换7．4二叉树的存储结构7．4．1二叉树的顺序存储结构7．4．2二叉树的链式存储结构7．5二叉树与树的遍历7．5．1二叉树的遍历7．5．2由遍历序列恢复二叉树7．5．3二叉树的等价性7．5．4树和树林的遍历7．5．5基于二叉树遍历操作的算法举例7．6线索二叉树7．6．1线索二叉树的构造7．6．2线索二叉树的利用7．6．3期工程二叉树的线索化7．6．4线索二叉树的更新7．7二叉排序树7．7．1二叉排序树的定义7．7．2二叉排序树的建立7．7．3在二X排序树中删除结点7．7．4二叉排序树的查找7．8平衡二叉树7．9哈夫曼树及其应用7．9．1哈夫曼树的概念7．9．2哈夫曼编码习题第8章  图8．1图的基本概念8．1．1图的定义和基本术语8．1．2图的基本操作8．2图的存储方法8．2．1邻接矩阵存储方法8．2．2邻接表存储方法8．2．3有向图的十字链表存储方法8．2．4无向图的多重邻接表存储方法8．3图的遍历8．3．1深度优先搜索8．3．2广度优先搜索8．3．3连通分量8．4最小生成树8．4．1普里姆算法8．4．2克鲁斯卡尔算法8．5最短路径8．6．AOV网与拓扑排序8．6．1AOV网8．6．2拓扑排序8．6．3拓扑排序算法8．7AOE网与关键路径8．7．1AOE网8．7．2关键路径8．7．3关键路径的确定习题第9章  文件及查找9．1文件概述9．1．1文件的基本概念9．1．2文件的存储介质9．1．3文件的基本操作9．2顺序文件9．2．1连续顺序文件及其查找9．2．2链接顺序文件及其查找9．3索引文件9．3．1稠密索引文件9．3．2非稠密索引分块文件9．3．3多级索引文件9．4B-树和B+树9．4．1B-树的基本概念9．4．2B-树的基本操作9．4．3B+树的基本概念9．4．4B+树的基本操作9．5散列(hash)文件9．5．1概述9．5．2散列函数的几种常见构造方法9．5．3处理冲突的方法9．5．4散列文件的操作9．5．5散列法的平均查找长度习题第10章  内排序10．1概述10．1．1排序的基本概念10．1．2排序的分类10．2插入排序10．3选择排序10．4泡排序10．5谢尔排序10．6快速排序10．7堆积排序10．7．1堆积的定义10．7．2堆积排序算法10．8二路归并排序10．8．1归并子算法10．8．2一趟归并扫描子算法10．8．3二路归并排序算法10．9基数排序10．10各种内排序方法的比较10．10．1稳定性比较10．10．2复杂性比较习题第11章  外排序11．1概述11．2磁带排序11．2．1多路平衡归并排序法11．2．2多步归并排序11．3初始归并段的合理分布与产生11．3．1初始归并段的合理分布11．3．2一种产生初始归并段的方法——置换选择排序11．4磁盘排序习题附录  上机实践题习题答案参考文献

作者简介

《数据结构教程》（第二版）是1996年出版的第一版的修订版。修订版在保持第一版基本框架和特色的基础上，对其中的内容做了大量的增删和修改，书中所有算法采用C语言描述。

　　书中讨论了包括线性表、堆栈、队列、树和图在内的各种数据结构和数据文件的基本概念、逻辑结构与存储结构，以及在这些结构的基础上所实施的相关操作。全书仍分为11章。每一章在增加了大量例题解析的同时，还配有丰富的、各种类型的习题，并且提供了体现各章基本内容的上机实践题。

　　本书可以作为高等院校计算机专业本科学生的教材，也可以作为报考高等学校计算机专业硕士研究生入学考试的复习用书，同时还可以作为从事计算机系统软件和应用软件设计与开发人员的参考资料。

图书封面

 数据结构教程下载