数据结构

目录 1绪论(1) 1.1概述(1) 1.1.1什么是数据结构(1) 1.1.2学习数据结构的意义(3) 1.2基本概念和术语(4) 1.2.1数据与数据元素(4) 1.2.2数据的逻辑结构(4) 1.2.3数据的存储结构(5) 1.2.4数据运算(6) 1.2.5数据类型(6) 1.2.6抽象数据类型(7) 1.3算法和算法描述语言(8) 1.3.1算法的书写格式(9) 1.3.2算法中的语句(9) 1.3.3常量、变量说明方式和数据类型标识符(12) 1.3.4运算符号约定(13) 1.4算法分析(13) 思考题与习题(17) 2线性表(19) 2.1线性表的定义和运算(19) 2.1.1线性表的定义(19) 2.1.2线性表的运算(20) 2.2线性表的顺序存储(21) 2.2.1顺序表(21) 2.2.2基本运算在顺序表上的实现(22) 2.2.3顺序表的应用实例(26) 2.3线性表的链式存储(27) 2.3.1单链表(27) 2.3.2循环链表(38) 2.3.3双链表(40) 2.4线性表存储结构的讨论(42) 2.4.1线性表顺序存储与链接存储的比较(42) 2.4.2线性表存储空间的静态分配与动态分配(43) 2.5线性表的应用举例(45) 思考题与习题(48) 3栈和队列(50) 3.1栈(50) 3.1.1栈的定义和运算(50) 3.1.2栈的顺序存储(51) 3.1.3栈的链表存储(55) 3.1.4栈的应用(57) 3.2队列(63) 3.2.1队列的定义和运算(63) 3.2.2队列的链表存储(64) 3.2.3顺序队列(67) 3.2.4队列应用举例(71) 3.3栈的应用——栈和递归(72) 3.3.1递归程序的实现(73) 3.3.2递归程序设计(80) 思考题与习题(84) 4串(86) 4.1串的定义和运算(86) 4.1.1串的定义(86) 4.1.2串的运算(87) 4.2串的存储(89) 4.2.1串值的存储(89) 4.2.2符号表(92) 4.3模式匹配(95) 4.3.1强行搜索算法(95) 4.3.2kmp算法(97) 思考题与习题(102) 5数组和广义表(103) 5.1数组(103) 5.1.1数组的定义和运算(103) 5.1.2数组的顺序存储结构(104) 5.1.3特殊矩阵的压缩存储(110) 5.1.4稀疏矩阵的压缩存储(111) 5.2广义表(117) 5.2.1广义表的定义和运算(117) 5.2.2广义表的存储(119) *5.2.3广义表运算的实现(120) 思考题与习题(121) 6树(123) 6.1概述(123) 6.2二叉树(125) 6.2.1二叉树的有关概念(126) 6.2.2二叉树的性质(126) 6.2.3二叉树的存储结构(129) 6.3二叉树的遍历(130) 6.3.1遍历算法的实现(131) 6.3.2遍历算法的进一步讨论与应用(136) 6.3.3遍历算法思想的应用(137) 6.4线索二叉树(139) 6.4.1线索二叉树结构(140) 6.4.2线索二叉树中前驱后继的讨论(141) 6.4.3线索二叉树的插入(146) 6.4.4二叉树的线索化(149) 6.5树和森林(150) 6.5.1树的存储结构(150) 6.5.2树(森林)与二叉树的转换(154) 6.5.3树(森林)的遍历(155) 6.6哈夫曼树(158) 6.6.1问题描述及求解方法(159) 6.6.2应用实例(162) 思考题与习题(164) 7图(167) 7.1图的定义与术语(168) 7.1.1图的定义(168) 7.1.2图的基本术语(169) 7.1.3图的基本操作(170) 7.2图的存储表示(172) 7.2.1邻接矩阵表示法(172) 7.2.2邻接表表示法(173) 7.2.3邻接多重表表示法(176) 7.2.4十字链表表示法(177) 7.3图的遍历(179) 7.3.1深度优先遍历(180) 7.3.2广度优先遍历(182) 7.4最小生成树(184) 7.4.1最小生成树的概念(184) 7.4.2普里姆算法(185) 7.4.3克鲁斯卡尔算法(188) 7.5拓扑排序与关键路径(189) 7.5.1拓扑排序(190) 7.5.2关键路径(193) 7.6最短路径(199) 7.6.1从某个源点到其余各顶点的最短路径(199) 7.6.2所有顶点对之间的最短路径(203) 思考题与习题(207) 8排序(210) 8.1基本概念(210) 8.1.1什么是排序(210) 8.1.2排序的分类(211) 8.1.3基本操作(211) 8.1.4存储结构(212) 8.1.5内部排序的方法(212) 8.1.6稳定性(213) 8.2插入排序(213) 8.2.1直接插入排序(214) 8.2.2折半插入排序(217) 8.2.3希尔排序(218) 8.3交换排序(220) 8.3.1冒泡排序(220) 8.3.2快速排序(222) 8.4选择排序(229) 8.4.1直接选择排序(229) 8.4.2堆排序(230) 8.5归并排序(235) 8.5.1方法描述(235) 8.5.2排序算法(236) 8.5.3算法分析(238) 8.6基数排序(238) 8.6.1概述(238) 8.6.2从高到低的排序(239) 8.6.3从低到高的排序(240) 8.7几种排序方法的比较(242) 8.7.1时间复杂度(243) 8.7.2空间复杂度(243) 8.7.3稳定性(244) 8.7.4关于“排序方法的时间复杂度的下限”(244) 8.7.5实例(245) 8.8外部排序简介(247) 思考题与习题(249) 9查找(250) 9.1基本概念(250) 9.2顺序表的查找(252) 9.2.1简单顺序表的查找(253) 9.2.2折半查找(254) 9.2.3索引顺序表的查找(257) 9.3树表的查找(258) 9.3.1二叉排序树(259) 9.3.2平衡二叉树(261) 9.3.3b树和b+树(265) 9.4散列表(271) 9.4.1散列表(272) 9.4.2散列函数的构造方法(273) 9.4.3冲突及其解决方法(276) 9.4.4散列表的查找及其分析(278) 思考题与习题(281) 10文件简介(282) 10.1文件的基本概念(282) 10.1.1文件的分类(282) 10.1.2文件的逻辑结构(283) 10.1.3文件的物理结构(283) 10.1.4文件的操作(283) 10.2顺序文件(284) 10.3索引文件(285) 10.4isam文件和vsam文件(286) 10.4.1isam文件(286) 10.4.2vsam文件(286) 10.5散列文件(287) 10.6多关键字文件(288) 10.6.1多重表文件(288) 10.6.2倒排文件(290) 思考题与习题(291) 参考文献(293)