《数据结构》c语言版.doc

《数据结构》 第五版 清华大学自动化系 李宛洲 2004年5月 目录 第一章 数据结构--概念与基本类型 6 1.1概述 6 1.1.1数据结构应用对象 6 1.1.2学习数据结构的基础 7 1.1.2.1 C语言中的结构体 7 1.1.2.2 C语言的指针在数据结构中的关联作用 8 1.1.2.3 C语言的共用体(union)数据类型 12 1.1.3数据结构定义 15 1.2 线性表 17 1.2.1 顺序表 18 1.2.2 链表 20 1.2.2.1链表的基本结构及概念 20 1.2.2.2单链表设计 22 1.2.2.3单链表操作效率 29 1.2.2.4双链表设计 30 1.2.2.5链表深入学习 32 1.2.2.6稀疏矩阵的三元组与十字链表 36 1.2.3 堆栈 41 1.2.3.1堆栈结构 41 1.2.3.2基本操作 42 1.2.3.3堆栈与递归 44 1.2.3.4递归与分治算法 46 1.2.3.5递归与递推 50 1.2.3.6栈应用 53 1.2.4 队列 57 1.2.4.1队列结构 57 1.2.3.2队列应用 59 1.3 非线性数据结构--树 65 1.3.1 概念与术语 65 1.3.1.1引入非线性数据结构的目的 65 1.3.1.2树的定义与术语 66 1.3.1.3树的内部节点与叶子节点存储结构问题 67 1.3.2 二叉树 67 1.3.2.1二叉树基本概念 67 1.3.2.2完全二叉树的顺序存储结构 69 1.3.2.3二叉树遍历 70 1.3.2.4二叉树唯一性问题 72 1.3.3 二叉排序树 73 1.3.3.1基本概念 73 1.3.3.2程序设计 74 1.3.4 穿线二叉树 80 1.3.4.1二叉树的中序线索化 81 1.3.4.2中序遍历线索化的二叉树 83 1.3.5 堆 84 1.3.5.1建堆过程 84 1.3.5.2在堆中插入节点 87 1.3.6 哈夫曼树 88 1.3.6.1最佳检索树 88 1.3.6.2哈夫曼树结构与算法 90 1.3.6.3 哈夫曼树应用 91 1.3.6.4哈夫曼树程序设计 94 1.3.7 空间数据结构----二叉树深入学习导读 97 1.3.7.1k-d树概念 98 1.3.7.2k-d树程序设计初步 99 1.4非线性数据结构--图 102 1.4.1图的基本概念 102 1.4.2图形结构的物理存储方式 105 1.4.2.1相邻矩阵 105 1.4.2.2图的邻接表示 106 1.4.2.3图的多重邻接表示 108 1.4.3图形结构的遍历 109 1.4.4无向连通图的最小生成树（minimum-cost spanning tree:MST） 112 1.4.5有向图的最短路径 115 1.4.5.1单源最短路径（single-source shortest paths） 115 1.4.5.2每对顶点间最短路经（all-pairs shortest paths） 118 1.4.6拓扑排序 119 第二章 检索 125 2.1 顺序检索 125 2.2 对半检索 126 2.2.1 对半检索与二叉平衡树 126 2.2.2对半检索思想在链式存储结构中的应用---跳跃表 129 2.3 分块检索 135 2.4 哈希检索 136 2.4.1哈希函数 137 2.4.2闭地址散列 138 2.4.2.1线性探测法和基本聚集问题 138 2.4.2.2删除操作造成检索链的中断问题 140 2.4.2.3随机探测法 141 2.4.2.4平方探测法 142 2.4.2.5二次聚集问题与双散列探测方法 143 2.4.3开地址散列 144 2.4.4哈希表检索效率 145 第三章 排序 148 3.1 交换排序方法 148 3.1.1直接插入排序 148 3.1.2冒泡排序 150 3.1.3 选择排序 151 3.1.4 树型选择排序 152 3.2 Shell排序 154 3.3 快速排序 155 3.4 堆排序 158 3.5 归并排序 159 3.6 数据结构小结 162 3.6.1 数据结构的基本概念 162 3.6.2 数据结构分类 163 3.6.2.1数据结构中的指针问题 163 3.6.2.2线性表的效率问题 164 3.6.2.3二叉树 164 3.6.3排序与检索 165 3.7算法分析的基本概念 165 3.7.1基本概念 165 3.7.2上限分析 167 3.7.3下限分析 168 3.7.4空间代价与时间代价转换 168 第6章 高级数据结构内容--索引技术 170 6.1 基本概念 170 6.2 线性索引 171 6.2.1 线性索引 171 6.2.2 倒排