数据结构基础(上) ppt.ppt_第1页
数据结构基础(上) ppt.ppt_第2页
数据结构基础(上) ppt.ppt_第3页
数据结构基础(上) ppt.ppt_第4页
数据结构基础(上) ppt.ppt_第5页
已阅读5页,还剩284页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

JYP,1,数据结构基础(上),教材: 数据结构(C+描述)(金远平编著,清华大学出版社),JYP,2,第1章 基本概念和方法,本章论述学习和研究数据结构所必须的并且将反复出现的基本概念和方法。,JYP,3,1.1 数据结构与软件系统,设计解决实际问题的计算机软件系统,首先需要建立被处理对象的数据模型。 数据和世上万物一样,都是具有结构的。人们很自然地用数据结构表示应用领域的被处理对象。例如,树和图。 数据结构由一个数据对象以及该对象中的所有数据元素之间的关系组成。 数据元素本身可以是数据结构,因此,可以构造非常复杂的数据结构。,JYP,4,为了模拟实际问题的求解过程和现实对象的行为,还必须提供对数据结构的相应操作。 数据结构的实现是以下一层数据结构表示上一层数据结构,直至以程序设计语言提供的基本数据类型表示的过程。 评价数据结构表示能力的标准主要是它能否方便且有效地实现需要的操作,而实现操作的算法设计及其效率高低也依赖于数据结构表示。 数据结构的定义、表示及其操作的实现相互关联,都是数据结构研究的重要内容。,JYP,5,计算机软件系统可看成是通过不同层次的数据结构及其操作实现的。例如:,JYP,6,中间层数据结构起着核心作用,称之为建模层。 对数据结构的研究产生了一批通用性强、具有很高实用价值的中间层数据结构,如数组、字符串、集合、线性表、栈、队列、链表、树、图、符号表等。 系统地学习进而掌握数据结构的知识和方法,对于提高设计与开发软件系统尤其是复杂软件系统的能力,无疑是十分重要的。,JYP,7,1.2 数据抽象与封装,抽象和封装的概念在日常生活中是普遍存在的,例如,人们常用的手机。 通过数据封装,将一个数据对象的内部结构和实现细节对外屏蔽。 通过数据抽象,将一个数据对象的规格说明与其实现分离,对外提供简洁、清晰的接口。 数据结构多层表示的过程反过来也就是从基础数据结构到应用领域数据结构的不断抽象与封装的过程。,JYP,8,用抽象数据类型(ADT)描述数据抽象与封装是一种自然、有效的方法。 数据类型由一个数据对象的集合和一组作用于这些数据对象的操作组成。例如,C+的基本数据类型char、int、float和double等。 抽象数据类型是一个数据类型,该数据类型的组织遵循将数据对象及对这些数据对象的操作的规格说明与这些数据对象的表示、操作的实现相分离的原则。,JYP,9,当强调一个数据对象的结构时,使用数据结构的概念。 与数据结构的概念对比,抽象数据类型包含了一个数据结构的集合,还包含了对数据结构的操作。 抽象数据类型成为描述数据结构及其操作的有效方式。 定义ADT的语言本质上不依赖具体的程序设计语言,这里采用C+描述。,JYP,10,例1.1 抽象数据类型“圆”的定义为: class Circle / 对象: 几何圆 public: Circle(float r); / 构造函数,创建一个半径为r的对象实例 float Circumference( ); / 返回该实例的周长 float Area( ); / 返回该实例的面积 ; 该抽象数据类型的名称为Circle,数据对象定义为几何圆,操作包括构造函数、计算周长和面积等。注意:这些定义不依赖于数据对象的具体表示,也没有给出操作实现的过程。,JYP,11,数据抽象和封装机制的意义: (1)简化软件开发: 假设一个问题经分析将使用A、B、C三个数据类型和协调代码求解。 (a)四位程序员,可由其中三位程序员各开发一个数据类型,另一位程序员实现协调代码。 (b)一位程序员,数据抽象也可减少其在某一具体时间需要考虑的范围。,JYP,12,(2)易于测试和排除错误: 如下图所示,数据抽象明显提高了测试和排除错误的效率。,JYP,13,(3)有利于重用: 数据抽象和封装机制使开发人员可以将数据结构及其操作实现为可重用的软件组件。这些组件具有清晰的界面定义,更容易从一个软件系统中提取出来,应用于另一个软件系统。 (4)便于改变数据类型的表示: 由于数据封装,外界不能直接访问数据类型的内部表示。因此,只要操作接口不变,数据类型内部表示和实现的改变不会影响使用该数据类型的其他程序。,JYP,14,1.3 算法定义,数据结构的操作实际上是以算法的形式实现的。 定义:算法是一个有限的指令集合,执行这些指令可以完成某一特定任务。一个算法还应当满足以下特性: 输入 零个或多个由外界提供的输入量。 输出 至少产生一个输出量。 确定性 每一指令都有确切的语义,无歧义。 有限性 在执行有限步骤后结束。 有效性 每一条指令都应能经过有限层的表示转化为计算平台的基本指令,即算法的指令必须是可行的。,JYP,15,程序和算法不同,程序可以不满足有限性。例 如,一个软件的总控程序在未接受新的任务之前一直处于“等待”循环中。 实现数据结构操作的程序总是可结束的,因此,后面将不再严格区分算法和程序这两个术语。 必须保证指令的有效性,例如,指令“if (哥德巴赫猜想是真)then x = y;”是无效的。 作业:P253,JYP,16,1.4 递归算法,直接递归:函数在执行过程中调用本身。 间接递归:函数在执行过程中调用其它函数再经过这些函数调用本身。 表达力:,函数定义 赋值 if-else while,函数定义 赋值 if-else 递归,JYP,17,当问题本身是递归定义的,其解法适合用递归描述。 例1.3 阶乘函数的定义是 1 当n=1 n! = n(n-1)! 当n1 用递归方法计算阶乘函数简明扼要,易于理解,如下所示: long Factorial ( long n ) if ( n = = 1 ) return 1; / 终止条件 else return n*Factorial ( n-1); / 递归步骤 ,JYP,18,用参数n= 5调用Factorial的过程如下: Factorial (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) = 120,JYP,19,递归算法有四个特性: (1)必须有可最终达到的终止条件,否则程序将陷入无穷循环; (2)子问题在规模上比原问题小,或更接近终止条件; (3)子问题可通过再次递归调用求解或因满足终止条件而直接求解; (4)子问题的解应能组合为整个问题的解。,JYP,20,例1.4 全排列生成器:给定一个具有n1个元素的集合,打印该集合的全排列。 分析四个元素(a,b,c,d)的情况,结果可以如下构造: (1) a后接(b,c,d)的全排列 (2) b后接(a,c,d)的全排列 (3) c后接(a,b,d)的全排列 (4) d后接(a,b,c)的全排列 这表明,如果能生成n 1个元素的全排列,就能生成n个元素的全排列。,JYP,21,对于只有1个元素的集合,可以直接生成其全排列。于是,全排列生成问题的递归步骤和终止条件可以确定。 求解函数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; ,JYP,22,else / ak,an-1 的排列大于1,递归生成 for ( i = k; i n; i+) char temp = ak; ak = ai; ai = temp; / 交换ak / 和 ai perm(a,k+1,n); / 生成 ak+1,an-1的全排列 temp = ak; ak = ai; ai = temp; / 再次交换 ak 和 / ai , 恢复原顺序 / else结束 / perm结束 通过调用perm(a, 0, n),可以生成n个元素的全排列。,JYP,23,用n = 3 和 a02 = (a, b, c)调用perm的示意如下:,JYP,24,当算法操作的数据结构是递归定义的时候也适合使用递归。后面将有许多此类的重要例子。 作业:P255,6,JYP,25,1.5 性能分析,除了正确性、可用性、可读性和容错性以外,算法的性能是评价算法优劣的重要指标。 空间复杂性:算法开始运行直至结束过程中所需要的最大存储资源开销的一种度量。 时间复杂性:算法开始运行直至结束所需要的执行时间的一种度量。 性能评价分为事前估计和事后测量。 性能分析就是指对算法的空间复杂性和时间复杂性进行事前估计。,JYP,26,1.5.1 空间复杂性,程序P的空间需求 S(P) = c + SP(实例特性) 其中,c是常数,SP(实例特性) 是实例特性的函数。 分析的重点是SP(实例特性)。 对于一个给定问题,首先要确定其实例特性,才可能分析求解算法的空间要求。 确定实例特性与具体问题密切相关。,JYP,27,例如: 1 float rsum (float *a, const int n) 2 if (n = 0 ) return 0; / 当n = 1时返回a0 3 else return rsum( a, n1) + an1; 4 rsum是一个递归求和算法,其实例特性是n。每次递归调用需在栈顶保存n的值、a的值、返回值和返回地址,共需4个存储单元。 由于算法的递归深度是n+1,故所需栈空间是4(n+1),即Srsum(n) = 4(n+1)。,JYP,28,1.5.2 时间复杂性,算法P的运行时间 T(P) = c + TP(实例特性) 时间复杂性分析的目的在于揭示算法的运行时间随着其实例特性变化的规律。 将一组与实例特性无关的操作抽象为一个程序步,从而有效地简化性能分析的过程。 程序步:算法中的一个在语法和语义上有意义的指令序列,而且该序列执行时间与算法的实例特性无关。,JYP,29,各类C+语句的程序步数详见教科书。 可以通过列出各个语句的程序步数确定整个程序的程序步数。 例1.5 程序sum: 1 float sum (float *a, const int n) 2 float s = 0; 3 for (int i = 0; i n; i+) 4 s += ai; 5 return s; 6 ,JYP,30,其中各语句的程序步数如下所示:,其总程序步数是2n+3。,JYP,31,例1.6 设rsum(a, n)的程序步数为Trsum(n),其各语句的程序步数如下:,可见,当n = 0时Trsum(0) = 2;当n 0时Trsum(n) = 2+ Trsum(n-1)。,JYP,32,通过反复代入可得: 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的程序步数为2n+2。,JYP,33,许多程序的实例特性并不仅仅依赖于实例规模n,还可能与实例内容密切相关。 例如,二分查找的程序步数,不仅与元素个数n,而且与集合内容有关。 有时需要按最好、最坏和平均三种情况分析算法的时间复杂性。,JYP,34,1.5.3 O表示法,程序步本身就不是一个准确的概念,而是一个抽象的概念。 再作一次抽象,从由多种因素构成的时间复杂性中抽取出其主要因素,将常数抽象为1,有利于抓住主要矛盾,简化复杂性分析。 假设函数f和g是非负函数。 定义:f(n) = O(g(n) 当且仅当存在正值常数c和n0,使得对所有n n0,f(n) c*g(n)。,JYP,35,例1.8 5n + 4 = O(n) 100n + 6 = O(n) 10 n2 + 4n + 2 = O(n2) 6*2n + n2 = O(2n) 3n + 2 O(1) O(1)表示常数, O(log n) 表示对数,O(n)表示线性,O(n2)表示平方,O(n3)表示立方, O(2n)表示指数。,JYP,36,f(n) = O(g(n)只表示对所有n n0,g(n)是f(n)的上界。因此,n = O(n2) = O(n3) = O(2n)。为了使f(n) = O(g(n)提供尽可能多的信息,g(n)应尽可能小。 有时,由于现有分析能力的限制,人们还不能得出一个算法计算时间的准确数量级。例如对实际计算时间为O(n log n)的算法,目前的分析结果只能表明其计算时间是O(n2),这时说该算法的计算时间是O(n2)也没错,待到以后认识深入了,可以改说成O(n log n)。,JYP,37,定理1.1 设f(n)= amnm + am-1nm-1 + + a1n + a0,则 f(n) = O(nm)。,JYP,38,例1.11 n位二进制数加1的时间复杂性。设数组a模拟一个n位二进制数,下列算法将a表示的二进制数加1。 emun Binary 0, 1 ; void BinaryAddOne ( Binary *a, const int n ) int i = n-1; while (ai = = 1 ,JYP,39,下面分别分析其最好、最坏和平均时间复杂性: (1)最好情况:当右边第一位为0时,扫描停止,算法时间复杂性为O(1)。 (2)最坏情况:当n个二进制位全为1时,需扫描n位,算法时间复杂性为O(n)。,JYP,40,(3)平均情况。n位二进制数共有2n种取值。以n=3 为例,有下列取值:,JYP,41,一般,从右到左有连续m个1需m + 1次操作,这种取值共2n-(m+1)个(m n);n个二进制位全为1只有1种可能,需n + 1次操作。因此,对于n 1,该算法的平均时间复杂性为:,JYP,42,O表示法具有渐进性质,对于实例规模较小的问题,常数因子可能起主要作用。 例如,如果算法P实际运行106n毫秒,算法Q实际运行n2毫秒,并且总有n 106,则在其它因素等同情况下,算法Q更适用。 作业:P258,12,JYP,43,1.5.5 实际可行的复杂性,下一页中的表列出了在每秒10亿个程序步的计算机上时间复杂性为f(n)的算法运行所需要的时间。 从实际可行的角度考虑,对于合理大的n(例如,n100),只有复杂性较小(如,n,nlog2n,n2,n3)的算法是实用的。即使计算机的速度再提高1000倍,表中时间也只不过缩小1000倍。在这种情况下,当n=100时,n10个程序步的运行时间是3.17年,2n个程序步的运行时间是41010年。,JYP,44,可见,如果一个算法的时间复杂性过高,当n大于一定值时,再快的计算机也无法在实际可行的时间内完成其运行。,JYP,45,1.6 性能测量,性能测量:在一定的数据范围内准确获取程序运行所需要的空间和时间,属于事后测量。 测量的结果依赖于编译器及其设置,还依赖于程序运行的计算机。下面重点研究性能(程序的计算时间)测量的方法。 假设函数time ( &hsec )将当前时间返回到变量hsec中,精度为1毫秒。下面以测量顺序查找算法seqsearch在最坏情况下的性能为例,说明性能测量的方法。,JYP,46,int seqsearch (int *a, const int n, const int x ) int i = n; a0 = x; while (ai != x) i-; return i; 顺序查找算法的最坏时间复杂性是O(n)。为了反映被忽略的常数因子的影响,对于较小的n应选较多的值测量,对于较大的n值则可稀疏测量。 限于时钟精度,对于太短的事件必须重复m次,然后用测得的总时间除以m求出事件的时间。,JYP,47,顺序查找算法的测量程序如下: 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 = 100*( j+1 ); cout “ n 总时间 运行时间” endl; for ( j=0; j20; j+ ) long start, stop; time ( / 失败查找,JYP,48,time ( 执行TimeSearch(300000)的输出如下表所示。 从该表可以看出,t基本上随n线性增长。利用n = 0和60这两点的数据,可得线性函数 t = 0.000096n + 0.0008。由此可推算,当n = 1000,t = 0.00968。这与实际测量的数据完全吻合。,JYP,49,JYP,50,规划性能测量实验时应注意以下问题: 时钟精度、期望的测量结果精度以及与此相关的重复次数。 根据是测量最坏性能还是平均性能,生成合适的实验数据。 实验目的:是为了比较还是为了预测实际运行时间? 当实验目的是预测实际运行时间时,人们需要通过测量数据建立t与n之间的函数关系。,JYP,51,一般需用计算机生成导致一个算法最坏性能的数据集。 但在有的情况下计算机生成也非常困难。这时可根据实例特性的值随机生成足够量的实验数据,取这些数据导致的最长运行时间作为最坏性能。 生成平均性能数据更为困难,一般也采用随机生成的方法。 实验作业:P2515,JYP,52,1.7 C+中的模板,C+的模板(template)有效地提高了函数和类的可重用性。 模板(又称为参数化类型)是一种能被实例化为任何数据类型的变量,这些类型既包括C+基本类型又包括用户定义的类型。 模板函数: template int seqsearch (KeyType *a, const int n, KeyType x ) int i=n; a0=x; while (ai != x) i-; return i; ,JYP,53,通过调用seqsearch,可以很容易地在字符数组或浮点数数组中查找元素: char carray200; float farray300; char x = r; float y = 306.523; / 设此时以上数组已完成初始化 seqsearch(carray, 200, x); seqsearch(farray, 300, y); 函数seqsearch的KeyType在调用时被实例化为相应的实参类型,例如,调用seqsearch(farray, 300, y)表示在浮点数数组farray中查找浮点数y。,JYP,54,seqsearch使用操作符“!=”比较两个KeyType对象,使用操作符“=”将一个KeyType对象赋值给另一个KeyType对象。 对于用户定义的数据类型,这些操作不可能由系统预定义。用户必须重载这些操作以实现新的语义。,JYP,55,模板类: template class Bag public: Bag ( int MaxSize = DefaultSize ); / 假设DefaultSize已定义 int Add (const Type,JYP,56,template Bag:Bag ( int MaxSize = DefaultSize ):n(MaxSize) b = new Typen; top = -1; template int Bag:Add (const Type ,JYP,57,template int Bag:Delete (const int k) if (top + 1 f; Bag c; 于是,Bag对象f存放浮点数,c存放圆。,JYP,58,1.8 效率与权衡,时间和空间的权衡; 通用性和效率的权衡; 开发效率与运行效率的权衡; 等等。,JYP,59,第2章 线性表,本章学习最简单同时又最常用的数据结构线性表。,JYP,60,2.1 线性表与数组,线性表L定义为: ( a0, a1, , an-1),n1 L = ( ), n = 0 线性表由n个元素构成。当n = 0时, ( ) 表示空线性表。当n 1时,表中第一个元素有唯一的后继,最后一个元素有唯一的前驱,其余元素有唯一的后继和前驱,因而呈现线性关系。,JYP,61,线性表的操作主要包括: (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个元素。,JYP,62,假设线性表的元素类型是浮点数,其ADT定义为: class LinearList / 对象: L = ( a0, a1, , an-1) 或 ( ), ai浮点数, 0i n public: 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 Delete( int i ); / 删除第i个元素并返回其值 ;,JYP,63,如何表示线性表的结构,从而高效实现这些操作? 最通常的方法是用程序设计语言提供的数组,即用数组的第i个单元表示线性表的ai元素。 数组第i个单元与第i+1个单元在物理上是连续存放的,因此称上述方法为顺序映射(sequential mapping)。 顺序映射使随机存取表中的任何元素的时间是O(1),但插入和删除第i个元素将导致其后续元素的迁移。 作业:P622,JYP,64,2.2 多项式,数学上,多项式P(x)定义为:,其中非零项的最大指数称为阶。 多项式的ADT定义如下: class Polynomial / 对象:一个有序对的集合, 其中,ai 是系数,ei 是指 / 数,且指数是0的整数。 public: Polynomial ( ); / 返回多项式 p(x) = 0,JYP,65,int operator ! ( ); / 若 *this 是零多项式返回1,否则返回0 float Coef (int e); / 返回*this 中指数为e 的项的系数 int LeadExp ( ); / 返回*this 中最大指数 void AddTerm (int e, float c); / 将 加入*this Polynomial Add (Polynomial poly); / 返回多项式 *this 与 / poly之和 Polynomial Mult (Polynomial poly); / 返回多项式 *this 与 / poly之积 float Eval ( float f); / 计算并返回x = f时*this 多项式的值 ;,JYP,66,2.2.1 多项式的表示,规定:多项式中的项按指数递减顺序排列。 方法1 定义一个有MaxDegree+1个元素的数组表示系数,数组下标表示相应的指数: private: int degree; / 当前多项式的阶 float coefMaxDegree+1; / MaxDegree是多项式的最高阶 若p是类Polynomial的一个对象,则: p.degree = n p.coefi = an-i,0in 这种表示法使多项式的许多操作实现非常简单。,JYP,67,方法2 当p.degree MaxDegree时,方法1很浪费空间,可动态定义coef数组的元素个数: private: int degree; float *coef; 构造函数为: Polynomial:Polynomial( int d) degree = d; coef = new float degree+1; / 动态申请数组空间 ,JYP,68,方法3 对于有很多零项的稀疏多项式,方法2仍然很浪费空间。例如x800+3仅有2个非零项,其余799项都是零项。这时,只存储非零项更为有效。由此将多项式表示为另一种形式:,其中,bi0,( 0im ),em em-1 e0 0。 为此,不仅需要显式存储系数,而且需要显式存储指数。同时,为了充分利用存储资源,所有Polynomial类的多项式都用一个元素类型为term的数组termArray表示:,JYP,69,term定义如下: class Polynomial; / 向前声明 class term friend Polynomial; private: float coef; / 系数 int exp; / 指数 ;,JYP,70,Polynomial的私有成员定义如下: private: static term termArrayMaxTerms; / 静态成员声明 static int free; / 静态成员声明 int Start, Finish; / 多项式的起、始位置 其中,MaxTerms是常数。由于类中的静态成员声明不构成其定义,还必须在类定义之外定义静态成员如下: term Polynomial:termArrayMaxTerms; int Polynomial:free = 0; / 指示termArray中的下一个可用单元,JYP,71,例如,A(x) = 2x800+3x3+1和B(x) = 7x5+x3+5x+2,一个多项式p(x)的项数为p.Finishp.Start+1。 当多项式的零项很多时,方法3明显好于方法2。但当绝大多数都是非零项时,方法3所用空间大约是方法2的两倍。,JYP,72,2.2.2 多项式相加,用方法3表示多项式A和B。由于多项式的项是按指数递减顺序排列的,因而通过对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 ,JYP,73,9 case : NewTerm(termArraya.coef, termArraya.exp); 13 a+; 14 15 for (;a=Finish;a+) NewTerm(termArraya.coef, termArraya.exp);/加入A(x)的剩余项 16 for (;b=b.Finish;b+) NewTerm(termArrayb.coef, termArrayb.exp);/加入B(x)的剩余项 17 C.Finish=free1; 18 return C; 19,JYP,74,void Polynomial:NewTerm(float c, int e) /将新项加入C(x)中 if (free = MaxTerms) cout “空间不够!” endl; return; termArrayfree.coef = c; termArrayfree.exp = e; free+; / NewTerm结束,JYP,75,分析: 设m和n分别是A和B的非零项个数。 第2行O(1)。 第3行的循环内执行一次,a或b或a和b增加1,循环次数最多是m+n1。 第15和16行的循环的总次数不超过m+n。 整个算法的时间复杂性是O(m+n)。 free超过MaxTerms时的处理很麻烦。 作业:P624,5,JYP,76,2.3 稀疏矩阵,矩阵是常用的数学对象,由m行、n列元素构成,也称为m n矩阵。当m = n时,称该矩阵为方阵。 例子:,JYP,77,表示: 用二维数组,如Amn,表示矩阵十分自然。但对于大型稀疏矩阵,非零项只占所需空间的很小部分。 较好的办法是只存储非零项,而将零元素作为缺省值。,JYP,78,稀疏矩阵抽象数据类型 class SparseMatrix / 对象: 三元组的集合,行、列、值都是整型 public: SparseMatrix ( int Rows, int Cols ); SparseMatrix Transpose ( ); / 返回(*this)矩阵的转置矩阵 SparseMatrix Add ( SparseMatrix b); SparseMatrix Multiply ( SparseMatrix b); ;,JYP,79,2.3.1 稀疏矩阵的表示,用三元组唯一表示矩阵元素 用一个由此三元组构成的数组表示整个稀疏矩阵 所有三元组按行号递增顺序排序,同一行内的三元组按列号递增顺序排序 存储稀疏矩阵的行数、列数和非零项的个数,JYP,80,class SparseMatrix; / 向前声明 class MatrixTerm friend SparseMatrix; private: int row, col, value; / 行、列、值 ; 并在SparseMatrix中定义: private: int Rows, Cols, Terms; / 行数、列数、非零项个数 MatrixTerm smArrayMaxTerms; / MaxTerms是常数,JYP,81,前面的稀疏矩阵用三元组表示为:,JYP,82,2.3.2 稀疏矩阵的转置,图2.3(b)是图2.3(a)中矩阵的转置:,JYP,83,初始方法: 顺序扫描原矩阵数组,取元素,将其转变为存入新矩阵。 问题:转置矩阵中的三元组也必须按照行、列排序,而在处理完所有元素之前,我们并不知道应该存放在什么位置。 改进方法: 按原矩阵的列构建新矩阵的行,对j = 0, , Cols-1 顺序扫描原矩阵,找到第j列元素,将其转变为新矩阵的第j行元素存入三元组数组的当前位置。,JYP,84,由此得算法: 1 SparseMatrix SparseMatrix:Transpose ( ) / 返回矩阵a (*this)的转置矩阵 2 SparseMatrix b; 3 b.Rows = Cols; / b的行数 = a的列数 4 b.Cols = Rows; / b的列数 = a的行数 5 b.Terms = Terms; 6 if ( Terms 0 ) / 不是零矩阵 7 int CurrentB = 0; / 当前位置指针 8 for ( int c = 0; c Cols; c+ ) / 按照列转置 9 for ( int i = 0; i Terms; i+ ) 10 if (smArrayi.col = c ) / 找到第c列的元素 11 b.smArrayCurrentB.row = c; 12 b.smArrayCurrentB.col = smArrayi.row;,JYP,85,13 b.smArrayCurrentB.value= smArrayi.value; 14 CurrentB+; 15 16 / if ( Terms 0 )结束 17 return b; 18 / Transpose结束 分析:第8到15行的循环共执行Cols次,每次执行导致第10行的判断执行Terms次,第10行的总时间是ColsTerms次。第11,12,13和14行执行Terms次。第27行只用常数时间。算法的总时间复杂性是O(ColsTerms),需要O(1)辅助空间。,JYP,86,进一步改进: 第915行的循环扫描一次仅找到少数有效三元组,导致算法Transpose的时间代价较大。如果先扫描一遍矩阵a,获得其中各列的元素个数,就可知道矩阵b各行的元素个数。由此很容易推算出b中各行的开始位置。这样,可以再次扫描a,逐项将a中元素置入b的正确位置。 RowSizei 矩阵b第i行的元素个数 RowStarti 矩阵b第i行的当前可置入位置 初始时, RowStart0 = 0 RowStarti = RowStarti1+RowSizei1,JYP,87,以后每次往b的第i行置入一个元素,RowStarti加1。由此得算法FastTranspose: 1 SparseMatrix SparseMatrix:FastTranspose ( ) / 快速转置 2 int *rowSize = new intCols; 3 int *rowStart = new intCols; 4 SparseMatrix b; 5 b.Rows = Cols; b.Cols = Rows; b.Terms = Terms; 6 if ( Terms 0 ) / 计算b中第i行的非零项个数 7 for (int i = 0; i Cols; i+) rowSizei = 0; / 初始化 8 for ( i = 0; i Terms; i+ ) rowSizesmArrayi.col+; 9 RowStart0 = 0; / RowStarti = b中第i行的开始位置 10 for (i = 1;i Cols;i+) rowStarti = rowStarti-1 + rowSizei-1;,JYP,88,11 for ( i = 0; i Terms; i+ ) / 从 a 向b复制 12 int j = RowStartsmArrayi.col; 13 b.smArrayj.row = smArrayi.col; 14 b.smArrayj.col = smArrayi.row; 15 b.smArrayj.value = smArrayi.value; 16 RowStartsmArrayi.col+; 17 18 19 delete rowSize; delete rowStart; 20 return b; 21,JYP,89,对图2.3(a)的稀疏矩阵应用算法FastTranspose,执行完第10行后,RowSize和RowStart的值为:,FastTranspose的四个循环分别迭代Cols、Terms、Cols-1和Terms次,总时间复杂性是O(Cols + Terms)。 与Transpose相比,FastTranspose 多使用了O(Cols)的辅助空间,但改进了计算时间。这体现了时间与空间的权衡。,JYP,90,作业:P627,9,JYP,91,2.4 字符串,字符串是由n(n0)个字符构成的线性序列,可表示为S = s0, , sn-1, 其中,si 取自字符集,n是字符串的长度。若n = 0,则S为空串。通过从字符串中删除零或多个任意位置的字符可得其一个子序列。 class String / 对象: n0个字符构成的线性序列 public: String (const char *init, int m);/ 初始化为长度等于m的 / 字符串init int operator = (String t ); int operator ! ( ); int Length ( ); String Concat (String t);,JYP,92,String Substr (int i, int j); / 返回由字符串 *this 的第i个位 / 置及其后共计j个字符构成的子字符串 int Find ( String pat ); / 若pat是空字符串,或pat不是 / *this的子字符串,返回-1;否则返回*this中 / 第一个与pat匹配的子字符串的开始位置i int Lcs ( String x ); / 返回*this和x的最长公共子序 / 列的长度 ;,JYP,93,2.4.1 字符串模式匹配的简单算法,设有字符串s和pat,其长度分别为LengthS 和LengthP。顺序考察s的第i个位置,判定其是否为一个匹配的起点,直至首次成功匹配,如下图所示:,设字符串由类型为char*的私有数据成员str表示,函数Find实现了上述策略。,JYP,94,int String:Find ( String pat ) char *p = pat.str, *q = str; int i = 0; / i 是起点 if ( *p / pat 为空字符串,或不出现在s中 / Find结束,JYP,95,对于s的每一个被考察的位置,都可能在匹配pat的最后字符时失败,因此Find的时间复杂性是O(LengthPLengthS)。 即使改变策略,先检查pat的最后字符与s的第i + LengthP 1个位置的字符,再检查其它字符,也不能根本改进时间复杂性,因为匹配还可能最后在pat的倒数第2个字符处失败。,JYP,96,2.4.2 字符串模式匹配的KMP算法,能否用O(LengthP+LengthS)的时间求解字符串模式匹配问题呢? 这样的算法一定是最佳的,因为在最坏情况下求解此问题必须至少扫描s和pat一遍。 Find需要回溯扫描s中的字符,没有充分利用前面扫描获得的知识,因而效率低下。 要有根本改进,应避免回溯扫描。这就需要利用模式pat中子字符串关系规律和已有扫描成果。Knuth,Morris和Pratt提出的算法(KMP算法)就是基于这种思想,并达到了线性时间复杂性。,JYP,97,KMP算法的基本策略是:预处理模式pat,获得其中与模式匹配有关的子字符串关系规律,从而当匹配失败发生时,可以确定继续与s当前位置匹配的pat的新位置。 设s = s0, , sm-1,pat = p0, , pn-1,当前正在比较si与pj是否相等。如果相等则i、j各自向前推进一步,继续比较。否则,有两种情况需要处理:,JYP,98,(1)j = 0,只需继续比较si+1与p0即可,如下图所示:,JYP,99,(2)j 0,设y=p0, , pj-1,x是y的两头匹配的最大真子字符串,且x=p0, , pk,则由于已有匹配的结果,si-k-1, , si-1=pj-k-1, , pj-1=x,从而si-k-1, , si-1 = p0, , pk,因此 si 可与 pk+1继续比较。如下图所示:,JYP,100,注意: 由于x是y的的两头匹配的最大子字符串,用反证法不难证明,si 与 pk+1继续比较不会遗漏模式。 y也是其本身两头匹配的最大子字符串,但y不能作为x用,否则比较将陷入无穷循环。 将以上分析形式化,可得模式p = p0, , pn-1的失败函数f 的定义: f(j) =,最大的kj,使得p0, , pk=pi-k, , pj ,如果 这样的k0存在的话 1 否则,JYP,101,例如,pat = “abcabcacab”,有,根据f定义,很容易得出以下模式匹配规则:若已有si-j, , si-1 = p0, , pj-1 且si pj ,则当j = 0可继续比较si+1与p0;当j 0可继续比较si与pf(j-1)+1。 由此可得以下算法FastFind。,JYP,102,1 int String:FastFind ( String pat ) 2 3 int j = 0, i = 0; 4 int LengthP = pat.Length( ), LengthS = Length( ); 5 while ( j LengthP) 14 / FastFind 结束,JYP,103,对FastFind的分析: 第7、10行共最多可执行LengthS次,因为每次i都增加1,且i在算法中从不减少。 j最多可增加至LengthS(第7行)。 执行第11行的条件是j 0,且每次j至少减少1(注意f(j1)+1 (j1)+1=j),所以此行最多执行LengthS次。 因此,FastFind的总计算时间是O( LengthS)。,JYP,104,失败函数f的计算: f(0) = 1。 假设已有f(j1),则可通过以下观察计 算f(j):,若a = b,则f(j) = f(j-1)+1,否则(标记f1(j) = f(j),fm(j) = f( fm-1(j)),JYP,105,若a = c,则f(j) = f2(j-1)+1,否则可以继续计算下去,直至找到某个m,使第fm(j1)+1个位置的字符与a相等,或fm(j1) = 1且第0位置的字符仍不等于a。,JYP,106,由此,可得失败函数的另一种定义形式: f(j) =,1 如果j=0 fm(j1)+1 m是使得pfk(j-1)+1=pj 的最小的k 1 如果上述k不存在,由此定义可直接得出计算 f 的算法 fail。,JYP,107,1 void String:fail ( ) / 计算模式p ( *this)的失败函数 2 int Leng

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论