西電初試專業(yè)課講義數(shù)據(jù)結(jié)構(gòu)ch05arraygl

1、第五章 數(shù)組和廣義表本章內(nèi)容5.1 數(shù)組的定義5.2 數(shù)組的順序表示5.3 矩陣的壓縮存儲(chǔ) 5.3.1 特殊矩陣 5.3.2 稀疏矩陣5.4 廣義表的定義5.5 廣義表的存儲(chǔ)結(jié)構(gòu)5.1數(shù)組的定義數(shù)組是我們很熟悉的一種數(shù)據(jù)結(jié)構(gòu)，它可以看作線性表的推廣。數(shù)組作為一種數(shù)據(jù)結(jié)構(gòu)其特點(diǎn)是結(jié)構(gòu)中的元素本身可以是具有某種結(jié)構(gòu)的數(shù)據(jù)，但屬于同一數(shù)據(jù)類型，比如：一維數(shù)組可以看作一個(gè)線性表，二維數(shù)組可以看作“數(shù)據(jù)元素是一維數(shù)組”的一維數(shù)組，三維數(shù)組可以看作“數(shù)據(jù)元素是二維數(shù)組”的一維數(shù)組，依此類推。 由于數(shù)組中各元素具有統(tǒng)一的類型，并且數(shù)組元素的下標(biāo)一般具有固定的上界和下界，因此，數(shù)組的處理比其它復(fù)雜的結(jié)構(gòu)更為簡(jiǎn)

2、單。多維數(shù)組是一維數(shù)組的推廣。例如，二維數(shù)組A： 5.1數(shù)組的定義(續(xù))Amn=a11 a12 a1na21 a22 a2n am1 am2 amn二維數(shù)組A可以看成是由m個(gè)行向量組成的向量，也可以看成是n個(gè)列向量組成的向量。數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。因此，除了結(jié)構(gòu)的初始化和銷毀之外，數(shù)組只有存取元素和修改元素值的操作。 由于計(jì)算機(jī)的內(nèi)存結(jié)構(gòu)是一維的，因此用一維內(nèi)存來(lái)表示多維數(shù)組，就必須按某種次序?qū)?shù)組元素排成一列序列，然后將這個(gè)線性序列存放在存儲(chǔ)器中。數(shù)組一旦建立，結(jié)構(gòu)中的元素個(gè)數(shù)和元素間的關(guān)系就不再發(fā)生變化。因此，一般采用順序存儲(chǔ)的方法來(lái)表示數(shù)組。5.2 數(shù)組的順序表示行優(yōu)

3、先順序或以行為主序存儲(chǔ)方式：將數(shù)組元素按行排列，第i+1個(gè)行向量緊接在第i個(gè)行向量后面。以二維數(shù)組為例，按行優(yōu)先順序存儲(chǔ)的線性序列為： a11,a12,a1n,a21,a22,a2n,am1,am2,amn 在PASCAL、C等語(yǔ)言中，數(shù)組就是按行優(yōu)先順序存儲(chǔ)的。5.2 數(shù)組的順序表示(續(xù))Amn=a11 a12 a1na21 a22 a2n am1 am2 amnLOC(aij)=LOC(a11)+(i-1)*n+j-1*d列優(yōu)先順序或以列為主序存儲(chǔ)方式：將數(shù)組元素按列向量排列，第j+1個(gè)列向量緊接在第j個(gè)列向量之后，A的m*n個(gè)元素按列優(yōu)先順序存儲(chǔ)的線性序列為： a11,a21,am1,a

4、12,a22,am2,an1,an2,anm在FORTRAN語(yǔ)言中，數(shù)組按列優(yōu)先順序存儲(chǔ)。5.2 數(shù)組的順序表示(續(xù))Amn=a11 a12 a1na21 a22 a2n am1 am2 amnLOC(aij)=LOC(a11)+(j-1)*m+i-1*d行優(yōu)先順序先排最右的下標(biāo)，從右到左，最后排最左下標(biāo)。列優(yōu)先順序先排最左下標(biāo)，從右向左，最后排最左下標(biāo)。例如：三維數(shù)組Am*n*p5.2 數(shù)組的順序表示(續(xù))只要知道開始結(jié)點(diǎn)的存放地址（即基地址）、維數(shù)和每維的上、下界，以及每個(gè)數(shù)組元素所占用的單元數(shù)，就可以將數(shù)組元素的存放地址表示為其下標(biāo)的線性函數(shù)。因此，數(shù)組中的任一元素可以在相同的時(shí)間內(nèi)存取

5、，即順序存儲(chǔ)的數(shù)組是一個(gè)隨機(jī)存取結(jié)構(gòu)。數(shù)組存儲(chǔ)的特點(diǎn)Example壓縮存儲(chǔ)：為多個(gè)值相同的非零元素只分配一個(gè)存儲(chǔ)空間；對(duì)零元素不分配空間。5.3 矩陣的壓縮存儲(chǔ)特殊矩陣：非零元素按照一定的規(guī)律分布。5.3.1特殊矩陣的壓縮存儲(chǔ)a1,1 a1,2 a1,na2,1 a2,2 a2,n ai,j an,1 an,2 an,naij=aji1 2 3 42 1 3 43 3 1 44 4 4 1對(duì)稱矩陣常見的特殊矩陣有對(duì)稱矩陣、三角矩陣、對(duì)角矩陣等。對(duì)稱矩陣：元素的值按照主對(duì)角線對(duì)稱5.3.1(續(xù))對(duì)稱矩陣的壓縮存儲(chǔ)對(duì)稱矩陣1 2 3 42 1 3 43 3 1 44 4 4 11 2 3 42 1

6、 3 4 3 3 1 4 4 4 4 11213314441數(shù)組B12345678910下標(biāo)k例如：一個(gè)4*4的對(duì)稱矩陣。5.3.1(續(xù))對(duì)稱矩陣的壓縮存儲(chǔ)對(duì)稱矩陣數(shù)組Bai,jan,na1,1a2,1a2,2a3,11234km下標(biāo)a1,1 a1,2 a1,na2,1 a2,2 a2,n ai,j an,1 an,2 an,na1,1a2,1 a2,2 ai,j an,1 an,2 an,n k = ? m = ?推廣至一般情況，n*n的對(duì)稱矩陣5.3.1(續(xù))三角矩陣的壓縮存儲(chǔ)1 0 0 02 1 0 03 3 1 04 4 4 11 2 3 40 1 3 40 0 1 40 0 0 1(

7、a) 下三角矩陣(a) 上三角矩陣三角矩陣：上(下)三角矩陣是指矩陣的下（上）三角（不包括對(duì)角線）中的元素均為常數(shù)或零的n階矩陣，即非零元素的分布在矩陣中呈現(xiàn)為三角形。例如：一個(gè)4*4的三角矩陣。5.3.1(續(xù))三角矩陣的壓縮存儲(chǔ)1 8 8 82 1 8 83 3 1 84 4 4 11 2 3 49 1 3 49 9 1 49 9 9 1(c) 下三角矩陣(d) 上三角矩陣?yán)纾阂粋€(gè)4*4的三角矩陣。5.3.1(續(xù))三角矩陣的壓縮存儲(chǔ)a0,0 a0,1 a0,2 a0,n-2 a0, n-1 a1,1 a1,2 a1,n-2 a1, n-1 ai,i ai,j ai, n-1 an-1, n

8、-1 0a0,0a0,1a0,2a0,3ai,jan-1, n-1b1b2b3b4bkbm k = ? m = ?推廣至一般情況，n*n的三角矩陣以行為主序壓縮存儲(chǔ)5.3.1(續(xù))三角矩陣的壓縮存儲(chǔ)a0,0 a0,1 a0,2 a0,n-2 a0, n-1 a1,1 a1,2 a1,n-2 a1, n-1 ai,i ai,j ai, n-1 an-1, n-1 0a0,0a0,1a1,1a0,2ai,jan-1, n-1b1b2b3b4bkbm k = ? m = ?a1,2b5a2,2b6推廣至一般情況，n*n的三角矩陣以列為主序壓縮存儲(chǔ)5.3.1(續(xù))三對(duì)角矩陣的壓縮存儲(chǔ)a0,0 a0,1

9、a1,0 a1,1 a1,2 a2,1 a2,2 a2,3 . ai,j . an-2,n-3 an-2,n-2 an-2,n-1 an-1,n-2 an-1, n-1a0,0a0,1a1,0ai,j數(shù)組B12kk+1m下標(biāo)0. k = ? m = ?對(duì)角矩陣是指所有的非零元素都集中在以主對(duì)角線為中心的帶狀區(qū)域中。上述各種特殊矩陣，其非零元素的分布都是有規(guī)律的，因此總能找到一種方法將它們壓縮存儲(chǔ)到一維數(shù)組中，并且一般都能找到矩陣中的元素與該一維數(shù)組元素的對(duì)應(yīng)關(guān)系，通過(guò)這個(gè)關(guān)系，仍能對(duì)矩陣的元素進(jìn)行隨機(jī)存取。5.3.1(續(xù))特殊矩陣的壓縮存儲(chǔ)Example什么是稀疏矩陣？簡(jiǎn)單說(shuō)，設(shè)矩陣A中有s個(gè)

10、非零元素，若s遠(yuǎn)遠(yuǎn)小于矩陣元素的總數(shù)（即smn），則稱A為稀疏矩陣。設(shè)在矩陣A中，有s個(gè)非零元素。令 e=s/(m*n)，稱e為矩陣的稀疏因子。通常認(rèn)為e0.05時(shí)稱之為稀疏矩陣。5.3.2稀疏矩陣5.3.2稀疏矩陣的壓縮存儲(chǔ)在存儲(chǔ)稀疏矩陣時(shí)，由于非零元素的分布一般是沒有規(guī)律的，因此在存儲(chǔ)非零元素的同時(shí)，還必須同時(shí)記下它所在的行和列的位置（i,j)。反之，一個(gè)三元組(i,j,aij)惟一確定了矩陣A的一個(gè)非零元。因此，稀疏矩陣可由表示非零元的三元組及其行列數(shù)唯一確定。 ( (1,2,12), (1,3,9), (3,1,-3), (3,6,14), (4,3,24), (5,2,18), (6

11、,1,15), (6,4,-7) )5.3.2稀疏矩陣的壓縮存儲(chǔ)M= 0 12 9 0 0 0 0 0 0 0 0 0 0 0-3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 015 0 0 7 0 0 0例如，一個(gè)6*7的稀疏矩陣稀疏矩陣中的非零元素假設(shè)以順序存儲(chǔ)結(jié)構(gòu)來(lái)表示三元組表，則可得到稀疏矩陣的一種壓縮存儲(chǔ)方法三元組順序表。 #define maxsize 10000 typedef int datatype; typedef struct int i,j; datatype v; triple; /* 三元組*/5.3.2(續(xù))稀疏矩陣的壓縮存儲(chǔ)

12、typedef struct triple datamaxsize; int m,n,t; tripletable;5.3.2(續(xù))三元組順序表M= 0 12 9 0 0 0 0 0 0 0 0 0 0 0-3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 015 0 0 7 0 0 0i j v 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 12345678轉(zhuǎn)置MT= 0 0 -3 0 0 1512 0 0 0 18 0 9 0 0 24 0 0 0 0 0 0 0 -7 0 0 0 0 0

13、0 0 0 14 0 0 0 0 0 0 0 0 0M= 0 12 9 0 0 0 0 0 0 0 0 0 0 0-3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 015 0 0 7 0 0 05.3.2(續(xù))三元組順序表上的轉(zhuǎn)置i j v 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 12345670轉(zhuǎn)置i j v 2 1 12 3 1 9 1 3 -3 6 3 14 3 4 24 2 5 18 1 6 15 4 6 -7 12345670排序i j v 1 3 -3 1 6 15 2 1

14、12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 12345670typedef struct triple datamaxsize; int m,n,t;tripletable;Void transmatrix(tripletable A, tripletable &AT) AT.m=A.n; AT.n=A.m; AT.t=A.t; if (AT.t=0) return; for(p=0;pA.t;+p) AT.datap.i = AT.datap.j; AT.datap.j = AT.datap.i; AT.datap.v = AT.datap.v; /按照AT.d

15、atap.i進(jìn)行非遞減排序 5.3.2(續(xù))三元組順序表5.3.2(續(xù))三元組順序表上的轉(zhuǎn)置(二)轉(zhuǎn)置i j v 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 12345670i j v 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 12345670設(shè)置向量num,numcol表示矩陣A中第col列中非零元的個(gè)數(shù)。(A的列數(shù)：A.n)5.3.2(續(xù))三元組順序表上的轉(zhuǎn)置(二)for(col=1;col=A.n;+col) numcol = 0;for(p=1;p=A.

16、t;+p) /計(jì)算A中每列非零元的個(gè)數(shù) numA.datap.j+;列號(hào)設(shè)置向量cpot,cpotcol指示A中第col列的第一個(gè)非零元在轉(zhuǎn)置矩陣AT.data中的恰當(dāng)位置。5.3.2(續(xù))三元組順序表上的轉(zhuǎn)置(二)cpot1=1cpotcol=cpotcol-1+numcol-1 2colA.ncpot1=1;for(col = 2; col=A.n; +col) cpotcol=cpotcol-1+numcol-1;5.3.2(續(xù))三元組順序表上的轉(zhuǎn)置(二)cpot1357889 1 2 3 4 5 6 7num2221010M= 0 12 9 0 0 0 0 0 0 0 0 0 0 0-

17、3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 015 0 0 7 0 0 0轉(zhuǎn)置i j v 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 23456781i j v 23456781cpot1357889 1 2 3 4 5 6 72 1 12三元組順序表上的轉(zhuǎn)置(二續(xù))轉(zhuǎn)置i j v 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 23456781i j v 23456781cpot1457889 1 2 3 4 5 6 72

18、1 12三元組順序表上的轉(zhuǎn)置(二續(xù))轉(zhuǎn)置i j v 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 23456781i j v 23456781cpot1457889 1 2 3 4 5 6 72 1 123 1 9三元組順序表上的轉(zhuǎn)置(二續(xù))轉(zhuǎn)置i j v 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 23456781i j v 23456781cpot1467889 1 2 3 4 5 6 72 1 123 1 9三元組順序表上的轉(zhuǎn)置(二續(xù))轉(zhuǎn)置i j v 1 2

19、12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 23456781i j v 23456781cpot1467889 1 2 3 4 5 6 72 1 123 1 91 3 -3三元組順序表上的轉(zhuǎn)置(二續(xù))轉(zhuǎn)置i j v 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 23456781i j v 23456781cpot2467889 1 2 3 4 5 6 72 1 123 1 96 3 141 3 -3三元組順序表上的轉(zhuǎn)置(二續(xù))轉(zhuǎn)置i j v 1 2 12 1 3 9 3 1

20、 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 23456781i j v 23456781cpot2467899 1 2 3 4 5 6 72 1 123 1 93 4 241 3 -36 3 14三元組順序表上的轉(zhuǎn)置(二續(xù))轉(zhuǎn)置i j v 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 23456781i j v 23456781cpot2477899 1 2 3 4 5 6 72 1 123 1 92 5 181 3 -36 3 143 4 24三元組順序表上的轉(zhuǎn)置(二續(xù))轉(zhuǎn)置i j v 1 2

21、12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 23456781i j v 23456781cpot2577899 1 2 3 4 5 6 72 1 123 1 91 6 151 3 -36 3 143 4 242 5 18三元組順序表上的轉(zhuǎn)置(二續(xù))轉(zhuǎn)置i j v 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 23456781i j v 23456781cpot3577899 1 2 3 4 5 6 72 1 123 1 94 6 -71 3 -36 3 143 4 242

22、5 181 6 15三元組順序表上的轉(zhuǎn)置(二續(xù))for(col=1;col=A.n;+col) numcol = 0;for(p=1;p=A.t;+p) /計(jì)算A中每列非零元的個(gè)數(shù) numA.datap.j+;5.3.2(續(xù))三元組順序表上的轉(zhuǎn)置(二)cpot1=1;for(col = 2; col=A.n; +col) /計(jì)算元素位置 cpotcol=cpotcol-1+numcol-1;for(col=1;col=A.n;+col) numcol = 0;for(p=1;p=A.t;+p) /計(jì)算A中每列非零元的個(gè)數(shù) numA.datap.j+;cpot1=1;for(col = 2; c

23、ol=A.n; +col) /計(jì)算元素位置 cpotcol=cpotcol-1+numcol-1;for(p = 1; p=A.t; +p) /轉(zhuǎn)置 col = A.datap.j; q = cpotcol; AT.dataq.i = A.datap.j; AT.dataq.j = A.datap.i; AT.dataq.v = A.datap.v; cpotcol+; 十字鏈表121213931-3361443245218611564-75.3廣義表的定義廣義表是線性表的推廣。L=(a1,a2,.,an ),n0,ai可以是單元素，也可以是一個(gè)表。例如：A = ( )：A是一個(gè)空表。B =

24、(e)：B只有一個(gè)原子。C = (a, (b,c,d) )：C有一個(gè)原子和一個(gè)子表。D = (A, B, C)：D有3個(gè)子表。E = (a, E) = (a, (a, (a, , ) )：E是一個(gè)遞歸的表。5.3廣義表的定義廣義表 LS = ( 1, 2, , n )的結(jié)構(gòu)特點(diǎn):廣義表中的數(shù)據(jù)元素有相對(duì)次序;廣義表的長(zhǎng)度定義為表中的元素個(gè)數(shù);廣義表的深度定義為表的嵌套層數(shù); 注意:“原子”的深度為 0 ; “空表”的深度為 1 。廣義表可以共享;廣義表可以是一個(gè)遞歸的表; 遞歸表的深度是無(wú)窮值，長(zhǎng)度是有限值。5.4 廣義表的定義廣義表是一個(gè)多層次的線性結(jié)構(gòu)例: D=(E, F)其中: E=(a

25、, (b, c) F=(d, (e)DEFa( )d( )bce5.4 廣義表的定義例：A = ( )：長(zhǎng)度為0，深度為1。B = (e)：長(zhǎng)度為1，深度為1 。C = (a, (b,c,d) )：長(zhǎng)度為2，深度為2 。D = (A, B, C)：長(zhǎng)度為3，深度為3 。E = (a, E) = (a, (a, (a, , ) )：長(zhǎng)度為2，深度為 。5.4 廣義表的定義任何一個(gè)非空廣義表 LS = ( 1, 2, , n) 均可分解表頭和表尾兩部分:表頭(Head)：第一個(gè)元素Head(LS) = 1表尾(Tail)：除第一個(gè)元素外其余元素構(gòu)成的表Tail(LS) = ( 2, , n)例如:

26、 D = ( E, F ) = (a, (b, c), F )Head( D ) = E Tail( D ) = ( F )Head( E ) = a Tail( E ) = ( ( b, c) )Head( ( b, c) ) = ( b, c) Tail( ( b, c) ) = ( )Head( ( b, c) ) = b Tail( ( b, c) ) = ( c )Tail( Head(Head(a, (b, c), F ) = ?5.4 廣義表的定義基本操作結(jié)構(gòu)的創(chuàng)建和銷毀InitGList(&L); DestroyGList(&L);CreateGList(&L, S); Cop

27、yGList(&T, L);狀態(tài)函數(shù)GListLength(L); GListDepth(L);GListEmpty(L); GetHead(L); GetTail(L);插入和刪除操作InsertFirst_GL(&L, e);DeleteFirst_GL(&L, &e);遍歷Traverse_GL(L, Visit()廣義表的存儲(chǔ)結(jié)構(gòu)(一)鏈表存儲(chǔ)C = (a,(b,c,d)D = (A,B,C)E = (a,E)鏈表結(jié)點(diǎn)結(jié)構(gòu)tag=1hptp表結(jié)點(diǎn)tag=0atom原子結(jié)點(diǎn)廣義表的存儲(chǔ)結(jié)構(gòu)(一)C = (a,(b,c,d)C10aHead(C) = a Tail(C)=(b,c,d)1廣義表的存儲(chǔ)結(jié)構(gòu)(一)C = (a,(b,c,d)C10a1Head(C) = a Tail(C)=(b,c,d)1(b,c,d)廣義表的存儲(chǔ)結(jié)構(gòu)(一)C = (a,(b,c,d)C10a110b10c10dHead(C) = a Tail(C)=(b,c,d)(b,c,d)(c,d)(d)廣義表的存儲(chǔ)結(jié)構(gòu)(一)C = (a,(b,c,d)C10a110b10c10dB= (e)C10a110b10c10d10eBA= ()C10a110b10c10d10eBAD= (A,