数据结构课件非常详细 ch5.ppt

《数据结构课件非常详细 ch5.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章数组和广义表ADTArray{数据对象：D＝{aj1,j2,...,,ji,jn

2、ji=0,...,bi-1,i=1,2,..,n}n是数组的维数，bi是数组第i维的长度数据关系：R＝{R1,R2,...,Rn}Ri＝{

3、0jkbk-1,1kn且ki,0jibi-2,i=2,...,n}基本操作}ADTArray基本操作：InitArray(&A,n,bound1,...,boundn)若维数n和各维长度合法，则构造相应的数组A，返回OKDestroyArray(

4、&A)销毁数组AValue(A,&e,index1,...,indexn)若各下标不超界，e赋值为所指定A的元素值，返回OKAssign(&A,e,index1,...,indexn)若各下标不超界，将e的值赋值给所指定A的元素，返回OK对二维数组，有：数据对象:D={aij

5、0≤i≤b1-1,0≤j≤b2-1}数据关系:R={ROW,COL}ROW={

6、0≤i≤b1-2,0≤j≤b2-1}COL={

7、0≤i≤b1-1,0≤j≤b2-2}数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线

8、性表5.1数组的定义和特点定义数组特点数组结构固定数据元素同构数组运算给定一组下标，存取相应的数据元素给定一组下标，修改数据元素的值()()()()()()()()()5.2数组的顺序存储结构次序约定以行序为主序以列序为主序a00a01……..a0,n-1a10a11……..a1,n-1am-1,0am-1,1……..am-1,n-1………………….Loc(i,j)=Loc(0,0)+(b2×i+j)×L按行序为主序存放am-1,n-1……..am-1,1am-1,0……….a1,n-1……..a11a10a0,n-1…….a01a0001n-1m*n

9、-1n按列序为主序存放am-1,n-1……..a1,n-1a0,n-1……….am-1,1……..a11a01am-1,0…….a10a00a00a01……..a0,n-1a10a11……..a1,n-1am-1,0am-1,1……..am-1,n-1………………….Loc(i,j)=Loc(0,0)+(b1×j+i)×L对于n维数组5.3矩阵的压缩存储对称矩阵a11a12….……..a1na21a22……..…….a2nan1an2……..ann………………….a11a21a22a31a32an1ann…...…...k=01234n(n-1)/2n

10、(n+1)/2-1按行序为主序：三角矩阵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,n-1ann.0a32a33a340………0……………………………Loc(aij)=Loc(a11

11、)+[(3n-5)+(j-1)]×La11a12a21a22a23ann-1ann…...…...k=012343n-2-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）唯一确定稀疏矩阵定义：非零元较零元少，且分布没有一定规律的矩阵压缩存储原则：只存矩阵的行列维数和每个非零元的行列下标及其值稀疏矩阵的压缩存储方法顺序存储结构三元组表#defineMAXSIZE20typedefstruct{inti,j;ElemTyp

12、ee;}Triple;Typedefstruct{Tripledata[MAXSIZE+1];intmu，nu，tu；}TSMatrix；三元组表所需存储单元个数为3(tu+1)其中tu为非零元个数678121213931-3361443245218611564-7maijv012345678ma[0].i,ma[0].j,ma[0].v分别存放矩阵行列维数和非零元个数行列下标非零元值求转置矩阵问题描述：已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表问题分析一般矩阵转置算法：for(col=0;col

13、