《数据结构》课件第四章

第四章数组内容提要数组的定义、表示与实现矩阵的压缩存储特殊矩阵稀疏矩阵数组基本定义数组的维数一旦被定义，就不再改变二维数组也可以看作元素类型为一维数组的一维数组类型Typedefelemtypearray2[m][n];等价于Typedefelemtypearray1[n];//先定义一个一维数组Typedefarray1array2[m];数组的顺序存储方式由于存储单元是一维的结构，而数组是个多维的结构，那么用一组连续存储单元存放数组的元素时，映射问题是关键。行优先存储：将数组按行向量排列，即第i+1行紧接在第i行后。（C语言采用这种方式）列优先存储：将数组元素按列向量排列。a00a01…a0na10a11..a20a00a10…an0a01a11..an1数组元素的存储地址★

二维数组(m*n)Loc(i,j)=Loc(0,0)+(i*n+j)*s0<i≤m-1,0<j≤n-1（适用于数组下标规定从0起始的编程语言）三维数组(m*n*p)Loc[i][j][k]=Loc[0][0][0]+(i*(n*p)+j*p+k)*s0<i≤m-1,0<j≤n-1，0<k≤p-1

下面是数组的顺序存储表示和实现typedefstruct{//数组元素基址，由InitArray函数来分配

ElemType*base;

//数组维数

intdim;//数组维界基址，存放每一维的长度

int *bounds;

//数组映象函数常量基址，由InitArray分配

int*constants;}Array；数组的操作数组除了结构的初始化和销毁操作之外，只有两个操作：给定一组下标，读取相应的数据元素

GetValue(A,&e,i,j)给定一组下标，修改相应数据元素中的某一个或几个数据项的值

ChangeValue(A,e,i,j)矩阵的压缩存储矩阵是很多科学与工程计算问题中研究的数学对象。如何存储矩阵的元，从而使矩阵的各种运算能有效地进行？这是很重要的。为了节约矩阵存储的空间，往往对一些特殊矩阵进行压缩存储——多个值相同的元只分配一个存储空间；对零元不分配空间矩阵常识特殊矩阵——数值相同的元素或零元素在矩阵中的分布有一定规律对称矩阵：两种对称方向下/上三角矩阵：右上/左下三角（不包括对角线）中的元均为常数或０稀疏矩阵稀疏因子＝非０元的个数／（m×n）当稀疏因子≦0.05时的矩阵被称为稀疏矩阵对称矩阵的压缩存储对称矩阵的特点：aij=aji(1<=i,j<=n)分配方法：为每一对对称元分配一个存储空间例：若以一维数组作为n阶对称矩阵的存储结构，以行序为主序，存储下三角(包括主对角线)矩阵。则数组与矩阵中的aij存在一一对应的关系an,n..an,1…a31a22a21a11K=012n(n-1)/2n(n+1)/2-1j<i

1i－+2)1j－(jj≥i

1j－+2)1i－(i=k当当下标转换算法intij_to_k(inti,intj){If(i<1||j<1)return(-1);If(i>=j)return(i(i-1)/2+j-1);Elsereturn(j(j-1)/2+i-1);}输入并存储对称矩阵的算法VoidMyint(elemtypea[],intn);{for(k=0;k<n(n+1)/2;k++)Scanf(&a[k]);}读取对称矩阵中某元素的算法Statusgetelem(elemtypea[],inti,intj,elemtype&e){k=ij_to_k(i,j);

if(k>=0){e=a[k];returnOK;}elsereturnERROR;}输出打印对称矩阵的算法Voidprint(elemtypeA[];inti;intn){for(inti=1;i<=n;i++){printf(“\n);for(j=1;j<=n;j++){getelem(A,i,j,e);printf(“%d”,e);}}}//行为主序稀疏矩阵的存储

定义：如果一个m*n的矩阵中非零元素比零元素的个数少得多，且非零元素的分布没有规律压缩存储：只存储非零元素由一个三元组能够惟一确定矩阵的每个非零元——三元组顺序表

//非零元个数的最大值为mu*nu*0.05，假设为40#defineMAXSIZE40

typedefstruct{introw，col;ElemTypevalue；}Triple；typedefstruct{

//data:非零元三元组表，data[0]用来放置总行数、总列数和非零元素个数

Tripledata[MAXSIZE+1]；

//矩阵的行数、列数和非零元个数

intmu，nu，tu;//tu表示稀疏矩阵中的非零元素的个数}TSMatrix；typedefstruct{introw，col;ElemTypevalue；}Triple；typedefstruct{Tripledata[MAXSIZE+1]；……稀疏矩阵的转置运算

对于一个m*n的矩阵M，它的转置矩阵T是一个n*m的矩阵转置方法：矩阵行列值转换，原有的m*n矩阵M要变为n*m的矩阵T。每个三元组中的row和col位置互换，即原来的Aij对应Bji三元组A的排列是以原矩阵的行号为主序，而三元组B是以原矩阵的列为排列顺序rowcolvalue121213931-3361443245218611564-7rowcolvalue13-3161521122518319342446-76314稀疏矩阵的转置算法时间复杂度：

O(nu*tu)已知矩阵的三元组顺序表A,求其转置矩阵的三元组顺序表BStatusTransposeSMatrix(TSMatrixA，TSMatrix&B){

//采用三元组表存储表示，求稀疏矩阵A的转置矩阵B。

B.mu=A.nu；B.nu=A.mu；B.tu=A.tu；

if(B.tu){q=1；//b组,0号位存其他的信息

for(j=1；j<=A.nu；++j)for(p=1；p<=A.tu；++p)//p是A组的下标

if(A.data[p].col==j){

B.data[q].row=A.data[p].col;B.data[q].col=A.data[p].row;B.data[q].value=A.data[p].value;q++;}}returnOK；}//TransposeSMatrix时间复杂度：O(nu*tu)十字链表当矩阵的非零元个数和位置在操作(即矩阵运算)过程中变化较大时，就不宜采用顺序存储结构来表示三元组的线性表。 例如，在作“将矩阵B加到矩阵A上”的操作时，由于非零元的添加或正负抵消归零等将会引起A.data中元素值的变动。为此，对这种类型的矩阵，采用链式存储结构表示三元组的线性表更为恰当。每个非零元可用一个含五个域的结点表示其中row，col和val三个域分别表示该非零元所在的行、列和非零元的值向右域right用以链接同一行中下一个非零元向下域down用以链接同一列中下一个非零元。rightdownvalcolrow//—

—稀疏矩阵的十字链表存储表示—

—

typedefstructOLNode{ inti，j；

ElemTypee；

structOLNode*right，*down;}OLNode；*OLink；

typedefstruct{

//行和列链表头指针向量,基址由CreateSMatrix分配

OLink*rhead，*chead; intmu，nu,tu;//稀疏矩阵的行数、列数和非 零元个数

}CrossList；

稀疏矩阵M的十字链表311541122213M.cheadM.rhead生成十字链表(当i值为0时结束输入)两个矩阵相加和第二章中讨论的两个一元多项式相加极为相似。不同的是一元多项式中只有一个变元(即指数项)，而矩阵中每个非零元有两个变元(行值和列值)，每个结点既在行表中又在列表中，致使插入