實用數(shù)據(jù)結(jié)構(gòu)基礎第6章_多維數(shù)組和廣義表ppt課件

1、2019年5月11日星期三1第 6 章 樹 知 識 點 多維數(shù)組的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu) 特殊矩陣的壓縮存儲 稀疏矩陣的三元組存儲、十字鏈表存儲 廣義表的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其基本算法 難 點 多維數(shù)組和廣義表可以看作是線性表的推廣，其特點是線性表中的數(shù)據(jù)元素仍然是一個表。第 6 章 目 錄 6-1 6-1 多維數(shù)組多維數(shù)組 6-2 6-2 特殊矩陣的壓縮存儲特殊矩陣的壓縮存儲 6-3 6-3 稀疏矩陣稀疏矩陣 6-4 6-4 廣義表廣義表 小小 結(jié)結(jié) 驗證性實驗：稀疏矩陣和廣義表子系統(tǒng)驗證性實驗：稀疏矩陣和廣義表子系統(tǒng) 自主性實驗自主性實驗6 6：稀疏矩陣十字鏈表的存儲：稀疏矩陣十字鏈表的存儲

2、單元練習單元練習6 6 6-1 多維數(shù)組6.1.1 邏輯結(jié)構(gòu)邏輯結(jié)構(gòu) 數(shù)組作為一種數(shù)據(jù)結(jié)構(gòu)，其特點是數(shù)組作為一種數(shù)據(jù)結(jié)構(gòu)，其特點是結(jié)構(gòu)中的元素可以是具有某種結(jié)構(gòu)的數(shù)結(jié)構(gòu)中的元素可以是具有某種結(jié)構(gòu)的數(shù)據(jù)，但屬于同一數(shù)據(jù)類型。比如，一維據(jù)，但屬于同一數(shù)據(jù)類型。比如，一維數(shù)組可以看作一個線性表，二維數(shù)組可數(shù)組可以看作一個線性表，二維數(shù)組可以看作以看作“數(shù)據(jù)元素是一維數(shù)組的一維數(shù)數(shù)據(jù)元素是一維數(shù)組的一維數(shù)組，三維數(shù)組可以看作組，三維數(shù)組可以看作“數(shù)據(jù)元素是二維數(shù)據(jù)元素是二維數(shù)組的一維數(shù)組。一般把三維以上的數(shù)組的一維數(shù)組。一般把三維以上的數(shù)組稱為多維數(shù)組，數(shù)組稱為多維數(shù)組，n維的多維數(shù)組可維的多維數(shù)組可

3、以視為以視為n1維數(shù)組元素組成的線性結(jié)構(gòu)。維數(shù)組元素組成的線性結(jié)構(gòu)。其中每一個一維數(shù)組又由其中每一個一維數(shù)組又由m個單元組成。個單元組成。 圖圖6-1是一個是一個n行行m列的數(shù)組。列的數(shù)組。 在二維數(shù)組中的每一個元素最多可以有兩個直接前驅(qū)和兩個直接后繼邊在二維數(shù)組中的每一個元素最多可以有兩個直接前驅(qū)和兩個直接后繼邊界除外），在界除外），在n維數(shù)組中的每一個元素最多可以有維數(shù)組中的每一個元素最多可以有n個直接前驅(qū)和個直接前驅(qū)和n個直接后繼。個直接后繼。所以多維數(shù)組是一種非線性結(jié)構(gòu)。所以多維數(shù)組是一種非線性結(jié)構(gòu)。 數(shù)組是一個具有固定格式和數(shù)量的數(shù)據(jù)有序集，每一個數(shù)據(jù)元素有唯一的數(shù)組是一個具有固定格

4、式和數(shù)量的數(shù)據(jù)有序集，每一個數(shù)據(jù)元素有唯一的一組下標來標識，通常在很多高級語言中數(shù)組一旦被定義，每一維的大小及上一組下標來標識，通常在很多高級語言中數(shù)組一旦被定義，每一維的大小及上下界都不能改變。因此，在數(shù)組上一般不做插入或刪除數(shù)據(jù)元素的操作。在數(shù)下界都不能改變。因此，在數(shù)組上一般不做插入或刪除數(shù)據(jù)元素的操作。在數(shù)組中經(jīng)常做的兩種操作如下。組中經(jīng)常做的兩種操作如下。（1取值操作：給定一組下標，讀取其對應的數(shù)據(jù)元素。取值操作：給定一組下標，讀取其對應的數(shù)據(jù)元素。 （2賦值操作：給賦值操作：給定一組下標，存儲或修改與其相對應的數(shù)據(jù)元素。定一組下標，存儲或修改與其相對應的數(shù)據(jù)元素。 6.1.2 存儲

5、結(jié)構(gòu)存儲結(jié)構(gòu) 通常，數(shù)組在內(nèi)存被映象為向量，即用向通常，數(shù)組在內(nèi)存被映象為向量，即用向量作為數(shù)組的一種存儲結(jié)構(gòu)，這是因為在計量作為數(shù)組的一種存儲結(jié)構(gòu)，這是因為在計算機內(nèi)存儲結(jié)構(gòu)是一維的。數(shù)組的行列固定算機內(nèi)存儲結(jié)構(gòu)是一維的。數(shù)組的行列固定后，通過一個映象函數(shù)，就可以根據(jù)數(shù)組元后，通過一個映象函數(shù)，就可以根據(jù)數(shù)組元素的下標得到它的存儲地址。對于一維數(shù)組素的下標得到它的存儲地址。對于一維數(shù)組只要按下標順序分配即可；對多維數(shù)組分配只要按下標順序分配即可；對多維數(shù)組分配時，要把它的元素映象存儲在一維存儲器中。時，要把它的元素映象存儲在一維存儲器中。1存儲方式存儲方式（1以行為主以行為主row majo

6、r order） 以行為主的存儲方式也稱為按行優(yōu)先順序以行為主的存儲方式也稱為按行優(yōu)先順序方式，實現(xiàn)時按行號從小到大的順序，先存方式，實現(xiàn)時按行號從小到大的順序，先存儲第儲第0行的全部元素，再存放第行的全部元素，再存放第1行的元素、行的元素、第第2行的元素行的元素 一個一個23二維數(shù)組的邏輯結(jié)構(gòu)如圖二維數(shù)組的邏輯結(jié)構(gòu)如圖6-2所示，所示，以行為主的內(nèi)存映象如圖以行為主的內(nèi)存映象如圖6-3a所示，其所示，其分配順序為：分配順序為：a00，a01，a02，a10 ，a11，a12。 以行為主序的分配規(guī)律是：最右邊的下標先變化，即最右下標從小到大，循以行為主序的分配規(guī)律是：最右邊的下標先變化，即最右

7、下標從小到大，循環(huán)一遍后，右邊第二個下標再變環(huán)一遍后，右邊第二個下標再變，從右向左，最后是左下標。，從右向左，最后是左下標。（2以列為主序以列為主序column major order） 以列為主的存儲方式也稱為按列優(yōu)先順序方式，實現(xiàn)時按列號從小到大的順以列為主的存儲方式也稱為按列優(yōu)先順序方式，實現(xiàn)時按列號從小到大的順序，先存儲第序，先存儲第0列的全部元素，再存儲第列的全部元素，再存儲第1列的元素、第列的元素、第2 列的元素列的元素 圖圖6-2所示的邏輯結(jié)構(gòu)，以列為主的內(nèi)存映象如圖所示的邏輯結(jié)構(gòu)，以列為主的內(nèi)存映象如圖6-3b所示，其分配順序所示，其分配順序為：為：a00，a10，a01，a1

8、1，a02，a12 。 以列為主分配的規(guī)律恰好與以行為主次序相反：最左邊的下標先變化，即最以列為主分配的規(guī)律恰好與以行為主次序相反：最左邊的下標先變化，即最左下標從小到大，循環(huán)一遍后，左邊第二個下標再變左下標從小到大，循環(huán)一遍后，左邊第二個下標再變，從左向右，最后是右，從左向右，最后是右下標。下標。2存儲地址存儲地址“以行為主次序分配存儲單元為例看其地址的計算以行為主次序分配存儲單元為例看其地址的計算（1二維數(shù)組中二維數(shù)組中aij的地址的地址 在在C語言中數(shù)組中每一維的下界定義為語言中數(shù)組中每一維的下界定義為0，數(shù)組的基址為，數(shù)組的基址為LOC(a00)，每個數(shù)組，每個數(shù)組元素占據(jù)元素占據(jù)d個

9、字節(jié)，那么個字節(jié)，那么aij 的物理地址可用一個線性尋址函數(shù)計算：的物理地址可用一個線性尋址函數(shù)計算： LOC(aij) = LOC(a00) + ( in + j ) d （0下標起始的語言）下標起始的語言）（2三維數(shù)組中三維數(shù)組中aijk的地址的地址 同理對于三維數(shù)組元素同理對于三維數(shù)組元素aijk的物理地址為：的物理地址為： LOC(aijk)=LOC(a000)+( (inp+ jp +k) d （0下標起始的語言）下標起始的語言） 【例【例6-1】設二維數(shù)組】設二維數(shù)組A56，每個元素占，每個元素占4個字節(jié)個字節(jié)Byte），存），存儲器按字節(jié)編址。已知儲器按字節(jié)編址。已知A的起始地址

10、為的起始地址為2000。計算。計算（1數(shù)組的大小數(shù)組的大小 nmd=564=120 Byte（2數(shù)組結(jié)點數(shù)組結(jié)點a45的存儲地址的存儲地址 LOC(aij)=LOC(a00)+(i*n+j)*d / n為總列數(shù)為總列數(shù) LOC(a45)=2000+(46+5)4=2116（3按行為主存儲，計算按行為主存儲，計算a32的存儲地址的存儲地址 LOC(aij)=LOC(a00)+(i*n+j)*d / n為總列數(shù)為總列數(shù) LOC(a32)=2000+(36+2)4=2080（4按列為主存儲，計算按列為主存儲，計算a32的存儲地址的存儲地址 LOC(aij)=LOC(a00)+(j*m+i)*d /

11、m為總行數(shù)為總行數(shù) LOC(a32)=2000+(25+3)4=2052 【例【例6-2】若矩陣】若矩陣Anm 中存在某個元素中存在某個元素aij，滿足：，滿足：aij是第是第i行中最行中最小值且是第小值且是第j列中的最大值，則稱該元素為矩陣列中的最大值，則稱該元素為矩陣A的一個鞍點。試編的一個鞍點。試編寫一個算法，找出寫一個算法，找出A中的所有鞍點。中的所有鞍點。基本思想：在矩陣基本思想：在矩陣A中求出每一行的最小值元素，然后判斷該元素是中求出每一行的最小值元素，然后判斷該元素是否是它所在列中的最大值。如果是則打印輸出，接著處理下一行。否是它所在列中的最大值。如果是則打印輸出，接著處理下一行

12、。設矩陣設矩陣A用一個二維數(shù)組表示，其算法如下：用一個二維數(shù)組表示，其算法如下：void saddle(int A,int n,int m) int i,j,min; for(i=0;in;i+) / 按行處理按行處理 min=Ai0 for(j=1;jm;j+) if(Aijmin) min=Aij; / 找第找第i行最小值行最小值 for (j=0;jm;j+)/ 檢測最小值是否是鞍點檢測最小值是否是鞍點 if(Aij=min) k=j; p=0; while(pn & Apj=n) printf(%d,%d,%dn,i,k,min); 算法的時間復雜度為算法的時間復雜度為O(n

13、(m +n m)。6-2 特殊矩陣的壓縮存儲特殊矩陣的壓縮存儲 矩陣是一個二維數(shù)組，是眾多科學與工程矩陣是一個二維數(shù)組，是眾多科學與工程計算問題中研究的數(shù)學對象。在矩陣中非零元素計算問題中研究的數(shù)學對象。在矩陣中非零元素或零元素的分布有一定規(guī)律的矩陣稱為特殊矩陣或零元素的分布有一定規(guī)律的矩陣稱為特殊矩陣，如三角矩陣、對稱矩陣、帶狀矩陣、稀疏矩陣，如三角矩陣、對稱矩陣、帶狀矩陣、稀疏矩陣等。當矩陣的階數(shù)很大時，用普通的二維數(shù)組存等。當矩陣的階數(shù)很大時，用普通的二維數(shù)組存儲這些特殊矩陣將會占用很多的存儲單元。從節(jié)儲這些特殊矩陣將會占用很多的存儲單元。從節(jié)約存儲空間的角度考慮，下面來考慮這些特殊矩約

14、存儲空間的角度考慮，下面來考慮這些特殊矩陣的存儲方法。陣的存儲方法。 6.2.1 對稱矩陣 對稱矩陣是一種特殊矩陣，n階方陣的元素滿足性質(zhì)：aij=aji （0=i , j=n1）。 如圖6-4所示是一個階對稱矩陣。對稱矩陣是關(guān)于主對角線的對稱，因此只需存儲上三角或下三角部分的數(shù)據(jù)即可。比如，只存儲下三角中的元素aij，其特點是中j=i且0=i=n1，對于上三角中的元素aij ，它和對應的aji相等，因此當訪問的元素在上三角時，直接去訪問和它對應的下三角元素即可，這樣，原來需要nn個存儲單元，現(xiàn)在只需要n(n+1)/2個存儲單元了，節(jié)約了n(n1)/2個存儲單元。圖圖6-4 56-4 5階對稱

15、方陣及它的壓縮存儲階對稱方陣及它的壓縮存儲 如何只存儲下三角部分呢？將下三角部分以行序為主序順序存儲到一個向如何只存儲下三角部分呢？將下三角部分以行序為主序順序存儲到一個向量量SASA中去。在下三角中共有中去。在下三角中共有n(n+1)/2n(n+1)/2個元素，存儲到一個向量空間個元素，存儲到一個向量空間SA0SA0至至SAn(n+1)/2-1SAn(n+1)/2-1中，存儲順序可用圖中，存儲順序可用圖6-56-5示意。示意。圖圖6-5 對稱矩陣下三角壓縮存儲對稱矩陣下三角壓縮存儲 原矩陣下三角中的某一個元素原矩陣下三角中的某一個元素aij具體對應一個具體對應一個sak，用，用“以行優(yōu)先存放

16、下以行優(yōu)先存放下三角部分的元素時，三角部分的元素時，a00存入存入sa0，a10存入存入sa1，a11存入存入sa2。sak與與aij的的一一對應關(guān)系為：一一對應關(guān)系為： k=j(j +1)/2+i （0=k n (n+1)/21）當當ij時，在下三角部分時，在下三角部分aij前有前有i行，共有行，共有1+2+3+i個元素，而個元素，而aij是第是第i行的第行的第j個元素，即有個元素，即有k=1+2+3+i+j =i(i+1)/2+j。 當當ij時，時，aij是上三角中的元素，因為是上三角中的元素，因為aij=aji ，這樣，訪問上三角中的元素，這樣，訪問上三角中的元素aij時則去訪問和它對應

17、的下三角中的時則去訪問和它對應的下三角中的aji即可，因此將上式中的行列下標交換就即可，因此將上式中的行列下標交換就是上三角中的元素在是上三角中的元素在SA中的對應關(guān)系：中的對應關(guān)系： k=j(j +1)/2+i （0=krow=m; H-row=m; H-col=n; H-col=n; hd0=H; hd0=H; for(i=1; iS; i+) for(i=1; irow=0; p-col=0; p-row=0; p-col=0; p-right=p; p-down=p; p-right=p; p-down=p; hdi=p; hdi-1-v_next.next=p; hdi=p; hdi

18、-1-v_next.next=p; hdS-v_next.next=H; / 將頭結(jié)點們形成循環(huán)鏈表將頭結(jié)點們形成循環(huán)鏈表 for(k=1;krow=i; p-col=j; p-v_next.v=v q=hdi; while(q-right!=hdi&(q-right-col)right; p-right=q-right; / 插入插入 q-right=p; q=hdi; while(q-down!=hdj&(q-down-row)down; p-down=q-down; / 插入插入 q-down=p; return H; 上述算法中，建立頭結(jié)點循環(huán)鏈表時間復雜度為上述算法中

19、，建立頭結(jié)點循環(huán)鏈表時間復雜度為O(S)，插入每個結(jié)點，插入每個結(jié)點到相應的行表和列表的時間復雜度是到相應的行表和列表的時間復雜度是O(tS)，這是因為每個結(jié)點插入時都，這是因為每個結(jié)點插入時都要在鏈表中尋找插入位置，所以總的時間復雜度為要在鏈表中尋找插入位置，所以總的時間復雜度為O(tS)。該算法對三元。該算法對三元組的輸入順序沒有要求。如果我們輸入三元組時是按以行為主序或列組的輸入順序沒有要求。如果我們輸入三元組時是按以行為主序或列輸入的，則每次將新結(jié)點插入到鏈表的尾部的，改進算法后，時間復雜度輸入的，則每次將新結(jié)點插入到鏈表的尾部的，改進算法后，時間復雜度為為O(S+t)。2 2稀疏矩陣

20、的加法稀疏矩陣的加法 已知兩個十字鏈表存儲的稀疏矩陣已知兩個十字鏈表存儲的稀疏矩陣A A和和B B，計算，計算C=A+BC=A+B，C C也采用十字鏈表方也采用十字鏈表方式存儲，并且在式存儲，并且在A A的基礎上形成的基礎上形成C C。 由矩陣的加法規(guī)則知，只有由矩陣的加法規(guī)則知，只有A A和和B B行列對應相等，二者才能相加。行列對應相等，二者才能相加。C C中的非零中的非零元素元素cijcij只可能有只可能有3 3種情況：或者是種情況：或者是aij+bijaij+bij，或者是，或者是aijaijbij=0bij=0），或者是），或者是bijbijaij=0aij=0），因此當），因此當B

21、 B加到加到A A上時，對上時，對A A十字鏈表的當前結(jié)點來說，對應下列四種十字鏈表的當前結(jié)點來說，對應下列四種情況：或者改變結(jié)點的值情況：或者改變結(jié)點的值aij+bij0aij+bij0），或者不變），或者不變bijbij0 0），或者插入一），或者插入一個新結(jié)點個新結(jié)點aijaij0 0），還可能是刪除一個結(jié)點），還可能是刪除一個結(jié)點aij+bijaij+bij0 0）。整個運算從矩）。整個運算從矩陣的第一行起逐行進行。對每一行都從行表的頭結(jié)點出發(fā)，分別找到陣的第一行起逐行進行。對每一行都從行表的頭結(jié)點出發(fā)，分別找到A A和和B B在該在該行中的第一個非零元素結(jié)點后開始比較，然后按行中的第

22、一個非零元素結(jié)點后開始比較，然后按4 4種不同情況分別處理。設種不同情況分別處理。設papa和和pbpb分別指向分別指向A A和和B B的十字鏈表中行號相同的兩個結(jié)點，的十字鏈表中行號相同的兩個結(jié)點，4 4種情況如下：種情況如下：（1若若pa-col=pb-col且且pa-v+pb-v0，則只要用，則只要用aij+bij的值改寫的值改寫pa所指結(jié)點的值域即可。所指結(jié)點的值域即可。（2若若pa-col=pb-col且且pa-v+pb-v=0，則需要在矩陣，則需要在矩陣A的十字鏈表中刪除的十字鏈表中刪除pa所指結(jié)點，此時需改變該行鏈表中前趨結(jié)所指結(jié)點，此時需改變該行鏈表中前趨結(jié)點的點的right域

23、，以及該列鏈表中前趨結(jié)點的域，以及該列鏈表中前趨結(jié)點的down域。域。（3若若pa-col col且且pa-col0即不是表頭結(jié)點），即不是表頭結(jié)點），則只需要將則只需要將pa指針向右推進一步，并繼續(xù)進行比較。（指針向右推進一步，并繼續(xù)進行比較。（4） 若若pa-col pb-col或或pa-col0即是表頭結(jié)點），則需要在即是表頭結(jié)點），則需要在矩陣矩陣A的十字鏈表中插入一個的十字鏈表中插入一個pb所指結(jié)點。所指結(jié)點。 由前面建立十字鏈表算法知，總表頭結(jié)點的行列域存放的是由前面建立十字鏈表算法知，總表頭結(jié)點的行列域存放的是矩陣的行和列，而各行列鏈表的頭結(jié)點其行列域值為零，矩陣的行和列，而各行

24、列鏈表的頭結(jié)點其行列域值為零，當然各非零元素結(jié)點的行列域其值不會為零，下面分析的當然各非零元素結(jié)點的行列域其值不會為零，下面分析的4種情種情況利用了這些信息來判斷是否為表頭結(jié)點。況利用了這些信息來判斷是否為表頭結(jié)點。3 3 矩陣的轉(zhuǎn)置矩陣的轉(zhuǎn)置 設設SPMatrix A; SPMatrix A; 表示一表示一m m* *n n的稀疏矩陣，其轉(zhuǎn)置的稀疏矩陣，其轉(zhuǎn)置B B則是一個則是一個n n* *m m的稀疏的稀疏矩陣，因此也有矩陣，因此也有SPMatrix B; SPMatrix B; 由稀疏矩陣由稀疏矩陣A A求它的轉(zhuǎn)置求它的轉(zhuǎn)置B B只要將只要將A A的行、列轉(zhuǎn)化的行、列轉(zhuǎn)化成成B B的列

25、、行。的列、行。 將將A.dataA.data中每一三元組的行列交換后轉(zhuǎn)化到中每一三元組的行列交換后轉(zhuǎn)化到B.dataB.data后，似乎已完成后，似乎已完成了轉(zhuǎn)置，其實不然。了轉(zhuǎn)置，其實不然。A A的轉(zhuǎn)置的轉(zhuǎn)置B B如圖如圖6.156.15所示，圖所示，圖6.166.16是它對應的三元組存儲。是它對應的三元組存儲。也就是說，在也就是說，在A A的三元組存儲基礎上得到的三元組存儲基礎上得到B B的三元組表存儲。的三元組表存儲。轉(zhuǎn)置算法的實質(zhì)是將矩陣轉(zhuǎn)置算法的實質(zhì)是將矩陣A A的行和列轉(zhuǎn)化成矩陣的行和列轉(zhuǎn)化成矩陣B B的列和行。的列和行。sparmatrix Trans(sparmatrix A

26、) / sparmatrix Trans(sparmatrix A) / 調(diào)用稀疏矩陣調(diào)用稀疏矩陣A A sparmatrix B; / sparmatrix B; / 定義稀疏矩陣定義稀疏矩陣B B B.rows=A.cols; B.rows=A.cols; B.cols=A.rows;B.cols=A.rows;B.terms=A.terms;B.terms=A.terms; for (int n=0;n=A.terms-1;n+) for (int n=0;ntag=0; gh-tag=0; gh-node.data= gh-node.data=* *s;s; gh-link=NULL;

27、 gh-link=NULL; elseelse gh=new linknode; gh=new linknode; gh-tag=1; gh-tag=1; p=gh; p=gh; s+; s+; strncpy(subs,s,len-2); strncpy(subs,s,len-2); subslen-2=0; subslen-2=0; do Disastr(subs,hstr); r=CreateGL(hstr); p-node.sublist=r; q=p; len=strlen(subs); if (len0) p=new linknode; p-tag=1; q-link=p; whi

28、le (len0); q-link=NULL; return gh; 創(chuàng)建廣義表算法的時間復雜度為創(chuàng)建廣義表算法的時間復雜度為O(n)。 2廣義表取頭算法廣義表取頭算法 若廣義表若廣義表GL=（a1，a2，an），則），則headGL）=a1 。取表頭運算的結(jié)果可以是原。取表頭運算的結(jié)果可以是原子，也可以是一個子表。子，也可以是一個子表。 例如，例如，head（a1，a2），（），（a3，a4，a5），），a6）=（a1，a2）。）。Head(linknode *GL) if GL-tag=1 p=GL-hp; return p; 3. 廣義表取尾算法廣義表取尾算法 若廣義表若廣義表GL=（a

29、1，a2，an），則），則tailGL）=（a2，an） 。取表尾運算的結(jié)果。取表尾運算的結(jié)果是取出除表頭以外的所有元素。是取出除表頭以外的所有元素。 例如，例如，tail（a1，a2），（），（a3，a4，a5），），a6）=（a3，a4，a5），），a6）。）。 Tail(linknode *GL) if GL-tag=1 p=GL-tp; return p; 4. 4. 求廣義表深度算法求廣義表深度算法int Depth(linknode int Depth(linknode * *GL)GL) int max=0; int max=0;while (GL!=NULL)while (GL

30、!=NULL) if (GL-tag=0) / if (GL-tag=0) / 有子表有子表 int dep=Depth(GL-sublit) int dep=Depth(GL-sublit) if (depmax) if (depmax) max=dep; max=dep; GL=GL-link;GL=GL-link; return max+1; / return max+1; / 非空表的深度是各元素的深度的最大值加非空表的深度是各元素的深度的最大值加1 1 求廣義表深度算法的時間復雜度為求廣義表深度算法的時間復雜度為O(n)O(n)。（1 1） 數(shù)組是一個具有固定格式和數(shù)量的數(shù)據(jù)有序集，

31、每一個數(shù)據(jù)元素有唯一的數(shù)組是一個具有固定格式和數(shù)量的數(shù)據(jù)有序集，每一個數(shù)據(jù)元素有唯一的一組下標來標識，在數(shù)組上不太適宜做插入、刪除數(shù)據(jù)元素的操作。一組下標來標識，在數(shù)組上不太適宜做插入、刪除數(shù)據(jù)元素的操作。（2 2二維數(shù)組中二維數(shù)組中aijaij的地址為：的地址為： LOC(aij) = LOC(a00) + ( i LOC(aij) = LOC(a00) + ( in + j ) n + j ) d d （0 0下標起始的語言）下標起始的語言）（3 3三維數(shù)組中三維數(shù)組中aijkaijk的地址為：的地址為： LOC(aijk)=LOC(a000)+( (i LOC(aijk)=LOC(a00

32、0)+( (in np+ jp+ jp +k) p +k) d d （0 0下標起始的語下標起始的語言）言）（4 4對稱矩陣是一種特殊矩陣，對稱矩陣是一種特殊矩陣，n n階方陣的元素滿足性質(zhì)：階方陣的元素滿足性質(zhì)： aij=aji aij=aji （0i , jn-10i , jn-1）。對稱矩陣是關(guān)于主對角線的對稱，因此只需存）。對稱矩陣是關(guān)于主對角線的對稱，因此只需存儲上三角或下三角部分的數(shù)據(jù)即可。儲上三角或下三角部分的數(shù)據(jù)即可。小 結(jié) （5三角矩陣的特殊性是以主對角線劃分矩陣。主對角線任意一側(cè)不包括三角矩陣的特殊性是以主對角線劃分矩陣。主對角線任意一側(cè)不包括主對角線中的元素均為常數(shù)主對角

33、線中的元素均為常數(shù)C）。下三角矩陣，主對角線以上均為同一個）。下三角矩陣，主對角線以上均為同一個常數(shù)；上三角矩陣，主對角線以下均為同一個常數(shù)，均可以采用壓縮存儲。常數(shù)；上三角矩陣，主對角線以下均為同一個常數(shù)，均可以采用壓縮存儲。（6在在m*n的矩陣中有的矩陣中有t個非零元素，且個非零元素，且t遠小于遠小于m*n，這樣的矩陣稱稀疏矩陣。，這樣的矩陣稱稀疏矩陣。稀疏矩陣常用的有：三元組表存儲、帶行指針的鏈表存儲、十字鏈表存儲等存稀疏矩陣常用的有：三元組表存儲、帶行指針的鏈表存儲、十字鏈表存儲等存儲方法。儲方法。（7） 廣義表是廣義表是nn0個數(shù)據(jù)元素的有序序列，廣義表的元素可以是單元素，個數(shù)據(jù)元素

34、的有序序列，廣義表的元素可以是單元素，也可以是一個廣義表。也可以是一個廣義表。（8） 由于廣義表的元素有兩種形式，所以其結(jié)點的存儲形式也有兩種：表結(jié)由于廣義表的元素有兩種形式，所以其結(jié)點的存儲形式也有兩種：表結(jié)點由標志域、表頭指針域、表尾指針域組成；而原子結(jié)點由標志域和值域組成。點由標志域、表頭指針域、表尾指針域組成；而原子結(jié)點由標志域和值域組成。1 1實驗目的實驗目的 （1 1） 掌握稀疏矩陣三元組表的存儲方法。掌握稀疏矩陣三元組表的存儲方法。 （2 2掌握稀疏矩陣三元組表創(chuàng)建、顯示、轉(zhuǎn)置和查找等算法。掌握稀疏矩陣三元組表創(chuàng)建、顯示、轉(zhuǎn)置和查找等算法。 （3 3掌握廣義表的存儲方法。掌握廣義表的存儲方法。 （4 4掌握廣義表的新建、顯示和查找等算法。掌握廣義表的新建、顯示和查找等算法。 （5 5掌握稀疏矩陣三元組表和廣義表的算法分析方法。掌握稀疏矩陣三元組表和廣義表的算法分析方法。2 2實驗內(nèi)容實驗內(nèi)容 （1 1編寫稀疏矩陣三元組表的存儲程序；編寫稀疏矩陣三元組表的存儲程序； （2 2編寫疏矩陣三元組表創(chuàng)建、顯示、轉(zhuǎn)置和查找程序；編寫疏矩陣三元組表創(chuàng)建、顯示、轉(zhuǎn)置和查找程序； （3 3編寫建立廣義表的程序；編寫建立廣義表的程序； （4 4編寫廣義表的顯示和查找程序；編寫廣義表的顯示和查找程序； （5 5設計選擇式菜