清华大学出版社数据结构（C语言版）第4章 数组

第4章数组4.1数组的定义4.2数组的顺序表示和实现4.3矩阵的压缩存储4.1数组的定义一维数组可以看成是一个线性表；二维数组可看作一种特殊的线性表，即线性表中数据元素本身也是一个线性表。一、数组的定义和特点1.定义数组是有序数据的集合2.数组特点数组结构固定数据元素同构()()()()()()()()()次序约定:以行序为主序

a11a12……..a1n

a21a22……..a2n

am1am2……..amn

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

按行序为主序存放:Basic,Pascal,C语言

amn

……..

am2

am1……….

a2n

……..

a22

a21a1n

…….a12

a1101n-1m*n-1n4.2数组的顺序表示和实现次序约定:以列序为主序

按列序为主序:(Fortran语言）01m-1m*n-1m

amn

……..

a2n

a1n……….

am2

……..

a22

a12am1

…….a21

a11

a11

a12

……..

a1n

a21

a22

……..

a2n

am1

am2

……..

amn

….Loc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*lK=(j-1)*m+(i-1)4.2数组的顺序表示和实现1.对称矩阵

a11a12

….

……..a1n

a21

a22

……..…….a2n

an1

an2

……..ann

….a11

a21

a22

a31

a32

an1ann

…...…...k=01234按行序为主序：4.3矩阵的压缩存储

a11

00

……..0

a21a22

0

……..0

an1an2an3……..ann

….0Loc(aij)=Loc(a11)+[+(j-1)]*Lk=i*(i-1)/2+(j-1)(i>=j)i(i-1)22.三角矩阵4.3矩阵的压缩存储a11

a21

a22

a31

a32

an1ann

…...…...k=01234按行序为主序：3.对角矩阵

a11

a120

…………….0

a21

a22

a23

0

……………00

0

…an-1,n-2an-1,n-1

an-1,n0

0

……an,n-1ann.

0

a32a33

a34

0

………0……………Loc(aij)=Loc(a11)+(3*(i-2)+2+(j-i+1))*L(I-1<=j<=I+1)a11a12a21a22a23ann-1ann

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

7

8

121213931-3361443245218611564-7dataijv012345678data[0].i,data[0].j,data[0].v分别存放矩阵行列维数和非零元素个数行列下标非零元素值

#defineMAXSIZE12500

typedefstruct{

inti,j;//该非零元的行下标和列下标

ElemTypee;//该非零元的值

}Triple;//三元组类型typedefunion{

Tripledata[MAXSIZE+1];

intmu,nu,tu;}TSMatrix;//稀疏矩阵类型如何求转置矩阵？用常规的二维数组表示时的算法for(col=1;col<=nu;++col)

for(row=1;row<=mu;++row)T[col][row]=M[row][col];用“三元组”表示时如何实现？121415-522-731363428211451-522-713364328首先应该确定每一行的第一个非零元在三元组中的位置。

cpot[1]=1;

for(col=2;col<=;++col)cpot[col]=cpot[col-1]+num[col-1];StatusFastTransposeSMatrix(TSMatrixM,TSMatrix&T){=;=;=;

if()

{

for(col=1;col<=;++col)num[col]=0;

for(t=1;t<=;++t)++num[M.data[t].j];

cpot[1]=1;

for(col=2;col<=;++col)cpot[col]=cpot[col-1]+num[col-1];for(p=1;p<=;++p){}

}//if

returnOK;}//FastTransposeSMatrix

转置矩阵元素Col=M.data[p].j;q=cpot[col];T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].e=M.data[p].e;++cpot[col]三元组顺序表又称有序的双下标法，它的特点是，非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。然而，若需随机存取某一行中的非零元，则需从头开始进行查找。行逻辑联接的顺序表#defineMAXMN500typedefstruct{Tripledata[MAXSIZ