数据结构与算法设计的关系

《数据结构与算法设计的关系》由会员分享，可在线阅读，更多相关《数据结构与算法设计的关系（5页珍藏版）》请在金锄头文库上搜索。

1、数据结构与算法设计的关系1. 数据结构研究的内容那么,什么是数据结构呢?要弄清数据结构，就应先弄清数据的概念.所谓数据，就是指人们利用文字符号，数字符号以及其他规定的符号对现实世 界的事物及其活动所做的抽象描述.例如，日常生活中使用的各种文字,数字和 特定符号都是数据.从计算机的角度来看,数据是所有能被输入到计算机中，且 能被计算机处理的符号的集合.它是计算机操作的对象的总称,也是计算机处 理信息的某种特定的符号表现形式.数据结构是指数据以及相互之间的联系，可以看作是相互之间存在着某种特 定关系的数据元素的集合，因此，可以把数据结构看成是带结构的数据元素的 集合.数据结构包括一下几个方面：(1

2、) 数据元素之间的逻辑关系，即数据的逻辑结构(2) 数据元素及其关系在计算机存储中的存储方式,即数据的存储结构, 也称为数据的物理结构.(3) 施加在数据上的操作，即数据的运算.因此,数据结构是一门讨论描述现实世界实体的数学模型(通常为非数值计算)及 其之上的运算在计算机中如何表示和实现的科学.常用的数据结构有：数组(Array)在程序设计中，为了处理方便，把具有相同类型的若干变量按有序的形式组 织起来。这些按序排列的同类数据元素的集合称为数组。在C语言中，数组属于 构造数据类型。一个数组可以分解为多个数组元素，这些数组元素可以是基本数 据类型或是构造类型。因此按数组元素的类型不同，数组又可分

3、为数值数组、字 符数组、指针数组、结构数组等各种类别。栈(Stack)是只能在某一端插入和删除的特殊线性表。它按照后进先出的原则存储数据， 先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹 出数据(最后一个数据被第一个读出来)。队列(Queue)一种特殊的线性表，它只允许在表的前端(front)进行删除操作，而在表的 后端(rear)进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称 为队头。队列中没有元素时，称为空队列。链表(Linked List)是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是 通过链表中的指针链接次序实现的。链表由一系列结

4、点(链表中每一个元素称为 结点)组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储 数据元素的数据域，另一个是存储下一个结点地址的指针域。树(Tree)是包含n (n0)个结点的有穷集合K，且在K中定义了一个关系N，N满足 以下条件：(1) 有且仅有一个结点k0，他对于关系N来说没有前驱，称K0为树的根 结点。简称为根(root)。(2) 除K0外，k中的每个结点，对于关系N来说有且仅有一个前驱。(3) K中各结点，对关系N来说可以有m个后继(m=0)。图(Graph)图是由结点的有穷集合V和边的集合E组成。其中，为了与树形结构加以区 别，在图结构中常常将结点称为顶点，边是顶点的

5、有序偶对，若两个顶点之间存 在一条边，就表示这两个顶点具有相邻关系。堆(Heap)在计算机科学中，堆是一种特殊的树形数据结构，每个结点都有一个值。通 常我们所说的堆的数据结构，是指二叉堆。堆的特点是根结点的值最小(或最大)， 且根结点的两个子树也是一个堆。散列表(Hash)若结构中存在关键字和K相等的记录，则必定在f(K)的存储位置上。由此， 不需比较便可直接取得所查记录。称这个对应关系f为散列函数(Hash function)， 按这个思想建立的表为散列表。2. 算法设计研究的内容数据元素之间的关系有逻辑关系和物理关系，对应的运算有逻辑结构上的运 算功能和具体存储结构上的运算实现.把具体存储

6、结构上的运算实现过程成 为算法.确切的说,算法是对特定问题求解步骤的一种描述,它是指令的有限序列，其中 每一条指令表示计算机的一个或多个操作.一个算法局域一下5个重要的特 性：有穷性算法的有穷性是指算法必须能在执行有限个步骤之后终止确切性算法的每一步骤必须有确切的定义；输入一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输 入是指算法本身定出了初始条件；(4) 输出一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输 出的算法是毫无意义的；(5) 可行性算法中执行的任何计算步都是可以被分解为基本的可执行的操作步，即 每个计算步都可以在有限时间内完成。算法设计与分析的基本方

7、法有1. 递推法递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。它 把问题分成若干步，找出相邻几步的关系，从而达到目的，此方法称为递推 法。2. 递归递归指的是一个过程：函数不断引用自身，直到引用的对象已知3. 穷举搜索法穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验， 并从众找出那些符合要求的候选解作为问题的解。4.贪婪法贪婪法是一种不追求最优解，只希望得到较为满意解的方法。贪婪法般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须 耗费的大量时间。贪婪法常以当前情况为基础作最优选择，而不考虑各种可 能的整体情况，所以贪婪法不要回溯。5. 分治法分治

8、法是把一个复杂的问题分成两个或更多的相同或相似的子问题，再 把子问题分成更小的子问题直到最后子问题可以简单的直接求解，原问 题的解即子问题的解的合并。6. 动态规划法动态规划是一种在数学和计算机科学中使用的，用于求解包含重叠子问 题的最优化问题的方法。其基本思想是，将原问题分解为相似的子问题，在 求解的过程中通过子问题的解求出原问题的解。动态规划的思想是多种算法 的基础，被广泛应用于计算机科学和工程领域。7. 迭代法迭代法是数值分析中通过从一个初始估计出发寻找一系列近似解来解决 问题（一般是解方程或者方程组）的过程，为实现这一过程所使用的方法统 称为迭代法。算法设计应满足一下的目标：1. 正确

9、性2. 可使用性3. 可读性4. 健壮性5. 高效率和低存储量需求人们在对算法进行分析时，通常包括对算法的效率和空间的分析，随着计算机 硬件的发展，存储空间对计算机越来越充裕，算法的空间效率相比于时间效率 更显次要.算法有两种衡量算法效率的方法:时候统计法和事前分析估计法.前者的缺点： 一是必须执行程序;而是存在其他因素掩盖算法本质.所以通常人们更多的采 用的是事前分析估计法来分析算法效率.一个算法用高级语言实现后,在计算 机上运行时所消耗的时间与很多因所有关，如计算机的运行速度，编写程序采 用的计算机语言,编译陈胜的机器语言代码质量和问题的规模等.在这些因素 中,前三个都与具体的机器有关.撇

10、开这些与计算机硬件，软件有关的因素,仅考 虑算法本事的效率高低，可以认为一个特定算法的运行工作量的大小只依赖 于问题的规模，即算法的复杂度.关于时间复杂度：（1）时间频度一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试 才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个 算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的 时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花 费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T（n）。（2）时间复杂度在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频 度

11、T（n）也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用 T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极 限值为不等于零的常数，则称f(n)是 T(n)的同数量级函数。记作T(n)=O(f(n), 称O(f(n)为算法的渐进时间复杂度，简称时间复杂度。在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为0(1), 另外，在时间频度不相同时，时间复杂度有可能相同，如T(n)=nA2+3n+4与 T(n)=4nA2+2n+1它们的频度不同，但时间复

12、杂度相同，都为0(nA2)o按数量级递增排列，常见的时间复杂度有：常数阶0(1),对数阶O(log2n)(以2为底n的对数，下同),线性阶0(n), 线性对数阶O(nlog2n),平方阶0(nA2)，立方阶0(nA3),.，k次方阶O(nAk),指数阶0(2An)。随着问题规模n的不断增大，上述时间复杂 度不断增大，算法的执行效率越低。3. 二者之间的联系与区别算法的设计取决于数据(逻辑)结构，而算法的实现依赖于采用的存储结构。数据的存储结构实质上是它的逻辑结构在计算机存储器中的实现，为了全面 的反映一个数据的逻辑结构，它在存储器中的映象包括两方面内容，即数据 元素之间的信息和数据元素之间的关

13、系。不同数据结构有其相应的若干运算。 数据的运算是在数据的逻辑结构上定义的操作算法，如检索、插入、删除、 更新和排序等。数据的运算是数据结构的一个重要方面，讨论任一种数据结构时都离不开开 对该结构上的数据运算及其实现算法的讨论。数据结构对算法的影响主要有两个方面：(1) 数据结构的存储能力(2) 定义在数据结构上的运算通过对求解问题进行分析,在选择数据结构需要考虑一下几个方面：(1) 数据结构要适应问题的状态描述(2) 数据结构应与所选择的算法相适应(3) 数据结构的选择同时要兼顾程序设计的方便(4) 灵活应用已有知识4. 举例数据结构+算法=程序程序设计的本质是对要处理问题选择好的数据结构，

14、同时在此结构上施加一 种好的算法.举例：试写一个算法，将一个头结点指针为a的单链表A分解成两个单链表A 和B，其中头结点指针分别为a和b，使得A链表中含有原链表A中序号为 奇数的元素，而B链表中含有原链表中序号为偶数的元素，并保持原来的相 对顺序。分析：根据题目要求，需要遍历整个链表A，当遇到序号为偶数的 结点时，先将其删除，并在删除时把这些结点链接到B表中，一直到遍历结 束。其实现算法如下：void split(LinkList a,LinkList b) /按序号奇偶分解单链表LinkNode *p,*q,*r;p=a;b=a-next; /第一个偶数号结点连接到B表上 r=b; /r指向B表的当前尾结点while(p!=NULL & p-next!=NULL)q=p-next; /q指向偶数序号的结点p-next=q-next;/将 q 从愿 A 中删除r-next=q;/将q结点连接到B链表的末尾r=q;/r总是指向B链表的最后一个结点p=p-next;/p指向原链表A中奇数序号的结点r-next=NULL;这个算法要从头至为尾扫描整个链表，所以它的时间复杂度是O(n)。5. 参考文献算法导论算法设计与分析数据结构教程