1、第五章第五章 数组和广义表数组和广义表5.1 5.1 数组的类型定义数组的类型定义5.3 5.3 稀疏矩阵的压缩存储稀疏矩阵的压缩存储 5.2 5.2 数组的顺序表示和实现数组的顺序表示和实现5.4 5.4 广义表的类型定义广义表的类型定义5.5 5.5 广义表的表示方法广义表的表示方法5.6 5.6 广义表操作的递归函数广义表操作的递归函数5.7 5.7 本章小结本章小结5.8 5.8 习习 题题第五章第五章 数组和广义表数组和广义表5.1 数组的类型定义数组的类型定义 由于数组中各元素具有统一的类型，并且数组元素由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因
2、此，数组的处的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单。多维数组是向量的推理比其它复杂的结构更为简单。多维数组是向量的推广。例如，二维数组：广。例如，二维数组：00010,110111,11,01,11,1.nnm nmmmnaaaaaaAaaa(a)a01a11am-1,1a0,n-1a1,n-1am-1,n-1a00a10am-1,0Amn=(b)Amn=（a00,a01,a0,n-1),(a10,a11,a1,n-1),(am-1,0,am-1,1,am-1,n-1)(c)第五章第五章 数组和广义表数组和广义表typedef Elemtype array2m
3、n;等价于：等价于：typedef Elemtype array1n;typedef array1 array2m;一般地：多维数组的定义如下页所示：一般地：多维数组的定义如下页所示：第五章第五章 数组和广义表数组和广义表ADT Array 数据对象：数据对象：Daj1,j2,.,ji,jn|ji=0,.,bi-1,i=1,2,.,n 数据关系：数据关系：RR1,R2,.,Rn Ri|0 jk bk-1,1 k n 且且k i,0 ji bi-2,i=2,.,n 基本操作基本操作:ADT Array 第五章第五章 数组和广义表数组和广义表InitArray(&A,n,bound1,.,boun
4、dn)操作结果：若维数操作结果：若维数 n 和各维长度合法，构造相应的和各维长度合法，构造相应的数组数组A，并返回，并返回OK。DestroyArray(&A)操作结果：销毁数组操作结果：销毁数组A A。Value(A,&e,index1,.,indexn)初始条件：初始条件：A A是是n n维数组，维数组，e e为元素变量，随后是为元素变量，随后是n n 个个下标值。下标值。操作结果：操作结果：若各下标不超界，则若各下标不超界，则e e赋值为所指定的赋值为所指定的A A 的元素值，并返回的元素值，并返回OKOK。第五章第五章 数组和广义表数组和广义表Assign(&A,e,index1,.,
5、indexn)初始条件：初始条件：A A是是n n维数组，维数组，e e为元素变量，随后是为元素变量，随后是n n 个个下标值。下标值。操作结果：操作结果：若下标不超界，则将若下标不超界，则将e e的值赋给所指定的的值赋给所指定的A A的元素，并返回的元素，并返回OKOK。数组一旦被定义，它的维数和维界就不再改变。因数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。素和修改元素值的操作。第五章第五章 数组和广义表数组和广义表二维数组的抽象定义二维数组的抽象定义:数据对象数据对象:D=ai
6、j|0ib1-1,0 jb2-1数据关系数据关系:R=ROW,COL ROW=|0ib1-2,0jb2-1 COL=|0ib1-1,0 jb2-2第五章第五章 数组和广义表数组和广义表5.2 数组的顺序表示和实现数组的顺序表示和实现类型特点类型特点:1)1)只有引用型操作，没有加工型操作只有引用型操作，没有加工型操作;2)2)数组是多维的结构，而存储空间是一个一维的结构。数组是多维的结构，而存储空间是一个一维的结构。有两种顺序映象的方式有两种顺序映象的方式:1)1)以行序为主序以行序为主序(低下标优先低下标优先););/我们所选择的我们所选择的2)2)以列序为主序以列序为主序(高下标优先高下标
7、优先););以以“行序为主序行序为主序”的存储映象的存储映象a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2L第五章第五章 数组和广义表数组和广义表 按行序为主序存放按行序为主序存放01n-1m*n-1n am-1n-1 .am-11 am-10 .a1n-1 .a11 a10 a0n-1 .a01 a00 a00 a01 .a0n-1 a10 a11 .a1n-1 am-10 am-11 am-1n-1 .Loc(i,j)=Loc(0,0)+n*i+j*L第五章第五章 数组和广义表数组和广义表二维数组二维数组A A中任一元素中任一元素a aij
8、ij 的存储位置的存储位置 LOC(i,j)=LOC(i,j)=LOC(0,0)LOC(0,0)+(b(b2 2i ij)j)L L称为基地址或基址称为基地址或基址每个元素占每个元素占L个存储单元个存储单元已经存储的元素已经存储的元素数数LOC(jLOC(j1 1,j,j2 2)=LOC(0,0)+(b)=LOC(0,0)+(b2 2j j1 1j j2 2)L LLOC(jLOC(j1 1,j,j2 2,j,j2 2)=LOC(0,0,0)+(b)=LOC(0,0,0)+(b2 2b b3 3j j1 1b b3 3j j2 2j j3 3)L LLOC(j1,j2,.,jn)=LOC(0,
9、0,.,0)+(b2 b3 bn j1+b3 b4 bn j2+bn jn-1+jn)L第五章第五章 数组和广义表数组和广义表 推广到一般情况，可得到推广到一般情况，可得到 n n 维数组数据元素存储位维数组数据元素存储位置的映象关系：置的映象关系：nn-1ikni=1k=i+1(jb+j)*L LOC(j1,j2,.,jn)=LOC(0,0,.,0)+(b2 b3 bn j1+b3 bn j2+b4 bnj3+bn-1 bn jn-2+bn jn-1+jn)L =LOC(0,0,.,0)+=LOC(0,0,.,0)+niii=1c j其中其中 c cn=L=L，c ci-1=b=bi c c
10、i,1 i 1 i n n。(c c1,c c2,c c3,.,c cn-1,c cn)称为称为 n n 维数组的映象函数维数组的映象函数(常常量量)。数组元素的存储位置是其下标的线性函数。数组元素的存储位置是其下标的线性函数第五章第五章 数组和广义表数组和广义表c cn=L L，c cn-1 =b=bnL L=b=bnc cnc cn-2 =b=bn-1b bnL L=b=bn-1c cn-1c cn-3 =b=bn-2b bn-1b bnL L=b=bn-2c cn-2 c c3 =b=b4b b5 b bnL L=b=b4c c4 c c2=b=b3b b4b b5 b bnL L=b=
11、b3c c3c c1=b=b2b b3b b4b b5 b bnL L=b=b2c c2 c ci-1=b=bi c ciLnikkibC1设设第五章第五章 数组和广义表数组和广义表 容易看出，数组元素的存储位置是其下标的线容易看出，数组元素的存储位置是其下标的线性函数，一旦确定了数组的各维的长度，性函数，一旦确定了数组的各维的长度，c ci i 就是就是常数。由于计算各个元素存储位置的时间相等，所常数。由于计算各个元素存储位置的时间相等，所以存取数组中任一元素的时间也相等。我们称具有以存取数组中任一元素的时间也相等。我们称具有这一特点的存储结构为随机存储结构。这一特点的存储结构为随机存储结构
12、。第五章第五章 数组和广义表数组和广义表下面是数组顺序存储表示和实现下面是数组顺序存储表示和实现/-数组顺序存储表示数组顺序存储表示-#includestdarg.h/标准头文件标准头文件,提供一个类型提供一个类型va_list,三个宏三个宏va_start/va_arg 和和va_end 的定义的定义#define MAX_ARRAY_DIM 8 /假设数组的最大维数假设数组的最大维数typedef structElemType *base;/存储数组元素的首地址存储数组元素的首地址(基址基址),由由InitArray分配分配int dim;/数组的维数数组的维数int*bounds;/存放
13、数组维界的基地址存放数组维界的基地址,由由InitArray分配分配int*constants;/存放映象函数常量基址存放映象函数常量基址,由由InitArray分配分配 Array;第五章第五章 数组和广义表数组和广义表Status InitArray(Array&A,int dim,)/若维数若维数 dim 和各维长度合法，构造相应的数组和各维长度合法，构造相应的数组A，并返回，并返回OKif(dim MAX_ARRAY_DIM)return ERROR;A.dim=dim;A.bounds=(int*)malloc(dim*sizeof(int);if(!A.bounds)exit(OV
14、ERFLOW);/若各维长度合法若各维长度合法,则存入则存入A.bounds,并求出元素总数并求出元素总数elemtotalelemtotal=1;va_start(ap,dim);/ap为为va_list类型类型,存放变长参数表信息的数组存放变长参数表信息的数组for(i=0;idim;i+)A.boundsi=va_arg(ap,int);/-基本操作的实现算法基本操作的实现算法-第五章第五章 数组和广义表数组和广义表if(A.boundsi=0;i-)A.constantsi=A.boundsi+1*A.constantsi+1;return OK;/InitArray第五章第五章 数组
15、和广义表数组和广义表Status DestroyArray(Array&A)/销毁数组销毁数组Aif(!A.base)return ERROR;free(A.base);A.base=NULL;if(!A.bounds)return ERROR;free(A.bounds);A.bounds=NULL;if(!A.constants)return ERROR;free(A.constants);A.constants=NULL;return OK;/DestroyArray第五章第五章 数组和广义表数组和广义表Status Locate(Array A,va_list ap,int&off)/
16、若若ap所指下标合法所指下标合法,求出该下标对应元素在数组中的相对位置求出该下标对应元素在数组中的相对位置off=0;/最终最终off带回在存储该元素时已经存储的元素个数带回在存储该元素时已经存储的元素个数For(i=0;iA.dim;i+)ind=va_arg(ap,int);if(ind=A.boundsi)return(OVERFLOW);off+=A.constantsi*ind;return OK;/Locatecjiiioffdim1第五章第五章 数组和广义表数组和广义表Status Value(Array A,ElemType&e,)/如果用如果用VC实现实现/A是一数组，是一数
17、组，e为一元素变量，随后是为一元素变量，随后是n 个下标值。个下标值。/A和和e换顺序换顺序 /若各下标不超界，则若各下标不超界，则e赋值为所指定的赋值为所指定的A 的元素值，并返回的元素值，并返回OK。va_start(ap,e);/va_start(ap,A)if(result=Locate(A,ap,off)=0)return result;e=*(A.base+off);return OK;/ValueStatus Assign(Array&A,ElemType e,)va_start(ap,e);if(result=Locate(A,ap,off)=ji=j k=j k=j*(j-1
18、)/2+i-1 (j-1)/2+i-1 当当ijij a11 a21 a22 a31 an1 annk=0 1 2 3n(n-1)212)1(nn第五章第五章 数组和广义表数组和广义表2 2、三角矩阵、三角矩阵 以主对角线划分，三角矩阵有上三角和下三角两种。以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩阵如图上三角矩阵如图a a所示，它的下三角（不包括主对角线）所示，它的下三角（不包括主对角线）中的元素均为常数。下三角矩阵正好相反，它的主对中的元素均为常数。下三角矩阵正好相反，它的主对角线上方均为常数，如图角线上方均为常数，如图b b所示。在大多数情况下，所示。在大多数情况下，三角矩阵
19、三角矩阵常数为零常数为零。a00 a01 a 0 n-1 a00 c c c a11 a 1 n-1 a10 a11 c .c c a n-1 n-1 an-1 0 an-1 1 an-1 n-1 (a)上三角矩阵 (b)下三角矩阵 第五章第五章 数组和广义表数组和广义表 三角矩阵中的重复元素三角矩阵中的重复元素c c可共享一个存储空间，可共享一个存储空间，其余的元素正好有其余的元素正好有n(n+1)/2n(n+1)/2个，因此，三角矩阵可压个，因此，三角矩阵可压缩存储到向量缩存储到向量sa0.n(n+1)/2sa0.n(n+1)/2中，其中中，其中c c存放在向量存放在向量的最后一个分量中。
20、的最后一个分量中。上三角矩阵中，主对角线之上的第上三角矩阵中，主对角线之上的第i i行行(0i n)(0i jij第五章第五章 数组和广义表数组和广义表 下三角矩阵的存储和对称矩阵类似，下三角矩阵的存储和对称矩阵类似，sak和和aij对应关系是：对应关系是：i(i+1)/2+j ij n(n+1)/2 ij 3、对角矩阵、对角矩阵 对角矩阵中，所有的非零元素集中在以主对角线为中心的带状区对角矩阵中，所有的非零元素集中在以主对角线为中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。下图给出了一个三
21、对角矩阵，元素之外，其余元素皆为零。下图给出了一个三对角矩阵，a00 a01 a10 a11 a12 a21 a22 a23 .可用以行序为主序的可用以行序为主序的 an-2 n-3 an-2 n-2 an-2 n-1 an-1 n-2 an-1 n-1 形式存储形式存储 图图5.3 对角矩阵对角矩阵k=第五章第五章 数组和广义表数组和广义表 什么是稀疏矩阵？简单说，设矩阵什么是稀疏矩阵？简单说，设矩阵A A中有中有t t个非零个非零元素，若元素，若t t远远小于矩阵元素的总数（即远远小于矩阵元素的总数（即tmtmn n），），则称则称A A为稀疏矩阵为稀疏矩阵。定义稀疏因子定义稀疏因子:通常
22、认为通常认为 0.05 0.05 的矩阵为稀疏矩阵。的矩阵为稀疏矩阵。稀疏矩阵的压缩存储稀疏矩阵的压缩存储方法方法:三元组表示法三元组表示法 /三元组为：（行，列，值）三元组为：（行，列，值）nmt5.3.2 稀疏矩阵稀疏矩阵第五章第五章 数组和广义表数组和广义表例如，下列三元组表例如，下列三元组表(1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7)(5,2,18),(6,1,15),(6,4,-7)加上行数加上行数6
23、6和列数和列数7 7便可作为下列矩阵便可作为下列矩阵M M的另一种的另一种描述。而由上述三元组表的不同表示方法可引出稀描述。而由上述三元组表的不同表示方法可引出稀疏矩阵不同的压缩存储方法。疏矩阵不同的压缩存储方法。0 12 9 0 0 0 0 0 0 3 0 0 15 0 0 0 0 0 0 0 12 0 0 0 18 0 -3 0 0 0 0 14 0 9 0 0 24 0 0 0 0 24 0 0 0 0 0 0 0 0 0 7 0 18 0 0 0 0 0 0 0 14 0 0 0 15 0 0 7 0 0 0 6 7 7 0 0 0 0 0 0图图5.4 5.4 稀疏矩阵稀疏矩阵M M
24、和和T T 0 0 0 0 0 0M=T=转置转置7 6 6第五章第五章 数组和广义表数组和广义表#define MAXSIZE 12500 /非零元素最大个数非零元素最大个数 typedef struct int i,j;/该非零元的行下标和列下标该非零元的行下标和列下标 ElemType e;/该非零元的值该非零元的值 Triple;/三元组类型三元组类型1.三元组顺序表三元组顺序表typedef struct Triple dataMAXSIZE+1;/非零元三元组表中非零元三元组表中0号单元未用号单元未用 int mu,nu,tu;/行、列及非零元个数行、列及非零元个数 TSMatri
25、x;/稀疏矩阵类型稀疏矩阵类型第五章第五章 数组和广义表数组和广义表i j e 1 2 12 1 3 9 3 1 -3 36 14 43 24 5 2 18 61 15 6 4 -7M.dataM.mu=6M.nu=7M.tu=87600070015000001800000240001400003000000000009120M第五章第五章 数组和广义表数组和广义表用常规的二维数组表示时的算法用常规的二维数组表示时的算法 其时间复杂度为其时间复杂度为:O(M.muM.M.nu)for(col=1;col=M.nu;+col)for(row=1;row=M.mu;+row)Tcolrow=Mro
26、wcol;（1）用三元组表示时用三元组表示时转置运算转置运算的实现的实现用三元组表示时如何实现？用三元组表示时如何实现？第五章第五章 数组和广义表数组和广义表方法方法1：i j e 1 2 12 1 3 9 3 1 -3 36 14 43 24 5 2 18 61 15 6 4 -7M.dataM.mu=6M.nu=7M.tu=8转置后转置后得得Ti j v 1 3 -31 6 15 2 1 12 2 5 18 3 1 9 34 24 46 -7 6 3 14T.dataT.mu=7T.nu=6T.tu=8第五章第五章 数组和广义表数组和广义表Status TransposeSMattrix(
27、TSMatrix M,TSMatrix&T)/采用三元组表存储表示，求稀疏矩阵的转置矩阵采用三元组表存储表示，求稀疏矩阵的转置矩阵TT.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu)q=1;/q表示下一次找到的非零元在表示下一次找到的非零元在T.data中的下标中的下标for(col=1;col=M.nu;col+)for(p=1;p=M.tu;p+)if(M.datap.j=col)T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.e=M.datap.e;+q;return OK;/TransposeSMattrix其时
28、间复杂度为其时间复杂度为:O(M.nuM.tu)，若若 M.tu 与与M.mu M.nu同数量级同数量级 时，时，有有O(M.tu M.nu2)第五章第五章 数组和广义表数组和广义表方法二：快速转置方法二：快速转置 其基本思想是对其基本思想是对M.dataM.data仅扫描一遍，在扫描到每一仅扫描一遍，在扫描到每一个元素时将其放个元素时将其放T.dataT.data的的合适合适的位置上。的位置上。cpot1=1;cpotcol=cpotcol-1+numcol-1;(2 col M.nu)1357889colnumcolcpotcol122232415061707600070015000001
29、800000240001400003000000000009120M第五章第五章 数组和广义表数组和广义表1）根据）根据M的的mu、nu和和tu 的值，对的值，对T的的mu、nu和和tu赋赋 相应的值；相应的值；2）初始化数组）初始化数组num;3）扫描扫描M.data，计算计算num的值；的值；4）根据）根据num的值，计算的值，计算cpot的值；的值；5）扫描）扫描M.data一遍，将非零元放在一遍，将非零元放在T.data的合适的合适 的位置上。的位置上。算法描述如下页所示：算法描述如下页所示：第五章第五章 数组和广义表数组和广义表Status FastTransposeSMatrix(
30、TSMatrix M,TSMatrix&T)/采用三元组表存储表示，求稀疏矩阵的转置矩阵采用三元组表存储表示，求稀疏矩阵的转置矩阵TT.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu)for(col=1;col=M.nu;col+)numcol=0;/0号单元不用号单元不用for(t=1;col=M.tu;t+)+numM.datat.j;cpot1=1;/求第求第col列中第一个非零元在列中第一个非零元在T.data中的序号中的序号for(col=2;col=M.nu;col+)cpotcol=coptcol-1+numcol-1;for(t=1;t=M.tu;t+)
31、col=M.datat.j;q=cpotcol;T.dataq.i=M.datat.j;T.dataq.j=M.datat.i;T.dataq.e=M.datat.e;+cpotcol;return OK;/FastTransposeSMatrix 时间复杂度为：时间复杂度为：第五章第五章 数组和广义表数组和广义表分析算法分析算法FastTransposeSMatrixFastTransposeSMatrix的时间复杂度的时间复杂度：时间复杂度为时间复杂度为:O(M.nu+M.tu)for(col=1;col=M.nu;+col)for(t=1;t=M.tu;+t)for(col=2;col=
32、M.nu;+col)for(p=1;p=M.tu;+p)第五章第五章 数组和广义表数组和广义表 三元组顺序表又称三元组顺序表又称有序的双下标法有序的双下标法，它的特点是，它的特点是，非零元在表中按行序有序存储，因此非零元在表中按行序有序存储，因此便于进行依行便于进行依行顺序处理的矩阵运算顺序处理的矩阵运算。然而，若需随机存取某一行。然而，若需随机存取某一行中的非零元，则需从头开始进行查找。中的非零元，则需从头开始进行查找。2.行逻辑链接的顺序表行逻辑链接的顺序表typedef struct Triple dataMAXSIZE+1;/非零元三元组表非零元三元组表 int rposMAXMN+1
33、;/各行第一个非零元的位置表各行第一个非零元的位置表 int mu,nu,tu;RLSMatrix;/行逻辑链接顺序表类型行逻辑链接顺序表类型在在行逻辑链接的顺序表表示稀疏矩阵时，一些操作的实现。行逻辑链接的顺序表表示稀疏矩阵时，一些操作的实现。第五章第五章 数组和广义表数组和广义表（1）取值运算，给定一组下标，求矩阵的元素值）取值运算，给定一组下标，求矩阵的元素值void value(RLSMatrix M,int r,int c,ElemType&e)p=M.rposr;/第第r行第一个非零元和位置行第一个非零元和位置while(p=M.tu&M.datap.i=r&M.datap.j c
34、)p+;if(M.datap.i=r&M.datap.j=c)e=M.datap.e;else e=0;/value第五章第五章 数组和广义表数组和广义表for(i=1;i=m1;+i)for(j=1;j=n2;+j)Qij=0;for(k=1;k=n1;+k)Qij+=Mik*Nkj;其时间复杂度为其时间复杂度为:O(m1n2n1)(2)矩阵乘法运算矩阵乘法运算:2.1 精典乘法运算算法：精典乘法运算算法：第五章第五章 数组和广义表数组和广义表M=0 21 0-2 40 03 0 0 5 0 -1 0 02 0 0 0N=3 44 2Q=M N0 6 -1 0 0 4Q=3 21 0 0 0
35、 1 0 0 01 0 0 0A=B=1 10 00 00 03 44 2C=A B1 1 1 1 1 1C=3 2第五章第五章 数组和广义表数组和广义表M、N和和Q的三元组表示分别如下：的三元组表示分别如下：i j e1 1 31 4 52 2 -13 1 2i j e1 2 22 1 13 1 -23 2 4i j e1 2 62 1 -13 2 4M.dataN.dataQ.data1nk=1M(i,k)*N(k,j)Q(i,j)=第五章第五章 数组和广义表数组和广义表 Q初始化初始化;if Q是非零矩阵是非零矩阵 /逐行求积逐行求积 for(arow=1;arow=M.mu;+arow
36、)/处理处理M的每一行的每一行 ctemp=0;/累加器清零累加器清零 计算计算Q中第中第arow行的积并存入行的积并存入ctemp 中；中；将将ctemp 中非零元压缩存储到中非零元压缩存储到Q.data；/for arow /if 基本思想：基本思想：第五章第五章 数组和广义表数组和广义表Status MultSMatrix (RLSMatrix M,RLSMatrix N,RLSMatrix&Q)/求矩阵乘积求矩阵乘积Q=M N,采用行逻辑链接存储表示采用行逻辑链接存储表示 if(M.nu!=N.mu)return ERROR;Q.mu=M.mu;Q.nu=N.nu;Q.tu=0;/初始
37、化初始化Q，Q.tu表示现已存入表示现已存入Q中的非零元个数中的非零元个数 if(M.tu*N.tu!=0)/Q是非零矩阵是非零矩阵 for(arow=1;arow=M.mu;+arow)/处理处理M的每一行的每一行 /for arow /if return OK;/MultSMatrix第五章第五章 数组和广义表数组和广义表M=0 21 0-2 40 03 0 0 5 0 -1 0 02 0 0 0N=3 44 2Q=M N0 6 -1 0 0 4Q=3 2i j e1 1 31 4 52 2 -13 1 2i j e1 2 22 1 13 1 -23 2 4i j e1 2 62 1 -1
38、3 2 4M.dataN.dataQ.data第五章第五章 数组和广义表数组和广义表 ctemp =0;/当前行各元素累加器清零当前行各元素累加器清零 Q.rposarow=Q.tu+1;/Q的第的第arow行在行在Q.data中的位置中的位置 if(arowM.mu)tp=M.rposarow+1;else tp=M.tu+1;for(p=M.rposarow;ptp;+p)/对当前行中每一个非零元对当前行中每一个非零元 brow=M.datap.j;if(brow N.nu)t=N.rposbrow+1;else t=N.tu+1 /t为本行最后一个非零元的下一位为本行最后一个非零元的下一
39、位 for(q=N.rposbrow;q t;+q)ccol=N.dataq.j;/乘积元素在乘积元素在Q中列号中列号 ctempccol+=M.datap.e*N.dataq.e;/for q /求得求得Q中第中第crow(=arow)行的非零元行的非零元处理处理 的每一行的每一行M第五章第五章 数组和广义表数组和广义表for(ccol=1;ccol MAXSIZE)return ERROR;Q.dataQ.tu=（arow,ccol,ctempccol）;/if第五章第五章 数组和广义表数组和广义表分析上述算法的时间复杂度分析上述算法的时间复杂度累加器累加器ctempctemp初始化初始化
40、的时间复杂度为的时间复杂度为(M.mu(M.mu N.nuN.nu)，求求Q Q的所有非零元的所有非零元的时间复杂度为的时间复杂度为(M.tu(M.tu N.tu/N.muN.tu/N.mu)，进行进行压缩存储压缩存储的时间复杂度为的时间复杂度为(M.mu(M.mu N.nuN.nu)，总的时间复杂度就是总的时间复杂度就是(M.mu(M.mu N.nu+M.tuN.nu+M.tu N.tu/N.muN.tu/N.mu)。若若M M是是m m行行n n列的稀疏矩阵，列的稀疏矩阵，N N是是n n行行p p列的稀疏矩阵，列的稀疏矩阵，则则M M中非零元的个数中非零元的个数 M.tuM.tu=M M
41、 m m n n，N N中非零元的个数中非零元的个数 N.tuN.tu=N N n n p p，相乘算法的时间复杂度就是相乘算法的时间复杂度就是 (m(m p p(1+n(1+n M M N N)，当当 M M0.05 0.05 和和 N N0.050.05及及 n 1000n i=i;p-j=j;p-e=e;/生成结点生成结点if(M.rheadi=NULL|M.rheadi-jj)/插在表头插在表头p-right=M.rheadi;M.rheadi=p;else /将将p插在合适的位置上插在合适的位置上for(q=M.rheadi;q-right&q-right-jright);p-rig
42、ht=q-right;q-right=p;/行插入，在行插入，在q后后if(M.cheadj=NULL|M.cheadj-ii)/插在表头插在表头 p-down=M.cheadj;M.rheadj=p;else/将将p插在合适的位置上插在合适的位置上 第五章第五章 数组和广义表数组和广义表for(q=M.cheadj;q-down&q-down-idown);p-down=q-down;q-down=p;/列插入，在列插入，在q后后return OK;/CreatMatrix_OL第五章第五章 数组和广义表数组和广义表3.2 十字链表存储时两矩阵相加运算算法十字链表存储时两矩阵相加运算算法vo
43、id addMatrix(CrossList&A,CrossList B)/A=A+Bfor(row=1;rowjpb-j:产生一个结点产生一个结点p；p所指结点所指结点 的值的值=pb所指结点的值；将所指结点的值；将p 插在插在pa的前面（的前面（pre的后面）的后面）完成行插入；将完成行插入；将p插在相应列插在相应列 的适当位置上的适当位置上,pb后移；后移；break;case pa-jj:pre=pa;pa=pa-right;break;case pa-j=pb-j:k=pa-e+pb-e;第五章第五章 数组和广义表数组和广义表 if(k)pa-e=k;pre=pa;pa=pa-rig
44、ht;pb=pb-right;else 在相应的行、列中，删除在相应的行、列中，删除pa所指结点；所指结点；pa、pb后后 移；移；break;/switch /while/for/addMatrix 第五章第五章 数组和广义表数组和广义表5.4 广义表的类型定义广义表的类型定义ADT Glist 数据对象：数据对象：Dei|i=1,2,.,n;n0;eiAtomSet 或或 eiGList,AtomSet为某个数据对象为某个数据对象 数据关系：数据关系：R1|ei-1,eiD,2in 基本操作基本操作:P107 12 种基本操作种基本操作 ADT Glist(a,(b,c),(d,(e,f)
45、,g)第五章第五章 数组和广义表数组和广义表 结构的创建和销毁结构的创建和销毁 InitGList(&L);DestroyGList(&L);CreateGList(&L,S);CopyGList(&T,L);状态函数状态函数 GListLength(L);GListDepth(L);GListEmpty(L);GetHead(L);GetTail(L);插入和删除操作插入和删除操作 InsertFirst_GL(&L,e);DeleteFirst_GL(&L,&e);遍历遍历 Traverse_GL(L,Visit();第五章第五章 数组和广义表数组和广义表广义表是递归定义的线性结构，可以形
46、式的写广义表是递归定义的线性结构，可以形式的写为：为：LS=(LS=(1 1,2 2,n n)其中：其中：i i或为原子或为广义表或为原子或为广义表例如例如:A=()B=(e)C=(a,(b,c,d)D=(A,B,C)E=(a,E)相当于一个无限的列表相当于一个无限的列表 (a,(a,(a,)基本概念：基本概念：原子、子表、表长、原子、子表、表长、空表、空表、表头表头、表尾表尾、表的深度表的深度第五章第五章 数组和广义表数组和广义表广义表是一个广义表是一个多层次多层次的的线性结构线性结构例如：例如：D=(A,B,C)=(),(e),(a,(b,c,d)ACaeBbcdD第五章第五章 数组和广义
47、表数组和广义表 任何一个非空广义表任何一个非空广义表 LS=(1,2,n)均可分解为均可分解为 表头表头 Head(LS)=1和和表尾表尾 Tail(LS)=(2,n)两部分两部分例如：例如：F=(a,b),c,(d)Head(F)=(a,b),Tail(F)=(c,(d)Head(Head(F)=a;Tail(Head(F)=(b)第五章第五章 数组和广义表数组和广义表5.5 5.5 广义表的存储结构广义表的存储结构1)1)通常采用头、尾指针的链表结构通常采用头、尾指针的链表结构表结点表结点:tag=1 hp tptag=0 atom原子结点：原子结点：第五章第五章 数组和广义表数组和广义表
48、/-广义表的头尾链表存储表示广义表的头尾链表存储表示-typedef enum ATOM,LIST ElemTag;/typedef struct GLNode ElemTag tag;/公共部分，用于区分原子结点和表结点公共部分，用于区分原子结点和表结点 union H /atom是原子结点的值域，是原子结点的值域，AtomType 由用户定义由用户定义 AtomType atom;struct struct GLNode*hp,*tp;ptr;H;/ptr是表结点的指针域，是表结点的指针域，ptr.hp和和ptr.tp分别指向表头和表尾分别指向表头和表尾GLNode,*Glist;/广义表
49、类型广义表类型第五章第五章 数组和广义表数组和广义表空表空表 LS=NULL非空表非空表 LStag=1 指向表头的指针指向表尾的指针若表头为原子，则为若表头为原子，则为tag=0 atom否则，依次类推。否则，依次类推。第五章第五章 数组和广义表数组和广义表A=()B=(e)C=(a,(b,c,d)D=(A,B,C)A=NULLB 1 0 e 1 1 1 1 10 a0 b 0 d0 cC 1 1 1 D第五章第五章 数组和广义表数组和广义表2）广义表的扩展线性链表存储结构）广义表的扩展线性链表存储结构typedef enum ATOM,LIST ElemTag;/typedef struc
50、t GLNode ElemTag tag;/公共部分，用于区分原子结点和表结点公共部分，用于区分原子结点和表结点 union H AtomType atom;/atom是原子结点的值域是原子结点的值域 struct GLNode*hp;H;/表结点的表头指针表结点的表头指针struct GLNode*tp;/相当于线性链表的相当于线性链表的next，指向下一个，指向下一个 /元素结点元素结点 GLNode,*Glist;/广义表类型广义表类型原子结点：原子结点：tag=1 hp tptag=0 atom tp表结点表结点:第五章第五章 数组和广义表数组和广义表A=()B=(e)C=(a,(b,
