目录第1章数据结构与算法概述11.1数据结构11.1.1什么是数据结构11.1.2数据结构的分类21.2抽象数据类型61.3算法71.3.1什么是算法71.3.2算法的特性91.3.3算法的复杂度101.3.4算法与数据结构121.4小结12【思考题】12第2章线性表132.1什么是线性表132.2线性表的顺序存储（顺序表）142.2.1顺序存储的原理142.2.2顺序存储的实现152.3线性表的链式存储（链表）232.3.1链式存储的原理232.3.2链式存储的实现242.4双链表312.4.1什么是双链表322.4.2双链表的实现322.5循环链表392.5.1什么是循环链表392.5.2循环链表的实现402.5.3约瑟夫环432.6本章小结48【思考题】49目录数据结构与算法——C语言版第3章栈和队列503.1什么是栈503.2栈的实现513.2.1栈的顺序存储实现513.2.2栈的链式存储实现563.3栈的应用603.3.1用栈实现四则运算603.3.2栈的递归应用723.4什么是队列753.5队列的实现753.5.1顺序队列的实现763.5.2链式队列的实现803.5.3循环队列843.6本章小结86【思考题】87第4章串884.1什么是串884.2串的存储结构894.2.1串的顺序存储894.2.2串的链式存储974.3串的模式匹配算法984.3.1朴素的模式匹配984.3.2KMP算法（无回溯的模式匹配）1014.4本章小结105【思考题】105第5章数组和广义表1065.1数组1065.2矩阵的压缩存储1095.2.1特殊矩阵1095.2.2稀疏矩阵的定义1105.2.3稀疏矩阵的创建1125.2.4稀疏矩阵的转置1145.2.5稀疏矩阵的十字链表表示1185.3广义表1235.3.1广义表的定义1235.3.2广义表的存储结构1245.3.3广义表的递归运算1255.4本章小结132【思考题】132第6章树1336.1树1336.1.1什么是树1336.1.2树的表示法1356.2二叉树1386.2.1什么是二叉树1386.2.2二叉树的分类1386.2.3二叉树的性质1396.3二叉树的存储结构1416.3.1二叉树的顺序存储1416.3.2二叉树的链式存储1436.4二叉树的遍历1476.4.1二叉树的遍历1476.4.2递归思想的应用1516.5二叉树的非递归遍历1546.6二叉树与树、森林之间的转换1626.6.1二叉树与树之间的转换1626.6.2二叉树与森林之间的转换1626.7二叉树的创建1646.7.1中序和先序创建二叉树1646.7.2#号法创建树1666.8线索二叉树1696.8.1什么是线索二叉树1696.8.2二叉树的线索化1716.8.3线索化二叉树的遍历1756.9赫夫曼树1776.9.1什么是赫夫曼树1776.9.2赫夫曼树的构造1786.9.3赫夫曼编码1796.10本章小结180【思考题】181第7章图1827.1图的基本概念1827.1.1图的定义与基本术语1827.1.2图的基本操作1857.2图的存储结构1867.2.1图的邻接矩阵存储1877.2.2图的邻接表存储1897.2.3图的十字链表存储1927.2.4图的邻接多重表存储1947.3图的遍历1967.3.1深度优先遍历1967.3.2广度优先遍历1987.4最小生成树2017.4.1什么是最小生成树2017.4.2Prim算法2037.4.3Kruskal算法2077.5最短路径2107.5.1从源点到其他顶点的最短路径2117.5.2每对顶点的最短路径2167.6拓扑排序2197.7关键路径2247.8本章小结229【思考题】230第8章查找2318.1查找概述2318.2顺序表的查找2328.3有序表的查找2338.3.1折半查找2338.3.2插值查找2358.3.3斐波纳契查找2358.4索引顺序查找2398.5二叉排序树2418.6平衡二叉树2468.6.1平衡二叉树的概念2468.6.2平衡二叉树的插入2478.6.3平衡二叉树的删除2528.7B树2548.7.1B树的概念2548.7.2B树的插入2568.7.3B树的删除2588.8键树2618.9哈希表2658.9.1什么是哈希表2658.9.2哈希函数的构造方法2678.9.3处理哈希冲突2698.9.4哈希表的查找实现2738.10本章小结275【思考题】275第9章内部排序2769.1排序的概念与分类2769.2交换排序2789.2.1冒泡排序2799.2.2快速排序2839.3插入排序2869.3.1直接插入排序2869.3.2折半插入排序2899.3.3希尔排序2909.4选择排序2949.4.1简单选择排序2949.4.2树形选择排序2969.4.3堆排序2989.5归并排序3039.6基数排序3079.6.1基数排序基础3079.6.2链式基数排序3109.7内部排序方法比较3149.8磁盘排序3159.8.1外部存储设备3159.8.2磁盘排序分析3179.8.3置换选择排序3199.8.4多路平衡归并3219.8.5最佳归并树3249.9本章小结325【思考题】326第10章文件32710.1文件概述32710.2顺序文件和索引文件32810.2.1顺序文件32810.2.2索引文件32910.3ISAM文件和VSAM文件33110.3.1ISAM文件33110.3.2VSAM文件33410.4哈希文件33610.5多关键字文件33710.5.1多重表文件33710.5.2倒排文件33810.6本章小结339【思考题】339第11章综合项目——贪吃蛇34011.1项目分析34011.1.1模块设计34011.1.2模块描述34211.1.3项目分析34511.2项目实现34611.2.1创建项目34611.2.2项目设计34611.2.3项目实现34911.2.4主函数实现36011.2.5效果展示36411.3项目心得365【思考题】366