《数据结构》完整加精版课件.ppt

1、1数据结构基础数据结构基础 2第第1 1章章 基本概念和方法基本概念和方法 本章论述学习和研究数据结构所必须的并且本章论述学习和研究数据结构所必须的并且将反复出现的基本概念和方法。将反复出现的基本概念和方法。31.1 数据结构与软件系统数据结构与软件系统 P.1 设计解决实际问题的计算机软件系统，首先需要设计解决实际问题的计算机软件系统，首先需要建立被处理对象的数据模型。建立被处理对象的数据模型。数据和世上万物一样，都是具有结构的。人们很数据和世上万物一样，都是具有结构的。人们很自然地用数据结构表示应用领域的被处理对象。自然地用数据结构表示应用领域的被处理对象。例如，树和图。例如，树和图。数据

2、结构数据结构由一个数据对象以及该对象中的所有数由一个数据对象以及该对象中的所有数据元素之间的关系组成。据元素之间的关系组成。数据元素数据元素本身可以是数据结构，因此，可以构造本身可以是数据结构，因此，可以构造非常复杂的数据结构。非常复杂的数据结构。4 数据结构的数据结构的实现实现是以下一层数据结构表示上一层是以下一层数据结构表示上一层数据结构，直至以程序设计语言提供的基本数据数据结构，直至以程序设计语言提供的基本数据类型表示的过程类型表示的过程。为了模拟实际问题的求解过程和现实对象的行为，为了模拟实际问题的求解过程和现实对象的行为，还必须提供对数据结构的相应还必须提供对数据结构的相应操作操作。

3、评价数据结构表示能力的标准主要是它能否方便评价数据结构表示能力的标准主要是它能否方便且有效地实现需要的操作，而实现操作的算法设且有效地实现需要的操作，而实现操作的算法设计及其效率高低也依赖于数据结构表示。计及其效率高低也依赖于数据结构表示。数据结构的定义、表示及其操作的实现相互关联，数据结构的定义、表示及其操作的实现相互关联，都是数据结构研究的重要内容。都是数据结构研究的重要内容。5 计算机软件系统可看成是通过不同层次的数据结计算机软件系统可看成是通过不同层次的数据结构及其操作实现的。例如：构及其操作实现的。例如：6 中间层数据结构起着核心作用，称之为中间层数据结构起着核心作用，称之为建模层建

4、模层。对数据结构的研究产生了一批通用性强、具有很对数据结构的研究产生了一批通用性强、具有很高实用价值的中间层数据结构，如数组、字符串、高实用价值的中间层数据结构，如数组、字符串、集合、线性表、栈、队列、链表、树、图、符号集合、线性表、栈、队列、链表、树、图、符号表等。表等。系统地学习进而掌握数据结构的知识和方法，对系统地学习进而掌握数据结构的知识和方法，对于提高设计与开发软件系统尤其是复杂软件系统于提高设计与开发软件系统尤其是复杂软件系统的能力，无疑是十分重要的。的能力，无疑是十分重要的。71.2 数据数据抽象与封装抽象与封装 P.2 抽象和封装的概念在日常生活中是普遍存在的，抽象和封装的概念

5、在日常生活中是普遍存在的，例如，人们常用的手机。例如，人们常用的手机。通过通过数据封装数据封装，将一个数据对象的内部结构和实，将一个数据对象的内部结构和实现细节对外屏蔽。现细节对外屏蔽。通过通过数据抽象数据抽象，将一个数据对象的规格说明与其，将一个数据对象的规格说明与其实现分离，对外提供简洁、清晰的接口。实现分离，对外提供简洁、清晰的接口。Eg.int 数据结构多层表示的过程反过来也就是从基础数数据结构多层表示的过程反过来也就是从基础数据结构到应用领域数据结构的不断抽象与封装的据结构到应用领域数据结构的不断抽象与封装的过程。过程。8 数据类型数据类型由一个数据对象的集合和一组作用于这由一个数据

6、对象的集合和一组作用于这些数据对象的操作组成。例如，些数据对象的操作组成。例如，C和和C+的基本数的基本数据类型据类型char、int、float和和double等等。用抽象数据类型（用抽象数据类型（ADT）描述数据抽象与封装是）描述数据抽象与封装是一种自然、有效的方法。一种自然、有效的方法。抽象数据类型抽象数据类型是一个数据类型，该数据类型的组是一个数据类型，该数据类型的组织遵循将数据对象及对这些数据对象的操作的规织遵循将数据对象及对这些数据对象的操作的规格说明与这些数据对象的表示、操作的实现相分格说明与这些数据对象的表示、操作的实现相分离的原则。离的原则。9 当强调一个数据对象的结构时，使

7、用数据结构的当强调一个数据对象的结构时，使用数据结构的概念。概念。与数据结构的概念对比，抽象数据类型包含了一与数据结构的概念对比，抽象数据类型包含了一个数据结构的集合，还包含了对数据结构的操作。个数据结构的集合，还包含了对数据结构的操作。(C与与C+的差别）。的差别）。抽象数据类型成为描述数据结构及其操作的有效抽象数据类型成为描述数据结构及其操作的有效方式。方式。定义定义ADT的语言本质上不依赖具体的程序设计语的语言本质上不依赖具体的程序设计语言，这里采用言，这里采用C+描述。描述。Eg.Eg.(C+(C+并非并非100%100%的的ADTADT，如，如friendfriend，inlinei

8、nline等等)10例例1.1 抽象数据类型抽象数据类型“圆圆”的定义为：的定义为：P.3P.3class Circle /对象对象:几何圆public:Circle(float r);/构造函数，创建一个半径为r的对象实例 float Circumference();/返回该实例的周长 float Area();/返回该实例的面积;该抽象数据类型的名称为该抽象数据类型的名称为Circle，数据对象定义，数据对象定义为几何圆，操作包括构造函数、计算周长和面积等为几何圆，操作包括构造函数、计算周长和面积等以及计算结果如何获得。注意：这些定义不依赖于以及计算结果如何获得。注意：这些定义不依赖于数据

9、对象的具体表示，也没有给出操作实现的过程。数据对象的具体表示，也没有给出操作实现的过程。11数据抽象和封装机制的意义：数据抽象和封装机制的意义：（0）便于对软件的理解和使用（对用户）便于对软件的理解和使用（对用户）（1）简化软件开发：简化软件开发：假设一个问题经分析将使用假设一个问题经分析将使用A、B、C三个数据三个数据类型和协调代码求解。类型和协调代码求解。（a a）四位程序员，可由其中三位程序员各开发）四位程序员，可由其中三位程序员各开发一个数据类型，另一位程序员实现协调代码。一个数据类型，另一位程序员实现协调代码。（b b）一位程序员，数据抽象也可减少其在某一）一位程序员，数据抽象也可减

10、少其在某一具体时间需要考虑的范围。具体时间需要考虑的范围。12（2）易于测试和排除错误：易于测试和排除错误：如下图所示，数据抽象明显提高了测试和排除如下图所示，数据抽象明显提高了测试和排除错误的效率。错误的效率。13（3）有利于重用：）有利于重用：数据抽象和封装机制使开发人员可以将数据结数据抽象和封装机制使开发人员可以将数据结构及其操作实现为可重用的软件组件。这些组件构及其操作实现为可重用的软件组件。这些组件具有清晰的界面定义，更容易从一个软件系统中具有清晰的界面定义，更容易从一个软件系统中提取出来，应用于另一个软件系统。提取出来，应用于另一个软件系统。（4）便于改变数据类型的表示：）便于改变

11、数据类型的表示：由于数据封装，外界不能直接访问数据类型的由于数据封装，外界不能直接访问数据类型的内部表示。因此，只要操作接口不变，数据类型内部表示。因此，只要操作接口不变，数据类型内部表示和实现的改变不会影响使用该数据类型内部表示和实现的改变不会影响使用该数据类型的其他程序。的其他程序。141.3 算法定义算法定义 (Algorithm)P.5(Algorithm)P.5 数据结构的操作实际上是以算法的形式实现的。数据结构的操作实际上是以算法的形式实现的。定义：定义：算法算法是一个有限的指令集合，执行这些指令是一个有限的指令集合，执行这些指令可以完成某一特定任务。一个算法还应当满足以下可以完成

12、某一特定任务。一个算法还应当满足以下特性：特性：输入输入 零个或多个由外界提供的输入量。零个或多个由外界提供的输入量。输出输出 至少产生一个输出量。至少产生一个输出量。确定性确定性 每一指令都有确切的语义，无歧义。每一指令都有确切的语义，无歧义。有限性有限性 在执行有限步骤后结束。在执行有限步骤后结束。有效性有效性 每一条指令都应能经过有限层的表示转每一条指令都应能经过有限层的表示转化为计算平台的基本指令，即算法的指令必须是可化为计算平台的基本指令，即算法的指令必须是可行的。行的。15 程序和算法不同，程序可以不满足有限性。例程序和算法不同，程序可以不满足有限性。例 如，一个软件的总控程序在未

13、接受新的任务之前如，一个软件的总控程序在未接受新的任务之前一直处于一直处于“等待等待”循环中。循环中。实现数据结构操作的程序总是可结束的，因此，实现数据结构操作的程序总是可结束的，因此，后面将不再严格区分算法和程序这两个术语。后面将不再严格区分算法和程序这两个术语。必须保证指令的有效性，例如，指令必须保证指令的有效性，例如，指令“if（哥德（哥德巴赫猜想是真）巴赫猜想是真）then x=y；”是无效的。是无效的。作业：作业：P253 161.4 递归算法递归算法 P.6 直接递归直接递归：函数在执行过程中调用本身。：函数在执行过程中调用本身。间接递归间接递归：函数在执行过程中调用其它函数再经：

14、函数在执行过程中调用其它函数再经过这些函数调用本身。过这些函数调用本身。表达力：表达力：函数定义函数定义赋值赋值if-elseif-elsewhilewhile 函数定义函数定义赋值赋值if-elseif-else递归递归 17 当问题本身是递归定义的，其解法适合用递归描当问题本身是递归定义的，其解法适合用递归描述。述。例例1.3 阶乘函数的定义是阶乘函数的定义是 1 当当n=1n!=n(n-1)！当当n1 用递归方法计算阶乘函数简明扼要，易于理解，用递归方法计算阶乘函数简明扼要，易于理解，如下所示：如下所示：long Factorial(long n)if(n=1)return 1;/终止条

15、件 else return n*Factorial(n-1);/递归步骤 18用参数用参数n=5调用调用Factorial的过程如下：的过程如下：P.7Factorial(5)=(5*Factorial(4)=(5*(4*Factorial(3)=(5*(4*(3*Factorial(2)=(5*(4*(3*(2*Factorial(1)=(5*(4*(3*(2*1)=(5*(4*(3*2)=(5*(4*6)=(5*24)=12019 递归算法有四个特性：递归算法有四个特性：P.7P.7（1）必须有可最终达到的终止条件，否则程序将必须有可最终达到的终止条件，否则程序将陷入无穷循环；陷入无穷循环

16、；（2）子问题在规模上比原问题小，或更接近终止）子问题在规模上比原问题小，或更接近终止条件；条件；（3）子问题可通过再次递归调用求解或因满足终）子问题可通过再次递归调用求解或因满足终止条件而直接求解；止条件而直接求解；（4）子问题的解应能组合为整个问题的解。）子问题的解应能组合为整个问题的解。20例例1.4 全排列生成器：给定一个具有全排列生成器：给定一个具有n1n1个元素的个元素的集合，打印该集合的全排列。集合，打印该集合的全排列。分析四个元素分析四个元素(a(a，b b，c c，d)d)的情况，结果可以如的情况，结果可以如下构造：下构造：（1）a后接后接(b，c，d)的全排列的全排列 （2

17、）b后接后接(a，c，d)的全排列的全排列 （3）c后接后接(a，b，d)的全排列的全排列 （4）d后接后接(a，b，c)的全排列的全排列 这表明，如果能生成这表明，如果能生成n 1个元素的全排列，就能个元素的全排列，就能生成生成n个元素的全排列。个元素的全排列。/此处a为（b，c，d）全排列的前缀，其余类推 对于只有对于只有1个元素的集合，可以连同此时的前缀直个元素的集合，可以连同此时的前缀直接生成其全排列。于是，全排列生成问题的递归步接生成其全排列。于是，全排列生成问题的递归步骤和终止条件可以确定。骤和终止条件可以确定。21 用用n=3 和和 a0.2=(a,b,c)调用调用perm的示意

18、如下：的示意如下：22求解函数求解函数perm：void perm(char*a,const int k，const int n)/n 是数组a的元素个数，生成部分元素ak,an-1的全排列 int i;if(k=n-1)/终止条件，输出排列 for(i=0;in;i+)cout ai “”;/输出包括前 /缀，以构成整个问题的解 cout endl;i。k n-1前缀前缀 当前部分元素的全排列当前部分元素的全排列23 else /ak,an-1 的排列大于1，递归生成 for(i=k;i n;i+)char temp=ak;ak=ai;ai=temp;/交换ak /和 ai perm(a,k

19、+1,n);/生成 ak+1,an-1的全排列 temp=ak;ak=ai;ai=temp;/再次交换 ak 和 /ai,恢复原顺序 /else结束 /perm结束 通过调用通过调用perm(a,0,n)，可以生成，可以生成n个元素的全排个元素的全排列。列。24 当算法操作的数据结构是递归定义的时候也适合当算法操作的数据结构是递归定义的时候也适合使用递归。后面将有许多此类的重要例子使用递归。后面将有许多此类的重要例子。作业：作业：P255，6251.5 性能分析性能分析 P.9 除了正确性、可用性、可读性和容错性以外，除了正确性、可用性、可读性和容错性以外，算算法的性能法的性能是评价算法优劣的

20、重要指标。是评价算法优劣的重要指标。空间复杂性空间复杂性：算法开始运行直至结束过程中所需：算法开始运行直至结束过程中所需要的最大存储资源开销的一种度量。要的最大存储资源开销的一种度量。时间复杂性时间复杂性：算法开始运行直至结束所需要的执：算法开始运行直至结束所需要的执行时间的一种度量。行时间的一种度量。性能评价性能评价分为分为事前估计事前估计和和事后测量事后测量。性能分析性能分析就是指对算法的空间复杂性和时间复杂就是指对算法的空间复杂性和时间复杂性进行事前估计。性进行事前估计。261.5.1 空间复杂性空间复杂性 P.9 程序程序P的空间需求的空间需求 S(P)=c+SP(实例特性实例特性)其

21、中，其中，c是常数，是常数，SP(实例特性实例特性)是实例特性的是实例特性的函数。函数。分析的重点是分析的重点是SP(实例特性实例特性)。对于一个给定问题，首先要确定其实例特性，才对于一个给定问题，首先要确定其实例特性，才可能分析求解算法的空间要求。可能分析求解算法的空间要求。确定实例特性与具体问题的规模密切相关。确定实例特性与具体问题的规模密切相关。0n-10n-127例如例如:1 float rsum(float*a,const int n)2 if(n=0)return 0;/当n=1时返回a03 else return rsum(a,n1)+an1;4 rsum是一个递归求和算法，其实

22、例特性是是一个递归求和算法，其实例特性是n。每。每次递归调用需在栈顶保存次递归调用需在栈顶保存n的值、的值、a的值、返回值和的值、返回值和返回地址，共需返回地址，共需4个存储单元。个存储单元。由于算法的递归深度是由于算法的递归深度是n+1，故所需栈空间是，故所需栈空间是4(n+1)，即，即Srsum(n)=4(n+1)。281.5.2 时间复杂性时间复杂性 P.10 算法算法P的运行时间的运行时间 T(P)=c+TP(实例特性实例特性)时间复杂性分析的目的在于揭示算法的运行时间时间复杂性分析的目的在于揭示算法的运行时间随着其实例特性变化的规律。随着其实例特性变化的规律。将一组与实例特性无关的操

23、作抽象为一个程序步，将一组与实例特性无关的操作抽象为一个程序步，从而有效地简化性能分析的过程。从而有效地简化性能分析的过程。程序步程序步：算法中的一个在语法和语义上有意义的：算法中的一个在语法和语义上有意义的指令序列，而且该序列执行时间与算法的实例特指令序列，而且该序列执行时间与算法的实例特性无关。性无关。29各类各类C+C+语句的程序步数详见教科书（语句的程序步数详见教科书（P11-12P11-12）。）。可以通过列出各个语句的程序步数确定整个程序可以通过列出各个语句的程序步数确定整个程序的程序步数。的程序步数。例例1.5 程序程序sum:计算计算a0+a1+an-1 P9 1 float

24、sum(float*a,const int n)2 float s=0;3 for(int i=0;i 0时时Trsum(n)=2+Trsum(n-1)。321 float rsum(float*a,const int n)2 if(n=0)return 0;/当n=1时返回a03 else return rsum(a,n1)+an1;4 33通过反复代入可得：通过反复代入可得：Trsum(n)=2+Trsum(n-1)=2+2+Trsum(n-2)=2*2+Trsum(n-2)=2+2+2+Trsum(n-3)=2*3+Trsum(n-3)=2n+Trsum(0)=2n+2 所以所以rsum

25、的程序步数为的程序步数为2n+2。34 许多程序的实例特性并不仅仅依赖于实例规模许多程序的实例特性并不仅仅依赖于实例规模n，还可能与还可能与实例内容实例内容密切相关。密切相关。例如，顺序查找的程序步数，不仅与元素个数例如，顺序查找的程序步数，不仅与元素个数n，而且与集合内容有关。而且与集合内容有关。有时需要按最好、最坏和平均三种情况分析算法有时需要按最好、最坏和平均三种情况分析算法的时间复杂性。的时间复杂性。351.5.3 O表示法表示法 P.14 程序步本身就不是一个准确的概念，而是一个抽程序步本身就不是一个准确的概念，而是一个抽象的概念。象的概念。再作一次抽象，从由多种因素构成的时间复杂性

26、再作一次抽象，从由多种因素构成的时间复杂性中抽取出其主要因素，将常数抽象为中抽取出其主要因素，将常数抽象为1，有利于，有利于抓住主要矛盾，简化复杂性分析。抓住主要矛盾，简化复杂性分析。假设函数假设函数f和和g是非负函数。是非负函数。定义：定义：f(n)=O(g(n)当且仅当存在正值常数当且仅当存在正值常数c和和n0，使得对所有使得对所有n n0，f(n)c*g(n)。g(n)是参照物，通是参照物，通常是一些常用的标常是一些常用的标准函数。准函数。36常用的常用的7种度量：种度量：O(1)、O(log n)、O(n)、O(n log n)、O(n2)、O(n3)、O(2n)且且 n 充分大时：充

27、分大时：O(1)O(log n)O(n)O(n log n)O(n2)O(n3)=0)/从右向左扫描，遇到第一 /个0位停止，并将所经过的全部1置0 ai=0;i-;if(i=0)ai=1;40下面分别分析其最好、最坏和平均时间复杂性：下面分别分析其最好、最坏和平均时间复杂性：（1）最好情况最好情况：当右边第一位为：当右边第一位为0 0时，扫描停止，时，扫描停止，算法时间复杂性为算法时间复杂性为O(1)O(1)。（2 2）最坏情况最坏情况：当：当n n个二进制位全为个二进制位全为1 1时，需扫描时，需扫描n n位，算法时间复杂性为位，算法时间复杂性为O(n)O(n)。41（3 3）平均情况平均

28、情况。n n位二进制数共有位二进制数共有2 2n n种取值。以种取值。以n=3 n=3 为例，有下列取值：为例，有下列取值：42一般，从右到左有连续一般，从右到左有连续m个个1需需m+1次操作，这次操作，这种取值共种取值共2n-(m+1)个（个（m 100），只有复杂性较小（如，），只有复杂性较小（如，n，nlog2n，n2，n3）的算法是实用的。即使计算机的速度再提高）的算法是实用的。即使计算机的速度再提高1000倍，表中时间也只不过缩小倍，表中时间也只不过缩小1000倍。在这种情倍。在这种情况下，当况下，当n=100时，时，n10个程序步的运行时间是个程序步的运行时间是3.17年，年，2n

29、个程序步的运行时间是个程序步的运行时间是4 1010年。年。45 可见，如果一个算法的时间复杂性可见，如果一个算法的时间复杂性过高，当过高，当n n大于一定值时，再快的计算大于一定值时，再快的计算机也无法在实际可行的时间内完成其运机也无法在实际可行的时间内完成其运行。行。BANG！461.6 性能测量性能测量 性能测量性能测量：在一定的数据范围内准确获取程序运：在一定的数据范围内准确获取程序运行所需要的空间和时间，属于事后测量。行所需要的空间和时间，属于事后测量。测量的结果依赖于编译器及其设置，还依赖于程测量的结果依赖于编译器及其设置，还依赖于程序运行的计算机。下面重点研究性能（程序的计序运行

30、的计算机。下面重点研究性能（程序的计算时间）测量的方法。算时间）测量的方法。假设函数假设函数time(&hsec)将当前时间返回到变将当前时间返回到变量量hsec中，精度为中，精度为1毫秒。下面以测量顺序查找算毫秒。下面以测量顺序查找算法法seqsearch在最坏情况下的性能为例，说明性能在最坏情况下的性能为例，说明性能测量的方法。测量的方法。47int seqsearch(int*a,const int n,const int x)int i=n;a0=x;while(ai!=x)i-;return i;顺序查找算法的最坏时间复杂性是顺序查找算法的最坏时间复杂性是O(n)。为了。为了反映被忽

31、略的常数因子的影响，对于较小的反映被忽略的常数因子的影响，对于较小的n应选应选较多的值测量，对于较大的较多的值测量，对于较大的n值则可稀疏测量。值则可稀疏测量。限于时钟精度，对于太短的事件必须限于时钟精度，对于太短的事件必须重复重复m次，次，然后用测得的总时间除以然后用测得的总时间除以m求出事件的时间。求出事件的时间。48顺序查找算法的测量程序如下：顺序查找算法的测量程序如下：void TimeSearch(const long m)int a1001,n20;for(int j=1;j=1000;j+)aj=j;/初始化a for(j=0;j10;j+)/n的取值 nj=10*j;nj+10

32、=100*(j+1);cout “n 总时间 运行时间”endl;for(j=0;j20;j+)long start,stop;time(&start);/开始计时 for(long b=1;b=m;b+)int k=seqsearch(a,nj,0);/失败查找49 time(&stop);/停止计时 long totalTime=stop-start;float runTime=(float)(totalTime)/(float)m;cout nj totalTime runTimeendl;执行执行TimeSearch(300000)的输出如下表所示。的输出如下表所示。从该表可以看出，从

33、该表可以看出，t基本上随基本上随n线性增长。利用线性增长。利用n=0和和60这两点的数据，可得线性函数这两点的数据，可得线性函数 t=0.000096n+0.0008。由此可推算，当。由此可推算，当n=1000，t=0.00968。这。这与实际测量的数据完全吻合。与实际测量的数据完全吻合。5051规划性能测量实验时应注意以下问题：规划性能测量实验时应注意以下问题：时钟精度、期望的测量结果精度以及与此相关时钟精度、期望的测量结果精度以及与此相关的重复次数。的重复次数。根据是测量最坏性能还是平均性能，生成合适根据是测量最坏性能还是平均性能，生成合适的实验数据。的实验数据。实验目的：是为了比较还是为

34、了预测实际运行实验目的：是为了比较还是为了预测实际运行时间？时间？当实验目的是预测实际运行时间时，人们需要当实验目的是预测实际运行时间时，人们需要通过测量数据建立通过测量数据建立t与与n之间的函数关系。之间的函数关系。52 一般需用计算机生成导致一个算法最坏性能的一般需用计算机生成导致一个算法最坏性能的数据集。数据集。但在有的情况下计算机生成也非常困难。这时但在有的情况下计算机生成也非常困难。这时可根据实例特性的值随机生成足够量的实验数据，可根据实例特性的值随机生成足够量的实验数据，取这些数据导致的最长运行时间作为最坏性能。取这些数据导致的最长运行时间作为最坏性能。生成平均性能数据更为困难，一

35、般也采用随机生成平均性能数据更为困难，一般也采用随机生成的方法。生成的方法。实验作业：实验作业：P2515531.7 C+中的模板中的模板 P.22 C+的模板（的模板（template）有效地提高了函数和类）有效地提高了函数和类的可重用性。的可重用性。模板模板（又称为参数化（又称为参数化类型类型）是一种能被实例化）是一种能被实例化为任何数据类型的变量，这些类型既包括为任何数据类型的变量，这些类型既包括C+基本基本类型又包括类型又包括用户定义的类型用户定义的类型。模板函数模板函数:template int seqsearch(KeyType*a,const int n,KeyType x)/在

36、a1,a2,an中查找x int i=n;a0=x;/找不到时结束条件，返回值为找不到时结束条件，返回值为 0 while(ai!=x)i-;return i;54 通过调用通过调用seqsearch，可以很容易地在字符数组，可以很容易地在字符数组或浮点数数组中查找元素或浮点数数组中查找元素:char carray200;float farray300;char x=r;float y=306.523;/设此时以上数组已完成初始化 seqsearch(carray,200,x);seqsearch(farray,300,y);函数函数seqsearch的的KeyType在调用时被实例化为在调用

37、时被实例化为相应的实参类型，例如，调用相应的实参类型，例如，调用seqsearch(farray,300,y)表示在浮点数数组表示在浮点数数组farray中查找浮点数中查找浮点数y。55 seqsearch使用操作符使用操作符“!=”比较两个比较两个KeyType对对象，使用操作符象，使用操作符“=”将一个将一个KeyType对象赋值给另对象赋值给另一个一个KeyType对象。对象。对于用户定义的数据类型，这些操作不可能由对于用户定义的数据类型，这些操作不可能由系统预定义。用户必须系统预定义。用户必须重载重载这些操作以实现新的这些操作以实现新的语义。语义。56模板类模板类：P.23templa

38、te class Bag public:Bag(int MaxSize=DefaultSize);/假设DefaultSize已定义 int Add(const Type&x);/将对象x加入容器中 int Delete(const int k);/从容器中删除并打印k 个对象private:int top;/指示已用空间 Type*b;/用数组b存放Type对象 int n;/容量;57template Bag:Bag(int MaxSize=DefaultSize):n(MaxSize)b=new Typen;top=-1;template int Bag:Add(const Type&x

39、)if(top=n-1)return 0;/返回0表示加入失败 else b+top=x;return 1;58template int Bag:Delete(const int k)if(top+1 k)return 0;/返回0表示容器内元素不足k/个，删除失败 else for(int i=0;i k;i+)cout btop i “”;top=top-k;return 1;Bag f;Bag c;于是，于是，Bag对象对象f存放浮点数，存放浮点数，c存放圆。存放圆。591.8 效率与权衡效率与权衡 时间和空间的权衡；时间和空间的权衡；通用性和效率的权衡；通用性和效率的权衡；开发效率与运

40、行效率的权衡；开发效率与运行效率的权衡；等等。等等。60第第2 2章章 线性表线性表 本章学习最简单同时又最常用的数据结构本章学习最简单同时又最常用的数据结构线性表。线性表。612.1 线性表与数组线性表与数组 P.26 线性表线性表L定义为：定义为：(a0,a1,an-1)，n1 L=()，n=0 线性表由线性表由n个元素构成。当个元素构成。当n=0时，时，()表示空表示空线性表。当线性表。当n 1时，表中第一个元素有唯一的后时，表中第一个元素有唯一的后继，最后一个元素有唯一的前驱，其余元素有唯继，最后一个元素有唯一的前驱，其余元素有唯一的后继和前驱，因而呈现一的后继和前驱，因而呈现线性关系

41、线性关系。62 线性表的操作主要包括：线性表的操作主要包括：（1）计算表的长度）计算表的长度n。（2）从左到右（或从右到左）遍历表的元素。）从左到右（或从右到左）遍历表的元素。（3）访问第）访问第i个元素，个元素，0i n。（4）将新值赋予第）将新值赋予第i个元素，个元素，0i n。（5）将新元素插入第）将新元素插入第i个位置，个位置，0i n，使原来的，使原来的第第i，i+1，n1个元素变为第个元素变为第i+1，i+2，n个元素。个元素。（6）删除第）删除第i个元素，个元素，0i n，使原来的第，使原来的第i+1，i+2，n1个元素变为第个元素变为第i，i+1，n2个元素。个元素。63 假设

42、线性表的元素类型是浮点数，其假设线性表的元素类型是浮点数，其ADT定义为：定义为：class LinearList /对象:L=(a0,a1,an-1)或(),ai浮点数,0i npublic:LinearList();/构造函数，创建一个空表 int Length();/返回该实例的长度 void LeftToRight();/从左到右遍历全部元素 float Retrieve(int i);/返回第i个元素的值 void Store(int i,float v);/将v的值赋予第i个元素 void Insert(int i,float v);/将v作为第i个元素插入 float Delet

43、e(int i);/删除第i个元素并返回其值;64 如何表示线性表的结构，从而高效实现这些操如何表示线性表的结构，从而高效实现这些操作？作？最通常的方法是用程序设计语言提供的数组，最通常的方法是用程序设计语言提供的数组，即用数组的第即用数组的第i个单元表示线性表的个单元表示线性表的ai元素。元素。数组第数组第i个单元与第个单元与第i+1个单元在物理上是连续存个单元在物理上是连续存放的，因此称上述方法为放的，因此称上述方法为顺序映射顺序映射（sequential mapping）。）。顺序映射使随机存取表中的任何元素的时间是顺序映射使随机存取表中的任何元素的时间是O(1)，但插入和删除第，但插入

44、和删除第i个元素将导致其后续元素的个元素将导致其后续元素的迁移。迁移。作业：作业：P622652.2 多项式多项式 P.27数学上，多项式数学上，多项式P(x)P(x)定义为：定义为：其中非零项的最大指数称为其中非零项的最大指数称为阶阶。多项式的多项式的ADTADT定义如下：定义如下：class Polynomial/对象：一个有序对的集合,其中，ai 是系数，ei 是指/数，且指数是0的整数。public:Polynomial();/返回多项式返回多项式 p(x)=066 int operator!();/若*this 是零多项式返回1，否则返回0 float Coef(int e);/返回

45、*this 中指数为e 的项的系数 int LeadExp();/返回*this 中最大指数 void AddTerm(int e,float c);/将 加入*this Polynomial Add(Polynomial poly);/返回多项式*this 与/poly之和。P1+P2+P3可表述为：/P1.Add(P2).Add(P3)Polynomial Mult(Polynomial poly);/返回多项式*this 与/poly之积。float Eval(float f);/计算并返回x=f时*this 多项式的值;672.2.1 多项式的表示多项式的表示 P.28规定规定:多项式

46、中的项按指数递减顺序排列。多项式中的项按指数递减顺序排列。方法方法1 1 定义一个有定义一个有MaxDegree+1MaxDegree+1个元素的数组表示个元素的数组表示系数，数组下标表示相应的指数：系数，数组下标表示相应的指数：private:int degree;/当前多项式的阶 float coefMaxDegree+1;/MaxDegree是多项式的最高阶若若p p是类是类PolynomialPolynomial的一个对象，则：的一个对象，则：p.degree=n p.coefi=an-i，0in /幂次信息隐藏在数组位置中幂次信息隐藏在数组位置中这种表示法使多项式的许多操作实现非常简

47、单。这种表示法使多项式的许多操作实现非常简单。68方法方法2 2 当当p.degree em-1 e0 0。为此，不仅需要显式存储系数，而且需要显式为此，不仅需要显式存储系数，而且需要显式存储指数。同时，为了充分利用存储资源，所有存储指数。同时，为了充分利用存储资源，所有Polynomial类的多项式都用一个元素类型为类的多项式都用一个元素类型为term的的数组数组termArray表示：表示：70term定义如下：定义如下：class Polynomial;/向前声明class term friend Polynomial;private:float coef;/系数 int exp;/指数

48、;71Polynomial的数据成员定义如下：的数据成员定义如下：private:static term termArrayMaxTerms;/静态成员声明 static int free;/静态成员声明 int Start,Finish;/多项式的起、始位置其中，其中，MaxTerms是常数。由于类中的静态成员声是常数。由于类中的静态成员声明不构成其定义，还必须在类定义之外定义静态成明不构成其定义，还必须在类定义之外定义静态成员如下：员如下：term Polynomial:termArrayMaxTerms;int Polynomial:free=0;/指示termArray中的下一个可用单

49、元 StarttermArray free Finish 72例如，例如，A(x)=2x800+3x3+1和和B(x)=7x5+x3+5x+2 一个多项式一个多项式p(x)的项数为的项数为p.Finishp.Start+1。当多项式的零项很多时，方法当多项式的零项很多时，方法3明显好于方法明显好于方法2。但当绝大多数都是非零项时，方法但当绝大多数都是非零项时，方法3所用空间大约所用空间大约是方法是方法2的两倍。的两倍。732.2.2 多项式相加多项式相加 P.30 用方法用方法3表示多项式表示多项式A和和B。由于多项式的项是按。由于多项式的项是按指数递减顺序排列的，因而通过对指数递减顺序排列的

50、，因而通过对A和和B逐项扫描，逐项扫描，比较指数，很容易实现比较指数，很容易实现 C=A+B。用函数用函数NewTerm将新的属于将新的属于C的项存入的项存入free所指所指的的termArray可用单元。可用单元。1 Polynomial Polynomial:Add(Polynomial B)2 Polynomial C;int a=Start;int b=B.Start;C.Start=free;float c;3 while(a=Finish&b=B.Finish)4 switch(compare(termArraya.exp,termArrayb.exp)5 case=:c=term