《数据结构与算法第3章稀疏矩阵和广义表》由会员分享，可在线阅读，更多相关《数据结构与算法第3章稀疏矩阵和广义表（41页珍藏版）》请在金锄头文库上搜索。
1、主要内容： 稀疏矩阵 广义表 这两种数据结构是线性表的扩展：数据元素本身也是一个数据结构,第三章 稀疏矩阵和广义表,3.4 稀疏矩阵 一、 稀疏矩阵的定义： 概念：非零元素个数远远少于零元素个数的矩阵,三元组线性表： ( (1,4,22),(1,7,15),(2,2,11),(2,6,17),(3,4,-6),(4,6,39),(5,1,91),(6,3,28) ),稀疏矩阵的三元组线性表表示: 稀疏矩阵若用二维数组存储太浪费空间。 一般只考虑存储非零元素，每个非零元素可由行、列、值三元组(i, j, aij)表示，三元组按行号为主序排列，构成一个表示稀疏矩阵的三元组线性表。 三元组线性表可用
2、顺序或链接方式存储。,稀疏矩阵的抽象数据类型： ADT SpaseMatrix is Data: 用三元组线性表表示的稀疏矩阵， 用类型名SMatrix表示 Operation: void InitMatrix(SMatrix end SpaseMatrix,二、 稀疏矩阵的存储结构： 稀疏矩阵有顺序和链接两种存储结构。存储内容为三元组线性表及其行数、列数、非零元个数。 顺序存储 用顺序结构存储三元组线性表，即数组的每个元素对应一个非零元的三元组。 typedef struct int row, col; /非零元素的行号、列号 ElemType val; /元素值 Triple; typed
3、ef struct int m, n, t; /矩阵的行、列数及非零元素个数 Triple smMaxTerms+1; /三元组线性表，从sm1开始 SMatrix;,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）带行指针向量的链接存储 每一行的非零元对应一个单链表(按列号次序)，用一维数组保存所有单链表的头指
4、针。 typedef struct Node int row, col; /非零元素的行号、列号 ElemType val; /元素值 struct Node *next; TripleNode; typedef struct int m, n, t; /矩阵的行、列数及非零元素个数 TripleNode *vectorMaxRows+1; /从vector1开始保存 LMatrix;,( (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）十字链接存储 既带行指针向量，又带列指针向量，
5、每一个结点同时位于两个单链表中。 typedef struct Node int row, col; /非零元素的行号、列号 ElemType val; /元素值 struct Node *right, *down; /指向同一行,同一列的下一个结点 CrossNode; typedef struct int m, n, t; /矩阵的行、列数及非零元素个数 CrossNode *rvMaxRows+1; /行指针向量，从rv1开始 CrossNode *cvMaxColumns+1; /列指针向量，从cv1开始 CLMatrix;,7 0 0 0 15 0,0 0 0 0 0 0,-2 0
6、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) ),三、 稀疏矩阵的运算 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( SMatr
7、ix ,(2)LMatrix类型 void InputMatrix( LMatrix ,1 2 . . . MaxRows,M.vector,M.m,M.n,M.t,/插在单链表末尾 if (q=NULL) M. vectorrow = 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 M) /按三元组线性表格式输出稀疏矩阵 cout“(“; for (int i=1; iM.t; i+) c
8、out“(“M.smi.row“,”; coutM.smi.col“,”; coutM.smi.val“)“,”; if (M.t != 0) /输出最后一项 cout“(“M.smM.t.row“,”; coutM.smM.t.col“,”; coutM.smM.t.val“)“; cout“)”endl; ,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) ),(2)LMatrix类型 作业,4.转置运算 以SM
9、arix类型为例,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;
10、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.smi.col=col) S.smk.row=col; S.smk.col=M.smi.row; S.smk.val=M.smi.val; k+; return S; ,（2）快速转置法 对sm数组进行2次扫描。第一次扫描计算出原矩阵中每一列非零元的个数（用num数组存放），由此计算出每一列的第一个非零元在转置矩阵数组中的位置（用pot数组存放） ；第二次扫描则把每个三元组写到转置矩阵数组的相应位置上。 计算公式：
11、pot1=1 potcol=potcol-1 +numcol-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);
12、 S.m=M.n; S.n=M.m; S.t=M.t; if (t=0) return S; num=new intM.n+1; pot= new intM.n+1; for (col=1; col=M.n; col+) numcol=0; for (i=1; i=M.t; i+) num M.smi.col +; pot1=1; for (col=2; col=M.n; col+) potcol=potcol-1 +numcol-1;,for (i=1; i=M.t; i+) j= M.smi.col; k= potj; S.smk.row=M.smi.col; S.smk.col=M.sm
13、i.row; S.smk.val=M.smi.val; potj+; delete num; delete pot; return S; ,5.加法运算 采用LMatrix类型，计算 M=M1+M2 (M1与M2需大小相同） 算法主要思想： for 矩阵的每一行i p1与p2 分别指向 M1与M2 第i行的第一个非零元结点； while p1与p2 均未扫描完一行 if p1结点的列号 p2结点的列号 复制p2结点，插到M的p结点后， p2与p向后移； if p1结点的列号 = p2结点的列号 相加p1与p2结点的元素值 if 该值0, 则申请新结点，赋相应值后，插该结点到 M的p结点后， p
14、1与p2及p均后移； else p1与p2向后移； while p1未扫描完一行,则把剩余结点全体复制到M的p结点后 while p2未扫描完一行,则把剩余结点全体复制到M的p结点后,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.vectori=newptr; else p-next=newptr; p=newptr; k+; /while while (p1!=NULL) newptr=new TripleNode; *newptr=*p1; newptr-next=NULL; if (p=NULL ) M.vectori=newptr;
