数据结构05章PPT课件

1、1. ADT数组的定义： P90ADT Array D_Object: j1 = 0,1, bi1, i = 1,2,nD=aj1j2jn | aj1j2 jn ElemSet,n(0)称为数称为数组的维数，组的维数，bi是数组第是数组第i维的长度，维的长度，ji是数组元素的第是数组元素的第i维下标维下标D_Relation: R=R1, R2 , RnRi= | aj1ji jn , aj1ji+1 jn D, i = 1,2,n, 0 jk bk 1, 1 k n 且k i, 0 ji bi 2B_OP: (共4种)第1页/共75页InitArray(&A, n, bound1,

2、, boundn)/ Init_C: 维数维数n和各维长度合法；和各维长度合法；R: 构造数组构造数组A，返回，返回OKDestroyArray(&A)/ Init_C: 存在存在A；R: 销毁销毁AValue(A, &e, index1, , indexn)/ R: 若下标不超界，则将若下标不超界，则将A中指定的元素赋给中指定的元素赋给e，返回，返回OKAssign(&A, e, index1, , indexn)/ R:若下标不超界，则将若下标不超界，则将e赋给赋给A中指定的元素，返回中指定的元素，返回OK/ Init_C: n维数组维数组A, e为元素变量和为元素

3、变量和n个下标值；个下标值；/ Init_C: n维数组维数组A, e为元素变量和为元素变量和n个下标值；个下标值； ADT Array第2页/共75页ADT Array的定义说明n维数组的逻辑特性为： 在n维数组中，每个元素都受n个关系的约束。因而是非线性关系。但每个关系中，每个元素aj1j2 ji jn都有一直接后继aj1j2 ji1 jn(最后一个元素除外)，属于线性关系。 n维数组中数据元素个数为：inib1 每个元素aj1j2 jn都对应于一组下标(j1 j2 jn)，每个下标取值范围是0 ji bi1, bi称为第i维的长度(或“维界”)(i = 1,2,n)。第3页/共75页 n

4、维数组是一个同构的数据结构，即：它的每一个数据元素均属同一数据类型。2. n维数组的另一定义： 当n = 1时，n维数组退化为定长的线性表。我们用一维、二维数组来分析：D_Object: Dai| ai ElemSet, 0 i b11, b1 为数组长度R1= | ai1 , ai D, 1 i b1 1D_Relation: R= R1第4页/共75页 当n = 2时，n维数组成为二维数组。D_Object: D=aij| aij ElemSet, 0i b11, 0 j b21, b1,b2分别为数组第1维、第2维长度Row =| aij, ai, j +1 D, 0 i b11, 0

5、j b22D_Relation: R= R1, R2 = Row, ColCol = | aij, ai+1 ,j D, 0 i b12, 0 j b21第5页/共75页因而，从其逻辑结构来看，数组实际上是线性表的推广。如一个二维数组以mn矩阵形式表示，可看成如下的线性表：(其中p=m或n)mnmmnnaaaaaaaaa212222111211A = A =),.,(21p),.,(21mjjjjaaa(1 j n) 当p=n时，线性表 是把二维数组A看成是由n个元素组成的线性表，而每个元素 又是一个列向量形式的线性表：),.,(21pj第6页/共75页 在C语言中，如下定义二维数组：),.,

6、(21p),.,(21iniiiaaa(1 i m) 当p=m时，线性表 是把二维数组A看成是由m个元素组成的线性表，而每个元素 又是一个行向量形式的线性表：i 由此可见，一个二维数组可看成是一维数组作为元素而组成的线性表。 typedef ElemType Arraymn; 即：定义了包含m个一维数组元素的长度为m的数组，每个一维数组又包含n个元素。第7页/共75页 同样，一个三维数组可看成是其元素为二维数组构成的线性表。 依此类推，对于k维数组，可看成是其数据元素为k1维数组的线性表。 由此可见，n维数组是一种较复杂的数据结构，但它可以由简单的数据结构线性表辗转合成而得。第8页/共75页3

7、. 数组的运算 给定一组下标，存取相应的元素。 给定一组下标，修改相应的数据元素中的个某个数据项的值。 数组一旦被定义，其维数与维界不再改变，除了初始化及销毁运算之外，通常只有两种运算：第9页/共75页由于数组的运算一般不包括插入和删除，因此不必考虑数据元素的移动。因而，采用顺序存储方式是较为适宜的。数组作为一种多维结构，若要将其元素存于一维结构的存储器中，则必须给出一个约定，这个约定就是我们存取数组元素的规则。以二维数组为例，通常可有两种约定：1. 存储方式第10页/共75页 行主次序存储(row major order)，即：把二维数组看成行向量组成的一维结构。如：BASIC、PASCAL

8、、C等语言中的数组。 列主次序存储(column major order)，即:把二维数组看成列向量组成的一维结构。如：FORTRAN语言中的数组。行主次序列主次序a11a12a1na21a2nam1amn12ma11a21am1a12am2a1namn12n第11页/共75页 数组的顺序存储是一种随机存取的结构。只要给出数组的一组下标即可确定数据元素在存储器中的位置(地址)。2. 存储地址 以行主次序为例：设每个数据元素占L个存储单元，则相对地址为：一维数组的第i个元素存储地址用公式表示为： LOC (ai1) = LOC(a0)+(i1)*L第12页/共75页 二维数组A中任一元素ai1,

9、j1的存储位置可由下式确定：LOC(i, j) = LOC(0, 0)+(b2*i+j)*L 其中：LOC(i, j)是ai+1,j+1的存储地址；LOC(0, 0)是a11的存储地址，即：二维数组A的起始地址，又称“首地址”(或基地址)。例1：设二维数组A2010，则：LOC(i, j) = LOC(0, 0) + (10i+j)L(0 i 19, 0 j 9)第13页/共75页当i=3, j=4时：LOC(3, 4) = A00+(103+4)L即：为元素a45的存储位置。= A00+34*L 由二维数组的访问公式可推导出求n维数组中的数据元素的访问公式：LOC(j1, j2 , jn)

10、= LOC(0, 0, 0)+(b2*b3* bn*j1 +b3* bn*j2+ bn*jn1+ jn)LLjbjLOCnkniknii*)() 0 , 0 , 0(111第14页/共75页其中： cn = 1*L, ci1 = bi * ci , (1in)knikibc1可缩写成n维数组的映象函数 (下标的线性函数) ：niiinjcLOCjjjLOC121)0 , 0 , 0(),.,(即：令(1in1)亦即：ci1 = bi * bi+1 * bi+2 * bn * cn (1in1)第15页/共75页3. 存储结构 P93 /-数组的顺序存储表示数组的顺序存储表示-#include

11、/ 标准头文件，提供宏标准头文件，提供宏va_start、 / va_arg和和va_end，用于存取变长参数表，用于存取变长参数表#define MAX_ARRAY_DIM 8 / 维数最大值为维数最大值为8typedef struct ElemType *base; / 数组基址，由数组基址，由InitArray分配分配 int dim; / 数组维数数组维数 int *bounds; / 维界基址，由维界基址，由InitArray分配分配 int *constants; / 映象函数常量基址，由映象函数常量基址，由InitArray分配分配 Array;第16页/共75页注：变长参数表说

12、明在C语言的头文件stdarg.h中，有如下定义： typedef void *va_list;#define va_start(ap, parmN) (ap = )#define va_arg(ap, type) (*(type *)(ap) )#define va_end(ap)#define _va_ptr () 用于定义变长参数表。第17页/共75页4. 基本运算 P93 1) 构造数组算法：构造数组算法： P93Status InitArray(Array &A, int dim, ) / 若维数若维数dim和各维长度合法，则构造数组和各维长度合法，则构造数组A，并返回，并返

13、回OK if (dimMAX_ARRAY_DIM) return ERROR; A.dim = dim; A.bounds = (int *)malloc(dim*sizeof(int); if (! A.bounds) exit(OVERFLOW); / 各维长度合法各维长度合法,存入存入A.bounds,并求出并求出A的总元素的总元素elemtotal elemtotal = 1; va_start(ap, dim); / ap为为va_list类型类型,存放变长参数表信息存放变长参数表信息 for (i = 0; i dim; +i) A.boundsi = va_arg(ap, int

14、); if (A.boundsi = 0; i) A.constantsi = A.boundsi+1*A.constantsi+1; return OK; / InitArray第19页/共75页2) 销毁数组算法：销毁数组算法： P94Status DestroyArray(Array &A) / 销毁数组销毁数组A if (! A.base) return ERROR; free(A.base); A.base = NULL; if (! A.bounds) return ERROR; free(A.bounds); A.bounds = NULL; if (! A.consta

15、nts) return ERROR; free(A.constants); A.constants = NULL; return OK; / DestroyArray第20页/共75页3) 求地址算法：求地址算法： P94Status Locate(Array A, va_list ap, int &off) / 若若ap指示的各下标值合法指示的各下标值合法,则求该元素在则求该元素在A中相对地址中相对地址off off = 0; for (i = 0; i A.dim; +i) ind = va_arg(ap, int); if ( ind = A.boundsi) return OV

16、ERFLOW; off + = A.constantsi*ind; / for return OK; / Locate第21页/共75页4) 取元素算法：取元素算法： P94Status Value(Array A, ElemType &e, ) / n维数组维数组A, e为元素变量和为元素变量和n个下标值；个下标值； / 若各下标不超界，则将若各下标不超界，则将A中指定的元素赋给中指定的元素赋给e，返回，返回OK va_start(ap, e); if (result = Locate(A, ap, off) = 0) return result; e = *(A.base + of

17、f); return OK; / Value5) 元素赋值算法：元素赋值算法： P95 只须将上述算法中的语句只须将上述算法中的语句“e = *(A.base + off);”改为改为“*(A.base + off) = e;”即可。即可。第22页/共75页所谓压缩存储是指：为矩阵中多个值相同的元素只分配一个存储空间；对零元素不分配存储空间。1. 压缩存储所谓特殊矩阵是指：相同的元素或零元素在矩阵中分布有一定的规律的矩阵。2. 特殊矩阵1) n阶对称矩阵：阶对称矩阵：满足下述性质的n阶矩阵A：aij = aji (1 i, jn)第23页/共75页对于对称矩阵，我们为每一对对称元素仅分配一个存

18、储空间，则n2个元素可以压缩存储到包含n(n+1)/2个元素的数组空间中。不妨记为san(n+1)/2, 称为n阶对称矩阵A的压缩存储压缩存储。不失一般性，我们以行主次序存储其下三角(包括对角线)中的元素。则sak和矩阵元素aij之间存在一一对应的关系：第24页/共75页12)1(12)1(ijjjiik(i j)(i j) 对于任意给定一组下标(i, j)，总可以在sa中找 到矩阵的元素aij 。 对于任意的k(0k(n(n+1)/2) 1)，总可以 确定sak中的元素在矩阵中的位置(i, j)。即：iiikii2) 1(11 |max第25页/共75页对称矩阵的压缩存储映象：a11a12a

19、1na21a2nam1amnk = 0 1 n1 n (n(n+1)/2)12) 三角矩阵三角矩阵(与数学中略有不同与数学中略有不同)：所谓上(下)三角矩阵是指：矩阵的下(上)三角(不包括对角线)中的元素均为常数c，或者0的n阶矩阵。 三角矩阵的压缩存储除了与对称矩阵存储方式一样外，再加一个存储常数c的存储空间。 对角矩阵为三角矩阵的特例。第26页/共75页3. 稀疏矩阵 直观定义：直观定义：非零元较零元少，且分布没有一定的规律的矩阵。即：非特殊矩阵。 抽象定义：抽象定义：假设在mn矩阵中，有t个元素不为零。令 ，称 为矩阵的稀疏因子。通常认为 时称为稀疏矩阵。即：非零元个数零元个数。nmt0

20、5. 01) 定义定义:第27页/共75页2) ADT稀疏矩阵定义：稀疏矩阵定义： P96ADT SparseMatrix D_Object: D=aij |i=1,2,m; j=1,2,n;aij ElemSet, m和和n分别称为矩阵的行数和列数分别称为矩阵的行数和列数 D_Relation:R=Row, Col Row=|1im, 1jn1 Col = |1im1, 1jn B_OP: (共共8种种) CreateSMatrix(&M); / 创建创建 DestroySMatrix(&M); / 销毁销毁 PrintSMatrix(M); / 输出输出 CopySMatr

21、ix(M, &T); / 复制复制 AddSMatrix(M, N, &Q); / 加法：加法：Q=M+N SubSMatrix(M, N, &Q); / 减法：减法：Q=MN MultSMatrix(M, N, &Q);/ 乘法：乘法：Q=MN TransposeSMatrix(M, &T); / 转置转置 ADT SparseMatrix第28页/共75页 三元组顺序表三元组顺序表(又称又称“有序的双下标法有序的双下标法”)4) 稀疏矩阵的压缩存储方法：稀疏矩阵的压缩存储方法： 矩阵A中的任一非零元aij由三元组(Row, Col, Value)唯一

22、确定。即：(i, j, aij) 稀疏矩阵可由表示非零元的三元组及其行列数唯一确定，即：(i, j, aij)和(RowN, ColN)。则每一稀疏矩阵的所有非零元可表示成一三元组表。 假设以行主次序排列非零元，则三元组表唯一。三元组表的顺序存储结构如下：P98第29页/共75页 /-稀疏矩阵的三元组顺序表存储表示稀疏矩阵的三元组顺序表存储表示-#define MAXSIZE 12500 / 非零元个数的最大值为非零元个数的最大值为12500typedef struct int i, j; / 该非零元的行下标和列下标该非零元的行下标和列下标 ElemType e; Triple;typede

23、f struct Triple dataMAXSIZE+1; / 非零元三元组表非零元三元组表,data0空空 int mu, nu, tu; / 行数、列数和非零元个数行数、列数和非零元个数 TSMatrix;第30页/共75页 012 9 0 0 0 0 0 0 0 0 0 0 03 0 0 0 0 14 0 0 0 24 0 0 0 0 018 0 0 0 0 0 15 0 0 7 0 0 0M =求下列67稀疏矩阵M的转置矩阵：例：第31页/共75页 M中共有42个元素，而非零元素只有8个。则对应的三元组表和行、列值为：(1, 2, 12), (1, 3, 9), (3, 1, 3),

24、 (3, 6, 14), (4, 3, 24), (5, 2, 18), (6, 1, 15), (6, 4, 7)和(6, 7, 8)分析： 表中的最后一个元素(6, 7, 8)表示矩阵M为67阶的矩阵，且有8个非零元。 转置运算是一种最简单的矩阵运算，且转置后的矩阵仍为稀疏矩阵。即：对于mn矩阵M，其转置T为nm矩阵，且T(i, j)=M(j, i),1in, 1jm。第32页/共75页设a和b是TSMatrix型的变量，分别表示M和T。那么，如何由a.data得到b.data呢？(约定0号单元不用)方法如下：) 行列数互换：RowNColN) 三元组中的行列标互换：i j) 按行主次序重

25、排三元组之间的次序即可得b.data。 前两条容易做到，关键是如何实现第三条，即：如何使b.data中的三元组按T的行主次序排列？第33页/共75页ijValue12121393133614432452186115647ijValue13316152112251831934244676314a.datab.datai和和j互换并互换并重排重排b.data第34页/共75页两种方法：两种方法：算法思想：按照b.data中三元组的次序依次在a.data中找到相应的三元组进行转置。为了找到M的每列中的所有非零元素，必须每次对三元组表a.data全部扫描一遍。a) 经典算法：经典算法：按矩阵按矩阵M的

26、列序进行转置。的列序进行转置。第35页/共75页矩阵的转置算法： P99Status TransposeSMatrix(TSMatrix M, TSMatrix &T) / 采用采用三元组表存储表示，求稀疏矩阵三元组表存储表示，求稀疏矩阵M的转置矩阵的转置矩阵T。 T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; if (T.tu) q = 1; for (col = 1; col = M.tu; col) for (p = 1; p = M.tu; p) if (M.datap.j = = col) T.dataq.i = M.datap.j; T.dataq.j =

27、 M.datap.i; T.dataq.e = M.datap.e; q; / if / if return OK; / TransposeSMatrix第36页/共75页算法分析：算法分析：算法耗费的主要时间在二重for循环中，故其时间复杂度为：T(n)=O(M.nuM.tu)，简记为O(nutu)，即：和M的列数及非零元个数成正比。 一般的矩阵转置算法的时间复杂度为：T(n)=O(munu)。显然，当tu和munu同数量级时，上述算法的时间复杂度为：O(munu2)。因此，上述算法仅适于tu munu。即：非零元个数远远小于零元个数。第37页/共75页算法思想：按a.data中三元组的次序

28、进行转置，并将转置后的三元组直接存放到b.data中恰当的位置。那么，必须预先确定M中每一列(即T中每一行)的第一个非零元在b.data中应有的位置以及M中每一列非零元的个数。附设两个数组:numM.nu+1和cpotM.nu+1b) 快速转置：快速转置：求转置矩阵的改进算法。求转置矩阵的改进算法。(约定0号单元不用)第38页/共75页其中：numcol存放矩阵M中第col列非零元的个数。 cpotcol存放矩阵M中第col列的第一个非零元在b.data中的恰当位置。显然有：cpot11;cpotcolcpotcol1+numcol1 (2cola.nu)本例中的矩阵M的num和cpot的值如

29、下表： col1234567 numcol2221010 cpotcol1357889第39页/共75页快速转置算法： P100Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T) / 采用采用三元组表存储表示，求稀疏矩阵三元组表存储表示，求稀疏矩阵M的转置矩阵的转置矩阵T。 T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; if (T.tu) for (col = 1; col = M.nu; col) numcol=0; for (t = 1; t = M.tu; t) numM.datat.j; / 求求M中每列

30、含非零元个数中每列含非零元个数 cpot1=1; / 求第求第col列中第一个非零元在列中第一个非零元在b.data中的序号中的序号 for (col = 2; col = M.nu; col) cpotcol = cpotcol1 numcol1; for (p = 1; p = M.tu; p) col = M.datap.j; q = cpotcol; T.dataq.i = M.datap.j; 第40页/共75页 T.dataq.j = M.datap.i; T.dataq.e = M.datap.e; cpotcol; / for / if return OK; / FastTra

31、nsposeSMatrix算法分析：算法分析：算法中有四个并列的单循环，故总的时间复杂度为：T(n)=O(nutu)。当tu和munu同数量级时，其时间复杂度为：T(n)=O(munu)，和经典算法的时间复杂度相同。第41页/共75页存储量：比经典算法多两个辅助向量num、 pot；但只要将计算cpot的算法改动一下，也可以只用一个辅助向量(同学们自己完成)。三元组顺序表存储特点：非零元按行有序存储，适用于依行处理的矩阵运算；但若需按行号存取某一元素，则需从头查找。如：矩阵乘法。第42页/共75页 行逻辑链接的顺序表行逻辑链接的顺序表 为便于随机存取矩阵中任一行的非零元，则需知道每行的第一个非

32、零元在三元组表中的位置。可类似快速转置算法中创建存放每行第一个非零元的辅助数组rpos，并固定在稀疏矩阵的存储结构中。称这种“带行链接信息”的三元组表为行逻辑链接的顺序表。 其存储结构只需在三元组顺序表的存储结构中的TSMatrix结构中加上：int ropsMAXRC+1; 并将“TSMatix”类型名改为“RLSMatrix”。第43页/共75页下面讨论稀疏矩阵M和N的乘法运算：Q=MN 我们已经熟悉了矩阵相乘的经典算法。但当M和N为稀疏矩阵并用三元组作存储结构时，就不能用上述算法。算法思想： a) 为求Q，只需对于M中每个元素M.datap (p=1,2,M.tu), 找到N中所有满足条

33、件M.datap.j=N.dataq.i的元素N.dataq (q=1,2,N.tu), 求得M.datap.eN.dataq.e。第44页/共75页 b) 设一累计和数组变量ctempN.nu(初值为0), 用于累加M.datap.eN.dataq.e的值。 c) 按行处理M中的非零元，并按N.rpos提供的信息，按行寻找N中的非零元，若满足条件，则相乘并累加到ctempN.nu中，M中的该行与N中在各列处理完毕后，将ctemp中的非零元压缩存储到Q.data中，并重置ctempN.nu=0；再使M的行增1，依此类推。 d) 两个稀疏矩阵的乘积不一定是稀疏矩阵。第45页/共75页乘法算法实现

34、： P102Status MultSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix &Q) / 采用行逻辑链接采用行逻辑链接存储表示，求矩阵乘积存储表示，求矩阵乘积Q=MN。 if (M.nu!=N.mu) return ERROR; Q.mu=M.mu; Q.nu=N.nu; Q.tu=0; / Q初始化初始化 if (M.tu*N.tu != 0) / Q是非零矩阵是非零矩阵 for (arow = 1; arow = M.mu; arow) / 处理处理M的每行的每行 ctemp = 0; / 当前行各元素累加器清零当前行各元素累加器清零 Q.r

35、posarow=Q.tu+1; for (p = M.rposarow; p M.rposarow; p) / 对当前行中每一非零元找到对应元在对当前行中每一非零元找到对应元在N中的行号中的行号 brow = M.datap.j; if (brow N.nu) t = N.rposbrow+1; else t = N.tu+1;第46页/共75页 for (q=N.rposbrow; q t; q) ccol = N.dataq.j / 乘积元素在乘积元素在Q中的列号中的列号 ctempccol + = M.datap.e*N.dataq.e; / for q / 求得求得Q中第中第crow(

36、=arow)行的非零元行的非零元 for (ccol = 1; ccol MAXSIZE) return ERROR; Q.dataQ.tu = arow, ccol, ctempccol; / if / for arow / if return OK; / MultSMatrix 第47页/共75页在矩阵运算时，常常遇到：其一，非零元个数变化；其二，非零元在矩阵中的位置的变化(如作加减运算、乘法运算时)。尽管运算的结果仍是稀疏矩阵，若仍用三元组作为存储结构，不便为三元组分配空间，既使分配足够大的空间，当非零元个数变化时，还将对元素作大量的移动。 十字链表十字链表a) 定义：定义：第48页/共

37、75页因此，三元组就不适宜在进行这类运算时作为存储结构，而需要采用一种动态的链表结构。为了正确地描述非零元之间的关系，可以将矩阵中的非零元用链指针链接成一个纵横交叉的链表，即称之为十字链表十字链表。第49页/共75页 /-稀疏矩阵的十字链表存储表示稀疏矩阵的十字链表存储表示-typedef struct OLNode int i, j; / 该非零元的行下标和列下标该非零元的行下标和列下标 ElemType e; struct OLNode *right, *down; / 该非零元所在行表和列表的后继链域该非零元所在行表和列表的后继链域 OLNode, OLink;typedef struc

38、t Olink *rhead, *chead; / 行和列链表头指针数组基址，由行和列链表头指针数组基址，由CreateSMatrix分配分配 int mu, nu, tu; / 行数、列数和非零元个数行数、列数和非零元个数 CrossList;b) 存储结构：存储结构：第50页/共75页非零元结点结构：rowcolvaldownrightrow：表示非零元在矩阵中的行号col：表示非零元在矩阵中的列号val：非零元的值。 down：指向同一列中下一个非零元的指针。right：指向同一行中下一个非零元的指针。 另设两个分别存储行、列链表的头指针M.rhead和M.chead的一维数组，分别指向

39、行、列的第一个非零元结点。第51页/共75页例：设矩阵M3 0050 1 002 000则对应的十字链表为：第52页/共75页1 42 23 1 21 1 315 M.cheadM.rhead第53页/共75页c) 算法实现：算法实现：创建稀疏矩阵算法实现： P104第54页/共75页下面讨论稀疏矩阵M和N的加法运算：Q=MN算法思想： ) M和N为同型矩阵，那么，和Q的元素只可能有三种情况：aij+bij，或者aij(bij = 0 )，或者bij(aij = 0 )。因而，当N加到M上时，对M的十字链表来说，存在四种情况：a) 改变结点的val域值(aij+bij 0 )；b) val域值

40、不变(bij = 0 ); c) 插入一个新结点(aij = 0 )；d) 删除一个结点(aij+bij = 0 )。由此，只需从M和N的第一行起，逐行比较该行中的第一个非零元，分别按上述四情况处理。第55页/共75页加法算法实现： (补充) ) 设立辅助指针便于插入和删除结点。a) 在M的行链表上设pre指针，指示pa所指结点的前驱；b) 在M的每一列链表上设一个指针hlj，其初值和列链表的头指针相同，即：hlj = cheadj。Status AddSMatrix(CrossList &M, CrossList N) / 采用十字链表采用十字链表存储表示，求矩阵加法存储表示，求矩阵

41、加法M = MN。 if (M.mu!=N.mu | M.nu!=N.nu) return ERROR; for (j = 1; j = M.nu; j) hlj=M.cheadj; / hl初始化初始化 for (arow = 1; arow j pbj) 第56页/共75页 if (!(p = (OLNode *)malloc(sizeof(OLNode) exit(OVERFLOW); *p = *pb; if (pre = = NULL) M.rheadpi = p; else preright = p; pright = pa; pre = p; if (M.cheadpj = =

42、NULL) M.cheadpj = p; pdown = NULL; / if else pdown = hlpj down; hlpj down = p; hlpj = p; / if if (pa != NULL & paj j) pre = pa; pa = paright; / if if (paj = = pbj) pae + = pbe;第57页/共75页 if (!pae) if (pre = = NULL) M.rheadpai = paright; else preright = paright; p = pa; pa = paright; / if if (M.ch

43、eadpj = = p) M.cheadpj = hlpj = pdown; else hlpj down = pdown; free(p); / if pb = pbright; / while / for return OK; / AddSMatrix 注：注：T(n) = O(M.tuN.tu)第58页/共75页1、概念：广义表(或称列表)是线性表的推广。广泛地用于人工智能等领域的表处理语言LISP语言。ADT GLists D_Object: Dei| ei AtomSet OR ei GLists， 1i n, n0，AtomSet为 某个D_Object D_Relation: R

44、1=| ei-1, ei D, 2in B_OP: (共12种) ADT GLists2、ADT 广义表的定义：第59页/共75页根据定义，广义表的元素ei既可是数据元素，又可是广义表。为区别起见，我们称eiAtomSet的元素为“单元素单元素”，称eiGLists的元素为“子表子表”。并以小写字母表示单元素，以大写字母表示子表。由于广义表中的元素ei不一定属于同一数据类型，所以说广义表是一种不同构的数据结构。一般，一个广义表可记为：LS=(e1 ,e2 ,e3 , en)第60页/共75页LS为广义表的名称，n为广义表的长度。当n=0时，为空广义表；对于一个非空的广义表，e1称为LS的表头表

45、头(用函数Head(LS)表示), 除e1以外的其余元素组成的表(e2 , e3 ,en)称为LS的表尾表尾(用函数Tail(LS)表示)。广义表实例：1)2)A=( )B=( e )空的广义表；长度为0Head(A)=NULL, Tail( )=( )只有一个单元素，长度为1Head(B)=e , Tail(B)=( )第61页/共75页3)4)5)C=( a, (b, c, d ) )D=( A, B, C ) E=( a, E )由两个元素组成，分别是a和(b, c, d), 长度为2Head(c)=a, Tail(c)=(b, c, d )三个元素都是子表元素 Head(D)=A, T

46、ail(D)=(B, C)长度为2，这是一个递归的列表, 相当于(a, (a, (a, )Head(E)=a, Tail(E)=(E)第62页/共75页由上述例可得下述重要结论：a) 任何一个非空的列表，其表头可能是单元素，也可能是子表，而表尾必定为列表。b) 列表是一个多层次的结构，即列表的元素可是子表，子表的元素又可以是子表，形成一层层嵌套。如列表D的层次可由下图描述：表示子表。表示单元素。一层 二层 三层 四层DACBebadc第63页/共75页c) 列表可为其它列表所共享，如，A, B, C是D的子表，即A, B, C中的元素为D所共享。d) 列表可以是一个递归的表，即列表可以自身为其

47、元素。如列表E。第64页/共75页ii) 列表的长度和列表的深度。此外，还需注意区分如下的概念。i) 空的列表( )和由空的列表元素组成的列表 ( ( ) ) LS1=( )长度为零，Head(LS1)=NULL, Tail(LS1)=( )；LS2=( ) )长度为1, 它含有一个元素，该元素是一个空的列表，Head(LS2)=( )，Tail(LS2)=( ) 。长度：列表的元素个数；深度：列表的层次数。如列表D的长度等于3，深度等于4。第65页/共75页3、广义表的存储结构两种两种由于广义表的元素可以不同构，因此不宜用顺序存储结构，而通常采用链式存储结构，每一个元素用结点表示，由于列表的元素有两类，因此，必须设定两类结点：元素结点表示单元素表结点表示子表结点结构：任何一个非空列表可分解成表头和表尾；反之，对确定的表头和表尾可唯一确定列表。1) 头尾链表存储结构头尾链表存储结构: 第66页/共75页其中：tag ：标志域；hp：指示表头的指针；tp：指示表尾的指针。元素结点由两个域组成：tag data其中： tag：标志域；data：值域在一列表中: tag=1(表示结点是表结点)0(表示结点是元素