数据结构与应用算法教程

数据结构与应用算法教程目录目录 第1章绪论及C语言介绍(1) 1.1引言(1) 1.2数据结构的基本概念(2) 1.2.1数据结构的基本术语(2) 1.2.2数据的逻辑结构(4) 1.2.3数据的存储结构(5) 1.2.4数据类型与抽象数据类型(6) 1.3算法描述与分析(8) 1.3.1算法与算法描述(8) 1.3.2算法分析(11) 1.3.3算法的时间复杂度与空间复杂度(12) 1.4C语言相关知识回顾(14) 1.4.1函数的基本概念(14) 1.4.2结构体概述(18) 1.4.3数据结构的综合应用(22) 1.5小结(24) 习题1(25) 第2章线性表的结构分析与应用(27) 2.1线性表的定义和运算(27) 2.2线性表的顺序存储结构(29) 2.2.1顺序表的定义(29) 2.2.2顺序表的实现与操作(30) 2.3线性表的链式存储结构(36) 2.3.1单链表的定义(37) 2.3.2单链表的实现与操作(37) 2.3.3双链表的定义与实现(47) 2.3.4双链表的操作(47) 2.3.5循环链表的定义与实现(56) 2.3.6循环链表的操作(57) 2.4链式结构的应用算法(60) 2.5线性表的顺序存储结构和链式存储结构的对比(64) 2.6小结(65) 2.7习题2(65) 第3章栈和队列的结构分析与应用(69) 3.1栈的定义(69) 3.1.1栈的顺序存储和实现(70) 3.1.2顺序栈的操作(71) 3.1.3栈的链式存储和实现(73) 3.1.4链式栈的操作(74) 3.1.5顺序栈与链式栈的比较(75) 3.2栈的应用算法(76) 3.2.1栈与递归(76) 3.2.2栈与数制转换(76) 3.2.3栈与背包问题(77) 3.3队列的定义(79) 3.3.1队列的顺序存储和实现(80) 3.3.2循环队列的表达和实现(81) 3.3.3循环队列的操作(82) 3.3.4链式队列的表达和实现(84) 3.3.5链式队列的操作(85) 3.4队列的应用算法(87) 3.5小结(90) 习题3(90) 第4章字符串的结构分析与应用(93) 4.1字符串及其类型定义(93) 4.1.1串及其相关术语(93) 4.1.2串的抽象数据类型(94) 4.2串的定长顺序存储(94) 4.2.1串的定长顺序存储结构(94) 4.2.2定长顺序串的基本操作(95) 4.3串的堆存储结构(99) 4.3.1堆存储结构(99) 4.3.2堆结构上的基本操作(99) 4.4串的链式存储结构(100) 4.4.1链式存储结构(100) 4.4.2链式结构上的基本操作(101) 4.5字符串的应用算法(103) 4.5.1KMP算法原理(103) 4.5.2KMP算法实现(107) 4.5小结(109) 习题4(109) 第5章二维数组及广义表的结构分析(112) 5.1二维数组的行存储和列存储(112) 5.2矩阵的压缩存储(113) 5.2.1特殊矩阵的压缩存储(114) 5.2.2稀疏矩阵的压缩存储(116) 5.3广义表的概念(122) 5.3.1广义表常用表示(122) 5.3.2广义表的深度(122) 5.3.3广义表的基本运算(123) 5.3.4广义表的存储结构(123) 5.4矩阵的应用算法(124) 5.5小结(125) 习题5(125) 第6章树和二叉树(128) 6.1树的定义和术语(128) 6.1.1树的定义(128) 6.1.2树的逻辑表示方法(129) 6.1.3树的基本术语(129) 6.2二叉树(131) 6.2.1二叉树的定义和性质(131) 6.2.2二叉树的存储结构(133) 6.3二叉树的遍历(136) 6.3.1二叉树的递归遍历算法(137) 6.3.2二叉树的非递归遍历算法(143) 6.3.3二叉树的层次遍历算法(150) 6.4二叉树遍历算法的应用(152) 6.4.1查找数据元素(152) 6.4.2统计叶子节点的数目(154) 6.4.3求二叉树深度(156) 6.5线索化二叉树(157) 6.5.1线索二叉树的定义及结构(157) 6.5.2线索二叉树的基本操作及算法实现(159) 6.6树的存储结构(162) 6.6.1树的双亲表示法(163) 6.6.2树的孩子表示法(165) 6.6.3树的孩子兄弟表示法(169) 6.7树、森林与二叉树的转换(170) 6.7.1树转化为二叉树(171) 6.7.2森林转化为二叉树(171) 6.8树和森林的遍历(172) 6.9哈夫曼树及其应用(173) 6.9.1哈夫曼树的相关定义(173) 6.9.2哈夫曼树的构造(173) 6.9.3哈夫曼树的实现(174) 6.9.4哈夫曼编码(177) 6.9.5哈夫曼树及编码的完整算法(179) 6.10树结构的应用算法(183) 6.10.1回溯法(183) 6.10.2《移动迷宫》游戏算法(187) 6.11小结(192) 习题6(192) 第7章图的结构分析与应用(197) 7.1图的概念和术语(197) 7.2图的存储结构(200) 7.2.1邻接矩阵表示法(200) 7.2.2邻接表表示法(202) 7.3图的遍历(205) 7.3.1深度优先搜索遍历(205) 7.3.2广度优先搜索遍历(207) 7.3.3图遍历的应用算法(208) 7.4无向图的应用(210) 7.4.1生成树和生成森林(211) 7.4.2最小生成树(211) 7.5有向图的应用(216) 7.5.1拓扑排序(216) 7.5.2最短路径求解算法(219) 7.6小结(224) 习题7(224) 第8章查找的分析与应用(228) 8.1查找的基本概念(228) 8.2线性表的查找(230) 8.2.1顺序查找法(230) 8.2.2折半查找法(231) 8.2.3分块索引查找法(234) 8.2.4线性表查找的性能对比及分析(235) 8.3静态查找法的应用算法(236) 8.3.1使用折半查找法实现学生信息查询模块的设计(236) 8.3.2静态树表优化查找算法(237) 8.4树表的查找(240) 8.4.1二叉排序树(240) 8.4.2二叉排序树的查找(241) 8.4.3二叉排序树的插入及构建(241) 8.4.4二叉排序树的删除(242) 8.4.5二叉排序树的查找性能分析(245)