搜索
数据结构与算法设计第一章数据结构与算法的引入宁夏育才中学2第一章内容简介第五节数据结构中的基本术语第一节算法的描述与评价第二节Pascal语言中的数据类型第三节建立数学模型第四节程序的调试数据结构与算法设计宁夏育才中学3概论“程序=算法+数据结构”是由著名的计算机科学家沃斯（N·Writh）提出的程序公式，简明的概括了程序的组成。从中可以看出，编程解决各种各样的实际问题，只学习掌握好诸如pascal、C等程序设计语言是远远不够的，另外还必须具备数据结构和算法的相关知识。数据结构主要讲述客观世界中纷繁复杂的事物及其内在的联系如何有效地在计算机中进行表示；算法主要讲解建立在这种表示基础上的一些常用的解决实际问题的思想、方法和步骤。二者是一个相辅相成的统一体，是缺一不可的两个方面。有了它们以后，我们才能比较顺利地编写程序。宁夏育才中学4数据结构与算法的密切关系数据结构是建立在算法的基础上，而选择什么样的数据结构对于程序设计来说，是至关重要的决策，它直接影响到程序的效率。选择一个合适的数据结构便很容易形成一个简洁有效的算法；否则，如果数据结构选择不好，除了影响程序开发速度之外，更重要的是影响设计出来的程序的运行效率。概论第一节算法的描述与评价第一节算法的描述与评价宁夏育才中学6算法什么是“算法”？算法是为解决一个问题而采用的方法和步骤。或者说，算法是解题方法的精确描述，解决一个问题的过程就是实现一个算法的过程。宁夏育才中学7算法的特点1.确定性算法的每一步都必须是明确无误的，不能含糊其辞，不能存在歧义，否则就会使执行者无所适从。如计算”3/0”或”将3或4与X相乘”等是不允许的。2.有穷性、可行性一个算法必须包含有限个操作步骤，即执行若干步之后，算法能够终止，而不能无限地执行下去。当然，这种有穷性还应该在一个合理的范围之内，即在有限的时间内做完。比如一个算法要执行一万年才能得到结果，尽管它不是无限的，但显然没有什么实际意义。（可行性与确定性、有穷性是相容的。）3.有效性算法中的每一步运算都必须能够在计算机上有效地执行，整个算法执行完毕后必须得到确定的结果。例如，求-5的平方根，求所有自然数的和，就无法在计算机上有效地执行。4.有输入一个算法一般都要求0个或0个以上的输入信息，这些输入信息是算法所需的初始数据，取自某一特定的集合。5.有输出一个算法一般有一个或多个输出信息，他们通常可以被解释为“对输入的计算结果。”宁夏育才中学8算法的描述描述算法的方法，常用的有自然语言、程序流程图、N-S图、类程序设计语言和程序设计语言等。（1）用自然语言描述算法（2）用流程图来描述算法框图结构化流程图（N-S图）（3）用程序语言来描述算法宁夏育才中学9（1）用自然语言描述算法自然语言主要是通过文字或数学式来描述解决问题的过程。例如:交换X、Y的值。第一步：给X、Y分别赋初值；第二步:把X的值送给A；第三步:把Y的值送给X；第四步：把X的值送给Y；这种描述通俗易懂，但比较繁琐，容易出现二义性，对算法中的判断和转移等描述的不够直观清楚。宁夏育才中学10（2）用流程图来描述算法所谓流程图法，就是指用图形来表示程序的方法，它采用一些几何图形来代表各种性质的操作，是程序设计中广泛使用的一种辅助设计手段。流程图主要有两种模式：框图和结构化流程图（N-S图）宁夏育才中学11框图美国国家标准化协会（ANSI）制订的一套流程图符号标准：开始、终止框判断框输入/输出框处理框注释框连接点连接线输入x，y开始x→ay→xa→y输出x，y结束宁夏育才中学12顺序、选择、循环三种基本结构AB顺序结构条件满足？AB选择结构A条件满足？是当型循环A条件满足？否是直到型循环宁夏育才中学13由顺序、选择、循环这三种基本结构可以派生出其他形式的结构。由这三种基本结构所构成的算法可以处理任何复杂的问题。所谓结构化程序，就是由这三种基本结构所组成的程序。可以看到，三种基本结构都具有以下特点：①有一个入口。②有一个出口。③结构中每一部分都应当有被执行到的机会。也就是说，每一部分都应当有一条从入口到出口的路径通过它（至少通过一次）。④没有死循环（无终止的循环）。顺序、选择、循环三种基本结构宁夏育才中学14结构化流程图（N-S图）结构化流程图是美国学者I.Nassi和B.Schneiderman两个人1973年提出的，因此也称为N-S结构化流程图，它的基本成分有以下三种：①顺序结构一条简单的指令，用一个矩形框来表示顺序结构例如：交换两个变量（在框内写一条简单的指令）执行A块执行B块输入x，yx→ay→xa→y输出x，y宁夏育才中学15②选择结构③循环结构满足条件否？满足不满足执行B块执行A块While条件循环体循环体until条件当型循环直到型循环结构化流程图（N-S图）宁夏育才中学16（3）用程序语言来描述算法一个算法如果交给计算机去执行，最终是要通过程序来描述的。选择不同的语言，即使基于相同的算法，程序描述也不相同，但基本上差不多。一般采用类pascal语言来描述，即采用伪代码描述的方式。宁夏育才中学17伪代码伪代码是采用一种介于自然语言和计算机语言之间的文字和符号来描述的算法，其中的自然语言可以是英语、汉语等。例如求某数是否为负数，采用伪代码描述如下：ifx0then输出‘是’else输出‘否’采用伪代码描述的算法，其结构紧凑且易懂，写法比较灵活，没有严格的规则，只要能表达清楚算法含义即可。相比流程图，伪代码可随手写出，且容易修改。另外，伪代码的书写格式与高级程序设计语言（如Pascal、C等）非常相似，能很容易地转化为高级语言的源程序。宁夏育才中学18算法描述1.赋值语句变量名：=表达式；2.读语句read（变量名）或readln变量名表；3.写语句write（输出项）或writeln输出项；4.转向语句goto语句标号；5.调用过程语句过程名（参数表）；6.退出循环语句break；用于各种循环中，该语句被执行时，将立即退出当前循环，相当于goto到该循环语句后的第一条语句上，它是循环语句的一个非正常出口。7.返回语句exit；return或return参数；用于过程或函数体中，该语句被执行时，将立即退出当前过程或函数，返回到调用前所保存的位置继续向下执行，它是执行过程或函数的一个非正常出口。8.非正常结束程序语句halt；在程序的任何一个地方使用该语句，则立即结束程序。宁夏育才中学199.出错处理语句Error（字符串）；在算法中为了避免非法操作，需要进行出错处理时使用该语句，它表示此算法执行到此中止。在实际算法中，它可能是转去执行一个错误处理程序，也可能是简单地打印出错误信息并停止运行等。该语句括号内的字符串用以说明出错的原因，如使用字符串“overflow”表示溢出，“Outofrange”表示超出范围或越界。在程序中一般可以定义一个这样的过程来实现。10.复合语句begin语句1；语句2；……；语句n；end；11.条件语句if条件then语句1；[else语句2；]条件语句当然还可以嵌套。12.情况语句case选择表达式of常量1：语句1；常量2：语句2；……常量n：语句n；[else语句n+1]end；算法描述宁夏育才中学2013.For循环语句格式1：for变量名：=初值to终值do语句；格式2：for变量名：=初值downto终值do语句；如果格式1中初值大于终值，或格式2中初值小于终值，则都不会执行循环体。14.While循环语句while条件do语句；15.repeat/until循环语句repeat一组语句until条件；算法描述宁夏育才中学21算法的评价对于解决同一个问题，往往能够编写出许多不同的算法。例如大家所熟知的排序问题，就有交换排序、选择排序，插入排序等多种算法。进行算法评价的目的，在于从解决同一个问题的不同算法中选择出较为合适的一种，同时从不同算法的比较中知道如何对现有的算法进行改进，从而设计出更好的算法。一般从五个方面对算法进行比较：①正确性②健壮性③可读性④时间复杂度⑤空间复杂度宁夏育才中学22①正确性正确性是设计和评价一个算法的首要条件，如果一个算法不正确，其他方面就无从谈起。一个正确的算法是指在合理的数据输入下，能在有限的运行时间内得出正确的结果。通通过对数据输入的所有可能情况的分析和上机调试可以证明算法是否正确，或者找出算法的反例说明算法存在缺陷。例如：课本46页，求一元二次方程ax2+bx+c=0(a≠0)的实数根。请同学们思考，为什么不正确？宁夏育才中学23②健壮性健壮性是指一个算法对不合理（又称不正确、非法、错误等）数据输入的反应和处理能力。一个好的算法应该能够识别出错误数据并进行相应处理。对错误数据的处理一般包括打印出错信息、调用错误处理程序、返回标识错误的特定信息、中止程序运行等方式。宁夏育才中学24③可读性可读性是指一个算法供人们阅读和理解的容易程序。一个可读性好的算法，应该使用便于识别和记忆的、与描述事物或实现的功能相一致的标识符，应该符合结构化和模块化的程序设计思想，应该对其中的每个功能模块以及重要的数据、数据类型和语句等加以注释，应该建立有相应的文档，用来对整个算法的功能、结构、使用及有关事项进行必要的说明。宁夏育才中学25④时间复杂度时间复杂度又称计算复杂度，它是算法有效性的量度之一，量度算法有效性的另一个重要指标是空间复杂度。时间复杂度是一个算法运行时间的相对量度。一个算法的运行时间是指在计算机上从开始到结束运行所花费的时间。它大致等于计算机执行一种简单操作（如赋值、转向、比较、输入、输出等）所需时间与算法中进行简单操作次数的乘积。因为执行一种简单操作所需的时间随机器而异，它是由机器本身硬软件环境决定的，与算法无关，所以只讨论影响运行时间的另一个因素——算法中进行简单操作的次数。一个算法中，进行简单操作的次数越少，其运行时间也就越少；次数越多，运行时间也越多。所以，把算法中包含简单操作次数的多少叫做算法的时间复杂度，它是一个相对的量度。宁夏育才中学26程序例题1--对一个一维的实数型数组，求它的累加和的算法。ProgramsumA;Constn=100;VarA:array[1..n]ofreal；i:integer;sum:real;Begin(1)sum:=0;(2)fori:=1tondosum:=sum+a[i];(3)writeln(‘sum=‘，sum);End.宁夏育才中学27求累加和的算法时间复杂度：第（1）步和第（3）步是一次复制操作和一次输出操作，重点分析第（2）步包含多少简单操作的次数，为了便于分析，将（2）改写为：(1)sum:=0;(2)i:=1;1:ifinthengoto2;sum:=sum+a[i];i:=i+1;Goto1;(3)2:writeln(‘sum=’,sum);1次n+1次n次1次n次n次因此，这个求累加和算法的时间复杂度为：T（n）=4n+41次宁夏育才中学28程序例题2--对一个一维的整数数组，按从大到小排序。ProgramsortA;Constn=10;Vara:array[1..n]ofinteger;i,j,p,t:integer;Begin(1)Fori:=1tondoreadln(a[i]);(2)Fori:=1ton-1doBeginP:=i;Forj:=itondoifa[j]a[p]thenp:=j;t:=a[i];a[i]=a[p];a[p]=t;End;(3)Fori:=1tondoIfImod5=0thenWriteln(a[i]:5)Elsewrite(a[i]:5);End.把第（2）步改写为：(2)i:=1;1:ifi=nthengoto4;p:=i;j:=i;2:ifjnthengoto3;ifa[j]a[p]thenp:=j;j:=j+1;goto2;t:=a[i];a[i]:=a[p];a[p]:=t;3:i:=i+1;goto1;(3)4:fori:=1tondo