数据结构基础课件

1、数据结构基础 教材：数据结构（C+描述）（金远平编著，清华大学出版社，2005）讲课教师： 金远平，软件学院 1JYP 考试： 期末考试采用开卷方式，占总评成绩的70%。 平时作业和实验占总评成绩30%。 考试注重：概念、方法、技巧、思想、创新、关键步骤、程序设计风格2JYP 参考文献：1 E. Horowitz, S. Sahni, D. Mehta, Fundamentals of Data Structure In C+, Computer Science Press,19952 W. Ford and W. Topp, Data Structures with C+,清华大学出版社（影

2、印版）, 19973 T. A. Standish, Data Structures, Algorithms & Software Principles in C, Addison-Wesley Publishing Company, 19943JYP第1章 基本概念和方法 本章论述学习和研究数据结构所必须的并且将反复出现的基本概念和方法。 4JYP1.1 数据结构与软件系统 设计解决实际问题的计算机软件系统，首先需要建立被处理对象的数据模型。 数据和世上万物一样，都是具有结构的。人们很自然地用数据结构表示应用领域的被处理对象。例如，树和图。 数据结构由一个数据对象以及该对象中的所有数据元素之

3、间的关系组成。数据元素本身可以是数据结构，因此，可以构造非常复杂的数据结构。 5JYP 为了模拟实际问题的求解过程和现实对象的行为，还必须提供对数据结构的相应操作。数据结构的实现是以下一层数据结构表示上一层数据结构，直至以程序设计语言提供的基本数据类型表示的过程。 评价数据结构表示能力的标准主要是它能否方便且有效地实现需要的操作，而实现操作的算法设计及其效率高低也依赖于数据结构表示。 数据结构的定义、表示及其操作的实现相互关联，都是数据结构研究的重要内容。 6JYP计算机软件系统可看成是通过不同层次的数据结构及其操作实现的。例如： 7JYP中间层数据结构起着核心作用，称之为建模层。对数据结构的

4、研究产生了一批通用性强、具有很高实用价值的中间层数据结构，如数组、字符串、集合、线性表、栈、队列、链表、树、图、符号表等。 系统地学习进而掌握数据结构的知识和方法，对于提高设计与开发软件系统尤其是复杂软件系统的能力，无疑是十分重要的。 8JYP1.2 数据抽象与封装 抽象和封装的概念在日常生活中是普遍存在的，例如，人们常用的手机。通过数据封装，将一个数据对象的内部结构和实现细节对外屏蔽。通过数据抽象，将一个数据对象的规格说明与其实现分离，对外提供简洁、清晰的接口。数据结构多层表示的过程反过来也就是从基础数据结构到应用领域数据结构的不断抽象与封装的过程。9JYP用抽象数据类型（ADT）描述数据抽

5、象与封装是一种自然、有效的方法。 数据类型由一个数据对象的集合和一组作用于这些数据对象的操作组成。例如，C+的基本数据类型char、int、float和double等。 抽象数据类型是一个数据类型，该数据类型的组织遵循将数据对象及对这些数据对象的操作的规格说明与这些数据对象的表示、操作的实现相分离的原则。 10JYP当强调一个数据对象的结构时，使用数据结构的概念。与数据结构的概念对比，抽象数据类型包含了一个数据结构的集合，还包含了对数据结构的操作。抽象数据类型成为描述数据结构及其操作的有效方式。 定义ADT的语言本质上不依赖具体的程序设计语言，这里采用C+描述。 11JYP例1.1 抽象数据类

6、型“圆”的定义为：class Circle / 对象: 几何圆public: Circle(float r); / 构造函数，创建一个半径为r的对象实例 float Circumference( ); / 返回该实例的周长 float Area( ); / 返回该实例的面积; 该抽象数据类型的名称为Circle，数据对象定义为几何圆，操作包括构造函数、计算周长和面积等。注意：这些定义不依赖于数据对象的具体表示，也没有给出操作实现的过程。12JYP数据抽象和封装机制的意义：（1）简化软件开发： 假设一个问题经分析将使用A、B、C三个数据类型和协调代码求解。 （a）四位程序员，可由其中三位程序员各

7、开发一个数据类型，另一位程序员实现协调代码。 （b）一位程序员，数据抽象也可减少其在某一具体时间需要考虑的范围。 13JYP（2）易于测试和排除错误： 如下图所示，数据抽象明显提高了测试和排除错误的效率。 14JYP（3）有利于重用： 数据抽象和封装机制使开发人员可以将数据结构及其操作实现为可重用的软件组件。这些组件具有清晰的界面定义，更容易从一个软件系统中提取出来，应用于另一个软件系统。（4）便于改变数据类型的表示： 由于数据封装，外界不能直接访问数据类型的内部表示。因此，只要操作接口不变，数据类型内部表示和实现的改变不会影响使用该数据类型的其他程序。 15JYP1.3 算法定义 数据结构的

8、操作实际上是以算法的形式实现的。定义：算法是一个有限的指令集合，执行这些指令可以完成某一特定任务。一个算法还应当满足以下特性： 输入 零个或多个由外界提供的输入量。 输出 至少产生一个输出量。 确定性 每一指令都有确切的语义，无歧义。 有限性 在执行有限步骤后结束。 有效性 每一条指令都应能经过有限层的表示转化为计算平台的基本指令，即算法的指令必须是可行的。16JYP程序和算法不同，程序可以不满足有限性。例 如，一个软件的总控程序在未接受新的任务之前一直处于“等待”循环中。实现数据结构操作的程序总是可结束的，因此，后面将不再严格区分算法和程序这两个术语。必须保证指令的有效性，例如，指令“if

9、（哥德巴赫猜想是真）then x = y；”是无效的。作业：P253 17JYP1.4 递归算法 直接递归：函数在执行过程中调用本身。间接递归：函数在执行过程中调用其它函数再经过这些函数调用本身。表达力：函数定义赋值if-elsewhile 函数定义赋值if-else递归 18JYP当问题本身是递归定义的，其解法适合用递归描述。 例1.3 阶乘函数的定义是 1 当n=1n! = n(n-1)！ 当n1 用递归方法计算阶乘函数简明扼要，易于理解，如下所示：long Factorial ( long n ) if ( n = = 1 ) return 1; / 终止条件 else return n

10、*Factorial ( n-1); / 递归步骤 19JYP用参数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) = 12020JYP递归算法有四个特性：（1）必须有可最终达到的终止条件，否则程序将陷入无穷循环；（2）子问题在规模上比原问题小，或

11、更接近终止条件；（3）子问题可通过再次递归调用求解或因满足终止条件而直接求解；（4）子问题的解应能组合为整个问题的解。21JYP例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个元素的全排列。22JYP 对于只有1个元素的集合，可以直接生成其全排列。于是，全排列生成问题的递归步骤和终止条件可以确定。 求解函数p

12、erm：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;23JYP 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); / 生成

13、ak+1,an-1的全排列 temp = ak; ak = ai; ai = temp; / 再次交换 ak 和 / ai , 恢复原顺序 / else结束 / perm结束 通过调用perm(a, 0, n)，可以生成n个元素的全排列。 24JYP 用n = 3 和 a0.2 = (a, b, c)调用perm的示意如下：25JYP当算法操作的数据结构是递归定义的时候也适合使用递归。后面将有许多此类的重要例子。作业：P255，626JYP1.5 性能分析 除了正确性、可用性、可读性和容错性以外，算法的性能是评价算法优劣的重要指标。空间复杂性：算法开始运行直至结束过程中所需要的最大存储资源开销

14、的一种度量。时间复杂性：算法开始运行直至结束所需要的执行时间的一种度量。性能评价分为事前估计和事后测量。性能分析就是指对算法的空间复杂性和时间复杂性进行事前估计。27JYP1.5.1 空间复杂性 程序P的空间需求 S(P) = c + SP(实例特性) 其中，c是常数，SP(实例特性) 是实例特性的函数。分析的重点是SP(实例特性)。对于一个给定问题，首先要确定其实例特性，才可能分析求解算法的空间要求。确定实例特性与具体问题密切相关。28JYP例如:1 float rsum (float *a, const int n) 2 if (n = 0 ) return 0;/ 当n = 1时返回a0

15、3 else return rsum( a, n1) + an1;4 rsum是一个递归求和算法，其实例特性是n。每次递归调用需在栈顶保存n的值、a的值、返回值和返回地址，共需4个存储单元。 由于算法的递归深度是n+1，故所需栈空间是4(n+1)，即Srsum(n) = 4(n+1)。29JYP1.5.2 时间复杂性 算法P的运行时间 T(P) = c + TP(实例特性)时间复杂性分析的目的在于揭示算法的运行时间随着其实例特性变化的规律。将一组与实例特性无关的操作抽象为一个程序步，从而有效地简化性能分析的过程。程序步：算法中的一个在语法和语义上有意义的指令序列，而且该序列执行时间与算法的实例

16、特性无关。30JYP各类C+语句的程序步数详见教科书。可以通过列出各个语句的程序步数确定整个程序的程序步数。例1.5 程序sum： 1 float sum (float *a, const int n) 2 float s = 0; 3 for (int i = 0; i 0时Trsum(n) = 2+ Trsum(n-1)。33JYP1 float rsum (float *a, const int n) 2 if (n = 0) /从右向左扫描，遇到第一 / 个0位停止，并将所经过的全部1置0 ai = 0; i-; if ( i = 0 ) ai = 1;41JYP下面分别分析其最好、最

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

18、P 可见，如果一个算法的时间复杂性过高，当n大于一定值时，再快的计算机也无法在实际可行的时间内完成其运行。47JYP1.6 性能测量 性能测量：在一定的数据范围内准确获取程序运行所需要的空间和时间，属于事后测量。测量的结果依赖于编译器及其设置，还依赖于程序运行的计算机。下面重点研究性能（程序的计算时间）测量的方法。 假设函数time ( &hsec )将当前时间返回到变量hsec中，精度为1毫秒。下面以测量顺序查找算法seqsearch在最坏情况下的性能为例，说明性能测量的方法。48JYPint seqsearch (int *a, const int n, const int x ) int

19、 i = n; a0 = x; while (ai != x) i-; return i; 顺序查找算法的最坏时间复杂性是O(n)。为了反映被忽略的常数因子的影响，对于较小的n应选较多的值测量，对于较大的n值则可稀疏测量。 限于时钟精度，对于太短的事件必须重复m次，然后用测得的总时间除以m求出事件的时间。49JYP顺序查找算法的测量程序如下： 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

20、*j; nj+10 = 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 ); / 失败查找50JYP time (&stop); / 停止计时 long totalTime = stop - start; float runTime = (float) (totalTime) / (float)m; cout nj totalTime run

21、Timeendl; 执行TimeSearch(300000)的输出如下表所示。从该表可以看出，t基本上随n线性增长。利用n = 0和60这两点的数据，可得线性函数 t = 0.000096n + 0.0008。由此可推算，当n = 1000，t = 0.00968。这与实际测量的数据完全吻合。 51JYP52JYP规划性能测量实验时应注意以下问题： 时钟精度、期望的测量结果精度以及与此相关的重复次数。 根据是测量最坏性能还是平均性能，生成合适的实验数据。 实验目的：是为了比较还是为了预测实际运行时间？ 当实验目的是预测实际运行时间时，人们需要通过测量数据建立t与n之间的函数关系。53JYP 一

22、般需用计算机生成导致一个算法最坏性能的数据集。 但在有的情况下计算机生成也非常困难。这时可根据实例特性的值随机生成足够量的实验数据，取这些数据导致的最长运行时间作为最坏性能。 生成平均性能数据更为困难，一般也采用随机生成的方法。实验作业：P251554JYP1.7 C+中的模板 C+的模板（template）有效地提高了函数和类的可重用性。 模板（又称为参数化类型）是一种能被实例化为任何数据类型的变量，这些类型既包括C+基本类型又包括用户定义的类型。模板函数:template int seqsearch (KeyType *a, const int n, KeyType x ) int i=n

23、; a0=x; while (ai != x) i-; return i; 55JYP 通过调用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中查找浮

24、点数y。 56JYP seqsearch使用操作符“!=”比较两个KeyType对象，使用操作符“=”将一个KeyType对象赋值给另一个KeyType对象。 对于用户定义的数据类型，这些操作不可能由系统预定义。用户必须重载这些操作以实现新的语义。57JYP模板类：template class Bag public: Bag ( int MaxSize = DefaultSize ); / 假设DefaultSize已定义 int Add (const Type& x ); / 将对象x加入容器中 int Delete (const int k ); / 从容器中删除并打印k 个对象priva

25、te: int top; / 指示已用空间 Type *b; / 用数组b存放Type对象 int n; / 容量; 58JYPtemplate Bag:Bag ( int MaxSize = DefaultSize ):n(MaxSize) b = new Typen; top = -1;template int Bag:Add (const Type& x) if (top = = n-1) return 0; / 返回0表示加入失败 else b+top = x; return 1;59JYPtemplate int Bag:Delete (const int k) if (top +

26、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存放圆。60JYP1.8 效率与权衡 时间和空间的权衡；通用性和效率的权衡；开发效率与运行效率的权衡；等等。 61JYP第2章 线性表 本章学习最简单同时又最常用的数据结构线性表。62JYP2.1 线性表与数组 线性表L定义为： ( a0, a1, , an-1)，n1 L = ( )， n = 0 线性表由n个元

27、素构成。当n = 0时， ( ) 表示空线性表。当n 1时，表中第一个元素有唯一的后继，最后一个元素有唯一的前驱，其余元素有唯一的后继和前驱，因而呈现线性关系。63JYP 线性表的操作主要包括：（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个元素。64JYP 假设线性表的元素类型是浮点数，其ADT定义为：class

28、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 Delete( int i

29、 ); / 删除第i个元素并返回其值;65JYP 如何表示线性表的结构，从而高效实现这些操作？ 最通常的方法是用程序设计语言提供的数组，即用数组的第i个单元表示线性表的ai元素。 数组第i个单元与第i+1个单元在物理上是连续存放的，因此称上述方法为顺序映射（sequential mapping）。 顺序映射使随机存取表中的任何元素的时间是O(1)，但插入和删除第i个元素将导致其后续元素的迁移。 作业：P62266JYP2.2 多项式 数学上，多项式P(x)定义为：其中非零项的最大指数称为阶。多项式的ADT定义如下：class Polynomial / 对象：一个有序对的集合, 其中，ai 是系

30、数，ei 是指/ 数，且指数是0的整数。public: Polynomial ( ); / 返回多项式 p(x) = 067JYP 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 Mul

31、t (Polynomial poly); / 返回多项式 *this 与 / poly之积 float Eval ( float f); / 计算并返回x = f时*this 多项式的值; 68JYP2.2.1 多项式的表示 规定:多项式中的项按指数递减顺序排列。方法1 定义一个有MaxDegree+1个元素的数组表示系数，数组下标表示相应的指数：private: int degree;/ 当前多项式的阶 float coefMaxDegree+1; / MaxDegree是多项式的最高阶若p是类Polynomial的一个对象，则： p.degree = n p.coefi = an-i，0i

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

33、Terms; / 静态成员声明 static int free; / 静态成员声明 int Start, Finish;/ 多项式的起、始位置其中，MaxTerms是常数。由于类中的静态成员声明不构成其定义，还必须在类定义之外定义静态成员如下：term Polynomial:termArrayMaxTerms;int Polynomial:free = 0; / 指示termArray中的下一个可用单元 73JYP例如，A(x) = 2x800+3x3+1和B(x) = 7x5+x3+5x+2 一个多项式p(x)的项数为p.Finishp.Start+1。 当多项式的零项很多时，方法3明显好于

34、方法2。但当绝大多数都是非零项时，方法3所用空间大约是方法2的两倍。 74JYP2.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 & b = B.Finish )4

35、switch (compare(termArraya.exp, termArrayb.exp) 5 case =: c=termArraya.coef + termArrayb.coef;6 if (c) NewTerm(c, termArraya.exp);7 a+; b+; 8 break;75JYP 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=

36、MaxTerms) cout “空间不够！” endl; return; termArrayfree.coef = c; termArrayfree.exp = e; free+; / NewTerm结束77JYP分析： 设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 78JYP2.3 稀疏矩阵 矩阵是常用的数学对象，由m行、n列元素构成，也称为m n矩阵。当m = n时，

37、称该矩阵为方阵。例子： 79JYP表示：用二维数组，如Amn，表示矩阵十分自然。但对于大型稀疏矩阵，非零项只占所需空间的很小部分。较好的办法是只存储非零项，而将零元素作为缺省值。80JYP稀疏矩阵抽象数据类型 class SparseMatrix / 对象: 三元组的集合，行、列、值都是整型 public: SparseMatrix ( int Rows, int Cols ); SparseMatrix Transpose ( ); / 返回(*this)矩阵的转置矩阵 SparseMatrix Add ( SparseMatrix b); SparseMatrix Multiply ( S

38、parseMatrix b); ; 81JYP2.3.1 稀疏矩阵的表示 用三元组唯一表示矩阵元素 用一个由此三元组构成的数组表示整个稀疏矩阵 所有三元组按行号递增顺序排序，同一行内的三元组按列号递增顺序排序存储稀疏矩阵的行数、列数和非零项的个数 82JYPclass SparseMatrix;/ 向前声明class MatrixTerm friend SparseMatrix;private: int row, col, value;/ 行、列、值;并在SparseMatrix中定义：private: int Rows, Cols, Terms;/ 行数、列数、非零项个数 MatrixTer

39、m smArrayMaxTerms; / MaxTerms是常数83JYP前面的稀疏矩阵用三元组表示为： 84JYP2.3.2 稀疏矩阵的转置 图2.3(b)是图2.3(a)中矩阵的转置： 85JYP初始方法： 顺序扫描原矩阵数组，取元素，将其转变为存入新矩阵。 问题：转置矩阵中的三元组也必须按照行、列排序，而在处理完所有元素之前，我们并不知道应该存放在什么位置。改进方法： 按原矩阵的列构建新矩阵的行，对j = 0, , Cols-1 顺序扫描原矩阵，找到第j列元素，将其转变为新矩阵的第j行元素存入三元组数组的当前位置。86JYP 由此得算法：1 SparseMatrix SparseMatr

40、ix: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 0 )结束17 return b;18 / Transpose结束 分析：第8到15行的循环共执行Cols次，每

41、次执行导致第10行的判断执行Terms次，第10行的总时间是ColsTerms次。第11，12，13和14行执行Terms次。第27行只用常数时间。算法的总时间复杂性是O(ColsTerms)，需要O(1)辅助空间。88JYP进一步改进： 第915行的循环扫描一次仅找到少数有效三元组，导致算法Transpose的时间代价较大。如果先扫描一遍矩阵a，获得其中各列的元素个数，就可知道矩阵b各行的元素个数。由此很容易推算出b中各行的开始位置。这样，可以再次扫描a，逐项将a中元素置入b的正确位置。 RowSizei 矩阵b第i行的元素个数 RowStarti 矩阵b第i行的当前可置入位置 初始时， R

42、owStart0 = 0 RowStarti = RowStarti1+RowSizei189JYP 以后每次往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

43、行的非零项个数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;90JYP11 for ( i = 0; i Terms; i+ ) / 从 a 向b复制12 int j = RowStartsmArrayi.col;13 b.smArrayj

44、.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;2191JYP 对图2.3(a)的稀疏矩阵应用算法FastTranspose，执行完第10行后，RowSize和RowStart的值为： FastTranspose的四个循环分别迭代Cols、Terms、Cols-1和Terms次，总时间复杂性是O(Cols +

45、 Terms)。 与Transpose相比，FastTranspose 多使用了O(Cols)的辅助空间，但改进了计算时间。这体现了时间与空间的权衡。 92JYP作业：P627，993JYP2.4 字符串 字符串是由n（n0）个字符构成的线性序列，可表示为S = s0, , sn-1, 其中，si 取自字符集，n是字符串的长度。若n = 0，则S为空串。通过从字符串中删除零或多个任意位置的字符可得其一个子序列。class String / 对象: n0个字符构成的线性序列public: String (const char *init, int m);/ 初始化为长度等于m的/ 字符串init

46、 int operator = (String t ); int operator ! ( ); int Length ( ); String Concat (String t); 94JYPString 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的最长公共子序/

47、列的长度;95JYP2.4.1 字符串模式匹配的简单算法 设有字符串s和pat，其长度分别为LengthS 和LengthP。顺序考察s的第i个位置，判定其是否为一个匹配的起点，直至首次成功匹配，如下图所示： 设字符串由类型为char*的私有数据成员str表示，函数Find实现了上述策略。96JYPint String:Find ( String pat ) char *p = pat.str, *q = str; int i = 0;/ i 是起点 if ( *p & *q ) while ( i 0，设y=p0, , pj-1，x是y的两头匹配的最大真子字符串，且x=p0, , pk，则由

48、于已有匹配的结果，si-k-1, , si-1=pj-k-1, , pj-1=x，从而si-k-1, , si-1 = p0, , pk，因此 si 可与 pk+1继续比较。如下图所示： 102JYP注意： 由于x是y的的两头匹配的最大子字符串，用反证法不难证明，si 与 pk+1继续比较不会遗漏模式。 y也是其本身两头匹配的最大子字符串，但y不能作为x用，否则比较将陷入无穷循环。 将以上分析形式化，可得模式p = p0, , pn-1的失败函数f 的定义：f(j) = 最大的k 0可继续比较si与pf(j-1)+1。由此可得以下算法FastFind。104JYP1 int String:Fa

49、stFind ( String pat )2 3 int j = 0, i = 0;4 int LengthP = pat.Length( ), LengthS = Length( );5 while ( j LengthP) & ( i LengthS)6 if ( pat.strj = stri ) / 字符匹配7 j+; i+;8 9 else10 if ( j = 0) i+;11 else j = pat.f j-1 + 1; / while结束/ f是类String的数据成员12 if ( j 0，且每次j至少减少1（注意f(j1)+1 (j1)+1=j），所以此行最多执行Leng

50、thS次。因此，FastFind的总计算时间是O( LengthS)。106JYP失败函数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)） 107JYP 若a = c，则f(j) = f2(j-1)+1，否则可以继续计算下去，直至找到某个m，使第fm(j1)+1个位置的字符与a相等，或fm(j1) = 1且第0位置的字符仍不等于a。108JYP 由此，可得失败函数的另一种定义形式：f(j) =1如果j=0fm(j1)+1m是使得pfk(j-1

51、)+1=pj 的最小的k1如果上述k不存在 由此定义可直接得出计算 f 的算法 fail。 109JYP1 void String:fail ( ) / 计算模式p ( *this)的失败函数2 int LengthP= Length( ); f0= -1; 3 for (int j = 1; j =0) i=fi; /寻找m6 if ( *(str+j) = *(str+i+1) fj = i+1;7 else fj = -1;/ 找不到满足条件的m8 / for 结束9 / fail 结束对fail的分析： 由于f(i) i，while循环每迭代一次i至少减少1。 110JYPi在for循

52、环中的第4行被赋值，当j=1时i=f(0)= 1，以后最多在上次值的基础上加1（当上次执行经由第6行时）。由于第4行共执行LengthP1次，i的总增加值最多为LengthP1。如果每次至少减少1，经过LengthP1次减少，i必定小于0。while循环中的语句在整个算法中最多执行LengthP1次。 因此，fail的计算时间为O(LengthP )。 整个模式匹配问题可用O(LengthP + LengthS)的时间完成。111JYP作业：P6315，16112JYP2.5 栈 栈是一种受限的线性表，其插入和删除操作只能在表的一端进行，该端称为顶端（top）。栈S = ( a0, , an-

53、1)，a0是栈底元素，an-1是栈顶元素，ai在ai-1之上（0 i n）。由于最后插入的元素最先删除，又称栈为后进先出（LIFO）表，如下所示：113JYP抽象数据类型Stack template class Stack public: Stack ( int MaxStackSize = DefaultSize); Boolean IsFull( ); void Add(const Type& item); Boolean IsEmpty( ); Type* Delete( Type& ); ; Delete操作返回栈顶元素的指针，栈为空时返回0。为确保该指针所指的数据在Delete函数结

54、束仍然114JYP存在，采用一个引用参数，将被删除元素复制到该引用参数，并返回该参数的指针。栈的表示 最简单方法是用一维数组，如stackMaxSize ，再用变量top指示栈顶元素。top = 1表示栈空。 Stack的数据成员：private: int top; Type* stack; int MaxSize;115JYP Stack的构造函数：template Stack:Stack(int MaxStackSize):MaxSize(MaxStackSize) stack = new TypeMaxSize; top = -1; IsFull( )的实现：template inlin

55、e Boolean Stack:IsFull( ) if (top = MaxSize-1) return TRUE; else return FALSE; 116JYP IsEmpty( )的实现：template inline Boolean Stack:IsFull( ) if (top = -1) return TRUE; else return FALSE; Add的实现： template void Stack:Add(const Type& x) if (IsFull( ) StackFull( ); else stack+top = x;117JYP Delete的实现： te

56、mplate Type* Stack:Delete( Type& x) if (IsEmpty( ) StackEmpty( ); return 0; x = stacktop-; return &x; StackFull( )和StackEmpty( )的实现依赖于具体的应用。作业：P6319 118JYP2.6 队列 队列是另一种受限的线性表，其插入操作只能在表的尾端（rear）进行，删除操作只能在表的前端（front）进行。队列S = ( a0, , an-1)，a0是前端元素，an-1是尾端元素，ai在ai-1之后（0 i n）。由于最先插入的元素最先删除，又称栈为先进先出（FIFO）

57、表，如下所示：119JYP抽象数据类型Queue template class Queue public: Queue ( int MaxQueueSize = DefaultSize); Boolean IsFull( ); void Add(const Type& item); Boolean IsEmpty( ); Type* Delete( Type& ); ; 120JYP队列的表示 最简单方法是用一个一维数组和两个变量front与rear。为了便于判断队列是否为空，front指向队列第一个元素所在位置的前一个，rear指向队列最后一个元素所在位置。 Queue的数据成员：priva

58、te: int front, rear; Type* queue; int MaxSize;121JYP Queue的构造函数：template Queue:Queue(int MaxQueueSize): MaxSize(MaxQueueSize) queue = new TypeMaxSize; front = rear = -1; IsFull( )的实现：template inline Boolean Queue:IsFull( ) if (rear=MaxSize-1) return TRUE; else return FALSE;122JYP IsEmpty( )的实现：templ

59、ate inline Boolean Queue:IsEmpty( ) if (front= rear) return TRUE; else return FALSE; Add的实现： template void Queue:Add(const Type& x) if (IsFull( ) QueueFull( ); else queue+rear = x;123JYP Delete的实现： template Type* Queue:Delete( Type& x) if (IsEmpty( ) QueueEmpty( ); return 0; x = queue+front; return

60、&x; 124JYP 如下所示，IsFull( ) = TRUE并不一定表示队列中有MaxSize个元素： 125JYP 因此，将数组queueMaxSize视为环状队列，如下所示： 126JYP判断队列是否为空的条件仍然是front = rear。front = rear也可能意味着队列满，造成了二义性。队列为空时的front = rear是由于删除操作使front “追”上rear所致；而队列满的时候，front = rear是由于加入操作使rear “追”上front所致。为了消除二义性，只允许队列容纳最多MaxSize 1个元素，使得rear 永远“追”不上front。127JYP 通