《数据结构与算法分析总结.pdf》由会员分享，可在线阅读，更多相关《数据结构与算法分析总结.pdf（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构和算法设计与分析 谈到运算机方面的专业课程，我感觉数据结构算是一门必不可少的课了，它是运算机从业和研究人员了解、开发及最大程度的利用运算机硬件的一种工具。数据结构与算法分析是两门紧密联系的课程,算法要靠好的数据结构来实现,二者的关系是密不可分的,谈到算法不能不讲数据结构,谈数据结构也不可幸免的要了解算法,好的算法必然有一个好的数据结构，很多算法事实上是对某种数据结构实行的一种变换,研究算法也确实是研究在实行变换进程中数据的动态性质。这两门课程别离是我在大二和研一的时候学的，因为它们紧密的联系，那个地址将其放在一路总结如下。什么是数据结构呢？研究数据的逻辑结构和存储结构（物理结构）和它们
2、之间的关系，且为该结构概念相应的运算设计相应的算法。那个地址的数据是指可输入到运算性能被程序处置的符号的集合。其中，数据的逻辑结构是指数据之间逻辑关系的描述，逻辑结构的分类有线性结构、树形结构和图结构。数据的存储结构是指数据在运算机中存储结构，也称为物理结构，它有 4 类大体的存储映射方式：1.顺序的方式；2.链接的方式；3.索引的方式；4.散列的方式。在程序设计语言中，数据结构直接反映在数据类型上，比如一个整型变量确实是一个节点，依照类型给他分派内存单元。抽象数据类型：一组值和在这些值上概念的操作集合，它是描述数据结构的一种理论工具，其特点是把数据结构作为独立于应用程序的一种抽象代数结构。线
3、性表结构：由一系列元素组成的有序的序列，除第一个元素和最后一个元素外，每一个元素都只有一个直接前趋和直接后继，元素的个数称为线性表的长度。它的存储方式有顺序存储和链式存储。顺序存储方式它的优势是存储单元是持续的，适合快速访问元素内容，链表的特点是动态申请内存空间，并通过指针来链接结点，依照线性表的前驱关系把一个个结点链接起来，如此能够动态地依照需要分派内存空间，常常常利用于插入新结点或删除节点的需要，链表还能够依照结点中指针个数分为单链表、双链表、循环链表等。在线性表结构中有两类专门的线性表：栈和队列。栈是一种限制访问端口的线性表，常称为后进先出表。正是这种特殊的性质使得栈的用途超级普遍，比如
4、在计算表达式的值时处置运算符的前后顺序，另外一个大的用途确实是递归了，hanoi 塔确实是最典型的用了递归的思想，在算法中，也有很多运用递归思想的例子。队列也属于限制访问点的线性表，它的特点确实是加入和删除元素都只能在队列的一端进行，即队列首出，队列尾进，最大的特点是先来先效劳，先进先出。因为那个特点，队列常被用作消息缓冲器。在算法设计中，顺序表要紧用于检索，而利用栈中的递归思想在算法中那么应用超级普遍，如递归排序，分治算法等。树结构：是一种超级重要的非线性数据结构，它是由一个根结点和假设干叶结点组成的树状结构，除根结点每一个结点只能有一个父节点，能够有假设干子结点，假设干个树结构还能够组成丛
5、林，树的存储结构也分为顺序存储和链式存储，最典型的是左小孩右兄弟法。在树结构中比较重要的算法确实是周游（遍历）树，有先根顺序、后根顺序和中根顺序。树结构中有几类超级重要的特殊树结构，如二叉树，B 树，B+树等，其中，二叉树应用最为普遍。二叉树：是指每一个结点最多有两个子结点的树结构，具体细分，依照叶子结点的特性可分为满二叉树、完全二叉树等。二叉树的遍历也分为深度优先和广度优先。另外，二叉树有几条超级重要的性质，这也使得它的应用超级普遍。在算法设计中，典型的利用树的深度优先遍历的算法是回溯法，而典型的广度优先搜索算法是分枝定界法。图：是一种较线性表和树更为复杂的数据结构。一样来讲，数据的逻辑结构
6、可表示为结点的有穷集合 K 和 K 上的一个关系 r,假设是对 K 中结点相关于 r 的前驱、后继个数加以限制，那么能够别离概念线性结构、树形结构和图结构，即：线性结构：惟一前驱，惟一后继，反映一种线性关系；树形结构：惟一前驱，多个后继，反映一种层次关系；图结构：不限制前驱的个数，亦不限制后继的个数，反映一种网状关系。通常常利用 G=(V,E)代表一个图，其中 V 是极点集，E 是边集。图分为有向图和无向图，图的存储方式有邻接表和邻接矩阵法。和树类似的，图中也需要周游，一样有深度优先搜索和广度优先搜索，而比树的周游要更复杂，也更重要。在这一块中，有两种比较典型的求最短途径和最小支撑树的算法需要
7、注意，它们别离是 Dijkstra 算法和 Prim 算法。另外需要注意的是图的连通性。在算法设计中，典型的用到图论的算法有贪婪算法和动态打算算法。关于运算机科学来讲，算法的概念相当重要。通俗的讲，算法是指解决问题的一种方式或一个进程，或严格来讲，是由假设干条指令组成的有穷序列，且知足以下 4 条性质；（1）输入：有零个或多个由外部提供的量作为算法的输入。（2）输出：算法产生至少一个量作为输出。（3）确信性：组成算法的每条指令是清楚的，无歧义的。（4）有限性：算法中每条指令的执行次数是有限的，执行每条指令的时刻也是有限的。咱们研究一个算法或评判一个算法主假设是通过估量该算法的复杂性，包括时刻复
8、杂性和空间复杂性。空间复杂性是指利用该算法的程序在运行时需要占用多少内存空间，具体包括指令空间、数据空间和环境栈空间。时刻复杂性是指执行该程序所需要的时刻量级，一样是估算的时刻，包括编译时刻和运行时刻。同时评判一个算法的好坏还要看其时刻复杂性和空间复杂性随着输入规模的增加趋势，一样能同意的最好是线性增加。在算法设计这本书中，每介绍一个算法都会分析其算法复杂度，由此可看出它的重要性。第一，从递归的分治算法开始。分治算法的大体思想是将一个规模为 n 的问题分解为 k个规模较小的子问题，这些子问题彼此独立且与原问题相同。递归的解这些子问题，然后将各个子问题的解归并取得原问题的解。该算法的要紧应用有大
9、整数乘法，矩阵乘法、归并排序等。能够大大降低算法的时刻复杂度，但利用递归栈可能增加程序的空间规模。动态打算算法和贪婪算法：与分治算法类似，动态打算的大体思想也是将待求解问题分解成假设干子问题，先求解子问题，然后从这些子问题的解取得原问题的解。与分治算法不同的是，适合于用动态打算法求解的问题，经分解取得的子问题往往不是彼此独立的。动态打算算法适用于解最优化问题。通常可按以下 4 个步骤：（1）找出最优解的性质，并刻画其结构特点。（2）递归的概念最优值。（3）以自底向上的方式计算出最优值。（4）依照计算最优值时取得的信息，构造最优解。动态打算算法的大体要素是最优子结构性质和子问题重叠性质。最优子结
10、构性质。假设是问题的最优解所包括的子问题的解也是最优的，咱们就称该问题具有最优子结构性质（即知足最优化原理）。最优子结构性质为动态打算算法解决问题提供了重要线索。子问题重叠性质。子问题重叠性质是指在用递归演算法自顶向下对问题进行求解时，每次产生的子问题并非老是新问题，有些子问题会被重复计算多次。动态打算算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保留在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而取得较高的效率。另外一点要素是备忘录方式，它作为动态打算算法的变形，用表格保留已解决问题的答案，在下次需要解此子问题时，只要简单
11、查看子问题的解答，而没必要从头计算。与动态打算不同的是备忘录方式的递归是自顶向下的，而动态打算那么是自底向上的。动态打算算法设计谋略典型的应用案例有：矩阵连乘、最大字段和、流水作业调度等。有时知足动态打算条件的问题能够有更好的算法，比如贪婪算法。贪婪算法即老是做出在当前看来是最好的选择。也确实是说贪婪算法并非从整体最优上加以考虑，它所做的老是做出的选择只是在某种意义上的局部最优。这种启发式的策略并非能老是奏效，可是对某些特定的问题确能达到预期目的。比如活动安排的例子。贪婪算法的大体要素要紧有贪婪选择性质和最优子结构性质。所谓贪婪选择性质是指所求问题的整体最优解能够通过一系列局部最优的选择，即贪
12、婪选择来达到。这是贪婪算法与动态打算的要紧区别，它们的一路点是都要求问题具有最优子结构性质。贪婪算法的典型案列是：活动安排、最优装载问题、最短途径和最优生成树问题。回溯法和分枝定界法：回溯法有“通用的解题法”之称。用它能够系统的搜索一个问题的所有解或任一解。它在问题的解空间树中，按深度优先策略，从根节点起身搜索解空间树。其算法框架包括递归回溯和迭代回溯，两个专门的解空间树为子集树和排列树。典型的回溯法的案例有：批处置作业调度、图的 m 着色、旅行售货员问题、0-1 背包问题等。分枝定界法类似于回溯法，也是在问题的解空间上搜索问题解的算法。一样情形下，分治定界法与回溯法的求解目标不同。回溯法的求
13、解目标是找出解空间中知足约束条件的所有 的解，而分枝定界法的求解目标那么是找出知足约束条件的一个解，或是知足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。由于求解目标不同，致使分支定界法与回溯法对解空间的搜索方式也不相同。回溯法以深度优先的方式搜索解空间，而分枝定界法那么以广度优先或以最小花费优先的方式搜索解空间。另外，在算法分析中必然要提的是 NP 问题。第一需要介绍 P(Polynomial,多项式)问题.P问 题 是 能 够 在 多 项 式 时 刻 内 被 确 信 机(通 常 意 义 的 运 算 机)解 决 的 问 题。NP(Non-Determinist
14、ic Polynomial,非确信多项式)问题,是指能够在多项式时刻内被非确信机(他能够猜,他老是能猜到最能知足你需要的那种选择,假设是你让他解决 n 皇后问题,他只要猜 n 次就能够够完成-每次都是那么幸运)解决的问题.那个地址有一个闻名的问题-千禧难题之首,是说 P 问题是不是等于 NP 问题,也即是不是所有在非确信机上多项式可解的问题都能在确信机上用多项式时刻求解。NP 完全(NP Complete,NPC)问题是指如此一类 NP 问题,所有的 NP 问题都能够用多项式时间划归到他们中的一个。因此显然 NP 完全的问题具有如下性质:它能够在内求解，当且仅当所有的其他的 NP完全问题也能够在多项式时刻内求解。如此一来,只要咱们找到一个的多项式解,所有的NP问题都能够多项式时刻内划归成那个NPC问题,再用多项式时刻解决,如此NP 就等于 P 了。小结一下，在算法设计这么课中学了这么几大类典型的算法，里面也涉及到具体的应用案例，但我感觉学算法的目的远不是学会这几种固定的特殊问题的解法算了，事实上领会这些巧妙算法背后的思想然后学会迁移到其他新的问题中去才是领会了算法设计的精华。