維數(shù)組和廣義表

第4章多維數(shù)組和廣義表4.1多維數(shù)組4.2數(shù)組的存儲結(jié)構(gòu)4.3矩陣的壓縮存儲特殊矩陣和特殊矩陣4.4廣義表的根本概念1整理課件線性表——具有相同類型的數(shù)據(jù)元素的有限序列。限制插入、刪除位置線性表——具有相同類型的數(shù)據(jù)元素的有限序列。限制元素類型為字符棧——僅在表尾進行插入和刪除操作的線性表。隊列——在一端進行插入操作，而另一端進行刪除操作的線性表。串——零個或多個字符組成的有限序列。特殊線性表2整理課件線性表——具有相同類型的數(shù)據(jù)元素的有限序列。將元素的類型進行擴充廣義線性表（多維）數(shù)組——線性表中的數(shù)據(jù)元素可以是線性表，但所有元素的類型相同。廣義表——線性表中的數(shù)據(jù)元素可以是線性表，且元素的類型可以不相同。3整理課件4.1多維數(shù)組多維數(shù)組可看成線性表的推廣。一維數(shù)組：就是線性表；二維數(shù)組：每個元素為一維數(shù)組的線性表，這個元素可以是行向量，也可以是列向量。三維數(shù)組：每個元素為二維數(shù)組的線性表。n維數(shù)組：每個元素為n?1維數(shù)組的線性表。非線性：元素受多個線性關(guān)系〔如行、列〕的約束，可多個前驅(qū)和后繼。元素類型相同，元素個數(shù)和元素間關(guān)系在數(shù)組建立后一般不能改變。4整理課件constintm=10;constintn=5;typedefintR[n];Rx[m];intx[m][n];constintm=10;constintn=5;typedefintA[m][n];Ax;根本運算——讀和寫：〔1〕讀：給定一組下標，讀出相應的元素?！?〕寫：給定一組下標，修改相應的元素。存取和修改操作本質(zhì)上只對應一種操作——尋址5整理課件4.2數(shù)組的存儲結(jié)構(gòu)A[0..n]：LOC(i)=LOC(0)+i×cA[1..n]：LOC(i)=LOC(1)+(i?1)×c沒有插入和刪除運算，采用順序存儲方式

一、一維數(shù)組：設一維數(shù)組的下標的范圍為閉區(qū)間［s，t］，每個數(shù)組元素占用c個存儲單元，那么其任一元素ai的存儲地址可由下式確定：Loc(ai)＝Loc(as)＋(i－s)×ccasai-1ai……atas+1……Loc(ai)6整理課件4.2數(shù)組的存儲結(jié)構(gòu)非線性結(jié)構(gòu)，但內(nèi)存單元是一維的線性結(jié)構(gòu)，在進行順序存儲時，需要將多維關(guān)系映射為一維的線性關(guān)系。二、二維數(shù)組：常用的映射方法有兩種：按行優(yōu)先：先行后列，先存儲行號較小的元素，行號相同者先存儲列號較小的元素。

按列優(yōu)先：先列后行，先存儲列號較小的元素，列號相同者先存儲行號較小的元素。

二維數(shù)組內(nèi)存二維結(jié)構(gòu)一維結(jié)構(gòu)7整理課件行優(yōu)先：按行排列，如PASCAL、C，對A[1..m][1..n]:a11,a12,…,a1n,a21,a22,…a2n,……,am1,am2,…,amn對A[s..t][q..r]:

h=(i?s)×(r?q+1)+(j?q+1)

LOC(i,j)=LOC(s,q)+(h?1)×c

=LOC(s,q)+[(i?s)×(r?q+1)+(j?q)]×c對A[1..m][1..n]:

LOC(i,j)=LOC(1,1)+[(i?1)×n+(j?1)]×c對A[0..m-1][0..n-1]，即C數(shù)組A[m][n]:

LOC(i,j)=LOC(0,0)+[i×n+j]×c列優(yōu)先：按列排列，如FORTRAN，對A[1..m][1..n]a11,a21,…,am1,a12,a22,…am2,……,an1,an2,…,anm提問：列優(yōu)先時，元素相對位置如何計算？8整理課件行優(yōu)先：對每一個左下標，逐個變動其右邊的下標〔右下標先動〕，或說，先排最右的下標，從右到左，最后排最左下標。列優(yōu)先：對每一個右下標，逐個變動其左邊的下標〔左下標先動〕，或說，先排最左的下標，從左向右，最后排最右下標。如三維數(shù)組A[2..3,0..1,1..3]，按行存儲：a201,a202,a203,a211,a212,a213,a301,a302,a303,a311,a312,a313三維數(shù)組A[1..m,1..n,1..p]，按行存儲：LOC(i,j,k)=LOC(1,1,1)+[(i?1)×n×p+(j?1)×p+(k?1)]×c

不管是按行存儲還是按列存儲，數(shù)組元素的地址都是其下標的線性函數(shù)，任一元素都可在相同的〔邏輯〕時間內(nèi)存取，故數(shù)組是一種隨機存取結(jié)構(gòu)。三、多維數(shù)組：m頁,每頁n行p列四維：A[1..m,1..n,1..p,1..q]？9整理課件數(shù)組A[0..4,-1..-3,5..7]中含有元素的個數(shù)〔〕。A.55B.45C.36D.16設二維數(shù)組A[1..m，1..n]〔即m行n列〕按行存儲在數(shù)組B[1..m*n]中，那么二維數(shù)組元素A[i，j]在一維數(shù)組B中的下標為()。A.〔i-1〕*n+jB.〔i-1〕*n+j-1C.i*〔j-1〕D.j*m+i-1BA10整理課件二維數(shù)組A的元素都是6個字符組成的串，行下標i的范圍從0到8，列下標j的范圈從1到10。從供選擇的答案中選出應填入以下關(guān)于數(shù)組存儲表達中〔〕內(nèi)的正確答案?！?〕存放A至少需要〔〕個字節(jié)；〔2〕A的第8列和第5行共占〔〕個字節(jié)；供選擇的答案：〔1〕A.90B.180C.270D.540〔2〕A.108B.114C.54D.60D有9+10-1=18個元素(8-0+1)*(10-1+1)*6A11整理課件4.3矩陣壓縮存儲如果矩陣的非零元素呈某種規(guī)律分布，或者有大量的零元素，那么沒有必要屢次重復存儲相同的非零元素或零元素，如對相同的非零元素只分配一個存儲空間，對零元素不分配空間，從而節(jié)省存儲空間。這就是矩陣的壓縮存儲。以下僅討論下標從1開始特殊矩陣：非零元素或零元素的分布有一定規(guī)律的矩陣稀疏矩陣：非零元素個數(shù)s遠遠小于矩陣元素總數(shù)〔s<<m×n〕12整理課件4.3.1特殊矩陣(1)對稱矩陣：n階方陣A[n][n]，滿足a[i][j]=a[j][i]元素關(guān)于主對角線對稱，可只存上三角或下三角，即每兩個對稱的元素共享一個存儲空間。所需空間1+2+…+n=n(n+1)/2，節(jié)約一半左右。對上三角或下三角局部，又可按行或按列存儲，故對稱矩陣一般有4種不同的存儲方式。如何壓縮存儲？13整理課件(2)k，求i、j：由于1≤j≤i，所以i(i?1)/2+1≤k≤i(i?1)/2+i=i(i+1)/2即i2?i?2k+2≤0且i2+i?2k≥0，解該不等式組，得(1)i、j，求k：k=[1+2+…+(i?1)]+j=i(i?1)/2+j(i≥j)LOC(i,j)=LOC(k)=LOC(1)+(k?1)×c如果i<j,那么aij的值存放在aji對應的存儲空間，k=j(j-1)/2+i;求出i后便可得j=k?i(i?1)/2。aij和V[k]一一對應下三角，按行存稱V[1..n(n+1)/2]為對稱矩陣A的壓縮存儲14整理課件(2)三角矩陣下三角〔上三角〕矩陣：矩陣A[n][n]主對線上方〔或下方〕的元素全部相同，均為常數(shù)c。多數(shù)情況下，常數(shù)c為零。重復的c只存儲一次，其余n(n+1)/2個，故將三角矩陣存儲到向量V[1..n(n+1)/2+1]中，其中常數(shù)c存放在向量的最后。如下三角，按行存：15整理課件對角矩陣對角矩陣：除了主對角線及其鄰近的上下假設干條次對角線上的元素外，其余元素皆為零。非零元素集中在以主對角線為中心的帶狀區(qū)域中，是帶狀矩陣中的一種。將對角矩陣首、末行各補一個虛元素，那么每行的非零元素個數(shù)都相同，可壓縮到二維數(shù)組Bn×w中〔w為帶寬〕。bi’j’和aij的對應關(guān)系如下：16整理課件例設有3對角矩陣A[1..n,1..n]，將對角線上的元素按行存于一維數(shù)組B[1..3n?2]中，使得B[k]=A[i,j]。求：〔1〕用i、j表示k的下標變換公式；〔2〕用k表示i、j的下標變換公式?！?〕k=[3(i?1)?1]+[j?(i?1)+1]=2i+j?2〔2〕由于i?1≤j≤i+1，所以2i+(i?1)?2≤k≤2i+(i+1)?2，即3i?3≤k≤3i?1，從而(k+1)/3≤i≤(k+3)/3。于是：k/3<i≤k/3+1，由于i為整數(shù)，所以i=k/3+1?；蛘撸?k+1)/3≤i<(k+1)/3+1，所以i=(k+1)/3

求出i后，將它帶入上面k的表達式，便可得：j=k?2i+2=k-2k/3

，或j=k+2?2(k+1)/3

。17整理課件將一個A[1..100，1..100]的三對角矩陣，按行優(yōu)先存入一維數(shù)組B[1‥298]中，A中元素A6665〔即該元素下標i=66，j=65〕，在B數(shù)組中的位置K為〔〕。A.198B.195C.197D.194A[N，N]是對稱矩陣，將下面三角〔包括對角線〕以行序存儲到一維數(shù)組T[N〔N+1〕/2]中，那么對任一上三角元素a[i][j]對應T[k]的下標k是〔〕。A.i〔i-1〕/2+jB.j〔j-1〕/2+iC.i〔j-i〕/2+1D.j〔i-1〕/2+1BB18整理課件4.3.2稀疏矩陣為節(jié)省存儲單元，只存非零元。非零元分布一般沒有規(guī)律，存儲次序無法反映邏輯關(guān)系，必須顯式存儲行列邏輯次序。1500000

0110000

000600

0000009

00000A=如何只存儲非零元素？將非零元的值和行號、列號作為一個結(jié)點存放，于是每一個非零元素由一個三元組〔行號,列號,元素值〕唯一確定。稀疏矩陣的壓縮存儲會失去隨機存取功能。19整理課件1三元組表三元組表：三元組按行序〔或列序〕排列的順序存儲結(jié)構(gòu)。三元組表是稀疏矩陣的一種順序存儲結(jié)構(gòu)。一般還要指出當前表的長度，即非零元的個數(shù)。要唯一確定稀疏矩陣，還必須知道矩陣的行數(shù)和列數(shù)。constintmaxsize=100; //三元組表的容量typedefstruct{inti,j; //行號、列號

datatypeval; //元素值}nodetype; //三元組結(jié)點類型typedefstruct{intm,n; //行數(shù)、列數(shù)

intt; //當前表長，非零元素個數(shù)

nodetypedata[maxsize];//三元組表}spmatrix; //稀疏矩陣類型20整理課件轉(zhuǎn)置假設直接將三元組的行號和列號互換，那么轉(zhuǎn)置后的三元組將不是按行序而是按列序排列的，這時需要對三元組重新排序。21整理課件按列序轉(zhuǎn)置，順序存放矩陣B的行就是矩陣A的列，將A的三元組表按列序轉(zhuǎn)置，得到的B的三元組表必定按行序排列。voidtrans(spmatrix*A,spmatrix*B){intpa,pb,col;B?>m=A?>n;B?>n=A?>m;B?>t=A?>t;if(A?>t<1)return; //沒有非零元

pb=0; //pb為B中三元組表當前空位置

for(col=0;col<A?>n;col++)//對A所有列循環(huán)

for(pa=0;pa<A?>t;pa++)//對A三元組循環(huán)，找列號

if(A?>data[pa].j==col){B?>data[pb].i=A?>data[pa].j;B?>data[pb].j=A?>data[pa].i;B?>data[pb].val=A?>data[pa].val;pb++;}}○(n×

t)

22整理課件2行鏈表每行的非零元做成鏈表?！?11∧841∧152-523∧-15412345∧243找同一列上的非零元不方便。類似，可建列鏈表；找列元素方便，找行元素不方便。23整理課件4.4廣義表的根本概念廣義表〔Lists，又稱列表〕：n(n≥0)個元素a1,a2,a3,…,an的有限序列，其中ai或者是原子，或者是一個廣義表。通常記作LS=〔a1,a2,a3,…,an)。LS是廣義表的名字，n為它的長度。假設ai是廣義表，那么稱它為LS的子表。遞歸定義，在定義廣義表時又用到了廣義表的概念。為了區(qū)分原子和廣義表，大寫字母表示廣義表，用小寫字母表示原子。對非空廣義表，其第一個元素稱為表頭，其余元素組成的表稱為表尾。廣義表展開后所含括號的最大嵌套層數(shù)稱為深度。遞歸表：允許廣義表的成員內(nèi)含有廣義表自己再入表〔ReentrantList〕：允許元素共享的廣義表。純表〔PureList〕：表中沒有共享和遞歸的成分，即沒有任何成分出現(xiàn)屢次。24整理課件A

＝()B

＝(e)C

＝(a,(b，c，d))D

＝(A,B,C)E＝(a,E)F＝(())廣義表的圖形表示ABeCabcdD分支結(jié)點對應廣義表，非分支結(jié)點〔即葉子〕對應原子或空表。25整理課件A=()空表，無表頭，無表尾，長度為0，深度為1。注意空表沒有表頭也沒有表尾。B=(A)=(())表頭為()，表尾為()，長度為1，深度為2。這里表頭和表尾都為空表。C=(a,b)表頭為a，表尾為(b)，長度為2，深度為1。這是線性表。D=(C,x)=((a,b),x)表頭為(a,b)，表尾為(x)，長度為2，深度為2。E=(y,D)=(y,(C,x))=(y,((a,b),x))表頭為y，表尾為(D)，長度為2，深度為3。F=(C,D)=((a,b),((a,b),x))表頭為C，表尾為(D)，長度為2，深度為3。這是再入表。G=(z,G)=(z,(z,(z,(…))))表頭為z，表尾為(G)，長度為2，深度為∞。這是遞歸表。26整理課件線性表∈純表∈再入表∈遞歸表沒有共享和遞歸成分的純表(a)～(e)相當于樹形結(jié)構(gòu)；有共享成分的再入表(f)相當于有向無環(huán)圖〔DAG〕；有遞歸成分的遞歸表(g)相當于有回路的有向圖。廣義表不僅是線性表的推廣，也是樹的推廣。27整理課件例通過取表頭head(LS)和取表尾tail(LS)運算，從廣義表A=(x,(a,b),y)中取出原子b。在廣義表中取某個元素，需要將該元素所在的子表逐步別離出來，直到所求的元素成為某個子表的表頭，再用取表頭運算取