第5讲 数组和广义表.ppt

《第5讲 数组和广义表.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第5章矩阵和广义表数组矩阵广义表矩阵一般用二维数组来描述一个m×n矩阵a：ElemTypea[m][n]；矩阵中的元素a(i,j)对应于二维数组的元素a[i-1][j-1]。这种形式要求使用数组的下标[][]来指定每个矩阵元素。特殊矩阵如果值相同的元素或零元素在矩阵中按一定的规律分布，这样的矩阵称为特殊矩阵，可以用特殊方法进行存储和处理，以便提高空间效率和时间效率。1.方阵：是行数和列数相同的矩阵。2.对称矩阵：a是一个对称矩阵当且仅当对于所有的i和j，有a(i,j)=a(j,i)。a11a12….……..a1na21a22……..…….a2nan1an2……..ann………………….a

2、11a21a22a31a32an1ann…...…...k=01234n(n-1)/2n(n+1)/2-1按行序为主序：三角矩阵共计元素个数为：n(n+1)/23.下三角矩阵a1100……..0a21a220……..0an1an2an3……..ann………………….0Loc(aij)=Loc(a11)+[(+(j-1)]*Li(i-1)2a11a21a22a31a32an1ann…...…...k=01234n(n-1)/2n(n+1)/2-1按行序为主序：三对角矩阵a11a120…………….0a21a22a230……………000…an-1,n-2an-1,n-1an-1,n00……an

3、,n-1ann.0a32a33a340………0……………………………Loc(aij)=Loc(a11)+[2(i-1)+(j-1)]L

4、i-j

5、≤1a11a12a21a22a23ann-1ann…...…...k=01234n(n-1)/2n(n+1)/2-1按行序为主序：稀疏矩阵(SparseMatrix)稀疏矩阵是非零元素个数远远少于矩阵元素个数的矩阵。假设m行n列的矩阵含t个非0元素，一般称δ=t/(mn)为稀疏因子，且认为δ≤0.05的矩阵为稀疏矩阵。以常规方法，即以二维数组表示高阶的稀疏矩阵时产生的问题:1)零值元素占了很大空间;2)计算中进行了很多和零值的运算，遇除法，还需判

6、别除数是否为零。1)尽可能少存或不存零值元素；解决问题的原则2)尽可能减少没有实际意义的运算；3)操作方便。即：1.能尽可能快地找到与下标值(i，j)对应的元素，2.能尽可能快地找到同一行或同一列的非零值元。三元组表当稀疏矩阵的阶很高时，其中0元素会很多。如采用一般矩阵的存储方法，将存储大量0元素，这样将浪费大量的存储空间。一种直观、常用的方法是，对每个非零元素，用三元组（行号，列号，元素值）来表示，这样每个元素的信息就全部记录下来了。三元组声明如下：已知稀疏矩阵三元组顺序表示例三元组表示为//三元组类模板templatestructTriple{//数据成

7、员:introw,col;//非零元素的行下标与列下标ElemTypevalue;//非零元素的值};//稀疏矩阵三元组顺序表类模板templateclassTriSparseMatrix{protected://稀疏矩阵三元组顺序表的数据成员:Triple*triElems;//存储稀疏矩阵的三元组表intmaxSize;//非零元素最大个数introws,cols,num;//稀疏矩阵的行数,列数及非零元个数public://抽象数据类型方法声明voidInitMatrix(intrs,intcs,intsize)；intGetRow

8、s();//返回稀疏矩阵行数intGetCols();//返回稀疏矩阵列数intGetNum();//返回稀疏矩阵非零元个数intSetElem(intr,intc,ElemTypev）intGetElem(intr,intc,ElemType&v);TriSparseMatrix&operator=(constTriSparseMatrix©);//重载赋值运算符staticvoidSimpleTranspose(constTriSparseMatrix&source,TriSparseMatrix

9、&dest);//将稀疏矩阵source转置成稀疏矩阵dest的简单算法};templatevoidInitMatrix(intrs,intcs,intsize)//构造一个rs行cs列非零元素最大个数为size的空稀疏矩阵{if(rs<1

10、

11、cs<1)throwError("行数或列数无效!");//抛出异常maxSize=size;//非零元素最大个数rows=rs;//行数cols=cs;//列数