首页 考试资料幻灯片工程技术公务员考试小学教学中学教学大学教学外语资料
数据结构实验书


本书在编写方面以通俗易懂为其宗旨,特别注意了技术细节的交代,以便于自学,故也可作为从事计算机 应用等工作的科技人员参考用书。在学习本书时应至少掌握一门高级程序设计的知识,如掌握的是 C 语言

则最为理想;若能具有初步的离散数学和概率论的知识,对书中某些内容的理解会更容易。学习本书的同 时还需要把《数据结构》(C 语言版)(严蔚敏著)作为配套参考用书。 参加本书编写工作的教师和编写的章节是:第一章和第八章由四川师大的刘芳老师完成,第二章和第三章 分别由绵阳师院的吴文铁老师和段金蓉老师完成,第四章由乐山师院的孙锐老师完成,第五章由内江师院 的龙文光老师完成,第六章由自贡师专的梁金明老师完成,第七章和第九章分别由四川师院的蒲在毅老师 和贺春林老师完成,第十章由四川师大的王玲老师完成;主编和副主编对全书作了细致地审核,最后由主 编进行了定稿。 我们的努力是希望能帮助读者系统地完成上机实验,同时更好地理解数据结构的知识,为今后设计复杂程 序打好基础。如果读者能够从中获得一些有益的帮助,我们就倍感欣慰了。由于时间比较紧,加之作者水 平有限,书中必有不妥和错误之处,我们殷切期待读者的批评和指正。

第一章
【实验目的】

实现抽象数据类型

1. 复习高级程序设计语言的使用方法,将类 C 语言描述的算法转换成 C 源程序上机调试并通过;学会分析 基本的算法时间复杂度和空间复杂度; 2. 加深理解数据的逻辑结构和物理结构; 3. 帮助读者了解抽象数据类型的定义、表示和实现方法。抽象数据类型需要借助固有的数据类型来表示和 实现,即利用高级程序设计语言中已存在的数据类型来说明新的结构,用已经实现的操作来组合新的操作, 具体实现的细节则依赖于所用语言的功能; 4. 熟悉类 C 语言的书写规范,特别要注意值调用和引用调用的区别,以及如何转变成 C 的源程序,熟悉指 针变量作函数参数的基本用法。

第一节 知识准备
一、 数据结构课程的地位 《数据结构》的先行课程是程序设计语言(PASCAL、C 或 C++语言)、离散数学;后继课程有操作系统、编 译原理、数据库方法、算法设计与分析、人工智能等。数据结构和算法是程序设计的两大支柱。可以这样 说:数据结构是介于数学、计算机硬件和计算机软件之间的一门核心课程。

二、 基本概念和术语 1. 数据:是对客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并能被计算机程序处理 的符号的总称。 2. 数据元素:是数据的基本单位。 3. 数据对象:是性质相同的数据元素的集合,是数据的一个子集。 4. 数据结构:是相互之间存在一种或多种特定关系的数据元素的集合。通常有四种基本的数据结构:集 合、线性结构、树型结构、图型(网状)结构。 5. 数据的逻辑结构:是描述数据元素之间的逻辑关系,是一种定义性的说明。 6. 物理(存储)结构:是数据结构的机内表示,可以分为顺序表示法和非顺序表示法。 7. 数据类型:是一个值的集合和定义在这个值集合上的一组操作的总称。 8. 抽象数据类型:是指一个数学模型以及定义在该模型上的一组操作。其定义仅取决于它的一组逻辑特 性,而与其在计算机内如何表示和实现无关。

三、 抽象数据类型的表示和实现 抽象数据类型可以通过固有的数据类型来表示和实现,本书在高级语言的虚拟层次上讨论抽象数据类型的 表示和实现,且讨论的数据结构和算法主要是面向用户的,故采用类 C 语言作为描述工具。 类 C 语言的基本规范可以参看教材相关内容。 这里需要说明的是函数参数的类型,为了便于算法描述,除 C 语言提供的传值方式以外,增添 C++语言的 引用参数的参数传递形式。在形式参数表里,以&打头的参数为引用参数,相当于传地址,在编写 C 语言源 程序时要进行一定的转换和处理。

四、 算法和算法分析 评价一个算法,首先以考虑其正确性为前提,而运算工作量(执行速度或执行时间)是最主要考虑因素, 有时还要考虑算法执行时所占存储空间的大小。 为了量化地评价算法,特别引入算法复杂度,包括时间复杂度和空间复杂度。通常重点考虑算法的时间复 杂度。 分析算法的时间复杂度是以问题规模 n 为依据,并选择一定的基本操作,求得函数 f(n)表示基本操作重复 执行的次数。 时间复杂度表示为 T (n) =O(f(n)), 它说明随问题规模 n 的增大, 算法执行时间增长率和 f(n) 的增长率相同。 一般常见的时间复杂度有 , , , , , 等。对于某一个问题而言,如果算法时间复杂度的数量级

越低,说明算法的效率越高。凡 T(n)为 n 的对数函数,线性函数或多项式(包含幂函数)的算法称为有 效的或好的算法,而指数阶的算法是爆炸性的,是不实用的坏算法。时间复杂度对计算机处理数据的影响 见表 1-1。

表 1-1

时间复杂度对计算机处理数据的影响

时间复杂度 1 秒钟处理的数据量 1 小时处理的数据量 速度提高 10 倍后单位时间处理的数据量 速度提高 10000 后单位时间处理的数据量 O( O( O( O( O( ) 1000 3.6×106 提高 10 倍 提高 10000 倍 ) 140 2.0×105 约提高 9 倍 约提高 9000 倍 ) 31 1897 约提高 3 倍 提高 100 倍 ) 10 153 约提高 2 倍 约提高 22 倍 ) 5 21 提高不到 1 倍 提高不到 1 倍

第二节

类 C 算法的程序实现

【问题描述】 类 C 语言作为数据结构和算法的描述工具,使得数据结构和算法的描述和讨论简明清晰,不拘泥与 C 语言的细节,又容易转换成 C 或 C++程序。有关基本操作的算法采用函数的形式描述,为了便于算法 描述,除了值调用的形式外,增添了 C++语言的引用调用的参数传递方式。一般地说,凡需要将函数 中变化的形式参数的值反映在实际参数中,就可以通过引用参数调用的形式。而在 C 语言的实现中, 就可以通过指针变量作形式参数,接受变量的地址,达到“传地址”的目的。以下有两个问题,我们 用类 C 语言描述算法,然后写出对应的完整的源程序,并附加一些练习来使读者加深理解和体会。 1. 编写函数输入一组数据存入一维数组中,数据元素的个数和数据值的输入都在函数中完成; 2. 编写算法求这组数据的最大值、最小值,并通过函数参数返回。 【数据描述】 #define MAXNUM 20 typedef int ElemType ElemType; //定义数据的最大数目 // 定义数据元素的类型,此处设为 int,用户也可自行定义

a[MAXNUM+1];

123456789101112131415161718192021222324252627282930

 


 

  【Top

最新搜索

 


 

热点推荐