1、數(shù)據(jù)結(jié)構(gòu),2,第三章 數(shù)組,3.1 數(shù)組的概念 3.1.1 數(shù)組的定義 3.1.2 數(shù)組的形式化定義 3.2 數(shù)組的存儲結(jié)構(gòu) 3.3 矩陣的壓縮存儲 3.3.1 對稱矩陣的壓縮存儲 3.3.2 對角矩陣的壓縮存儲 3.4 稀疏矩陣的三元組表示,3,3.5 稀疏矩陣的十字鏈表表示 3.6 數(shù)組應用舉例 3.6.1 一元多項式的數(shù)組表示 3.6.2 n階魔方 上機作業(yè),4,3.1.1 數(shù)組的定義,1、數(shù)組,數(shù)組(Array)是一組按一定格式排列的、具有相同屬性的項目或者數(shù)據(jù)元素，如線性表、矩陣等。,如果線性表的所有元素都是線性表(稱為子表) ，且這些子線性表具有相同的上限標號和下限標號，那么這類線

2、性表也稱為數(shù)組。,數(shù)組可以看成是下標與值組成的數(shù)偶的有序集合，即對于每個下標，總有一個相應的元素與之對應。 這種基于位置上的對應關(guān)系是一種線性關(guān)系，因此，數(shù)組的邏輯結(jié)構(gòu)就是一種線性結(jié)構(gòu)。,5,2、數(shù)組的表示,在數(shù)組中用下標來唯一標識數(shù)據(jù)元素。如果數(shù)組元素只需要一個下標就能唯一確定，則稱為一維數(shù)組；至少需要n個下標才能唯一確定一個元素，則稱為n維數(shù)組。,一維數(shù)組表示成：A(n) 或者 A(m : n)；其中A是數(shù)組名稱，m稱為數(shù)組的下界，n稱為上界；而A(n)的下界默認為1。,二維數(shù)組表示成：A(m,n) 或者 A(i:m ,j:n)；,n維數(shù)組表示成：A(i1,i2,i3,.,in)；其中i1

3、,i2,i3, ., in表示數(shù)組各維的下標上界，下界均為1。,6,3.1.2 數(shù)組的形式化定義,1、一維數(shù)組的形式化定義,一維數(shù)組的邏輯結(jié)構(gòu)可以形式化地定義為：ARRAY_1=(D,R)， 其中，D=ai|c1|c1=i=c2, ai,ai+1D 。 c1、c2,分別表示下標的一對界偶，即下界和上界。,數(shù)組中元素個數(shù) = c2 - c1 + 1,7,2、二維數(shù)組的形式化定義,二維數(shù)組，其邏輯結(jié)構(gòu)的形式化定義可以表示成：ARRAY_2=(D,R)，其中，D=aij|c1|c1|c1=i=c2-1, d1=j=d2, aij,ai+1,jD （c1、c2）與（d1、d2）分別是下標i和j的上下界

4、。,數(shù)組中元素個數(shù) = (c2 - c1 + 1)*(d2 - d1 + 1),8,n維數(shù)組的邏輯結(jié)構(gòu)的形式化定義ARRAY_n=(D,R)，其中， D=aj1,j2,jn|ci| cki，ci=ji=di-1， aj1,，ji,jn ,aj1,，ji+1,jnD ,3、n維數(shù)組的形式化定義,9,4、數(shù)組的操作,n維數(shù)組的每個元素受到n個關(guān)系的約束，再每個關(guān)系中，每個元素都存在一個直接后繼。每個關(guān)系都是線性關(guān)系。因此，n維數(shù)組是線性表的一種推廣。,一般數(shù)組的規(guī)模是固定的，沒有插入、刪除運算。,給出一組下標，檢索對應的數(shù)據(jù)元素；或者存取相應元素的值；,重新排列數(shù)組元素。,10,3.2 數(shù)組的存儲

5、結(jié)構(gòu),1、數(shù)組的降維存儲,由于計算機內(nèi)的存儲空間是一維(線性)的，要將多維數(shù)組存儲到計算機內(nèi)，必須將多維數(shù)組映射到一維存儲空間中，因此，需要降低數(shù)組的維數(shù)，即將n維數(shù)組看成是n個n-1維數(shù)組的有序集合。,在計算機中，數(shù)組也與線性表一樣，是保存在一塊連續(xù)的內(nèi)存空間中的，即數(shù)組采用的是順序分配方式。,11,2、行主序,一個23的二維數(shù)組A(2,3)共有六個元素，需要用6個連續(xù)的單元存放。,對這些元素，有兩種組織方式。一種是以“行”為主次序進行分配，稱為行主序。,A(i,j)元素存放位置=B + (i-1)*3 + (j-1)*Len,12,3、列主序,以“列”為主次序進行存儲分配。,A(i,j)元

6、素存放位置=B + (i-1) + (j-1)*2*Len,13,4、數(shù)組A(m,n)的存儲地址訪問公式,以“行”為主次序存放： A(i,j)的起始地址 = b + (i-1)*n + (j-1)*L 以“列”為主次序存放： A(i,j)的起始地址 = b + (i-1) + (j-1)*m*L,5、數(shù)組A(m:n,p:q)的存儲地址訪問公式,以“行”為主次序存放： A(i,j)首址 = b + (i-m)*(q-p+1) + (j-p)*L 以“列”為主次序存放： A(i,j)首址 = b + (i-m) + (j-p)*(n-m+1)*L,14,6、三維數(shù)組A(p,m,n),以行為主次序的

7、訪問公式如下： A(i,j,k)首址=b+(i-1)*m*n+(j-1)*n+(k-1)*L,以列為主次序的訪問公式如下： A(i,j,k)首址=b+(i-1)+(j-1)*p+(k-1)*p*m*L,15,7、n維數(shù)組A(d1,d2,d3,.,dn)行主序：,數(shù)組中任一元素A(j1,j2,j3,.,jn)的存儲位置，可以通過訪問公式計算，數(shù)組各元素的存取是隨機的，在時間上大致相等，因此，數(shù)組是一種隨機存取的數(shù)據(jù)結(jié)構(gòu)。,16,3.3.1 對稱矩陣的壓縮存儲,1、對稱矩陣,一個m行n列的矩陣共有m*n個數(shù)據(jù)元素。當m=n時，則稱該矩陣為n階方陣。,在程序設(shè)計中，通常將矩陣表示為一個二維數(shù)組。采用

8、順序存儲方式。,若一個n階矩陣A的元素滿足性質(zhì)：aij=aji，1=i,j=n，則稱該矩陣為n階對稱矩陣。,n階對稱矩陣中幾乎一半的元素相同，因此，對于每一對對稱元素可以只分配一個存儲單元。這樣，n階對稱矩陣的n2個元素就可以壓縮到（n*(n+1)/2）個存儲單元中。,17,2、對稱矩陣的壓縮存儲,a11，a12，a13，a1i，a1n a21，a22，a23，a2i，a2n ai1，ai2， ai3， aii， ain an1，an2，an3，ani，ann,18,按行主序存儲對稱矩陣下三角元素。,數(shù)組LTA(1 : (n*(n+1)/2)作為A的存儲結(jié)構(gòu)，A中的任意一個元素aij與LTAk

9、之間存在的對應關(guān)系：,對于每一組下標值(i,j)均可以在LTA中找到元素aij，反之，對于所有k=1，2，(n*(n+1)/2)，都能確定LTAk在矩陣A中的位置(i,j) 。,19,3.3.2 對角矩陣的壓縮存儲,矩陣的所有非零元素都集中在以對角線為中心的帶狀區(qū)域中，即除了主對角線上和直接在主對角線上、下方若干條對角線上的元素外，其余元素皆為零。,1、對角矩陣,對于三對角矩陣B，可以按行（或列）主序方式將對角矩陣B中的所有非零元素壓縮存儲到一個一維數(shù)組LTB1：3n-2中。,20,2、對角矩陣的行主序方式存儲,按行主序方式存儲，則B中任意一個非零元素bij，與LTBk之間存在一一對應關(guān)系，即

10、k = 2*i + j 2時，則有bij =LTBk。,k=3*(i-1)-1 + (j-(i-1)+1 =3i - 4 + j - i + 2 = 2i + j - 2,第i行的非0元素bij 應當是： bi j-1 bi j bi j+1,21,1、稀疏矩陣,3.4 稀疏矩陣的三元組表示,當一個數(shù)組中的元素很多都是0時，該數(shù)組就稱為稀疏數(shù)組。一個矩陣中有許多0元素時，則稱該矩陣為稀疏矩陣。,一個mn的矩陣M，采用順序方式存儲時，需要分配mn個單元；當有許多0元素時，會造成存儲空間的浪費。因此，可以考慮進行壓縮存儲。,一個mn的矩陣M，每個元素可以用一個行標號和列標號來唯一確定它的位置，因此

11、，可以用元素的行和列標號來指示非0元素的位置，同時保存下該非0元素值。即用(i,j,Vij)表示非0元素。,22,2、稀疏矩陣的三元組表示,1 1 15,1 4 22,1 6 -15,2 2 11,2 3 3,3 4 -6,5 1 91,6 3 28,6 6 8,下限為0和1，上限為t和3的二維數(shù)組A(0:t,1:3)來存儲稀疏矩陣的非0元素。t是非0元素個數(shù)。,23,3、稀疏矩陣的轉(zhuǎn)置運算,轉(zhuǎn)置是一種最簡單的矩陣運算。矩陣M轉(zhuǎn)置成另一個矩陣N，應滿足M(i,j) = N(j,i)，1 i m及1 j n。,24,4、三元組表示矩陣的轉(zhuǎn)置,6 6 8,1 1 15,4 1 22,6 1 -15

12、,2 2 11,3 6 28,3 2 3,4 3 -6,1 5 91,25,按列順序?qū)崿F(xiàn)轉(zhuǎn)置：,4 3 -6,6 6 8,1 1 15,4 1 22,6 1 -15,2 2 11,3 2 3,1 5 91,3 6 28,26,算法步驟 （1）從A中讀取矩陣的行數(shù)m、列數(shù)n和非零元素個數(shù)t，并設(shè)置B的行數(shù)為n、列數(shù)為m、非零元素個數(shù)為t； （2）設(shè)置計數(shù)器col=1，表示當前正在轉(zhuǎn)置A的第col列元素（B的第col行）； （3）從A中選擇列號為col的元素，轉(zhuǎn)置后順序存入B； （4）當A中列號為col的元素轉(zhuǎn)置完后，給col加1； （5）如果col不大于n，重復步驟（2）（3）（4），否則結(jié)束，

13、完成轉(zhuǎn)置。,27,void Transpose( int A(ROW,COL) , B(ROW, COL) )； int m, n, t, p, q, Col; m = A0,1; n = A0,2; t = A0,3; B0,1 = n; B0,2 = m; B0,3 = t; if (t0) q = 1; for (col = 1;Col= n; col+) / 當前轉(zhuǎn)置的列號為col / for (p = 1; p = t; p+) if (Ap,2 = col) / 本次需要轉(zhuǎn)置的元素 / Bq,1 = Ap,2; Bq,2 = Ap,1; Bq,3 = Ap,3; q = q + 1

14、; ；/ 一個元素轉(zhuǎn)置 / ；/ 所有元素轉(zhuǎn)置結(jié)束 / ；/ 算法結(jié)束 /,28,5、快速轉(zhuǎn)置,快速轉(zhuǎn)置的思路是： 每行中的非0元素個數(shù)是可以統(tǒng)計出來的； 每個非0元素都有自己最終的存儲位置； 按行進行轉(zhuǎn)置時，直接將元素存入對應位置。,設(shè)置一個數(shù)組Num(n)統(tǒng)計每列（轉(zhuǎn)置后每行）的非0元素個數(shù)；,設(shè)置一個數(shù)組Pot(n)存儲轉(zhuǎn)置后每行第一個非0元素的存儲位置。,29,計算每列的非0元素個數(shù),快速轉(zhuǎn)置過程,for (Col = 1, Col= n Col+) NumCol = 0; for (p=1, p=t, p+) NumAp,2 = NumAp,2+1;,計算轉(zhuǎn)置后每行第一個非0元素的存

15、儲位置：,Pot1 = 1; for (Col = 2, Col = n, Col+) PotCol = PotCol-1 + NumCol-1;,30,6 6 8,1 1 15,2,4 1 22,7,6 1 -15,9,2 2 11,4,5,3 2 3,4 3 -6,8,1 5 91,3,3 6 28,6,31,快速轉(zhuǎn)置算法,void Fast-Transpose(int A(ROW,COL),B(ROW,COL) int m, n, t, p, q, Col; m = A0,1; n = A0,2; t = A0,3; B0,1 = n; B0,2 = m; B0,3 = t; if (t

16、 = 0) return; for (Col=1;Col=n;Col+) NumCol = 0; for (p=1;p=t;p+) NumAp,2 = NumAp,2+1; Pot1 = 1; /計算轉(zhuǎn)置后每行第一個非0元素存儲位置/ for (Col=2;Col=n;Col+) PotCol = PotCol-1+NumCol-1; for (p = 1; p= t; p+) /開始轉(zhuǎn)置/ Col = Ap,2; BPotCol,1 = Ap,2; BPotCol,2 = Ap,1; BPotCol,3 = Ap,3; PotCol = PotCol + 1; /元素轉(zhuǎn)置結(jié)束/ / 算法結(jié)束

17、 /,32,3.5 稀疏矩陣的十字鏈表表示,1、稀疏矩陣的循環(huán)鏈表表示,用鏈表表示稀疏矩陣中的非0元素，需要存儲：行號、列號、元素值；將非零元素以行主序方式用循環(huán)鏈表鏈接起來。,33,2、稀疏矩陣的十字鏈表表示,每個元素按行有一個后繼，按列有一個后繼，因此，需要設(shè)置兩個指針，分別指向行后繼和列后繼元素；,用鏈表表示稀疏矩陣中的非0元素，需要存儲：行號、列號、元素值；,Row、Col、Value分別表示非0元素的行、列和值，Down和Right表示向下（列）和向右（行）指針，分別鏈接同一列和同一行中的非0元素。,34,35,3.6.1 一元多項式的數(shù)組表示,方法1：定義一個一維數(shù)組A1：n+2。

18、其中，A1用來存儲多項式的階數(shù)，從A2開始到An+2，分別存儲n+1個系數(shù)an，an-1，a0。,1、一元n階多項式的數(shù)組表示,例如，多項式A（x）=10 x6 8x5 + 3x2 1，表示成：,36,例如，B（x）=x200+4,方法2：定義一個一維數(shù)組A1：2m+1來表示多項式。其中，第1個元素A1存放多項式中系數(shù)非0項的總項數(shù)m；從第2個元素到第2m+1個元素（共2m個）依次存放系數(shù)非0項的指數(shù)與系數(shù)偶對（共m個偶對）。,37,3.6.2 n階魔方,所謂n階魔方是一個填數(shù)游戲。要求將數(shù)字1n2個數(shù)字不重復地填入到一個由n行n列組成的方陣中，使得方陣中每行、每列、兩個對角線上的數(shù)字之和分別

19、等于同一個數(shù)值。這個方陣就稱為“魔方”。,最早的魔方據(jù)說是大禹治水(公元前2200)在神龜背上看到的3階魔方：,洛書上的3階魔方,38,公元80年出版的古書大戴禮記：“二九四、七五三、六一八”,1977年出土的第二代汝陰侯夏侯灶(公元前165年)墓文物“太乙九宮占盤”八個方位所刻數(shù)字及中心位置的九宮數(shù)字恰為“四九二、三五七、八一六”,南宋楊輝：研究魔方第一人，給出了3、4-10階魔方,39,楊輝4階魔方稱為“花十六圖”或“四四圖”，分陽圖和陰圖,楊輝4階魔方,陰圖生成法：十六子依次四行排列；外角四子互換：1-16、4-13；內(nèi)角四子互換：6-11；7-10,40,如何構(gòu)造魔方,適合于奇數(shù)階魔方 將1設(shè)置在最上行中間，然后按對角線的方向（自右下向左上、或者自左下向右上方向）依次填入數(shù)字；如果到達頂部則轉(zhuǎn)向底部；左（右）邊界則轉(zhuǎn)向右（左邊），如果其上已有數(shù)字則轉(zhuǎn)向下方。,例如n=3 “魔方”為：,1,2,3,4,5,6,7,8,9,1、連續(xù)擺數(shù)法,41,n=5 “魔方”為：,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,42,void MAGIC(int M(ROW,COL)，n) int