第5讲 数组和广义表.ppt

《第5讲 数组和广义表.ppt》由会员分享，可在线阅读，更多相关《第5讲 数组和广义表.ppt（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构与算法分析（数据结构与算法分析（C+C+版）版）第第5 5章章 矩阵和广义表矩阵和广义表数组数组矩阵矩阵广义表广义表数据结构与算法分析（数据结构与算法分析（C+C+版）版）矩阵矩阵一般用二维数组来描述一个一般用二维数组来描述一个mn 矩阵矩阵a：ElemType amn；矩阵中的元素矩阵中的元素a(i,j)对应于二维数组的元素对应于二维数组的元素ai-1 j-1。这种形式要求使用数组的下标。这种形式要求使用数组的下标 来指定来指定每个矩阵元素。每个矩阵元素。数据结构与算法分析（数据结构与算法分析（C+C+版）版）特殊矩阵特殊矩阵 如果值相同的元素或零元素在矩阵中按一定的规律分布，这样的

2、矩阵称为特殊矩阵，可以用特殊方法进行存储和处理，以便提高空间效率和时间效率。1.方阵：是行数和列数相同的矩阵。2.对称矩阵：a是一个对称矩阵当且仅当对于所有的i 和 j，有a(i,j)=a(j,i)。数据结构与算法分析（数据结构与算法分析（C+C+版）版）a11 a12 .a1n a21 a22.a2n an1 an2 .ann .a11 a21 a22 a31 a32 an1 ann.k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序：按行序为主序：按行序为主序：按行序为主序：三角矩阵共计三角矩阵共计元素个元素个数为：数为：数为：数为：n(n+1)/2n(n+1)/

3、2数据结构与算法分析（数据结构与算法分析（C+C+版）版）3.3.下三角矩阵下三角矩阵下三角矩阵下三角矩阵 a11 0 0.0 a21 a22 0.0 an1 an2 an3.ann .0Loc(aij)=Loc(a11)+(+(j-1)*L i(i-1)2a11 a21 a22 a31 a32 an1 ann.k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序：按行序为主序：按行序为主序：按行序为主序：数据结构与算法分析（数据结构与算法分析（C+C+版）版）三对角矩阵三对角矩阵三对角矩阵三对角矩阵 a11 a12 0 .0 a21 a22 a23 0 0 0 0 a

4、n-1,n-2 an-1,n-1 an-1,n 0 0 an,n-1 ann.0 a32 a33 a34 0 0 Loc(aij)=Loc(a11)+2(i-1)+(j-1)L|i-j|1a11 a12 a21 a22 a23 ann-1 ann.k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序：按行序为主序：按行序为主序：按行序为主序：数据结构与算法分析（数据结构与算法分析（C+C+版）版）稀疏矩阵稀疏矩阵(Sparse Matrix)数据结构与算法分析（数据结构与算法分析（C+C+版）版）稀疏矩阵是非零元素个数稀疏矩阵是非零元素个数稀疏矩阵是非零元素个数稀疏矩阵

5、是非零元素个数远远少于矩阵元素个数远远少于矩阵元素个数远远少于矩阵元素个数远远少于矩阵元素个数的矩阵。的矩阵。的矩阵。的矩阵。假设假设m行行n列的矩阵含列的矩阵含t个非个非0元素，一般称元素，一般称=t/(mn)为稀为稀疏因子，且认为疏因子，且认为0.05的矩阵为稀疏矩阵。的矩阵为稀疏矩阵。数据结构与算法分析（数据结构与算法分析（C+C+版）版）以常规方法，即以二维数组表示高阶的以常规方法，即以二维数组表示高阶的稀疏矩阵时产生的问题稀疏矩阵时产生的问题:1)零值元素占了很大空间零值元素占了很大空间;2)计算中进行了很多和零值的运算，遇除计算中进行了很多和零值的运算，遇除法，还需判别除数是否为零

6、。法，还需判别除数是否为零。数据结构与算法分析（数据结构与算法分析（C+C+版）版）1)尽可能少存或不存零值元素；尽可能少存或不存零值元素；解决问题的原则解决问题的原则2)尽可能减少没有实际意义的运算；尽可能减少没有实际意义的运算；3)操作方便。操作方便。即：即：1.能尽可能快地找到与下标值能尽可能快地找到与下标值 (i，j)对应的元素，对应的元素，2.能尽可能快地找到同一行或能尽可能快地找到同一行或 同一列的非零值元。同一列的非零值元。数据结构与算法分析（数据结构与算法分析（C+C+版）版）三元组表三元组表当稀疏矩阵的阶很高时，其中当稀疏矩阵的阶很高时，其中0 0元素会很多。元素会很多。如采

7、用一般矩阵的存储方法，将存储大量如采用一般矩阵的存储方法，将存储大量0 0元素，这样将浪费大量的存储空间。元素，这样将浪费大量的存储空间。一种直观、常用的方法是，对每个非零元一种直观、常用的方法是，对每个非零元素，用素，用三元组（行号，列号，元素值）三元组（行号，列号，元素值）来来表示，这样每个元素的信息就全部记录下表示，这样每个元素的信息就全部记录下来了。三元组声明如下：来了。三元组声明如下：数据结构与算法分析（数据结构与算法分析（C+C+版）版）已知稀疏矩阵三元组顺序表示例三元组顺序表示例三元组表示为数据结构与算法分析（数据结构与算法分析（C+C+版）版）/三元组类模板三元组类模板三元组类

8、模板三元组类模板templateclass template structstruct Triple Triple/数据成员数据成员数据成员数据成员:intint row,row,colcol;/非零元素的行下标与列下标非零元素的行下标与列下标非零元素的行下标与列下标非零元素的行下标与列下标ElemTypeElemType value;value;/非零元素的值非零元素的值非零元素的值非零元素的值;数据结构与算法分析（数据结构与算法分析（C+C+版）版）/稀疏矩阵三元组顺序表类模板稀疏矩阵三元组顺序表类模板稀疏矩阵三元组顺序表类模板稀疏矩阵三元组顺序表类模板templateclass temp

9、late class class TriSparseMatrixTriSparseMatrix protected:protected:/稀疏矩阵三元组顺序表的数据成员稀疏矩阵三元组顺序表的数据成员稀疏矩阵三元组顺序表的数据成员稀疏矩阵三元组顺序表的数据成员:TripleTriple*triElemstriElems;/存储稀疏矩阵的三元组表存储稀疏矩阵的三元组表存储稀疏矩阵的三元组表存储稀疏矩阵的三元组表intint maxSizemaxSize;/非零元素最大个数非零元素最大个数非零元素最大个数非零元素最大个数intint rows,cols,num;rows,cols,num;/稀疏矩阵

10、的行数稀疏矩阵的行数稀疏矩阵的行数稀疏矩阵的行数,列数及非零元个数列数及非零元个数列数及非零元个数列数及非零元个数数据结构与算法分析（数据结构与算法分析（C+C+版）版）public:public:/抽象数据类型方法声明抽象数据类型方法声明抽象数据类型方法声明抽象数据类型方法声明 void InitMatrix(int rs,int cs,int size)；intint GetRowsGetRows();();/返回稀疏矩阵行数返回稀疏矩阵行数返回稀疏矩阵行数返回稀疏矩阵行数 intint GetColsGetCols();();/返回稀疏矩阵列数返回稀疏矩阵列数返回稀疏矩阵列数返回稀疏矩阵

11、列数 intint GetNumGetNum();();/返回稀疏矩阵非零元个数返回稀疏矩阵非零元个数返回稀疏矩阵非零元个数返回稀疏矩阵非零元个数 intint SetElem(intSetElem(int r,r,intint c,c,ElemTypeElemType v v）intint GetElem(intGetElem(int r,r,intint c,c,ElemTypeElemType&v);&v);TriSparseMatrixTriSparseMatrix&operator=(const&operator=(const TriSparseMatrixTriSparseMatr

12、ix©);©);/重载赋值运算符重载赋值运算符重载赋值运算符重载赋值运算符static void static void SimpleTranspose(constSimpleTranspose(const TriSparseMatrixTriSparseMatrix&source,&source,TriSparseMatrixTriSparseMatrix&destdest);/);/将稀疏将稀疏将稀疏将稀疏矩阵矩阵矩阵矩阵sourcesource转置成稀疏矩阵转置成稀疏矩阵转置成稀疏矩阵转置成稀疏矩阵destdest的简单算法的简单算法的简单算法的简单算法;数据结构与算法分

13、析（数据结构与算法分析（C+C+版）版）template void InitMatrix(int rs,int cs,int size)/构造一个构造一个rs行行cs列非零元素最大个数为列非零元素最大个数为size的空稀疏矩的空稀疏矩阵阵if(rs 1|cs 1)throw Error(行数或列数无效行数或列数无效!);/抛出异常抛出异常maxSize=size;/非零元素最大个数非零元素最大个数rows=rs;/行数行数cols=cs;/列数列数num=0;/非零元素个数非零元素个数triElems=new TriplemaxSize;/分配存分配存储空间储空间 数据结构与算法分析（数据结构

14、与算法分析（C+C+版）版）int SetElem(int r,int c,ElemType v)功能：功能：设置指定位置的元素值设置指定位置的元素值算法思路：算法思路：对于设置指定位置对于设置指定位置(r,c)的元素值的元素值v，首先查找在三，首先查找在三元组顺序表中是否有指定位置的三元组元组顺序表中是否有指定位置的三元组:(1)如果存在如果存在当当v0时为更新操作，即将时为更新操作，即将v赋值给原元素赋值给原元素e；否则为删除操作，即删除该三元组。否则为删除操作，即删除该三元组。(2)如果不存在指定的三元组如果不存在指定的三元组当当v0时为按序插入操作；时为按序插入操作；否则不作任何操作。

15、否则不作任何操作。数据结构与算法分析（数据结构与算法分析（C+C+版）版）template class template intint TriSparseMatrixTriSparseMatrix:SetElem(intSetElem(int r,r,intint c,c,ElemTypeElemType v)v)if(r rows|c cols|r 1|c rows|c cols|r 1|c=0&for(j=num-1;j=0&(r (r triElemsj.rowtriElemsj.row|r=|r=triElemsj.rowtriElemsj.row&c c=0&if(j=0&triEl

16、emsj.rowtriElemsj.row=r&=r&triElemsj.coltriElemsj.col=c)=c)/找到三元组找到三元组找到三元组找到三元组if(v=0)if(v=0)/删除三元组删除三元组删除三元组删除三元组for(i=j+1;i num;i+)for(i=j+1;i num;i+)triElemsitriElemsi-1=-1=triElemsitriElemsi;num-;num-;elseelse/修改元素值修改元素值修改元素值修改元素值triElemsj.valuetriElemsj.value=v;=v;return SUCCESS;return SUCCESS

17、;数据结构与算法分析（数据结构与算法分析（C+C+版）版）else if(v!=0)else if(v!=0)if(num if(num j;i-)for(i=num-1;i j;i-)triElemsitriElemsi+1=+1=triElemsitriElemsi;triElemsjtriElemsj+1.row=r;+1.row=r;/行行行行triElemsjtriElemsj+1.col=c;+1.col=c;/列列列列triElemsjtriElemsj+1.value=v;+1.value=v;num+;num+;return SUCCESS;return SUCCESS;el

18、seelse return OVER_FLOW;return OVER_FLOW;return SUCCESS;return SUCCESS;数据结构与算法分析（数据结构与算法分析（C+C+版）版）数据结构与算法分析（数据结构与算法分析（C+C+版）版）算法的基本思想：算法的基本思想：算法的基本思想：算法的基本思想：第一次从第一次从第一次从第一次从sourcesource中取出应该放置到中取出应该放置到中取出应该放置到中取出应该放置到destdest中第一个位置的元素，行列号互换后，放于中第一个位置的元素，行列号互换后，放于中第一个位置的元素，行列号互换后，放于中第一个位置的元素，行列号互换后

19、，放于destdest中第一个中第一个中第一个中第一个位置；第二次从位置；第二次从位置；第二次从位置；第二次从sourcesource中选取应该放到中选取应该放到中选取应该放到中选取应该放到destdest中的第二个位中的第二个位中的第二个位中的第二个位置的元素，置的元素，置的元素，置的元素，如此进行，依次生成，如此进行，依次生成，如此进行，依次生成，如此进行，依次生成destdest中的各元素。中的各元素。中的各元素。中的各元素。由于转置后列号变行号，所以转置后元素的行序排列实质由于转置后列号变行号，所以转置后元素的行序排列实质由于转置后列号变行号，所以转置后元素的行序排列实质由于转置后列号

20、变行号，所以转置后元素的行序排列实质上是原矩阵元素的列序排列。实现算法可形式化描述为：上是原矩阵元素的列序排列。实现算法可形式化描述为：上是原矩阵元素的列序排列。实现算法可形式化描述为：上是原矩阵元素的列序排列。实现算法可形式化描述为：destPosdestPos=0;=0;/稀疏矩阵稀疏矩阵稀疏矩阵稀疏矩阵destdest的下一个三元组的存放位置的下一个三元组的存放位置的下一个三元组的存放位置的下一个三元组的存放位置for(colfor(col=最小列号最小列号最小列号最小列号;colcol =最大列号最大列号最大列号最大列号;colcol+)+)在在在在sourcesource中从头查找有

21、无列号为中从头查找有无列号为中从头查找有无列号为中从头查找有无列号为colcol的三元组；的三元组；的三元组；的三元组；若有，则将其行、列号交换后，依次存入若有，则将其行、列号交换后，依次存入若有，则将其行、列号交换后，依次存入若有，则将其行、列号交换后，依次存入destdest中中中中destPosdestPos所指位置，同时所指位置，同时所指位置，同时所指位置，同时destPosdestPos加加加加1 1；稀疏矩阵的转置稀疏矩阵的转置数据结构与算法分析（数据结构与算法分析（C+C+版）版）templateclass template void void TriSparseMatrixTr

22、iSparseMatrix:SimpleTransposeSimpleTranspose(TriSparseMatrixTriSparseMatrix source,source,TriSparseMatrixTriSparseMatrix&destdest)/操作结果：将稀疏矩阵操作结果：将稀疏矩阵操作结果：将稀疏矩阵操作结果：将稀疏矩阵sourcesource转置成稀疏矩阵转置成稀疏矩阵转置成稀疏矩阵转置成稀疏矩阵destdest的简的简的简的简/单算法单算法单算法单算法 dest.rowsdest.rows=source.colssource.cols;/行数行数行数行数 dest.co

23、lsdest.cols=source.rowssource.rows;/列数列数列数列数 dest.numdest.num=source.numsource.num;/非零元素个数非零元素个数非零元素个数非零元素个数 dest.maxSizedest.maxSize=source.maxSizesource.maxSize;/最大非零元素个数最大非零元素个数最大非零元素个数最大非零元素个数 delete delete dest.triElemsdest.triElems;/释放存储空间释放存储空间释放存储空间释放存储空间 dest.triElemsdest.triElems=new Tripl

24、e=new Triple dest.maxSizedest.maxSize;/分配存储空间分配存储空间分配存储空间分配存储空间数据结构与算法分析（数据结构与算法分析（C+C+版）版）if(if(dest.numdest.num 0)0)intint destPosdestPos=0;=0;/稀疏矩阵稀疏矩阵稀疏矩阵稀疏矩阵destdest的下一个三元组的存放位置的下一个三元组的存放位置的下一个三元组的存放位置的下一个三元组的存放位置 for(for(intint colcol=1;=1;colcol=source.colssource.cols;colcol+)+)/转置前的列变为转置后的行转

25、置前的列变为转置后的行转置前的列变为转置后的行转置前的列变为转置后的行 for(for(intint sourcePossourcePos=0;=0;sourcePossourcePos 0时时,表的表的第一个表元素第一个表元素称为广义表称为广义表 的的表头表头(head),除此之外除此之外,其它表元素组其它表元素组 成的表成的表称为广义表的称为广义表的表尾表尾(tail)数据结构与算法分析（数据结构与算法分析（C+C+版）版）A=()/空表，长度为空表，长度为0B=(x,y,z)/单元素表，长度为单元素表，长度为3C=(B，y，z)/非单非单元素表元素表，长度为，长度为3D=(x，(y，z)

26、/非单元素表，非单元素表，长度为长度为2E=(x，E)/非单元素表，非单元素表，长度为长度为2数据结构与算法分析（数据结构与算法分析（C+C+版）版）由于广义表中的元素又可以是广义表，因此对于广义表有由于广义表中的元素又可以是广义表，因此对于广义表有由于广义表中的元素又可以是广义表，因此对于广义表有由于广义表中的元素又可以是广义表，因此对于广义表有深度的概念。广义表深度的概念。广义表深度的概念。广义表深度的概念。广义表GLGL的深度的深度的深度的深度Depth(GLDepth(GL)定义如下：定义如下：定义如下：定义如下：广义表的深度本质上就是广义表表达式中括号的最大嵌套广义表的深度本质上就是

27、广义表表达式中括号的最大嵌套广义表的深度本质上就是广义表表达式中括号的最大嵌套广义表的深度本质上就是广义表表达式中括号的最大嵌套层数。层数。层数。层数。数据结构与算法分析（数据结构与算法分析（C+C+版）版）求广义表的深度求广义表的深度例如，对于广义表例如，对于广义表 E(B(a,b),D(B(a,b),C(u,(x,y,z),A()1111234数据结构与算法分析（数据结构与算法分析（C+C+版）版）补充：广义表的两个操作1.Head()或GetHead()得到广义表的表头元素（单元素or表元素）2.Tail()或GetTail()得到广义表的表尾，除表头元素之外的剩余元素组成的子表（肯定是

28、广义表）例1：A=(a,b,c,d)Head(A)=a Tail(A)=(b,c,d)例2：若Head(L)=Tail(L),则 L=(a),a)注：a并不是代表单元素数据结构与算法分析（数据结构与算法分析（C+C+版）版）练习：1.A=(a,b,c,d),则Head(A)=Tail(A)=2.已知广义表LS=(a,(b,c,d),e),运用head和tail函数取出原子b的运算是 Head(Head(Tail(LS)(a,b,c,d)()数据结构与算法分析（数据结构与算法分析（C+C+版）版）3.设广义表L=(),(),则Head(L),Tail(L),L的长度和深度分别为多少 Head(L)长度为0，深度为1 Tail(L)长度为1，深度为2 L长度为2，深度为24.Tail(Head(a,b),(c,d)=?(b)数据结构与算法分析（数据结构与算法分析（C+C+版）版）5.已知两个已知两个45的稀疏矩阵的三元组表分别如下的稀疏矩阵的三元组表分别如下,请请画出这两个稀疏矩阵之和的三元组表。画出这两个稀疏矩阵之和的三元组表。