文档介绍：数据结构与算法
本章知识要点:
算法的基本概念;
数据结构的定义;
线性表的定义和存储;
树、二叉树的定义和存储;
查找与排序算法。
算法
算法的基本概念
算法(algorithm)是一组有穷的规则,规定了解决某一特定类型问题的一系列运算,是对解题方案的准确与完整的描述。
算法是解题的步骤,可以把算法定义成解一确定类问题的任意一种特殊的方法。在计算机科学中,算法要用计算机算法语言描述,算法代表用计算机解一类问题的精确、有效的方法。算法+数据结构=程序,求解一个给定的可计算或可解的问题,不同的人可以编写出不同的程序,来解决同一个问题,这里存在两个问题:一是与计算方法密切相关的算法问题;二是程序设计的技术问题。算法和程序之间存在密切的关系。
作为一个算法,一般应具有以下几个基本特性。
1)确定性
算法的每一种运算必须有确定的意义,该种运算执行某种动作应无二义性,目的明确;这一性质反映了算法与数学公式的明显差别。在解决实际问题时,可能会出现这样的情况:针对某种特殊问题,数学公式是正确的,但按此数学公式设计的计算过程可能会使计算机系统无所适从,这是因为根据数学公式设计的计算过程只考虑了正常使用的情况,而当出现异常情况时,此计算过程就不能适应了。
2)可行性
要求算法中有待实现的运算都是基本的,每种运算至少在原理上能由人用纸和笔在有限的时间内完成;针对实际问题设计的算法,人们总是希望能够得到满意的结果。但一个算法又总是在某个特定的计算工具上执行的,因此,算法在执行过程中往往要受到计算工具的限制,使执行结果产生偏差。
3)输入
一个算法有0个或多个输入,在算法运算开始之前给出算法所需数据的初值,这些输入取自特定的对象集合。
4)输出
作为算法运算的结果,一个算法产生一个或多个输出,输出是同输入有某种特定关系的量。
5)有穷性
一个算法总是在执行了有穷步的运算后终止,即该算法是可达的。数学中的无穷级数,在实际计算时只能取有限项,即计算无穷级数值的过程只能是有穷的。因此,一个数的无穷级数表示只是一个计算公式,而根据精度要求确定的计算过程才是有穷的算法。算法的有穷性还应包括合理的执行时间的含义。因为,如果一个算法需要执行千万年,显然失去了实用价值。
满足前四个特性的一组规则不能称为算法,只能称为计算过程,操作系统是计算过程的一个例子,在一个算法中,有些指令可能是重复执行的,因此指令的执行次数可能远远大于算法中的指令条数。由有穷性可知,对于任何输入,一个算法在执行了有限类指令后一定要终止并且必须在有限的时间内完成,因此,一个程序如果对任何输入都不会陷入无限循环时,即是有穷的,则它就是一个算法。操作系统用来管理计算机资源,控制作业的运行,没有作业运行时,计算过程并不停止,而是处于等待状态。
算法的描述方法可以归纳为以下几种:
(1)自然语言。
(2)图形,如N-S图、流程图,图的描述与算法语言的描述对应。
(3)算法语言,即计算机语言、程序设计语言、伪代码。
(4)形式语言。用数学的方法,可以避免自然语言的二义性。
用各种算法描述方法所描述的同一算法,该算法的功用是一样的,允许在算法的描述和实现方法上有所不同。
人们的生产活动和日常生活离不开算法,都在自觉不自觉地使用算法,例如,人们要购买物品,会首先确定购买哪些物品,准备好所需的钱,然后确定到哪些商场选购、怎样去商场、行走的路线,若物品的质量好如何处理,对物品不满意又怎样处理,购买物品后做什么等。以上购物的算法是用自然语言描述的,也可以用其他描述方法描述该算法。图1-1所示的是用流程图描述算法的例子,其函数为:
图1-1 流程图
计算机解题的过程实际上是在实施某种算法,这些算法可称为计算机算法。计算机算法不同于人工处理的方法。在实际应用时,各种方法之间往往存在着一定的联系。
1)列举法
列举法的基本思想是根据提出的问题,列举所有可能的情况,并用问题中给定的条件检验哪些是需要的,哪些是不需要的。因此,列举法常用于解决“是否存在”或“有多少种可能”等类型的问题,例如求解不定方程的问题。
列举法的特点是算法比较简单,但当列举的可能情况较多时,执行列举算法的工作量将会很大。因此,在用列举法设计算法时,使方案优化,尽量减少运算工作量,是应该重点注意的。通常,在设计列举算法时,只要对实际问题进行详细的分析,将与问题有关的知识条理化、完备化、系统化,从中找出规律;或对所有可能的情况进行分类,引出一些有用的信息,是可以大大减少列举量的。
列举原理是计算机应用领域中十分重要的原理。许多实际问题,若采用人工列举是不可想象的,但由于计算机的运算速度快,擅长重复