第5章 數(shù)組廣義表

第五章數(shù)組廣義表

5.1數(shù)組的類型定義

5.2數(shù)組的順序表示和實(shí)現(xiàn)

5.3矩陣的壓縮存儲(chǔ)

5.4廣義表的類型定義

5.5廣義表的存儲(chǔ)結(jié)構(gòu)**5.6m元多項(xiàng)式的表示**5.7廣義表的遞歸算法1.二維數(shù)組(矩陣)：Amn=a00a01a02...a0,n-1a10a11a12...a1,n-1……………..am-1,0am-1,1am-1,2...am-1,n-1按行劃分:A可看成一個(gè)線性表A=(a0,a1,…,am-1)ai=(ai0,ai0,…,ain-1)按列劃分:A可看成一個(gè)線性表A=(a0,a1,…,an-1)aj=(a0j,a1j,…,am-1,j)5.1數(shù)組的類型定義

一個(gè)二維數(shù)組類型可以定義為其分量類型為一維數(shù)組類型的線性表類型;

同理，一個(gè)n維數(shù)組類型可以定義為其數(shù)據(jù)元素為n-1維數(shù)組類型的線性表類型。

5.1數(shù)組的類型定義ADTArray{

數(shù)據(jù)對(duì)象：ji=0,…,bi-1,i=1,2,…,n,D＝{aj1,j2,…,jn|n稱為數(shù)據(jù)元素的維數(shù)，bi是數(shù)組第i維的長(zhǎng)度，ji

是數(shù)組元素的第i維下標(biāo)，aj1,j2,…,jn∈ElemSet}

數(shù)據(jù)關(guān)系：R＝{R1,R2,...,Rn}

Ri＝{<aj1,...ji,...jn,aj1,...ji+1,...jn>|0jkbk-1,1kn且ki,0ji

bi-2,aj1,...ji,...jn,aj1,...ji+1,...jn∈D,i=2,...,n}基本操作}ADTArray

5.1數(shù)組的類型定義基本操作：InitArray(&A,n,bound1,...,boundn)DestroyArray(&A)Value(A,&e,index1,...,indexn)Assign(&A,e,index1,...,indexn)***5.1數(shù)組的類型定義1、數(shù)組元素的地址關(guān)系

以二維數(shù)組為例說(shuō)明。對(duì)于二維數(shù)組有兩種存儲(chǔ)方式：(1)以行序?yàn)橹鞯拇鎯?chǔ)方式;(2)以列序?yàn)橹鞯拇鎯?chǔ)方式。a00a01a02a03a10a11

a12

a13a20a21a22a23a00a01a02a03a10a11

a12

a13a20a21a22a23第7個(gè)位置第8個(gè)位置

假如a00的起始地址是loc(a00),數(shù)組中每一個(gè)元素所占空間為L(zhǎng),a12的起始地址怎么計(jì)算：行序：loc(a12)=loc(a00)+[(1×4)+2]×L

列序：loc(a12)=loc(a00)+[(2×3)+1]×L5.2數(shù)組的順序表示和實(shí)現(xiàn)以行序?yàn)橹餍虻拇鎯?chǔ)結(jié)構(gòu)的元素位置確定給定數(shù)組A[b1][b2],每個(gè)元素所占空間為L(zhǎng),a00的起始地址記為loc(0,0),aij的起始地址為：

LOC[i,j]=LOC[0,0]+(b2i+j)LA[b1][b2][b3]3維數(shù)組的數(shù)據(jù)元素aijk的存儲(chǔ)位置：

LOC(i,j,k)=LOC(0,0,0,)+(b2b3i+b3j+k)L5.2數(shù)組的順序表示和實(shí)現(xiàn)A[b1][b2]...[bn]n維數(shù)組的數(shù)據(jù)元素存儲(chǔ)位置：LOC(j1,j2,…jn)=LOC(0,0,…,0)+(b2…bnj1+b3…bnj2+…+bnjn-1+jn)L

5.2數(shù)組的順序表示和實(shí)現(xiàn)#include<stdarg.h>//標(biāo)準(zhǔn)頭文件，提供宏va_start、

//va_arg和va_end,用于存放變長(zhǎng)參數(shù)表#defineMAX_ARRAY_DIM8//數(shù)組維數(shù)typedefstruct{Elemtype*base;//基址

intdim;//維數(shù)

int*bound;//數(shù)組維界基址

int*constants;//數(shù)組映像函數(shù)常量基址}Array;5.2數(shù)組的順序表示和實(shí)現(xiàn)StatusInitArray(Array&A,intdim,…){

if(dim<1||dim>MAX_ARRAY_DIM)returnERROR;A.dim=dim;A.bounds=(int*)malloc(dim*sizeof(int));if(!A.bounds)exit(OVERFLOW);elemtotal=1;va.start(ap,dim);//ap為va_list類型，是存放變長(zhǎng)參數(shù)表信息的數(shù)組

for(i=0;i<dim;++i){A.bounds[i]=va.arg(ap,int);if(A.bounds[i]<0)returnUNDERFLOW;Elemtotal*=A.bound[i];}va.end(ap);5.2數(shù)組的順序表示和實(shí)現(xiàn)A.base=(ElemType*)malloc(elemtotal*sizeof(ElemType));if(!A.base)exit(OVERFLOW);A.constants=(int*)malloc(dim*sizeof(int));if(!A.constants)exit(OVERFLOW);A.constants[dim-1]=1;for(i=dim-2);i>=0;--i)A.constants[i]=A.bounds[i+1]*A.constants[i+1];returnOK;}***5.2數(shù)組的順序表示和實(shí)現(xiàn)5.3矩陣的壓縮存儲(chǔ)

5.3.1特殊矩陣5.3.2稀疏矩陣5.3.3矩陣的壓縮存儲(chǔ)下(上)三角矩陣與對(duì)稱矩陣A

1

00022

00453036781

23522

46343

75678下三角矩陣對(duì)稱矩陣用一維數(shù)組存儲(chǔ)sa[n*(n+1)/2]當(dāng)i>=j時(shí)aij對(duì)應(yīng)存儲(chǔ)在A[i(i-1)/2+j-1]***5.3.1特殊矩陣假設(shè)

m行n列的矩陣含

t個(gè)非零元素，則稱為稀疏因子。通常認(rèn)為

0.05的矩陣為稀疏矩陣。何謂稀疏矩陣？5.3.2稀疏矩陣ADTSparseMatrix{

數(shù)據(jù)對(duì)象：D＝{aij|i=1,2,…,m;j=1,2,…,n;aij∈ElemSet,m,n分別為行數(shù)與列數(shù)}

數(shù)據(jù)關(guān)系：R＝{Row,Col}

Row＝{<ai,j,ai,j+1>|i=1,…,m,j=1,…,n-1}Col＝{<ai,j,ai+1,j>|i=1,…,m-1,j=1,…,n}基本操作}ADTArray

5.3.2稀疏矩陣基本操作：CreatSMatrix(&M)DestroyArray(&M)……………..MultSMatrix(M,N,&Q)TransposeSMatrix(M,&T)5.3.2稀疏矩陣隨機(jī)稀疏矩陣的壓縮存儲(chǔ)方法:1、三元組順序表2、行邏輯聯(lián)接的順序表3、十字鏈表5.3.2稀疏矩陣

數(shù)組的表示方法稀疏矩陣0

1

000000

2

01

0000((1，2，1)，(2，4，2)，(3，1，1))5.3.3矩陣的壓縮存儲(chǔ)

#defineMAXSIZE12500typedefstruct{

inti,j;

//該非零元的行下標(biāo)和列下標(biāo)

ElemTypee;

//該非零元的值

}Triple;//

三元組類型三元組順序表typedefstruct{

Tripledata[MAXSIZE+1];//data[0]未用

intmu,nu,tu;

}TSMatrix;

//稀疏矩陣類型5.3.3矩陣的壓縮存儲(chǔ)如何求轉(zhuǎn)置矩陣？5.3.3矩陣的壓縮存儲(chǔ)用常規(guī)的二維數(shù)組表示時(shí)的算法其時(shí)間復(fù)雜度為？

O(mu×nu)

for(col=1;col<=nu;++col)for(row=1;row<=mu;++row)T[col][row]=M[row][col];5.3.3矩陣的壓縮存儲(chǔ)用“三元組”表示時(shí)如何實(shí)現(xiàn)？121415-522-731363428211451-522-7133643285.3.3矩陣的壓縮存儲(chǔ)用“三元組”表示時(shí)如何實(shí)現(xiàn)？121415-522-731363428211451-522-7133643285.3.3矩陣的壓縮存儲(chǔ)StatusTransposeSMatrix(TSMatrixM,TSMatrix&T){intp,q,col;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;}//Transpose5.3.3矩陣的壓縮存儲(chǔ)

分析算法TransposeSMatrix的時(shí)間復(fù)雜度：時(shí)間復(fù)雜度為:O(M.nu*M.tu)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;}5.3.3矩陣的壓縮存儲(chǔ)算法改進(jìn)：121415-522-7313634281336211422-7432851-5for(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;}分析時(shí)間復(fù)雜性5.3.3矩陣的壓縮存儲(chǔ)算法改進(jìn)：121415-522-7313634281336211422-7432851-5

設(shè)置num和cpot兩個(gè)向量。num[col]表示矩陣M中第col列中有幾個(gè)非零元，cpot[col]指示M中第col列的第一個(gè)非零元在b.data中的恰當(dāng)位置。

cpot[1]=1cpot[col]=cpot[col-1]+num[col-1]5.3.3矩陣的壓縮存儲(chǔ)算法改進(jìn)：121415-522-7313634281336211422-7432851-5col12345Num[col]12011Cpot[col]124455.3.3矩陣的壓縮存儲(chǔ)StatusFastTransposeSMatrix(TSMatrixM,TSMatrix&T){intcol,t,p,q;intnum[20],cpot[20];T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){for(col=1;col<=M.nu;++col)num[col]=0;for(t=1;t<=M.tu;++t)//求M中每一列所含非零元的個(gè)數(shù)

++num[M.data[t].j];5.3.3矩陣的壓縮存儲(chǔ)cpot[1]=1;//求M中每一列的第一個(gè)非零元在b.data中的序號(hào)

for(col=2;col<=M.nu;++col)cpot[col]=cpot[col-1]+num[col-1];for(p=1;p<=M.tu;++p){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];}//for}//ifreturnOK;}//FastTransposeSMatrix5.3.3矩陣的壓縮存儲(chǔ)

分析算法FastTransposeSMatrix的時(shí)間復(fù)雜度：時(shí)間復(fù)雜度為:O(M.nu+M.tu)for(col=1;col<=M.nu;++col)……for(t=1;t<=M.tu;++t)……for(col=2;col<=M.nu;++col)……for(p=1;p<=M.tu;++p)……5.3.3矩陣的壓縮存儲(chǔ)三元組順序表又稱有序的雙下標(biāo)法，它的特點(diǎn)是，非零元在表中按行序有序存儲(chǔ)，因此便于進(jìn)行依行順序處理的矩陣運(yùn)算。然而，若需隨機(jī)存取某一行中的非零元，則需從頭開始進(jìn)行查找。行邏輯聯(lián)接的順序表5.3.3矩陣的壓縮存儲(chǔ)

#defineMAXRC500typedefstruct{Tripledata[MAXSIZE+1];

intrpos[MAXRC+1];intmu,nu,tu;}RLSMatrix;//行邏輯鏈接順序表類型將上節(jié)快速轉(zhuǎn)置矩陣的算法中創(chuàng)建的指示“行”信息的輔助數(shù)cpot固定在稀疏矩陣的存儲(chǔ)結(jié)構(gòu)中。5.3.3矩陣的壓縮存儲(chǔ)兩個(gè)矩陣相乘的經(jīng)典算法

Q=M×NM是m1×n1,N是n1×n2,Q是m1×n2矩陣乘法的精典算法: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í)間復(fù)雜度為？

O(m1×n2×n1)5.3.3矩陣的壓縮存儲(chǔ)

稀疏矩陣相乘×＝5.3.3矩陣的壓縮存儲(chǔ)

ije11314522-1312

ije12221131-2324

ije12621-1324row1234rpos[row]1245row1234rpos[row]13455.3.3矩陣的壓縮存儲(chǔ)

StatusMultSMatrix(RLSMatrixM,RLSMatrixN,RLSMatrix&Q){intarow,brow,p,q,t,ctemp[30],l,ccol,tp;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是非零矩陣5.3.3矩陣的壓縮存儲(chǔ)

{for(arow=1;arow<=M.mu;++arow){for(l=1;l<=M.nu;++l)ctemp[l]=0;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){//對(duì)當(dāng)前行中每一個(gè)非零元

brow=M.data[p].j;//找到對(duì)應(yīng)元在N中的行號(hào)

if(brow<N.mu)t=N.rpos[brow+1];elset=N.tu+1;5.3.3矩陣的壓縮存儲(chǔ)for(q=N.rpos[brow];q<t;++q){ccol=N.data[q].j;//乘積元素在Q中列號(hào)

ctemp[ccol]+=M.data[p].e*N.data[q].e;}//forq}//求得Q中第crow(=arow)行的非零元5.3.3矩陣的壓縮存儲(chǔ)for(ccol=1;ccol<=Q.nu;++ccol)//壓縮存儲(chǔ)該行非零元

if(ctemp[ccol]){if(++Q.tu>MAXSIZE)returnERROR;Q.data[Q.tu].i=arow;Q.data[Q.tu].j=ccol;Q.data[Q.tu].e=ctemp[ccol];}//if}//forarow}//ifreturnOK;}//MultSMatrix5.3.3矩陣的壓縮存儲(chǔ)分析上述算法的時(shí)間復(fù)雜度累加器ctemp初始化的時(shí)間復(fù)雜度為(M.muN.nu)，求Q的所有非零元的時(shí)間復(fù)雜度為(M.tuN.tu/N.mu)，進(jìn)行壓縮存儲(chǔ)的時(shí)間復(fù)雜度為(M.muN.nu)，總的時(shí)間復(fù)雜度就是(M.muN.nu+M.tuN.tu/N.mu)。5.3.3矩陣的壓縮存儲(chǔ)分析上述算法的時(shí)間復(fù)雜度若M是m行n列的稀疏矩陣，N是n行p列的稀疏矩陣，則M中非零元的個(gè)數(shù)

M.tu=Mmn，

N中非零元的個(gè)數(shù)

N.tu=Nnp，相乘算法的時(shí)間復(fù)雜度就是

(mp(1+nMN))

，當(dāng)M<0.05和N<0.05及n<1000時(shí)，相乘算法的時(shí)間復(fù)雜度就相當(dāng)于

(mp)。***5.3.3矩陣的壓縮存儲(chǔ)十字鏈表30050-100200011314522-1312^^^^^^^5.3.3矩陣的壓縮存儲(chǔ)typedefstructOLNode{inti,j;ElemTypee;StructOLNode*right,*down;}OLNode;*OLink;typedefstruct{OLink*rhead,*chead;intmu,nu,tu;}CrossList;5.3.3矩陣的壓縮存儲(chǔ)十字鏈表StatusCreateSMatrix_OL(CrossList&M){if(M)free(M);scanf(&m,&n,&t);M.mu=m;M.nu=n;M.tu=t;if(!(M.rhead=(OLink*)malloc((m+1)*sizeof(OLink))))returnERROR;if(!(M.chead=(OLink*)malloc((n+1)*sizeof(OLink))))returnERROR;for(inta=1;a<=m;a++)M.rhead[a]=NULL;for(intb=1;b<=n;b++)M.chead[b]=NULL;5.3.3矩陣的壓縮存儲(chǔ)十字鏈表for(intc=1;c<=t;c++){//按任意次序輸入非零元

scanf(&i,&j,&e);if(!(p=(OLNode*)malloc(sizeof(OLNode))))returnERROR;p->i=i;p->j=j;p->e=e;p->down=NULL;p->right=NULL;//新結(jié)點(diǎn)

if(M.rhead[i]==NULL||M.rhead[i]->j>j){p->right=M.rhead[i];M.rhead[i]=p;}5.3.3矩陣的壓縮存儲(chǔ)十字鏈表else{for(q=M.rhead[i];(q->right)&&(q->right->j<j);q=q->right);p->right=q->right;q->right=p;}//完成行插入

if(M.chead[j]==NULL||M.chead[j]->i>i){p->down=M.chead[j];M.chead[j]=p;}else{//尋查在列表中的插入位置

for(q=M.chead[j];(q->down)&&q->down->i<i;q=q->down);p->down=q->down;q->down=p;}//完成列插入

}//forreturnOK;}//CreateSMatrix_OL5.3.3矩陣的壓縮存儲(chǔ)十字鏈表(董事長(zhǎng)、總經(jīng)理、秘書、人事部、分公司....)(總經(jīng)理、秘書、人事部、分公司....)5.4廣義表的類型定義

廣義表是線性表的推廣，也稱列表（Lists）。

1.定義

廣義表是n個(gè)元素的有限序列，記作

A=（a1,a2,……an)

其中A是表名，n是廣義表的長(zhǎng)度，ai是廣義表的元素，它可以是單個(gè)元素，也可以是廣義表。原子：

如果ai是單個(gè)元素，稱為原子，用小寫字母表示;

子表：

如果ai是廣義表，稱為子表，用大寫字母表示。5.4廣義表的類型定義

1.定義

廣義表是n個(gè)元素的有限序列，記作

A=（a1,a2,……an)

表頭（Head）：非空廣義表的第一個(gè)元素a1;

表尾（Tail）：除了表頭的其余元素組成的表;

深度：廣義表中括號(hào)嵌套的最大層數(shù)。

2.特點(diǎn)存儲(chǔ)空間難以確定，常采用鏈?zhǔn)酱鎯?chǔ)。5.4廣義表的類型定義ADTGlist{

數(shù)據(jù)對(duì)象：D＝{ei|i=1,2,..,n;n≥0;ei∈AtomSet或ei∈GList,AtomSet為某個(gè)數(shù)據(jù)對(duì)象}

數(shù)據(jù)關(guān)系：

LR＝{<ei-1,ei>|ei-1,ei∈D,2≤i≤n}

基本操作：}ADTGlist5.4廣義表的類型定義InitGlist(&L)CreateGlist(&L,S)DestroyGList(&L)CopyGList(&T,L)GListLength(L)GListDepth(L)GetHead(L)GetTail(L)………5.4