1、JYP,1,数据结构基础,教材：数据结构（C+描述）（金远平编著，清华大学出版社，2005）讲课教师： 金远平，软件学院 ,JYP,2,考试： 期末考试采用开卷方式，占总评成绩的70%。 平时作业和实验占总评成绩30%。 考试注重：概念、方法、技巧、思想、创新、关键步骤、程序设计风格,JYP,3,参考文献：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, 1994,JYP,4,第1章 基本概念和方法,本章论述学习和研究数据结构所必须的并且将反复出现的基本概念和方法。,JYP,5,1.1 数据结构与软件系统,设计解决实际问题的计算机软件系统，首先需要建立被处理对象的数据模型。 数据和世上万物一样，都是具有结构的。人们很自然地用数据结构表示应用领域的被处理对象。例如，树和图。 数据结构由一个数据对
3、象以及该对象中的所有数据元素之间的关系组成。数据元素本身可以是数据结构，因此，可以构造非常复杂的数据结构。,JYP,6,为了模拟实际问题的求解过程和现实对象的行为，还必须提供对数据结构的相应操作。数据结构的实现是以下一层数据结构表示上一层数据结构，直至以程序设计语言提供的基本数据类型表示的过程。 评价数据结构表示能力的标准主要是它能否方便且有效地实现需要的操作，而实现操作的算法设计及其效率高低也依赖于数据结构表示。 数据结构的定义、表示及其操作的实现相互关联，都是数据结构研究的重要内容。,JYP,7,计算机软件系统可看成是通过不同层次的数据结构及其操作实现的。例如：,JYP,8,中间层数据结构
4、起着核心作用，称之为建模层。对数据结构的研究产生了一批通用性强、具有很高实用价值的中间层数据结构，如数组、字符串、集合、线性表、栈、队列、链表、树、图、符号表等。 系统地学习进而掌握数据结构的知识和方法，对于提高设计与开发软件系统尤其是复杂软件系统的能力，无疑是十分重要的。,JYP,9,1.2 数据抽象与封装,抽象和封装的概念在日常生活中是普遍存在的，例如，人们常用的手机。通过数据封装，将一个数据对象的内部结构和实现细节对外屏蔽。通过数据抽象，将一个数据对象的规格说明与其实现分离，对外提供简洁、清晰的接口。数据结构多层表示的过程反过来也就是从基础数据结构到应用领域数据结构的不断抽象与封装的过程
5、。,JYP,10,用抽象数据类型（ADT）描述数据抽象与封装是一种自然、有效的方法。 数据类型由一个数据对象的集合和一组作用于这些数据对象的操作组成。例如，C+的基本数据类型char、int、float和double等。 抽象数据类型是一个数据类型，该数据类型的组织遵循将数据对象及对这些数据对象的操作的规格说明与这些数据对象的表示、操作的实现相分离的原则。,JYP,11,当强调一个数据对象的结构时，使用数据结构的概念。与数据结构的概念对比，抽象数据类型包含了一个数据结构的集合，还包含了对数据结构的操作。抽象数据类型成为描述数据结构及其操作的有效方式。 定义ADT的语言本质上不依赖具体的程序设计
6、语言，这里采用C+描述。,JYP,12,例1.1 抽象数据类型“圆”的定义为：class Circle / 对象: 几何圆public: Circle(float r); / 构造函数，创建一个半径为r的对象实例 float Circumference( ); / 返回该实例的周长 float Area( ); / 返回该实例的面积; 该抽象数据类型的名称为Circle，数据对象定义为几何圆，操作包括构造函数、计算周长和面积等。注意：这些定义不依赖于数据对象的具体表示，也没有给出操作实现的过程。,JYP,13,数据抽象和封装机制的意义：（1）简化软件开发： 假设一个问题经分析将使用A、B、C三
7、个数据类型和协调代码求解。 （a）四位程序员，可由其中三位程序员各开发一个数据类型，另一位程序员实现协调代码。 （b）一位程序员，数据抽象也可减少其在某一具体时间需要考虑的范围。,JYP,14,（2）易于测试和排除错误： 如下图所示，数据抽象明显提高了测试和排除错误的效率。,JYP,15,（3）有利于重用： 数据抽象和封装机制使开发人员可以将数据结构及其操作实现为可重用的软件组件。这些组件具有清晰的界面定义，更容易从一个软件系统中提取出来，应用于另一个软件系统。（4）便于改变数据类型的表示： 由于数据封装，外界不能直接访问数据类型的内部表示。因此，只要操作接口不变，数据类型内部表示和实现的改变
8、不会影响使用该数据类型的其他程序。,JYP,16,1.3 算法定义,数据结构的操作实际上是以算法的形式实现的。定义：算法是一个有限的指令集合，执行这些指令可以完成某一特定任务。一个算法还应当满足以下特性： 输入 零个或多个由外界提供的输入量。 输出 至少产生一个输出量。 确定性 每一指令都有确切的语义，无歧义。 有限性 在执行有限步骤后结束。 有效性 每一条指令都应能经过有限层的表示转化为计算平台的基本指令，即算法的指令必须是可行的。,JYP,17,程序和算法不同，程序可以不满足有限性。例 如，一个软件的总控程序在未接受新的任务之前一直处于“等待”循环中。实现数据结构操作的程序总是可结束的，因
9、此，后面将不再严格区分算法和程序这两个术语。必须保证指令的有效性，例如，指令“if （哥德巴赫猜想是真）then x = y；”是无效的。作业：P253,JYP,18,1.4 递归算法,直接递归：函数在执行过程中调用本身。间接递归：函数在执行过程中调用其它函数再经过这些函数调用本身。表达力：,函数定义赋值if-elsewhile,函数定义赋值if-else递归,JYP,19,当问题本身是递归定义的，其解法适合用递归描述。 例1.3 阶乘函数的定义是 1 当n=1n! = n(n-1)！ 当n1 用递归方法计算阶乘函数简明扼要，易于理解，如下所示：long Factorial ( long n
10、) if ( n = = 1 ) return 1; / 终止条件 else return n*Factorial ( n-1); / 递归步骤,JYP,20,用参数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,21,递归算法
11、有四个特性：（1）必须有可最终达到的终止条件，否则程序将陷入无穷循环；（2）子问题在规模上比原问题小，或更接近终止条件；（3）子问题可通过再次递归调用求解或因满足终止条件而直接求解；（4）子问题的解应能组合为整个问题的解。,JYP,22,例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,
12、23,对于只有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,24,else / ak,an-1 的排列大于1，递归生成 for ( i = k; i n; i+) char temp =
13、 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,25,用n = 3 和 a0.2 = (a, b, c)调用perm的示意如下：,JYP,26,当算法操作的数据结构是递归定义的时候也适合使用递归。后面将有许多此类的重要例子。作业：P255，6,JYP,27,1.5 性能分析,除了正
14、确性、可用性、可读性和容错性以外，算法的性能是评价算法优劣的重要指标。空间复杂性：算法开始运行直至结束过程中所需要的最大存储资源开销的一种度量。时间复杂性：算法开始运行直至结束所需要的执行时间的一种度量。性能评价分为事前估计和事后测量。性能分析就是指对算法的空间复杂性和时间复杂性进行事前估计。,JYP,28,1.5.1 空间复杂性,程序P的空间需求 S(P) = c + SP(实例特性) 其中，c是常数，SP(实例特性) 是实例特性的函数。分析的重点是SP(实例特性)。对于一个给定问题，首先要确定其实例特性，才可能分析求解算法的空间要求。确定实例特性与具体问题密切相关。,JYP,29,例如:1
15、 float rsum (float *a, const int n) 2 if (n = 0 ) return 0;/ 当n = 1时返回a03 else return rsum( a, n1) + an1;4 rsum是一个递归求和算法，其实例特性是n。每次递归调用需在栈顶保存n的值、a的值、返回值和返回地址，共需4个存储单元。 由于算法的递归深度是n+1，故所需栈空间是4(n+1)，即Srsum(n) = 4(n+1)。,JYP,30,1.5.2 时间复杂性,算法P的运行时间 T(P) = c + TP(实例特性)时间复杂性分析的目的在于揭示算法的运行时间随着其实例特性变化的规律。将一组
16、与实例特性无关的操作抽象为一个程序步，从而有效地简化性能分析的过程。程序步：算法中的一个在语法和语义上有意义的指令序列，而且该序列执行时间与算法的实例特性无关。,JYP,31,各类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)。,JYP,34,1 float rsum (float *a, const int n) 2 if (n = 0 )
17、 return 0;/ 当n = 1时返回a03 else return rsum( a, n1) + an1;4 ,JYP,35,通过反复代入可得： 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,36,许多程序的实例特性并不仅仅依赖于实例规模n，还可能与实例内容密切相关。 例如，二分查找的程序步数，不仅与元素个数n，而且与集合内容有关。 有时需要按最好、最坏
18、和平均三种情况分析算法的时间复杂性。,JYP,37,1.5.3 O表示法,程序步本身就不是一个准确的概念，而是一个抽象的概念。 再作一次抽象，从由多种因素构成的时间复杂性中抽取出其主要因素，将常数抽象为1，有利于抓住主要矛盾，简化复杂性分析。假设函数f和g是非负函数。 定义：f(n) = O(g(n) 当且仅当存在正值常数c和n0，使得对所有n n0，f(n) c*g(n)。,JYP,38,例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
19、 n) 表示对数，O(n)表示线性，O(n2)表示平方，O(n3)表示立方， O(2n)表示指数。,JYP,39,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,40,定理
20、1.1 设f(n)= amnm + am-1nm-1 + + a1n + a0，则 f(n) = O(nm)。,JYP,41,例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,42,下面分别分析其最好、最坏和平均时间复杂性：（1）最好情况：当右边第一位为0时，扫描停止，算法时间复杂性为O(1)。（2）最坏情况：当n个二进制位全为1时，需扫描n位，算法
21、时间复杂性为O(n)。,JYP,43,（3）平均情况。n位二进制数共有2n种取值。以n=3 为例，有下列取值：,JYP,44,一般，从右到左有连续m个1需m + 1次操作，这种取值共2n-(m+1)个（m 100），只有复杂性较小（如，n，nlog2n，n2，n3）的算法是实用的。即使计算机的速度再提高1000倍，表中时间也只不过缩小1000倍。在这种情况下，当n=100时，n10个程序步的运行时间是3.17年，2n个程序步的运行时间是41010年。,JYP,47,可见，如果一个算法的时间复杂性过高，当n大于一定值时，再快的计算机也无法在实际可行的时间内完成其运行。,JYP,48,1.6 性能
22、测量,性能测量：在一定的数据范围内准确获取程序运行所需要的空间和时间，属于事后测量。测量的结果依赖于编译器及其设置，还依赖于程序运行的计算机。下面重点研究性能（程序的计算时间）测量的方法。 假设函数time ( &hsec )将当前时间返回到变量hsec中，精度为1毫秒。下面以测量顺序查找算法seqsearch在最坏情况下的性能为例，说明性能测量的方法。,JYP,49,int seqsearch (int *a, const int n, const int x ) int i = n; a0 = x; while (ai != x) i-; return i; 顺序查找算法的最坏时间复杂性是
23、O(n)。为了反映被忽略的常数因子的影响，对于较小的n应选较多的值测量，对于较大的n值则可稀疏测量。 限于时钟精度，对于太短的事件必须重复m次，然后用测得的总时间除以m求出事件的时间。,JYP,50,顺序查找算法的测量程序如下： 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=
24、0; j 1时，表中第一个元素有唯一的后继，最后一个元素有唯一的前驱，其余元素有唯一的后继和前驱，因而呈现线性关系。,JYP,64,线性表的操作主要包括：（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,65,假设线性表的元素类型是浮点数，其ADT定义为：class LinearList / 对象: L
25、 = ( 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 ); / 删除第i个元素并返回其值
26、;,JYP,66,如何表示线性表的结构，从而高效实现这些操作？ 最通常的方法是用程序设计语言提供的数组，即用数组的第i个单元表示线性表的ai元素。 数组第i个单元与第i+1个单元在物理上是连续存放的，因此称上述方法为顺序映射（sequential mapping）。 顺序映射使随机存取表中的任何元素的时间是O(1)，但插入和删除第i个元素将导致其后续元素的迁移。 作业：P622,JYP,67,2.2 多项式,数学上，多项式P(x)定义为：,其中非零项的最大指数称为阶。多项式的ADT定义如下：class Polynomial / 对象：一个有序对的集合, 其中，ai 是系数，ei 是指/ 数，且
27、指数是0的整数。public: Polynomial ( ); / 返回多项式 p(x) = 0,JYP,68,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 (Polynom
28、ial poly); / 返回多项式 *this 与 / poly之积 float Eval ( float f); / 计算并返回x = f时*this 多项式的值;,JYP,69,2.2.1 多项式的表示,规定:多项式中的项按指数递减顺序排列。方法1 定义一个有MaxDegree+1个元素的数组表示系数，数组下标表示相应的指数：private: int degree;/ 当前多项式的阶 float coefMaxDegree+1; / MaxDegree是多项式的最高阶若p是类Polynomial的一个对象，则： p.degree = n p.coefi = an-i，0in这种表示法使多
29、项式的许多操作实现非常简单。,JYP,70,方法2 当p.degree em-1 e0 0。 为此，不仅需要显式存储系数，而且需要显式存储指数。同时，为了充分利用存储资源，所有Polynomial类的多项式都用一个元素类型为term的数组termArray表示：,JYP,72,term定义如下：class Polynomial;/ 向前声明class term friend Polynomial;private: float coef; / 系数 int exp;/ 指数;,JYP,73,Polynomial的私有成员定义如下：private: static term termArrayMax
30、Terms; / 静态成员声明 static int free; / 静态成员声明 int Start, Finish;/ 多项式的起、始位置其中，MaxTerms是常数。由于类中的静态成员声明不构成其定义，还必须在类定义之外定义静态成员如下：term Polynomial:termArrayMaxTerms;int Polynomial:free = 0; / 指示termArray中的下一个可用单元,JYP,74,例如，A(x) = 2x800+3x3+1和B(x) = 7x5+x3+5x+2,一个多项式p(x)的项数为p.Finishp.Start+1。 当多项式的零项很多时，方法3明显
31、好于方法2。但当绝大多数都是非零项时，方法3所用空间大约是方法2的两倍。,JYP,75,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,76,9 case
32、 : NewTerm(termArraya.coef, termArraya.exp); 13 a+;14 15 for (;a=Finish;a+) NewTerm(termArraya.coef, termArraya.exp);/加入A(x)的剩余项16 for (;b= MaxTerms) cout “空间不够！” endl; return; termArrayfree.coef = c; termArrayfree.exp = e; free+; / NewTerm结束,JYP,78,分析： 设m和n分别是A和B的非零项个数。 第2行O(1)。 第3行的循环内执行一次，a或b或a和b
33、增加1，循环次数最多是m+n1。 第15和16行的循环的总次数不超过m+n。 整个算法的时间复杂性是O(m+n)。 free超过MaxTerms时的处理很麻烦。作业：P624，5,JYP,79,2.3 稀疏矩阵,矩阵是常用的数学对象，由m行、n列元素构成，也称为m n矩阵。当m = n时，称该矩阵为方阵。例子：,JYP,80,表示：用二维数组，如Amn，表示矩阵十分自然。但对于大型稀疏矩阵，非零项只占所需空间的很小部分。较好的办法是只存储非零项，而将零元素作为缺省值。,JYP,81,稀疏矩阵抽象数据类型 class SparseMatrix / 对象: 三元组的集合，行、列、值都是整型 pub
34、lic: SparseMatrix ( int Rows, int Cols ); SparseMatrix Transpose ( ); / 返回(*this)矩阵的转置矩阵 SparseMatrix Add ( SparseMatrix b); SparseMatrix Multiply ( SparseMatrix b); ;,JYP,82,2.3.1 稀疏矩阵的表示,用三元组唯一表示矩阵元素 用一个由此三元组构成的数组表示整个稀疏矩阵 所有三元组按行号递增顺序排序，同一行内的三元组按列号递增顺序排序存储稀疏矩阵的行数、列数和非零项的个数,JYP,83,class SparseMatri
35、x;/ 向前声明class MatrixTerm friend SparseMatrix;private: int row, col, value;/ 行、列、值;并在SparseMatrix中定义：private: int Rows, Cols, Terms;/ 行数、列数、非零项个数 MatrixTerm smArrayMaxTerms; / MaxTerms是常数,JYP,84,前面的稀疏矩阵用三元组表示为：,JYP,85,2.3.2 稀疏矩阵的转置,图2.3(b)是图2.3(a)中矩阵的转置：,JYP,86,初始方法： 顺序扫描原矩阵数组，取元素，将其转变为存入新矩阵。 问题：转置矩阵中的三元组也必须按照行、列排序，而在处理完所有元素之前，我们并不知道应该存放在什么位置。改进方法： 按原矩阵的列构建新矩阵的行，对j = 0, , Cols-1 顺序扫描原矩阵，找到第j列元素，将其转变为新矩阵的第j行元素存入三元组数组的当前位置。,
