1、本章的基本內(nèi)容是： 數(shù)組的邏輯結構特征； 數(shù)組的存儲方式及尋址方法； 特殊矩陣和稀疏矩陣的壓縮存儲方法； 廣義表的基本概念和存儲結構。,3.1.1 數(shù)組的定義,是由一組類型相同的數(shù)據(jù)元素構成的有序集合，每個數(shù)據(jù)元素稱為一個數(shù)組元素（簡稱為元素），每個元素受n(n1)個線性關系的約束，每個元素在n個線性關系中的序號i1、i2、in稱為該元素的下標，并稱該數(shù)組為n維數(shù)組。,3.1 多維數(shù)組,數(shù)組的特點:,元素本身可以具有某種結構,但屬于同一數(shù)據(jù)類型； 數(shù)組是線性表的推廣; 數(shù)組是一個具有固定格式和數(shù)量的數(shù)據(jù)集合。,數(shù)組示意圖,3.1.2 數(shù)組的存儲結構與尋址,采用順序存儲結構存儲數(shù)組首先需要將多維

2、結構映射到一維結構。,常用的映射方法有兩種：按行優(yōu)先和按列優(yōu)先。,按行優(yōu)先存儲的基本思想是：先行后列，先存儲行號較小的元素，行號相同者先存儲列號較小的元素。,1.一維數(shù)組的存儲與尋址,設一維數(shù)組的下標的范圍為閉區(qū)間l，h，則其 的任一元素ai的存儲位置可由下式確定： LOC(ai)LOC(al)(il)c,2.二維數(shù)組的存儲與尋址,二維數(shù)組按行優(yōu)先存儲尋址示意圖,aij前面的元素個數(shù)=陰影部分的面積=整行數(shù)每行元素個數(shù)+本行中aij前面的元素個數(shù)=(i -l1)(h2 -l21)(j -l2),二維數(shù)組尋址的計算方法,aij,按列優(yōu)先存儲的基本思想：先列后行，先存儲列號較小的元素，列號相同者先

3、存儲行號較小的元素。,任一元素存儲地址的計算方法你能推導出來嗎？,n（n2）維數(shù)組，一般也采用按行優(yōu)先和按列優(yōu)先兩種存儲方法。 請給出基本思想和尋址計算方法，好嗎？,下標為 i1, i2, i3的數(shù)組元素的存儲地址： 按頁/行/列存放 各維元素個數(shù)為 m1, m2, m3,LOC ( ai j k ) = Loc(a000) + ( i* m2 * m3 + j* m3 + k ) * l,3.2 矩陣的壓縮存儲,在矩陣中很多值相同的元素并且它們的分布有一定的規(guī)律，我們將這樣的矩陣稱為特殊矩陣。 若矩陣中有很多零元素稱為稀疏矩陣,壓縮存儲的基本思想是： 為多個值相同的元素只分配一個存儲空間；

4、對零元素不分配存儲空間。,3.2.1 特殊矩陣的壓縮存儲對稱矩陣,36478 62842 48169 74605 82957,A,5階對稱矩陣,對稱矩陣特點：在一個n階方陣中，有aij=aji ，其中1i , jn。,只需要n（n1）/2個存儲單元。,(a) 下三角矩陣 (b) 存儲說明 (c) 計算方法,aij在一維數(shù)組中的序號 =陰影部分的面積 = i(i+1)/2+ j+1 一維數(shù)組下標從0開始 aij在一維數(shù)組中的下標 k= i(i+1)/2+ j,對稱矩陣按行優(yōu)先存儲尋址示意圖,結論：將下三角中的所有元素按行優(yōu)先存儲到一維數(shù)組中SA，下三角中的元素aij（ij）在數(shù)組SA中的下標k與

5、i、j的關系為：ki(i1)/2j 。 同理我們可以得到： 上三角中的元素aij（ij），因為aijaji，則訪問和它對應的元素aji即可，即：kj(j1)/2i 。,對稱矩陣的壓縮存儲,3.2.1 特殊矩陣的壓縮存儲三角矩陣,3 cc c c 6 2c c c 4 81 c c 7 46 0 c 8 29 5 7,(a)下三角矩陣,3 4 8 1 0 c2 9 4 6 cc 5 7 cc c 0 8 cc c c 7,(b)上三角矩陣,只需存儲n(n1)/21,下三角矩陣的壓縮存儲既要存儲下三角中的元素，還要存儲對角線上方的常數(shù)。因為是同一個常數(shù)，所以只存一個即可。,對于上三角矩陣，其存儲思

6、想與下三角類似，按行存儲上三角部分，最后存儲對角線下方的常數(shù)。,結論：1.下三角矩陣中任一元素aij在SA中的下標k與i、j的對應關系為：,2.上三角矩陣中任一元素aij在SA中的下標k與i、j的對應關系為：,K=j(j1)/2i 當ij,K=i(i1)/2j 當ij,3.2.1 特殊矩陣的壓縮存儲對角矩陣,所謂對角矩陣是指所有非零元素都集中在以主對角線為中心的帶狀區(qū)域中，除了主對角線和它的上下方若干條對角線的元素外，所有其他元素都為零。,(b) 壓縮為5*3的矩陣,對角矩陣的壓縮存儲方法2,(c) 壓縮到一維數(shù)組中,(a) 三對角矩陣,0 0 0 0 0 0 0 0 0 0 0 0,A=,按

7、行存儲非零元素,元素aij在一維數(shù)組中的序號 =2 + 3(i1)+( ji + 2) =2i+ j+1 一維數(shù)組下標從0開始 元素aij在一維數(shù)組中的下標 =2i+ j,(b) 尋址的計算方法,3.2.2 稀疏矩陣的壓縮存儲,什么是稀疏矩陣?有哪些特征?,三元組定義:將稀疏矩陣中的每個非零元素表示為：(行號，列號，非零元素值)稱為三元組表示法。,C+中，用結構類型來描述三元組： template struct element int row, col; T item ;,三元組表：將稀疏矩陣的非零元素對應的三元組所構成的集合，按行優(yōu)先的順序排列成一個線性表。,采用順序存儲結構存儲的三元組表稱

8、為三元組順序表。,稀疏矩陣,A的三元組順序表,一、三元組順序表 假設以順序存儲結構來表示三元組表，則可得到稀疏矩陣的一種壓縮存儲方法三元順序表。 #define maxsize 10000 typedef int datatype; typedef struct int i,j; datatype v; triple;,typedef struct triple datamaxsize; int m,n,t; tripletable; 設A為tripletable型的結構變量，圖5.4中所示的稀疏矩陣的三元組的表示如下： i j v 1 2 12 1 3 9 3 1 -3 3 6 14 4 3

9、 24 5 2 18 6 1 15 6 4 -7,下面以矩陣的轉置為例，說明在這種壓縮存儲結構上如何實現(xiàn)矩陣的運算。 一個mn的矩陣A，它的轉置B是一個nm的矩陣，且aij=bji，0im，0jn，即A的行是B的列，A的列是B的行。 將A轉置為B，就是將A的三元組表a.data置換為表B的三元組表b.data，如果只是簡單地交換a.data中i和j的內(nèi)容，那么得到的b.data將是一個按列優(yōu)先順序存儲的稀疏矩陣B，要得到按行優(yōu)先順序存儲的b.data，就必須重新排列三元組的順序。 由于A的列是B的行，因此，按a.data的列序轉置，所得到的轉置矩陣B的三元組表b.data必定是按行優(yōu)先存放的。

10、,按這種方法設計的算法，其基本思想是：對A中的每一列 col(0coln-1)，通過從頭至尾掃描三元表a.data，找出所有列號等于col的那些三元組，將它們的行號和列號互換后依次放入b.data中，即可得到B的按行優(yōu)先的壓縮存儲表示。 i 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,Void transmatrix(tripletable a,tripletable b) int p q col; b.m=a.n; b.n=a.m; b.t=a.t; if(b.t=0) printf(“A=0n”); q=0;,for

11、(col=1;col=a.n;col+) for(p=0;p=a.t;p+) if(a.datap.j=col) b.dataq.i=a.datap.j; b.dataq.j=a.datap.i; b.dataq.v=a.datap.v; q+; ,分析這個算法，主要的工作是在p和col的兩個循環(huán)中完成的，故算法的時間復雜度為O(n*t)，即矩陣的列數(shù)和非零元的個數(shù)的乘積成正比。而一般傳統(tǒng)矩陣的轉置算法為： for(col=0;col=n-1;+col) for(row=0;row=m;+row) tcolrow=mrowcol; 其時間復雜度為O(n*m)。當非零元素的個數(shù)t和m*n同數(shù)量級

12、時，算法transmatrix的時間復雜度為O(n*n2)。,三元組順序表雖然節(jié)省了存儲空間，但時間復雜度比一般矩陣轉置的算法還要復雜，同時還有可能增加算是法的難度。因此，此算法僅適用于t=m*n的情況。 下面給出另外一種稱之為快速轉置的算法，其算法思想為：對A掃描一次，按A第二列提供的列號一次確定位置裝入B的一個三元組。具體實施如下：一遍掃描先確定三元組的位置關系，二次掃描由位置關系裝入三元組。可見，位置關系是此種算法的關鍵。,為了預先確定矩陣M中的每一列的第一個非零元素在數(shù)組B中應有的位置，需要先求得矩陣M中的每一列中非零元素的個數(shù)。因為：矩陣M中第一列的第一個非零元素在數(shù)組B中應有的位置

13、等于前一列第一個非零元素的位置加上前列非零元素的個數(shù)。 為此，需要設置兩個一維數(shù)組num0.n和cpot0.n num0.n：統(tǒng)計M中每列非零元素的個數(shù)，numcol的值可以由A的第二列求得。,cpot0.n：由遞推關系得出M中的每列第一個非零元素在B中的位置。 算法通過cpot數(shù)組建立位置對應關系： cpot1=1 cpotcol=cpotcol-1+numcol-1 2=cpl=a.n 例如：圖5.4中的矩陣M和相應的三元組A可以求得numcol和 cpotcol的值如下： col 1 2 3 4 5 6 7 numcol 2 2 2 1 0 1 0 cpotcol 1 3 5 7 8 8

14、 9,A i j v,第一列元素個數(shù) 第二列元素個數(shù) 第三列元素個數(shù),num,cpot,q=cpotcol,p,p,快速轉置算法如下： void fasttranstri(tritupletable b,tritupletable a) int p,q,col,k; int num0.a.n,copt0.a.n; b.m=a.n; b.n=a.m; b.t=a.t; if(b.t=0) printf(“a=0”n); for(col=1;col=a.u;+col) numcol=0; for(k=1;k=a.t;+k) +numa.datak.j;,cpot0=1; for(col=2;col

15、=a.t;+col) cpotcol=cpotcol-1+numcol-1; for(p=1;p=a.t;+p) col=a.datap.j; q=cpotcol; b.dataq.i=a.datap.j; b.dataq.j=a.datap.i; b.dataq.v=a.datap.v; +cpotcol; ,算法的偽代碼描述：,1. 設置轉置后矩陣B的行數(shù)、列數(shù)和非零元素的個數(shù)； 2. 在B中設置初始存儲位置pb； 3. for (col=最小列號; col=最大列號; col+) 3.1 在A中查找列號為col的三元組； 3.2 交換其行號和列號，存入B中pb位置； 3.3 pb+；,分

16、析時間復雜度？,稀疏矩陣三元組順序表存儲操作 轉置算法,分析：如何確定當前從A中取出的三元組在B中的位置。注意到A中第0列的第一個非零元素一定存儲在B中下標為0的位置上，該列中其它非零元素應存放在B中后面連續(xù)的位置上，那么第1列的第一個非零元素在B中的位置便等于第0列的第一個非零元素在B中的位置加上第0列的非零元素的個數(shù)，以此類推。,該算法的基本思想：是在A中依次取三元組，交換其行號和列號放到B 中適當位置。,1.引入兩個數(shù)組作為輔助數(shù)據(jù)結構： numnu：表示矩陣A中某列的非零元素的個數(shù)； cpotnu：初始值表示矩陣A中某列的第一個非零元素在B中的位置。,算法設計：,2.num與cpot遞

17、推關系：,1. 設置轉置后矩陣B的行數(shù)、列數(shù)和非零元素的個數(shù)； 2. 計算A中每一列的非零元素個數(shù)； 3. 計算A中每一列的第一個非零元素在B中的下標； 4. 依次取A中的每一個非零元素對應的三元組； 4.1 確定該元素在B中的下標pb； 4.2 將該元素的行號列號交換后存入B中pb的位置； 4.3 預置該元素所在列的下一個元素的存放位置；,算法的偽代碼：,稀疏矩陣鏈接存儲的基本思想是：將每個非零元素對應的三元組存儲為一個鏈表結點，結點由5個域組成，,其中: row：存儲非零元素的行號； col：存儲非零元素的列號； item：存儲非零元素的值； right：指針域，指向同一行中的下一個三元組

18、； down：指針域，指向同一列中的下一個三元組.,例:,3.3 廣 義 表,3.3.1 廣義表的邏輯結構,廣義表的定義,廣義表是n（n0）個數(shù)據(jù)元素的有限序列，一般記作：LS(a1，a2，an),其中:LS是廣義表的名稱，ai（1in）是LS的成員（也稱直接元素），它可以是單個的數(shù)據(jù)元素，也可以是一個廣義表，分別稱為LS的單元素和子表。,其它概念: 1表頭:當廣義表LS非空時，稱第一個元素為LS的表頭； 2表尾: 廣義表LS中除去表頭后其余元素組成的廣義表為LS的表尾; 3 廣義表長度:廣義表LS中的直接元素的個數(shù)； 4 廣義表的深度:廣義表LS中括號的最大嵌套層數(shù)。,廣義表( )和廣義表(

19、 )不同？,廣義表表示方法,通常用圖形方法來表示廣義表的邏輯結構，具體表示方法為：對每個廣義表的直接元素ai用一個結點來表示，若ai為單元素，則用矩形結點表示，若ai為廣義表，則用圓形結點表示，結點之間的邊表示元素之間的“包含/屬于”關系。,廣義表的特性, 廣義線性性； 元素復合性； 元素遞歸性； 元素共享性：,3.3.2 廣義表的存儲結構及實現(xiàn),廣義表的存儲結構頭尾表示法,結點結構有兩種：一種是表結點；另一種是元素結點。,其中，tag：區(qū)分表結點和元素結點的標志； hp：指向表頭結點的指針； tp：指向表尾結點的指針； data：存放單元素的數(shù)據(jù)域。,enum Elemtag Atom, List; template struct GLNode Elemtag tag; union T data; struct GLNode *hp, *tp; ptr; ; ;,定義廣義表的結點結構,template class Lists public: Lists( ) ls=NULL; Lists(Lists ls1, Lists ls2); L