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

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

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

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

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

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

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

ElemType

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

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

intmu,

nu,tu;/*矩陣的行數(shù)、列數(shù)和非零元素的個(gè)數(shù)*/}TSMatrix；第二十四頁，共五十二頁，2022年，8月28日稀疏矩陣M對(duì)應(yīng)的三元組表121213931-3361443245218611564-7第二十五頁，共五十二頁，2022年，8月28日000000稀疏矩陣N對(duì)應(yīng)的三元組表13-3161521122518319342446-76314-T第二十六頁，共五十二頁，2022年，8月28日000000在三元組表存儲(chǔ)結(jié)構(gòu)下的

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

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

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

其中2≤col≤M.nu。c第三十一頁，共五十二頁，2022年，8月28日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)當(dāng)tu和mn*nu等數(shù)量級(jí)時(shí)為O(mu*nu)第三十二頁，共五十二頁，2022年，8月28日為了便于隨機(jī)存取任意一行的非零元,則需知道每一行的第一個(gè)非零元在三元組表中的位置。為此可將上節(jié)快速轉(zhuǎn)置矩陣的算法中創(chuàng)建的，指示“行”信息的輔助數(shù)組cpot固定在稀疏矩陣的存儲(chǔ)結(jié)構(gòu)中。其類型描述如下：typedefstruct{Triple

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

intmu,

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

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

ElemType

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

intmu,

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

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