关于我们
精品教材 更多
规划教材 更多
|
数据结构案例教程(C/C++版)
《数据结构案例教程(C/C++版)》依据高职学生学习的特点,经过长期高职教学实践成型。全书包括数据结构与算法、线性表、栈和队列、串、递归、树、图、查找和内排序9部分内容,剔除了数组、矩阵、广义表、外排序和文件等内容,并将较难的内容编排到了“知识与技能扩展”部分,以供读者作为选修内容学习。同时,对于实际工作中应用较少的知识点(如线段树、并查集等)进行了精简。
全书紧紧围绕9部分内容,精心设计了9个有趣的“大话”形式的开场白,旨在通过轻快的类比,帮助学生宏观理解对应的知识点。同时,每章均精选了相对应的经典案例,借助这些案例的讲解和分析,使学生在解决问题的过程中逐步掌握结构设计与算法,并提高学生的通识素养和专业兴趣。
《数据结构案例教程(C/C++版)》可作为高职学院和中职学校计算机相关专业的数据结构和算法教程,同时也可作为程序设计开发者和爱好者的学习参考用书。
数据结构是一门训练编程思维、提高问题解决能力的课程。从谋生角度来看,其效果
可能不会立竿见影;但从长远来看,思维培养比技能训练对学生未来的发展更具深远意义。 本书参考中国高职院校计算机教育课程体系提出的“新的教学三部曲:提出问题→ 解决问题→归纳分析”设计全书架构;按照“目标→问题→任务→方法→结论→扩展”组 织目录结构;并根据“定位准确、取舍合理”的指导思想,对课程内容进行了合理的调整 和改进。全书包括数据结构与算法、线性表、栈和队列、串、递归、树、图、查找和内排 序9 部分内容,剔除了数组、矩阵、广义表、外排序和文件等内容,并将较难的内容(如 KMP、Floyd 等算法)编排到了“知识与技能扩展”部分,以作为选修内容。此外,教材 中的程序尽量减少了对指针的使用;并对实际工作中应用得较少的知识点,如线段树、并 查集、树表查找等,进行了精简。 全书紧紧围绕这9 部分内容,精心设计了9 个有趣的“大话”形式的开场白,旨在通 过轻快的类比,帮助学生宏观理解对应的知识点。同时,每章均精选了相对应的经典案例, 借助这些案例的讲解和分析,既可以使学生在解决问题的过程中掌握结构设计方法与算法; 又能提高学生的通识素养和专业兴趣。 考虑到高职三年的课程安排和面向对象的复杂性,本书特采用C++ 兼容方式编写, 所提供的程序代码均可在Visual C++ 6.0 和Visual Studio 2008/2010 等C++ 环境中运行。 本书由湖南信息职业技术学院的邓锐主编,赵莉和朱清妍任副主编,参与教材编写、 代码测试和技术支持的还有彭顺生、张四平、方丽和杨丽等。感谢学校同事和清华大学出 版社编辑部的朋友们,特别是朱英彪、贾小红老师,你们是本书的支持者和首批读者,感 谢你们提供的宝贵意见和建议;感谢峨眉山青天工作室的9 幅精美插图创作;感谢软件专 业的小伙伴们,特别是杨成、何聪、唐衡龙、曹志雄、郭军宏、王小林等同学,正是与你 们的开心交流,才激发出这些“大话”素材,并促使我们不断改进教学,在三尺讲台上享 受那充满创造力的感觉。 本书是湖南省职业教育与成人教育学会科研规划课题“高职计算机专业教材中引入‘大 话’模式研究”(XHB2013052)、湖南省职业教育“十二五”省级重点建设项目(高职 特色专业软件技术)、湖南省职业院校生产性实习实训基地项目、湖南省教育科学“十二五” 规划课题“高职软件技术专业在双元课程体系模块化的探究”(XJK012CZJ015)等项目 的阶段性研究成果。 本书配有相应的教学资源,如案例源程序和相关视频教学素材等,可以通过清华大 学出版社的教学资料网站(www.tup.tsinghua.edu.cn)下载,也可通过dengrui 2008@163. com 或rkyyt@163.com 直接与作者联系获取,还可以通过“世界大学城”(http://www. worlduc.com/UserShow/default.aspx?uid=212249) 或超星慕课(http://mooc.chaoxing.com/ mycourse/teachercourse?moocId=629135andclazzid=11770)访问更多资源。 在编写本书的过程中,参考了相关教材和参考书,但由于水平有限,书中不妥和疏漏 之处在所难免,希望广大读者批评指正。 编者 2014 年10 月
第1 章 数据结构与算法 ............................................................................................... 1
开场白 ..........................................................................................................................1 1.1 案例提出——高斯的巧妙解题 .........................................................................2 1.2 知识点学习 .........................................................................................................3 1.2.1 数据结构 ................................................................................................3 1.2.2 算法 ......................................................................................................12 1.2.3 数据结构+ 算法= 程序 ......................................................................17 1.3 案例问题解决 ...................................................................................................17 1.3.1 1787 年高斯算法——比较算法优劣 .................................................17 1.3.2 2014 年高斯算法——比较结构优劣 .................................................18 1.4 知识与技能扩展 ...............................................................................................18 课后习题 ....................................................................................................................19 上机实战 ....................................................................................................................20 第2 章 线性表 ............................................................................................................. 22 开场白 ........................................................................................................................22 2.1 案例提出——约瑟夫与海盗 ...........................................................................23 2.2 知识点学习 .......................................................................................................23 2.2.1 线性表 ..................................................................................................23 2.2.2 线性表的顺序存储结构 ......................................................................25 2.2.3 线性表的链式存储结构 ......................................................................30 2.2.4 静态链表 ..............................................................................................42 2.3 案例问题解决 ...................................................................................................42 2.3.1 用顺序表解决约瑟夫问题 ..................................................................43 2.3.2 用循环链表解决约瑟夫问题 ..............................................................44 2.4 知识与技能扩展 ...............................................................................................47 课后习题 ....................................................................................................................48 上机实战 ....................................................................................................................48 第3 章 栈和队列 ......................................................................................................... 50 开场白 ........................................................................................................................50 3.1 案例提出——迷宫问题 ...................................................................................51 3.2 知识点学习 .......................................................................................................52 3.2.1 栈 ..........................................................................................................52 3.2.2 队列 ......................................................................................................63 3.3 案例问题解决 ...................................................................................................71 3.3.1 用栈来解决迷宫问题 ..........................................................................71 3.3.2 用队列来解决迷宫问题 ......................................................................75 3.4 知识与技能扩展 ...............................................................................................79 课后习题 ....................................................................................................................80 上机实战 ....................................................................................................................81 第4 章 串 ...................................................................................................................... 83 开场白 ........................................................................................................................83 4.1 案例提出——埃特巴什码 ...............................................................................84 4.2 知识点学习 .......................................................................................................85 4.2.1 串的基本概念 ......................................................................................85 4.2.2 串的存储结构 ......................................................................................86 4.2.3 串的模式匹配 ....................................................................................100 4.3 案例问题解决 .................................................................................................102 4.3.1 顺序结构埃特巴什码 ........................................................................102 4.3.2 链式结构埃特巴什码 ........................................................................105 4.4 知识与技能扩展——KMP 算法 ...................................................................109 课后习题 ..................................................................................................................112 上机实战 ..................................................................................................................113 第5 章 递归 ................................................................................................................ 115 开场白 ......................................................................................................................115 5.1 案例提出——验证黄金分割 .........................................................................116 5.2 知识点学习 .....................................................................................................117 5.2.1 什么是递归 ........................................................................................117 5.2.2 递归调用的过程 ................................................................................120 5.2.3 递归算法的设计 ................................................................................120 5.3 案例问题解决——验证黄金分割 .................................................................122 5.4 知识与技能扩展——递归转换 .....................................................................123 课后习题 ..................................................................................................................125 上机实战 ..................................................................................................................126 第6 章 树 .................................................................................................................... 128 开场白 ......................................................................................................................128 6.1 案例提出——高效的电文编译 .....................................................................129 6.2 知识点学习 .....................................................................................................129 6.2.1 树的基本概念 ....................................................................................129 6.2.2 二叉树 ................................................................................................136 6.2.3 哈夫曼树 ............................................................................................153 6.3 案例问题解决 .................................................................................................158 6.4 知识与技能扩展——二叉树遍历非递归算法 .............................................162 课后习题 ..................................................................................................................169 上机实战 ..................................................................................................................170 第7 章 图 .................................................................................................................... 172 开场白 ......................................................................................................................172 7.1 案例提出——道路畅通与伤员急救问题的解决 .........................................173 7.2 知识点学习 .....................................................................................................175 7.2.1 图的基本概念 ....................................................................................175 7.2.2 图的存储结构 ....................................................................................177 7.2.3 图的遍历 ............................................................................................183 7.2.4 最小生成树 ........................................................................................187 7.2.5 有向无环图及其应用 ........................................................................191 7.2.6 单源最短路径——迪杰斯特拉算法 ................................................197 7.3 案例问题解决 .................................................................................................201 7.3.1 省政府“畅通工程”——普里姆算法 ............................................201 7.3.2 伤员急需运送——迪杰斯特拉算法 ................................................203 7.4 知识与技能扩展——弗洛伊德算法 .............................................................205 课后习题 ..................................................................................................................207 上机实战 ..................................................................................................................208 第8 章 查找 ................................................................................................................ 210 开场白 ......................................................................................................................210 8.1 案例提出——词典中查找单词 .....................................................................211 8.2 知识点学习 .....................................................................................................211 8.2.1 查找的基本概念 ................................................................................211 8.2.2 线性表的查找 ....................................................................................212 8.2.3 树表查找——二叉排序树 ................................................................218 8.3 案例问题解决 .................................................................................................226 8.4 知识与技能扩展——哈希表查找 .................................................................227 课后习题 ..................................................................................................................231 上机实战 ..................................................................................................................232 第9 章 内排序 ........................................................................................................... 234 开场白 ......................................................................................................................234 9.1 案例提出——光棍节的排序活动 .................................................................235 9.2 知识点学习 .....................................................................................................236 9.2.1 排序的基本概念 ................................................................................236 9.2.2 插入排序 ............................................................................................237 9.2.3 交换排序 ............................................................................................240 9.2.4 选择排序 ............................................................................................244 9.2.5 归并排序 ............................................................................................249 9.2.6 基数排序 ............................................................................................252 9.3 案例问题解决 .................................................................................................253 9.4 知识与技能扩展——各种内排序方法的比较和选择 .................................256 课后习题 ..................................................................................................................257 上机实战 ..................................................................................................................258 参考文献 ........................................................................................................................ 260
我要评论
|