第五章 数组和广义表--WL.ppt

第五章 数组和广义表 5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.3.1 特殊矩阵 5.3.2 稀疏矩阵 5.4 广义表的定义 5.5 广义表的存储结构 表头：若广义表LS非空，则a1是LS的表头。 表尾：其余元素组成的表（a1,a2,…,an）称为LS的表尾。 例： head(L)=a tail(L)=(b) head(B)=A tail(B)=(y) head(tail(L))=b tail(tail(L))=( ) 注: ( )和(( ))不同,前者是空表,长度为0;后者是有一个 元素的空表,长度为1 表的深度: 是指表展开后所含号的层次. 例如,表A的深度为2,表D的深度为∞. 1、广义表结点定义 （1）标志域 utype, 表明结点类型。0为表头结点，1 为整型原子结点，2为字符型原子结点，3为子表结点。 （2）值域 value。当 utype = 0 时为表引用计数，= 1时为整数值，= 2 时为字符值， = 3 时为指向子表的表头结点的指针。 （3）尾指针域 tlink。当 utype = 0 时为指向该表表头元素的指针；当 utype ? 0 时为指向同一层下一个表结点的指针。 3.广义表的数据类型 void transmatrix(TripleTable a,TripleTable b) { int p, q, col; b.m=a.n; b.n=a.m; //b的行列即是a列行 b.t=a.t; //非0元个数 if(b.t=0) printf(“A=0\n”); //显示矩阵为0矩阵 q=0; //b中的第一个非零元的下标 for(col=0;cola.n;col++) for(p=0;pa.t;p++) //在线性表中扫描 if(a.data[p].j==col){ //如果找到相应列 b.data[q].i=a.data[p].j; //得到b的一个元素 b.data[q].j=a.data[p].i; b.data[q].v=a.data[p].v; q++; //准备下一个元素 } } 分析这个算法的效率： 由于主要的工作是在p和col的两个循环中完成的，故算法的时间复杂度为O(n*t)，即矩阵的列数和非零元的个数的乘积成正比。而一般传统矩阵的转置算法为： for(col=0;coln;++col) for(row=0;rowm;++row) t[col][row]=m[row][col]; 其时间复杂度为O(n*m)。当非零元素的个数t和m*n同数量级时，算法transmatrix的时间复杂度为O(n*n2)。 注：三元组顺序表虽然节省了存储空间，但时间复杂度比一般矩阵转置的算法还要复杂，同时还有可能增加算法的难度。因此，此算法仅适用于t=m*n的情况。 改进： 快速转置的算法，其算法思想为：对A扫描一次，按A第二列提供的列号一次确定位置装入B的一个三元组。具体实施如下：一遍扫描先确定三元组的位置关系，二次扫描由位置关系装入三元组。可见，位置关系是此种算法的关键。 （1）需要先求得矩阵M中的每一列中非零元素的个数。因为：矩阵M中第i列的第一个非零元素在数组B中序号(Xi1)等于第i-1列第一个非零元素的序号(Xi-11加上该列非零元素的个数（ni-1)。即: Xi1=Xi-11+ni-1 为此，需要设置两个一维数组 num[0..n]:统计M中每列非零元素的个数，num[col]的值可以由A的第二列求得。 cpot[0..n]:由递推关系得出M中的每列第一个非零元素在B中的位置。即： cpot[col]=cpot[col-1]+num[col-1] 算法通过cpot数组建立位置对应关系： cpot[1]=1 cpot[col]=cpot[col