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) 请教你的老师或者查
13、阅有关的专业教学计划，并简述： 在你主修的专业中，数据结构课程与哪些后续课程有什么关联？_ 就你主修的专业而言，学习数据结构与算法有什么实际意义？_4) 上网搜索和浏览，了解数据结构和算法知识的应用情况，看看哪些网站在做着数据结构与算法的技术支持工作？请在表1.1中记录搜索结果。提示：一些数据结构与算法专业网站的例子包括： (算法与数据结构) (编程爱好者论坛-数据结构与算法讨论区)你习惯使用的网络搜索引擎是：_你在本次搜索中使用的关键词主要是：_表1.1 数据结构与算法专业网站实验记录网站名称网 址内容描述请记录：在本次实验的网络搜索和浏览中，你感觉比较重要的2个数据结构与算法专业网站是：1
14、) 网站名称：_2) 网站名称：_请分析：你认为各数据结构与算法专业网站当前的技术热点是：1) 技术名称：_技术描述：_2) 技术名称：_技术描述：_3) 本实验的各部分操作能够顺利完成吗？如果不能，请分析并说明为什么。_1.1.5 实验总结_1.1.6 实验评价 (教师)_1.2 抽象数据类型的表示和实现(实验估计时间：90分钟)1.2.1 背景知识1. 抽象数据类型的定义抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，就不影响其外部的使用。抽象数据类型
15、和数据类型实质上是一个概念。例如，各个计算机都拥有的“整型”类型是一个抽象数据类型，尽管它们在不同处理器上的实现方法可以不同，但由于其定义的数学特性相同，在用户看来是相同的。因此，“抽象”的意义在于数据类型的数学抽象特性。另一个方面，抽象数据类型的范围更广，它不再局限于各种处理器中已定义并实现的数据类型，还包括用户在设计软件系统时自己定义的数据类型。为了提高软件的复用率和提高软件的可移植性，一个软件系统的框架应建立在数据之上，而不是在操作之上 (后者是传统软件设计方法所为) 。即在构成软件系统的每个相对独立的模型上，定义一组数据和施于这些数据上的一组操作，并在模块内部给出这些数据的表示及其操作
16、的细节，而在模块外部使用的只是抽象的数据和抽象的操作。显然，所定义的数据类型的抽象层次越高，含有该抽象数据类型的软件模块的复用程度也就越高。2. 抽象数据类型的表示一个含抽象数据类型的软件模块通常应包含定义、表示和实现3个部分。抽象数据类型可用以下三元组表示： (D, S, P)其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。通常采用以下格式定义抽象数据类型： ADT抽象数据类型名 数据对象： 数据关系： 基本操作： ADT抽象数据类型名其中，数据对象和数据关系的定义用伪码描述，基本操作的定义格式为： 基本操作名(参数表) 初始条件：描述了操作执行之前数据结构和参数应满足的条件，若
17、不满足，则操作失败，并返回相应出错信息。若初始条件为空，则省略之。 操作结果：说明了操作正常完成之后，数据结构的变化状况和应返回的结构。基本操作有两种参数： 赋值参数：只为操作提供输入值。 引用参数：以&打头，除了可提供输入值外，还将返回操作结果。3 抽象数据类型举例以下以抽象数据类型三元组为例，说明抽象数据类型是如何定义的 (这里只包括几个常见的基本操作，读者可在理解的基础上，根据需要自行添加相关的操作) 。(1) 三元组的顺序存储结构三元组实际上就是一个数据对象中有3个数据元素。这里采用动态分配的顺序存储结构来表示三元组在计算机中的具体存储方式，如图1.2所示。图1.2 动态分配的顺序存储
18、的三元组图中，ElemType表示三元组中元素的数据类型，可以是整型数，也可以是字符、浮点数或者更复杂的数据类型。Triplet为指向三元组起始元素的指针类型，这就好比有3个数的序列，第1个数为T0 ，第2个数为T1 ，第3个数则为T2 (T为Triplet类型) 。(2) 三元组的抽象数据类型定义三元组的抽象数据类型定义如下： ADT Triplet 数据对象：D=e1, e2, e3 | e1, e2, e3ElemSet (ElemSet为某个数据对象的集合) 数据关系：R1=, 基本操作： InitTriplet(&T, v1, v2, v3) 操作结果：构造三元组T，元素e1, e2
19、和e3分别被赋以参数v1, v2, v3值 DestroyTriplet(&T) 操作结果：三元组T被销毁 Get(T, i, &e) 初始条件：三元组T已存在，1i3 操作结果：用e返回T的第i元的值 Put(&T, i, e) 初始条件：三元组T已存在，1i3 操作结果：改变T的第i元的值为e Max(T, &e) 初始条件：三元组T已存在 操作结果：用e返回T的三个元素中的最大值 Min(T, &e) 初始条件：三元组T已存在 操作结果：用e返回T的三个元素中的最小值 ADT Triplet1.2.2 实验目的1) 通过抽象数据类型三元组的表示和实现，了解抽象数据类型的定义方式。2) 掌
20、握抽象数据类型的定义方式和用C语言实现的方法。3) 熟悉如何运用主函数检验各基本操作函数的正确性的具体操作。1.2.3 工具/准备工作在开始实验前，请回顾教科书中相关的内容。需要一台计算机，其中装有Borland C+ 5.0或Microsoft Visual C+ 6.0开发环境。 1.2.4 实验内容与步骤1. 基础知识请分析并填空：1) 抽象数据类型中基本操作有两种参数：赋值参数和引用参数。赋值参数的作用是_，引用参数的作用是_。2) 在数据结构中，从逻辑上可以把数据结构分成_和_。3) 线性结构中元素之间存在_关系，树形结构中元素之间存在_关系，图形结构中元素之间存在_关系。4) 数组
21、、串、有序表和顺序表中，_是属于物理结构的。5) 抽象数据类型中基本操作的定义 (即基本操作的函数原型说明) 包括_、_和_。2. 抽象数据类型的实现下面以抽象数据类型三元组为例，说明抽象数据类型是如何在计算机中实现的。我们用C语言函数来实现三元组的基本操作。在实现三元组的基本操作之前，必须搭好实现该抽象数据类型的整个C语言程序的模块框架结构图，如图1.3所示。图1.3 实现三元组操作的C语言源程序模块框架图这种模块结构能提高代码的复用程度，经过多次实验后，你将体会到它的优势。其中，example.h是解释标准库函数的头文件 (本书中所有的实验都必须使用该头文件中某些标准的库函数，因此，在以后
22、实验程序的模块框架图中不再赘述) ；alog1_1.cpp中包含了三元组的动态顺序存储结构定义和一些三元组的基本操作；main1_1.cpp则是包含了验证三元组基本操作正确性的主函数main()，下面的程序结构中会有具体说明。提示：对实验中使用的程序文件说明如下：1) example.h为解释标准库函数的头文件，如果不用此文件，在主程序代码最前面必须包括必须使用的标准库函数。2) 以alog开头、以 .cpp为扩展名的文件称为实现文件，包含相应存储结构的一组基本操作，例如alog1_1.cpp 即为实验1.2中第一个实现文件。3) 以main开头、以 .cpp为扩展名的文件称为主文件，包含调用
23、各个操作的主函数main()，例如main1_1.cpp 即为实验1.2中的第一个主文件。(1) 解释伪码和标准库函数的头文件example.h / example.h：伪代码的定义和常见的库函数 # include / 字符串基本操作 # include / 处理与字符相关的函数 # include / 处理与时间相关的函数 # include / 处理与input/output相关的函数 # include / atoi()，malloc()，free() 等 # include / 处理与数学运算相关函数 # include / exit() (2) 三元组的顺序存储结构定义根据图1-2
24、所示，可以定义以下动态分配的三元组的顺序存储结构如下： -三元组的动态分配的存储结构- typedef ElemType *Triplet;/ 由初始化操作分配3个元素的存储空间 / Triplet是指向ElemType类型元素的指针，存放ElemType类型元素的地址提示：typedef的功能是定义一个新类型Triplet，即指向ElemType类型数据的指针。如果用Triplet定义一个变量T，即Triplet T，就相当于“ElemType *T; ”。(3) 三元组基本操作的实现下面分别介绍几个在源文件alog1_1.cpp中的三元组基本操作的实现过程。1) 初始化操作。 int In
25、itTriplet(Triplet &T, ElemType v1, ElemType v2, ElemType v3) / 操作结果：构造三元组T，依次置T的3个元素的初值为v1， v2和v3 (见图1.4) ，经过此操作，系统将分配给三元组T一个起始地址。 if (!(T=(ElemType *) malloc (3*sizeof(ElemType) exit(0);/ 申请空间失败，退出系统 T0=v1; T1=v2; T2=v3; return 1; / 若返回值为1，则初始化成功 图1.4 构造三元组T请分析：上述程序段实际上就是对一个数组进行的操作，完全可以将T定义为一个数组，以开
26、辟一个相同数据类型的连续存储空间，它们在具体实现上也相似。但是，二者之间仍存在着本质上的区别。这些区别主要体现在哪些方面？_2) 销毁操作。 void DestroyTriplet(Triplet &T) / 操作结果：三元组T被销毁 free(T); T=NULL; return; 3) 取指定元素操作。 int Get(Triplet T, int i, ElemType &e) / 初始条件：三元组T已存在，1i3。操作结果：用e返回T第i元的值 if (i3) return 0;/ 若返回值为0，则操作失败 e=Ti-1; return 1;/ 若返回值为1，则操作成功，e为T中第i-
27、1个元素的值 4) 改变指定元素值操作。 int Put(Triplet T, int i, ElemType e) / 初始条件：三元组T已存在，1i3。操作结果：改变T第i元的值为e if (i3) return 0;/ 若返回值为0，则操作失败 Ti-1=e; return 1;/ 若返回值为1，则操作成功 5) 求最大元素操作 void Max(Triplet T, ElemType &e) / 初始条件：三元组T已存在。操作结果：用e返回指向T的最大元素的值 e=(T0=T1)?(T0=T2)?T0:T2):(T1=T2)?T1:T2); return; 试分析：实际上“e=(T0=
28、T1)?(T0=T2)?T0:T2):(T1=T2)?T1: T2) ;”这条语句可以用一个嵌套的if . else语句实现： if (T0=T1) if (T0=T2) e=T0; else e=T2; else if (T1T2) e=T1; else e=T2;请在上边空白处画出实现这个操作的程序流程图或N-S图。请记录：通过对以上几个函数的分析，你能体会到引用“&”的作用是什么吗？_(4) 三元组操作的具体实现过程步骤1：新建一个实现文件alog1_1.cpp，将三元组的存储结构和基本操作的程序代码输入到文件中。实现文件 (alog1_1.cpp) ： / alog1_1.cpp：顺序
29、存储三元组的6个基本操作 typedef ElemType *Triplet;/ 定义三元组动态的顺序存储结构 int InitTriplet(Triplet &T, ElemType v1, ElemType v2, ElemType v3) if (!(T=(ElemType *) malloc (3*sizeof(ElemType) exit(0);/ 退出系统 T0=v1; T1=v2; T2=v3; return 1;/ 若返回值为1，则初始化成功 void DestroyTriplet(Triplet &T) free(T); T=NULL; return ; int Get(Tr
30、iplet T, int i, ElemType &e) if (i3) return 0;/ 若返回值为0，则操作失败 e=Ti-1; return 1; / 若返回值为1，则操作成功，e为T中第二个元素的值 int Put(Triplet T, int i, ElemType e) if (i3) return 0;/ 若返回值为0，则操作失败 Ti-1=e; return 1;/ 若返回值为1，则操作成功 void Max(Triplet T, ElemType &e) e=T0=T1?T0=T2?T0:T2:T1=T2?T1:T2; return; void Min(Triplet T
31、, ElemType &e) e=T0; if (T1e) e=T1; if (T2e) e=T2; return; 步骤2：建立一个验证实现文件的主文件main1_1.cpp。主文件 (main1_1.cpp) ： / 主函数main1_1.cpp：验证alog1_1.cpp的正确性 # include example.h/ 包含解释伪码和标准库函数的头文件example.h typedef int ElemType;/ 定义三元组元素逻辑类型ElemType为整型 # include triplet.cpp/ 包含三元组数据类型及其6个基本操作 void main() Triplet T;/ _ ElemType m; int i; i=InitTriplet(T, 1, 3, 5);/_ printf(调用初始化函数后，i=%d (1：成功；否则：不成功) , i); printf(n三元组中三个元素的值分别为：n); printf(T0=%d, T1=%d, T2=%d, T0, T1, T2); i=Get(T, 2, m);/ _ if (i=1)
