数据结构与算法实验教程实验分析.doc

1.1 数据结构与算法的计算环境 (实验估计时间：90分钟) 1.1.1 背景知识任何实际问题只有建立了数学模型才可以被计算机计算，而数据结构就是实际问题中元素的数学抽象，算法则是建立和解决数学模型的方法数据结构用来反映的内部构成，即数据由构成，以什么方式构成，呈什么结构。数据结构逻辑和物理结构。逻辑结构反映数据之间的逻辑关系，而物理结构反映数据在计算机内部的存储安排。数据结构是数据存在的形式是信息的一种组织方式，其目的是为了提高算法的效率通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。相同算法中的抽象数据类型用不同的数据结构表示会造成不同的执行效率这就有必要研究不同数据结构表示的效率差异及其适用场合。 数据结构主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。因此，主要有个方面的内容数据的逻辑结构数据的物理结构对数据的操作或算法。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的存储结构。 数据是指由有限的符号 (比如0”和1”，具有其自己的结构、操作和相应的语义) 组成的元素的集合。结构是元素之间关系的集合。通常来说，一个数据结构DS 可以表示为一个二元组：S=(D, S) 这里D是数据元素的集合 (或者是结点，可能还含有数据项或数据域) ，S是定义在D (或其他集合) 上的关系的集合，S = { R | R : D×D×...} ，称之为元素的逻辑结构。…n-1} (学生在队伍中的关系是前后次序关系) 逻辑结构有种基本类型：集合结构、线性结构、树状结构和网络结构。表和树是最常用的两种高效数据结构，许多高效的算法用这两种数据结构来设计实现。表(全序关系) 是线性结构，树 (偏序或层次关系) 和图 (局部有序) 是非线性结构。 数据结构的物理结构是指逻辑结构的存储镜像 (image)。数据结构 DS 的物理结构 P 对应于从 DS 的数据元素到存储区M (维护着逻辑结构S) 的一个映射： : (D, S) - M 1) 存储器模型一个存储器M是一系列固定大小的存储单元，每个单元U有一个唯一的地址A(U) ，该地址被连续地编码。每个单元U有一个唯一的后继单元U=succ(U) 。 P种基本映射模型：顺序 (sequential) 、链接 (linked) 、索引 (indexed) 和散列 (hashing) 映射。因此，我们至少可以得到4 × 4种可能的物理结构 (并不是所有的可能组合都合理) ： ??? equential (sets) ??? linked lists ??? indexed trees ??? hash graphs 例如，学生排队问题中，因为数据元素之间是一种前后次序关系，即采用的逻辑数据结构为线性结构，在计算机中可以开辟一个连续的存储空间来存放数据元素，故可采用顺序结构作为其物理结构。 2) 数据结构DS上的操作所有的定义在DS上的操作在改变数据元素 (点) 或点的域时必须保持DS的逻辑和物理结构。 DS上的基本操作任何其他对DS的高级操作都可以用这些基本操作来实现。最好将DS和的所有基本操作看作一个整体——称之为模块。我们可以进一步将该模块抽象为数据类型 (其中DS的存储结构被表示为私有成员，基本操作被表示为公共方法) 。算法 算法lgorithm) 是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗说，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。 一个算法应该具有以下个重要的特征有穷性：一个算法必须保证执行有限步之后结束确切性：算法的每一步骤必须有确切的定义可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。 输入：一个算法有0个或多个输入，以刻画运算对象的初始情况所谓0个输入是指算法本身定了初始条件输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的算法表达中抽象机制要用计算机解决一个稍为复杂的实际问题，大体都要经历如下步骤 图1.1 从问题到程序 1) 将实际问题数学化即把实际问题抽象为一个带有一般性的数学问题。这一步要引入一些数学概念，精确地阐述数学问题，弄清问题的已知条件、所要求的结果以及在已知条件和所要求的结果之间存在着的隐式或显式的联系。 对于确定的数学问题，设计其求解的方法即所谓的算法设计。这一步要建立问题的求解模型，即确定问题的数据模型并在此模型上定义一组运算然后借助于对这组运算的调用和控制，从已知数据出发导向所要求的结果，形成算法并用自然语言来表述。这种语言还不是程序设计语言，不能被计算机所接受。 用计算机的种程序设计语言来表达已设计好的算法。换句话说，将