数据结构与算法分析总结.docx
《数据结构与算法分析总结.docx》由会员分享,可在线阅读,更多相关《数据结构与算法分析总结.docx(7页珍藏版)》请在三一办公上搜索。
1、数据结构与算法分析总结数据结构和算法设计与分析 谈到计算机方面的专业课程,我觉得数据结构算是一门必不可少的课了,它是计算机从业和研究人员了解、开发及最大程度的利用计算机硬件的一种工具。数据结构与算法分析是两门紧密联系的课程,算法要靠好的数据结构来实现,二者的关系是密不可分的,谈到算法不得不讲数据结构,谈数据结构也不可避免的要了解算法,好的算法一定有一个好的数据结构,很多算法实际上是对某种数据结构实行的一种变换,研究算法也就是研究在实行变换过程中数据的动态性质。这两门课程分别是我在大二和研一的时候学的,因为它们密切的联系,这里将其放在一起总结如下。 什么是数据结构呢?研究数据的逻辑结构和存储结构
2、以及它们之间的关系,且为该结构定义相应的运算设计相应的算法。这里的数据是指可输入到计算机能被程序处理的符号的集合。其中,数据的逻辑结构是指数据之间逻辑关系的描述,逻辑结构的分类有线性结构、树形结构和图结构。数据的存储结构是指数据在计算机中存储结构,也称为物理结构,它有4类基本的存储映射方法:1.顺序的方法;2.链接的方法;3.索引的方法;4.散列的方法。在程序设计语言中,数据结构直接反映在数据类型上,比如一个整型变量就是一个节点,根据类型给他分配内存单元。抽象数据类型:一组值以及在这些值上定义的操作集合,它是描述数据结构的一种理论工具,其特点是把数据结构作为独立于应用程序的一种抽象代数结构。
3、线性表结构:由一系列元素组成的有序的序列,除了第一个元素和最后一个元素外,每个元素都只有一个直接前趋和直接后继,元素的个数称为线性表的长度。它的存储方式有顺序存储和链式存储。顺序存储方式它的优点是存储单元是连续的,适合快速访问元素内容,链表的特点是动态申请内存空间,并通过指针来链接结点,按照线性表的前驱关系把一个个结点链接起来,这样可以动态地根据需要分配内存空间,经常用于插入新结点或删除节点的需要,链表还可以根据结点中指针个数分为单链表、双链表、循环链表等。在线性表结构中有两类特别的线性表:栈和队列。栈是一种限制访问端口的线性表,常称为后进先出表。正是这种特殊的性质使得栈的用途非常广泛,比如在
4、计算表达式的值时处理运算符的先后次序,另外一个大的用处就是递归了,hanoi 塔就是最典型的用了递归的思想,在算法中,也有很多运用递归思想的例子。队列也属于限制访问点的线性表,它的特点就是加入和删除元素都只能在队列的一端进行,即队列首出,队列尾进,最大的特点是先来先服务,先进先出。因为这个特点,队列常被用作消息缓冲器。 在算法设计中,顺序表主要用于检索,而利用栈中的递归思想在算法中则应用非常广泛,如递归排序,分治算法等。 树结构:是一种非常重要的非线性数据结构,它是由一个根结点和若干叶结点组成的树状结构,除了根结点每个结点只能有一个父节点,可以有若干子结点,若干个树结构还可以构成森林,树的存储
5、结构也分为顺序存储和链式存储,最典型的是左孩子右兄弟法。在树结构中比较重要的算法就是周游树,有先根次序、后根次序以及中根次序。树结构中有几类非常重要的特殊树结构,如二叉树,B树,B+树等,其中,二叉树应用最为广泛。 二叉树:是指每个结点最多有两个子结点的树结构,具体细分,根据叶子结点的特性可分为满二叉树、完全二叉树等。二叉树的遍历也分为深度优先和广度优先。另外,二叉树有几条非常重要的性质,这也使得它的应用非常广泛。 在算法设计中,典型的利用树的深度优先遍历的算法是回溯法,而典型的广度优先搜索算法是分枝定界法。 图:是一种较线性表和树更为复杂的数据结构。一般来讲,数据的逻辑结构可表示为结点的有穷
6、集合K和K上的一个关系r,如果对K中结点相对于r的前驱、后继个数加以限制,则可以分别定义线性结构、树形结构和图结构,即: 线性结构:惟一前驱,惟一后继,反映一种线性关系; 树形结构:惟一前驱,多个后继,反映一种层次关系; 图结构:不限制前驱的个数,亦不限制后继的个数,反映一种网状关系。 通常用G=(V,E)代表一个图,其中V是顶点集,E是边集。图分为有向图和无向图,图的存储方式有邻接表和邻接矩阵法。和树类似的,图中也需要周游,同样有深度优先搜索和广度优先搜索,而比树的周游要更复杂,也更重要。在这一块中,有两种比较典型的求最短路径和最小支撑树的算法需要注意,它们分别是Dijkstra算法和Pri
7、m算法。另外需要注意的是图的连通性。 在算法设计中,典型的用到图论的算法有贪心算法和动态规划算法。 对于计算机科学来说,算法的概念至关重要。通俗的讲,算法是指解决问题的一种方法或一个过程,或者严格来讲,是由若干条指令组成的有穷序列,且满足以下4条性质; 输入:有零个或多个由外部提供的量作为算法的输入。 输出:算法产生至少一个量作为输出。 确定性:组成算法的每条指令是清晰的,无歧义的。 有限性:算法中每条指令的执行次数是有限的,执行每条指令的时间也是有限的。 我们研究一个算法或者评价一个算法主要是通过估计该算法的复杂性,包括时间复杂性和空间复杂性。空间复杂性是指使用该算法的程序在运行时需要占用多
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 算法 分析 总结
链接地址:https://www.31ppt.com/p-3560147.html