數(shù)據結構第5章數(shù)組與廣義表

1、本章主要知識點本章主要知識點 數(shù)組數(shù)組 特殊矩陣的壓縮存儲特殊矩陣的壓縮存儲 稀疏矩陣稀疏矩陣 廣義表廣義表數(shù)組數(shù)組 1.數(shù)組的定義數(shù)組的定義 數(shù)組是由類型相同類型相同的數(shù)據元素構成的 有序集合，每個數(shù)據元素稱為一個數(shù)組元數(shù)組元 素素（簡稱元素）,每個元素受個線性關系 的約束，每個元素在個線性關系中的序號 稱為該元素的下標下標，并稱該數(shù)組為維數(shù) 組，稱為該數(shù)組的維數(shù)維數(shù)。 特點特點: （1）數(shù)組中的數(shù)據元素具有相同數(shù)據類型相同數(shù)據類型。（2）數(shù)組是一種隨機存取隨機存取結構，給定一組下標，就可以訪問與其對應的數(shù)據元素。（3）數(shù)組中的數(shù)據元素個數(shù)個數(shù)是固定固定的。一旦定義了數(shù)組，它的維數(shù)和元素數(shù)目

2、也就確定了。 數(shù)組中通常只有兩種操作：數(shù)組中通常只有兩種操作：(1) 存取存?。航o定一組下標，存取相應的數(shù)據元素；(2) 修改修改：給定一組下標，修改相應的數(shù)據元素的值。2.數(shù)組的順序表示數(shù)組的順序表示數(shù)組一般都是采用順序存儲順序存儲的方法來表示。數(shù)組通常有兩種順序存儲方式：(1) 行優(yōu)先順序行優(yōu)先順序(Row Major Order) ：將數(shù)組元素按行排列，第i+1個行向量緊接在第i個行向量后面。對二維數(shù)組，按行優(yōu)先順序存儲的線性序列為： mnmmnnaaaaaaaaa,212222111211 (2) 列優(yōu)先順序列優(yōu)先順序(Column Major Order) ：將數(shù)組元素按列向量排列，

3、第j+1個列向量緊接在第j個列向量之后，對二維數(shù)組，按列優(yōu)先順序存儲的線性序列為：nmnnmmaaaaaaaaa,212221212111 設有二維數(shù)組A=(aij)mn，若每個元素占用L個存儲單元，a11作為該數(shù)組的第一個元素，LOCa11表示元素a11的首地址，即數(shù)組的首地址。以以“行優(yōu)先順序行優(yōu)先順序”存儲存儲:(1) 第1行中的每個元素對應的(首)地址是： LOCa1j=LOCa11+(j-1) L (2) 第2行中的每個元素對應的(首)地址是： LOCa2j=LOCa11+nL +(j-1) L (3) 第m行中的每個元素對應的(首)地址是： LOCamj=LOCa11+(m-1)

4、nL +(j-1) L 二維數(shù)組中任一元素aij的(首)地址是： LOCaij=LOCa11+(i-1) n +(j-1) L 三維數(shù)組中任一元素aijk的(首)地址是： LOC(aijk)=LOCa111+(i-1)np+(j-1)p+(k-1) L n維數(shù)組中任一元素aj1j2jn的(首)地址是：LOCaj1j2jn=LOCa11 1+(b2bn)(j1-1)+ (b3bn) (j2-1)+ + bn(jn-1-1)+ (jn-1) L 以以“列優(yōu)先順序列優(yōu)先順序”存儲：存儲：(1) 第1列中的每個元素對應的(首)地址是： LOCaj1=LOCa11+(j-1) L (2) 第2列中的每個

5、元素對應的(首)地址是： LOCaj2=LOCa11+mL +(j-1) L(3) 第n列中的每個元素對應的(首)地址是： LOCajn=LOCa11+ (n-1) mL +(j-1) L 二維數(shù)組中任一元素aij的(首)地址是： LOCaij=LOCa11+(i-1)m+(j-1)L 例例 若6行5列的數(shù)組以列序為主序順序存 儲，基地址為1000，每個元素占2個 存儲單元，則第3行第4列的元素（假 定無第0行第0列）的地址是多少?解解 LOC(a34)= LOCa11+(3-1)6+(4- 1)2=1000+(3-1)6+(4-1)2=1030 特殊矩陣的壓縮存儲特殊矩陣的壓縮存儲矩陣矩陣：

6、是一個由mn個元素排成的m行 （橫向）n列（縱向）的表。 mnmmnnaaaaaaaaa.212222111211 特殊矩陣特殊矩陣是指元素值的排列具有一定規(guī)律規(guī)律的矩陣。常見的這類矩陣有：對稱矩對稱矩陣陣、下（上）三角矩陣下（上）三角矩陣、對角線矩陣對角線矩陣等等。 可以利用它的規(guī)律來進行壓縮存儲壓縮存儲，即為多個值相同的元素只分配一個存儲空間，對0元素不分配存儲空間，因此就不用占用mn那么多的空間。1 對稱矩陣對稱矩陣 若一個n階方陣A=(aij)nn中的元素滿足性質： aij=aji 其中，1i,jn且ij，則稱A為對稱矩陣 。 對稱矩陣關于主對角線對稱主對角線對稱，因此只需存儲上三角上

7、三角或下三角下三角部分即可。 原來需要n*n個存儲單元，現(xiàn)在只需要n(n+1)/2個存儲單元了，節(jié)約了n(n-1)/2個存儲單元。用數(shù)組SAn(n+1)/2來壓縮存儲該對稱矩陣 ： 下三角中的元素aij，其特點特點是：ij且1in，存儲到SA中后， SA中的下標k與i、j的關系： k=i*(i-1)/2+j-1 (kn*(n+1)/2 ) 上三角中的元素aij，其特點特點是ij ，有： aij=aji 上三角中的元素在SA中的對應關系： k=j*(j-1)/2+i-1 (kn*(n+1)/2 ) 2 三角矩陣三角矩陣 以主對角線劃分，三角矩陣有上三角和下三角兩種。如圖所示。其中(a)圖為下三角

8、矩陣：主對角線以上均為同一個常數(shù)；(b)圖為上三角矩陣，主對角線以下均為同一個常數(shù)。 (1) 下三角矩陣下三角矩陣 三角矩陣中的重復元素c可共享一個存儲空間，其余的元素正好有n(n+1)/2個，因此，三角矩陣可壓縮存儲到向量SA0n(n+1)/2中，其中c存放在向量的最后1個分量SAn(n+1)/2中。 該存儲方式可節(jié)約n*(n-1)/2-1個存儲單元。 SAk與aji 的對應關系：(2) 上三角矩陣上三角矩陣 對于上三角矩陣，存儲思想與下三角類似，以行為主序順序存儲上三角部分，最后存儲對角線下方的常量。 SAk 與aji 的對應關系: 3 對角矩陣對角矩陣 在一個矩陣中，除了主對角線和主對角

9、線上或下方若干條對角線上的元素之外，其余元素皆為零或常數(shù)。即所有的非零元素集中在以主對角線為了中心的帶狀區(qū)域中。 以三對角矩陣為例，需存儲的元素個數(shù)總量為3n-2。 若存入的數(shù)組空間為B1.3n-2中，元素在一維數(shù)組B中的下標k和元素在矩陣中的下標i和j的對應關系為： k=2(i-1)+j (1i,jn; 1k3n-2) 稀疏矩陣稀疏矩陣 設矩陣A是一個 m 行 n 列的矩陣含 t 個非零元素，則稱 為矩陣的稀疏因 子。如果某一矩陣的稀疏因子滿足 0.05時稱為稀疏矩陣稀疏矩陣。 nmt0200000000000210010070003 一個稀疏矩陣里存在大量的零元素，若以常規(guī)方法，即以二維數(shù)

10、組來存儲稀疏矩陣時產生如下問題:1) 零值元素占了很多空間;2) 如果進行計算，則會進行很多和零值的運算，如是除法，還需判別除數(shù)是否為零。 稀疏矩陣的三元組存儲稀疏矩陣的三元組存儲 稀疏矩陣中存在大量的零元素零元素，這些零元素并不需要存儲，所以采用壓縮存儲時，只存儲非零元素存儲非零元素。為了能準確定位該非零元素，必須存儲非零元素的行下標值行下標值、列下標值列下標值、元素值元素值。因此，可以用一個三三元組元組(i, j, aij)來唯一確定稀疏矩陣的一個非零元素。三元組結點定義：三元組結點定義： #define MAX_SIZE 101typedef int elemtype ;typedef

11、struct int row ; /*行下標*/ int col ; /*列下標*/ elemtype value; /*元素值*/Triple ;三元組順序表定義：三元組順序表定義： typedef struct int rn ; /*行數(shù)*/ int cn ; /*列數(shù)*/ int tn ; /*非0元素個數(shù)*/ Triple dataMAX_SIZE ; TMatrix ; 在壓縮存儲方式下如何實現(xiàn)稀疏矩陣在壓縮存儲方式下如何實現(xiàn)稀疏矩陣的轉置操作呢？的轉置操作呢？基本算法思想： 將矩陣的行、列下標值交換； 重排三元組表中元素的順序，即交換后仍然是按行優(yōu)先順序排序的。方法一：方法一：算法

12、思想：按稀疏矩陣A的三元組表a.data中的列次序依次找到相應的三元組存入b.data。每找到轉置后矩陣的一個三元組，需從頭至尾掃描整個三元組表a.data 。 void TransMatrix(TMatrix a , TMatrix b) int p , q , col ; b.rn= ; =a.rn ; b.tn=a.tn ; if (b.tn=0) printf(“ The Matrix A=0n” ); else q=0; for (col=1; col= ; col+) for (p=0 ;pa.tn ; p+) if (a.datap.col=col) b.dataq.row=a.

13、datap.col ; b.dataq.col=a.datap.row ; b.dataq.value=a.datap.value; q+ ; 算法的時間復雜度為算法的時間復雜度為O(cntn) 傳統(tǒng)矩陣的轉置算法為：for(col=1; col=n ;+col) for(row=0 ; row=m ;+row) bcolrow=arowcol ;時間復雜度為時間復雜度為O(nm) 當非零元素的個數(shù)tn和mn同數(shù)量級時，算法TransMatrix的時間復雜度為O(mn2)。 方法二方法二(快速轉置的算法快速轉置的算法) 算法思想：一遍掃描三元組表A.data，將每個元素放到轉置后的三元組表B.

14、data的正確位置上 。 為了做到這一點，需求出矩陣A中每列第一個非零元的位置和每列非零元素的個數(shù)。為此，增加存放每列非零元素個數(shù)的一維數(shù)組number和每列第一個非零元素在B中位置的一維數(shù)組position 。 TSMatrix FastTransMatrix(TSMatrix A, TSMatrix B) B.m=A.n; B.n=A.m; B.len=A.len; if(A.len) for(j=1;j=A.n;j+) numberj=0; for(t=1;t=A.len;t+) numberA.datat.col+; position1=1;.nj1 , 1-numberj1-posi

15、tionj0, 0Ajjposition for(j=2;j=A.n;j+) positioncol=positioncol-1+numbercol-1; for(p=1;p=0)個元素a1,a2,a3,an的有限序列，其中ai或者是原子項原子項，或者是一個廣廣義表義表。通常記作LS=（a1,a2,a3,an)。LS是廣義表的名字，n為它的長度。若ai是廣義表，則稱它為LS的子表。 若廣義表LS（n=1)非空，則a1是LS的表表頭頭，其余元素組成的表(a2,a3,an)稱為LS的 表尾表尾。 （1）A=（） 表A是一個空表，其長度為零。（2）B=（e） 表B只有一個原子e，B的長度為1。（3）

16、C=（a,(b,c) 表C的長度為2，兩個元素分別為原子a和子表(b,c)。（4）D=（A，B，C） 表D的長度為3，三個元素都是廣義表。（5）E=（a, E） 表E是一個遞歸的表，長度為2，相當于一個無限的廣義表E=(a,(a,(a,(a,)。廣義表的重要性質：廣義表的重要性質： 廣義表是一種多層次多層次的數(shù)據結構，其元素可以是單元素，也可以是子表，而子表的元素還可以是子表。廣義表可以是遞歸遞歸的表。廣義表的定義并沒有限制元素的遞歸，即廣義表也可以是其自身的子表。廣義表可以為其他表所共享共享。例如，表A、表B、表C是表D的共享子表。 廣義表有兩個重要的基本操作，即取表頭取表頭操作操作(Hea

17、d或GetHead)和取表尾操作取表尾操作（Tail或GetTail）。 根據廣義表的表頭、表尾的定義可知，對于任意一個非空的列表，其表頭可能是單單元素元素也可能是列表列表，而表尾必為列表列表。 GetHead(a,b,c) =a GetTail (a,b,c,d) =(b,c,d) GetHead(a,b),(d) =(a,b) GetTail(a,b),(d) =(d) GetHead(GetTail(a,b),(c,d) =(c,d)2廣義表的存儲結構廣義表的存儲結構 頭尾表示法頭尾表示法 若廣義表不空，則可分解成表頭和表尾；反之，一對確定的表頭和表尾可惟一地確定一個廣義表。 結點結構形式有兩種：一種是表結點表結點，用以表示列表；另一種是元素結點元素結點，用以表示單元素。 在結點中