《數(shù)據(jù)結(jié)構(gòu)與算法》第5章數(shù)組和廣義表

第5章數(shù)組和廣義表5.1數(shù)組的定義5.2數(shù)組的順序表示和實現(xiàn)5.3矩陣的壓縮存儲5·4廣義表5.5廣義表的存儲結(jié)構(gòu)5.1數(shù)組的定義說明：

A是數(shù)組的名字

A是一個n維數(shù)組，共有

bi個元素

bi是第i維的長度，稱為維界，表示該維的下標(biāo)變化為0∽bi-1

每一個數(shù)組元素的類型都是int

除第一個元素外，每個元素都有一個直接前驅(qū)

除最后一個元素外，每個元素都有一個直接后繼在C中定義：intA[b1][b2]…..[bn];因此，可以把數(shù)組看成是一個定長的線性表，表中每個元素也可以是一個定長的線性表，…...1.給定一組下標(biāo)，存取或修改相應(yīng)元素的值2.查找滿足條件的數(shù)組元素3.對數(shù)組元素進(jìn)行排序數(shù)組的使用：數(shù)組元素數(shù)組的ADTADTArray{數(shù)據(jù)對象：D={aj1j2….jn|n(>0)稱為數(shù)組的維數(shù)，

bi是數(shù)組的第i維的長度

ji是數(shù)組元素的第i維下標(biāo)，ji=0,…,bi-1,1≤i≤naj1j2….jn∈ElemSet}

數(shù)據(jù)關(guān)系：R={R1,R2,….,Rn}Ri={<aj1…ji….jn，aj1…ji+1...jn>|0≤jk≤bk-1,1≤k≤n且k≠i,0≤ji≤bi-2,aj1…ji….jn，aj1…ji+1...jn∈D,i=1,2,…,n}根本操作：InitArray(&A,n,bound1,…,boundn)操作結(jié)果：假設(shè)維數(shù)n和各維長度合法，那么構(gòu)造相應(yīng)的數(shù)組A，并返回OK。DestroyArray(&A)操作結(jié)果：銷毀數(shù)組A。Value(A,&e,index1,…,indexn)初始條件：A是n維數(shù)組，e為元素變量，隨后是n個下標(biāo)值。操作結(jié)果：假設(shè)各下標(biāo)不超界，那么e賦值為指定的A的元素值，并返回OK。Assign(&A,e,index1,…,indexn)初始條件：A是n維數(shù)組，e為元素變量，隨后是n個下標(biāo)值。操作結(jié)果：假設(shè)各下標(biāo)不超界，那么將e的值賦給指定的A的元素，并返回OK。}ADTArray5.2數(shù)組的順序表示和實現(xiàn)行序：越是后面的下標(biāo)變化越快列序：越是前面的下標(biāo)變化越快數(shù)組一旦定義，可由下標(biāo)知道任意元素的位置一維：Loc[i]=Loc[0]+i*h

//h為每個元素占用的存儲單元長度h

h

h

hh

hhh

h

h0123456789二維：Loc[i,j]=Loc[0,0]+(b2*i+j)*h三維：Loc[i,j,k]=Loc[0,0,0]+(b2*b3*i+b3*j+k)*h下標(biāo)i

下標(biāo)

i下標(biāo)j

下標(biāo)

j

下標(biāo)

kn維：Loc[j1,j2,….,jn]=Loc[0,0,…,0]+(b2*b3*…*bn*j1+b3*b4*…*bn*j2+….+bn*jn-1+jn)*h令C1=b2*b3*…*bn*hC2=b3*b4*….*bn*h……..Cn-1=bn*hCn=hLoc[j1,j2,….jn]=Loc[0,0,…,0]+

ji*CiCi=Ci+1*bi+1函數(shù)中可變個數(shù)參數(shù)的使用方法：//實例：printf(*format,……)1.參加相關(guān)的頭文件#include<stdarg.h>2.定義指向第一個可變參數(shù)的指針typedefvoid*va_list;3.利用最后一個固定參數(shù)找到第一個可變參數(shù)voidva_start(va_listargptr,last_parm)//最后一個固定參數(shù)名為last_parm//argptr指向變長參數(shù)表中的第一個參數(shù)4.依次找到下一個可變參數(shù)typeva_arg(va_listargptr,type)//返回argptr指向的type類型的參數(shù)，argptr指向下一個參數(shù)5.指針懸空〔不指向任何地方〕voidva_end(va_listargptr)//-----數(shù)組的順序存儲表示-----

#include<stdarg.h>

//標(biāo)準(zhǔn)頭文件，提供宏va_start、va_arg和va_end//用于存取變長參數(shù)表#defineMAX_ARRAY_DIM8

//假設(shè)數(shù)組維數(shù)的最大值為8typedefstruct{ElemType*base;//數(shù)組元素基址,由InitArray分配

intdim//數(shù)組維數(shù)

int*bounds;//數(shù)組維界基址,由InitArray分配,biint*constants

//數(shù)組映象函數(shù)常量基址，由InitArray分配,ci}Array;//-----根本操作函數(shù)原型說明-----StatusInitArray(Array&A,intdim,…);//假設(shè)維數(shù)dim和隨后的各維長度合法，那么構(gòu)造相應(yīng)的數(shù)組A，并返回OK。StatusDestroyArray(Array&A);//銷毀數(shù)組A。StatusValue(ArrayA,ElemType&e,…);//A是n維數(shù)組，e為元素變量，隨后是n個下標(biāo)值。//假設(shè)各下標(biāo)不超界，那么e賦值為指定的A的元素值，并返回OK。StatusAssign(Array&A,ElemTypee,…);//A是n維數(shù)組，e為元素變量，隨后是n個下標(biāo)值。//假設(shè)各下標(biāo)不超界，那么將e的值賦給指定的A的元素，并返回OK。//-----根本操作的算法描述-----StatusInitArray(Array&A,intdim,…);1.獲得dim2.申請空間存放bi的值4.計算數(shù)組元素個數(shù)elemtotal3.獲得bi的值5.申請空間存放A中所有元素的值6.申請空間存放Ci的值存放bici的值給A分配存儲空間//-----根本操作的算法描述-----StatusInitArray(Array&A,intdim,…){//假設(shè)維數(shù)dim和各維長度合法，那么構(gòu)造相應(yīng)的數(shù)組A，并返回OK。if(dim<1||dim>MAX_ARRAY_DIM)returnERROR;A.dim=dim;A.bounds=(int*)malloc(dim*sizeof(int));if(!A.bounds)exit(OVERFLOW);//假設(shè)各維長度合法，那么存入A.bounds,并求出A的元素總數(shù)elemtotalelemtotal=1;va_start(ap,dim);//ap為va_list類型，是存放變長參數(shù)表信息的數(shù)組for(i=0;i<dim;++i){A.bounds[i]=va_arg(ap,int);if(A.bounds[i]<0)returnUNDERFLOW;elemtotal*=A.bounds[i];}va_end(ap);A.base=(ElemType*)malloc(elemtotal*sizeof(ElemType));if(!A.base)exit(OVERFLOW);

//求映象函數(shù)的常數(shù)Ci,A.constants[i-1],i=1,…,dimA.constants=(int*)malloc(dim*sizeof(int));if(!A.constants)exit(OVERFLOW);A.constants[dim-1]=1;//h=1,指針的增減以元素的大小為單位

for(i=dim-2;i>=0;--i)A.constants[i]=A.bounds[i+1]*A.constants[i+1];returnOK;}StatusDestroyArray(Array&A){//銷毀數(shù)組Aif(!A.base)returnERROR;

free(A.base);A.base=NULL;if(!A.bounds)returnERROR;

free(A.bounds);A.bounds=NULL;if(!A.constants)returnERROR;

free(A.constants);A.constants=NULL;returnOK;}StatusLocate(ArrayA,va_listap,int&off){//假設(shè)ap指示的各下標(biāo)值合法，//那么求出該元素在A中的相對地址offoff=0;for(i=0;i<A.dim;++i){ind=va_arg(ap,int);if(ind<0||ind>=A.bounds[i])returnOVERFLOW;off+=A.constants[i]*ind;}returnOK;}StatusValue(ArrayA,ElemType&e,…){//A是n維數(shù)組，e為元素變量，隨后是n個下標(biāo)值。//假設(shè)各下標(biāo)不超界，那么將e的值賦給指定的A的元素，并返回OK。va_start(ap,e);if((result=Locate(A,ap,off))<=0)returnresult;e=*(A.base+off);returnOK;}StatusAssign(Array&A,ElemTypee,…){//A是n維數(shù)組，e為元素變量，隨后是n個下標(biāo)值。//假設(shè)各下標(biāo)不超界，那么將e的值賦給指定的A的元素，并返回OK。va_start(ap.e);if((result=Locate(A,ap,off))<=0)returnresult;*(A.base+off)=e;returnOK;}5.3矩陣的壓縮存儲一、特殊矩陣1．對稱矩陣

n階矩陣滿足：aij=aji

a11a12a13a14a15a16

a21a22a23a24a25a26

a31a32a33a34a35a36

a41a42a43a44a45a46

a51a52a53a54a55a56a61a62a63

a64a65a66a11a12a13a14a15a16

a21a22a23a24a25a26

a31a32a33a34a35a36

a41a42a43a44a45a46

a51a52a53a54a55a56a61a62a63

a64a65a66將n2個矩陣元素壓縮存儲到n(n+1)/2個存儲單元中a[1..n2]與sa[0..n(n+1)/2-1]的對應(yīng)關(guān)系?a11a21a22a31a32a33a41a42a43a44

a51a52a53a54a55a61a62a63

a64a65

a66A中任意一元素aij與sa[k]之間存在對應(yīng)關(guān)系:k=i

(i-1)/2+j-1當(dāng)i≥j時j

(j-1)/2+i-1當(dāng)i<j時2．對角矩陣帶寬為2b+1的帶狀矩陣當(dāng)0

i,j

n-1且|i-j|>b時ai,j=0帶狀區(qū)域中共有(2b+1)n-b(b+1)個元素a11a12

a21a22a23

an-1,nan,n-1an,n0元素非0元素0元素bb存儲方法：除去第一行和最后一行，每行都存放2b+1個元素整個帶狀矩陣放在(2b+1)n-2b個單元中，增補(bǔ)了b(b-1)個元素，增補(bǔ)的方法是以對角線為中心,左右各b個元素,缺乏補(bǔ)齊Loc(a[i][i])=Loc(a[i-1][i-1])+(2b+1)h=Loc(a[0][0])+(2b+1)*i*hLoc(a[i][j])=Loc(a[i][i])+(j-i)*h=Loc(a[0][0])+(2bi+j)h例：b=1,n=61,11,22,12,22,33,23,33,44,34,44,55,45,55,66,56,61,1 1,2 2,1 2,2 2,3 3,2 3,3 3,44,3 4,4 4,5 5,4 5,5 5,6 6,5 6,6例：b=2,n=61,11,21,32,12,22,32,43,13,23,33,43,54,24,34,44,54,65,35,45,55,66,46,56,61,11,21,32,12,22,32,43,13,23,33,43,54,24,34,4 4,54,65,35,4 5,55,6 6,46,56,6非零元比零元少，且分布沒有規(guī)律

=t/(m*n)

0.05二、稀疏矩陣

(SparseMatrix)行數(shù)m=6,列數(shù)n=7,非零元素個數(shù)t=6

1·稀疏矩陣的ADTADTSpareMatrix{數(shù)據(jù)對象：D={aij|i=1,2,…,m;j=1,2,…,n;ai,j∈ElemSet,m和n分別稱為矩陣的行數(shù)和列數(shù)}數(shù)據(jù)關(guān)系：R={Row,Col}Row={<ai,j,ai,j+1>|1≤i≤m,1≤j≤n-1}Col={<ai,j,ai+1,j>|1≤i≤m-1,1≤j≤n}根本操作：CreateSMatrix(&M);操作結(jié)果：創(chuàng)立稀疏矩陣M。DestroySMatrix(&M);初始條件：稀疏矩陣M存在。操作結(jié)果：銷毀稀疏矩陣M。

PrintSMatrix(M);

初始條件：稀疏矩陣M存在。操作結(jié)果：輸出稀疏矩陣M。

CopySMatrix(M,&T);

初始條件：稀疏矩陣M存在。操作結(jié)果：由稀疏矩陣M復(fù)制得到T。

AddSMatrix(M,N,&Q);

初始條件：稀疏矩陣M與N的行數(shù)和列數(shù)對應(yīng)相等。操作結(jié)果：求稀疏矩陣的和Q=M+N。

SubSMatrix(M,N,&Q);

初始條件：稀疏矩陣M與N的行數(shù)和列數(shù)對應(yīng)相等。操作結(jié)果：求稀疏矩陣的差Q=M-N。MulSMatrix(M,N,&Q);

初始條件：稀疏矩陣M的列數(shù)等于N的行數(shù)。操作結(jié)果：求稀疏矩陣的積Q=M*N。

TransposeMatrix(M,&T);

初始條件：稀疏矩陣M存在。操作結(jié)果：求稀疏矩陣M的轉(zhuǎn)置疏矩T。}ADTSparseMatrix2·稀疏矩陣的壓縮存儲用一個三元組(i,j,aij)表示矩陣中的一個非零元再加上行數(shù)m和列數(shù)n就可以唯一確實定一個稀疏矩陣0 12 9 0 0 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 0 15 0 0 -7 0 0 0三元組表((1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7))稀疏矩陣〔1〕三元組順序表用順序結(jié)構(gòu)表示三元組，以行序為主序//-----稀疏矩陣的三元組順序表存儲表示-----#defineMAXSIZE12500//假設(shè)非零元素個數(shù)的最大值為12500typedefstruct{inti,j;//該非零元素的行下標(biāo)和列下標(biāo)ElemTypee;}Triple；typedefstruct{Tripledata[MAXSIZE+1];//非零元素三元組表，data[0]未用intmu,nu,tu;//矩陣的行數(shù)、列數(shù)和非零元素個數(shù)}TSMatrix;((1,3,-3),(1,6,15),(2,1,12),(2,5,18),(3,1,9),(3,4,24),(4,6,-7),(6,3,14))矩陣轉(zhuǎn)置01290 00 0 00 0 0 00 0 -30 0 0 0140 00 24 0 00 0 018 0 0 00 0 1500 -7 000三元組表((1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7))StatusTransposeSMatrix(TSMatrixM,TSMatrix&T){//采用三元組表存儲表示，求稀疏矩陣M的轉(zhuǎn)置疏矩T。

T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){q=1;for(col=1;col<=M.nu;++col)for(p=1;p<=M.tu;++p)if(M.data[p].j==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;++q;

}

}returnOK;}//TransposeMatrix應(yīng)確切知道轉(zhuǎn)置前每一列的第一個非零元在T中的位置用num[col]表示M中第col列中非零元的個數(shù)

cpos[col]表示M中第col列的第一個非零元在T的位置按三元組的順序進(jìn)行轉(zhuǎn)置col 1 2 3 4 5 6 7 num[col] 2 2 2 1 0 1 0 cpos[col] 1 3 5 7 8 8 9 01290 00 0 00 0 0 00 0 -30 0 0 0140 00 24 0 00 0 018 0 0 00 0 1500 -7 000((1,3,-3),(1,6,15),(2,1,12),(2,5,18),(3,1,9),(3,4,24),(4,6,-7),(6,3,14))((1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7))StatusFastTransposeSMatrix(TSMatrixM,TSMatrix&T){//采用三元組表存儲表示，求稀疏矩陣M的轉(zhuǎn)置疏矩T。

T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){q=1;for(col=1;col<=M.nu;++col)num[col]=0;for(t=1;t<=M.tu;++t)++num[M.data[t].j];

//求M中每一列含非零元素個數(shù)

cpos[1]=1;for(col=2;col<=M.nu;++col)

//求第col列中第一個非零元素在T.data中的序號

cpos[col]=cpos[col-1]+num[col-1];for(p=1;p<=M.tu;++p){col=M.data[p].j;q=cpos[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;++cpos[col];}}returnOK;}//FastTransposeMatrix〔2〕行邏輯鏈接的順序表兩個矩陣相乘的一般方法：for(i=1;i<=m1;++i)for(j=1;j<=n2;++j){Q[i][j]=0;for(k=1;k<=n1;++k)Q[i][j]+=M[i][k]*N[k][j];}假設(shè)M和N都是稀疏矩陣，那么M[i][k]和N[k][j]中有一個是零，就不用相乘，因此，實際是M中的三元組的j與N中三元組的i相同才相乘因而要記錄矩陣中每一行的第一個非零元和最后一個非零元在三元組中的位置行邏輯順序表類型typedefstruct{Tripledata[MAXSIZE+1];//非零元素三元組表

intrpos[MAXRC+1];//各行第一個非零元素的位置表

intmu,nu,tu;//矩陣的行數(shù)、列數(shù)和非零元素個數(shù)}RLSMatrix;30 050-10 020 0 0M.data=((1,1,3),(1,4,5),(2,2,-1),(3,1,2))M.rpos:M.mu=3M.nu=4M.tu=4row 1 2 3 rpos[row] 1 3 4N.data=((1,1,1),(1,2,2),(3,2,4),(4,1,-2))N.rpos: 1 20 00 4-2 0row 1 2 3 4rpos[row] 1 3 3 4N.mu=4N.nu=2N.tu=4可能與(1,1,3)相乘的元素有:(1,1,1)、(1,2,2)存(1,1)、(1,2)可能與(1,4,5)相乘的元素有:(4,1,-2)存(1,1)可能與(3,1,2)相乘的元素有:(1,1,1)、(1,2,2)存(3,1)、(3,2)30 050-10 020 0 0M.data=((1,1,3),(1,4,5),(2,2,-1),(3,1,2))M.rpos:M.mu=3M.nu=4M.tu=4row123 rpos[row] 13 4N.data=((1,1,1),(1,2,2),(3,2,4),(4,1,-2))N.rpos: 1 20 00 4-2 0row 1 2 3 4rpos[row] 1 3 3 4N.mu=4N.nu=2N.tu=4第1行：(1,4,5)

(4,1,-2)30 050-10020 00M.data=((1,1,3),(1,4,5),(2,2,-1),(3,1,2))M.rpos:M.mu=3M.nu=4M.tu=4row123 rpos[row] 13 4N.data=((1,1,1),(1,2,2),(3,2,4),(4,1,-2))N.rpos: 1 20 00 4-2 0row 1 2 3 4rpos[row] 1 3 3 4N.mu=4N.nu=2N.tu=4(1,1,3)(1,1,1)(1,1,3)(1,2,2)Q初始化；if〔Q是非零矩陣〕{//逐行求積for(arow=1;arow<=M.mu;++arow)//處理M的每一行{ctemp[]=0;//累加器清零計算Q中第arow行的積并存入ctemp[]中；將ctemp[]中非零元素壓縮存儲到Q.data;}//forarow}//if兩個稀疏矩陣相乘〔Q=M*N〕的大致過程：StatusMultSMatrix(RLSMatrixM,RLSMatrixN,RLSMatrix&Q){

//求矩陣乘積Q=M*N，采用行邏輯鏈接存儲表示

if(M.nu!=N.mu)returnERROR;Q.mu=M.mu;Q.nu=N.nu;Q.tu=0;

//Q初始化

if(M.tu*N.tu!=0)//Q是非零矩陣

{for(arow=1;arow<=M.mu;++arow)

{//處理M的每一行

ctemp[1..N.nu]=0;

//當(dāng)前行各元素累加器清零

Q.rpos[arow]=Q.tu+1;

if(arow<M.mu)tp=M.rpos[arow+1];elsetp=M.tu+1;for(p=M.rpos[arow];p<tp;++p)

{

//對當(dāng)前行中每一個非零元素

brow=M.data[p].j;

//找到對應(yīng)元素在N中的行號

if(brow<N.mu)t=N.rops[brow+1];elset=N.tu+1;for(q=N.rpos[brow];q<t;++q){ccol=N.data[q].j

//乘積元素在Q中的列號

ctemp[ccol]+=M.data[p].e*N.data[q].e}//forq

}//求得Q中第arow行的非零元素for(ccol=1;ccol<=Q.nu;++ccol)

//壓縮存儲該行非零元素

if(ctemp[ccol]){if(++Q.tu>MAXSIZE)returnERROR;Q.data[Q.tu]={arow,ccol,ctemp[ccol]};}//if}//forarow}//ifreturnOK;}//MultSMatrix〔3〕十字鏈表當(dāng)稀疏矩陣中非零元的個數(shù)和位置變化較大時，可采用鏈?zhǔn)酱鎯Y(jié)構(gòu):ij edown right同一行的非零元通過right鏈接成一個線性表同一列的非零元通過down鏈接成一個線性表30 0 50-10 020 0 0//-----稀疏矩陣的十字鏈表表示和建立十字鏈表的算法-----typedefstructOLNode{inti,j;//該非零元素的行和列下標(biāo)

ElemTypee;structOLNode*right,*down;//該非零元素所在行表和列表的后繼鏈域}OLNode;*OLink;typedefstruct{OLink*rhead,*chead;//行和列鏈表頭指針向量基址由CreatSMATRIX分配

intmu,nu,tu;//稀疏矩陣的行數(shù)、列數(shù)和非零元素個數(shù)}CrossList;ij edown right5·4廣義表廣義表是線性表的推廣，又稱列表(張三，李四，王五，馬六，......)((張三，...),(李四,王五，....),(馬六,孫七,......),...)

一、廣義表的表示廣義表一般記作：LS=(a1,a2,……,an)

其中：LS為廣義表的名稱，n為廣義表的長度，

ai為廣義表的元素每個元素既可以是單個不可分的元素

-----廣義表LS的原子也可以是一個廣義表

--------廣義表LS的子表一般用大寫字母表示廣義表的名稱，用小寫字母表示原子非空廣義表的第一個元素稱為LS的表頭(head)

其余元素組成的表稱為LS的表尾(tail)1．廣義表是一個多層次的結(jié)構(gòu)2．廣義表可以為其他廣義表所共享3．廣義表可以是一個遞歸的表4．〔〕與〔〔〕〕不同二、廣義表特性例： A=() B=(e) C=(a,(b,c,d)) D=(A,B,C) E=(a,E)長度：01232三、抽象數(shù)據(jù)類型廣義表定義ADTGlist{數(shù)據(jù)對象：D={ei|i=1,2,…,n;n≥0;ei∈AtomSet或ei∈Glist,AtomSet為某個數(shù)據(jù)對象}數(shù)據(jù)關(guān)系：R1={<ei-1,ei>|ei-1,ei∈D,2≤i≤n}根本操作：InitGlist(&L);操作結(jié)果：創(chuàng)立空的廣義表L。CreateGlist(&L,S);初始條件：S是廣義表的書寫形式串。操作結(jié)果：由S創(chuàng)立廣義表L。DestroyGlist(&L);初始條件：廣義表L存在。操作結(jié)果：銷毀廣義表LCopyGlist(&T,L);

初始