《数据结构与算法课程学习总结》由会员分享，可在线阅读，更多相关《数据结构与算法课程学习总结（6页珍藏版）》请在金锄头文库上搜索。
1、数据结构与算法课程学习总结数据结构与算法课程学习总结2010 年 05 月 20 日班级： 姓名： 学号：一、课程学习内容总结一、课程学习内容总结（1 1）第一章知识点及主要知识）第一章知识点及主要知识：本章的重点是数据结构中的逻辑结构、存储结构、数据的运算 3 个方面的 概念及相互关系，难点是算法复杂度的分析方法。基本概念和术语有数据、数 据元素、数据项、数据结构。特别是数据结构的逻辑结构、存储结构及运算的 含义及其相互关系；数据的结构的两大类逻辑结构和 4 个常用的存储表示方法； 算法、算法的时间复杂度和空间复杂度、最坏的和平均时间复杂度等概念，算 法描述和算法分析的方法、对一般的算法要能
2、分析出时间复杂度和空间复杂度。本人掌握知识情况及分析：本人掌握知识情况及分析：通过对这一章的学习，我理解了数据和数据结构的有关概念，熟悉了数据 结构的逻辑结构和存储结构。但对算法的时间、空间性能分析还不太熟练，尤 其是空间性能分析需要加强。（2 2）第二章知识点及主要知识）第二章知识点及主要知识：本章介绍了顺序表、顺序串的结构、数据类型、基本运算及相关应用。 顺序表是一种具有线性逻辑结构、顺序存储结构的数据集合，它的一些基 本运算包括初始化表、求表长、查找表中元素、插入元素及删除元素等。其中， 实现顺序表的插入与删除运算时要大量移动元素，算法的时间复杂度为 O(n)。 顺序串是顺序表的一个特列
3、。其特别之处在于组成顺序串的数据元素是一组字 符。 顺序串的运算主要是针对字符串来进行的，其基本运算大多数都比较简单， 只有“子串定位” （串的模式匹配）运算较为复杂。模式匹配时各种串处理系统 中重要的操作之一，本章介绍了模式匹配的简单算法思想。本人掌握知识情况及分析本人掌握知识情况及分析：通过对这一章的学习，对于顺序表的概念、生成算法理解较为清晰，并且 熟悉简单顺序查找和二分查找，不过对于分块查找较为含糊；在排序问题中， 因为冒泡排序在大一 C 语言课上已经学习过了，再来学习感觉很轻松。对于插 入排序和选择排序理解的不错，但是，在实际运用中仍然出现明显不熟练的现 象。在学习归并排序过程中感觉
4、较吃力，现在对这种排序方法仍然非常模糊， 所以需要花较多的时间来补习。此外串的模式匹配也是我较难理解的一个内容。（3 3）第三章知识点及主要知识：）第三章知识点及主要知识：本章介绍了几种链表的结构、数据类型、基本运算及相关的应用。 单链表是一种简单、常用的数据结构。与顺序表相比，其插入、删除结点 不需要移动元素，且不必事先估计存储空间的大小。所以，应用链表来完成多 项式相加、有序表的归并及箱子排序等运算，其时间性能较好。 对单链表中的每个结点增加一个指向其前驱结点的指针域就构成了双向链 表。双向链表的插入操作有前插和后插之分，其操作过程较单链表的复杂、灵 活。 链串是链接存储的字符串。若每个字
5、符占用一个结点空间，链串的存储空 间浪费较大；且由于对字符串的操作通常不是针对单个字符进行，所以链串中 的每个结点一般存放多个字符，称为块链串。本章介绍了在结点大小为 1 的的 链块串上实现的串匹配算法，算法的时间复杂度与顺序串上的串匹配算法相同。本人掌握知识情况及分析：本人掌握知识情况及分析：通过对这一章的学习，对于单链表的概念理解的不错了，并且学会了有关 单链表的基本算法，但在双向循环链表这一块知识点上，感觉理解有点困难， 在这一方面还需加强（4 4）第四章知识点及主要知识：）第四章知识点及主要知识：本章介绍了栈及其相关应用。 栈是一种运算受限制的线性结构，遵守“先进后出”的规则，其插入与
6、删 除操作都在栈顶进行。顺序存储和链接存储的栈分别被称为顺序栈和链栈。不 同的存储结构决定了各种运算实现方法的不同。 在对栈的逻辑结构、存储结构及基本运算介绍的基础上，本章重点介绍了 栈的一些基本应用。栈作为一类重要的数据类型，被广泛应用各种程序设计中。 本章选取了一些典型的应用问题。分别进行了问题分析，提出了算法思想，并 给出了解决问题的算法实现过程，供读者在学习和工作中借鉴使用。本人掌握知识情况及分析：本人掌握知识情况及分析：通过这一章学习，认识了一种新的线性结构-堆栈，有关堆栈的知识，除 有关算法较为特殊以外，新的知识点比较少，因为其余算法都在先前学过的顺 序表和链表中遇到过，并且学这一
7、新知识点时比较重视，所以对这部分内容学 的还是很不错的，只是仍然在算法的性能分析上有所不足。（5 5）第五章知识点及主要知识：）第五章知识点及主要知识：本章介绍了队列及其相关应用。 队列是一种运算受限制的线性结构，遵守“先进先出”的规则，其插入在 队尾、删除在对头。顺序存储和链接存储的队列分别被称为顺序队列和链队列。 由于不断有出队运算，使得顺序队列出现“假溢出”现象，为了避免这种现象发生，同时也为了节省存储空间，我们提出了循环队列的概念。队列的不同存 储结构决定了各种运算的实现方法的不同。 在对队列的逻辑结构、存储结构及基本运算介绍的基础上，本章介绍了队 列的一些基本应用。队列作为一类重要的
8、数据结构，被广泛应用于各种实际问 题解决及程序设计中。本人掌握知识情况及分析：本人掌握知识情况及分析：通过这一章的学习，又认识了一个新的线性结构-队列，并且队列与堆栈 一样，都是运算受限制的线性结构，新的知识点也不多， ，与堆栈基本算法在思 想上大同小异，只要注意它的出对和入队就行。但对于循环队列还有一些小模 糊，腾出时间来把书好好看一看，应该会有所好转。（6 6）第六章知识点及主要知识：）第六章知识点及主要知识：本章在介绍数组的概念和存储的方法的基础上，重点介绍了矩阵的存储及 应用，以及广义表的相关概念。 矩阵广泛应用于科学与工程计算问题中，通常采用二维数组来存储矩阵。 在数值计算过程中，经
9、常出现一些阶数很高、但其数据元素分布具有一点规律 的矩阵，我们称这样的矩阵为特殊矩阵，包括对称矩阵、三角矩阵、对角矩阵 和稀疏矩阵。本章介绍了这些特殊矩阵的存储方法，并重点介绍了稀疏矩阵的 存储及应用。 尽管广义表是线性表的一种推广，但它并不是线性表。本章在介绍了广义 表的相关概念的基础上，介绍了广义表的存储结构。广义表浓缩了线性表、数 组等常见数据结构的特点，在有效利用存储空间方面更胜一筹，目前在文本处 理、人工智能、代数操作和计算机图形等各领域都具有应用价值。本人掌握知识情况及分析：本人掌握知识情况及分析：通过这一章的学习，对于矩阵的存储理解的比较好，但对于矩阵的应用确 感觉有点吃力，对于
10、书本上的关于矩阵转置算法的 C 语言描述也不太理解。在 稀疏矩阵相加算法中，用三元组表实现时比较容易理解，但对于十字链表进行 矩阵相加的方法还是感觉有点吃力的。（7 7）第七章知识点及主要知识：）第七章知识点及主要知识：本章主要内容有二叉树的概念，二叉树的有关性质，两种特殊的二叉树 （完全二叉树和满二叉树） ，二叉树的两种存储结构（顺序存储结构、链式存储 结构） ， 二叉树的遍历的递归算法和非递归算法，线索化二叉树算法，二叉树中叶子个 数的统计，二叉树的深度计算等。这些基本问题和基本算法是学习的要点。在 此基础上，本章列出的二叉树应用问题，如表达式求值、哈夫曼树和哈夫曼编 码问题、二叉排序树、
11、堆和堆排序等问题。本人掌握知识情况及分析：本人掌握知识情况及分析：通过对本章的学习，接触到了本书的一个重点内容-二叉树，由于老师上 这章之前说过这部分内容的重要性，所以引起了足够的重视，但却也有一些内容没有完全理解。比如在第一节基本概念中，二叉树的性质 4 就没有完全理解， 还有一些其他的小内容也是如此。但对二叉树的存储结构和遍历算法这部分内 容掌握较好，能够熟练运用，并且对于二叉树应用中的哈弗曼树也比较熟练。（8 8）第八章知识点及主要知识：）第八章知识点及主要知识：树在二叉树的基础上做了更为一般化的扩展，而森林是树的集合。 树或森林与二叉树之间有一个自然的一一对应关系。任何一个森林或一颗
12、树可以唯一地对应到一颗二叉树；反之，任何一颗二叉树也能唯一对应到一个 森林或一棵树。 数的常用存储结构包括双亲表示法、孩子表示法和孩子兄弟表示法 3 种。 对一棵树，按某种次序访问其中每一个结点一次且仅一次的过程称为树的 遍历。树有两种遍历方法：先序遍历和后序遍历。同样的森林也有两种遍历方 法：先序遍历和中序遍历。 本章还介绍了树的一种典型应用B 树。它是一种平衡的多路查找树。 本书给出了在 B 树中查找、插入和删除关键字的算法。本人掌握知识情况及分析：本人掌握知识情况及分析：通过对该章的学习，学到了树和森林相关知识，其实本章也是第七章的扩 展，因为树是在二叉树的基础上做了更为一般化的扩展，而
13、森林是树的集合。 但也有些特殊的地方。在第一节基本概念中，树和森林的性质很容易懂。对于 树和森林的存储结构和遍历算法这部分内容掌握也较好，其中对于递归思想的 运用比较多。对于孩子兄弟表示法也理解的不错，只是在运用时有时会出现一 些错误。对于 B 树的掌握还不太熟练，有待进一步加强。（9 9）第九章知识点及主要知识：）第九章知识点及主要知识：散列结构是一种查找效率很高的一种数据结构。它是一种特殊的数据结构， 表中各元素之间没有直接的关系。散列和冲突处理是散列法中最重要的两个概念。 常用的散列函数有直接定址法、除留余数法、数字分析法、平方取中法和 折叠法等。一个好的散列函数应该是一个均匀的散列函数
14、。 由于散列法的自身特点，冲突的发生时不可避免的。当不同关键字的结点 映射到相同的存储地址时，必须采用某种措施进行处理，才能保证散列法德正 常执行。常用的冲突处理方法分为开放定址法和链地址法两大类，其中开放定 址法还可以分为线性探测再散列、二次探测再散列和伪随机探测再散列 3 中方 式。开放定址法操作简单，节约空间，但容易引起“二次聚集” 。链地址法可以 从根本上杜绝二次聚集，但操作繁琐，空间占用大。本人掌握知识情况及分析：本人掌握知识情况及分析：通过本章的学习，接触到了一个新的数据结构-散列结构，在这一章内容 中，理解比较完善的知识点有：基本概念和存储结构。散列函数中直接定址法 和除留余数法
15、学得还不错，但对于数字分析法等方法则感觉比较棘手。能够理 解两种冲突处理的算法思想，但在用 C 语言描述时会有点吃力。（1010）第十章知识点及主要知识：）第十章知识点及主要知识：本章介绍了图的概念及其应用，是本书的重点。 图是一种较线性表和树更为复杂的数据结构。一个图中任意两个元素都可 以是相关，即每个元素可以有多个前驱和多个后继。 图可以分为有向图和无向图。图中的数据元素称为顶点。有向图中顶点之 间的关系称为弧，无向图中顶点的关系称为边。 图的存储结构的知识点有：邻接矩阵、邻接表、逆邻接表、十字链表和邻 接多重表。 图的遍历包括图的深度优先搜索遍历和广度优先搜索遍历。深度优先搜索 类似树的
16、先序遍历，广度搜索类似树的层次遍历的过程。 通过遍历算法可以检测树的连通性。对于连通图可以相应的生成深度优先 生成树和广度优先生成树。 其余知识点有：生成树和森林、最短路径问题和有向无环图及其应用。有 向无环图重点理解 AOV 网和拓扑排序及其算法。本人掌握知识情况及分析：本人掌握知识情况及分析：通过对这一章的学习，对于图的定义理解的比较好，因为之前的离散数学 中学习过，现在学习起来就非常轻松了，但对于基本运算如图的生成等起初理 解有困难，但随着学习深入，对它的概念也逐步明朗起来。邻接矩阵、邻接表 和逆邻接表掌握较好，而对十字链表和邻接多重表则较难理解。起初对于图的 遍历（包括深度和广度优先遍历）有些概念上的模糊，但拿了几个题目练习之 后，也理解的不错了，但对于最小生成树问题还是比较难理解的。最短路径和 AOV 网学习起来感觉比较轻松，但用 C 语言描述的话却又感觉不怎么轻松了。 二、学习体会二、学习体会这门课程的教材非常好，由于是老师自己编写的教材，对教材有着深刻的 理解，上课时能够将问题讲述得非常清晰，还能够联系实际应用，而不是简单
