数据结构边做边学(微课视频版)/21世纪新形态教学练一体化规划丛书

本书介绍了数据结构的 基本概念，线性表、栈、队 列、字符串、多维数组、树 和二叉树、图等常用的数据 结构，讨论了查找、排序和 索引等技术，给出了每种数 据结构常见的应用示例。本 书理论和实践并重，采用边 做边学的方式，首先详细阐 述理论知识，然后以应用实 例的方式实现了常见的算法 ，并附有程序运行结果和说 明。本书内容丰富，层次分 明，深入浅出。采用类C++ 语言描述算法，提供课件、 视频、源代码、课后习题参 考答案等相关教辅材料。 本书可以作为计算机各 相关专业的数据结构理论课 教材，也可以作为数据结构 课程设计的教材，还可以供 感兴趣的自学者阅读参考。

任平红，学术方面：研究领域主要为软件测试，参与省厅级课题多项，在国内外期刊上发表学术论文十余篇。教育背景：2005年毕业于中国石油大学（华东）计算机与通信工程学院，获计算机软件与理论工学硕士学位。著译作品：主编教材三部，参编教材一部。业务成果：参与和主持多个企业项目研发，指导学生参加各类比赛获得多项奖励，具有丰富的实际项目开发和教学经验。

目录 第1章绪论 1.1解决问题的一般过程 1.2数据结构的基本概念 1.3算法及算法分析 1.3.1算法及其特点 1.3.2高级程序设计语言 1.3.3算法和程序的关系 1.3.4算法分析 1.4小结 习题 第2章线性表 2.1线性表的逻辑结构 2.1.1线性表的定义 2.1.2线性表的基本操作 2.2线性表的顺序存储结构 2.2.1顺序表 2.2.2顺序表的实现 2.3顺序表的应用 2.3.1有序表重复元素的删除 2.3.2有序表的合并 2.4线性表的链式存储结构及实现 2.4.1单链表 2.4.2单链表的实现 2.4.3其他链表形式 2.5顺序表和链表的比较 2.5.1空间性能 2.5.2时间性能 2.6单链表的应用 2.6.1单链表的原地逆置 2.6.2判断单链表是否有序及对单链表排序 2.6.3利用单链表实现有序表的合并 2.6.4利用单链表判断两个集合是否相等 2.6.5利用单链表求两个集合的并集 2.6.6利用单链表求两个集合的交集 〖1〗 〖2〗 2.6.7利用单链表删除有序表中的重复元素 2.6.8删除普通单链表中的重复元素 2.6.9利用单链表实现一元多项式相加 2.7小结 习题 第3章栈和队列 3.1栈 3.1.1栈的逻辑结构 3.1.2栈的顺序存储结构 3.1.3栈的链式存储结构 3.1.4顺序栈和链栈的比较 3.2栈的应用 3.2.1Hanoi塔问题 3.2.2利用顺序栈实现进制转换 3.2.3迷宫问题 3.2.4八皇后问题 3.2.5火车调度问题 3.2.6表达式括号匹配问题 3.2.7后缀表达式求值 3.2.8中缀表达式求值 3.2.9中缀表达式转换为后缀表达式 3.3队列 3.3.1队列的逻辑结构 3.3.2顺序队列 3.3.3循环队列 3.3.4双端队列 3.3.5链队列 3.4小结 习题 第4章字符串和多维数组 4.1字符串 4.1.1字符串的逻辑结构 4.1.2字符串的存储结构 4.2字符串的模式匹配 4.2.1朴素的模式匹配算法 4.2.2KMP算法 4.3字符串的应用 4.3.1凯撒密码 4.3.2统计文本中单词的个数 4.3.3找词游戏 4.3.4变位词判断 4.3.5字符串的最长公共子序列 4.4多维数组 4.4.1多维数组的逻辑结构 4.4.2多维数组的寻址 4.5矩阵的压缩存储 4.5.1特殊矩阵的压缩存储 4.5.2稀疏矩阵的压缩存储 4.6多维数组的应用 4.6.1约瑟夫环问题 4.6.2求解矩阵的马鞍点 4.6.3螺旋方阵 4.6.4幻方 4.7小结 习题 第5章树和二叉树 5.1树的逻辑结构 5.1.1树的基本术语 5.1.2树的抽象数据类型定义 5.1.3树的遍历 5.2树的存储结构 5.2.1双亲表示法 5.2.2孩子链表表示法 5.2.3孩子兄弟表示法 5.3二叉树的逻辑结构 5.3.1二叉树的定义 5.3.2二叉树的性质 5.3.3二叉树的抽象数据类型定义 5.3.4二叉树的遍历 5.4二叉树的存储结构及实现 5.4.1顺序存储结构 5.4.2二叉链表 5.4.3三叉链表 5.5二叉树的应用 5.5.1非递归遍历二叉树 5.5.2二叉树遍历的应用 5.5.3线索二叉树的构造和应用 5.5.4赫夫曼树和赫夫曼编码 5.5.5求二叉树的最小深度 5.5.6判断二叉树是否是完全二叉树 5.5.7判断二叉树的结构是否对称 5.5.8判断二叉树是否对称 5.5.9求二叉树第k层的结点个数和叶子结点个数 5.5.10打印二叉树第k层的结点和叶子结点 5.5.11求二叉树最大的结点距离 5.5.12由前序序列和中序序列构造二叉树 5.5.13由后序序列和中序序列构造二叉树 5.5.14求二叉树的镜像 5.5.15判断两棵二叉树是否等价 5.6树、森林与二叉树的转换 5.7小结 习题 第6章图 6.1图的逻辑结构 6.1.1基本术语 6.1.2图的抽象数据类型定义 6.1.3图的遍历 6.2图的存储结构 6.2.1邻接矩阵 6.2.2邻接表 6.2.3十字链表 6.2.4邻接多重表 6.3最小生成树 6.3.1MST性质 6.3.2Prim算法 6.3.3Kruscal算法 6.4最短路径问题 6.4.1Dijkstra算法 6.4.2Floyd算法 6.5拓扑排序 6.6关键路径 6.7图的其他应用 6.7.1七巧板涂色问题 6.7.2五岔路口交通灯问题 6.7.3选址问题 6.7.4农夫过河问题 6.7.5旅行商问题 6.8小结 习题 第7章查找 7.1概述 7.1.1基本概念 7.1.2查找算法的性能分析 7.2线性表的查找 7.2.1顺序查找 7.2.2折半查找 7.2.3斐波那契查找 7.3树表的查找 7.3.1二叉排序树 7.3.2平衡二叉树 7.3.3树表的应用 7.4散列表的查找 7.4.1概述 7.4.2散列函数的设计 7.4.3处理冲突的方法 7.4.4散列表的查找性能分析 7.4.5闭散列表和开散列表的比较 7.5小结 习题 第8章排序 8.1概述 8.1.1基本概念 8.1.2排序的分类 8.1.3排序算法的性能 8.2插入排序 8.2.1直接插入排序 8.2.2希尔排序 8.3交换排序 8.3.1起泡排序 8.3.2双向起泡排序 8.3.3快速排序 8.4选择排序 8.4.1简单选择排序 8.4.2堆排序 8.5归并排序 8.5.1二路归并的非递归实现 8.5.2二路归并的递归实现 8.6分配排序 8.6.1桶式排序 8.6.2基数排序 8.7各种排序算法的比较 8.8排序算法的应用 8.8.1荷兰国旗问题 8.8.2螺钉和螺母问题 8.9小结 习题 第9章索引 9.1基本概念 9.2线性索引 9.2.1稠密索引 9.2.2分块索引 9.2.3多重表 9.2.4倒排表 9.3树形索引 9.3.123树 9.3.2B树 9.3.3B+树 9.4小结 习题 参考文献