1、数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 章章内内 容容 学时学时 章章 内内 容容 学时学时 1绪绪 论论27图图3+12线性表线性表4+28动态存储管理动态存储管理略略3栈和队列栈和队列49查找查找4+24串串略略10内部排序内部排序4+25数组和广义表数组和广义表 3+111外部排序外部排序略略6树和二叉树树和二叉树 4+2数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 一、教学内容：一、教学内容：1 1、数据结构基本概念、数据结构基本概念数据、数
2、据元素、数据对象、数据结构和数据类型等概念数据、数据元素、数据对象、数据结构和数据类型等概念2 2、算法及算法分析、算法及算法分析性能分析与度量：算法的性能标准；空间复杂度度量；时间复杂度度量性能分析与度量：算法的性能标准；空间复杂度度量；时间复杂度度量二、教学要求：二、教学要求：1 1、了解数据、数据对象、数据元素、数据类型、数据结构、数据的逻辑结构、了解数据、数据对象、数据元素、数据类型、数据结构、数据的逻辑结构与物理结构概念及逻辑结构与物理结构间的关系与物理结构概念及逻辑结构与物理结构间的关系2 2、了解算法的定义、算法的特性、算法的时间代价、算法的空间代价、了解算法的定义、算法的特性、
3、算法的时间代价、算法的空间代价3 3、掌握计算语句频度和估算算法时间复杂度的方法、掌握计算语句频度和估算算法时间复杂度的方法数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 什么是数据结构什么是数据结构基本概念和术语基本概念和术语抽象数据类型的概念抽象数据类型的概念 算法和算法分析算法和算法分析数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 1.1 什么是什么是数据结构数据结构一、为什么要学习数据结构？一、为什么要学习数据结构？计算机的主要用途：计算机的主要用途： 早期：早期：主要用于数值计算。 后来：后来：处理逐渐扩大到非数值计算领域（能处理多种复杂的具有一定结构关系的数据
4、）。 数值计算解决问题的一般步骤：数值计算解决问题的一般步骤：数学模型选择语言编出程序测试最终解答。数值计算的关键是：数值计算的关键是：如何得出数学模型（方程）？非数值计算问题：非数值计算问题：数据元素之间的相互关系一般无法用数学方程加以描述.数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 数据结构研究的问题用计算机进行信息表示和处理涉及到两个问题: 信息的表示信息的表示 信息的处理信息的处理 而信息的表示和组织又直接关系到处理信息的程序的效率。随着信息量的增加，信息范围的拓宽，使许多程序的规模变大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象
5、之间存在的关系，这就是数据结构这门课所要研究的问题。数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 例1 书目自动检索系统登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片001高等数学樊映川S01002理论力学罗远祥L01003高等数学华罗庚S01004线性代数栾汝书S02书目文件按书名按作者名按分类号高等数学001，003理论力学002，.线性代数004，.樊映川001,华罗庚002,.栾汝书004,.L002,S001,003,索引表线性表数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 例2 人机对奕问题树.数数 据据 结结 构构 武汉大学测绘学院武汉大
6、学测绘学院 例3 多叉路口交通灯管理问题CEDABABACADBABCBDDADBDCEAEBECED图数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 &求解非数值计算的问题：求解非数值计算的问题： 主要考虑的是设计出合适的数据结构及相应的算法。 即：首先要考虑对相关的各种信息如何表示、组对相关的各种信息如何表示、组织和存储？织和存储？ 因此，可以认为：数据结构是一门研究非数值计数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。之间的关系和操作的学科。数数 据据 结结 构构 武汉大学测绘学院武汉大学测
7、绘学院 答：答：计算机内的数值运算依靠方程式，而计算机内的数值运算依靠方程式，而非数值运算非数值运算（如（如表、树、图等）则要依靠数据结构。表、树、图等）则要依靠数据结构。 程序设计的实质是对实际问题选择一个好的数据结构，加之设计一个好的算法。而好的算法在很大程度上取决于描述实际问题的数据结构。同样的数据对象，用不同的数据结构来表示，同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。运算效率可能有明显的差异。数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 二、数据结构课程的形成和发展：二、数据结构课程的形成和发展： 形成阶段：形成阶段： 60年代初期，“数据结构”有关
8、的内容散见于操作系统、编译原理和表处理语言等课程。1968年，“数据结构”被列入美国一些大学计算机科学系的教学计划。 发展阶段：发展阶段： 数据结构的概念不断扩充，包括了网络、集合代数论、关系等“离散数学结构”的内容。 70年代后期，我国高校陆续开设该课程。数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 三、三、数据结构课程数据结构课程所处的地位：所处的地位：综合性的专业基础课数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 1.2 基本概念和术语基本概念和术语&几个概念：几个概念：数据数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能是对信息的一种符号表示。
9、在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。输入到计算机中并被计算机程序处理的符号的总称。数据元素数据元素(Data Element):是数据的基本单位，在程序中通常作是数据的基本单位，在程序中通常作为一个整体进行考虑和处理。为一个整体进行考虑和处理。 一个数据元素可由若干个数据项组成。数一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。据项是数据的不可分割的最小单位。数据元素按其组成可分为简单型数据元素和复杂型数据元素。简单型数数据元素按其组成可分为简单型数据元素和复杂型数据元素。简单型数据元素由一个数据项组成；复杂型数据元素由多个数据项组成，它通
10、常携据元素由一个数据项组成；复杂型数据元素由多个数据项组成，它通常携带着一个概念的多方面信息。例带着一个概念的多方面信息。例: int x; POINT dot; x简单型简单型, dot复杂型复杂型.数据对象数据对象(Data Object)：是性质相同的是性质相同的数据元素的集合数据元素的集合。是数。是数据的一个子集。据的一个子集。例如，整数数据对象的集合可表示为例如，整数数据对象的集合可表示为N0，1，2.，字母字符数据对象的集合可表示为字母字符数据对象的集合可表示为C=A,B,Z。数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 学号 姓名 性别 籍贯 电 话 通 讯 地 址
11、01 张三 男 长沙 8639000 麓山南路 327 号 02 李四 男 北京 23456789 学院路 435 号 03 王五 女 广州 30472589 天河路 478 号 04 赵六 男 上海 41237568 南京路 1563 号 05 钱七 女 南京 5013472 南京大学 06 刘八 女 武汉 61543726 武汉大学 07 朱九 男 昆明 4089651 云南大学 08 孙十 女 杭州 6154372 西湖路 635 号 例如：学生卡片记录表数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 &数据结构定义数据结构定义1-是相互之间存在一种或多种特定关系的数据元素的集
12、合。形式化定义：数据结构是一个二元组 Data_Structure = (D,R)其中，D是数据元素的有限集合， R是D上关系的集合数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 &数据结构定义数据结构定义2- 按某种逻辑关系按某种逻辑关系组织起来的一批数据（或称带结构的数据元素的集合）应用计算机语言并按一定的存储表示按一定的存储表示 方式方式把它们存储在计算机的存储器中，并在其上定义了一个运算的集合。在其上定义了一个运算的集合。具体来说，数据结构包含三个方面的内容，即数据的逻辑结构，数据的存贮结构和对数据所施加的运算（操作）。数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院
13、 这三个方面的关系为： （1）数据的逻辑结构独立于计算机，是数据本身所固有的。（2）存贮结构是逻辑结构在计算机存贮器中的映像，必须依赖于计算机。（3）运算是指所施加的一组操作总称。运算的定义直接依赖于逻辑结构，但运算的实现必须依赖于存贮结构。 数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 &逻辑结构逻辑结构-划分方法划分方法&一、集合 结构中的数据元素除了同属于一种类型外，别无其它关系。二、线性结构 结构中的数据元素之间存在一对一的关系。三、树型结构 结构中的数据元素之间存在一对多的关系。 a b c d e f g h 图 树形结构抽象描述示意图 a1a2a3a4数数 据据 结结
14、 构构 武汉大学测绘学院武汉大学测绘学院 四、图状结构或网状结构 结构中的数据元素之间存在多对多的关系。 1 2 3 4 图 图形结构抽象描述示意图 数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 数据的逻辑结构逻辑结构可归结为以下四类四类: :线性线性结构树形树形结构图状图状结构集合集合结构数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 数据的逻辑结构只抽象反映数据元素的逻辑关系 数据的存储（物理）结构数据的逻辑结构在计算机存储器中的实现 同一种逻辑结构可采用不同的存储方法（以上四种之一或组合），这主要考虑的是运算方便及算法的时空要求。数据的逻辑结构与存储结构密切相关算法
15、设计 逻辑结构算法实现 存储结构存储结构分为：顺序存储结构借助元素在存储器中的相对位置来表示 数据元素间的逻辑关系链式存储结构借助指示元素存储地址的指针表示数据 元素间的逻辑关系数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 元素元素n n.元素元素i i.元素元素2 2元素元素1 1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储地址存储内容存储内容Loc(元素元素i)=Lo+（i-1)*m顺序存储顺序存储数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 1536元素元素2 21400元素元素1 11346元素元素3 3 元素元素4 41345h存储地址存储
16、地址 存储内容存储内容 指针指针 1345 1345 元素元素1 1 14001400 1346 1346 元素元素4 4 . . . . . 14001400 元素元素2 2 1536 1536 . . . . . 1536 1536 元素元素3 3 1346 1346 链式存储链式存储 h数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 数据的运算：检索、排序、插入、删除、修改等数据的运算：检索、排序、插入、删除、修改等 线性结构线性结构 非线性结构非线性结构 顺序存储顺序存储 链式存储链式存储 线性表线性表栈栈队队树形结
17、构树形结构图形结构图形结构数据结构的三个方面：数据结构的三个方面：数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 （1） S=(D, R) D= a, b, c, d, e, f R=(a,e), (b,c), (c,a), (e,f), (f,d)解：解： 上述表达式可用图形表示为：上述表达式可用图形表示为：b c a e f d此结构为此结构为线性线性的。的。数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 d1 d5 d2 d4 d3该结构该结构是非线性的是非线性的。解：解：上述表达式可用图形表示为：上述表达式可用图形表示为：数数 据据 结结 构构 武汉大学测绘学院武汉
18、大学测绘学院 Q1 数据类型与抽象数据类型的区别？数据类型与抽象数据类型的区别？Q2 抽象数据类型如何定义？抽象数据类型如何定义？Q3 抽象数据类型如何表示和实现？抽象数据类型如何表示和实现？ 讨论：讨论：提示：教材中例提示：教材中例1-6和例和例1-7分别给出了抽象数据类分别给出了抽象数据类型型“三元组三元组”的定义、表示和实现，请阅读。的定义、表示和实现，请阅读。数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 数据类型：在一种程序设计语言中，变量所具有的数据种类。例1、 在FORTRAN语言中，变量的数据类型有整型、实型、和复数型 例2、在C语言中数据类型：基本类型和构造类型基本
19、类型：整型、浮点型、字符型构造类型：数组、结构、联合、指针、枚举型、自定义数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 typedef struct int num; char name20; float score;STUDENT;STUDENT stu1,stu2, *p;用户也可用typedef 自己定义数据类型数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 数据类型：是一个值的集合和定义在该值上 的一组操作的总称。抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作）它与数据类型实质上是一个概念，但其特它与数
20、据类型实质上是一个概念，但其特征是征是使用与实现分离使用与实现分离，实行，实行封装封装和和信息隐信息隐蔽蔽（独立于计算机）。（独立于计算机）。数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 抽象数据类型分类抽象数据类型分类 原子类型: 不可分解 固定聚合类型 可变聚合类型 多形数据类型数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 抽象数据类型抽象数据类型可以用以下的三元组来表示：可以用以下的三元组来表示： ADT = （D，S，P） 数据对象数据对象 D上的关系集上的关系集 D上的操作集上的操作集 ADTADT抽象数据类型名抽象数据类型名 数据数据对象对象： 数据数据关系
21、关系： 基本基本操作操作 ： ADT ADT抽象数据类型抽象数据类型名名ADT常用常用定义定义格式格式数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 基本操作名(参数表)初始条件:操作结果:参数分赋值参数和引用参数(用&打头)例 见1-6Max(T,&e)初始条件:三元组T已存在操作结果:用e返回T的三个元素中的最大值数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 抽象数据类型可以通过固有的数据类型（如整型、实型、字符型等）来表示和实现。注注1 ：它有些类似它有些类似C C语言中的语言中的结构（结构（struct)struct)类型类型，但增加了相关的但增加了相关的服务服务
22、。注注2 ：教材中用的是教材中用的是类类C C语言（介于伪码和语言（介于伪码和C C语言之语言之间）作为描述工具。其描述语法见间）作为描述工具。其描述语法见P10-11P10-11。 数据元素类型约定为数据元素类型约定为ElemType;ElemType;但上机时要用具体语言实现，我们用但上机时要用具体语言实现，我们用C+C+语言语言数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 1.4 算法和算法分析算法和算法分析一、算法的概念和描述：一、算法的概念和描述：1、什么是算法？、什么是算法？ 是对特定问题求解步骤的一种描述，算法是指令的有限序列，其中每一条指令表示一个或多个操作。程序就
23、是在数据的某特定的表示方式(结构)的基础上对抽象算法的具体表述。 Turing 1936 第一个系统地提出 数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 2、 算法描述算法具有以下五个特性：1）有穷性 一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。2）确定性 算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。3）可行性 一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。4）输入 一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。5）输出 一个算法有一个或多个输出，这些输出是同输入有着某些特定
24、关系的量。数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 算法设计的要求:评价一个好的算法有以下几个标准:(1) 正确性(Correctness ) 算法应满足具体问题的需求。(2)可读性(Readability) 算法应该好读。以有利于阅读者对程序的理解，便于调试和修改。 (3)健状性(Robustness) 算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。(4)效率与存储量需求 效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 注
25、意：注意：算法和程序的关系算法和程序的关系 算法的含义与程序十分相似，但二者是有区别的。一个程序不一定满足有穷性（死循环），另外，程序中的指令必须是机器可执行的，而算法中的指令则无此限制。一个算法若用计算机语言来书写，则它就可以是一个程序。数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 二、算法的描述和实现二、算法的描述和实现 描述描述-可采用自然语言、数学语言或约定的符号语言。 实现实现-必须借助程序设计语言提供的数据类型及其运算。 本课的描述本课的描述-采用类C语言。数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 三、算法分析三、算法分析 同一问题可用不同算法解决，而一
26、个算法的质量优劣将同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。算法和改进算法。 一个算法的评价有一个算法的评价有事后统计法事后统计法和和事前分析估计法事前分析估计法 一个算法执行所耗费的时间，从理论上是不能算出来的，一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个个算法都上机测试，只需知道哪个算法花费的时间多，哪个算
27、法花费的时间少就可以了。算法花费的时间少就可以了。程序的运行时间取决以下因素程序的运行时间取决以下因素: 算法策略算法策略 问题规模问题规模 程序语言程序语言 编译程序效率编译程序效率 机器执行速度机器执行速度数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 算法的效率可以认为是问题规模的函数算法的效率可以认为是问题规模的函数.主要从时间复杂度时间复杂度和空间复杂度空间复杂度来考虑。时间复杂度时间复杂度1、时间频度、时间频度 一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度语句频度或时间频度。记为
28、T(n)。数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 例1 求下列算法段的语句频度 for(i=1; i=n; i+)for(j =1; j =i ; j+)x=x+1; 分析：该算法为一个二重循环，执行次数为内、外循环次数相乘，但内循环次数不固定，与外循环有关，因些，时间频度T(n)=1+2+3+n= 2)1( nn数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 2、时间复杂度、时间复杂度在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。为此，我们引入时间复杂度概念。一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，
29、用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=(f(n),称(f(n) 为算法的渐近时间复杂度渐近时间复杂度，简称时间复杂度。例如，若T(n)=n(n+1)/2,则有 1/4T(n)/n21，故它的时间复杂度为(n2), 即(n)与n2 数量级相同。数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 算法效率的度量：采用算法效率的度量：采用时间复杂度时间复杂度例1.2 分析以下程序段的时间复杂度for (i=1;in;i+) y=y+1; for (j=0; j=(2*n)
30、; j+)x+; /* 1 * /* 2 * /数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 分析：语句的频度指的是该语句重复执行的次数。一个算法中所有语句的频度之和构成了该算法的运行时间。语句1的频度是：n-1语句2的频度是：12) 12)(1(2nnnn则该程序段的时间复杂度：T(n)=)(2222nOn数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 例1.3 分析以下程序段的时间复杂度i=1;while (i=n) i=i*2语句1的频度是：1设语句2的频度是f(n)，取最大值则该程序段的时间复杂度为：/* 1 * /* 2 * /nnf)(2nnf2log)(nn
31、f2log)()(loglog1)(1)(22nOnnfnT数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 & 常见函数的时间复杂度按数量递增排列及增长率。常见函数的时间复杂度按数量递增排列及增长率。 常数阶O(1) 对数阶O(log2n) 线性阶O(n) 线性对数阶O(nlog2n) 平方阶O(n2) 立方阶O(n3) k次方阶O(nk) 指数阶O(2n)定理：若A(n)=a m n m +a m-1 n m-1 +a1n+a0是一个m次多项式，则A(n)=O(n m)证略。数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 四、空间复杂度空间复杂度 与时间复杂度类似，空间复
32、杂度是指算法在计算机内执行时所需存储空间的度量。记作:l S(n)=O(f(n)l 我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。讨论方法与时间复杂度类似，不再赘述。数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 & 本章小结本章小结 数据、数据结构等基本概念数据、数据结构等基本概念 数据结构的三个方面的内容数据结构的三个方面的内容 抽象数据类型的概念抽象数据类型的概念 线性和非线性结构的逻辑特征线性和非线性结构的逻辑特征 数据存储的四种基本方法数据存储的四种基本方法 算法、算法的时间复杂度及其分析的简易方法算法、算法的时间复杂度及其分析的简易方法数数 据据 结结 构构
33、武汉大学测绘学院武汉大学测绘学院 一、填空题一、填空题1. 数据结构是一门研究非数值计算的程序设计问题中计算机的数据结构是一门研究非数值计算的程序设计问题中计算机的 以以及它们之间的及它们之间的 和运算等的学科。和运算等的学科。 2. 数据结构被形式地定义为（数据结构被形式地定义为（D, R），其中），其中D是是 的有限集合，的有限集合，R是是D上上的的 有限集合。有限集合。 3. 数据结构包括数据的数据结构包括数据的 、数据的、数据的 和数据的和数据的 这三个方这三个方面的内容。面的内容。 4. 数据结构按逻辑结构可分为两大类，它们分别是数据结构按逻辑结构可分为两大类，它们分别是 和和 。
34、5. 线性结构中元素之间存在线性结构中元素之间存在 关系，树形结构中元素之间存在关系，树形结构中元素之间存在 关关系，图形结构中元素之间存在系，图形结构中元素之间存在 关系。关系。 数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 6 在线性结构中，第一个结点在线性结构中，第一个结点 前驱结点，其余每个结点有且只有前驱结点，其余每个结点有且只有 1个前驱个前驱结点；最后一个结点结点；最后一个结点 后续结点，其余每个结点有且只有后续结点，其余每个结点有且只有1个后续结点。个后续结点。 7. 在树形结构中，树根结点没有在树形结构中，树根结点没有 结点，其余每个结点有且只有结点，其余每个结点
35、有且只有 个前个前驱结点；叶子结点没有驱结点；叶子结点没有 结点，其余每个结点的后续结点数可以结点，其余每个结点的后续结点数可以 。 8. 在图形结构中，每个结点的前驱结点数和后续结点数可以在图形结构中，每个结点的前驱结点数和后续结点数可以 。 9数据的存储结构可用数据的存储结构可用2种基本的存储方法表示，它们分别是种基本的存储方法表示，它们分别是 。 10. 数据的运算最常用的有数据的运算最常用的有5种，它们分别是种，它们分别是 。 11. 一个算法的效率可分为一个算法的效率可分为 效率和效率和 效率。效率。数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 （ ）1. 非线性结构是数
36、据元素之间存在一种：非线性结构是数据元素之间存在一种：A）一对多关系）一对多关系 B）多对多关系）多对多关系 C）多对一关系）多对一关系 D）一对一关系）一对一关系 （ ）2. 数据结构中，与所使用的计算机无关的是数据的数据结构中，与所使用的计算机无关的是数据的 结构；结构；A) 存储存储 B) 物理物理 C) 逻辑逻辑 D) 物理和存储物理和存储 （ ）3. 算法分析的目的是：算法分析的目的是：A) 找出数据结构的合理性找出数据结构的合理性 B) 研究算法中的输入和输出的关系研究算法中的输入和输出的关系C) 分析算法的效率以求改进分析算法的效率以求改进 D) 分析算法的易懂性和文档性分析算法
37、的易懂性和文档性 （ ）4. 算法分析的两个主要方面是：算法分析的两个主要方面是：A) 空间复杂性和时间复杂性空间复杂性和时间复杂性 B) 正确性和简明性正确性和简明性C) 可读性和文档性可读性和文档性 D) 数据复杂性和程序复杂性数据复杂性和程序复杂性 （ ）5. 计算机算法指的是：计算机算法指的是：A) 计算方法计算方法 B) 排序方法排序方法 C) 解决问题的有限运算序列解决问题的有限运算序列 D) 调度方法调度方法 （ ）6. 计算机算法必须具备输入、输出和计算机算法必须具备输入、输出和 等等5个特性。个特性。A) 可行性、可移植性和可扩充性可行性、可移植性和可扩充性 B) 可行性、确
38、定性和有穷性可行性、确定性和有穷性C) 确定性、有穷性和稳定性确定性、有穷性和稳定性 D) 易读性、稳定性和安全性易读性、稳定性和安全性数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 设有数据逻辑结构设有数据逻辑结构S=（D,R），试按各小题所给条件画出这些），试按各小题所给条件画出这些逻辑结构的图示，并确定相对于关系逻辑结构的图示，并确定相对于关系R，哪些结点是开始结点，哪些结点是开始结点，哪些结点是终端结点？，哪些结点是终端结点？ 1。D=d1,d2,d9 R=(d1,d2),(d1,d3),(d3,d4),(d3,d6),(d6,d8),(d4,d5), (d6,d7),(d8
39、,d9) 2。D=d1,d2,d9 R=(d1,d3),(d1,d8),(d2,d3),(d2,d4),(d2,d5),(d3,d9), (d5,d6),(d8,d9),(d9,d7), (d4,d7), (d4,d6)数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 逻辑结构唯一逻辑结构唯一存储结构不唯一存储结构不唯一运算的实现依赖运算的实现依赖于存储结构于存储结构数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 第第2 2章章 线性表线性表第第3 3章章 栈和队列栈和队列第第5 5章章 数组和广义表数组和广义表 线性结构线性结构在数据元素的非空有限集中，有且仅有一个开在数据
40、元素的非空有限集中，有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。一个直接前趋和一个直接后继。可表示为可表示为：（：（a1 , a2 , , an） 线性结构的特点：线性结构的特点：（逻辑、存储（逻辑、存储和运算）和运算）数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 线性结构包括线性表、堆栈、队列、字符串、数线性结构包括线性表、堆栈、队列、字符串、数组等等，其中，最简单、最常用的是组等等，其中，最简单、最常用的是-线性表线性表简言之，线性结构反映结点间的逻辑关系是简言之，线性结构反映结点间的逻辑关系
41、是 一对一一对一 的的见第见第2章章数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 一、教学内容一、教学内容：1 1、线性表的定义和性质及基本运算；线性表的定义和性质及基本运算；2 2、 线性表的顺序存储结构线性表的顺序存储结构3 3、 线性表的链式存储结构线性表的链式存储结构4 4、 多项式的代数运算多项式的代数运算数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 二、教学要求：二、教学要求：1 1、了解线性表的逻辑结构特性，以及线性表的两种存储实现方式了解线性表的逻辑结构特性，以及线性表的两种存储实现方式2 2、熟练掌握两种存储结构的描述方法。链表是本章的重点和难点。、熟
42、练掌握两种存储结构的描述方法。链表是本章的重点和难点。3 3、熟练掌握顺序表的定义与实现，包括查找、插入、删除算法的、熟练掌握顺序表的定义与实现，包括查找、插入、删除算法的实现；实现；4 4、熟练掌握在各种链表结构中实现线性表操作的基本方法，能在、熟练掌握在各种链表结构中实现线性表操作的基本方法，能在实际应用中选用适当的链表结构；实际应用中选用适当的链表结构；5 5、能够从时间和空间复杂度的角度综合比较线性表两种存储结、能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合构的不同特点及其适用场合。数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 （a1, a2,
43、 ai-1，ai, ai1 ，, an）1. 线性表的定义：线性表的定义：是是n个数据元素的有限序列个数据元素的有限序列n=0时称为时称为数据元素数据元素线性起点线性起点ai的直接前趋的直接前趋ai的直接后继的直接后继下标，下标，是元素是元素的序号，表示的序号，表示元素在表中的元素在表中的位置位置n为元素总为元素总个数，即表个数，即表长长空表空表线性终点线性终点数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 例例1 1 分析分析26 26 个英文字母组成的英文表个英文字母组成的英文表 （ A, B, C, D, , Z）学号学号姓名姓名性别性别年龄年龄班级班级200101181020
44、5于春梅于春梅女女 182001级电信级电信016班班2001011810260何仕鹏何仕鹏男男 182001级电信级电信017班班2001011810284王王 爽爽女女 182001级通信级通信011班班2001011810360王亚武王亚武男男 182001级通信级通信012班班： ：例例2 分析学生情况登记表分析学生情况登记表数据元素都是记录数据元素都是记录; 元素间关系是线性元素间关系是线性数据元素都是字母数据元素都是字母; 元素间关系是线性元素间关系是线性同一线性表中的元素必定具有相同特性同一线性表中的元素必定具有相同特性数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 线
45、性表的抽象数据类型的定义：线性表的抽象数据类型的定义： ADT List 数据对象：数据对象：D=ai|aiElemset,i=1,2,n,n0 数据关系：数据关系：R1=|ai-1,aiD,i=2,n 基本操作：基本操作： InitList(&l) 操作结果：构造一个空的线性表操作结果：构造一个空的线性表L DestroyList(&l) 初始条件：线性表已存在初始条件：线性表已存在 操作结果：销毁线性表操作结果：销毁线性表L 数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 ClearList(&l) 初始条件：线性表已存在初始条件：线性表已存在 操作结果：置线性表操作结果：置线性
46、表L为空表为空表 ListEmpty(L) 初始条件：线性表已存在初始条件：线性表已存在 操作结果：若线性表操作结果：若线性表L为空表，则返回为空表，则返回TRUE，否则返回，否则返回FALSE ListLenght(L) 初始条件：线性表已存在初始条件：线性表已存在 操作结果：返回线性表操作结果：返回线性表L数据元素个数数据元素个数 GetElem(L,i,&e) 初始条件：线性表已存在（初始条件：线性表已存在（1iListLenght(L)） 操作结果：用操作结果：用e返回线性表返回线性表L中第中第i个数据元素的值个数据元素的值数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 lo
47、catElem(L,e,comare() 初始条件：线性表已存在初始条件：线性表已存在,comare()是数据元素判定函数是数据元素判定函数 操作结果：返回线性表操作结果：返回线性表L中第中第1个与个与e满足关系满足关系comare()的数的数据元素的位序据元素的位序 PriorElem(L,cur_e,&pre_e) 初始条件：线性表已存在初始条件：线性表已存在 操作结果：若操作结果：若cur_e是线性表是线性表L的数据元素，且不是第一个，的数据元素，且不是第一个，则用则用pre_e返回它的前驱，否则操作失败，返回它的前驱，否则操作失败，pre_e无定义无定义 NextElem(L,cur_
48、e,&) 初始条件：线性表已存在初始条件：线性表已存在 操作结果：若操作结果：若cur_e是线性表是线性表L的数据元素，且不是第最后一的数据元素，且不是第最后一个，则用个，则用next_e返回它的后继，否则操作失败，返回它的后继，否则操作失败，next_e无定义无定义数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 ListInsert(&L,i,e) 初始条件：线性表已存在（初始条件：线性表已存在（1iListLenght(L)+1） 操作结果：在线性表操作结果：在线性表L中第中第i个数据元素之前插入新元素个数据元素之前插入新元素e，L长度加长度加1 ListDelete(&L,i,
49、&e) 初始条件：线性表已存在（初始条件：线性表已存在（1iListLenght(L)） 操作结果：删除线性表操作结果：删除线性表L中第中第i个数据元素，用个数据元素，用e返回其值，返回其值，L长度减长度减1 ListTraverse(L,visit() 初始条件：线性表已存在初始条件：线性表已存在 操作结果：依次对线性表操作结果：依次对线性表L的每个数据元素调用的每个数据元素调用visit()函函数，一旦数，一旦visit()失败，则操作失败失败，则操作失败 ADT List数数 据据 结结 构构 武汉大学测绘学院武汉大学测绘学院 上述是线性表抽象数据类型的定义，其中只是一些上述是线性表抽象
50、数据类型的定义，其中只是一些基本操作，另外可以更复杂。如：将两个线性表合基本操作，另外可以更复杂。如：将两个线性表合并等。复杂的操作可用基本操作实现。并等。复杂的操作可用基本操作实现。例例2-12-1假设假设: :有两个集合有两个集合 A 和和 B 分别用两个线性表分别用两个线性表 LA 和和 LB 表示，表示， 现要求一个新的集合现要求一个新的集合AAB 作如下操作：作如下操作：扩大线性表扩大线性表 LA，将存在于线性表，将存在于线性表LB 中而不存在于中而不存在于线性表线性表 LA 中的数据元素插入到线性表中的数据元素插入到线性表 LA 中去。中去。数数 据据 结结 构构 武汉大学测绘学院
