北航數(shù)據(jù)結(jié)構(gòu)Data03

數(shù)據(jù)結(jié)構(gòu)2第三章數(shù)組3.1數(shù)組的概念3.1.1數(shù)組的定義3.1.2數(shù)組的形式化定義3.2數(shù)組的存儲(chǔ)結(jié)構(gòu)3.3矩陣的壓縮存儲(chǔ)3.3.1對(duì)稱矩陣的壓縮存儲(chǔ)3.3.2對(duì)角矩陣的壓縮存儲(chǔ)3.4稀疏矩陣的三元組表示33.5稀疏矩陣的十字鏈表表示3.6數(shù)組應(yīng)用舉例3.6.1一元多項(xiàng)式的數(shù)組表示3.6.2n階魔方上機(jī)作業(yè)43.1.1數(shù)組的定義1、數(shù)組數(shù)組(Array)是一組按一定格式排列的、具有相同屬性的項(xiàng)目或者數(shù)據(jù)元素，如線性表、矩陣等。如果線性表的所有元素都是線性表(稱為子表)，且這些子線性表具有相同的上限標(biāo)號(hào)和下限標(biāo)號(hào)，那么這類線性表也稱為數(shù)組。數(shù)組可以看成是下標(biāo)與值組成的數(shù)偶的有序集合，即對(duì)于每個(gè)下標(biāo)，總有一個(gè)相應(yīng)的元素與之對(duì)應(yīng)。這種基于位置上的對(duì)應(yīng)關(guān)系是一種線性關(guān)系，因此，數(shù)組的邏輯結(jié)構(gòu)就是一種線性結(jié)構(gòu)。52、數(shù)組的表示在數(shù)組中用下標(biāo)來(lái)唯一標(biāo)識(shí)數(shù)據(jù)元素。如果數(shù)組元素只需要一個(gè)下標(biāo)就能唯一確定，則稱為一維數(shù)組；至少需要n個(gè)下標(biāo)才能唯一確定一個(gè)元素，則稱為n維數(shù)組。一維數(shù)組表示成：A(n)

或者A(m:

n)；其中A是數(shù)組名稱，m稱為數(shù)組的下界，n稱為上界；而A(n)的下界默認(rèn)為1。二維數(shù)組表示成：A(m,n)

或者A(i:m,j:n)；n維數(shù)組表示成：A(i1,i2,i3,...,in)；其中i1,i2,i3,...,in表示數(shù)組各維的下標(biāo)上界，下界均為1。63.1.2數(shù)組的形式化定義1、一維數(shù)組的形式化定義一維數(shù)組的邏輯結(jié)構(gòu)可以形式化地定義為：ARRAY_1=(D,R)，其中，D={ai|c1<=i<=c2,aidataobject}，R={ROW}，ROW={<ai,ai+1>|c1<=i<=c2,ai,ai+1D}。c1、c2,分別表示下標(biāo)的一對(duì)界偶，即下界和上界。數(shù)組中元素個(gè)數(shù)=c2-c1+172、二維數(shù)組的形式化定義二維數(shù)組，其邏輯結(jié)構(gòu)的形式化定義可以表示成：ARRAY_2=(D,R)，其中，D={aij|c1<=i<=c2,d1<=j<=d2,aijdataobject}，R={ROW,COL}，ROW={<aij,ai,j+1>|c1<=i<=c2,d1<=j<=d2-1,aij,ai,j+1D}COL={<aij,ai+1,j>|c1<=i<=c2-1,d1<=j<=d2,aij,ai+1,jD}（c1、c2）與（d1、d2）分別是下標(biāo)i和j的上下界。數(shù)組中元素個(gè)數(shù)=(c2-c1+1)*(d2-d1+1)8n維數(shù)組的邏輯結(jié)構(gòu)的形式化定義ARRAY_n=(D,R)，其中，

D={aj1,j2,…,jn|ci<=ji<=di,aj1,j2,…,jndataobject}，R={R1,R2,……,Rn}Ri={<aj1，…,ji,…,jn,aj1,…，ji+1,…,jn>|ck<=jk<=dk且k<>i，ci<=ji<=di-1，

aj1,…，ji,…,jn,aj1,…，ji+1,…,jnD}3、n維數(shù)組的形式化定義94、數(shù)組的操作n維數(shù)組的每個(gè)元素受到n個(gè)關(guān)系的約束，再每個(gè)關(guān)系中，每個(gè)元素都存在一個(gè)直接后繼。每個(gè)關(guān)系都是線性關(guān)系。因此，n維數(shù)組是線性表的一種推廣。一般數(shù)組的規(guī)模是固定的，沒(méi)有插入、刪除運(yùn)算。給出一組下標(biāo)，檢索對(duì)應(yīng)的數(shù)據(jù)元素；或者存取相應(yīng)元素的值；重新排列數(shù)組元素。103.2數(shù)組的存儲(chǔ)結(jié)構(gòu)1、數(shù)組的降維存儲(chǔ)由于計(jì)算機(jī)內(nèi)的存儲(chǔ)空間是一維(線性)的，要將多維數(shù)組存儲(chǔ)到計(jì)算機(jī)內(nèi)，必須將多維數(shù)組映射到一維存儲(chǔ)空間中，因此，需要降低數(shù)組的維數(shù)，即將n維數(shù)組看成是n個(gè)n-1維數(shù)組的有序集合。在計(jì)算機(jī)中，數(shù)組也與線性表一樣，是保存在一塊連續(xù)的內(nèi)存空間中的，即數(shù)組采用的是順序分配方式。112、行主序一個(gè)2×3的二維數(shù)組A(2,3)共有六個(gè)元素，需要用6個(gè)連續(xù)的單元存放。對(duì)這些元素，有兩種組織方式。一種是以“行”為主次序進(jìn)行分配，稱為行主序。A(1,1)A(1,2)A(1,3)第一行A(2,1)A(2,2)A(2,3)第二行(a)以行為主序存放123456A(i,j)元素存放位置=B+[(i-1)*3+(j-1)]*Lena11a12a13a21a22a23123、列主序以“列”為主次序進(jìn)行存儲(chǔ)分配。A(1,1)A(2,1)A(1,2)第一列A(2,2)A(1,3)A(2,3)第二列(b)以列為主序存放第三列123456A(i,j)元素存放位置=B+[(i-1)+(j-1)*2]*Lena11a12a13a21a22a23134、數(shù)組A(m,n)的存儲(chǔ)地址訪問(wèn)公式以“行”為主次序存放：

A(i,j)的起始地址=b+[(i-1)*n+(j-1)]*L以“列”為主次序存放：

A(i,j)的起始地址=b+[(i-1)+(j-1)*m]*L5、數(shù)組A(m:n,p:q)的存儲(chǔ)地址訪問(wèn)公式以“行”為主次序存放：

A(i,j)首址=b+[(i-m)*(q-p+1)+(j-p)]*L以“列”為主次序存放：

A(i,j)首址=b+[(i-m)+(j-p)*(n-m+1)]*L146、三維數(shù)組A(p,m,n)以行為主次序的訪問(wèn)公式如下：

A(i,j,k)首址=b+[(i-1)*m*n+(j-1)*n+(k-1)]*L以列為主次序的訪問(wèn)公式如下：

A(i,j,k)首址=b+[(i-1)+(j-1)*p+(k-1)*p*m]*L157、n維數(shù)組A(d1,d2,d3,......,dn)行主序：數(shù)組中任一元素A(j1,j2,j3,...,jn)的存儲(chǔ)位置，可以通過(guò)訪問(wèn)公式計(jì)算，數(shù)組各元素的存取是隨機(jī)的，在時(shí)間上大致相等，因此，數(shù)組是一種隨機(jī)存取的數(shù)據(jù)結(jié)構(gòu)。163.3.1對(duì)稱矩陣的壓縮存儲(chǔ)1、對(duì)稱矩陣一個(gè)m行n列的矩陣共有m*n個(gè)數(shù)據(jù)元素。當(dāng)m=n時(shí)，則稱該矩陣為n階方陣。在程序設(shè)計(jì)中，通常將矩陣表示為一個(gè)二維數(shù)組。采用順序存儲(chǔ)方式。若一個(gè)n階矩陣A的元素滿足性質(zhì)：aij=aji，1<=i,j<=n，則稱該矩陣為n階對(duì)稱矩陣。n階對(duì)稱矩陣中幾乎一半的元素相同，因此，對(duì)于每一對(duì)對(duì)稱元素可以只分配一個(gè)存儲(chǔ)單元。這樣，n階對(duì)稱矩陣的n2個(gè)元素就可以壓縮到（n*(n+1)/2）個(gè)存儲(chǔ)單元中。172、對(duì)稱矩陣的壓縮存儲(chǔ)a11，a12，a13，……，a1i，……，a1na21，a22，a23，……，a2i，……，a2n

……ai1，ai2，ai3，……，aii，……，ain……an1，an2，an3，……，ani，……，ann18按行主序存儲(chǔ)對(duì)稱矩陣下三角元素。數(shù)組LTA(1:(n*(n+1)/2))作為A的存儲(chǔ)結(jié)構(gòu)，A中的任意一個(gè)元素aij與LTA[k]之間存在的對(duì)應(yīng)關(guān)系：對(duì)于每一組下標(biāo)值(i,j)均可以在LTA中找到元素aij，反之，對(duì)于所有k=1，2，…，(n*(n+1)/2)，都能確定LTA[k]在矩陣A中的位置(i,j)。193.3.2對(duì)角矩陣的壓縮存儲(chǔ)矩陣的所有非零元素都集中在以對(duì)角線為中心的帶狀區(qū)域中，即除了主對(duì)角線上和直接在主對(duì)角線上、下方若干條對(duì)角線上的元素外，其余元素皆為零。1、對(duì)角矩陣對(duì)于三對(duì)角矩陣B，可以按行（或列）主序方式將對(duì)角矩陣B中的所有非零元素壓縮存儲(chǔ)到一個(gè)一維數(shù)組LTB[1：3n-2]中。202、對(duì)角矩陣的行主序方式存儲(chǔ)按行主序方式存儲(chǔ)，則B中任意一個(gè)非零元素bij，與LTB[k]之間存在一一對(duì)應(yīng)關(guān)系，即k=2*i+j–2時(shí)，則有bij=LTB[k]。k=3*(i-1)-1+(j-(i-1))+1=3i-4+j-i+2=2i+j-2第i行的非0元素bij應(yīng)當(dāng)是：bij-1bijbij+1211、稀疏矩陣3.4稀疏矩陣的三元組表示當(dāng)一個(gè)數(shù)組中的元素很多都是0時(shí)，該數(shù)組就稱為稀疏數(shù)組。一個(gè)矩陣中有許多0元素時(shí)，則稱該矩陣為稀疏矩陣。一個(gè)m×n的矩陣M，采用順序方式存儲(chǔ)時(shí)，需要分配m×n個(gè)單元；當(dāng)有許多0元素時(shí)，會(huì)造成存儲(chǔ)空間的浪費(fèi)。因此，可以考慮進(jìn)行壓縮存儲(chǔ)。一個(gè)m×n的矩陣M，每個(gè)元素可以用一個(gè)行標(biāo)號(hào)和列標(biāo)號(hào)來(lái)唯一確定它的位置，因此，可以用元素的行和列標(biāo)號(hào)來(lái)指示非0元素的位置，同時(shí)保存下該非0元素值。即用(i,j,Vij)表示非0元素。222、稀疏矩陣的三元組表示(ijVij)123456781115142216651916328668下限為0和1，上限為t和3的二維數(shù)組A(0:t,1:3)來(lái)存儲(chǔ)稀疏矩陣的非0元素。t是非0元素個(gè)數(shù)。233、稀疏矩陣的轉(zhuǎn)置運(yùn)算轉(zhuǎn)置是一種最簡(jiǎn)單的矩陣運(yùn)算。矩陣M轉(zhuǎn)置成另一個(gè)矩陣N，應(yīng)滿足M(i,j)=N(j,i)，1im及1jn。244、三元組表示矩陣的轉(zhuǎn)置6681115412261-15

22116681115412261-15

221136283236681115412261-15

221132343-643-66681115412261-15

2211323159143-66681115412261-15

2211323159143-66681115412261-15

22113231591362825按列順序?qū)崿F(xiàn)轉(zhuǎn)置：43-6668

1115

4122

61-15

22113231591362826算法步驟（1）從A中讀取矩陣的行數(shù)m、列數(shù)n和非零元素個(gè)數(shù)t，并設(shè)置B的行數(shù)為n、列數(shù)為m、非零元素個(gè)數(shù)為t；（2）設(shè)置計(jì)數(shù)器col=1，表示當(dāng)前正在轉(zhuǎn)置A的第col列元素（B的第col行）；（3）從A中選擇列號(hào)為col的元素，轉(zhuǎn)置后順序存入B；（4）當(dāng)A中列號(hào)為col的元素轉(zhuǎn)置完后，給col加1；（5）如果col不大于n，重復(fù)步驟（2）（3）（4），否則結(jié)束，完成轉(zhuǎn)置。27voidTranspose(intA(ROW,COL),B(ROW,COL))；{intm,n,t,p,q,Col;m=A[0,1];n=A[0,2];t=A[0,3];B[0,1]=n;B[0,2]=m;B[0,3]=t;if(t>0){q=1;for(col=

1;Col<=n;col++)//當(dāng)前轉(zhuǎn)置的列號(hào)為col//for(p=1;p<=t;p++)if(A[p,2]==col){//本次需要轉(zhuǎn)置的元素//B[q,1]=A[p,2];B[q,2]=A[p,1];B[q,3]=A[p,3];q=q+1;

}；//

一個(gè)元素轉(zhuǎn)置//

}；//所有元素轉(zhuǎn)置結(jié)束//}；//算法結(jié)束//285、快速轉(zhuǎn)置快速轉(zhuǎn)置的思路是：每行中的非0元素個(gè)數(shù)是可以統(tǒng)計(jì)出來(lái)的；每個(gè)非0元素都有自己最終的存儲(chǔ)位置；按行進(jìn)行轉(zhuǎn)置時(shí)，直接將元素存入對(duì)應(yīng)位置。設(shè)置一個(gè)數(shù)組Num(n)統(tǒng)計(jì)每列（轉(zhuǎn)置后每行）的非0元素個(gè)數(shù)；設(shè)置一個(gè)數(shù)組Pot(n)存儲(chǔ)轉(zhuǎn)置后每行第一個(gè)非0元素的存儲(chǔ)位置。29計(jì)算每列的非0元素個(gè)數(shù)快速轉(zhuǎn)置過(guò)程for(Col=1,Col<=nCol++)Num[Col]=0;for(p=1,p<=t,p++)Num[A[p,2]]=Num[A[p,2]]+1;計(jì)算轉(zhuǎn)置后每行第一個(gè)非0元素的存儲(chǔ)位置：Pot[1]=1;for(Col=2,Col<=n,Col++)Pot[Col]=Pot[Col-1]+Num[Col-1];30Pot[Col]134688Col123456668111524122761-15922114532343-68159133628631快速轉(zhuǎn)置算法voidFast-Transpose(intA(ROW,COL),B(ROW,COL)){intm,n,t,p,q,Col;m=A[0,1];n=A[0,2];t=A[0,3];B[0,1]=n;B[0,2]=m;B[0,3]=t;if(t<=0)return;for(Col=1;Col<=n;Col++)Num[Col]=0;for(p=1;p<=t;p++)Num[A[p,2]]=Num[A[p,2]]+1;Pot[1]=1;//計(jì)算轉(zhuǎn)置后每行第一個(gè)非0元素存儲(chǔ)位置//for(Col=2;Col<=n;Col++)Pot[Col]=Pot[Col-1]+Num[Col-1];for(p=1;p<=t;p++){//開(kāi)始轉(zhuǎn)置//Col=A[p,2];B[Pot[Col],1]=A[p,2];B[Pot[Col],2]=A[p,1];B[Pot[Col],3]=A[p,3];Pot[Col]=Pot[Col]+1;}//元素轉(zhuǎn)置結(jié)束//}//算法結(jié)束//323.5稀疏矩陣的十字鏈表表示1、稀疏矩陣的循環(huán)鏈表表示用鏈表表示稀疏矩陣中的非0元素，需要存儲(chǔ)：行號(hào)、列號(hào)、元素值；將非零元素以行主序方式用循環(huán)鏈表鏈接起來(lái)。ijVLinkmntLink表頭結(jié)點(diǎn)34511414222331533-1H332、稀疏矩陣的十字鏈表表示每個(gè)元素按行有一個(gè)后繼，按列有一個(gè)后繼，因此，需要設(shè)置兩個(gè)指針，分別指向行后繼和列后繼元素；用鏈表表示稀疏矩陣中的非0元素，需要存儲(chǔ)：行號(hào)、列號(hào)、元素值；RowColRightDownValue結(jié)點(diǎn)結(jié)構(gòu)mnRightDownt表頭結(jié)點(diǎn)Row、Col、Value分別表示非0元素的行、列和值，Down和Right表示向下（列）和向右（行）指針，分別鏈接同一列和同一行中的非0元素。3434501002003004010020030011431514222333-1353.6.1一元多項(xiàng)式的數(shù)組表示方法1：定義一個(gè)一維數(shù)組A[1：n+2]。其中，A[1]用來(lái)存儲(chǔ)多項(xiàng)式的階數(shù)，從A[2]開(kāi)始到A[n+2]，分別存儲(chǔ)n+1個(gè)系數(shù)an，an-1，…，a0。1、一元n階多項(xiàng)式的數(shù)組表示例如，多項(xiàng)式A（x）=10x6–8x5+3x2–1，表示成：36例如，B（x）=x200+4方法2：定義一個(gè)一維數(shù)組A[1：2m+1]來(lái)表示多項(xiàng)式。其中，第1個(gè)元素A[1]存放多項(xiàng)式中系數(shù)非0項(xiàng)的總項(xiàng)數(shù)m；從第2個(gè)元素到第2m+1個(gè)元素（共2m個(gè)）依次存放系數(shù)非0項(xiàng)的指數(shù)與系數(shù)偶對(duì)（共m個(gè)偶對(duì)）。373.6.2n階魔方所謂n階魔方是一個(gè)填數(shù)游戲。要求將數(shù)字1~n2個(gè)數(shù)字不重復(fù)地填入到一個(gè)由n行n列組成的方陣中，使得方陣中每行、每列、兩個(gè)對(duì)角線上的數(shù)字之和分別等于同一個(gè)數(shù)值。這個(gè)方陣就稱為“魔方”。最早的魔方據(jù)說(shuō)是大禹治水(公元前2200)在神龜背上看到的3階魔方：492357816洛書上的3階魔方38公元80年出版的古書《大戴禮記》：“二九四、七五三、六一八”1977年出土的第二代汝陰侯夏侯灶(公元前165年)墓文物“太乙九宮占盤”八個(gè)方位所刻數(shù)字及中心位置的九宮數(shù)字恰為“四九二、三五七、八一六”南宋楊輝：研究魔方第一人，給出了3、4-10階魔方39楊輝4階魔方稱為“花十六圖”或“四四圖”，分陽(yáng)圖和陰圖楊輝4階魔方216133115810791261441151395114106215117316128449516147112156103112813陰圖生成法：十六子依次四行排列；外角四子互換：1-16、4-13；內(nèi)角四子互換：6-11；7-104951614711215610311281340如何構(gòu)造魔方適合于奇數(shù)階魔方

將1設(shè)置在最上行中間，然后按對(duì)角線的方向（自右下向左上、或者自左下向右上方向）依次填入數(shù)字；如果到達(dá)頂部則轉(zhuǎn)向底部；左（右）邊界則轉(zhuǎn)向右（左邊），如果其上已有數(shù)字則轉(zhuǎn)向下方。例如n=3“魔方”為：12345678

91、連續(xù)擺數(shù)法81635749241n=5“魔方”為：1234567891011121314151617181920212223242542voidMAGIC(intM(ROW,COL)，