1、|第第1章章 緒論緒論|第第2章章 線性表線性表|第第3章章 串串|第第4章章 棧與隊列棧與隊列第第5章章 數組和廣義表數組和廣義表|第第6章章 樹和二叉樹樹和二叉樹|第第7章章 圖圖|第第8章章 查找查找|第第9章章 排序排序|5.1 5.1 數組數組|5.2 5.2 特殊矩陣的壓縮存儲特殊矩陣的壓縮存儲|5.3 5.3 廣義表廣義表|5.1.1 一維數組一維數組|5.1.2 多維數組多維數組|數組是一組相同數據類型的數據元素的集合，數組元素數組是一組相同數據類型的數據元素的集合，數組元素按次序存儲于一個地址連續的內存空間中。按次序存儲于一個地址連續的內存空間中。|數組元素在數組中的位置通常

2、稱為數組的下標。數組元素在數組中的位置通常稱為數組的下標。5.1 數組的定義數組的定義|數組分配內存空間的方式有數組分配內存空間的方式有2種種z靜態數組靜態數組：聲明時給出數組元素個數。當程序開始運行時，：聲明時給出數組元素個數。當程序開始運行時，數組即獲得系統分配的一塊地址連續的內存空間。靜態數數組即獲得系統分配的一塊地址連續的內存空間。靜態數組所占用的內存空間由系統自動管理。組所占用的內存空間由系統自動管理。z動態數組動態數組：聲明時不指定數組長度。當程序運行中需要使：聲明時不指定數組長度。當程序運行中需要使用數組時，向系統申請數組的存儲單元空間，并給出數組用數組時，向系統申請數組的存儲單

3、元空間，并給出數組長度。當數組使用完之后，需要向系統歸還所占用的內存長度。當數組使用完之后，需要向系統歸還所占用的內存空間。空間。|在在Java中，數組元素既可以是簡單數據類型，也可以是中，數組元素既可以是簡單數據類型，也可以是引用類型。而且引用類型。而且Java中的數組都是動態數組。中的數組都是動態數組。5.1.1 一維數組一維數組5.1.2 多維數組多維數組a1,1 a1,2 a1,3 a1,na2,1 a2,2 a2,3 a2 2,nam,1 am,2 2 am,3 am,n. . . . . . . . . . . . . . .Amn =以二維數組為例，以二維數組為例，數組和廣義表均

4、是元素為復合結構的線性結構。數組和廣義表均是元素為復合結構的線性結構。1 多維數組的概念多維數組的概念2. 多維數組的遍歷多維數組的遍歷 :以以行序行序為主序為主序:可以看成可以看成 A = ( 1， 2， ， m )T. . .其中其中 i 是一個是一個行向量行向量形式的線性表，形式的線性表，1im i = ( ai 1，ai 2， ，ai n ). . .a1,1 a1,2 a1,3 a1,na2,1 a2,2 a2,3 a2 2,nam,1 am,2 2 am,3 am,n. . . . . . . . . . . . . . .Amn =PASCAL、C按照某種次序訪問一個數據結構中的

5、所有元素，并且每按照某種次序訪問一個數據結構中的所有元素，并且每個數據元素恰好訪問一次，稱為對該數據結構的遍歷。個數據元素恰好訪問一次，稱為對該數據結構的遍歷。可以看成可以看成 A = ( 1， 2， ， n ). . .其中其中 j 是一個是一個列向量列向量形式的線性表，形式的線性表，1jn j = ( a1 j，a2 j， ，amj )T. . .a1,1 a1,2 a1,3 a1,na2,1 a2,2 a2,3 a2 2,nam,1 am,2 2 am,3 am,n. . . . . . . . . . . . . . .Amn =以以列序列序為主序為主序:FORTRAN3. 多維數組的

6、順序存儲結構多維數組的順序存儲結構數組一旦被定義，其數組一旦被定義，其維數維數和和維界維界就不再改變，故通常就不再改變，故通常采用采用 。如何將多維數組結構轉換對應一組連續的存儲單元？如何將多維數組結構轉換對應一組連續的存儲單元？順序存儲結構順序存儲結構以列序為主序以列序為主序a11a21 am,1a12a22 am,2 2a1,n am,na2 2,n 1 2 na11 a12 a13 a1,na21 a22 a23 a2 2,nam,1 am,2 2 am,3 am,n. . . . . . . . . . . . . . .Amn 1 2 . . . n以行序為主序以行序為主序a11a1

7、2 a1,na21a22 a2 2,n am,1 1 am,n am,2 2 1 2 ma11 a12 a13 a1,na21 a22 a23 a2 2,nam,1 am,2 2 am,3 am,n. . . . . . . . . . . . . . .Amn 1 2 m. . .對于數組，一旦規定了維數和維界，如何計算數組元素的存儲位置對于數組，一旦規定了維數和維界，如何計算數組元素的存儲位置?a11a12 a1,na21a22 a2 2,n am,1 1 am,n am,2 2 1 2 m 設數組以設數組以行序行序為主序。為主序。二維數組二維數組 Amn 數組元素數組元素 aij 的存儲

8、位置為的存儲位置為Loc(ai,j) =Loc(a1,1)是是a1,1的存儲位置；的存儲位置；存儲密度為存儲密度為1；1例，例，Loc(a2,2) =+ ( i-1)n + (j-1)Loc(a1,1)Loc(a1,1) + n +1例例1:一個二維數組一個二維數組A,行下標的范圍是行下標的范圍是1到到6,列下標的范圍是列下標的范圍是0到到7,每每個數組元素用相鄰的個數組元素用相鄰的6個字節存儲個字節存儲,存儲器按字節編址存儲器按字節編址;那么那么,這個這個數組占數組占 個字節。個字節。例例2:已知二維數組已知二維數組Am,m按行存儲的元素地址公式是：按行存儲的元素地址公式是：Loc(aij)

9、=Loc(a11)+(i-1)*m+(j-1)*K , 按列存儲的公式是？按列存儲的公式是？例例3計算機系考研題計算機系考研題：設數組設數組a160, 170的基地址為的基地址為2048，每個元素占每個元素占2個存儲單元，若以列序為主序順序存儲，則元素個存儲單元，若以列序為主序順序存儲，則元素a32,58的的 存儲地址為存儲地址為 。答：答：Volume=m*n*L= 6 * (7+1) * 6=48*6 =288288答答:Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*K 盡管是方陣,公式仍不同答答:Loc(aij) = Loc(a11) + (m (j-1) + i-1

10、) lLoc(a32,58)=2048+(60*(58-1)+32-1)*28950注意審題注意審題,以列為主序以列為主序!|設二維數組中的每一個數組元素設二維數組中的每一個數組元素Aij占用占用6個字節個字節,行下行下標標i從從0到到8,列下標列下標j從從2到到5,1)則二維數組則二維數組A共占用共占用_(1)_個字節個字節;2)A中中6行和行和4列的數組元素共占用列的數組元素共占用_(2)_個字節個字節;3)若按行優先順序存放二維數組若按行優先順序存放二維數組A,其第一個數組元素存放其第一個數組元素存放的首字節號為的首字節號為1000(十進制十進制),則最后一個數組元素存放則最后一個數組元

11、素存放的首字節為的首字節為_(3)_4)數組元素數組元素A34的首字節號為的首字節號為_(4)_9行行4列列 36*6 2.（9+4-1）*63.1000+216-6 4. 1000+（3*4+（4-2）*61. 數組數組A中中,每個元素每個元素A的長度為的長度為3個字節個字節,行下標行下標i從從1到到8,列列下標下標j從從1到到10,從首地址從首地址SA開始連續存放在存儲器內開始連續存放在存儲器內,存存放該數組至少需要的單元數是放該數組至少需要的單元數是?2. 數組數組A中中,每個元素每個元素A的長度為的長度為3個字節個字節,行下標行下標i從從1到到8,列列下標下標j從從1到到10,從首地址

12、從首地址SA開始連續存放在存儲器內開始連續存放在存儲器內,該該數組按行存放時數組按行存放時,元素元素A85的起始地址為的起始地址為?3. 數組數組A中中,每個元素每個元素A的長度為的長度為3個字節個字節,行下標行下標i從從1到到8,列列下標下標j從從1到到10,從首地址從首地址SA開始連續存放在存儲器內開始連續存放在存儲器內,該該數組按列存放時數組按列存放時,元素元素A58的起始地址為的起始地址為?240SA+222 SA+(8-1)*10+(5-1)*3SA+180 SA+(8-1)*8+(5-1)*3實際中，存在許多特殊矩陣，例如在矩陣中有許多實際中，存在許多特殊矩陣，例如在矩陣中有許多值

13、相值相同同的元素或者的元素或者零元素零元素。 10 0 10 0 10 0 10 0 0. . . . . . . . . . . . .用定長數組存儲造成浪費。用定長數組存儲造成浪費。5.2 特殊矩陣的壓縮存儲特殊矩陣的壓縮存儲為了節省存儲空間，需要對這類矩陣進行為了節省存儲空間，需要對這類矩陣進行壓縮存儲壓縮存儲。壓縮存儲壓縮存儲是指為是指為多個值相同多個值相同的元素只分配一個存儲空間；的元素只分配一個存儲空間；對對零元素零元素不分配空間。不分配空間。 對稱矩陣對稱矩陣 對角矩陣對角矩陣 稀疏矩陣稀疏矩陣 三角矩陣三角矩陣對稱矩陣是滿足 aij= aji 性質的n階矩陣(1i,jn)。可以

14、看出可以看出:對稱矩陣中的元素對稱矩陣中的元素，故只要，故只要存儲矩陣中存儲矩陣中或或中的元素，讓每兩個對稱的元素中的元素，讓每兩個對稱的元素共享一個存儲空間，共享一個存儲空間，的空間。能節約近的空間。能節約近一半的存儲空間。一半的存儲空間。1 5 1 3 75 0 8 0 01 8 9 2 63 0 2 5 17 0 6 1 3 a11 a21 a22 a31 a32 a33 an,1 an,2 an,3 an,nK= 0 1 2 3 4 5 n(n-1)/2 n(n+1)/2-1a11a21 a22a31 a32 a33 an,1 an,2 an,3 an,na11 a12 a13 a1n

15、a21 a22 a23 a2na31 a32 a33 a3n an1 an2 an3 annv當當ij時時,aij 在矩陣的在矩陣的下三角下三角中。中。在在aij 之前的之前的i-1行行(從第從第1行到第行到第i-1行行)共共有有1+2+i-1=i*(i-1)/2個元素個元素,在第在第i行行上上,aij 之前有之前有ai1,ai2,ai3,ai(j-1) 即即j-1個元個元素素,因此存儲單元的下標因此存儲單元的下標k有有: k = i(i-1)/2+( j-1)v當當ij 時時aij 在矩陣的在矩陣的上三角上三角中。中。由于由于aij=aji 所以交換上式所以交換上式i,j可得可得: k =

16、j( j-1)/2+( i-1)a11 a12 a13 a1na21 a22 a23 a2na31 a32 a33 a3n an1 an2 an3 ann公式不要死記硬背公式不要死記硬背應掌握其推導過程應掌握其推導過程二、三角矩陣二、三角矩陣所謂所謂下下(上上)三角矩陣三角矩陣是指矩陣的上是指矩陣的上(下下)三角三角(不包括對不包括對角線角線)中的元均為常數中的元均為常數 c 的的 n 階矩陣。階矩陣。a11a21 a22an1 1 an2 ann. . . . . . .C下三角矩陣下三角矩陣和對稱矩陣基本一樣，只需除存儲其下和對稱矩陣基本一樣，只需除存儲其下(上上)三角中的元三角中的元之外

17、，再增加一個存儲單元存放之外，再增加一個存儲單元存放 c 。k = i (i 1)2+ j - - 1當當 i j關鍵問題關鍵問題: 如何建立數組元如何建立數組元 SAk 和矩陣元和矩陣元 aij 之間的之間的一一對應關系。一一對應關系。k = 0123n(n+1)2- - 1n(n+1)2當當 i jn(n+1)2a11a21a22a31annca12 , ,a13 所有非所有非0元素都集元素都集中在以主對角線為中中在以主對角線為中心的帶狀區域。心的帶狀區域。它可以行為主它可以行為主,或或以對角線的順序以對角線的順序,將將其壓縮到一維數組上。其壓縮到一維數組上。a00 a01 a02 0 0

18、 0 0 0 0 0a10 a11 a12 a13 0 0 0 0 0 0a20 a21 a22 a23 a24 0 0 0 0 0 0 a31 a32 a33 a34 a35 0 0 0 0 0 0 a42 a43 a44 a45 a46 0 0 0 0 0 0 a53 a54 a55 a56 a57 0 0 0 0 0 0 a64 a65 a66 a67 a68 0 0 0 0 0 0 a75 a76 a77 a78 a79 0 0 0 0 0 0 a86 a87 a88 a89 0 0 0 0 0 0 0 a97 a98 a99oo一般情況一般情況oa11 a12a21 a22 a23a

19、32 a33 a34an,n-1-1 ann an-1-1,no三對角矩陣三對角矩陣關鍵問題關鍵問題: 如何建立數組元如何建立數組元 SAk 和矩陣元和矩陣元 aij 之間的一一之間的一一對應關系。對應關系。k=(3(i-1)-1)+(j-i+2)-1=2i + j - 3(| | i - - j | | 1)a11 a12a21 a22 a23 a32 a33 a34an,n-1-1 ann an-1-1, n-2-2 an-1-1, n-1 -1 an-1-1,n a43 a44 a450aij因因對角數對角數不不同而不同同而不同第第i(i1)行的第行的第j-i+2個非零元素個非零元素|1

20、 稀疏矩陣的三元組稀疏矩陣的三元組|2 三元組的順序存儲結構三元組的順序存儲結構|3 三元組的鏈式存儲結構三元組的鏈式存儲結構稀疏矩陣稀疏矩陣非零元很少的矩陣。非零元很少的矩陣。稀疏因子稀疏因子: 設設 mn 的矩陣，有的矩陣，有 t 個非零元，令個非零元，令mnt= ，稱，稱為矩陣的稀疏因子。為矩陣的稀疏因子。通常認為通常認為 0.05 時稱為時稱為稀疏矩陣稀疏矩陣。|稀疏矩陣的非零元素由三部分組成：行下標、列下標稀疏矩陣的非零元素由三部分組成：行下標、列下標和矩陣元素值，這稱為稀疏矩陣的三元組。和矩陣元素值，這稱為稀疏矩陣的三元組。|用稀疏矩陣的三元組用稀疏矩陣的三元組序列序列表示為：表示

21、為：1,1,1,3,1,2,3,3,7,4,3,8,4,4,9。 9800070200000001A（2） 三元組的順序存儲結構三元組的順序存儲結構三元組三元組( i ，j ，aij )表示非零元素表示非零元素i 行數，行數，j 列數，列數，aij 非零元。非零元。M67 = 0 12 9 0 0 0 00 0 0 0 0 0 0- -3 0 0 0 0 14 00 0 0 24 0 0 0 00 0 18 0 0 0 0 01515 0 0 - -7 0 0 0i j aij1 2 121 3 93 1 - -33 6 14144 3 24245 2 18186 1 15156 4 -7-7

22、 SparseNode1類的一個對象表示稀疏矩陣的一個三元組，它類的一個對象表示稀疏矩陣的一個三元組，它只記錄了稀疏矩陣中的一個元素的位置和值。只記錄了稀疏矩陣中的一個元素的位置和值。public class SparseNode1 /稀疏矩陣的三元組表示的結點結構 public int row; /行下標 public int column; /列下標 public int data; /值 public SparseNode1(int i,int j,int k) row=i; column=j; data=k; public SparseNode1() this(0,0,0); publ

23、ic void output() /輸出一個元素的三元組值 下面聲明的下面聲明的Sparse1類的一個對象則表示一個稀疏矩陣，類的一個對象則表示一個稀疏矩陣，成員成員table是一個數組表示的線性表，元素類型為是一個數組表示的線性表，元素類型為SparseNode1類。構造方法將一個稀疏矩陣轉換成三元組表示法。類。構造方法將一個稀疏矩陣轉換成三元組表示法。public class Sparse1 /稀疏矩陣的三元組順序存儲結構 protected SparseNode1 table; /數組，元素為三元組 public Sparse1(int mat1) /建立三元組表示 System.out

24、.println(稀疏矩陣:); int n=mat1.length; table=new SparseNode1 n*2; /估計數組長度 int i,j,k=0; for(i=0;imat1.length;i+) for(j=0;jmat1i.length;j+) public class Sparse1_ex public static void main(String args) int mat1=1,0,0,0, /稀疏矩陣稀疏矩陣 0,0,0,0, 2,0,7,0, 0,0,8,9; Sparse1 s1=new Sparse1(mat1); /一個對象表示一個稀疏一個對象表示一個

25、稀疏矩陣矩陣 s1.output(); 程序運行結果如下：程序運行結果如下：稀疏矩陣稀疏矩陣: 1 0 0 0 0 0 0 0 2 0 7 0 0 0 8 9稀疏矩陣三元組的順序表示稀疏矩陣三元組的順序表示: 行下標行下標 列下標列下標 值值table0 = 111table1 = 312table2 = 337table3 = 438table4 = 449table5 = nulltable6 = nulltable7 = null|數組長度不易設定，可能存在溢出與浪費問題。數組長度不易設定，可能存在溢出與浪費問題。|插入、刪除操作不方便。若矩陣元素的值發生變化，一插入、刪除操作不方便。若

26、矩陣元素的值發生變化，一個為零的元素變成非零元素，就要向線性表中插入一個個為零的元素變成非零元素，就要向線性表中插入一個三元組；若非零元素變成零元素，就要從線性表中刪除三元組；若非零元素變成零元素，就要從線性表中刪除一個三元組。為了保持線性表元素間的相對次序，進行一個三元組。為了保持線性表元素間的相對次序，進行插入和刪除操作時，就必須移動元素。插入和刪除操作時，就必須移動元素。1行的單鏈表示行的單鏈表示 將稀疏矩陣每行上的若干個非零元素作為結點鏈接成一個將稀疏矩陣每行上的若干個非零元素作為結點鏈接成一個單向鏈表，每條鏈表第單向鏈表，每條鏈表第1個結點的引用存放在數組中。個結點的引用存放在數組中

27、。 常用的鏈式存儲結構有兩種：行（列）的單鏈表示和常用的鏈式存儲結構有兩種：行（列）的單鏈表示和十字鏈表示。十字鏈表示。table1234column data next1112383749圖圖5.1 稀疏矩陣的行的單鏈表示稀疏矩陣的行的單鏈表示 其中，鏈表的每個結點由其中，鏈表的每個結點由3個成員組成：個成員組成：column（列下標），（列下標），data（值）和（值）和next（后繼結點的引用）。（后繼結點的引用）。Table數組元素存放每數組元素存放每條鏈表第條鏈表第1個結點的引用。個結點的引用。 聲明稀疏矩陣以行的單鏈表示為如下的聲明稀疏矩陣以行的單鏈表示為如下的SparseNode

28、2類：類：public class SparseNode2 /稀疏矩陣行的單鏈表示public int column; /列下標public int data; /值public SparseNode2 next; /后繼結點的引用public SparseNode2(int i,int j)column=i;data=j;next=null;public SparseNode2() 下面的下面的Sparse2類實現稀疏矩陣的行的單鏈表示，成員類實現稀疏矩陣的行的單鏈表示，成員table是是一個數組，元素類型為一個數組，元素類型為SparseNode2類。構造方法是將一個稀疏類。構造方法是將一

29、個稀疏矩陣轉換成行的單鏈表示。矩陣轉換成行的單鏈表示。public class Sparse2 /稀疏矩陣行的單鏈表示protected SparseNode2 table; /數組元素引用鏈表的第1個結點public Sparse2(int mat1) /建立稀疏矩陣行的單鏈表示int n=mat1.length;table=new SparseNode2n+1;int i,j,k=0;SparseNode2 p=null,q;for(i=0;in;i+)p=tablei+1;for(j=0;j null table2=null table3= 1 2 - 3 7 - null table4

30、= 3 8 - 4 9 - null 按行的單鏈表示的稀疏矩陣，每個結點可以很容易地按行的單鏈表示的稀疏矩陣，每個結點可以很容易地找到行的后繼結點，但很難找到列的后繼結點。為充分表找到行的后繼結點，但很難找到列的后繼結點。為充分表示行和列的后繼結點，可以采用十字鏈表示。示行和列的后繼結點，可以采用十字鏈表示。 將行的單鏈表示和列的單鏈表示結合起來存儲稀疏矩將行的單鏈表示和列的單鏈表示結合起來存儲稀疏矩陣稱為十字鏈表示。陣稱為十字鏈表示。 1 2 3 412341 1 1 3 3 7 4 3 8 4 4 9 3 1 2 | 每個結點表示一個非零元素。每個結點有每個結點表示一個非零元素。每個結點有

31、5個成員：行個成員：行下標，列下標，值，行后繼引用以及列后繼引用。下標，列下標，值，行后繼引用以及列后繼引用。| 從行的角度看，需要一個數組存放行的單鏈的第從行的角度看，需要一個數組存放行的單鏈的第1個結個結點；同樣，從列的角度看，還需要一個數組存放列的單鏈點；同樣，從列的角度看，還需要一個數組存放列的單鏈的第的第1個結點。使用這種表示，各行的非零元素和各列的個結點。使用這種表示，各行的非零元素和各列的非零元素都分別鏈接在一起，最多有非零元素都分別鏈接在一起，最多有m+n條鏈。條鏈。| 對元素的查找可順著所在行的鏈進行，也可以順著所對元素的查找可順著所在行的鏈進行，也可以順著所在列的鏈進行。在列的鏈進行。|5.3.1 廣義表的概