第3章2稀疏矩阵和广义表剖析.ppt

3.4稀疏矩阵 3.5广义表,第3章 集合、稀疏矩阵和广义表,3.4 稀疏矩阵 3.4.1 稀疏矩阵的定义 1稀疏矩阵：非零元素个数远远少于零元素个数的矩阵,三元组线性表表示： ( (1,4,22),(1,7,15),(2,2,11),(2,6,17),(3,4,-6),(4,6,39),(5,1,91),(6,3,28) ),2稀疏矩阵的三元组线性表表示 稀疏矩阵若用二维数组存储太浪费空间 一般只考虑存储非零元素，每个非零元素可由行、列、值三元组(i, j, aij)表示，三元组按行号为主序、列号为辅序进行排列，构成一个表示稀疏矩阵的三元组线性表 三元组线性表可用顺序或链接方式存储3稀疏矩阵的抽象数据类型 ADT SparseMatrix is Data: 用三元组线性表表示的稀疏矩阵， 用类型名SMatrix表示 Operation: void InitMatrix(SMatrix end SparseMatrix,3.4.2 稀疏矩阵的存储结构： 稀疏矩阵有顺序和链接两种存储结构存储内容为三元组线性表及其行数、列数、非零元个数 顺序存储 用顺序结构存储三元组线性表，即数组的每个元素对应一个非零元的三元组。

struct Triple{ int row, col; //非零元素的行号、列号 ElemType val; //元素值 }; struct SMatrix{ int m, n, t; //矩阵的行、列数及非零元素个数 Triple sm[MaxTerms+1]; //三元组线性表，从sm[1]开始 };,,,,,,,,,1,2,3,4,5,row,col,val,1,1,7,1,5,15,3,4,-1,4,1,-2,4,6,21,,…,sm:,MaxTerms,,,,m,n,t,4,6,5,非零元以行序为主序存储,( (1,1,7), (1,5,15), (3,4,-1), (4,1,-2), (4,6,21) ),链接存储 用链接结构存储三元组线性表 （1）带行指针向量的链接存储 每一行的非零元对应一个单链表(按列号次序)，用一维数组保存所有单链表的头指针 struct TripleNode{ int row, col; //非零元素的行号、列号 ElemType val; //元素值 TripleNode *next; }; struct LMatrix { int m, n, t; //矩阵的行、列数及非零元素个数 TripleNode *vector[MaxRows+1]; //从vector[1]开始保存 };,( (1,1,7), (1,5,15), (3,4,-1), (4,1,-2), (4,6,21) ),1 2 3 4,,,,,,vector,,,,m,n,t,4,6,5,带行指针向量的链接存储结构,（2）十字链接存储 既带行指针向量，又带列指针向量，每一个结点同时位于两个单链表中。

struct CrossNode { int row, col; //非零元素的行号、列号 ElemType val; //元素值 CrossNode *right, *down; //指向同一行,同一列的下一个结点 }; struct CLMatrix{ int m, n, t; //矩阵的行、列数及非零元素个数 CrossNode *rv[MaxRows+1]; //行指针向量，从rv[1]开始 CrossNode *cv[MaxColumns+1]; //列指针向量，从cv[1]开始 };,7 0 0 0 15 0,0 0 0 0 0 0,-2 0 0 0 0 21,0 0 0 -1 0 0,,,A=,5,15,,^ ^,1,,,,,,,,,6,21,∧,∧,4,,,,,,,,,4,-1,∧,∧,3,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,cv,rv,,^ ^,^ ^,∧,∧,( (1,1,7), (1,5,15), (3,4,-1), (4,1,-2), (4,6,21) ),*3.4.3 稀疏矩阵的运算 1.初始化 SMarix类型 void InitMatrix(SMatrix },,,,M.m,M.n,M.t,0,0,0,(2)LMatrix类型 void InitMatrix(LMatrix },1 2 . . . MaxRows,M.vector,,,,M.m,M.n,M.t,0,0,0,2. 输入 SMarix类型 void InputMatrix( SMatrix },(2)LMatrix类型 void InputMatrix( LMatrix ,1 2 . . . MaxRows,M.vector,,,,M.m,M.n,M.t,,,,//插在单链表末尾 if (q==NULL) M. vector[row] = p; else { while (q-next!=NULL) q=q-next; q-next=p; } cinrowcolval; } M.m=m; M.n=n; M.t=k; },3. 输出 SMarix类型 void OutputMatrix( SMatrix },,,,,,,,,1,2,3,4,m.t,row,col,val,1,1,7,1,5,15,3,4,-1,4,1,-2,4,6,21,sm:,输出：( (1,1,7), (1,5,15), (3,4,-1), (4,1,-2), (4,6,21) ),4.转置运算 以SMarix类型为例,,,,,,,,,1,2,3,4,5,row,col,val,1,1,7,1,5,15,3,4,-1,4,1,-2,4,6,21,…,sm:,,,,,,,,,1,2,3,4,5,1,1,7,1,4,-2,4,3,-1,5,1,15,6,4,21,…,7 0 0 -2,0 0 0 0,0 0 -1 0,0 0 0 0,A’=,,15 0 0 0,0 0 0 21,4*6,6*4,（1）普通转置法 对sm数组进行n(列数)次扫描，每次转换成相应行 SMatrix Transpose( SMatrix M) O(n*t) { int k=1; SMatrix S; InitMatrix(S); S.m=M.n; S.n=M.m; S.t=M.t; if (t==0) return S; for (int col=1; col=M.n; col++) for (int i=1; i=M.t; i++) if (M.sm[i].col==col) { S.sm[k].row=col; S.sm[k].col=M.sm[i].row; S.sm[k].val=M.sm[i].val; k++; } return S; },（2）快速转置法 对sm数组进行2次扫描。

第一次扫描计算出原矩阵中每一列非零元的个数（用num数组存放），由此计算出每一列的第一个非零元在转置矩阵数组中的位置（用pot数组存放） ；第二次扫描则把每个三元组写到转置矩阵数组的相应位置上 计算公式： pot[1]=1 pot[col]=pot[col-1] +num[col-1],,,,,,,,,1,2,3,4,5,row,col,val,1,1,7,1,5,15,3,4,-1,4,1,-2,4,6,21,,,,,,,,,1,1,7,1,4,-2,4,3,-1,5,1,15,6,4,21,1,2,3,4,5,row,col,val,,i 1 2 3 4 5 6 num 2 0 0 1 1 1 pot 1 3 3 3 4 5,,SMatrix FastTranspose( SMatrix M) O(n+t) { int k, i, j, col; int *num, *pot; SMatrix S; //S存放转置矩阵 InitMatrix(S); S.m=M.n; S.n=M.m; S.t=M.t; if (t==0) return S; num=new int[M.n+1]; pot= new int[M.n+1]; for (col=1; col=M.n; col++) num[col]=0; for (i=1; i=M.t; i++) num[ M.sm[i].col ]++; pot[1]=1; for (col=2; col=M.n; col++) pot[col]=pot[col-1] +num[col-1];,for (i=1; i=M.t; i++) { j= M.sm[i].col; k= pot[j]; S.sm[k].row=M.sm[i].col; S.sm[k].col=M.sm[i].row; S.sm[k].val=M.sm[i].val; pot[j]++; } delete [ ] num; delete [ ] pot; return S; },5.加法运算 采用LMatrix类型，计算 M=M1+M2 (M1与M2需大小相同） 两矩阵相加的前提条件是：两矩阵的大小相同，即行数和列数分别相等。

LMatrix Add(LMatrix M1, LMatrix M2) { int k=0; //统计非零元个数 Triple *p1, *p2, *p, *newptr; LMatrix M; InitMatrix(M); M.m=M1.m; M.n=M1.n; if ( (M1.t==0) ,while ( (p1!=NULL) } },//以下插入newptr到第i行链尾，并后移p指针 newptr-next=NULL; if (p==NULL ) M.vector[i]=newptr; else p-next=newptr; p=newptr; k++; } //while while (p1!=NULL) { newptr=new TripleNode; *newptr=*p1; newptr-next=NULL; if (p==NULL ) M.vector[i]=newptr; else p-next=newptr; p=newptr; p1=p1-next; k++; } //while,while (p2!=NULL) { newptr=new TripleNode; *newptr=*p2; newptr-next=NULL; if (p==NULL ) M.vector[i]=newptr; else p-next=newptr; p=newptr; p2=p2-next; k++; } //while } //for M.t=k; return M; } O(M1.t+M2.t),3.5 广义表（generalized list） 3.5.1广义表的定义 广义表是线性表的推广。

广义表是 n(n=0) 个数据元素a1, a2, …， an 构成的有限序列，数据元素可以是单个元素（称为单元素），也可以是广义表（称为子表或表元素）广义表是一种递归的数据结构 广义表一般表示为: LS = ( a1, a2, …， an ) n 称为广义表的长度，n=0 时称为空表,表示法： 小写字母表示单元素，大写字母表示表元素 ① A=( ) B=(d) C=(a, (b,c)) D=(A,B,C)=( (), (d), (a,(b。