严蔚敏数据结构 (2)

1第5章数组和广义表（Arrays&Lists）5.1数组的定义5.2数组的顺序存储表示和实现5.3矩阵的压缩存储5.4广义表的定义5.5广义表的存储结构2二、稀疏矩阵的操作0129000000000-3000140002400001800001500-70000–3001512000180900240000000-70014000000000(1,2,12)(1,3,9)(3,1,-3)(3,5,14)(4,3,24)(5,2,18)(6,1,15)(6,4,-7)(1,3,-3)(1,6,15)(2,1,12)(2,5,18)(3,1,9)(3,4,24)(4,6,-7)(5,3,14)已知三元组表a.data求三元组表b.data转置后MT（以转置运算为例，加减用十字链表）目的：3答：肯定不正确！除了：（1）每个元素的行下标和列下标互换（即三元组中的i和j互换）；还需要：（2）T的总行数mu和总列数nu也要互换；（3）重排三元组内各元素顺序，使转置后的三元组也按行（或列）为主序有规律的排列。上述（1）和（2）容易实现，难点在（3）。若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种说法正确吗？有两种实现转置的方法压缩转置快速(压缩)转置提问：4方法1：压缩转置思路：反复扫描a表（记为a.data）中的列序，从j=1～n依次进行转置。已知三元组表a.data求三元组表b.data①(1,3,-3)②(1,6,15)③(2,1,12)④(2,5,18)⑤(3,1,9)⑥(3,4,24)⑦(4,6,-7)⑧(5,3,14)(1,2,12)(1,3,9)(3,1,-3)(3,5,14)(4,3,24)(5,2,18)(6,1,15)(6,4,-7)1122colq1234每个元素的列分量表示为：a.data[p].jp1234......5方法2快速转置（自学）已知三元组表a.data求三元组表b.data③(1,3,-3)①(2,1,12)⑥(2,5,18)②(3,1,9)⑧(4,6,-7)④(5,3,14)⑦(1,6,15)⑤(3,4,24)(1,2,12)(1,3,9)(3,1,-3)(3,5,14)(4,3,24)(5,2,18)(6,1,15)(6,4,-7)思路：依次把a.data中的元素直接送入b.data的恰当位置上（即M三元组的p指针不回溯）。关键：怎样寻找b.data的“恰当”位置？p1234q356如果能预知M矩阵每一列(即T的每一行)的非零元素个数，又能很快得知第一个非零元素在b.data中的位置,则扫描a.data时便可以将每个元素准确定位(因已知若干参考点)技巧：为实现转置运算，应当按列生成M矩阵三元组表的两个辅助向量，让它携带每列的非零元素个数NUM(i)以及每列的第一个非零元素在三元组表中的位置POS(i)等信息。设计思路：i123456NUM(i)222110POS(i)135789计算式：POS(1)＝1POS(i)＝POS(i-1)+NUM(i-1)辅助向量的样式：请注意a.data特征：每列首个非零元素必定先被扫描到。7令：M矩阵中的列变量用col表示；num[col]：存放M中第col列中非0元素个数cpos[col]：存放M中第col列的第一个非0元素的位置（即b.data中待计算的“恰当”位置所需参考点）讨论：求出按列优先的辅助向量后，如何实现快速转置？col123456num[col]222110cpos[col]1计算式：cpos(1)＝1cpos[col]＝cpos[col-1]+num[col-1]357890129000000000-3000140002400001800001500-700Mcol123456由a.data中每个元素的列信息，可以直接从辅助向量cpos[col]中查出在b.data中的“基准”位置，进而得到当前元素之位置。想一想：是从原始矩阵M中来统计num[col]呢，还是从对应的三元组表a.data中统计更合理？三元组表a.data(6,4,-7)(6,1,15)(5,2,18)(4,3,24)(3,5,14)(3,1,-3)(1,3,9)(1,2,12)colp/t1234...8StatusFastTransposeSMatrix（TSMatirxM,TSMatirx&T）{T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){for(col=1;col=M.nu;col++)num[col]=0;for(t=1;t=M.tu;t++){col=M.data[t].j;++num[col];}cpos[1]=1;for(col=2;col=M.nu;col++)cpos[col]=cpos[col-1]+num[col-1];for(p=1;p=M.tu;p++){col=M.data[p].j;q=cpos[col];T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].value=M.data[p].value;++cpos[col];}//for}//ifreturnOK;}//FastTranposeSMatrix;快速转置算法描述：//M是顺序存储的三元组表，求M的转置矩阵T//先清0,再//统计每列非零元素个数//再生成每列首元位置辅助向量//p指向a.data，循环次数为非0元素总个数tu//查辅助向量得q，即T中位置前3个for循环用来产生两个辅助向量重要！巧妙修改向量内容（列坐标加1），使其不再固定指向本列第一个非零元素，而是预备给同列的下一非零元素定位之用元素转置91.与常规算法相比，附加了生成辅助向量表的工作。增开了2个长度为列长的数组(num[]和cpos[]）。传统转置：O(mu*nu)压缩转置：O(mu*tu)压缩快速转置：O(nu+tu)快速转置算法的效率分析：2.从时间上，此算法用了4个并列的单循环，而且其中前3个单循环都是用来产生辅助向量表的。for(col=1;col=M.nu;col++){};循环次数＝nu（列数）;for(i=1;i=M.tu;i++){};循环次数＝tu（非0元素个数）;for(col=2;col=M.nu;col++){};循环次数＝nu;for(p=1;p=M.tu;p++){};循环次数＝tu;该算法的时间复杂度＝nu+tu+nu+tu=O(nu+tu）讨论：最恶劣情况是矩阵中全为非零元素，此时tu=nu*mu而此时的时间复杂度也只是O(mu*nu)，并未超过传统转置算法的时间复杂度。小结：稀疏矩阵相乘的算法略，见教材P101-103增设辅助向量，牺牲空间效率换取时间效率。10第5章数组和广义表（Arrays&Lists）①元素的值并非原子类型，可以再分解，表中元素也是一个线性表（即广义的线性表）。②所有数据元素仍属同一数据类型。5.1数组的定义5.2数组的顺序表示和实现5.3矩阵的压缩存储5.4广义表的定义5.5广义表的存储结构数组和广义表的特点：一种特殊的线性表115.4广义表的定义广义表是线性表的推广，也称为列表（lists）记为：LS=(a1,a2,……，an)广义表名表头(Head）表尾(Tail)1、定义：①用小写字母表示原子类型，用大写字母表示列表。②第一个元素是表头，而其余元素组成的表称为表尾；n是表长在广义表中约定：特别提示：任何一个非空表，表头可能是原子，也可能是列表；但表尾一定是列表！122、特点：•有次序性•有长度•有深度•可递归•可共享一个直接前驱和一个直接后继＝表中元素个数＝表中括号的重数自己可以作为自己的子表可以为其他广义表所共享讨论：广义表与线性表的区别和联系？广义表中元素既可以是原子类型，也可以是列表；当每个元素都为原子且类型相同时，就是线性表。13E=(a,E)=(a,(a,E))=(a,(a,(a,…….)))，E为递归表1）A=()2）B=(e)3）C=(a,(b,c,d))4）D=(A,B,C)5）E=(a,E)例1：求下列广义表的长度。n=0，因为A是空表n=1，表中元素e是原子n=2，a为原子，(b,c,d)为子表n=3，3个元素都是子表n=2，a为原子，E为子表D=(A,B,C)=((),(e),(a,(b,c,d)))，共享表14ABDCeabcd②A=(a,(b,A))例2：试用图形表示下列广义表.（设代表子表，代表原子）e①D=(A,B,C)=((),(e),(a,(b,c,d)))Aab①的长度为3，深度为3②的长度为2，深度为∞深度＝括号的重数＝结点的层数15广义表的抽象数据类型定义见教材P107-108ADTGlist{数据对象：D={ei|i=1,2,……,n;n≥0;ei∈AtomSet或Glist}数据关系：R1={ei-1,ei|ei-1,ei∈D,2≤i≤n}基本操作：InitGList(&L);操作结果：创建空的广义表L.CreateGList(&L,S);初始条件：S是广义表的书写形式串。操作结果：由S创建广义表L.……}ADTGlist16介绍两种特殊的基本操作：GetHead(L)——取表头(可能是原子或列表)初始条件：广义表L存在。操作结果：取广义表L的头。GetTail(L)——取表尾(一定是列表)初始条件：广义表L存在。操作结果：取广义表L的尾。171.GetTail(b,k,p,h)＝;2.GetHead((a,b),(c,d))＝;3.GetTail((a,b),(c,d))＝;4.GetTail【GetHead((a,b),(c,d))】＝;例：求下列广义表操作的结果(k,p,h)（b）(a,b)5.GetTail（e）＝;6.GetHead(())＝.7.GetTail(())＝.()(a,b)()()((c,d))185.5广义表的存储结构由于广义表的元素可以是不同结构（原子或列表），难以用顺序存储结构表示，通常用链式结构，每个元素用一个结点表示。1.原子结点：表示原子，可设2个域或3个域，依习惯而选。valuetag=0标志域数值域注意：列表的“元素”还可以是列表，所以结点可能有两种形式：tpatomtag=０标志域值域表尾指针法2：标志域、值域、表尾指针指向下一结点法1：标志域，数值域19tphptag=1标志域表头指针表尾指针2.表结点：表示列表，若表不空，则可分解为表头和表尾，用3个域表示：标志域，表头指针，表尾指针。①A=()^10e③C=(a,(b,c,d))1^110a0b0d0c1^1例：②B=(e)A=NULL指向表头元素指向表尾（列表）^^1原子结点的第一种表示法20⑤E=(a,E)④D=(A,B,C)＝((),(e),(a,(b,c,d)))0a^11^10e1^11^110a0b0d0c1^1^1（参见教材P109图）原子结点的第一种表示法比较麻烦，若采用第二种会明快些（见P110图）21本章小结1.数组可视为一种广义线性表；2.数组的存储有行/低地址优先和列/高地址优先两种不同的顺序；3.对于稀疏矩阵，有较好的压缩存储和运算方法；4.广义表（列表）是线性表的推广，也是一种线性结构；5.任何一个非空表，表头可能是原子，也可能是列表；但表尾一定是列表。第5章结束线性结构内容结束