数据结构

第1章 绪论 1.1 重点难点 1.2 主要内容 1.2.1 数据的逻辑结构 1.2.2 数据结构的存储实现 1.2.3 算法分析 1.3 习题解答 1.3.1 简答题 1.3.2 程序设计题 1.4 进一步拓展 1.4.1 最大公因子问题 1.4.2 递归函数的时间复杂度的计算第2章 线性表 2.1 重点难点 2.2 主要内容 2.2.1 线性表的定义及基本运算 2.2.2 线性表的顺序实现 2.2.3 线性表的链接实现 2.3 习题解答 2.3.1 简答题 2.3.2 程序设计题 2.4 进一步拓展 2.4.1 字符串的存储与匹配 2.4.2 模拟动态内存分配第3章 栈 3.1 重点难点 3.2 主要内容 3.2.1 栈的基本概念 3.2.2 栈的顺序实现 3.2.3 栈的链接实现 3.3 习题解答 3.3.1 简答题 3.3.2 程序设计题 3.4 进一步拓展 3.4.1 基于线性表的栈的实现 3.4.2 迷宫问题第4章 队列 4.1 重点难点 4.2 主要内容 4.2.1 队列的概念 4.2.2 队列的顺序实现 4.2.3 队列的链接实现 4.3 习题解答 4.3.1 简答题 4.3.2 程序设计题 4.4 进一步拓展 4.4.1 迷宫问题 4.4.2 火车车厢重排第5章 树 5.1 重点难点 5.2 主要内容 5.2.1 树的定义和基本概念 5.2.2 二叉树的基本概念 5.2.3 二叉树的顺序实现 5.2.4 二叉树的链接实现 5.2.5 二叉树遍历的非递归实现 5.2.6 哈夫曼树和哈夫曼编码 5.2.7 树、森林和二叉树 5.3 习题解答 5.3.1 简答题 5.3.2 程序设计题 5.4 进一步拓展 5.4.1 户序线索树 5.4.2 户序线索树的存储 5.4.3 构造中序穿线 5.4.4 遍历二叉线索树第6章 优先级队列 6.1 重点难点 6.2 主要内容 6.2.1 优先级队列的概念 6.2.2 二叉堆 6.2.3 贝努里队列 6.3 习题解答 6.3.1 简答题 6.3.2 程序设计题 6.4 进一步拓展 6.4.1 双端队列 6.4.2 最小语言集第7章 集合与静态查找表 7.1 重点难点 7.2 主要内容 7.2.1 集合的基本概念 7.2.2 查找及静态查找表 7.2.3 无序表的查找 7.2.4 有序表的查找 7.3 习题解答 7.3.1 简答题 7.3.2 程序设计题第8章 查找树 8.1 重点难点 8.2 主要内容 8.2.1 二叉查找树 8.2.2 AVL树 8.2.3 红黑树 8.2.4 伸展树 8.2.5 B+树 8.3 习题解答 8.3.1 简答题 8.3.2 程序设计题 8.4 进一步拓展 8.4.1 线段树 8.4.2 道路问题第9章 散列表 9.1 重点难点 9.2 主要内容 9.2.1 散列函数 9.2.2 碰撞的解决 9.3 习题解答 9.3.1 简答题 9.3.2 程序设计题 9.4 进一步拓展第10章 排序 10.1 重点难点 10.2 主要内容 10.2.1 基本概念 10.2.2 插入排序 10.2.3 选择排序 10.2.4 交换排序 10.2.5 归并排序 10.2.6 外排序 10.3 习题解答 10.3.1 简答题 10.3.2 程序设计题 10.4 进一步拓展 10.4.1 基数排序的思想 10.4.2 基数排序的实现 10.4.3 基数排序的性能第11章 不相交集 11.1 重点难点 11.2 主要内容 11.2.1 不相交集的定义 11.2.2 不相交集的实现 11.3 习题解答 11.3.1 简答题 11.3.2 程序设计题 11.4 进一步拓展第12章 图 12.1 重点难点 12.2 主要内容 12.2.1 图的定义及术语 12.2.2 图的存储 12.2.3 图的遍历 12.3 习题解答 12.3.1 简答题 12.3.2 程序设计题 12.4 进一步拓展 12.4.1 逆邻接表 12.4.2 十字链表 12.4.3 邻接多重表第13章 最小生成树 13.1 重点难点 13.2 主要内容 13.2.1 Kruskal算法 13.2.2 Prim算法 13.3 习题解答 13.3.1 简答题 13.3.2 程序设计题 13.4 进一步拓展第14章 最短路径问题 14.1 重点难点 14.2 主要内容 14.2.1 单源最短路径 14.2.2 所有结点对的最短路径 14.3 习题解答 14.3.1 简答题 14.3.2 程序设计题第15章 算法设计基础 15.1 重点难点 15.2 主要内容 15.2.1 枚举法 15.2.2 贪婪法 15.2.3 分治法 15.2.4 动态规划 15.2.5 回溯法 15.2.6 随机算法 15.3 习题解答 15.3.1 简答题 15.3.2 程序设计题参考文献

《数据结构——题解与拓展》在内容安排上与《数据结构：思想与实现》相呼应。每章基本上都包括4个部分：重点难点、主要内容、习题解答和进一步拓展。重点难点部分总结了每一章学习的重点和难点；主要内容部分是对主教材相应章的内容的概括；习题解答部分给出了各章章后所附习题的分析与解答；进一步拓展部分是对主教材的补充，介绍了一些主教材没有提到，但也会被经常用到的数据结构以及这些数据结构的应用。本书由翁惠玉，俞勇编著。 《数据结构——题解与拓展》是国家精品课程“数据结构”(上海交通大学)的主讲教材之一，并与主教材《数据结构：思想与实现》(翁惠玉、俞勇编著)相配套。本书总结了主教材各章的主要内容以及重点难点，并对主教材中的习题进行了分析和解答。作为对主教材的补充，本书在大多数章中都增加了一个拓展部分，使学有余力的学生能够进一步深入地学习数据结构。本书概念清楚，内容丰富，通过学习，可以帮助学生进一步巩同数据结构的知识。 《数据结构——题解与拓展》可作为高等学校计算机及相关专业“数据结构”课程的教学辅导教材，也可以作为全国计算机专业硕士研究生入学考试的辅导用书。本书由翁惠玉，俞勇编著。【作者简介】 翁惠玉,毕业于上海交通大学，获博士学位。现为上海交通大学计算机系副教授，主要从事计算机网络和信息系统的研究，并长期承担程序设计的教学工作，主讲计算机系ACM试点班和电信学院大平台的程序设计课程，该课程于2004年被评为上海市精品课程。 俞勇，1961年生，上海交通大学教授、博士生导师。1986年毕业于华东师范大学计算机系，获得硕士学位。国家精品课程“数据结构”主持人，主编教材2本、译著1本。先后主持教育部教育教学改革项目2项，获得国家级和上海市教学成果奖6项，上海市优秀教材奖1项，并两次率队夺得ACM国际大学生程序设计竞赛全球总冠军。从事Web搜索与挖掘研究，先后主持国家自然科学基金、国家863计划等10多项，发表重要国际会议和期刊论文近百篇。 曾获得国务院特殊津贴，“全国师德标兵”、“上海市五一劳动奖章”、“宝钢优秀教师特等奖”、“上海市教学名师”等荣誉，曾被中央电视台新闻联播，上海教育台、光明日报、文汇报等十多家媒体报道。