數(shù)據(jù)結(jié)構第五章課件數(shù)組和廣義表

數(shù)據(jù)結(jié)構第五章課件數(shù)組和廣義表第1頁，共52頁，2023年，2月20日，星期六5.1.1數(shù)組的定義數(shù)組是大家都已經(jīng)很熟悉的一種數(shù)據(jù)類型，幾乎所有高級語言程序設計中都設定了數(shù)組類型。1．一維數(shù)組一維數(shù)組可以看成是一個線性表或一個向量（第2章已經(jīng)介紹），它在計算機內(nèi)是存放在一塊連續(xù)的存儲單元中，適合于隨機查找。這在第2章的線性表的順序存儲結(jié)構中已經(jīng)介紹。5.1多維數(shù)組的定義第2頁，共52頁，2023年，2月20日，星期六2．二維數(shù)組二維數(shù)組中的每一個元素最多可有兩個直接前驅(qū)和兩個直接后繼（邊界除外），故是一種典型的非線性結(jié)構。例如，設A是一個有m行n列的二維數(shù)組，則A可以表示為：二維數(shù)組可以看成是這樣一個定長的線性表,它的每個數(shù)據(jù)元素也是一個定長的線性表。第3頁，共52頁，2023年，2月20日，星期六二維數(shù)組可以看成是一個線性表A=(a0,a1,……,an-1)其中每個數(shù)據(jù)元素aj是一個列向量形式的線性表A=(a0,a1,……,an-1)第4頁，共52頁，2023年，2月20日，星期六或者,可以看成是一個線性表A=(a0,a1,……,am-1)其中每個數(shù)據(jù)元素aj是一個行向量形式的線性表A=(a0,a1,...am-1)第5頁，共52頁，2023年，2月20日，星期六同理，n維數(shù)組可以看成是這樣一個定長的線性表,它的每個數(shù)據(jù)元素也是n-1維的數(shù)組。n維數(shù)組最多可有n個直接前驅(qū)和n個直接后繼，故n維數(shù)組是一種非線性結(jié)構。3．n維數(shù)組

第6頁，共52頁，2023年，2月20日，星期六數(shù)組的操作數(shù)組一旦被定義，它的維數(shù)和維界就不再改變，因此，除了結(jié)構的初始化和銷毀之外，數(shù)組只有存取元素和修改元素值的操作。第7頁，共52頁，2023年，2月20日，星期六數(shù)組宜采用順序存儲結(jié)構：由于數(shù)組一般不作插入或刪除操作，也就是說，一旦建立了數(shù)組，則結(jié)構中的數(shù)組元素個數(shù)和元素之間的關系就不再發(fā)生變動，即它們的邏輯結(jié)構就固定下來了，不再發(fā)生變化。本章僅重點討論二維數(shù)組的存儲，三維及三維以上的數(shù)組可以作類似分析。5.2數(shù)組順序表示和實現(xiàn)第8頁，共52頁，2023年，2月20日，星期六由于計算機內(nèi)存結(jié)構是一維的（線性的），因此，用一維內(nèi)存存放多維數(shù)組就必須按某種次序?qū)?shù)組元素排成一個線性序列，然后將這個線性序列順序存放在存儲器中。二維數(shù)組的順序存儲有兩種形式:怎樣將數(shù)組中元素存入到計算機內(nèi)存中呢？第9頁，共52頁，2023年，2月20日，星期六1.行優(yōu)先順序a00a01……a0,n-1a10a11……a1,n-1am-1,0am-1,1……am-1,n-1……在BASIC語言、PASCAL語言、C/C++語言等高級語言程序設計中，都是按行優(yōu)先順序存放的?？梢缘贸龆鄋維數(shù)組按行優(yōu)先存放到內(nèi)存的規(guī)律：最左邊下標變化最慢，最右邊下標變化最快，右邊下標變化一遍，與之相鄰的左邊下標才變化一次。a0a1am-1第10頁，共52頁，2023年，2月20日，星期六2.列優(yōu)先順序a00a10……am-1,0a01a11……am-1,

1a0,n-1a1,n-1……am-1,n-1……在FORTRAN語言程序設計中，數(shù)組是按列優(yōu)先順序存放的?？梢缘贸鰊維數(shù)組按行優(yōu)先存放到內(nèi)存的規(guī)律：最左邊下標變化最慢，最右邊下標變化最快，右邊下標變化一遍，與之相鄰的左邊下標才變化一次。a0a1am-1第11頁，共52頁，2023年，2月20日，星期六二維數(shù)組元素存儲位置的計算設二維數(shù)組Am×n的起始地址(基地址),即a00的起始地址為LOC(0,0),每個數(shù)據(jù)元素占L個存儲單元,則A中任一元素aij的起始地址為:行優(yōu)先順序:LOC(i,j)=LOC(0,0)+(i*n+j)*L列優(yōu)先順序:LOC(i,j)=LOC(0,0)+(j*m+i)*L第12頁，共52頁，2023年，2月20日，星期六三維數(shù)組元素存儲位置的計算設三維數(shù)組Am×n×p的起始地址(基地址),即a000的起始地址為LOC(0,0,0),每個數(shù)據(jù)元素占L個存儲單元,則A中任一元素aijk的起始地址為:行優(yōu)先順序:LOC(i,j,k)=LOC(0,0,0)+(i*n*p+j*p*k)*L列優(yōu)先順序:LOC(i,j,k)=LOC(0,0,0)+(k*m*n+j*m+i)*L第13頁，共52頁，2023年，2月20日，星期六所以,數(shù)組元素是其下標的線性函數(shù).由于計算各個元素存儲位置的時間相等,所以存取數(shù)組中任一元素的時間也相等.我們稱具有這一特點的存儲結(jié)構為隨機存儲結(jié)構.第14頁，共52頁，2023年，2月20日，星期六矩陣是一個二維數(shù)組，它是很多科學與工程計算問題中研究的數(shù)學對象。當矩陣的階數(shù)很大時將會占較多存儲單元。而當里面的元素分布呈現(xiàn)某種規(guī)律時，這時，從節(jié)約存儲單元出發(fā)，可考慮若干元素共用一個存儲單元，即進行壓縮存儲。所謂壓縮存儲是指：為多個值相同的元素只分配一個存儲空間，值為零的元素不分配空間。假若值相同的元素或者零元素在矩陣中的分布有一定規(guī)律,則此類矩陣為特殊矩陣;非零元素較零元素少,且分布沒有一定規(guī)律的矩陣,為稀疏矩陣.5.3矩陣的壓縮存儲第15頁，共52頁，2023年，2月20日，星期六1．對稱矩陣若一個n階方陣A中元素滿足下列條件：aij=aji其中1≤i,j≤n，則稱A為對稱矩陣。例如，下圖是一個3*3的對稱矩陣。5.3.1特殊矩陣圖一個對稱矩陣第16頁，共52頁，2023年，2月20日，星期六對稱矩陣的壓縮存儲為每一對對稱元分配一個存儲空間,則可將n2個元壓縮存儲到n(n+1)/2個元的空間中.以行優(yōu)先存儲其下三角(包括對角線)中的元.假設以一維數(shù)組sa[n(n+1)/2]作為n階對稱矩陣A的存儲結(jié)構,則sa[k]和矩陣元素aij存在一一對應關系:K=i(i-1)/2+j-1當i≥jj(j-1)/2+i-1當i<jai1………aij

aiisaa11a21a22a31…an1…annk0123n(n-1)/2n(n+1)/2-1第17頁，共52頁，2023年，2月20日，星期六所謂下(上)三角矩陣中接線員矩陣的上(下)三角(不包括)對角線)中的無均為常數(shù)c或零的n階矩陣.與對稱矩陣類似,除了只存儲其下(上)三角中的元之個外,再加一個存儲常數(shù)C的存儲空間即可.2．三角矩陣第18頁，共52頁，2023年，2月20日，星期六（a）上三角矩陣b）下三角矩陣圖5.2三角矩陣第19頁，共52頁，2023年，2月20日，星期六所有的非零元都集中在以主對角線為中心的帶狀區(qū)域中的矩陣.如:三對角矩陣3．對角矩陣(帶狀矩陣)第20頁，共52頁，2023年，2月20日，星期六在實際應用中，我們還經(jīng)常會遇到一類矩陣：其矩陣階數(shù)很大，非零元個數(shù)較少，零元很多，但非零元的排列沒有一定規(guī)律，我們稱這一類矩陣為稀疏矩陣。按照壓縮存儲的概念，要存放稀疏矩陣的元素，由于沒有某種規(guī)律，除存放非零元的值外，還必須存儲適當?shù)妮o助信息，才能迅速確定一個非零元是矩陣中的哪一個位置上的元素。5.3.2稀疏矩陣第21頁，共52頁，2023年，2月20日，星期六在壓縮存放稀疏矩陣的非零元同時，若還存放此非零元所在的行號和列號，則稱為三元組表法，即稱稀疏矩陣可用三元組表進行壓縮存儲，但它是一種順序存儲（按行優(yōu)先順序存放）。一個非零元有行號、列號、值，為一個三元組，整個稀疏矩陣中非零元的三元組合起來稱為三元組表。1．三元組順序表第22頁，共52頁，2023年，2月20日，星期六圖三元組的結(jié)構eji第23頁，共52頁，2023年，2月20日，星期六稀疏矩陣的三元組順序表存儲表示:#defineMAXSIZE12500

/*非零元素的最多個數(shù)*/typedefstruct{inti,j;

/*該非零元素的行下標和列下標*/

ElemType

e；/*該非零元素的值*/}Triple;typedefstruct{Triple

data[MAXSIZE+1];/*非零元素的三元組表。data[0]未用*/

intmu,

nu,tu;/*矩陣的行數(shù)、列數(shù)和非零元素的個數(shù)*/}TSMatrix；第24頁，共52頁，2023年，2月20日，星期六稀疏矩陣M對應的三元組表121213931-3361443245218611564-7第25頁，共52頁，2023年，2月20日，星期六000000稀疏矩陣N對應的三元組表13-3161521122518319342446-76314-T第26頁，共52頁，2023年，2月20日，星期六000000在三元組表存儲結(jié)構下的

矩陣的轉(zhuǎn)置運算所謂的矩陣轉(zhuǎn)置是指變換元素的位置，把位于（i,j）位置上的元素換到（j,i）位置上，也就是說，把元素的行列互換。如下圖的6×7矩陣M，它的轉(zhuǎn)置矩陣就是7×6的矩陣N，并且N（i,j）=M（j,i），其中，1≤i≤7，1≤j≤6。-T第27頁，共52頁，2023年，2月20日，星期六算法分析顯然，稀疏矩陣的轉(zhuǎn)置仍舊是稀疏矩陣。假設M和T分別表示矩陣M和T.如何由M得到T呢?ije121213931-3361443245218611564-7ije13-3161521122518319342446-76314M.dataT.data只需(1)將每個元組中的i,j相互調(diào)換(2)重排三元組的次序第28頁，共52頁，2023年，2月20日，星期六處理方法1:按照T.data中三元組的次序依次在M.data中找到相應的三元組進行轉(zhuǎn)置.即,按照M的列序進行轉(zhuǎn)置StatusTransposeSMatrix(TSMatrixM,TSMatrix&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;}O(nu*tu)當tu和mn*nu等數(shù)量級時為O(mu*nu2)第29頁，共52頁，2023年，2月20日，星期六處理方法2:按照M.data中三元組的次序依次進行轉(zhuǎn)置,并將轉(zhuǎn)置后的三元組置入T.data中恰當?shù)奈恢?為了能將待轉(zhuǎn)置三元組M.data中元素一次定位到三元組T.data的正確位置上，需要預先計算以下數(shù)據(jù)：①

待轉(zhuǎn)置矩陣M每一列中非零元素的個數(shù)。（即轉(zhuǎn)置后矩陣T每一行中非零元素的個數(shù)）。②

待轉(zhuǎn)置矩陣M每一列中第一個非零元素在三元組T.data中的正確位置（即轉(zhuǎn)置后矩陣T每一行中第一個非零元素在三元組T.data中的正確位置。）第30頁，共52頁，2023年，2月20日，星期六為此，需要設兩個num[]和cpot[]。其中num[col]用來存放矩陣M中第col列中非零元素個數(shù)（轉(zhuǎn)置矩陣T中第col行非零元素的個數(shù)）。cpot[col]用來存放轉(zhuǎn)置前矩陣M中第col列（轉(zhuǎn)置后矩T中第col行）中第一個非零元素在三元組T.data中的正確位置。則cpot[1]=1，cpot[col]=cpot[col-1]+num[col-1]。

其中2≤col≤M.nu。c第31頁，共52頁，2023年，2月20日，星期六StatusTransposeSMatrix(TSMatrixM,TSMatrix&T){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)++num[M.data[t].j];cpot[1]=1;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;}O(nu+tu)當tu和mn*nu等數(shù)量級時為O(mu*nu)第32頁，共52頁，2023年，2月20日，星期六為了便于隨機存取任意一行的非零元,則需知道每一行的第一個非零元在三元組表中的位置。為此可將上節(jié)快速轉(zhuǎn)置矩陣的算法中創(chuàng)建的，指示“行”信息的輔助數(shù)組cpot固定在稀疏矩陣的存儲結(jié)構中。其類型描述如下：typedefstruct{Triple

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

intmu,

nu,tu;//矩陣的行數(shù)、列數(shù)和非零元素的個數(shù)}RLSMatrix2．行邏輯鏈接的順序表第33頁，共52頁，2023年，2月20日，星期六當矩陣的非零元個數(shù)和位置在操作過程中變化較大時，就不宜采用順序存儲結(jié)構來表示了。如“將矩陣B加至矩陣A”操作，由于非零元的插入或刪除將會引起A.data中元素的移動，此時宜采用鏈式存儲。十字鏈表為稀疏矩陣中的鏈接存儲中的一種較好的存儲方法3．十字鏈表第34頁，共52頁，2023年，2月20日，星期六每一個非零元用一個結(jié)點表示，結(jié)點包括五個域：除了表示非零元所在的行、列和值的三元組（i,j,e）外，還需增加兩個鏈域：行指針域（right），用來指向本行中下一個非零元素；列指針域（down），用來指向本列中下一個非零元素。十字鏈表結(jié)點定義ijrightdowne第35頁，共52頁，2023年，2月20日，星期六稀疏矩陣中同一行的非零元通過向右的right指針鏈接成一個帶表頭結(jié)點的線性鏈表。同一列的非零元也通過down指針鏈接成一個帶表頭結(jié)點的線性鏈表。因此，每個非零元既是第i行循環(huán)鏈表中的一個結(jié)點，又是第j列循環(huán)鏈表中的一個結(jié)點，相當于處在一個十字交叉路口，故稱鏈表為十字鏈表?？捎脙蓚€分別存儲行鏈表的頭指針和列鏈表的頭指針的一維數(shù)組表示之。十字鏈表類型定義第36頁，共52頁，2023年，2月20日，星期六M=0050-100200011314522-1312M.rheadM.chead^^^^^^^例：矩陣M的十字鏈表第37頁，共52頁，2023年，2月20日，星期六稀疏矩陣的十字鏈表存儲表示typedefstructOLNode{inti,j;

/*該非零元素的行下標和列下標*/

ElemType

e；/*該非零元素的值*/structOLNode*right,*down;}OLNode;*Olink;typedefstruct{Olink*rhead,*chead;

intmu,

nu,tu;}CrossList；第38頁，共52頁，2023年，2月20日，星期六廣義表是第2章提到的線性表的推廣。線性表中的元素僅限于原子項，即不可以再分，而廣義表中的元素既可以是原子項，也可以是子表（另一個線性表）。廣義表也稱為列表（lists).1．廣義表的定義廣義表是n≥0個元素a1，a2，…，an的有限序列，其中每一個ai或者是原子，或者是一個子表。5.4廣義表的定義第39頁，共52頁，2023年，2月20日，星期六廣義表通常記為LS=(a1,a2,…,an)，其中LS為廣義表的名字，n為廣義表的長度，每一個ai為廣義表的元素,可以是單個元素（原子），也可以是廣義表（子表）。在習慣中，一般用大寫字母表示廣義表，小寫字母表示原子。當廣義表LS非空時，稱第一個元素a1為LS的表頭（Head),稱其余元素組成的表（a2,…,an)是LS的表尾（Tail).第40頁，共52頁，2023年，2月20日，星期六（1）A=()，A為空表，長度為0。（2）B=(a,（b,c）)，B是長度為2的廣義表，第一項為原子，第二項為子表。（3）C=(x,y,z)，C是長度為3的廣義表，每一項都是原子。（4）D=(B,C)，D是長度為2的廣義表，每一項都是上面提到的子表。（5）E=(a,E)，是長度為2的廣義表，第一項為原子，第二項為它本身。2．廣義表舉例第41頁，共52頁，2023年，2月20日，星期六（1）用LS=(a1，a2，…，an)形式，其中每一個ai為原子或廣義表例如：A=(b,c)B=(a,A)E=(a,E)都是廣義表。3．廣義表的表示方法第42頁，共52頁，2023年，2月20日，星期六（2）將廣義表中所有子表寫到原子形式，并利用圓括號嵌套例如，上面提到的廣義表A、B、C可以描述為：A(b,c)B(a,A(b,c))E(a,E(a,E（…）))第43頁，共52頁，2023年，2月20日，星期六（3）將廣義表用樹和圖來描述（a）A=(b,c)（b）B=(a,A)（c）C=(A,B)圖廣義表用樹或圖來表示第44頁，共52頁，2023年，2月20日，星期六一個廣義表的深度是指該廣義表展開后所含括號的層數(shù)。例如，A=(b,c)的深度為1，B=(A,d)的深度為2，C=(f,B,h)的深度為34．廣義表的深度

第45頁，共52頁，2023年，2月20日，星期六GetHead(A)=bGetTail(A)=(c)GetHead(B)=AGetTail(B)=(d)GetHead(C)=fGetTail(C)=(B,h)5．廣義表的操作取表頭GetHead()和取表尾GetTail()如：對A=(b,c)B=(A,d)，C=(f,B,h)分別做上述操作6.區(qū)分列表（）和（（））的不同前者為空表，長度n=0；后者長度為n=1,可分解得其表頭和表尾均為空表（）第46頁，共52頁，2023年，2月20日，星期六由于廣義表的元素類型不一定相同，因此，難以用順序結(jié)構存儲表中元素，通常采用鏈接存儲方法來存儲廣義表中元素，并稱之為廣義鏈表。常見的表示方法:5.5