全国计算机等级考试二级教程-公共基础.docVIP

南讯 数据结构与算法 1.1算法 1.1.1算法的基本概念 算法：指解题方案的准确而完整的描述（即：解决某个问题的具体方法） 算法的基本特征 可行性(effectiveness) 针对实际问题设计的算法，人们总是希望能够得到满意的结果。但算法是再特定的计算工具上执行的，因而，在算法执行过程上往往受计算工具的限制， 是执行结果产生偏差。例如：计算下列三个值时：A=1012 B=1 C=-1012 变量的和是，如果采用不同的运算顺序，就会得到不同的结果，即： A+B+C=1012 +1+（-1012 ）=0 A+C+B=1012 +（-1012 ）+1=1，而在数学上A+B+C与 A+C+B，是完全等价的，因此算法与计算工具是又差异的。在设计一个算法是，必须要考虑它的可行性。 确定性(definiteness) 是指算法中的每一个步骤都必须是有明确的定义的，不允许有模棱两可的解释，也不允许有多义性。这一性质反应了算法与数学公式的明显区别。 有穷性(finiteness) 指的是 算法必须在有限的时间内完成，即算法必须在执行有限个步骤之后终止。算法的有穷性还包括合理的执行时间的含义，因为如果一个算法需要执行千万年，显然失去了使用价值。 拥有足够的情报 一个算法是否有效，还取决于算法所提供的情报是否足够。要使算法有效必需为算法提供足够的情报当算法拥有足够的情报时，此算法才最有效的；而当提供的情报不够时，算法可能无效。数据结构的 　　数据结构作为计算机的一门学科，主要研究和讨论以下三个方面：? ???　　?(数据集合中个数据元素之间所固有的逻辑关系，即数据的逻辑结构；? ???　　?(2)在对数据元素进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；? ???　　?(3)对各种数据结构进行的运算。? 数据结构(data?structure)是指相互之间存在一种或多种特定关系的数据元素的集合，即数据的组织形式。? 　　讨论以上问题的日的是为了提高数据处理的效率，所谓提高数据处理的效率有两个方面：? ????　　(l提高数据处理的速度；? ???　　?(2)尽量节省在数据处理过程中所占用的计算机存储空间。? 　　数据(data)：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。? 　　数据元素(data?element)：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。? 　　数据对象(data?object)：是性质相同的数据元素的集合，是数据的一个子集。? 　　在一般情况下，在具有相同特征的数据元素集合中，各个数据元素之间存在有某种关系(即连续)，这种关系反映了该集合中的数据元素所固有的一种结构。在数据处理领域中，通常把数据元素之间这种固有的关系简单地用前后件关系(或直接前驱与直接后继关系)来描述。? 　　前后件关系是数据元素之间的一个基本关系，但前后件关系所表示的实际意义随具体对象的不同而不同。一般来说，数据元素之间的任何关系都可以用前后件关系来描述。? 　　1数据的逻辑结构? 　　数据结构是指反映数据元素之间的关系的数据元素集合的表示。更通俗地说，数据结构是指带有结构的数据元素的集合。所谓结构实际上就是指数据元素之间的前后件关系。? 　　一个数据结构应包含以下两方面信息：? ???　　?(1)表示数据元素的信息；? ???　　?(2)表示各数据元素之间的前后件关系。? 数据结构的图形表示 　　数据结构除了用二元关系表示外，还可以直观地用图形表示。 在数据结构的图形表示中，对于数据集合D中的每一个数据元素用中间标有元素值的方框表示，一般称之为数据结点，并简称为结点；为了进一步表示各数据元素之间的前后件关系，对于关系R中的每一个二元组，用一条有向线段从前件结点指向后件结点。 数据结构图形表示 　? 在数据结构中，没有前件的结点称为根结点； 没有后件的结点称为终端结点(也称为叶子结点)。 一个数据结构中的结点可能是在动态变化的。根据需要或在处理过程中，可以在一个数据结构中增加一个新结点(称为插入运算)，也可以删除数据结构中的某个结点(称为删除运算)。插入与删除是对数据结构的两种基本运算。除此之外，对数据结构的运算还有查找、分类、合并、分解、复制和修改等。 线性结构与非线性结构如果在一个数据结构中一个数据元素都没有，则称该数据结构为空的数据结构。 　 根据