第三章 多维数组和广义表.ppt

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

1、第三章多维数组和广义表数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表。例如二维数组()()()()()()()()()3.1多维数组数组的两种顺序存储结构以行序为主序（行优先顺序）以列序为主序（列优先顺序）数组特点数组结构固定数据元素同构数组运算给定一组下标，存取相应的数据元素给定一组下标，修改数据元素的值Loc(aij)=Loc(a11)+[(i-1)*n+(j-1)]*d按行序为主序存放amn……..am2am1……….a2n……..a22a21a1n…….a12a11a11a12……

2、..a1na21a22……..a2nam1am2……..amn………………….若行列下标均从0开始，则Loc(aij)=Loc(a00)+(i*n+j)*dam-1n-1……..am-11am-10……….a1n-1……..a11a10a0n-1…….a01a00按列序为主序存放amn……..a2na1n……….am2……..a22a12am1…….a21a11Loc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*da11a12……..a1na21a22……..a2nam1am2……..amn……

3、…………….am-1n-1……..a1n-1a0n-1……….am-11……..a11a01am-10…….a10a00若行列下标均从0开始，则Loc(aij)=Loc(a00)+(j*m+i)*d3.2矩阵的压缩存储3.2.1特殊矩阵1.对称矩阵a00a01….……..a0n-1a10a11……..…….a1n-1an-10an-11……..an-1n-1………………….k=012345n(n-1)/2n(n+1)/2-1按行序为主序：0≤i

4、22…….an-1,0……..an-1,n-12.三角矩阵(下三角)a00cc……..ca10a11c……..can-10an-11an-12…….an-1n-1.………………….cLoc(aij)=Loc(a00)+[i(i+1)/2+j]*d共占用n(n+1)/2+1个单元按行序为主序：k=012345n(n-1)/2n(n+1)/2-1a00a10a11a20a21a22…….an-1,0……..an-1,n-1c三角矩阵(上三角)a00a01a02……....a0,n-1ca11a12…….a1,n-1

5、cccan-1,n-1………………..……….Loc(aij)=Loc(a00)+[i(2n-i+1)/2+j-i]*d按行序为主序：k=012n-1n(n+1)/2-1n(n+1)/2共占用n(n+1)/2+1个单元前i行上三角元素个数：n+(n-1)+….(n-i+1)=i(n+n-i+1)/2=i(2n-i+1)/2a00a01a02…..a0n-1a11a12….an-1n-1c3对角矩阵a00a010……………..0a10a11a120……………000…an-2,n-3an-2,n-2an-2,n-1

6、00……an-1,n-2an-1,n-10a21a22a230………0……………………………按行序为主序：k=012345673(n-1)-13(n-1)a00a01a10a11a12a21a22a23……..an-1,n-2an-1,n-13.2.2特殊矩阵的抽象数据类型ADTSpecialMatrixisData:特殊矩阵线性表Ｍ＝（a1,……an,an+1),Matrix为类型描述符Operations:voidInitMatrix(Matrix&m,inttype,intn);//初始化ElemType

7、GetMatrixElem(Matrixm,inti,intj);//取元素VoidSetMatrixElem(Matrix&m,inti,intj,ElemTypev);//赋元素值VoidClearMatrix(Matrix&m);清除特殊矩阵endSpecialMatrixstructMatrix//特殊矩阵线性表数据类型{ElemType*data;//定义线性表向量指针inttype,size;//特殊矩阵类型和规模};//type=1对称矩阵；type=2下三角矩阵；type=3上三角矩阵3.2.3

8、特殊矩阵基本算法描述voidInitMatrix(Matrix&m,inttype,intsize);//初始化{introw,col,value,n=size(size+1)/2;m.type=type;m.size=size;m.data=newElemType[n+1];for(inti=0;i>row>>col>>value;SetMatrixElem(