《数据结构第2章剖析》由会员分享，可在线阅读，更多相关《数据结构第2章剖析（128页珍藏版）》请在金锄头文库上搜索。
1、JYP,1,第2章 线性表,本章学习最简单同时又最常用的数据结构线性表。,JYP,2,2.1 线性表与数组,线性表L定义为： ( a0, a1, , an-1)，n1 L = ( )， n = 0 线性表由n个元素构成。当n = 0时， ( ) 表示空线性表。当n 1时，表中第一个元素有唯一的后继，最后一个元素有唯一的前驱，其余元素有唯一的后继和前驱，因而呈现线性关系。,JYP,3,线性表的操作主要包括： （1）计算表的长度n。 （2）从左到右（或从右到左）遍历表的元素。 （3）访问第i个元素，0i n。 （4）将新值赋予第i个元素，0i n。 （5）将新元素插入第i个位置，0i n，使原来的
2、第i，i+1，n1个元素变为第i+1，i+2，n个元素。 （6）删除第i个元素，0i n，使原来的第i+1，i+2，n1个元素变为第i，i+1，n2个元素。,JYP,4,假设线性表的元素类型是浮点数，其ADT定义为： class LinearList / 对象: L = ( a0, a1, , an-1) 或 ( ), ai浮点数, 0i n public: LinearList ( ); / 构造函数，创建一个空表 int Length( ); / 返回该实例的长度 void LeftToRight( ); / 从左到右遍历全部元素 float Retrieve( int i ); / 返回
3、第i个元素的值 void Store( int i, float v ); / 将v的值赋予第i个元素 void Insert( int i, float v ); / 将v作为第i个元素插入 float Delete( int i ); / 删除第i个元素并返回其值 ;,JYP,5,如何表示线性表的结构，从而高效实现这些操作？ 最通常的方法是用程序设计语言提供的数组，即用数组的第i个单元表示线性表的ai元素。 数组第i个单元与第i+1个单元在物理上是连续存放的，因此称上述方法为顺序映射（sequential mapping）。 顺序映射使随机存取表中的任何元素的时间是O(1)，但插入和删除第
4、i个元素将导致其后续元素的迁移。,JYP,6,2.2 多项式,数学上，多项式P(x)定义为：,其中非零项的最大指数称为阶。 多项式的ADT定义如下： class Polynomial / 对象：一个有序对的集合, 其中，ai 是系数，ei 是指 / 数，且指数是0的整数。 public: Polynomial ( ); / 返回多项式 p(x) = 0,JYP,7,int operator ! ( ); / 若 *this 是零多项式返回1，否则返回0 float Coef (int e); / 返回*this 中指数为e 的项的系数 int LeadExp ( ); / 返回*this 中最
5、大指数 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,8,2.2.1 多项式的表示,规定:多项式中的项按指数递减顺序排列。 方法1 定义一个有MaxDegree+1个元素的数组表示系数，数组下标表示相应的指数： p
6、rivate: int degree; / 当前多项式的阶 float coefMaxDegree+1; / MaxDegree是多项式的最高阶 若p是类Polynomial的一个对象，则： p.degree = n p.coefi = an-i，0in 这种表示法使多项式的许多操作实现非常简单。,JYP,9,方法2 当p.degree MaxDegree时，方法1很浪费空间，可动态定义coef数组的元素个数： private: int degree; float *coef; 构造函数为： Polynomial:Polynomial( int d) degree = d; coef = ne
7、w float degree+1; / 动态申请数组空间 ,JYP,10,方法3 对于有很多零项的稀疏多项式，方法2仍然很浪费空间。例如x800+3仅有2个非零项，其余799项都是零项。这时，只存储非零项更为有效。由此将多项式表示为另一种形式：,其中，bi0，( 0im )，em em-1 e0 0。 为此，不仅需要显式存储系数，而且需要显式存储指数。同时，为了充分利用存储资源，所有Polynomial类的多项式都用一个元素类型为term的数组termArray表示：,JYP,11,term定义如下： class Polynomial; / 向前声明 class term friend Pol
8、ynomial; private: float coef; / 系数 int exp; / 指数 ;,JYP,12,Polynomial的私有成员定义如下： private: static term termArrayMaxTerms; / 静态成员声明 static int free; / 静态成员声明 int Start, Finish; / 多项式的起、始位置 其中，MaxTerms是常数。由于类中的静态成员声明不构成其定义，还必须在类定义之外定义静态成员如下： term Polynomial:termArrayMaxTerms; int Polynomial:free = 0; / 指
9、示termArray中的下一个可用单元,JYP,13,例如，A(x) = 2x800+3x3+1和B(x) = 7x5+x3+5x+2,一个多项式p(x)的项数为p.Finishp.Start+1。 当多项式的零项很多时，方法3明显好于方法2。但当绝大多数都是非零项时，方法3所用空间大约是方法2的两倍。,JYP,14,2.2.2 多项式相加,用方法3表示多项式A和B。由于多项式的项是按指数递减顺序排列的，因而通过对A和B逐项扫描，比较指数，很容易实现 C=A+B。 用函数NewTerm将新的属于C的项存入free所指的termArray可用单元。 1 Polynomial Polynomial
10、:Add(Polynomial B) 2 Polynomial C;int a=Start;int b=B.Start;C.Start=free; float c; 3 while (a = Finish ,JYP,15,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, term
11、Arrayb.exp);/加入B(x)的剩余项 17 C.Finish=free1; 18 return C; 19,JYP,16,void Polynomial:NewTerm(float c, int e) /将新项加入C(x)中 if (free = MaxTerms) cout “空间不够！” endl; return; termArrayfree.coef = c; termArrayfree.exp = e; free+; / NewTerm结束,JYP,17,分析： 设m和n分别是A和B的非零项个数。 第2行O(1)。 第3行的循环内执行一次，a或b或a和b增加1，循环次数最多是
12、m+n1。 第15和16行的循环的总次数不超过m+n。 整个算法的时间复杂性是O(m+n)。 free超过MaxTerms时的处理很麻烦。,JYP,18,2.3 稀疏矩阵,矩阵是常用的数学对象，由m行、n列元素构成，也称为m n矩阵。当m = n时，称该矩阵为方阵。 例子：,JYP,19,表示： 用二维数组，如Amn，表示矩阵十分自然。但对于大型稀疏矩阵，非零项只占所需空间的很小部分。 较好的办法是只存储非零项，而将零元素作为缺省值。,JYP,20,稀疏矩阵抽象数据类型 class SparseMatrix / 对象: 三元组的集合，行、列、值都是整型 public: SparseMatrix
13、 ( int Rows, int Cols ); SparseMatrix Transpose ( ); / 返回(*this)矩阵的转置矩阵 SparseMatrix Add ( SparseMatrix b); SparseMatrix Multiply ( SparseMatrix b); ;,JYP,21,2.3.1 稀疏矩阵的表示,用三元组唯一表示矩阵元素 用一个由此三元组构成的数组表示整个稀疏矩阵 所有三元组按行号递增顺序排序，同一行内的三元组按列号递增顺序排序 存储稀疏矩阵的行数、列数和非零项的个数,JYP,22,class SparseMatrix; / 向前声明 class
14、MatrixTerm friend SparseMatrix; private: int row, col, value; / 行、列、值 ; 并在SparseMatrix中定义： private: int Rows, Cols, Terms; / 行数、列数、非零项个数 MatrixTerm smArrayMaxTerms; / MaxTerms是常数,JYP,23,前面的稀疏矩阵用三元组表示为：,JYP,24,2.3.2 稀疏矩阵的转置,图2.3(b)是图2.3(a)中矩阵的转置：,JYP,25,初始方法： 顺序扫描原矩阵数组，取元素，将其转变为存入新矩阵。 问题：转置矩阵中的三元组也必须
15、按照行、列排序，而在处理完所有元素之前，我们并不知道应该存放在什么位置。 改进方法： 按原矩阵的列构建新矩阵的行，对j = 0, , Cols 顺序扫描原矩阵，找到第j列元素，将其转变为新矩阵的第j行元素存入三元组数组的当前位置。,JYP,26,由此得算法： 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 = s
