数据结构与应用算法教程

　　《数据结构与算法》课程目前在我校计算机科学专业、软件工程专业、人工智能专业、网络工程，物联网和电信、通信专业都有开设，同时也是计算机相关专业的专业核心必修课程。本课程的研究不仅涉及计算机硬件（编码理论、存储装置和存取方法）的研究范围，而且和计算机软件的研究有着密切的关系，是介于数学、计算机硬件和计算机软件之间的一门核心课程。在计算机及相关科学中，它不仅是程序设计的重要理论基础，而且是设计和实现操作系统、数据库系统和软件工程、计算机网络以及信息技术应用系统等课程的重要基础。因此该课程的学习质量将直接影响计算机软件系列课程的学习效果，该课程着重培养学生分析问题、解决问题的能力。随着互联网+和大数据时代的来临，将会面临着更多的软件人才的需求，本课程在计算机信息科学专业中为此类人才的培养起着至关重要的作用。

　　1. 近5年承担的学术研究课题参与湖北省教育厅2014年高等学校省级教学研究项目：软件工程专业校企共赢“2+1+1”培养模式研究（2014417）项目排名第二； 2. 发表的教学研究论文及学术论文《数据结构算法课程开发内化教学方式探究》， 《中国校外教育》，第一作者，2013.12 《基于B/S模式智能化排课系统的分析与设计》，《电子技术与软件工程》，独撰，2013.7 《切割文字全等矩形图片拼接算法的设计实现》，《软件导刊》，独撰，2015.9 《Unity引擎方式下3D对战型游戏的网络设计与开发》，《现代电子技术》，独撰，2015.12

数据结构与应用算法教程目录目录 第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)