《数据结构课件5范文》由会员分享，可在线阅读，更多相关《数据结构课件5范文（6页珍藏版）》请在金锄头文库上搜索。
1、数据结构课件5范文 1第五章数组与广义表2主要内容?5.1数组的定义和操作?5.2数组的顺序表示和实现?数组的应用例子?5.3矩阵的压缩存储?5.4广义表的定义?5.5广义表的存储结构数组和广义表可以看成是一种特殊的线性表，即线性表中的数据元素本身也是一个线性表。 广义表的存储结构数组和广义表可以看成是一种特殊的线性表，即线性表中的数据元素本身也是一个线性表。 1、S2和S3三个串的最长公共子串？125.3矩阵的压缩存储5.3.1特殊矩阵的存储表示5.3.2稀疏矩阵的三元组表示法5.3.3稀疏矩阵的十字链表表示法135.3.1特殊矩阵的存储表示?对称矩阵a11a12.a1na21a22.a2n
2、a n1a n2.a nn.a11a21a22a31a32a n1a nn.k=01234n(n-1)/2n(n+1)/2-1按行序为主序? i je1234567831-3611512125218139432464-73614M.data678M.muM.nuM.tu19M=012900000000000-3000014000240000018000001500-7000T=00-3001512000180900240000000-70000000014000000000稀疏矩阵转置运算?稀疏矩阵转置运算?问题描述已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表问题描述已知一个稀疏矩阵
3、的三元组表，求该矩阵转置矩阵的三元组表20稀疏矩阵转置运算?问题分析一般矩阵转置算法void transpose(int M,int T)/普通矩阵转置for(col=1;col=n;col+)for(row=1;row=m;row+)/0行行0列不用列不用Tcolrow=Mrowcol;特点行、列下标交换T（n）=O(m*n)21i je1234567831-3611512125218139432464-73614M.data678M.muM.nuM.tui je12345678211246-713-33424161531963142518T.data768T.muT.nuT.tu矩阵M的三
4、元组顺序表矩阵M的三元组顺序表T的转置矩阵T的三元组顺序表T的转置矩阵T的三元组顺序表规律?稀疏矩阵转置运算22稀疏矩阵转置运算?解决思路只要做到?将矩阵行、列维数互换?将每个三元组中的i和j相互调换?重排三元组次序，使M中元素以T的行(M的列)为主序方法一以T为基准，“按需点菜”方法二以为基准，“按需点菜”方法二以M为基准，“按位就坐”？23方法一以T为基准，“按需点菜”?算法对M.data从头至尾扫描?第一次扫描时，将M.data中列号为1的三元组赋值到的三元组赋值到T.data中?第二次扫描时，将M.data中列号为2的三元组赋值到的三元组赋值到T.data中?依此类推，直至将M.dat
5、a所有三元组赋值到T.data中24i jv121213931-3361443245218611564-7i jv31-3251813-3611516151212211252181393194324342464-746-736146314M.data T.data对M六次扫描完成转置运算第一次扫描查找第1列元素第一次扫描查找第1列元素第一次扫描结束第一次扫描结束第二次扫描结束第二次扫描结束第二次扫描查找第2列元素第二次扫描查找第2列元素第三次扫描查找第3列元素第三次扫描查找第3列元素第四次扫描查找第4列元素第四次扫描查找第4列元素第五次扫描查找第5列元素第五次扫描查找第5列元素第六次扫描查找第
6、6列元素第六次扫描查找第6列元素方法一以T为基准，“按需点菜”25/转置运算算法void TransposeSMatrix(TSMatrix M,TSMatrix&T)/采用三元组表存储表示，求稀疏矩阵M的转置矩阵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)/p为扫描M.data的“指示器”/p“指向”三元组称为当前三元组if(M.datap.j=col)T.dataq.i=M.datap.j;T.dataq.j=M.dat
7、ap.i;T.dataq.e=M.datap.e;+q;26方法一以T为基准，“按需点菜”?时间复杂度分析?算法的基本操作为将M.data中的三元组赋值到T.data，是在两个循环中完成的，故算法的时间复杂度为，是在两个循环中完成的，故算法的时间复杂度为O(nutu)?我们知道，若用二维数组存储矩阵，转置算法的时间复杂度为我们知道，若用二维数组存储矩阵，转置算法的时间复杂度为O(munu)。 当非零元的个数tu和矩阵元素个数和矩阵元素个数munu同数量级时，转置运算算法1的时间复杂度为的时间复杂度为O(mununu)。 由此可见在这种情况下，用三元组顺序表存储矩阵，虽然可能节省了存储空间，但时
8、间复杂度提高了，因此算法仅适于。 由此可见在这种情况下，用三元组顺序表存储矩阵，虽然可能节省了存储空间，但时间复杂度提高了，因此算法仅适于tu ?该算法效率不高的原因是对为实现M到T的转置，该算法对的转置，该算法对M.data进行了多次扫描。 能否在对M.data一次扫描的过程中，完成一次扫描的过程中，完成M到T的转置？27方法二以M为基准，“按位就坐”?以M为基准，“按位就坐”?快速转置算法?即按M中三元组次序转置，转置结果放入T中恰当位置。 中恰当位置。 ?关键?预先确定M中每一列第一个非零元在T中位置？?为确定这些位置，转置前应先求得M的每一列中非零元个数的每一列中非零元个数28i jv
9、1234567831-3611512125218139432464-73614M.data678M.muM.nuM.tui jv12345678211246-713-33424161531963142518T.data768T.muT.nuT.tuM.data的三元组中每条纪录在的三元组中每条纪录在T.data三元组中的位置？三元组中的位置？各列第一个非零元三元组在各列第一个非零元三元组在T.data中的位置？方法二以M为基准，“按位就坐”29方法二以M为基准，“按位就坐”?实现设两个数组num、cpos?numcol存储M中第col列非零元个数?cposcol存储M中第col列第一个非零元三
10、元组在T.data中的位置?cposcol的计算方法?cpos1=1?cposcol=cposcol-1+numcol-1(2colM.nu)colnumcolcposcol122232415061707600070015000001800000240001400003000000000009120?=M30方法二以M为基准，“按位就坐”?快速转置算法主要步骤?求M中各列非零元个数num;?求M中各列第一个非零元在T.data中的下标cpos;?对M.data进行一次扫描，遇到col列的第一个非零元三元组时，按列的第一个非零元三元组时，按cposcol的位置，将其放至T.data中，当再次遇到
11、中，当再次遇到col列的非零元三元组时，只须顺序放到col列元素的后面列元素的后面;31方法二以M为基准，“按位就坐”colnumcolcposcol123456722811001352789121213931-3361443245218611564-7i jv ij vM.data T.data12122112第2列第一个非零元在T中的位置139第3列第一个非零元在b中的位置31931-313-33614631443243424521825186115161564-746-74第2列第二个非零元在T中的位置65第3列第二个非零元在b中的位置第1列第一个非零元在T中的位置2793第4列第一个非
12、零元在T中的位置求各列第1个非零元在T中位置求各列非零元个数扫描M.data实现M到T的转置32void FastTransposeSMatrix(TSMatrix M,TSMatrix&T)/采用三元组顺序表存储表示，求稀疏矩阵M的转置矩阵T。 T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu)for(col=1;col=M.nu;+col)numcol=0;for(t=1;t=M.tu;+t)+numM.datat.j;cpos1=1;/求第col列中第一个非零元在T.data中的序号for(col=2;col=M.tu;+col)cposcol=cposcol-
13、1+numcol-1;for(p=1;p ?从时间上看，算法中有四个并列的单循环，循环次数分别为从时间上看，算法中有四个并列的单循环，循环次数分别为mu、tu、tu和tu，因而总的时间复杂度为O(mu+tu)，在M的非零元个数tu和munu同等数量级时，其时间复杂度为同等数量级时，其时间复杂度为O(munu)，和普通矩阵转置算法的时间复杂度相同。 由此可见，只有当，和普通矩阵转置算法的时间复杂度相同。 由此可见，只有当tu 345.3.3稀疏矩阵的十字链表法?设行指针数组和列指针数组，数组的元素分别指向对应行、列第一个非零元，数组的元素分别指向对应行、列第一个非零元?结点定义tpedef structOLNodeint i,j;ElemType e;OLNode*ext,*rnext;OLNode,*OLink;tpedef structCrossListOLink*rhead;OLink*chead;int mu,nu,tu;CrossList;ijeextrnext3534008000450003?=A1134182252345.3.3稀疏矩阵的十字链表法36418234m=4,n=31,1,32,2,52,3,44,1,82,1,71132172255.3.3稀疏矩阵的十字链表法37广义表Microsoft PowerPoint演示文演。 内容仅供参考
