C语言基础课件1第4章 数组

1二维数组()()()()()()()()()数组A可看成一个线性表A=(a0，a1

，...，ak)

k=m-1或n-1ai

或者是行向量ai=(ai0

，ai1

，...，ai,n-1)0≤i≤m-1aj或者是列向量aj=(a0j

，a1j

，...，am-1,j)0≤j≤n-124.1.2数组的顺序存储结构次序约定以行序为主序以列序为主序

a11a12……..a1n

a21a22……..a2n

am1am2……..amn

….Loc(aij)=Loc(a11)+[(i-1)n+(j-1)]*l

按行序为主序存放amn

……..

am2am1

……….a2n

……..

a22a21a1n

…….a12

a1101n-1m*n-1n

按列序为主序01m-1m*n-1mamn

……..

a2na1n

……….am2

……..

a22a12am1

…….a21

a11

a11

a12

……..

a1n

a21

a22……..

a2n

am1

am2

……..amn

….Loc(aij)=Loc(a11)+[(j-1)m+(i-1)]*l

34.1.3矩阵的压缩存储方法压缩存储为多个值相同的元素只分配一个存储空间对零元素不分配空间4

a11

a12

….

……..a1n

a21

a22

……..…….a2n

an1

an2

……..ann

….a11a21a22a31a32an1ann

…...…...k=01234n(n-1)/2n(n+1)/2-1

按行序为主序：对称矩阵的压缩存储方法5

a11

00

……..0

a21

a22

0

……..0

an1

an2

an3……..ann

….

0Loc(aij)=Loc(a11)+[(+(j-1)]*l

i(i-1)2a11a21a22a31a32an1ann

…...…...k=01234n(n-1)/2n(n+1)/2-1按行序为主序：三角矩阵的压缩存储方法6

a11

a12

0

…………….0

a21

a22

a23

0

……………0

0

0

…an-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)+3*(i-1)-1+j-i+1=Loc(a11)+2(i-1)+(j-1)

a11a12a21a22a23ann-1ann

…...…...k=01234n(n-1)/2n(n+1)/2-1按行序为主序：对角矩阵的压缩存储方法7稀疏矩阵定义非零元较零元少，且分布没有一定规律的矩阵压缩存储原则只存矩阵的行列维数和每个非零元的行列下标及其值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)唯一确定8三元组表所需存储单元个数为3(t+1)其中t为非零元个数6

7

8

121213931-3361443245218611564-7maijv012345678ma.data[0]中分别存放矩阵行列维数和非零元个数行列下标非零元值稀疏矩阵的三元组表示法#defineMAX10typedefstruct{inti,j;elemtypev;}node;typedefstruct{intmu,nu,tu;nodedata[MAX];}mat;matma;mu,nu,tu分别存放矩阵行列维数和非零元个数9稀疏矩阵转置算法一算法思想将矩阵A的行数和列数互换=>矩阵B将每个三元组的i和j互换=>矩阵B对三元组表B，按其行序进行排序转置后的三元组B以行（即A的列）为主序排列6

7

8

121213931-3361443245218611564-7ijv01234567810稀疏矩阵转置算法二算法思想按矩阵A的列序进行转置首先寻找矩阵A的第1列的所有三元组，将其(i,j,v)改为(j,i,v)后依次存放到矩阵B的三元组表中然后中寻找矩阵A第2列的所有三元组，将其(i,j,v)改为(j,i,v)后依次存放到矩阵B的三元组表中依次类推转置后的三元组B以行（即A的列）为主序排列11678121213931-3361443245218611564-7ijv012345678ma76813-3161521122518319342446-76314ijv012345678mbkppppppppkkkkppppppppcol=1col=212稀疏矩阵的转置算法分析算法的主要耗费时间是在col和p的两重循环中，所以算法的时间复杂度为O(nu*tu)即和(A的列数与非零元素的个数的乘积)成正比当非零元个数值tu->m*n时(m、n分别表示数组的行列数),算法的时间复杂度成为O(m*n2)上述转置算法只适用于:tu<<m*n的情况13cpot[1]=1;cpot[col]=cpot[col-1]+num[col-1];(2colma[0].j)1357889快速转置:即按ma中三元组次序转置，转置结果放入b中恰当位置此法关键是要预先确定M中每一列第一个非零元在mb中位置,

即转置前应先求得M的每一列中非零元个数实现：设两个数组num[col]：表示矩阵M中第col列中非零元个数cpot[col]：指示M中第col列第一个非零元在mb中位置,显然:colnum[col]cpot[col]1222324150617014678121213931-3361443245218611564-7ijv012345678maijv012345678mbcolnum[col]cpot[col]11223235247158068179076813-3161521122518319342446-76314pppppppp462975315快速转置算法如下：voidfasttrans(matb,mata){intp,q,col,k;intnum[a.n+1],cpot[a.n+1];b.m=a.n;b.n=a.m;b.t=a.t;if(b.t<=0)printf(“a=0”\n);for(col=1;col<=a.n;++col)num[col]=0;for(k=1;k<=a.t;++k)++num[a.data[k].j];cpot[1]=1;for(col=2;col<=a.n;