《数据结构》学习指南

《数据结构》学习指南《数据结构》是计算机学科的主干课，编译原理、操作系统、数据库系统等多个专业课的重要基础课程，同时也是计算机程序设计与开发所需的必备知识。学习本课程要注意数据结构与算法紧密结合，对典型算法掌握其时间复杂性的分析过程，学会基本的算法正确性证明方法。教材中每章附带的习题和习题集中的习题可根据推荐的难度等级由浅入深、独立思考逐步完成。如遇到较难习题，要逐级参考分级启发式提示并结合自己的思路尝试解决。在学习过程中，通过ADL语言描述快速理解并掌握算法的设计思想，再结合上机实验和课程设计等实践环节利用C++语言进行验证实验、设计实验以及综合运用所学知识进行综合实验和创新实验，在理论和实践相结合的过程中不断巩固和加深对数据结构知识的理解，并提高编程能力，更好的完成本课程的学习。本课程主要包括绪论，线性表、树、图等基本数据结构，递归、排序、查找等基本算法，内存管理，文件等五部分。下面针对每一部分内容总结主要知识点并给出一些学习建议，并列出部分参考书目，以期能够帮助学生更好地完成本门课程的学习：绪论（第一章）知识点：数据、数据元素、数据结构等概念和术语的含义；数据的逻辑结构和存储结构；ADL书写算法的规范；算法的定义及其特性；评估算法的基本准则；算法时间复杂性的分析方法；时间与空间分析。学习指南：本部分知识以知道和理解为主，需要理解什么是数据结构，特别是数据结构的逻辑结构、存储结构及数据运算的含义及其相互关系，理解并熟悉ADL语言。熟练掌握算法的时间复杂度和空间复杂度，最好、最坏和平均时间复杂度等概念，这些概念在后续章节里会频繁使用和出现。掌握算法描述和算法分析的基本方法、对典型算法要能分析出时间复杂度。基本数据结构（第二、三、四、五章）知识点：线性表、树、图三种数据结构的逻辑结构；上述数据结构的存储结构；上述数据结构上的主要算法；上述数据结构的典型应用；上述数据结构的数学性质；学习指南：本部分是《数据结构》课程的重点内容之一，需要熟练掌握。上述知识点仅从宏观上概括了这一部分的内容，以使学生能够总体了解这一部分的知识分布。具体知识点可参考以下表格自行归纳，例如：线性表、树、图都有各自的遍历算法，图有拓扑排序算法；构造哈夫曼树是树的应用，堆栈和队列以及数组、字符串都是线性表的应用；在总结和分类这些知识点的过程中，归纳分析不同数据结构间的区别和联系有助于更好地掌握这一部分知识。线性表树图逻辑结构存储结构算法应用特性递归、排序、查找算法（第六、七、八章）知识点：递归算法的基本设计思想，算法执行原理；几类典型的排序算法的主要思想；插入排序、交换排序、选择排序、合并排序各包含哪些典型算法；上述算法的时间复杂性和空间复杂性分析和对比；几类典型的查找算法的主要思想；线性表查找、外查找、散列查找的典型算法；上述算法的时间复杂性和空间复杂性分析和对比；学习指南：递归算法在大部分章节的算法中都会使用到，需要重点理解递归算法的设计，以及递归与堆栈的关系，了解递归到非递归的转换方法以及递归典型应用。排序和查找是《数据结构》课程中最中要的两类算法，要熟练掌握。清楚掌握各个排序算法要其所属排序类别，各个类别的排序思想。以及算法特点，如时间复杂性、空间复杂性、稳定性等。学习过程中可尝试自行完成下面的表格，更加系统的掌握排序算法。掌握不同类型的查找算法之间的区别和联系、查找效率。在上机实践中验证并比较各个算法，并尝试优化算法。排序方法最好时间平均时间最坏时间辅助空间稳定性直接插入O(n)O(n2)O(n2)O(1)稳定直接选择冒泡快速……内存管理（第九章）知识点：均匀大小记录内存分配算法；均匀大小记录内存回收算法；不同大小记录内存分配算法；不同大小记录内存回收算法；伙伴系统的原理及相应算法。学习指南：内存管理的目的是为有效利用计算机内存中的可用资源，学习过程中对比均匀大小和不同大小记录的内存管理方法的区别和联系。在编程实践过程中，注意理解内存管理算法的同时注意巩固和回忆线性表部分所学知识。文件（第十章）文件的定义、分类等基本概念；文件的逻辑结构与存储结构；文件的四种存储结构：顺序结构，索引结构，散列结构和链结构；四种存储结构的特点及相应操作；学习指南：文件是是指存储在外存中的、由大量性质相同的记录组成的集合，学习本章内容要注意对比顺序文件、杂凑文件、索引文件和多关键字文件这四种存储结构的特点，掌握不同存储结构上操作算法的区别。随机数（第十一章）生成符合某概率分布的随机数的算法；随机数检验方法；随机排列与随机组合他的算法；随机数的应用；学习指南：本章的主要内容是随机数的产生和检验方法，要熟悉线性同余法等基本的随机数产生算法的原理。了解衡量随机序列的随机数检验方法，如2检验、KS检验、等分布检验、序列检验、间隔检验的经验检验方法，初步了解和验证随机数的应用。参考书：[1] WilliamFord,WilliamTopp,DataStructureswithC++.（中文译名：数据结构（C++语言描述））,Prentice-HallInternational,Inc.（影印本由清华大学出版社出版），1996.[2] MarkAllenWeiss,(FloridaInternationalUniversity),Algorithms,DataStructures,andProblemSolvingwithC++,Addison-WesleyPublishingCompany,Inc.,1996.[3] 管纪文，刘大有，《数据结构》，高等教育出版社，1985.[4] 许卓群，张乃孝，杨冬青，唐世渭，《数据结构》，高等教育出版社，1987.[5] 刘大有，李岳峰，《数据结构原理》，吉林大学出版社，1994.[6] 严蔚敏，吴伟民，《数据结构》（C语言版），清华大学出版社，1997.[7] 张乃孝，裘宗燕，《数据结构－C++与面相对象的途径》，高等教育出版社，1998.[8] 殷人昆，陶永