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

數(shù)據(jù)結(jié)構(gòu)5數(shù)組15數(shù)組和廣義表主要內(nèi)容數(shù)組的基本概念數(shù)組的存儲(chǔ)結(jié)構(gòu)矩陣的壓縮存儲(chǔ)特殊矩陣稀疏矩陣25數(shù)組和廣義表數(shù)組的基本概念數(shù)組的定義數(shù)組是下標(biāo)與值組成的偶對(duì)的有窮集合。數(shù)組的基本操作給定一組下標(biāo)，存取或修改相應(yīng)元素的值。給定一組下標(biāo)，檢索相應(yīng)的數(shù)組元素。對(duì)數(shù)組元素進(jìn)行排序。對(duì)數(shù)組的操作是基于下標(biāo)進(jìn)行的35數(shù)組和廣義表數(shù)組的存儲(chǔ)結(jié)構(gòu)一維數(shù)組A[1:n]A[1..n]=(a1,a2,a3,…,an-1,an)一維數(shù)組的特點(diǎn)給定一組下標(biāo)，存取或修改相應(yīng)元素的值。除了第一個(gè)元素外，其他每個(gè)元素有且僅有一個(gè)直接前驅(qū)。除了最后那個(gè)元素外，其他每個(gè)元素有且僅有一個(gè)直接后繼元素。一維數(shù)組的存儲(chǔ)LOC(ai)=LOC(a1)+(i-1)k典型的線性結(jié)構(gòu)a1a2a3a4a5…an-1anLOC(a1)45數(shù)組和廣義表數(shù)組的存儲(chǔ)結(jié)構(gòu)二維數(shù)組A[1:m,1:n]二維數(shù)組在內(nèi)存中的存放二維數(shù)組的“二維”是邏輯上的內(nèi)存永遠(yuǎn)是線性編址0,00,10,20,31,01,11,21,32,02,12,22,33,03,13,23,34,04,14,24,30,00,10,20,31,01,11,21,32,02,1...內(nèi)存中的存放方式9*2字節(jié)55數(shù)組和廣義表數(shù)組的存儲(chǔ)結(jié)構(gòu)LOC(aij)=LOC(a11)+(i-1)nk+(j-1)k=LOC(a11)+[(i-1)n+(j-1)]k若已知每個(gè)元素占k個(gè)存儲(chǔ)單元，并且知道第一個(gè)元素的存儲(chǔ)地址LOC(a11)，則二維數(shù)組的存儲(chǔ)行序?yàn)橹餍蚍峙浞绞教攸c(diǎn)前一行最后一個(gè)元素的存儲(chǔ)位置與后一行的第一個(gè)元素的存儲(chǔ)位置相鄰。65數(shù)組和廣義表數(shù)組的存儲(chǔ)結(jié)構(gòu)特點(diǎn)前一列最后一個(gè)元素的存儲(chǔ)位置與后一列的第一個(gè)元素的存儲(chǔ)位置相鄰。二維數(shù)組的存儲(chǔ)列序?yàn)橹餍蚍峙浞绞絃OC(aij)=LOC(a11)+(j-1)mk+(i-1)k=LOC(a11)+[(j-1)m+(i-1)]k若已知每個(gè)元素占k個(gè)存儲(chǔ)單元，并且知道第一個(gè)元素的存儲(chǔ)地址LOC(a11)，則75數(shù)組和廣義表問題：數(shù)組與線性表的區(qū)別與聯(lián)系相同之處：都是由若干個(gè)相同數(shù)據(jù)類型的數(shù)據(jù)元素a0,…,an-1構(gòu)成的有限序列。不同之處：(1)數(shù)組要求其元素占用一塊地址連續(xù)的內(nèi)存單元空間，而線性表無此要求；(2)線性表的元素是邏輯意義上不可再分的元素，而數(shù)組中的每個(gè)元素還可以是一個(gè)數(shù)組；(3)數(shù)組的操作主要是向某個(gè)下標(biāo)的數(shù)組元素中存放數(shù)據(jù)和取讀取某個(gè)下標(biāo)中的數(shù)組元素，這與線性表的插入和刪除操作不同。85數(shù)組和廣義表0,0,00,1,00,2,00,3,01,0,01,1,01,2,01,3,02,0,02,1,02,2,02,3,03,0,03,1,03,2,03,3,04,0,04,1,04,2,04,3,0yxz0,0,10,0,20,1,10,1,20,2,10,2,20,3,10,3,21,3,22,3,23,3,24,3,2N維數(shù)組三維數(shù)組Amnp，即m×n×p數(shù)組，對(duì)于數(shù)組元素aijk其物理地址為：LOC(aijk)=LOC(a111)+((i-1)*n*p+(j-1)*p+k-1)*l推廣到一般的三維數(shù)組：A[c1..d1][c2..d2][c3..d3]，則aijk的物理地址為：LOC(i,j,k)=LOC(ac1c2c3)+((i-c1)*(d2-c2+1)*(d3-c3+1)+(j-c2)*(d3-c3+1)+(k-c3))*l95數(shù)組和廣義表魔術(shù)方陣往一個(gè)n為奇數(shù)的n×n的魔術(shù)方陣中填入1到n2的整數(shù)，能使其各列、各行及對(duì)角線之和皆相等。規(guī)則：

首先將1填入最上列的中間格，然后往左上方走，(1)以1的級(jí)數(shù)增加其值，并將此值填入空格；(2)若方格已填滿，則在原地的下一方格填上數(shù)字，并繼續(xù)做；(3)若超出方陣，則往下到最底層或往右到最右方，看兩者哪一個(gè)有方格，即將數(shù)字填入此方格；(4)若兩者皆無方格，則在原地的下一方格填上數(shù)字。105數(shù)組和廣義表3階魔方115數(shù)組和廣義表5階魔方形成的步驟

A、將1填入此方陣最上列的中間方格，如圖1所示。圖1插入1后的魔術(shù)方陣圖圖2插入2后的魔術(shù)方陣圖

B、在A的基礎(chǔ)上往左上方走，由于超出方陣，依據(jù)規(guī)則(3)發(fā)現(xiàn)往下的最底層有空格，因此將2填上，如圖2所示。125數(shù)組和廣義表5階魔方形成的步驟

C、承B往左上方，依據(jù)規(guī)則(1)將3填上，然后再往左上方，此時(shí)，超出方陣，依據(jù)規(guī)則(3)將4填入最右方的方格，如圖3所示。圖3插入3后的魔術(shù)方陣圖

圖4插入4后的魔術(shù)方陣圖

D、承C往左上方，依據(jù)規(guī)則(1)將5填上，再往左上方時(shí)，此處方格已有數(shù)字，依據(jù)規(guī)則(2)往5的下方填，如圖4所示。135數(shù)組和廣義表5階魔方形成的步驟E、依此類推，依據(jù)上述4個(gè)規(guī)則繼續(xù)填，填到15的結(jié)果如圖5所示。

圖5插入15后的魔術(shù)方陣圖

圖6插入16后的魔術(shù)方陣圖16F、承E此時(shí)往左上方，發(fā)現(xiàn)往下的最底層和往右的最右方皆有空格，依據(jù)規(guī)則(4)在原地的下方，將此數(shù)字填上，如圖6所示。145數(shù)組和廣義表5階魔方形成的步驟G、繼續(xù)往下填，并依據(jù)規(guī)則(1)、(2)、(3)、(4)，最后的結(jié)果如圖7所示。圖7最終的魔術(shù)方陣圖此時(shí)我們可以算算各行、各列及對(duì)角線之和是否皆相等，答案是肯定的，其和都是65。155數(shù)組和廣義表0.將用做“魔方”的二維數(shù)組的所有元素清0；1.第一個(gè)數(shù)填在第一行居中的位置上(i=0，j=n/2)；2.以后每填一個(gè)數(shù)后，將位置移到當(dāng)前位置(i,j)的左上角，即做動(dòng)作i=i-1，j=j-1；3.根據(jù)不同情況對(duì)位置進(jìn)行修正：（1）若位置(i,j)上已經(jīng)填數(shù)，或者i,j同時(shí)小于0，將位置修改為i=i+2，j=j+1；（2）若i小于0，但j不小于0，修改i為n-1；（3）若j小于0，但i不小于0，修改j為n-1。165數(shù)組和廣義表數(shù)組的存儲(chǔ)結(jié)構(gòu)從理論上講，數(shù)組結(jié)構(gòu)也可以使用兩種存儲(chǔ)結(jié)構(gòu)，即順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。然而，由于數(shù)組結(jié)構(gòu)沒有插入、刪除元素的操作，所以使用順序存儲(chǔ)結(jié)構(gòu)更為適宜。換句話說，一般的數(shù)組結(jié)構(gòu)不使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。組成數(shù)組結(jié)構(gòu)的元素可以是多維的，但存儲(chǔ)數(shù)據(jù)元素的內(nèi)存單元地址是一維的，因此，在存儲(chǔ)數(shù)組結(jié)構(gòu)之前，需要解決將多維關(guān)系映射到一維關(guān)系的問題。175數(shù)組和廣義表特殊矩陣的壓縮存儲(chǔ)185數(shù)組和廣義表特殊矩陣對(duì)稱矩陣（即aij=aji,1<=i,j<=n）矩陣的壓縮a11a21a22……aij……annLTA[0..n(n+1)/2-1]k=012……n(n+1)/2-1195數(shù)組和廣義表k的含義：按行優(yōu)先，是第k個(gè)（從0開始）15675289683079041526837904i=3j=2k=4公式的推導(dǎo)（下三角）i=3，j=2則前面有一個(gè)i-1行的完整三角形，共有元素

(1+i-1)(i-1)/2=i(i-1)/2個(gè)另外，同一行，前面還有j-1個(gè)元素所以，k=i(i-1)/2+j-1205數(shù)組和廣義表三角矩陣壓縮方法和對(duì)稱矩陣完全相同10005200683079041567028900300004下三角上三角矩陣的壓縮215數(shù)組和廣義表矩陣的壓縮對(duì)角矩陣225數(shù)組和廣義表有3n-2個(gè)非零元素B中任一非零元素bij與LTB[K]之間存在對(duì)應(yīng)關(guān)系k=2*i+j235數(shù)組和廣義表

結(jié)論：對(duì)特殊矩陣的壓縮存儲(chǔ)實(shí)質(zhì)上就是將二維矩陣中的部分元素按照某種方案排列到一維數(shù)組中，不同的排列方案也就對(duì)應(yīng)不同的存儲(chǔ)方案。矩陣的壓縮245數(shù)組和廣義表矩陣的壓縮稀疏矩陣0000000030000000000001

40000000700000000050000000000000000000000A9×7=非零元素個(gè)數(shù)遠(yuǎn)遠(yuǎn)少于矩陣元素總數(shù)255數(shù)組和廣義表稀疏矩陣的定義設(shè)矩陣Am×n中有t個(gè)非零元素，若t遠(yuǎn)遠(yuǎn)小于矩陣元素的總數(shù)m×n，且非零元素的分布無規(guī)律，則稱矩陣A為稀疏矩陣為節(jié)省存儲(chǔ)空間，應(yīng)只存儲(chǔ)非零元素非零元素的分布一般沒有規(guī)律，應(yīng)在存儲(chǔ)非零元素時(shí)，同時(shí)存儲(chǔ)該非零元素的行下標(biāo)row、列下標(biāo)col、值value每一個(gè)非零元素由一個(gè)三元組唯一確定：(row,col,value)265數(shù)組和廣義表稀疏矩陣的壓縮表示000000003000000000000140000000700000000050000000000000000000000A9×7=0123456780123456975113301314427555行數(shù)列數(shù)元素個(gè)數(shù)行號(hào)列號(hào)元素值275數(shù)組和廣義表稀疏矩陣的順序存儲(chǔ)三元組(triple)順序表#define

smax16//非0元素個(gè)數(shù)typedef

struct{int

i,j;//行下標(biāo)、列下標(biāo)

datatypev;//元素的值}node;

typedef

struct

{nodedata[smax];

intm,n,t;//行數(shù)、列數(shù)、非0元素個(gè)數(shù)}spmatrix;285數(shù)組和廣義表稀疏矩陣的轉(zhuǎn)置

Tij=Mji

01290000

00000-300001400240000180000

0

0-30012

0001890024000

0

00018000001400566121213931-336144324521865613-32112251831934246314295數(shù)組和廣義表稀疏矩陣用三元組表示的轉(zhuǎn)置行數(shù)和列數(shù)交換i、j的值相互交換重排三元組之間的次序566121213931-336144324521865613-32112251831934246314656211231913-3631434242518305數(shù)組和廣義表用三元組表示，求稀疏矩陣M的轉(zhuǎn)置矩陣TM566121213931-3361443245218T1.行數(shù)和列數(shù)交換，總個(gè)數(shù)不變:

T.m=M.n;T.n=M.m;T.t=M.t;2.讓q定位T中的第一條記錄:

q=1;656q315數(shù)組和廣義表M566121213931-3361443245218T3.讓col取M的每一列:

for(col=1;col<=M.n;col++)

4.讓p掃描三元組M的每一條記錄:

for(p=1;p<=M.t;p++)656qcol=1p325數(shù)組和廣義表M566121213931-3361443245218T656qcol=1p5.如果p指向的記錄的j下標(biāo)與col相等:

if(M.data[p].j==col)ije335數(shù)組和廣義表M566121213931-3361443245218T656qcol=1p6.把M中的記錄p復(fù)制到T中的記錄q:

T.data[q].i=M.data[p].j;

T.data[q].j=M.data[p].i;

T.data[q].v=M.data[p].v;7.讓q下移:q++;13-3345數(shù)組和廣義表M566121213931-3361443245218T656qcol=2p13-321122518355數(shù)組和廣義表M566121213931-3361443245218T656qcol=3p13-3211225183193424……365數(shù)組和廣義表M566121213931-3361443245218T656qcol=6p13-32112251831934246314375數(shù)組和廣義表求稀疏矩陣M的轉(zhuǎn)置矩陣T的算法int

TransposeSMatrix(TSMatrixM,TSMatrix*T){intp,q,col;

T->m=M.n;T->n=M.m;T->t=M.t;

if(T->t){q=1;for(col=1;col<=M.n;col++)for(p=1;p<=M.t;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].v=M.data[p].v; q++;}}

retrnOK;}復(fù)制總體信息col掃描每一列p掃描三元組M的每一條記錄如果p指向的記錄的列下標(biāo)=col把M中的記錄p復(fù)制到T中的記錄q385數(shù)組和廣義表稀疏矩陣的轉(zhuǎn)置：簡(jiǎn)單算法簡(jiǎn)單算法的分析稀疏矩陣轉(zhuǎn)置算法復(fù)雜度=O(n*t)比較一般矩陣的轉(zhuǎn)置算法：其復(fù)雜度=O(m*n)如果t和m*n一個(gè)數(shù)量級(jí)，則稀疏矩陣轉(zhuǎn)置算法復(fù)雜度=O(m*n2)所以此算法只適用于t<<m*n時(shí)for(col=1;col<=nu;col++)for(row=1;row<=mu;row++)

T[col][row]=M[row][col];395數(shù)組和廣義表稀疏矩陣的轉(zhuǎn)置：簡(jiǎn)單算法簡(jiǎn)單算法的分析簡(jiǎn)單算法的主要問題在于為了使得結(jié)果三元組表的記錄按照行順序排列，需要分別針對(duì)結(jié)果三元組表的每一行（也就是原三元組表的每一列），掃描整個(gè)三元組表，查找屬于該行的所有記錄即對(duì)原三元組表的掃描需要反復(fù)進(jìn)行，而不是只需一次，因此時(shí)間復(fù)雜度=O(n*t)405數(shù)組和廣義表稀疏矩陣的轉(zhuǎn)置：快速轉(zhuǎn)置算法關(guān)鍵：希望對(duì)原三元組表只需掃描一遍問題：原三元組表中的一個(gè)三元組應(yīng)該放在結(jié)果三元組表中的什么位置呢？ijv0566112122139331-3436145432465218ijv0656113-3221123251843195342466314415數(shù)組和廣義表稀疏矩陣的轉(zhuǎn)置：快速轉(zhuǎn)置算法分析：原矩陣第1列只有一條記錄，而三元組1是第一個(gè)遇到的來自第2列的非零元素，應(yīng)該放在結(jié)果三元組表中的第2個(gè)位置ijv0566112122139331-3436145432465218ijv0656113-3221123251843195342466314425數(shù)組和廣義表稀疏矩陣的轉(zhuǎn)置：快速轉(zhuǎn)置算法類似的：第1列非零元素有1個(gè)，第2列非零元素有2個(gè)，而三元組2是第一個(gè)遇到的來自第3列的記錄，應(yīng)該放在結(jié)果三元組表中的第4個(gè)位置ijv0566112122139331-3436145432465218ijv0656113-3221123251843195342466314435數(shù)組和廣義表稀疏矩陣的轉(zhuǎn)置：快速轉(zhuǎn)置算法算法的實(shí)現(xiàn)數(shù)組num[col]：原矩陣第col列中，非零元素的個(gè)數(shù)數(shù)組cpot[col]：原矩陣第col列中，第1個(gè)非零元素在結(jié)果三元組表中的位置顯然有：cpot[1]=1cpot[col]=cpot[col-1]+num[col-1]445數(shù)組和廣義表稀疏矩陣的轉(zhuǎn)置：快速轉(zhuǎn)置算法ijv0566112122139331-3436145432465218ijv0656113-3221123251843195342466314col123456num[col]122001cpot[col]124666455數(shù)組和廣義表快速轉(zhuǎn)置算法Status

FastTransposeSMatrix(){ T.m=M.n;T.n=M.m;T.t=M.t;

if(T.t){

for(col=1;col<=M.n;col++)

num[col]=0;//初始化num

for(t=1;t<=M.t;t++) num[M.data[t].j]++;//統(tǒng)計(jì)每列元素個(gè)數(shù)

//計(jì)算T中每行開始的位置

cpot[1]=1;

for(col=2;col<=M.n;col++)

cpot[col]=cpot[col-1]+num[col-1];...4