数据结构电子课件教案-第5章 数组.ppt

1,矩阵,2,主要内容,1矩阵的定义2矩阵的顺序表示和实现数组的应用例子3矩阵的压缩存储,多维数组（矩阵）可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表,3,1数组的定义和特点,定义,矩阵的特点矩阵结构固定矩阵元素同构矩阵运算（两个最重要的运算）给定一组下标，存取相应的数据元素给定一组下标，修改数据元素的值,4,多维数组的存储方式以行序为主序以列序为主序,2数组的顺序表示和实现,重点：对于矩阵A=aijm*n不同存储方式下，元素aij的存储位置计算,5,数组的应用,例：寻找两个字符串的最长公共子串假设：S1sgabacbadfgbacst（长度：m）S2=gabadfgab(长度：n)(不失一般性：假设mn),解法思路：基本解法找出S2中的所有子串(T1,T2,Tk),将其作为模式串将(T1,T2,Tk)这k个模式串与S2进行模式匹配本文解法：利用数组,6,i行坐标j列坐标,如何表示对角线？,Mnm,k=i-j,主对角线k=0主对角线右上对角线k=-1,-2,-3,-(m-1)行标号都从0开始，列标号从1到m-1变化主对角线左下角k=1,2,3,n-1列标号从都从0开始，行标号从1到n-1变化,如何找到对角线上连续出现的1？,需要什么？需要连续1序列的最大长度（maxlen）及起始位置(jpos)算法思路搜索每一条对角线,只需要起始位置对一条对角线，从起始位置开始，寻找出现1的位置,7,voiddiagmax(intmat20,int,voiddiagscan(inti,intj,int,8,intmaxsamesubstring(char*string1,char*string2,char*,算法:求两个串的最长公共子串,9,思考求串S1和S2的所有公共子串，算法？求三个串S1、S2和S3三个串的最长公共子串？,10,3矩阵的压缩存储,3.1特殊矩阵的存储表示3.2稀疏矩阵的三元组表示法3.3稀疏矩阵的十字链表表示法,11,3.1特殊矩阵的存储表示,对称矩阵,12,3.1特殊矩阵的存储表示,三角矩阵,或,13,3.1特殊矩阵的存储表示,对角矩阵,Loc(aij)=Loc(a11)+2(i-1)+(j-1)*L,或,14,3.2稀疏矩阵的三元组表示法,定义：非零元较零元少，且分布没有一定规律的矩阵,M由(1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7)和矩阵维数（6,7）唯一确定,压缩存储原则：只存矩阵的行列维数和每个非零元的行列下标及其值,15,稀疏矩阵的压缩存储方法顺序存储结构：三元组表,TemplatestructTripleinti,j;/行、列坐标Te;/非零元值Triple;,16,templateclassspareMatpublic:SpareMat(intm,intn);SpareMat();voidTranspose();private:introws,cols,size;Triple*data;,17,M的三元组顺序表图示,ije,M.data,18,稀疏矩阵转置运算,稀疏矩阵转置运算问题描述：已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表,19,稀疏矩阵转置运算,问题分析：一般矩阵转置算法,voidtranspose(intM,intT)/普通矩阵转置for(col=1;col=n;col+)for(row=1;row=m;row+)/0行0列不用Tcolrow=Mrowcol;,特点：行、列下标交换,T（n）=O(m*n),20,ije,M.data,ije,T.data,矩阵M的三元组顺序表,转置矩阵T的三元组顺序表,规律?,21,稀疏矩阵转置运算,解决思路：只要做到将矩阵行、列维数互换将每个三元组中的i和j相互调换重排三元组次序，使M中元素以T的行(M的列)为主序,方法一：以T为基准，“按需点菜”方法二：以M为基准，“按位就坐”,？,22,方法一：以T为基准，“按需点菜”,算法：对M.data从头至尾扫描：第一次扫描时，将M.data中列号为1的三元组赋值到T.data中第二次扫描时，将M.data中列号为2的三元组赋值到T.data中依此类推，直至将M.data所有三元组赋值到T.data中,23,ijv,ijv,31-3,2518,13-3,6115,1615,1212,2112,5218,139,319,4324,3424,64-7,46-7,3614,6314,M.data,T.data,对M六次扫描完成转置运算,第一次扫描查找第1列元素,第一次扫描结束,第二次扫描结束,第二次扫描查找第2列元素,第三次扫描查找第3列元素,第四次扫描查找第4列元素,第五次扫描查找第5列元素,第六次扫描查找第6列元素,24,/转置运算算法voidTranspose(TSMatrixM,TSMatrix,25,时间复杂度分析算法的基本操作为将M.data中的三元组赋值到T.data，是在两个循环中完成的，故算法的时间复杂度为O(nutu)我们知道，若用二维数组存储矩阵，转置算法的时间复杂度为O(munu)。当非零元的个数tu和矩阵元素个数munu同数量级时，转置运算算法1的时间复杂度为O(mununu)。由此可见：在这种情况下，用三元组顺序表存储矩阵，虽然可能节省了存储空间，但时间复杂度提高了，因此算法仅适于tumunu的情况。该算法效率不高的原因是：对为实现M到T的转置，该算法对M.data进行了多次扫描。能否在对M.data一次扫描的过程中，完成M到T的转置？,26,方法二：以M为基准，“按位就坐”,以M为基准，“按位就坐”快速转置算法即按M中三元组次序转置，转置结果放入T中恰当位置。关键预先确定M中每一列第一个非零元在T中位置？为确定这些位置，转置前应先求得M的每一列中非零元个数,27,ijv,M.data,ijv,2112,46-7,13-3,3424,1615,319,6314,2518,T.data,M.data的三元组中每条纪录在T.data三元组中的位置？,各列第一个非零元三元组在T.data中的位置？,28,实现：设两个数组num、cposnumcol：存储M中第col列非零元个数cposcol：存储M中第col列第一个非零元三元组在T.data中的位置cposcol的计算方法：cpos1=1cposcol=cposcol-1+numcol-1(2colM.nu),29,快速转置算法主要步骤求M中各列非零元个数num;求M中各列第一个非零元在T.data中的下标cpos;对M.data进行一次扫描，遇到col列的第一个非零元三元组时，按cposcol的位置，将其放至T.data中，当再次遇到col列的非零元三元组时，只须顺序放到col列元素的后面;,30,2,2,8,1,1,0,0,1,3,5,2,7,8,9,ijv,ijv,M.data,T.data,1212,2112,第2列第一个非零元在b中的位置,139,第3列第一个非零元在b中的位置,319,31-3,13-3,3614,6314,4324,3424,5218,2518,6115,1615,64-7,46-7,4,第2列第二个非零元在b中的位置,6,5,第3列第二个非零元在b中的位置,第1列第一个非零元在b中的位置,2,7,9,3,第4列第一个非零元在b中的位置,求各列第1个非零元在b中位置,求各列非零元个数,扫描M.data实现M到T的转置,31,voidFastTransposeSMatrix(TSMatrixM,TSMatrix/for/if,32,时间复杂度分析该算法利用两个辅助向量num、cpos，实现了对M.data一次扫描完成M到T的转置。从时间上看，算法中有四个并列的单循环，循环次数分别为mu、tu、tu和tu，因而总的时间复杂度为O(mu+tu)，在M的非零元个数tu和munu同等数量级时，其时间复杂度为O(munu)，和普通矩阵转置算法的时间复杂度相同。由此可见，只有当tumunu时，使用快速转置算法才有意义。,33,3.3稀疏矩阵的十字链表法,设行指针数组和列指针数组，数组的元素分别指向对应行、列第一个非零元结点定义,templatestructOLNodeinti,j;Te;OLNode*cnext,*rnext;,34,t