数据结构总结

《数据结构与算法》课程学习总结报告。

本学期开设的《数据结构与算法》课程已经告一段落，现就其知识点及其掌握情况、学习体会以及对该门课程的教学建议等方面进行学习总结。

一、《数据结构与算法》知识点。

第一章是这门学科的基础章节，从整体方面介绍了“数据结构和算法”，同时引入相关的学术概念和术语，如数据、数据元素、数据类型以及数据结构的定义。重点是数据结构的括逻辑结构、存储结构和运算集合的含义及其相互联系。数据结构和两大逻辑结构的4四种常用存储方法；逻辑结构分为四类：

集合型、线性、树形和图形结构，数据元素的存储结构分为：顺序存储、链接存储、索引存储和散列存储四类。难点是算法复杂度的分析方法和性能的分析。

第二章详细地分析了顺序表。介绍了顺序表的相关概念及其有关运算。基本运算有：

初始化表、求表长、排序、元素的查找、插入及删除等。元素查找方法有：简单顺序查找、二分查找和分块查找。

排序方法有：直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序及归并排序等，在各种算法思想的先分析后，要弄清各种算法的时间复杂度与空间性能的优点和缺点，在什么特定的场合适合哪种算法思想。最后介绍了顺序串的概念，顺序串是顺序表的一个特例；区别在于组成顺序串的数据元素是一组字符，其重点在于串的模式匹配。

第三章介绍链表。链表中数据元素的存储不一定是连续的，还可以占用任意的、不连续的物理存储区域。与顺序表相比，链表的插入、删除不需要移动元素，给算法的效率带来较大的提高，且在存储空间上有动态申请的优点。

这一章中介绍了链表的节点结构、静态与动态链表的概念、链表的基本运算（如求表长、插入、查找、删除等）、单链表的建立（头插法和尾插法）以及双向循环链表的定义、结构、功能和基本算法。弄清其个运算的算法思想及其时间复杂度和空间性能。最后介绍了链表之中存储结构在实际中的相关应用。

第四章，堆栈是运算受限制的线性结构。其基本运算方法与顺序表和链表运算方法基本相同，不同的是堆栈须遵循“先进后出”的规则，对堆栈的操作只能在栈顶进行；堆栈在文字处理，匹配问题和算术表达式的求值问题方面的应用。

第五章，队列是一种够类似堆栈的线性结构。其基本运算方法与顺序表和链表运算方法基本相同，不同的是堆栈须遵循“先进先出”的规则，对堆栈的操作只能在栈顶进行；其运算有入队、出队等操作。在介绍队列时，提出了循环队列的概念，以避免“假溢出”的现象。

第六章介绍了特殊矩阵和广义表的概念与应用。其中，特殊矩阵包括对称矩阵、三角矩阵、对角矩阵和稀疏矩阵，书中分别详细介绍了它们的存储结构。其中三元组和十字链表这两种结构尤为重要；对着两种结构的建立了应用要掌握。

稀疏矩阵的应用包括转置和加法运算等。最后介绍了广义表的相关概念及存储结构，关于它的应用，课本中举了m元多项式的表示问题。

第七章二叉树的知识是重点内容。在介绍有关概念时，提到了二叉树的性质以及两种特殊的二叉树：完全二叉树和满二叉树。

接着介绍二叉树的顺序存储和链接存储以及生成算法。重点介绍二叉树的遍历算法（递归算法、先序、中序和后序遍历非递归算法）和线索二叉树。二叉树的应用：

基本算法、哈弗曼树、二叉排序树和堆排序，其中关于二叉排序树和哈弗曼书的构建是重点。

第八章介绍了树。树与二叉树是不同的概念。教材介绍了树和森林的概念、遍历和存储结构，还有树、森林和二叉树的相互关系，树或森林怎样转化成二叉树，二叉树又如何转换为树和森林等算法。

第九章，散列结构是一种查找效率很高的一种数据结构。本章的主要知识点有：散列结构的概念及其存储结构、散列函数、两种冲突处理方法、线性探测散列和链地址散列的基本算法以及散列结构的查找性能分析。

最后一章介绍了图的概念及其应用，是本书的难点。图的存储结构的知识点有：邻接矩阵、邻接表、逆邻接表、十字链表和邻接多重表。

图的遍历包括图的深度优先搜索遍历和广度优先搜索遍历。其余知识点有：有向图、连通图、生成树和森林、最短路径问题和有向无环图及其应用。

有向无环图重点理解aov网和拓扑排序及其算法。

二、对各知识点的掌握情况。

总体来看，对教材中的知识点理解较为完善，但各个章节均出现有个别知识点较为陌生的现象，对某些具体的问题和应用仍有一些模糊与措手。各个章节出现的知识点理解和掌握情况明确一下。。

第一章中我对数据和数据结构的概念理解较为透彻，熟悉数据结构的逻辑结构和存储结构。算法的时间、空间性能分析是重点，同样也是难点，尤其是空间性能分析需要加强。在某些强大与复杂的算法面前的处理有些棘手。

第二章，顺序表的概念、生成算法理解较为清晰，并且熟悉简单顺序查找和二分查找，对分块查找较为含糊。删除方面的问题比较容易些。排序问题中，由于冒泡排序在大一c语言课上已经学习过，再来学习感觉相对轻松些。

对插入排序和选择排序理解良好，但是，在实际运用中仍然出现明显不熟练的现象。由于在归并排序学习中感觉较吃力，现在对这种排序方法仍然非常模糊，所以需要花较多的时间来补习。此外串的模式匹配也是较难理解的一个地方。

第三章链表中，除对双向循环链表这一知识点理解困难之外，在对链表进行插入删除和排序相关操作上同顺序表的操作基本相当。其他的知识点像单链表的建立和基本算法等都较为熟悉。

第四章和第五章有关堆栈以及队列的知识点比较少，除有关算法较为特殊以外，其余算法都是先前学过的顺序表和链表的知识，加上思想上较为重视，因此这部分内容是我对全书掌握最好的一部分。在一些实际问题的应用与处理方面，对其进行存储结构的选择还是需要认真考虑的。在算法的时间复杂度和空间性能的分析仍有些困难。

第六章的学习感觉较为困难的部分在于矩阵的应用上。在矩阵的存储结构中，使用三元组表发相对较为简单，而使用十字链表就有些困难了。但在某些问题的处理上又必须或从节省空间考虑采用十字链表来处理，想矩阵的加法运算。

广义表的定义还是比较容易理解的，其存储结构也不难掌握，关于应用也只局限于在多项式的表示上。

第七章是全书的重点。在这一章中概念和定义都很多，有些很昏人但都很重要，要区分开来。二叉树的性质容易懂却很难记忆。

对二叉树的存储结构和遍历算法这部分内容掌握较好，能够熟练运用。关于二叉排序树和的哈弗曼树却相对有些压力，其生成和对其关键字的插入和删除时重点。

数据结构总结

数据结构总结

数据结构总结

数据结构总结

其他用户还读了