数据结构总结

《数据结构——c语言描述》

课程学习总结。

本学期开学习的《数据结构——c语言描述》课程的学习已经结束，对于其中所学习到的具体知识，学会了如何对算法进行具体描述、用c语言程序实现算法、对其它的一些知识也有了一定的了解，现在就其知识点及掌握情况、学习体会以及对该门课程的教学建议等方面进行学习总结。

一、《数据结构——c语言描述》知识点。

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

逻辑结构分为四类：集合型、线型、树型和图型结构，数据元素的存储结构分为：顺序存储、链式存储、索引存储和散列存储四类。

难点是算法复杂度的分析方法和性能分析。

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

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

排序的方法有：直接插入排序、冒泡排序、快速排序、直接选择排序及归并排序等。对各种算法思想先要分析后，要弄清各种算法的时间复杂度与空间性能的优点和缺点等，在什么特定的场合哪种算法思想最合适。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

二、学习情况。

从大体上，对教材中的知识点理解较为完善，但是各个章节均出现有个别知识点较为陌生的现象，对某些具体问题和应用仍有一些模糊和不理解。特别是第三章节后面开始所学习到了内容由于较难，所以对其中的极其个别的内容有一些不理解，以下是对各个章节出现知识点理解情况：

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

第二章，顺序表的概念，生气算法理解较为清晰，并且熟悉简单顺序查找和二分查找，对分块查找还是很模糊。对删除、排序都还是没什么大问题，因为以前有c语言的基础。但是，在实际的应用中仍然有不熟练的现象。

特别是在归并排序的学习中感到很吃力，所以到用的时候就很困难了。所以这一块还要花很多的时间来补习。

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

第四章和第五章有关堆栈以及队列的知识点比较少，除有关算法较为图书以外，其余的算法都是在前面的章节中学过的，加上自己有这一方面的兴趣，因此这一部分内容我基本上没有什么困难。在一些实际问题的应用和处理方面，对其进行存储结构的选择还是需要认真考虑的。在算法的时间复杂度和空间性能的分析还是有一些困难的。

对于第六章的学习感觉较为困难的部分在于矩阵的应用上，在矩阵的存储结构中，使用三元组表发相对较为简单，而是用十字链表就有些困难了。但在某些问题的处理上又必须后从节省空间考虑采用十字链表来处理，想矩阵的加法运算。广义表的定义还是比较容易理解的，其存储结构也不难掌握，关于应用也只局限于在多项式的表示上。

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

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