数据结构与算法设计PPT (15).pdf

《数据结构与算法设计PPT (15).pdf》由会员分享，可在线阅读，更多相关《数据结构与算法设计PPT (15).pdf（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第3章 字符串与数组3.5 稀疏矩阵的存储压缩 0000280000000091039000000006000017000110150022000A76-=稀疏矩阵(Sparse Matrix)行数m=6,列数n=7,非零元素个数t=6非零元素个数较少，分布没有规律template class SparseMatrixint Rows,Cols,Terms;/行/列/非零元素数TrituplesmArrayMaxTerms;public:/三元组表SparseMatrix(int MaxRow,int Maxcol);SparseMatrixTranspose();/转置SparseMatri

2、x /相加Add(SparseMatrixb);SparseMatrix /相乘Multiply(SparseMatrixb);稀疏矩阵(SparseMatrix)的抽象数据类型A的三元组顺序表图示A=row col val0 01 12 23 34 45 56 67 78 82 0 -35 0 150 1 124 1 180 2 93 2 245 3 -72 5 14012900000000000-3000014000240000018000001500-7000三元组(Trituple)类的定义template class SparseMatrix;template classTritup

3、lefriend class SparseMatrixprivate:int row,col;/非零元素所在行号/列号Type value;/非零元素的值 r ro ow w c co ol l v va al lu ue e-=-=0000015003901700000000006022280000000001100910000B 0000280000000091039000000006000017000110150022000A6776稀疏矩阵稀疏矩阵转置矩阵转置矩阵用三元组表表示的稀疏矩阵及其转置 行行行行(r ro ow w)列列列列(c co ol l)值值值值(v va al lu

4、 ue e)行行行行(r ro ow w)列列列列(c co ol l)值值值值(v va al lu ue e)0 0 0 3 3 2 22 2 0 0 0 4 4 9 91 1 1 0 0 6 6 1 15 5 1 1 1 1 1 1 11 1 2 1 1 1 1 1 11 1 2 2 2 5 5 2 28 8 3 1 1 5 5 1 17 7 3 3 3 0 0 2 22 2 4 2 2 3 3 (6 6 4 3 3 2 2 (6 6 5 3 3 5 5 3 39 9 5 5 5 1 1 1 17 7 6 4 4 0 0 9 91 1 6 5 5 3 3 3 39 9 7 5 5 2 2

5、 2 28 8 7 6 6 0 0 1 16 6稀疏矩阵转置算法思想 设矩阵列数为Cols，对矩阵三元组表扫描Cols 次。第k 次检测列号为k 的项。第k 次扫描找寻所有列号为k 的项，将其行号变列号、列号变行号，顺次存于转置矩阵三元组表。设矩阵三元组表总共有Terms 项，其时间代价为O(Cols*Terms)。若矩阵有 200 行，200 列，10,000 个非零元素，总共有 2,000,000 次处理。template SparseMatrixSparseMatrix:Transpose()SparseMatrixb(Cols,Rows);b.Rows=Cols;b.Cols=Rows

6、;b.Terms=Terms;/转置矩阵的列数,行数和非零元素个数if(Terms 0)int CurrentB=0;/转置三元组表存放指针用三元组表表示的稀疏矩阵转置过程for(intk=0;k Cols;k+)for(inti=0;i Terms;i+)if(smArrayi.col=k)b.smArrayCurrentB.row=k;b.smArrayCurrentB.col=smArrayi.row;b.smArrayCurrentB.value=smArrayi.value;CurrentB+;return b;用三元组表表示的稀疏矩阵及其转置 行行行行 (r ro ow w)列列列

7、列(c co ol l)值值值值(v va al lu ue e)行行行行(r ro ow w)列列列列(c co ol l)值值值值(v va al lu ue e)0 0 0 3 3 2 22 2 0 1 0 0 6 6 1 15 5 1 2 1 1 1 1 1 11 1 2 3 1 1 5 5 1 17 7 3 4 2 2 3 3 -6 6 4 5 3 3 5 5 3 39 9 5 6 4 4 0 0 9 91 1 6 7 5 5 2 2 2 28 8 7 CurrentB按照行主序存储用三元组表表示的稀疏矩阵及其转置 行行行行(r ro ow w)列列列列(c co ol l)值值值值

8、(v va al lu ue e)行行行行(r ro ow w)列列列列(c co ol l)值值值值(v va al lu ue e)0 0 0 3 3 2 22 2 0 0 0 4 4 9 91 1 1 0 0 6 6 1 15 5 1 1 1 1 1 1 11 1 2 1 1 1 1 1 11 1 2 2 2 5 5 2 28 8 3 1 1 5 5 1 17 7 3 3 3 0 0 2 22 2 4 2 2 3 3 (6 6 4 3 3 2 2 (6 6 5 3 3 5 5 3 39 9 5 5 5 1 1 1 17 7 6 4 4 0 0 9 91 1 6 5 5 3 3 3 39

9、9 7 5 5 2 2 2 28 8 7 6 6 0 0 1 16 6每行存储开始的位置快速转置算法 建立辅助数组rowSize和rowStart，记录矩阵转置后各行非零元素个数和各行元素在转置三元组表中开始存放位置。扫描矩阵三元组表，根据某项的列号，确定它转置后的行号，查rowStart表，按查到的位置直接将该项存入转置三元组表中。转置时间代价为 O(max(Terms,Cols)。若矩阵有 200 列，10000 个非零元素，总共需要10000 次处理。0123456 语 义rowSize 1 1 1 2 0 2 1 矩阵 A 各列非 零元素个数rowStart 0 1 2 3 5 5 7

10、 矩阵 B 各行开 始存放位置for(inti=0;i Cols;i+)rowSizei=0;for(i=0;i Terms;i+)rowSizesmArrayi.col+;rowStart0=0;for(i=1;i Cols;i+)rowStarti=rowStarti-1+rowSizei-1;每行开始存储位置计算template SparseMatrixSparseMatrix:FastTranspos()int*rowSize=new intCols;int*rowStart=new intCols;SparseMatrixb(Cols,Rows);b.Rows=Cols;b.Cols

11、=Rows;b.Terms=Terms;if(Terms 0)for(inti=0;i Cols;i+)rowSizei=0;for(i=0;i Terms;i+)rowSizesmArrayi.col+;稀疏矩阵的快速转置算法rowStart0=0;for(i=1;i Cols;i+)rowStarti=rowStarti-1+rowSizei-1;for(i=0;i (istream&,Matrix&);/矩阵输入重载函数private:MatrixNode*down,*right;/列/行链指针Boolean head;/结点类型稀疏矩阵的链表表示的类定义Union Triple tri

12、ple;MatrixNode*next;/矩阵元素结点(False)或链头结点(True)MatrixNode(Boolean,Triple*);/结点构造函数MatrixNode:MatrixNode(Boolean b,Triple*t)/矩阵结点构造函数head=b;/结点类型if(b)right=next=this;elsetriple=*t;稀疏矩阵的链表表示的类定义typedefMatrixNode*MatrixNodePtr;/一个指针数组,用于建立稀疏矩阵classMatrix friend istream&operator (istream&,Matrix&);/矩阵输入pu

13、blic:Matrix();/析构函数private:MatrixNode*headnode;/稀疏矩阵的表头;用正交链表表示的稀疏矩阵的建立istream&operator(istream&is,Matrix&matrix)Triple s;int p;is s.row s.col s.value;/输入矩阵的行数,列数和非零元素个数if(s.row s.col)p=s.row;elsep=s.col;/取行、列数大者matrix.headnode=/整个矩阵表头结点newMatrixNode(False,&s);if(!p)/零矩阵时matrix.headnoderight=matrix.

14、headnode;returnis;MatrixNodePtr*H=newMatrixNodePtr(p);/建立表头指针数组,指向各链表的表头for(int i=0;i p;i+)Hi=newMatrixNode(True,0);int CurrentRow=0;MatrixNode*last=H0;/当前行最后结点for(i=0;i t.row t.col t.value;/输入非零元素的三元组if(t.row CurrentRow)/如果行号大于当前行,闭合当前行lastright=HCurrentRow;CurrentRow=t.row;last=HCurrentRow;last=la

15、stright=/链入当前行newMatrixNode(False,&t);Ht.colnext=Ht.colnextdown=last;/链入列链表lastright=HCurrentRow;/闭合最后一行/闭合各列链表for(i=0;i s.col;i+)Hinextdown=Hi;/链接所有表头结点for(i=0;i p-1;i+)Hinext=Hi+1;Hp-1next=matrix.headnode;matrix.headnoderight=H0;delete H;return is;稀疏矩阵的删除 为执行稀疏矩阵的删除，需要使用可利用空间表来管理回收的空间。可利用空间表是单链表结构

16、，只允许在表头插入或删除，其表头指针为av。使用可利用空间表，可以高效地回收循环链表。如果需要建立新的稀疏矩阵，还可以从可利用空间表中分配结点。if(first!=NULL)CircListNode*second=firstlink;firstlink=av;av=second;first=NULL;利用可利用空间表回收循环链表if(av=NULL)newnode=newCircListNode;else newnode=av;av=avlink;从可利用空间表分配结点avnewnodeav分配前的可利用空间表分配后的可利用空间表和新结点用正交链表表示的稀疏矩阵的删除Matrix:Matrix()if(headnode=NULL)return;MatrixNode*x=headnoderight,*y;headnoderight=av;av=headnode;while(x!=headnode)y=xright;xright=av;av=y;x=xnext;headnode=NULL;