数据结构中经典算法分析

来源 :外语学法教法研究 | 被引量 : 0次 | 上传用户:wsh2000
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
  摘要:计算机数据结构是计算机从业和研究人员了解、开发及最大程度的利用计算机硬件的一种工具,数据结构与算法分析是两门紧密联系的学科,算法要靠好的数据结构来实现,二者的关系是密不可分的。本文主要对数据结构算法进行了研究,就经典算法展开了讨论,期望能对读者有所帮助。
  关键词:数据结构;算法;软件设计
  【中图分类号】TP311.12-4;G642
  一、数据结构与算法概述
  1.1数据结构
  数据结构是一门研究数据的逻辑结构和存储结构(物理结构)以及它们之间的关系的学科,且为该结构定义相应的运算设计相应的算法。这里的数据是指可输入到计算机能被程序处理的符号的集合。其中,数据的逻辑结构是指数据之间逻辑关系的描述,逻辑结构的分类有线性结构、树形结构和图结构。数据的存储结构是指数据在计算机中存储结构,也称为物理结构,在程序设计语言中,数据结构直接反映在数据类型上,比如一个整型变量就是一个节点,根据类型给他分配内存单元。
  1.2算法
  1.2.1算法是由基本运算及规定的运算顺序所构成的完整的解题步骤。计算机算法与数据结构之间的关系,算法最终依附于数据结构,数据结构直接影响算法的选择和运行效率。运算是计算机完成的,这就要设计计算机在操作时对相的一些操作模式,如插入、删除和修改的算法。也就是说,数据结构还需要给出每种结构类型所定义的各种运算的算法。
  1.2.2算法与数据结构研究的目的简单地说就是优化代码,提高程序执行效率。比如,把一堆无顺的数据通过一个算法实现顺序排列实现方法太多太多,但是也许运行速率最快的占用的存储空间很大也许运行速率不是很快的占用的存储空间却很小,所以要通过算法与数据结构分析。
  二、数据机构经典算法的选择
  选择经典算法的重要性,PASCAL语言的创始人、著名的计算机科学家N.沃思说得好“程序=数据结构+算法”,足以见得算法在程序设计中的重要地位。在合理的数据结构基础上,算法是对数据结构的操作(运算),是数据处理的核心。数据结构中所讲的基本数据结构有线性表、堆栈、队列、数组、树、二叉树、图以及相应的算法。一个算法是建立在某种数据结构的基础上,一个算法不可能脱离数据结构而孤立存在。只有通过分析算法,才能真正掌握某种数据结构。一个经典算法往往能起到以一当十、以点带面的关键作用。选择好经典算法后下一步就是要对其展开综合分析,下面以具体的算法为例进行讨论。
  三、利用经典算法说明基本原理
  3.1经典算法应能体现某个数据结构的基本特征
  我们知道线性表顺序存储时其优点是能够对每个数据元素随机访问,存储密度高,其缺点是插入、删除操作时需要移动大量的数据元素,操作效率低。“向有序(由小到大或由大到小)的线性表(顺序存储)插入一个新的数据元素”,这一经典算法集中反映了线性表顺序存储的这些特点。
  分析:将一个值为X的数据元素插入到有序(由小到大或由大到小)的线性表(顺序存储)中,可以分两步进行,首先查找到值为X的数据元素在线性表中应有的位置,采用从头到尾循环比较的方法确定其位置I,然后,将第I个以后的全部数据元素向后移动一个存储单元,最后将值为X的数据元素存放到第I个位置上,线性表元素个数增1。
  【算法1】
  PROCEDUREINSERT(V,m,n,X)
  //将值为X的数据元素插入到V数组中,(线性表顺序存贮在V中)m为最多元素个数,n为当前实际元素个数IF(m=n)THEN{“OVERFLOW”;RETURN}FORI=1TOnDO
  IF(X〈V(I))THENBREAK
  FORJ=nTOIBY-1DOV(J+1)=V(J)V(I)=X
  n=n+1
  RETURN
  分析:【算法1】的优点是简单,便于理解,缺点是:①循环体内有提前退出语句,不利于结构化程序设计;②确定新数据元素位置和移动数据元素分两步进行,有重复操作,可以改进之,将两步合并一步完成,即将循环比较与移动数据元素同时进行。从线性表的尾部开始向前循环比较,比新数据元素大者后移,直到小于等于时停止。
  【算法2】
  PROCEDUREINSERT(V,m,n,X)
  IF(m=n)THEN{“OVERFLOW”;RETURN}
  I=n
  WHILE(I〉=1)AND(V(I)〉X)DO{V(I+1)=V(I);I=I-1}V(I+1)=X
  n=n+1
  RETURN
  分析:注意【算法2】中循环条件,当循环结束后I=0或V(I)〈=X,新数据元素的位置为I+1,【算法1】的时间复杂度为0(2n),而【算法2】的时间复杂度为0(n),效率提高一倍。循环结构是结构化程序设计中最基本最核心的部分,归纳循环条件是关键。【算法2】能进一步推广。
  3.2利用经典算法学习算法设计
  经典算法能给学习者以启示、示范作用。分析:可以将【算法2】用于对线性表(顺序存储)排序算法中。在直接插入排序算法中,其算法思想是从第2个数据元素开始直到第n个数据元素,逐一插入到已有序的子线性表中。【算法3】
  PROCEDURESORT(V,n)
  FORI=2TOnDO
  {Y=V(I)
  J=I-1
  WHILE(J〉=1)AND(V(J)〉Y)DO{V(J+1)=V(J);J=J-1}V(J+1)=Y}
  RETURN
  分析:【算示3】其结构分为双重循环,外循环完成逐一取数据元素,即取第I个数据元素,内循环完成将第I个数据元素插入到前I-1个已有序的子线性表中。内循环完成的功能可以独立成为一个子函数(子过程),可以借用【算法2】。这正是结构化程序设计思想的体现,即主程序完成任务的划分,说明“做什么”,子函数(子过程)完成任务的具体实现,说明“如何做”。结构化程序设计方法采取“分解”的手段来控制系统的复杂性,将大系统划分为若干个相对独立的、功能单一的子模块。一方面子函数(子过程)可以实现软件的重用性,在不同的程序段有相同的处理过程时调用子函数(子过程),减少软件开发的工作量;另一方面子函数(子过程)对具体的实现技术细节进行隐藏,便于开发人员集中精力把握软件开发的核心和主要问题,降低了软件开发难度,从而保证软件质量。
  四、结束语
  对于计算机科学来说,算法的概念至关重要。通俗的讲,算法是指解决问题的一种方法或一个过程,在众多的算法中选择好少量的经典算法对于研究数据结构以及解决实际问题至关重要。掌握好经典算法的原理和规律,将对计算机程序设计开发起到事半功倍的作用。
  参考文献:
  [1]邓建龙.计算机软件基础数据结构之算法[J].信息与电脑:理论版,2012,(6).
  作者简介:赵梦龙(1981年12月21日),男,河南驻马店市,硕士研究生,讲师,信息安全与密码学
其他文献
<正> 当今的教育体系中要实现由应试教育向素质教育转轨教师素质起决定的作用,只有高素质的教师,才能有力推动素质教育的全面实施,只有具有创新意识和创新精神的教师,才能不
点评:SD和USB直接播放是目前音箱市场上非常热门的功能,HY-740Ⅱ增加了SD卡直接播放的功能,能够满足更多应用场合的使用需求,显得非常实用。
运用Logistic曲线分析了系统的一般发展过程,根据其发展速度将发展过程分为起步、成长、成熟和饱和四个时期,并结合可持续发展的内涵与实质,提出了可持续发展理论的数学依据和数
有同志问我,延安的新闻传统是什么? 这问题本应老一辈的新闻工作者来回答;我虽在延安生活过,我属晚辈,不一定能说准。在纪念《陕西日报》创刊五十周年之际,我有责任谈出自己
互联网+时代的到来,改变了中国的现状,给为中国带了技术革命,为中国带来了巨大的收益,为民众提供了便利和快捷的生活,改变了人们的生活方式。显然在带来便利的同时,对古老的公证行业产生了冲击,相对保守的公证行业在时代来临时并没有准备好,其提供的保全证据方式和方法已经不能满足民众的保全需求,技术的落后、人才的匮乏、思想的保守制约公证的发展,如何在新的环境下保全公证再出发,需要公证人加强努力学习和探索。本文
黑油模型是油藏模拟问题的典型数学模型,它由多个非线性偏微分方程耦合而形成,其快速数值求解是科学与工程计算的热点之一。在黑油模型的数值求解中,线性代数方程组的求解占整
本文对32例乙型肝炎患者及正常人外周血T淋巴细胞亚群,可溶性白细胞介素-α受体(sIL-2R)水平进行了检测,结果表明乙型肝炎患者T淋巴细胞亚群变化与sIL-2R水平有一定关系。
环境保护部向媒体公布了今年“六&#183;五”世界环境日中国主题为“绿色奥运与环境友好型社会”,同时还发布了主题标识。环境保护部要求各地围绕中国主题,以宣传“办绿色奥运,促
随着北京轨道交通网络的高速发展,在地铁明挖基坑围护施工时,往往会遇到砂卵石土层中钻孔桩成孔工艺优选问题,砂卵石土层中钻孔桩成孔工艺的选择是地铁明挖基坑围护施工成败的关
去年这个时候,中宣部在北京举办了省级报纸总编辑研讨班。江泽民、李瑞环同志关于新闻工作的指导方针问题发表了重要讲话。一年来,新闻战线取得了很大的成绩。特别是坚持正面