第5章數(shù)組和廣義表

1、2021-12-2312021-12-232 2021-12-233 數(shù)組是大家都已經(jīng)很熟悉的一種數(shù)據(jù)類型，幾乎所有高級語數(shù)組是大家都已經(jīng)很熟悉的一種數(shù)據(jù)類型，幾乎所有高級語言程序設計中都設定了數(shù)組類型。言程序設計中都設定了數(shù)組類型。 數(shù)組數(shù)組（ArrayArray）是由是由n(n1)個個相同類型數(shù)據(jù)元素相同類型數(shù)據(jù)元素a0，al，ai，an-1構成的構成的有限序列有限序列。n是數(shù)組的長度。其中數(shù)組中的數(shù)據(jù)元素是數(shù)組的長度。其中數(shù)組中的數(shù)據(jù)元素ai是是一個數(shù)據(jù)結構，即一個數(shù)據(jù)結構，即ai可以是線性表中的一個元素，本身也可以是可以是線性表中的一個元素，本身也可以是一個線性表一個線性表，而線性子表

2、中的每一個數(shù)據(jù)元素還可以再分解，而線性子表中的每一個數(shù)據(jù)元素還可以再分解 。根據(jù)數(shù)組元素根據(jù)數(shù)組元素ai的組織形式不同，數(shù)組可以分為一維數(shù)組、二維的組織形式不同，數(shù)組可以分為一維數(shù)組、二維數(shù)組以及多維（數(shù)組以及多維（n維）數(shù)組。維）數(shù)組。 2021-12-2342021-12-2351一維數(shù)組一維數(shù)組 一維數(shù)組可以看成是一個線性表或一個向量，它在計算機內(nèi)是一維數(shù)組可以看成是一個線性表或一個向量，它在計算機內(nèi)是存放在一塊連續(xù)的存儲單元中，適合于隨機查找。存放在一塊連續(xù)的存儲單元中，適合于隨機查找。 一維數(shù)組中，一旦一維數(shù)組中，一旦a0的存儲地址、一個數(shù)據(jù)元素所占存儲單元的存儲地址、一個數(shù)據(jù)元素所

3、占存儲單元數(shù)數(shù)k確定，則確定，則ai的存儲地址的存儲地址LOC(ai)就可求出：就可求出： LOC(ai)=LOC(a0)+i*k (0in) 2二維數(shù)組二維數(shù)組 二維數(shù)組，又稱矩陣二維數(shù)組，又稱矩陣(matrix)。二維數(shù)組中的每一個元素又是二維數(shù)組中的每一個元素又是一個定長的線性表（一維數(shù)組），都要受到兩個關系即行關系和一個定長的線性表（一維數(shù)組），都要受到兩個關系即行關系和列關系的約束，也就是每個元素都同屬于兩個線性表。列關系的約束，也就是每個元素都同屬于兩個線性表。例如，設例如，設A是一個有是一個有m行行n列的二維數(shù)組，則列的二維數(shù)組，則A可以表示為：可以表示為：2021-12-236

4、 a0,0 a0,1 a0,n-1A m n = a1,0 a1,1 a1,n-1 am-1,0 am-1,1 am-1,n-1 可以看成由可以看成由m m個行向量組成的向量，也可以看由個行向量組成的向量，也可以看由n n個列向量組成個列向量組成的向量。的向量。 數(shù)組中的每個元素由元素值數(shù)組中的每個元素由元素值a aijij及一組下標（及一組下標（i i，j j）來確定。來確定。a aijij既屬于第既屬于第i i行的行向量，又屬于第行的行向量，又屬于第j j列的列向量。列的列向量。 其中，其中，a ai i=(=( a ai i,0,0 a ai i,1,1 a ai i,n-1,n-1)

5、(0) (0i in)n) 可以認為可以認為A Am m* *n n=A=A，A A是這樣的一維數(shù)組：是這樣的一維數(shù)組： A=( aA=( a0 0，a al l，a ai i，a am-1m-1) ) 2021-12-237 顯然，二維數(shù)組同樣滿足數(shù)組的定義。一個二維數(shù)組可以看顯然，二維數(shù)組同樣滿足數(shù)組的定義。一個二維數(shù)組可以看作是每個數(shù)據(jù)元素都是相同類型的一維數(shù)組。以此類推，任何多作是每個數(shù)據(jù)元素都是相同類型的一維數(shù)組。以此類推，任何多維數(shù)組都可以看作一個線性表，這時線性表中的每個數(shù)據(jù)元素也維數(shù)組都可以看作一個線性表，這時線性表中的每個數(shù)據(jù)元素也是一個線性表。多維數(shù)組是特殊的線性表，是線性

6、表的推廣。是一個線性表。多維數(shù)組是特殊的線性表，是線性表的推廣。數(shù)組的性質(zhì)：數(shù)組的性質(zhì)：(1) (1) 數(shù)組中的數(shù)據(jù)元素數(shù)目固定。一旦定義了一個數(shù)組，其數(shù)據(jù)數(shù)組中的數(shù)據(jù)元素數(shù)目固定。一旦定義了一個數(shù)組，其數(shù)據(jù)元素數(shù)目不再有增減變化。它屬于靜態(tài)分配存儲空間的數(shù)據(jù)結構。元素數(shù)目不再有增減變化。它屬于靜態(tài)分配存儲空間的數(shù)據(jù)結構。(2) (2) 數(shù)組中的數(shù)據(jù)元素必須具有相同的數(shù)據(jù)類型。數(shù)組中的數(shù)據(jù)元素必須具有相同的數(shù)據(jù)類型。(3) (3) 數(shù)組中的每個數(shù)據(jù)元素都有一組唯一的下標值。數(shù)組中的每個數(shù)據(jù)元素都有一組唯一的下標值。 (4) (4) 數(shù)組是一種隨機存儲結構。可隨機存取數(shù)組中的任意數(shù)數(shù)組是一種隨機

7、存儲結構?？呻S機存取數(shù)組中的任意數(shù)據(jù)元素。據(jù)元素。 2021-12-238 數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。因此，除了結數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。因此，除了結構的初始化和銷毀之外，構的初始化和銷毀之外，數(shù)組的基本操作一般不會含有元素的插入數(shù)組的基本操作一般不會含有元素的插入或刪除等操作或刪除等操作, ,數(shù)組只有數(shù)組只有訪問數(shù)組元素訪問數(shù)組元素和修改元素值的操作。和修改元素值的操作。 (1) (1) value(Avalue(A，indexindexl l，indexindex2 2，indexindexd d) )：A A是已存在的是已存在的d d維維數(shù)組，數(shù)組，in

8、dexindexl l，indexindex2 2，indexindexd d是指定的是指定的d d個下標值，且這些下個下標值，且這些下標均不超過對應維的上界。其運算結果是返回由下標指定的標均不超過對應維的上界。其運算結果是返回由下標指定的A A中的中的對應元素的值。對應元素的值。(2) (2) assign(Aassign(A，e e，indexindexl l，indexindex2 2，indexindexd d) )：A A是已存在的是已存在的d d維數(shù)組，維數(shù)組，e e為元素變量，為元素變量，indexindexl l，indexindex2 2，indexindexd d是指定的是

9、指定的d d個個下標值，且這些下標均未越界。其運算結果是將下標值，且這些下標均未越界。其運算結果是將e e的值賦給由下標的值賦給由下標指定的指定的A A中的對應元素。中的對應元素。2021-12-239(3) (3) dispdisp(A)(A)：輸出數(shù)組輸出數(shù)組A A的所有元素。的所有元素。在大多數(shù)程序設計語言中，取數(shù)組元素值操作在大多數(shù)程序設計語言中，取數(shù)組元素值操作value(Avalue(A，indexindexl l，indexindex2 2，indexindexd d) ) 通常直接寫作通常直接寫作AAindexindexl l index index2 2 indexindex

10、d d ，而對數(shù)組元素的賦值操作而對數(shù)組元素的賦值操作assign(Aassign(A，e e，indexindexl l，indexindex2 2，indexindexd d) )寫作寫作e= Ae= Aindexindexl l index index2 2 indexindexd d ，或者類似的形式?；蛘哳愃频男问?。 2021-12-2310 由于數(shù)組一般不作刪除或插入運算，所以一旦數(shù)組被定義后，由于數(shù)組一般不作刪除或插入運算，所以一旦數(shù)組被定義后，數(shù)組中的元素個數(shù)和元素之間的關系就不再變動。通常采用順序存數(shù)組中的元素個數(shù)和元素之間的關系就不再變動。通常采用順序存儲結構表示數(shù)組。儲結

11、構表示數(shù)組。 對于一維數(shù)組，數(shù)組的存儲結構關系為對于一維數(shù)組，數(shù)組的存儲結構關系為: : LOC(ai)=LOC(a0)+i * k (0in) 對于二維數(shù)組，由于計算機的存儲單元是一維線性結構，如何對于二維數(shù)組，由于計算機的存儲單元是一維線性結構，如何用線性的存儲結構存放二維數(shù)組元素就有行用線性的存儲結構存放二維數(shù)組元素就有行/ /列次序問題。常用兩列次序問題。常用兩種存儲方法：以行序種存儲方法：以行序( (row major order)row major order)為主序的存儲方式和以列為主序的存儲方式和以列序序( (column major order)column major or

12、der)為主序的存儲方式。為主序的存儲方式。 2021-12-2311 行優(yōu)先順序行優(yōu)先順序將數(shù)組元素按行排列，第將數(shù)組元素按行排列，第i+1i+1個行向量個行向量緊接在第緊接在第i i個行向量后面。以二維數(shù)組為例，按行優(yōu)先順序個行向量后面。以二維數(shù)組為例，按行優(yōu)先順序存儲的線性序列為：存儲的線性序列為： a a1111,a,a1212, ,a,a1n1n,a,a2121,a,a2222, ,a a2n2n, ,a,am1m1,a,am2m2, , ,a amnmn 在在PASCALPASCAL、C C語言中，數(shù)組就是按行優(yōu)先順序存儲的。語言中，數(shù)組就是按行優(yōu)先順序存儲的。 列優(yōu)先順序列優(yōu)先順

13、序將數(shù)組元素按列向量排列，第將數(shù)組元素按列向量排列，第j+1j+1個列個列向量緊接在第向量緊接在第j j個列向量之后，個列向量之后，A A的的m m* *n n個元素按列優(yōu)先順序個元素按列優(yōu)先順序存儲的線性序列為：存儲的線性序列為： a a1111,a,a2121, ,a,am1m1,a,a1212,a,a2222, ,a am2m2, ,a,an1n1,a,an2n2, , ,a anmnm 在在FORTRANFORTRAN語言中，數(shù)組就是按列優(yōu)先順序存儲的。語言中，數(shù)組就是按列優(yōu)先順序存儲的。2021-12-2312 圖圖 5-1 二維數(shù)組的兩種存儲結構二維數(shù)組的兩種存儲結構 a00 a0

14、1A= a10 a11 a20 a21a00a01a10a11a20a21(a)二維數(shù)組a00a10a20a01a11a21(c)列序為主序(b)行序為主序對一個以行序為主序的計算機系統(tǒng)，當二維數(shù)組第一個數(shù)據(jù)元素對一個以行序為主序的計算機系統(tǒng)，當二維數(shù)組第一個數(shù)據(jù)元素a a0,00,0的存儲地址的存儲地址LOC(aLOC(a0,00,0) )以及每個數(shù)據(jù)元素所占用的存儲單元以及每個數(shù)據(jù)元素所占用的存儲單元k k確定確定后，該二維數(shù)組中任一數(shù)據(jù)元素后，該二維數(shù)組中任一數(shù)據(jù)元素a ai i,j,j的存儲地址可由下式確定的存儲地址可由下式確定:LOC(LOC(a ai i,j,j)=LOC(a)=L

15、OC(a0,00,0)+(i)+(in+jn+j) k) k其中其中n為每行中的列數(shù)。為每行中的列數(shù)。 2021-12-2313 圖圖 5-1 二維數(shù)組的兩種存儲結構二維數(shù)組的兩種存儲結構 a00 a01A= a10 a11 a20 a21a00a01a10a11a20a21(a)二維數(shù)組a00a10a20a01a11a21(c)列序為主序(b)行序為主序對一個以行序為主序的計算機系統(tǒng)，當二維數(shù)組第一個數(shù)據(jù)元素對一個以行序為主序的計算機系統(tǒng)，當二維數(shù)組第一個數(shù)據(jù)元素a a0,00,0的存儲地址的存儲地址LOC(aLOC(a0,00,0) )以及每個數(shù)據(jù)元素所占用的存儲單元以及每個數(shù)據(jù)元素所占用

16、的存儲單元k k確定確定后，該二維數(shù)組中任一數(shù)據(jù)元素后，該二維數(shù)組中任一數(shù)據(jù)元素a ai i,j,j的存儲地址可由下式確定的存儲地址可由下式確定:LOC(LOC(a ai i,j,j)=LOC(a)=LOC(a0,00,0)+(i)+(in+jn+j) k) k其中其中n為每行中的列數(shù)。為每行中的列數(shù)。 2021-12-2314 【例【例5-15-1】對于給定的二維數(shù)組】對于給定的二維數(shù)組float a34float a34，計算：計算： (1) (1) 數(shù)組數(shù)組a a中的數(shù)組元素數(shù)目；中的數(shù)組元素數(shù)目； (2) (2) 若數(shù)組若數(shù)組a a的起始地址為的起始地址為10001000，且每個數(shù)組元

17、素長度為，且每個數(shù)組元素長度為3232位位( (即即4 4個字節(jié)個字節(jié)) )，數(shù)組元素，數(shù)組元素a23a23的內(nèi)存地址。的內(nèi)存地址?！窘狻俊窘狻?1)(1)由于由于C C語言中數(shù)組的行、列下標值的下界均為語言中數(shù)組的行、列下標值的下界均為0 0，該數(shù)組，該數(shù)組行上界為行上界為3-1=23-1=2，列上界為，列上界為4-1=34-1=3，所以該數(shù)組的元素數(shù)目共有，所以該數(shù)組的元素數(shù)目共有3 3* *4=124=12個。個。 (2) (2)由于由于C C語言采用行序為主序的存儲方式，有：語言采用行序為主序的存儲方式，有： LOC(aLOC(a2,32,3)=LOC(a)=LOC(a0,00,0)+

18、(i)+(i* *n+j)n+j)* *k k =1000+(2 =1000+(2* *4+3)4+3)* *4 4 =1044 =10442021-12-2315 【例【例5-25-2】有】有m m名學生，每人考名學生，每人考n n門功課，試寫出求任一學生總分數(shù)門功課，試寫出求任一學生總分數(shù)和任一課程總分數(shù)的數(shù)據(jù)結構和算法。和任一課程總分數(shù)的數(shù)據(jù)結構和算法?！窘狻堪褜W生的考試成績存放在【解】把學生的考試成績存放在m m行行n n列的二維數(shù)組中，則第列的二維數(shù)組中，則第i(0i(0im)im)行第行第j(0j(0jn)jn)列中存放了第列中存放了第i i個學生的第個學生的第j j門課程考試成績

19、。門課程考試成績。即數(shù)據(jù)結構為：即數(shù)據(jù)結構為：#define M 10 /假設假設為為1010人人#define N 3 /假設假設為為3 3int scoreMN; /學生成績二維數(shù)組學生成績二維數(shù)組求第求第i i名學生總分數(shù)的算法為：名學生總分數(shù)的算法為：int student_sum(int scoreMN,int i) int j,sum=0; for(j=0;jN;j+) sum=sum+scoreij; return(sum); 2021-12-2316 求第求第j j門課程總分數(shù)的算法為：門課程總分數(shù)的算法為：int course_sum(int scoreMN,int j) i

20、nt i,sum=0; for(i=0;iM;i+) sum=sum+scoreij; return(sum); 2021-12-2317 矩陣是數(shù)值計算程序設計中經(jīng)常用到的數(shù)學模型，它是矩陣是數(shù)值計算程序設計中經(jīng)常用到的數(shù)學模型，它是由由 m m 行和行和 n n 列的數(shù)值構成（當列的數(shù)值構成（當m=n m=n 時稱為方陣）。時稱為方陣）。在高級在高級程序設計語言中程序設計語言中，通常用，通常用表示矩陣。然而表示矩陣。然而在數(shù)值分在數(shù)值分析過程中經(jīng)常遇到一些比較特殊的矩陣，它們的階數(shù)很高，析過程中經(jīng)常遇到一些比較特殊的矩陣，它們的階數(shù)很高，矩陣中元素數(shù)量很大，而且有很多元素的值相同或零值元素

21、，矩陣中元素數(shù)量很大，而且有很多元素的值相同或零值元素，如如對稱矩陣對稱矩陣、三角矩陣三角矩陣、帶狀矩陣帶狀矩陣和和稀疏矩陣稀疏矩陣等。等。為了節(jié)省為了節(jié)省存儲空間并且加快處理速度，需要對存儲空間并且加快處理速度，需要對這類矩陣這類矩陣進行壓縮存儲，進行壓縮存儲，壓縮存儲的原則壓縮存儲的原則是：是：。 2021-12-2318。 對稱矩陣是一個對稱矩陣是一個n n階階方陣。若一個方陣。若一個n n階矩陣階矩陣A A中的元素滿足中的元素滿足: : a ai i,j,j= =a aj j,I ,I (0i(0i，jn-1)jn-1)，則稱則稱A A為為n n階對稱矩陣。階對稱矩陣。 1 5 1 3

22、 7 a00 5 0 8 0 0 a10 a 11 1 8 9 2 6 a20 a21 a23 3 0 2 5 1 . 7 0 6 1 3 an-1 0 a n-1 1 a n-1 2 a n-1 n-1 對稱矩陣對稱矩陣2021-12-2319 在這個下三角矩陣中，第在這個下三角矩陣中，第i i行恰有行恰有i+1i+1個元素，元素總數(shù)為：個元素，元素總數(shù)為： ( (i+1)=n(n+1)/2i+1)=n(n+1)/2 由于對稱矩陣中的元素關于主對角線對稱，因此由于對稱矩陣中的元素關于主對角線對稱，因此可以為每一可以為每一對對稱的矩陣元素分配對對稱的矩陣元素分配 1 1 個存儲空間，個存儲空間

23、，n n階矩陣中的階矩陣中的n nn n個元素個元素就可以被壓縮到就可以被壓縮到 n(n+1)/2n(n+1)/2 個元素的存儲空間中去。個元素的存儲空間中去。 稱一維數(shù)組稱一維數(shù)組sa0.n(n+1)/2 為為n 階對稱矩陣階對稱矩陣A的壓縮存儲。的壓縮存儲。其存儲對應關系如上圖其存儲對應關系如上圖 : : k 0 1 2 3 4 n(n+1)/2-1a0,0 a1,0 a1,1 a2,0 a2,1 an-1,0 an-1,n-1Sak隱 含 元 素a0,1 a0,2 a0,n-1 對稱矩陣的壓縮存儲對稱矩陣的壓縮存儲 2021-12-2320其中，其中，sbn(n+1)/2中存放常數(shù)中存放

24、常數(shù)c或或0。 2021-12-2321常見的有三對角矩陣、五對角矩陣、七對角矩陣等。常見的有三對角矩陣、五對角矩陣、七對角矩陣等。具有具有3條非零對角線的對角矩陣條非零對角線的對角矩陣 66655655544544433433322322211211100100000000000000000000000000000000aaaaaaaaaaaaaaaaaaa2021-12-2322 ：對特殊矩陣的壓縮存儲實質(zhì)上就是將二維矩陣中的部分：對特殊矩陣的壓縮存儲實質(zhì)上就是將二維矩陣中的部分元素按照某種方案排列到一維數(shù)組中，不同的排列方案也就對應元素按照某種方案排列到一維數(shù)組中，不同的排列方案也就對應

25、不同的存儲方案。不同的存儲方案。2021-12-23235.2.2 稀疏矩陣的壓縮存儲方法稀疏矩陣的壓縮存儲方法 如果一個矩陣中有很多元素的值為零，即零元素的個數(shù)遠遠如果一個矩陣中有很多元素的值為零，即零元素的個數(shù)遠遠大于非零元素的個數(shù)時，稱該矩陣為稀疏矩陣。大于非零元素的個數(shù)時，稱該矩陣為稀疏矩陣。 根據(jù)存儲時所附加信息的不同，稀疏矩陣的順序存儲方法包根據(jù)存儲時所附加信息的不同，稀疏矩陣的順序存儲方法包括：三元組表示法、帶輔助行向量的二元組表示法和偽地址表示括：三元組表示法、帶輔助行向量的二元組表示法和偽地址表示法，其中以三元組表示法最常用。法，其中以三元組表示法最常用。 三元組表示法就是在

26、存儲非零元的同時，存儲該元素所對應三元組表示法就是在存儲非零元的同時，存儲該元素所對應的行下標和列下標。稀疏矩陣中的每一個非零元素由一個三元組的行下標和列下標。稀疏矩陣中的每一個非零元素由一個三元組( (i i，j j，a aijij) )唯一確定。矩陣中所有非零元素存放在由三元組組唯一確定。矩陣中所有非零元素存放在由三元組組成的數(shù)組中。成的數(shù)組中。 由由線性表的兩種不同存儲結構可以得到稀疏矩陣壓縮的不同線性表的兩種不同存儲結構可以得到稀疏矩陣壓縮的不同的存儲方法。的存儲方法。 2021-12-2324 假設有一個假設有一個6 67 7階稀疏矩陣階稀疏矩陣A A，其元素情況以及非零元對應其元素

27、情況以及非零元對應的三元組表（以行序為主序）如圖所示。的三元組表（以行序為主序）如圖所示。 0 0 1 0 0 0 0 0 2 0 0 0 0 0A67 = 3 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 7 4 0 6 7 71 0 2 12 1 1 23 2 0 34 3 3 55 4 4 66 5 5 77 5 6 4序號 行 列 值 (a) 稀疏矩陣稀疏矩陣 (b) 三元組表示三元組表示 三元組表中的第一行分別表示稀疏矩陣三元組表中的第一行分別表示稀疏矩陣A A的行數(shù)、列數(shù)和非零的行數(shù)、列數(shù)和非零元的個數(shù)。元的個數(shù)。顯然，非零元素

28、的三元組是按行號遞增的順序、相同顯然，非零元素的三元組是按行號遞增的順序、相同行號的三元組按列號遞增的順序排列的。行號的三元組按列號遞增的順序排列的。2021-12-23251 1三元組順序表三元組順序表 假設以行序為主序，且以一維數(shù)組作為三元組表的存儲結構，假設以行序為主序，且以一維數(shù)組作為三元組表的存儲結構，可以得到稀疏矩陣的一種壓縮存儲方法，稱為三元組順序表。三可以得到稀疏矩陣的一種壓縮存儲方法，稱為三元組順序表。三元組順序表的數(shù)據(jù)結構定義如下：元組順序表的數(shù)據(jù)結構定義如下：#define NUM 100 /矩陣中非零元素最大個數(shù)矩陣中非零元素最大個數(shù)typedef struct /三元

29、組結構三元組結構 int r, c; /行行(列列)號號 ElemType d; /元素值元素值 tupletype; /三元組定義三元組定義typedef struct int rows; /矩陣行數(shù)值矩陣行數(shù)值 int cols; /矩陣列數(shù)值矩陣列數(shù)值 int nums; /非零元素個數(shù)非零元素個數(shù) tupletype dataNUM; /三元組表三元組表 table; /三元組順序表定義三元組順序表定義 2021-12-2326 1稀疏矩陣的轉置運算稀疏矩陣的轉置運算 轉置是矩陣中最簡單的一種運算。轉置是矩陣中最簡單的一種運算。 對于一個對于一個m mn n的矩陣其轉置矩陣是一個的矩陣

30、其轉置矩陣是一個n nm m的矩陣，設為的矩陣，設為B Bn nm m 且滿足且滿足a ai i ,j ,j= =b bj j,i ,i 即：即：aij=bjiaij=bji，其中：其中：00im-1im-1，0jn-10jn-1 即即A A的行是的行是B B的列，的列，A A的列是的列是B B的行。的行。稀疏矩陣的三元組表稀疏矩陣的三元組表2021-12-2327三元組表示的稀疏矩陣的轉置常用的算法有以下兩種：三元組表示的稀疏矩陣的轉置常用的算法有以下兩種：1 1）矩陣的列序轉置）矩陣的列序轉置（傳統(tǒng)的轉置算法）（傳統(tǒng)的轉置算法）矩陣矩陣A是按行序為主序存儲的，若按列序為主序進行轉置就可以是

31、按行序為主序存儲的，若按列序為主序進行轉置就可以得到得到A陣的轉置矩陣陣的轉置矩陣B。假設矩陣假設矩陣A的三元組存入一維數(shù)組中，只的三元組存入一維數(shù)組中，只要在數(shù)組中按三元組的列域要在數(shù)組中按三元組的列域cols的值開始掃描，從第的值開始掃描，從第0列至第列至第n-1列列，依序將三元組列域與行域之值對換，并順次存人數(shù)組，依序將三元組列域與行域之值對換，并順次存人數(shù)組mb中。算中。算法如下：法如下：int transpose(table ma,table mb) int i,j,k=0,n,t; if(ma.nums=0)return(0)； /矩陣中無非零元素矩陣中無非零元素 m=ma.row

32、s; /m為矩陣為矩陣A的列數(shù)的列數(shù) n=ma.cols; /n為矩陣為矩陣A的行數(shù)的行數(shù) t=ma.nums; /為矩陣中非零元素個數(shù)為矩陣中非零元素個數(shù) mb.rows=n; /轉置矩陣轉置矩陣B的列數(shù)的列數(shù) mb.cols; /轉置矩陣轉置矩陣B的行數(shù)的行數(shù) mb.nums=t; /轉置矩陣中的非零元素個數(shù)轉置矩陣中的非零元素個數(shù) for(i=0;in;i+) /按矩陣按矩陣A的列序掃描的列序掃描 2021-12-2328for(j=0;jt;j+) if(ma.dataj.c=i) /判斷第判斷第j個三元組是不是第個三元組是不是第i列的列的 mb.datak.r=ma.dataj.c;

33、 mb.datak.c=ma.dataj.r; mb.datak+.d=ma.dataj.d; return(1); /成功完成矩陣轉置成功完成矩陣轉置 以上算法的時間復雜度分析：以上算法的時間復雜度分析：若若n n為轉置矩陣的列數(shù)，為轉置矩陣的列數(shù)，t t為矩陣為矩陣中非零元素個數(shù)，則算法的時間花費主要在兩個循環(huán)上，所以若中非零元素個數(shù)，則算法的時間花費主要在兩個循環(huán)上，所以若時間復雜度為時間復雜度為O(nO(nt)t)。也就是說，時間的花費和矩陣也就是說，時間的花費和矩陣A A的列數(shù)和的列數(shù)和非零元素個數(shù)的乘積成正比。若用非零元素個數(shù)的乘積成正比。若用m mn n的二維數(shù)組表示矩陣，則的二

34、維數(shù)組表示矩陣，則相應的矩陣轉置算法的循環(huán)為：相應的矩陣轉置算法的循環(huán)為：for ( i=0for ( i=0；i in n；i+ )i+ ) for (j=0 for (j=0；j jm m；j+j+ bij=aji bij=aji； 此時，時間復雜度為此時，時間復雜度為O(mn) 。2021-12-23292 2）快速轉置算法：）快速轉置算法： 三元組順序表雖然節(jié)省了存儲空間，但時間復雜度比三元組順序表雖然節(jié)省了存儲空間，但時間復雜度比一般矩陣轉置的算法還要復雜，同時還有可能增加算是法一般矩陣轉置的算法還要復雜，同時還有可能增加算是法的難度。因此，此算法僅適用于的難度。因此，此算法僅適用于

35、t=mt=m* *n n的情況。的情況。 其算法思想為：對其算法思想為：對A A掃描一次，按掃描一次，按A A第二列提供的列號一第二列提供的列號一次確定位置裝入次確定位置裝入B B的一個三元組。具體實施如下：一遍掃描的一個三元組。具體實施如下：一遍掃描先確定三元組的位置關系，二次掃描由位置關系裝入三元先確定三元組的位置關系，二次掃描由位置關系裝入三元組?？梢?，位置關系是此種算法的關鍵。組?？梢?，位置關系是此種算法的關鍵。 為了預先確定矩陣為了預先確定矩陣M M中的每一列的第一個非零元素在數(shù)組中的每一列的第一個非零元素在數(shù)組T T中中應有的位置，需要先求得矩陣應有的位置，需要先求得矩陣M M中的

36、每一列中非零元素的個數(shù)。中的每一列中非零元素的個數(shù)。因為矩陣因為矩陣M M中第一列的第一個非零元素在數(shù)組中第一列的第一個非零元素在數(shù)組T T中應有的位置等于中應有的位置等于前一列第一個非零元素的位置加上前列非零元素的個數(shù)。前一列第一個非零元素的位置加上前列非零元素的個數(shù)。2021-12-2330為此，需要設置兩個一維數(shù)組為此，需要設置兩個一維數(shù)組num0.nnum0.n和和rposrpos0.n0.n：num0.nnum0.n：統(tǒng)計統(tǒng)計M M中每列非零元素的個數(shù)。中每列非零元素的個數(shù)。rposrpos0.n0.n：M M中的每列第一個非零元素在中的每列第一個非零元素在T T中的位置。中的位置。

37、算法通過算法通過rposrpos數(shù)組建立位置對應關系：數(shù)組建立位置對應關系： rposrpos0=0 0=0 ； rpos rpos colcol=rposrpos colcol-1+num-1+numcolcol-1 0-1 0colcolM.rowsM.rows；例如圖例如圖5-4(5-4(a) a) 所示的稀疏矩陣的三元組表對應的所示的稀疏矩陣的三元組表對應的num0.n-1num0.n-1和和rposrpos0.n-10.n-1如圖如圖5-55-5所示。所示。 （算法見教科書）（算法見教科書）圖圖5-5 5-5 矩陣的矩陣的numnum和和rpos rpos 數(shù)組值數(shù)組值Col 0 1

38、 2 3 4 5 6numcol 1 1 1 1 1 1 1rposcol 0 1 2 3 4 5 62021-12-2331快速轉置算法如下：快速轉置算法如下： 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;

39、 for(col=2;col=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; 2021-12-2332帶行表的三元組帶行表的三元組) ) 有時為了方便某些矩陣運算，在按行優(yōu)先存儲的三元組有時為了方便某些矩陣運算，在按行優(yōu)先存儲的三元組中，加入一個行表來記錄稀疏矩陣中每行的非零元素在三元中，加入一個行表來記錄稀疏矩陣中每行的非零元素在三元組

40、表中的起始位置。當將行表作為三元組表的一個新增屬性組表中的起始位置。當將行表作為三元組表的一個新增屬性加以描述時，就得到了稀疏矩陣的另一種順序存儲結構：帶加以描述時，就得到了稀疏矩陣的另一種順序存儲結構：帶行表的三元組表。行表的三元組表。稱這種稱這種“帶行鏈接信息帶行鏈接信息”的三元組表為行邏的三元組表為行邏輯鏈接的順序表。輯鏈接的順序表。其類型描述如下：其類型描述如下： # #definedefine maxrow maxrow 100 100 typedef struct typedef struct triple data triple datamaxsizemaxsize; int r

41、pos int rpos maxrowmaxrow; int int n,m,t; n,m,t; rtripletable rtripletable 2021-12-2333 下面討論兩個稀疏矩陣相乘的例子，容易看出這種表示下面討論兩個稀疏矩陣相乘的例子，容易看出這種表示方法的優(yōu)越性：方法的優(yōu)越性： 若設若設 Q=M*N 其中，其中，M是是m1*n1矩陣，矩陣，N是是m2*n2矩陣。矩陣。 當當n1=m2時有：時有： for(i=1;i=m1;+i) for(j=1;j=n2;+j) qij=0 for(k=1;k(N)?(M)：(N) /矩陣行列較大者矩陣行列較大者typedef struc

42、t mtxn int row； int col； struct mtxn *right，*down； union int value； struct mtxn *next； tag； MatNode； 2021-12-2342 廣義表也是線性表的推廣，是一種多層次的線性結構，廣義表也是線性表的推廣，是一種多層次的線性結構，線性表線性表中的元素僅限于原子項，即不可以再分；中的元素僅限于原子項，即不可以再分； 而廣義表中的元素既可以是原子項，也可以是子表（另一個線而廣義表中的元素既可以是原子項，也可以是子表（另一個線性表）。性表）。主要用于人工智能領域的表處理語言主要用于人工智能領域的表處理語言L

43、ISPLISP語言。語言。 廣義表是廣義表是n0個元素個元素a1，a2，an的有限序列，其中每一個的有限序列，其中每一個ai或者是原子，或者是一個子表。廣義表通常記為或者是原子，或者是一個子表。廣義表通常記為LS=(a1,a2,an)，其中其中LS為廣義表的名字，為廣義表的名字，n為廣義表的長度，為廣義表的長度， 每一個每一個ai為廣義表為廣義表的元素。但在習慣中，一般用大寫字母表示廣義表，小寫字母的元素。但在習慣中，一般用大寫字母表示廣義表，小寫字母表示原子。表示原子。 若若n=0n=0時為空表。記作：時為空表。記作：L=( )L=( )。 2021-12-2343 當廣義表當廣義表L L非

44、空非空( (n n0)0)時，第一個數(shù)據(jù)元素時，第一個數(shù)據(jù)元素a a0 0被稱為廣義表的表被稱為廣義表的表頭頭( (head)head)，其余數(shù)據(jù)元素組成的表其余數(shù)據(jù)元素組成的表( (a a1 1，a an-1n-1) ) 被稱為廣義表被稱為廣義表L L的的表尾表尾( (tail)tail)，分別記為分別記為head(A)= ahead(A)= a0 0，tail=(atail=(a1 1，a an-1n-1) )。 因此：一個廣義表是由表頭和表尾構成的。因此：一個廣義表是由表頭和表尾構成的。 1）A=( ) A=( ) A為空表，長度為為空表，長度為0。 2 2）B=(e) B=(e) B

45、B是一個只含有原子是一個只含有原子e e的表，其長度為的表，其長度為l l； 。 3 3）C=(aC=(a，(b(b，c c，d) d) C是長度為是長度為2的廣義表，第一項為原子，第二項為子表。的廣義表，第一項為原子，第二項為子表。 4 4）D= (AD= (A，B B，C)=()C)=()，(e)(e)，(a(a，(b(b，c c，d)d) 5 5）E=(E=( a a，( (a a，b b) )，( (， ) ) ) ) E E 中只含有一個元素，該元素是一個表，中只含有一個元素，該元素是一個表，E E的長度為的長度為l l。 6 6）F=(aF=(a，F(xiàn))=(aF)=(a，(a(a，(

46、a(a，.).) F F是長度為是長度為2的廣義表，第一項為原子，第二項為它本身。的廣義表，第一項為原子，第二項為它本身。 2021-12-23443廣義表的表示方法（用廣義表的表示方法（用次序關系和層次關系表示）次序關系和層次關系表示）（1）用）用L=(a1，a2，an)形式，其中每一個形式，其中每一個ai為原子或廣義表為原子或廣義表 例如：例如：A=(b,c) B=(a,A) E=(a,E)都是廣義表。都是廣義表。 （2）將廣義表中所有子表寫成原子形式，并利用圓括號嵌套）將廣義表中所有子表寫成原子形式，并利用圓括號嵌套例如，廣義表例如，廣義表A、B、C可以描述為：可以描述為： A(b,c)

47、 B(a,A(b,c) E(a,E(a,E（）) （3）將廣義表用樹和圖來描述將廣義表用樹和圖來描述 （層次關系）層次關系） 上面提到的廣義表上面提到的廣義表A、B、C的描述見圖的描述見圖5-8。 （次序關系）（次序關系）2021-12-2345 廣義表中數(shù)據(jù)元素的最大層次為表的深度。數(shù)據(jù)元素的層次廣義表中數(shù)據(jù)元素的最大層次為表的深度。數(shù)據(jù)元素的層次就是包括該元素韻括號對就是包括該元素韻括號對 的數(shù)目。例如廣義表的數(shù)目。例如廣義表G=(a，b，(c，(d)中，數(shù)據(jù)元素中，數(shù)據(jù)元素a，b在第一層，數(shù)據(jù)元素在第一層，數(shù)據(jù)元素c在第二層，數(shù)據(jù)元在第二層，數(shù)據(jù)元素素d在第三層，廣義表在第三層，廣義表G

48、的深度為的深度為3。 （次序關系）（次序關系）eabcdabcdeabbcaaEDABCCBA圖圖 5-8 廣義表的圖形表示廣義表的圖形表示 從圖從圖5-8可以看出：廣義表的圖形表示像倒著畫的一棵樹，可以看出：廣義表的圖形表示像倒著畫的一棵樹，樹根結點代表整個廣義表，各層樹枝結點代表相應的子表，樹葉樹根結點代表整個廣義表，各層樹枝結點代表相應的子表，樹葉結點代表單元素或空表（如結點代表單元素或空表（如A表）。表）。 2021-12-2346 一個廣義表的深度是指該廣義表一個廣義表的深度是指該廣義表展開后所含展開后所含的的。例如，例如，A=(b,c)的深度為的深度為1，B=(A,d)的深度為的深

49、度為2，C=(f,B,h)的深度為的深度為3;廣義表兼有線性結構和層次結構的特性，歸納如下：廣義表兼有線性結構和層次結構的特性，歸納如下：(1) (1) 廣義表中的數(shù)據(jù)元素有固定的相對次序；廣義表中的數(shù)據(jù)元素有固定的相對次序；(2) (2) 廣義表的長度定義為最外層括弧中包含的數(shù)據(jù)元素個數(shù)；廣義表的長度定義為最外層括弧中包含的數(shù)據(jù)元素個數(shù)；(3) (3) 廣義表的深度定義為廣義表書寫形式中括弧的最大重數(shù)，因此廣義表的深度定義為廣義表書寫形式中括弧的最大重數(shù)，因此空表的深度為空表的深度為1 1，因為一個單元素不是廣義表，所以從定義上講沒有，因為一個單元素不是廣義表，所以從定義上講沒有深度可言，但

50、可以認為它的深度為深度可言，但可以認為它的深度為0 0；(4) (4) 廣義表可被其它廣義表所共享。例如上述例子中廣義表廣義表可被其它廣義表所共享。例如上述例子中廣義表B B同時也同時也是廣義表是廣義表 D D 中的一個子表；中的一個子表； (5) 廣義表可以是一個自遞歸的表。例如上述例子中的廣義表廣義表可以是一個自遞歸的表。例如上述例子中的廣義表 F，自遞歸的廣義表的長度是個有限值，而深度為無限值。自遞歸的廣義表的長度是個有限值，而深度為無限值。 2021-12-2347 5廣義表的分類廣義表的分類（1）線性表：元素全部是原子的廣義表。）線性表：元素全部是原子的廣義表。（2）純表：與樹對應的

51、廣義表，見圖）純表：與樹對應的廣義表，見圖5-8的的(c) 、(d)、 (e) 。（3）再入表：與圖對應的廣義表再入表：與圖對應的廣義表(允許結點共享允許結點共享)，（4）遞歸表：允許有遞歸關系的廣義表，例如遞歸表：允許有遞歸關系的廣義表，例如E=(a,E)。 這四種表的關系滿足：遞歸表這四種表的關系滿足：遞歸表 再入表再入表 純表純表 線性表線性表 BACbacAbcBaAbc再入表再入表2021-12-2348 5.3.2 廣義表的存儲結構由于廣義表的元素類型不一定相同，由于廣義表的元素類型不一定相同，表中的數(shù)據(jù)元素可以是單元素表中的數(shù)據(jù)元素可以是單元素（原子項），也可以是廣義表，（原子項

52、），也可以是廣義表，因此，難以用順序結構存儲表中元因此，難以用順序結構存儲表中元素，通常采用鏈接存儲方法來存儲廣義表中元素，并稱之為廣義鏈素，通常采用鏈接存儲方法來存儲廣義表中元素，并稱之為廣義鏈表。表。需要兩種結構的結點：需要兩種結構的結點：(1) (1) 表結點：用以表示廣義表。由三個域組成：標志域表結點：用以表示廣義表。由三個域組成：標志域tagtag、指向指向表頭的指針域表頭的指針域sublistsublist和指向下一個結點的指針域和指向下一個結點的指針域linklink。如圖如圖5-9(5-9(a)a)所示。所示。 (2) 原子結點：用以表示原子項。由三個域組成：標志域原子結點：用

53、以表示原子項。由三個域組成：標志域tag、值域值域data和指向下一個元素結點的指針域和指向下一個元素結點的指針域link。如圖如圖5-9(b)所示。所示。 tag=1 sublist link tag=0 data link（a）表結點（b）元素結點2021-12-2349 每個數(shù)據(jù)元素都可用表結點或原子結點表示。它們的主要區(qū)別每個數(shù)據(jù)元素都可用表結點或原子結點表示。它們的主要區(qū)別在于從不同的角度反映廣義表的構成。在于從不同的角度反映廣義表的構成。 例如，廣義表例如，廣義表C的鏈表存儲結構如圖的鏈表存儲結構如圖5-10所示。所示。 1 0 a1 0 b0 c0 d C圖圖 5-10 廣義表廣

54、義表(a,(b,c,d)的鏈表存儲結構圖的鏈表存儲結構圖 二叉樹二叉樹2021-12-2350廣義表的鏈式結構描述如下：廣義表的鏈式結構描述如下：typedef char ElemType;typedef struct glnode int tag; union ElemType data; struct glnode *sublist; val; struct glnode *link; GListNode; 可將一個廣義表看成一棵樹，為了方便存儲，通常將其轉換可將一個廣義表看成一棵樹，為了方便存儲，通常將其轉換成一棵二叉樹成一棵二叉樹 。廣義表廣義表C轉換成二叉樹過程轉換成二叉樹過程 如圖

55、如圖5-11所示：所示： 2021-12-2351acbd(a)廣 義 表 的 圖 形 表 示abddCC(b)轉 換 后 的 樹廣義表廣義表C C圖圖5-11 廣義表的轉換過程廣義表的轉換過程 2021-12-2352 廣義表的基本操作主要有：廣義表的基本操作主要有： 求廣義表的長度和深度、向廣求廣義表的長度和深度、向廣義表插入元素和從廣義表中查找或刪除元素、建立廣義表的存儲義表插入元素和從廣義表中查找或刪除元素、建立廣義表的存儲結構、輸出廣義表和復制廣義表等。結構、輸出廣義表和復制廣義表等。 由于廣義表是一種遞歸的數(shù)據(jù)結構，所以對廣義表的運算一由于廣義表是一種遞歸的數(shù)據(jù)結構，所以對廣義表的

56、運算一般采用遞歸的算法。般采用遞歸的算法。 在廣義表中，同一層次的每個結點是通過在廣義表中，同一層次的每個結點是通過1ink域鏈接起來的，域鏈接起來的，可把它看做是由可把它看做是由1ink域鏈接起來的單鏈表。域鏈接起來的單鏈表。 求廣義表的長度就變成求單鏈表的長度，求廣義表的長度就變成求單鏈表的長度，則它的深度可以遞則它的深度可以遞歸求出。歸求出。2021-12-2353求廣義表長度的遞歸算法如下：求廣義表長度的遞歸算法如下： int GListLength(GListNode *h) /h為一個廣義表頭結點的指針為一個廣義表頭結點的指針 int n=0; h=h-val.sublist; /

57、h指向廣義表的第一個元素指向廣義表的第一個元素 while(h!=NULL) n+; h=h-link; return n;廣義表深度的遞歸定義是：它等于所有子表中表的最大深度加廣義表深度的遞歸定義是：它等于所有子表中表的最大深度加1 1。若一個表為空或僅由單元素所組成，則深度為若一個表為空或僅由單元素所組成，則深度為l l。求廣義表深度求廣義表深度的遞歸函數(shù)的遞歸函數(shù)GListDepth()GListDepth()如下：如下： 2021-12-2354 1 h為空表為空表 GListDepth(h)= maxGListDepth(sh)|sh為為h的子表的子表+1 其它情況其它情況 int

58、GListDepth(GListNode *h) /h為廣義表頭結點的為廣義表頭結點的sublist域值或為不帶頭結點的廣義表域值或為不帶頭結點的廣義表 int max=0,dep; /max中存放子表的最大深度中存放子表的最大深度 while(h!=NULL) /遍歷表中的每一個結點遍歷表中的每一個結點 if(h-tag=1) /只需要求出子表深度即可，單元素深度為只需要求出子表深度即可，單元素深度為0 dep=GListDepth(h-val.sublist); /遞歸調(diào)用求出子表的深度遞歸調(diào)用求出子表的深度 if(depmax) /讓讓max始終為同一層所求過的子表中深度的最大值始終為同

59、一層所求過的子表中深度的最大值 max=dep; h=h-link; /使使h指向同一層的下一個結點指向同一層的下一個結點 return max+l; /返回表的深度返回表的深度 2021-12-2355假設廣義表以單鏈表的形式存儲，廣義表的元素類型假設廣義表以單鏈表的形式存儲，廣義表的元素類型elemtype 為為字符型字符型char，廣義表由鍵盤輸入，假定全部為字母，輸入格式為：廣義表由鍵盤輸入，假定全部為字母，輸入格式為：元素之間用逗號分隔，表元素的起止符號分別為左、右圓括號，元素之間用逗號分隔，表元素的起止符號分別為左、右圓括號，空表在其圓括號內(nèi)使用一個空表在其圓括號內(nèi)使用一個“#”字

60、符表示，最后使用一個分號字符表示，最后使用一個分號作為整個廣義表的結束。作為整個廣義表的結束。 例如例如“( (a a，(b(b，c c，d)d)”，就是一個符合上述規(guī)定的廣義表格就是一個符合上述規(guī)定的廣義表格式（注意：不包括引號）。式（注意：不包括引號）。建立廣義表存儲結構的算法同樣是一個遞歸算法。建立廣義表存儲結構的算法同樣是一個遞歸算法。 2021-12-2356 建立廣義表的算法如下：建立廣義表的算法如下：GListNode *GListCreat(char *s) GListNode *h; char ch; ch=*s; /取一個掃描字符取一個掃描字符 s+; /串指針后移一位串指