目录第1章绪论 1 1.1引言1 1.2基本概念2 1.3”数据结构”课程的内容5 1.4类C语言和算法评价6 1.4.1类C语言6 1.4.2算法评价8 习题110 第2章顺序表 1 2.1线性表13 2.1.1线性表的逻辑结构13 2.1.2线性表的基本运算13 2.1.3线性表的顺序存储结构15 2.1.4线性表基本运算的实现16 2.2栈和队列18 2.2.1栈19 2.2.2队列33 习题237 第3章链表41 3.1单链表41 3.1.1基本运算在单链表上的实现42 3.1.2单链表的应用示例46 3.2链栈和链队51 3.2.1基本运算在链栈上的实现52 3.2.2基本运算在链队上的实现53 3.2.3队列和栈的应用示例55 3.3循环链表与双重链表60 3.3.1循环链表61 3.3.2双重链表62 习题363 第4章数组和广义表67 4.1数组的逻辑结构67 4.1.1数组的逻辑结构67 4.1.2数组的顺序存储分配67 4.1.3矩阵的压缩存储69 4.1.4稀疏矩阵70 4.1.5用十字链表表示稀疏矩阵76 4.2广义表81 4.2.1广义表的基本概念81 4.2.2广义表链接表示法82 习题484 第5章字符串86 5.1字符串及其运算86 5.2字符串的存储表示87 5.2.1顺序表示87 5.2.2链接表示89 5.2.3模式匹配91 习题593 第6章树95 6.1基本术语及性质95 6.1.1基本术语95 6.1.2树的性质96 6.2树的抽象数据类型和树的存储97 6.2.1基本运算97 6.2.2树的存储98 6.3二叉树101 6.3.1二叉树的定义101 6.3.2二叉树的基本性质102 6.3.3二叉树的抽象数据类型与存储表示103 6.3.4树、森林与二叉树间的转换106 6.4二叉树的遍历108 6.4.1遍历的实现108 6.4.2遍历算法的应用示例112 6.5二叉线索树115 6.6树的遍历121 6.7树的应用122 6.7.1表达式求值122 6.7.2哈夫曼树及其应用123 习题6128 第7章图 132 7.1基本术语133 7.2图的存储结构134 7.2.1邻接矩阵135 7.2.2邻接表137 7.2.3十字链表139 7.2.4邻接多重表143 7.3图的遍历和求图的连通分量143 7.3.1深度优先搜索144 7.3.2广度优先搜索145 7.3.3求图的连通分量147 7.4生成树和最小生成树147 7.5最短路径153 7.5.1从某个源点到其余各顶点的最短路径154 7.5.2每一对顶点之间的最短路径157 7.6拓扑排序159 7.7关键路径163 习题7171 第8章查找表 173 8.1查找表的基本概念173 8.2静态查找表的实现174 8.2.1顺序查找174 8.2.2折半查找176 8.2.3分块查找180 8.3动态查找表的实现183 8.3.1二叉排序树183 8.3.2平衡二叉树191 8.3.3B-树和B 树196 8.3.4数字查找树205 8.4Hash法208 8.4.1构造Hash函数的方法210 8.4.2处理冲突的方法212 8.4.3哈希表的查找及性能分析216 习题8217 第9章内排序 218 9.1计数排序219 9.2直接插入排序220 9.3折半插入排序222 9.4冒泡排序223 9.5希尔排序224 9.6快速排序227 9.7简单选择排序229 9.8堆排序231 9.9归并排序235 9.10基数排序238 9.11总结242 习题9243 参考文献 244 附录上机实验 245