《数据结构和算法分析基础参考模板范本.doc》由会员分享，可在线阅读，更多相关《数据结构和算法分析基础参考模板范本.doc（30页珍藏版）》请在金锄头文库上搜索。
1、实验1数据结构和算法分析基础1.1 数据结构与算法的计算环境(实验估计时间：90分钟)1.1.1 背景知识除了进行科学计算之外，计算机已经被广泛地应用在控制、管理和数据处理等非数值计算的领域中。与此相应，处理对象也由早先纯粹的数值发展到字符、表格和图形图像等各种具有一定结构的数据，这给计算机程序设计带来了新的问题。为了编写一个“好”的程序，必须明确处理对象的特征及各对象之间的关系。这就是“数据结构”这门学科形成和发展的背景。任何实际问题只有建立了数学模型才可以被计算机计算，而数据结构就是实际问题中操作对象 (元素) 的数学抽象，算法则是建立和解决数学模型的方法。数据结构用来反映计算机加工处理的
2、对象，即数据的内部构成，即数据由哪几部分构成，以什么方式构成，呈什么样的结构等。数据结构包括逻辑结构和物理结构。这里的逻辑结构和物理结构是指一个事物的两个方面，而不是指两个不同的对象。逻辑结构反映数据元素之间的逻辑关系，而物理结构反映了数据元素在计算机内部的存储安排，也称为存储结构。数据结构是数据存在的形式，也是信息的一种组织方式，其目的是为了提高算法的效率。数据结构通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。由于相同算法中的抽象数据类型用不同的数据结构来表示，会造成不同的执行效率，这就有必要来研究不同数据结构表示的效率差异及其适用场合。1. 数据结构的研究
3、对象数据结构主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。因此，主要有3个方面的内容，即数据的逻辑结构、数据的存储 (物理) 结构和对数据的操作 (或算法) 等。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的存储结构。2. 数据结构的形式化定义数据是指由有限的符号 (比如“0”和“1”，具有其自己的结构、操作和相应的语义) 组成的元素的集合。结构是元素之间关系的集合。通常来说，一个数据结构DS 可以表示为一个二元组： DS=(D, S)这里，D是数据元素的集合 (或者是“结点”，可能还含有“数据项”或“数据域”) ，S是定义在D (或其他集合) 上的关系的集合，S
4、= R | R : DD. ，称之为元素的逻辑结构。例如：学生排队问题数据结构的二元组为： DS=(student, order)其中： student=ai | aiD, D为同类学生的信息集 order= | ai, ai+1student, i=1, 2, n-1 (学生在队伍中的关系是前后次序关系)逻辑结构有4种基本类型：集合结构、线性结构、树状结构和网络结构。表和树是最常用的两种高效数据结构，许多高效的算法都用这两种数据结构来设计实现。表(全序关系) 是线性结构的，树 (偏序或层次关系) 和图 (局部有序) 是非线性结构的。数据结构的物理结构是指逻辑结构的存储镜像 (image) ，
5、即用怎样的物理存储方式来表示其逻辑关系。数据结构 DS 的物理结构 P 对应于从 DS 的数据元素到存储区M (维护着逻辑结构S) 的一个映射： P: (D, S) - M1) 存储器模型。一个存储器M是一系列固定大小的存储单元，每个单元U有一个唯一的地址A(U) ，该地址被连续地编码。每个单元U有一个唯一的后继单元U=succ(U) 。P有4种基本映射模型：顺序 (sequential) 、链接 (linked) 、索引 (indexed) 和散列 (hashing) 映射。因此，我们至少可以得到4 4种可能的物理结构 (并不是所有的可能组合都合理) ： sequential(sets) l
6、inkedlists indexedtrees hashgraphs例如，学生排队问题中，因为数据元素之间是一种前后次序关系，即采用的逻辑数据结构为线性结构，在计算机中可以开辟一个连续的存储空间来存放数据元素，故可采用顺序结构作为其物理结构。2) 数据结构DS上的操作。所有的定义在DS上的操作在改变数据元素 (结点) 或结点的域时必须保持DS的逻辑和物理结构。3) DS上的基本操作。任何其他对DS的高级操作都可以用这些基本操作来实现。最好将DS和它的所有基本操作看作为一个整体称之为模块。我们可以进一步将该模块抽象为数据类型 (其中DS的存储结构被表示为私有成员，基本操作被表示为公共方法) 。例
7、如，学生排队问题中的基本操作有出列 (删除操作) 、入列 (插入操作) 和点名 (检索) 等。3. 算法算法 (algorithm) 是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗地说，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。一个算法应该具有以下5个重要的特征。1) 有穷性：一个算法必须保证执行有限步骤之后结束。2) 确切性：算法的每一步骤必须有确切的定义。3) 可行性：算法中的每一步骤必须充分可及，即算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。4) 输入：一个算法有0
8、个或多个输入，以刻画运算对象的初始情况。所谓0个输入是指算法本身定义了初始条件。5) 输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。4. 算法表达中抽象机制要用计算机解决一个稍为复杂的实际问题，大体都要经历如下步骤 (如图1.1所示) 。图1.1 从问题到程序1) 将实际问题数学化。即把实际问题抽象为一个带有一般性的数学问题。这一步要引入一些数学概念，精确地阐述数学问题，弄清问题的已知条件、所要求的结果，以及在已知条件和所要求的结果之间存在着的隐式或显式的联系等。2) 对于确定的数学问题，设计其求解的方法。即所谓的算法设计。这一步要建立问题的求解模型
9、，即确定问题的数据模型并在此模型上定义一组运算。然后，借助于对这组运算的调用和控制，从已知数据出发导向所要求的结果，形成算法并用自然语言来表述。这种语言还不是程序设计语言，不能被计算机所接受。3) 用计算机的某种程序设计语言来表达已设计好的算法。换句话说，将非形式自然语言表达的算法转变为一种程序设计语言表达的算法。这一步叫程序设计。4) 在计算机上编辑、调试和测试编制好的程序，直到输出预期的结果。在这里，我们只关心第3步，而且把注意力集中在算法程序表达的抽象机制上，目的是引入一个重要的概念抽象数据类型，同时为大型程序设计提供一种相应的自顶向下逐步求精、模块化的具体方法，即运用抽象数据类型来描述
10、程序的方法。抽象数据类型 (abstract data types，简称ADT) 是算法设计和程序设计中的重要概念。严格地说，它是算法的一个数据模型连同定义在该模型上、作为该算法构件的一组运算。这个概念明确地把数据模型与作用在该模型上的运算紧密地联系起来。事实正是如此。一方面，数据模型的运算依赖于数据模型的具体表示，因为数据模型运算以数据模型中的数据变量作为运算对象，或作为运算结果，或二者兼而为之；另一方面，有了数据模型的具体表示以及数据模型运算的具体实现，运算的效率随之确定。于是，就有这样的一个问题：如何选择数据模型的具体表示使该模型上的各种运算的效率都尽可能地高？很明显，对于不同的运算组，
11、为使组中所有运算的效率都尽可能地高，其相应的数据模型所具体表示的选择将是不同的。在这个意义下，数据模型的具体表示又反过来依赖于数据模型上定义的那些运算。特别是，当不同运算的效率互相制约时，还必须事先将所有运算的相应使用频度排序，让所选择的数据模型的具体表示优先保证使用频度较高的运算有较高的效率。数据模型与定义在该模型上的运算之间存在着的这种密不可分的联系，是抽象数据类型的概念产生的背景和依据。一些基本抽象数据类型，包括表、栈、队列、串、树、二叉树和图等，是最基本和最简单的，并且是实现其他抽象数据类型的基础。高级抽象数据类型主要包括集合、字典、散列表、有序字典、并查集、优先队列、优先级树和堆、检
12、索树、搜索树、分离集合等。1.1.2 实验目的1) 理解数据结构和算法的基本概念。2) 通过因特网搜索与浏览，了解数据结构和算法的计算环境，了解因特网环境中主流的数据结构和算法技术网站。3) 掌握通过专业网站不断丰富数据结构和算法最新知识的学习方法，尝试通过专业网站的辅助和支持来开展数据结构和算法的应用实践。1.1.3 工具/准备工作在开始本实验之前，请回顾教科书的相关内容。需要准备一台带有浏览器，能够访问因特网的计算机。1.1.4 实验内容与步骤1) 请查阅有关资料，简单叙述下列概念： 数据结构：_ 算法：_ ADT：_2) 请简述数据结构与算法对计算机学科的意义。_3) 请教你的老师或者查阅有关的专业教学计划，并简述： 在你主修的专业中，数据结构课程与哪些后续课程有什么关联？_ 就你主修的专业而言，学习数据结构与算法有什么实际意义？_
