1、DATA STRUCTURE,2020/7/30,2,第五章 數(shù)組和廣義表,本章內容 5.1 數(shù)組的定義 5.2 數(shù)組的順序表示 5.3 矩陣的壓縮存儲 5.3.1 特殊矩陣 5.3.2 稀疏矩陣 5.4 廣義表的定義 5.5 廣義表的存儲結構,2020/7/30,3,5.1數(shù)組的定義,數(shù)組是我們很熟悉的一種數(shù)據(jù)結構，它可以看作線性表的推廣。數(shù)組作為一種數(shù)據(jù)結構其特點是結構中的元素本身可以是具有某種結構的數(shù)據(jù)，但屬于同一數(shù)據(jù)類型，比如：一維數(shù)組可以看作一個線性表，二維數(shù)組可以看作“數(shù)據(jù)元素是一維數(shù)組”的一維數(shù)組，三維數(shù)組可以看作“數(shù)據(jù)元素是二維數(shù)組”的一維數(shù)組，依此類推。,由于數(shù)組中各元素具有

2、統(tǒng)一的類型，并且數(shù)組元素的下標一般具有固定的上界和下界，因此，數(shù)組的處理比其它復雜的結構更為簡單。多維數(shù)組是一維數(shù)組的推廣。,2020/7/30,4,例如，二維數(shù)組A：,5.1數(shù)組的定義(續(xù)),二維數(shù)組A可以看成是由m個行向量組成的向量，也可以看成是n個列向量組成的向量。 數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。因此，除了結構的初始化和銷毀之外，數(shù)組只有存取元素和修改元素值的操作。,2020/7/30,5,由于計算機的內存結構是一維的，因此用一維內存來表示多維數(shù)組，就必須按某種次序將數(shù)組元素排成一列序列，然后將這個線性序列存放在存儲器中。 數(shù)組一旦建立，結構中的元素個數(shù)和元素間的關系就不再發(fā)

3、生變化。因此，一般采用順序存儲的方法來表示數(shù)組。,5.2 數(shù)組的順序表示,2020/7/30,6,行優(yōu)先順序或以行為主序存儲方式：將數(shù)組元素按行排列，第i+1個行向量緊接在第i個行向量后面。以二維數(shù)組為例，按行優(yōu)先順序存儲的線性序列為： a11,a12,a1n,a21,a22,a2n,am1,am2,amn 在PASCAL、C等語言中，數(shù)組就是按行優(yōu)先順序存儲的。,5.2 數(shù)組的順序表示(續(xù)),LOC(aij)=LOC(a11)+(i-1)*n+j-1*d,2020/7/30,7,列優(yōu)先順序或以列為主序存儲方式：將數(shù)組元素按列向量排列，第j+1個列向量緊接在第j個列向量之后，A的m*n個元素按

4、列優(yōu)先順序存儲的線性序列為： a11,a21,am1,a12,a22,am2,an1,an2,anm 在FORTRAN語言中，數(shù)組按列優(yōu)先順序存儲。,5.2 數(shù)組的順序表示(續(xù)),LOC(aij)=LOC(a11)+(j-1)*m+i-1*d,2020/7/30,8,行優(yōu)先順序先排最右的下標，從右到左，最后排最左下標。 列優(yōu)先順序先排最左下標，從右向左，最后排最左下標。 例如：三維數(shù)組Am*n*p以行優(yōu)先方式順序存儲，則 LOC(aijk)=LOC(a111)+(i-1)*m*n+ (j-1)*n+(k-1)*d,5.2 數(shù)組的順序表示(續(xù)),2020/7/30,9,只要知道開始結點的存放地址

5、（即基地址）、維數(shù)和每維的上、下界，以及每個數(shù)組元素所占用的單元數(shù)，就可以將數(shù)組元素的存放地址表示為其下標的線性函數(shù)。因此，數(shù)組中的任一元素可以在相同的時間內存取，即順序存儲的數(shù)組是一個隨機存取結構。,數(shù)組存儲的特點,2020/7/30,10,壓縮存儲：為多個值相同的非零元素只分配一個存儲空間；對零元素不分配空間。,5.3 矩陣的壓縮存儲,2020/7/30,11,特殊矩陣：非零元素按照一定的規(guī)律分布。,5.3.1特殊矩陣的壓縮存儲,aij=aji,對稱矩陣,常見的特殊矩陣有對稱矩陣、三角矩陣、對角矩陣等。 對稱矩陣：元素的值按照主對角線對稱,2020/7/30,12,5.3.1(續(xù))對稱矩陣

6、的壓縮存儲,對稱矩陣,1,2,1,3,3,1,4,4,4,1,數(shù)組B,1,2,3,4,5,6,7,8,9,10,下標k,例如：一個4*4的對稱矩陣。,2020/7/30,13,5.3.1(續(xù))對稱矩陣的壓縮存儲,對稱矩陣,數(shù)組B,ai,j,an,n,k,m,下標,k = ? m = ?,推廣至一般情況，n*n的對稱矩陣,2020/7/30,14,5.3.1(續(xù))三角矩陣的壓縮存儲,(a) 下三角矩陣,(b) 上三角矩陣,三角矩陣：上(下)三角矩陣是指矩陣的下（上）三角（不包括對角線）中的元素均為常數(shù)或零的n階矩陣，即非零元素的分布在矩陣中呈現(xiàn)為三角形。,例如：一個4*4的三角矩陣。,2020/

7、7/30,15,5.3.1(續(xù))三角矩陣的壓縮存儲,(c) 下三角矩陣,(d) 上三角矩陣,例如：一個4*4的三角矩陣。,2020/7/30,16,5.3.1(續(xù))三角矩陣的壓縮存儲,0,a0,0,a0,1,a0,2,a0,3,ai,j,an-1, n-1,b1,b2,b3,b4,bk,bm,k = ? m = ?,推廣至一般情況，n*n的三角矩陣以行為主序壓縮存儲,2020/7/30,17,5.3.1(續(xù))三角矩陣的壓縮存儲,0,a0,0,a0,1,a1,1,a0,2,ai,j,an-1, n-1,b1,b2,b3,b4,bk,bm,k = ? m = ?,a1,2,b5,a2,2,b6,推

8、廣至一般情況，n*n的三角矩陣以列為主序壓縮存儲,2020/7/30,18,5.3.1(續(xù))三對角矩陣的壓縮存儲,a0,0,a0,1,a1,0,ai,j,數(shù)組B,1,2,k,k+1,m,下標,0,.,.,k = ? m = ?,對角矩陣是指所有的非零元素都集中在以主對角線為中心的帶狀區(qū)域中。,2020/7/30,19,上述各種特殊矩陣，其非零元素的分布都是有規(guī)律的，因此總能找到一種方法將它們壓縮存儲到一維數(shù)組中，并且一般都能找到矩陣中的元素與該一維數(shù)組元素的對應關系，通過這個關系，仍能對矩陣的元素進行隨機存取。,5.3.1(續(xù))特殊矩陣的壓縮存儲,2020/7/30,20,什么是稀疏矩陣？簡單

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

10、,1,-3), (3,6,14), (4,3,24), (5,2,18), (6,1,15), (6,4,-7) ),5.3.2稀疏矩陣的壓縮存儲,例如，一個6*7的稀疏矩陣,稀疏矩陣中的非零元素,2020/7/30,23,假設以順序存儲結構來表示三元組表，則可得到稀疏矩陣的一種壓縮存儲方法三元組順序表。 #define maxsize 10000 typedef int datatype; typedef struct int i,j; datatype v; triple; /* 三元組*/,5.3.2(續(xù))稀疏矩陣的壓縮存儲,2020/7/30,24,typedef struct tri

11、ple datamaxsize; int m,n,t; tripletable;,5.3.2(續(xù))三元組順序表,2020/7/30,25,轉置,2020/7/30,26,5.3.2(續(xù))三元組順序表上的轉置,轉置,排序,2020/7/30,27,typedef struct triple datamaxsize; int m,n,t; tripletable;,Void transmatrix(tripletable A, tripletable /按照AT.datap.i進行非遞減排序 ,5.3.2(續(xù))三元組順序表,2020/7/30,28,5.3.2(續(xù))三元組順序表上的轉置(二),轉置

12、,2020/7/30,29,設置向量num,numcol表示矩陣A中第col列中非零元的個數(shù)。(A的列數(shù)：A.n),5.3.2(續(xù))三元組順序表上的轉置(二),for(col=1;col=A.n;+col) numcol = 0; for(p=1;p=A.t;+p) /計算A中每列非零元的個數(shù) numA.datap.j+;,列號,2020/7/30,30,設置向量cpot,cpotcol指示A中第col列的第一個非零元在轉置矩陣AT.data中的恰當位置。,5.3.2(續(xù))三元組順序表上的轉置(二),cpot1=1 cpotcol=cpotcol-1+numcol-1 2colA.n,cpot

13、1=1; for(col = 2; col=A.n; +col) cpotcol=cpotcol-1+numcol-1;,2020/7/30,31,5.3.2(續(xù))三元組順序表上的轉置(二),cpot,1,3,5,7,8,8,9,1 2 3 4 5 6 7,num,2,2,2,1,0,1,0,2020/7/30,32,轉置,cpot,1,3,5,7,8,8,9,1 2 3 4 5 6 7,2 1 12,三元組順序表上的轉置(二續(xù)),2020/7/30,33,轉置,cpot,1,4,5,7,8,8,9,1 2 3 4 5 6 7,2 1 12,三元組順序表上的轉置(二續(xù)),2020/7/30,3

14、4,轉置,cpot,1,4,5,7,8,8,9,1 2 3 4 5 6 7,2 1 12,3 1 9,三元組順序表上的轉置(二續(xù)),2020/7/30,35,轉置,cpot,1,4,6,7,8,8,9,1 2 3 4 5 6 7,2 1 12,3 1 9,三元組順序表上的轉置(二續(xù)),2020/7/30,36,轉置,cpot,1,4,6,7,8,8,9,1 2 3 4 5 6 7,2 1 12,3 1 9,1 3 -3,三元組順序表上的轉置(二續(xù)),2020/7/30,37,轉置,cpot,2,4,6,7,8,8,9,1 2 3 4 5 6 7,2 1 12,3 1 9,6 3 14,1 3

15、-3,三元組順序表上的轉置(二續(xù)),2020/7/30,38,轉置,cpot,2,4,6,7,8,9,9,1 2 3 4 5 6 7,2 1 12,3 1 9,3 4 24,1 3 -3,6 3 14,三元組順序表上的轉置(二續(xù)),2020/7/30,39,轉置,cpot,2,4,7,7,8,9,9,1 2 3 4 5 6 7,2 1 12,3 1 9,2 5 18,1 3 -3,6 3 14,3 4 24,三元組順序表上的轉置(二續(xù)),2020/7/30,40,轉置,cpot,2,5,7,7,8,9,9,1 2 3 4 5 6 7,2 1 12,3 1 9,1 6 15,1 3 -3,6 3

16、 14,3 4 24,2 5 18,三元組順序表上的轉置(二續(xù)),2020/7/30,41,轉置,cpot,3,5,7,7,8,9,9,1 2 3 4 5 6 7,2 1 12,3 1 9,4 6 -7,1 3 -3,6 3 14,3 4 24,2 5 18,1 6 15,三元組順序表上的轉置(二續(xù)),2020/7/30,42,for(col=1;col=A.n;+col) numcol = 0; for(p=1;p=A.t;+p) /計算A中每列非零元的個數(shù) numA.datap.j+;,5.3.2(續(xù))三元組順序表上的轉置(二),cpot1=1; for(col = 2; col=A.n;

17、 +col) /計算元素位置 cpotcol=cpotcol-1+numcol-1;,2020/7/30,43,for(col=1;col=A.n;+col) numcol = 0; for(p=1;p=A.t;+p) /計算A中每列非零元的個數(shù) numA.datap.j+;,cpot1=1; for(col = 2; col=A.n; +col) /計算元素位置 cpotcol=cpotcol-1+numcol-1;,for(p = 1; p=A.t; +p) /轉置 col = A.datap.j; q = cpotcol; AT.dataq.i = A.datap.j; AT.dataq

18、.j = A.datap.i; AT.dataq.v = A.datap.v; cpotcol+; ,2020/7/30,44,十字鏈表,2020/7/30,45,5.3廣義表的定義,廣義表是線性表的推廣。 L=(a1,a2,.,an ),n0,ai可以是單元素，也可以是一個表。 例如： A = () B = (e) C = (a,(b,c,d) D = (A,B,C) E = (a,E),廣義表的長度 廣義表的深度 非空廣義表 表頭(Head)：第一個元素 表尾(Tail)：除第一個元素外其余元素構成的表,2020/7/30,46,廣義表的存儲結構(一),鏈表存儲 C = (a,(b,c,d

19、) D = (A,B,C) E = (a,E) 鏈表結點結構,tag=1,hp,tp,表結點,tag=0,atom,原子結點,2020/7/30,47,廣義表的存儲結構(一),C = (a,(b,c,d),C,Head(C) = a Tail(C)=(b,c,d),2020/7/30,48,廣義表的存儲結構(一),C = (a,(b,c,d),C,Head(C) = a Tail(C)=(b,c,d),(b,c,d),2020/7/30,49,廣義表的存儲結構(一),C = (a,(b,c,d),C,Head(C) = a Tail(C)=(b,c,d),(b,c,d),(c,d),(d),2020/7/30,50,廣義表的存儲結構(一),C = (a,(b,c,d),2020/7/30,51,B= (e),B,2020/7/30,52,A= (),B,A,2020/7/30,53,D= (A,B,C),B,A,D,(B,C),(C),2020/7/30,54,5.4廣義表的存儲結構(一),鏈表結點結構,tag=1,hp,tp,表結點,tag=0,atom,原子結點,typedef enum ATOM,LIST ElemTag; Typedef struct GLNode ElemTag tag; union AtomType atom