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

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

3、占存儲(chǔ)單元數(shù)數(shù)k確定，則確定，則ai的存儲(chǔ)地址的存儲(chǔ)地址LOC(ai)就可求出：就可求出： LOC(ai)=LOC(a0)+i*k (0in) 2二維數(shù)組二維數(shù)組 二維數(shù)組，又稱(chēng)矩陣二維數(shù)組，又稱(chēng)矩陣(matrix)。二維數(shù)組中的每一個(gè)元素又是二維數(shù)組中的每一個(gè)元素又是一個(gè)定長(zhǎng)的線性表（一維數(shù)組），都要受到兩個(gè)關(guān)系即行關(guān)系和一個(gè)定長(zhǎng)的線性表（一維數(shù)組），都要受到兩個(gè)關(guān)系即行關(guān)系和列關(guān)系的約束，也就是每個(gè)元素都同屬于兩個(gè)線性表。列關(guān)系的約束，也就是每個(gè)元素都同屬于兩個(gè)線性表。例如，設(shè)例如，設(shè)A是一個(gè)有是一個(gè)有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個(gè)行向量組成的向量，也可以看由個(gè)行向量組成的向量，也可以看由n n個(gè)列向量組成個(gè)列向量組成的向量。的向量。 數(shù)組中的每個(gè)元素由元素值數(shù)組中的每個(gè)元素由元素值a aijij及一組下標(biāo)（及一組下標(biāo)（i i，j j）來(lái)確定。來(lái)確定。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) 可以認(rèn)為可以認(rè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ù)組同樣滿(mǎn)足數(shù)組的定義。一個(gè)二維數(shù)組可以看顯然，二維數(shù)組同樣滿(mǎn)足數(shù)組的定義。一個(gè)二維數(shù)組可以看作是每個(gè)數(shù)據(jù)元素都是相同類(lèi)型的一維數(shù)組。以此類(lèi)推，任何多作是每個(gè)數(shù)據(jù)元素都是相同類(lèi)型的一維數(shù)組。以此類(lèi)推，任何多維數(shù)組都可以看作一個(gè)線性表，這時(shí)線性表中的每個(gè)數(shù)據(jù)元素也維數(shù)組都可以看作一個(gè)線性表，這時(shí)線性表中的每個(gè)數(shù)據(jù)元素也是一個(gè)線性表。多維數(shù)組是特殊的線性表，是線性

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

7、存儲(chǔ)結(jié)構(gòu)。可隨機(jī)存取數(shù)組中的任意數(shù)據(jù)元素。據(jù)元素。 2021-12-238 數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。因此，除了結(jié)數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。因此，除了結(jié)構(gòu)的初始化和銷(xiāo)毀之外，構(gòu)的初始化和銷(xiāo)毀之外，數(shù)組的基本操作一般不會(huì)含有元素的插入數(shù)組的基本操作一般不會(huì)含有元素的插入或刪除等操作或刪除等操作, ,數(shù)組只有數(shù)組只有訪問(wèn)數(shù)組元素訪問(wèn)數(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個(gè)下標(biāo)值，且這些下個(gè)下標(biāo)值，且這些下標(biāo)均不超過(guò)對(duì)應(yīng)維的上界。其運(yùn)算結(jié)果是返回由下標(biāo)指定的標(biāo)均不超過(guò)對(duì)應(yīng)維的上界。其運(yùn)算結(jié)果是返回由下標(biāo)指定的A A中的中的對(duì)應(yīng)元素的值。對(duì)應(yīng)元素的值。(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個(gè)個(gè)下標(biāo)值，且這些下標(biāo)均未越界。其運(yùn)算結(jié)果是將下標(biāo)值，且這些下標(biāo)均未越界。其運(yùn)算結(jié)果是將e e的值賦給由下標(biāo)的值賦給由下標(biāo)指定的指定的A A中的對(duì)應(yīng)元素。中的對(duì)應(yīng)元素。2021-12-239(3) (3) dispdisp(A)(A)：輸出數(shù)組輸出數(shù)組A A的所有元素。的所有元素。在大多數(shù)程序設(shè)計(jì)語(yǔ)言中，取數(shù)組元素值操作在大多數(shù)程序設(shè)計(jì)語(yǔ)言中，取數(shù)組元素值操作value(Avalue(A，indexindexl l，indexindex2 2，indexindexd d) ) 通常直接寫(xiě)作通常直接寫(xiě)作AAindexindexl l index index2 2 indexindex

10、d d ，而對(duì)數(shù)組元素的賦值操作而對(duì)數(shù)組元素的賦值操作assign(Aassign(A，e e，indexindexl l，indexindex2 2，indexindexd d) )寫(xiě)作寫(xiě)作e= Ae= Aindexindexl l index index2 2 indexindexd d ，或者類(lèi)似的形式。或者類(lèi)似的形式。 2021-12-2310 由于數(shù)組一般不作刪除或插入運(yùn)算，所以一旦數(shù)組被定義后，由于數(shù)組一般不作刪除或插入運(yùn)算，所以一旦數(shù)組被定義后，數(shù)組中的元素個(gè)數(shù)和元素之間的關(guān)系就不再變動(dòng)。通常采用順序存數(shù)組中的元素個(gè)數(shù)和元素之間的關(guān)系就不再變動(dòng)。通常采用順序存儲(chǔ)結(jié)構(gòu)表示數(shù)組。儲(chǔ)結(jié)

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

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

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

14、1A= a10 a11 a20 a21a00a01a10a11a20a21(a)二維數(shù)組a00a10a20a01a11a21(c)列序?yàn)橹餍?b)行序?yàn)橹餍驅(qū)σ粋€(gè)以行序?yàn)橹餍虻挠?jì)算機(jī)系統(tǒng)，當(dāng)二維數(shù)組第一個(gè)數(shù)據(jù)元素對(duì)一個(gè)以行序?yàn)橹餍虻挠?jì)算機(jī)系統(tǒng)，當(dāng)二維數(shù)組第一個(gè)數(shù)據(jù)元素a a0,00,0的存儲(chǔ)地址的存儲(chǔ)地址LOC(aLOC(a0,00,0) )以及每個(gè)數(shù)據(jù)元素所占用的存儲(chǔ)單元以及每個(gè)數(shù)據(jù)元素所占用的存儲(chǔ)單元k k確定確定后，該二維數(shù)組中任一數(shù)據(jù)元素后，該二維數(shù)組中任一數(shù)據(jù)元素a ai i,j,j的存儲(chǔ)地址可由下式確定的存儲(chǔ)地址可由下式確定: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ù)組的兩種存儲(chǔ)結(jié)構(gòu)二維數(shù)組的兩種存儲(chǔ)結(jié)構(gòu) a00 a01A= a10 a11 a20 a21a00a01a10a11a20a21(a)二維數(shù)組a00a10a20a01a11a21(c)列序?yàn)橹餍?b)行序?yàn)橹餍驅(qū)σ粋€(gè)以行序?yàn)橹餍虻挠?jì)算機(jī)系統(tǒng)，當(dāng)二維數(shù)組第一個(gè)數(shù)據(jù)元素對(duì)一個(gè)以行序?yàn)橹餍虻挠?jì)算機(jī)系統(tǒng)，當(dāng)二維數(shù)組第一個(gè)數(shù)據(jù)元素a a0,00,0的存儲(chǔ)地址的存儲(chǔ)地址LOC(aLOC(a0,00,0) )以及每個(gè)數(shù)據(jù)元素所占用的存儲(chǔ)單元以及每個(gè)數(shù)據(jù)元素所占用

16、的存儲(chǔ)單元k k確定確定后，該二維數(shù)組中任一數(shù)據(jù)元素后，該二維數(shù)組中任一數(shù)據(jù)元素a ai i,j,j的存儲(chǔ)地址可由下式確定的存儲(chǔ)地址可由下式確定: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】對(duì)于給定的二維數(shù)組】對(duì)于給定的二維數(shù)組float a34float a34，計(jì)算：計(jì)算： (1) (1) 數(shù)組數(shù)組a a中的數(shù)組元素?cái)?shù)目；中的數(shù)組元素?cái)?shù)目； (2) (2) 若數(shù)組若數(shù)組a a的起始地址為的起始地址為10001000，且每個(gè)數(shù)組元

17、素長(zhǎng)度為，且每個(gè)數(shù)組元素長(zhǎng)度為3232位位( (即即4 4個(gè)字節(jié)個(gè)字節(jié)) )，數(shù)組元素，數(shù)組元素a23a23的內(nèi)存地址。的內(nèi)存地址。【解】【解】(1)(1)由于由于C C語(yǔ)言中數(shù)組的行、列下標(biāo)值的下界均為語(yǔ)言中數(shù)組的行、列下標(biāo)值的下界均為0 0，該數(shù)組，該數(shù)組行上界為行上界為3-1=23-1=2，列上界為，列上界為4-1=34-1=3，所以該數(shù)組的元素?cái)?shù)目共有，所以該數(shù)組的元素?cái)?shù)目共有3 3* *4=124=12個(gè)。個(gè)。 (2) (2)由于由于C C語(yǔ)言采用行序?yàn)橹餍虻拇鎯?chǔ)方式，有：語(yǔ)言采用行序?yàn)橹餍虻拇鎯?chǔ)方式，有： 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名學(xué)生，每人考名學(xué)生，每人考n n門(mén)功課，試寫(xiě)出求任一學(xué)生總分?jǐn)?shù)門(mén)功課，試寫(xiě)出求任一學(xué)生總分?jǐn)?shù)和任一課程總分?jǐn)?shù)的數(shù)據(jù)結(jié)構(gòu)和算法。和任一課程總分?jǐn)?shù)的數(shù)據(jù)結(jié)構(gòu)和算法。【解】把學(xué)生的考試成績(jī)存放在【解】把學(xué)生的考試成績(jī)存放在m m行行n n列的二維數(shù)組中，則第列的二維數(shù)組中，則第i(0i(0im)im)行第行第j(0j(0jn)jn)列中存放了第列中存放了第i i個(gè)學(xué)生的第個(gè)學(xué)生的第j j門(mén)課程考試成績(jī)

19、。門(mén)課程考試成績(jī)。即數(shù)據(jù)結(jié)構(gòu)為：即數(shù)據(jù)結(jié)構(gòu)為：#define M 10 /假設(shè)假設(shè)為為1010人人#define N 3 /假設(shè)假設(shè)為為3 3int scoreMN; /學(xué)生成績(jī)二維數(shù)組學(xué)生成績(jī)二維數(shù)組求第求第i i名學(xué)生總分?jǐn)?shù)的算法為：名學(xué)生總分?jǐn)?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門(mén)課程總分?jǐn)?shù)的算法為：門(mén)課程總分?jǐn)?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ì)算程序設(shè)計(jì)中經(jīng)常用到的數(shù)學(xué)模型，它是矩陣是數(shù)值計(jì)算程序設(shè)計(jì)中經(jīng)常用到的數(shù)學(xué)模型，它是由由 m m 行和行和 n n 列的數(shù)值構(gòu)成（當(dāng)列的數(shù)值構(gòu)成（當(dāng)m=n m=n 時(shí)稱(chēng)為方陣）。時(shí)稱(chēng)為方陣）。在高級(jí)在高級(jí)程序設(shè)計(jì)語(yǔ)言中程序設(shè)計(jì)語(yǔ)言中，通常用，通常用表示矩陣。然而表示矩陣。然而在數(shù)值分在數(shù)值分析過(guò)程中經(jīng)常遇到一些比較特殊的矩陣，它們的階數(shù)很高，析過(guò)程中經(jīng)常遇到一些比較特殊的矩陣，它們的階數(shù)很高，矩陣中元素?cái)?shù)量很大，而且有很多元素的值相同或零值元素

21、，矩陣中元素?cái)?shù)量很大，而且有很多元素的值相同或零值元素，如如對(duì)稱(chēng)矩陣對(duì)稱(chēng)矩陣、三角矩陣三角矩陣、帶狀矩陣帶狀矩陣和和稀疏矩陣稀疏矩陣等。等。為了節(jié)省為了節(jié)省存儲(chǔ)空間并且加快處理速度，需要對(duì)存儲(chǔ)空間并且加快處理速度，需要對(duì)這類(lèi)矩陣這類(lèi)矩陣進(jìn)行壓縮存儲(chǔ)，進(jìn)行壓縮存儲(chǔ)，壓縮存儲(chǔ)的原則壓縮存儲(chǔ)的原則是：是：。 2021-12-2318。 對(duì)稱(chēng)矩陣是一個(gè)對(duì)稱(chēng)矩陣是一個(gè)n n階階方陣。若一個(gè)方陣。若一個(gè)n n階矩陣階矩陣A A中的元素滿(mǎn)足中的元素滿(mǎn)足: : a ai i,j,j= =a aj j,I ,I (0i(0i，jn-1)jn-1)，則稱(chēng)則稱(chēng)A A為為n n階對(duì)稱(chēng)矩陣。階對(duì)稱(chēng)矩陣。 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 對(duì)稱(chēng)矩陣對(duì)稱(chēng)矩陣2021-12-2319 在這個(gè)下三角矩陣中，第在這個(gè)下三角矩陣中，第i i行恰有行恰有i+1i+1個(gè)元素，元素總數(shù)為：個(gè)元素，元素總數(shù)為： ( (i+1)=n(n+1)/2i+1)=n(n+1)/2 由于對(duì)稱(chēng)矩陣中的元素關(guān)于主對(duì)角線對(duì)稱(chēng)，因此由于對(duì)稱(chēng)矩陣中的元素關(guān)于主對(duì)角線對(duì)稱(chēng)，因此可以為每一可以為每一對(duì)對(duì)稱(chēng)的矩陣元素分配對(duì)對(duì)稱(chēng)的矩陣元素分配 1 1 個(gè)存儲(chǔ)空間，個(gè)存儲(chǔ)空間

23、，n n階矩陣中的階矩陣中的n nn n個(gè)元素個(gè)元素就可以被壓縮到就可以被壓縮到 n(n+1)/2n(n+1)/2 個(gè)元素的存儲(chǔ)空間中去。個(gè)元素的存儲(chǔ)空間中去。 稱(chēng)一維數(shù)組稱(chēng)一維數(shù)組sa0.n(n+1)/2 為為n 階對(duì)稱(chēng)矩陣階對(duì)稱(chēng)矩陣A的壓縮存儲(chǔ)。的壓縮存儲(chǔ)。其存儲(chǔ)對(duì)應(yīng)關(guān)系如上圖其存儲(chǔ)對(duì)應(yīng)關(guān)系如上圖 : : 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 對(duì)稱(chēng)矩陣的壓縮存儲(chǔ)對(duì)稱(chēng)矩陣的壓縮存儲(chǔ) 2021-12-2320其中，其中，sbn(n+1)/2中存放常數(shù)中存放

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

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

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

27、情況以及非零元對(duì)應(yīng)的三元組表（以行序?yàn)橹餍颍┤鐖D所示。的三元組表（以行序?yàn)橹餍颍┤鐖D所示。 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序號(hào) 行 列 值 (a) 稀疏矩陣稀疏矩陣 (b) 三元組表示三元組表示 三元組表中的第一行分別表示稀疏矩陣三元組表中的第一行分別表示稀疏矩陣A A的行數(shù)、列數(shù)和非零的行數(shù)、列數(shù)和非零元的個(gè)數(shù)。元的個(gè)數(shù)。顯然，非零元素

28、的三元組是按行號(hào)遞增的順序、相同顯然，非零元素的三元組是按行號(hào)遞增的順序、相同行號(hào)的三元組按列號(hào)遞增的順序排列的。行號(hào)的三元組按列號(hào)遞增的順序排列的。2021-12-23251 1三元組順序表三元組順序表 假設(shè)以行序?yàn)橹餍颍乙砸痪S數(shù)組作為三元組表的存儲(chǔ)結(jié)構(gòu)，假設(shè)以行序?yàn)橹餍颍乙砸痪S數(shù)組作為三元組表的存儲(chǔ)結(jié)構(gòu)，可以得到稀疏矩陣的一種壓縮存儲(chǔ)方法，稱(chēng)為三元組順序表。三可以得到稀疏矩陣的一種壓縮存儲(chǔ)方法，稱(chēng)為三元組順序表。三元組順序表的數(shù)據(jù)結(jié)構(gòu)定義如下：元組順序表的數(shù)據(jù)結(jié)構(gòu)定義如下：#define NUM 100 /矩陣中非零元素最大個(gè)數(shù)矩陣中非零元素最大個(gè)數(shù)typedef struct /三元

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

30、其轉(zhuǎn)置矩陣是一個(gè)n nm m的矩陣，設(shè)為的矩陣，設(shè)為B Bn nm m 且滿(mǎn)足且滿(mǎn)足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三元組表示的稀疏矩陣的轉(zhuǎn)置常用的算法有以下兩種：三元組表示的稀疏矩陣的轉(zhuǎn)置常用的算法有以下兩種：1 1）矩陣的列序轉(zhuǎn)置）矩陣的列序轉(zhuǎn)置（傳統(tǒng)的轉(zhuǎn)置算法）（傳統(tǒng)的轉(zhuǎn)置算法）矩陣矩陣A是按行序?yàn)橹餍虼鎯?chǔ)的，若按列序?yàn)橹餍蜻M(jìn)行轉(zhuǎn)置就可以是

31、按行序?yàn)橹餍虼鎯?chǔ)的，若按列序?yàn)橹餍蜻M(jìn)行轉(zhuǎn)置就可以得到得到A陣的轉(zhuǎn)置矩陣陣的轉(zhuǎn)置矩陣B。假設(shè)矩陣假設(shè)矩陣A的三元組存入一維數(shù)組中，只的三元組存入一維數(shù)組中，只要在數(shù)組中按三元組的列域要在數(shù)組中按三元組的列域cols的值開(kāi)始掃描，從第的值開(kāi)始掃描，從第0列至第列至第n-1列列，依序?qū)⑷M列域與行域之值對(duì)換，并順次存人數(shù)組，依序?qū)⑷M列域與行域之值對(duì)換，并順次存人數(shù)組mb中。算中。算法如下：法如下：int transpose(table ma,table mb) int i,j,k=0,n,t; if(ma.nums=0)return(0)； /矩陣中無(wú)非零元素矩陣中無(wú)非零元素 m=ma.row

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

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

34、維數(shù)組表示矩陣，則相應(yīng)的矩陣轉(zhuǎn)置算法的循環(huán)為：相應(yīng)的矩陣轉(zhuǎ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； 此時(shí)，時(shí)間復(fù)雜度為此時(shí)，時(shí)間復(fù)雜度為O(mn) 。2021-12-23292 2）快速轉(zhuǎn)置算法：）快速轉(zhuǎn)置算法： 三元組順序表雖然節(jié)省了存儲(chǔ)空間，但時(shí)間復(fù)雜度比三元組順序表雖然節(jié)省了存儲(chǔ)空間，但時(shí)間復(fù)雜度比一般矩陣轉(zhuǎn)置的算法還要復(fù)雜，同時(shí)還有可能增加算是法一般矩陣轉(zhuǎn)置的算法還要復(fù)雜，同時(shí)還有可能增加算是法的難度。因此，此算法僅適用于的難度。因此，此算法僅適用于

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

36、每一列中非零元素的個(gè)數(shù)。中的每一列中非零元素的個(gè)數(shù)。因?yàn)榫仃囈驗(yàn)榫仃嘙 M中第一列的第一個(gè)非零元素在數(shù)組中第一列的第一個(gè)非零元素在數(shù)組T T中應(yīng)有的位置等于中應(yīng)有的位置等于前一列第一個(gè)非零元素的位置加上前列非零元素的個(gè)數(shù)。前一列第一個(gè)非零元素的位置加上前列非零元素的個(gè)數(shù)。2021-12-2330為此，需要設(shè)置兩個(gè)一維數(shù)組為此，需要設(shè)置兩個(gè)一維數(shù)組num0.nnum0.n和和rposrpos0.n0.n：num0.nnum0.n：統(tǒng)計(jì)統(tǒng)計(jì)M M中每列非零元素的個(gè)數(shù)。中每列非零元素的個(gè)數(shù)。rposrpos0.n0.n：M M中的每列第一個(gè)非零元素在中的每列第一個(gè)非零元素在T T中的位置。中的位置。

37、算法通過(guò)算法通過(guò)rposrpos數(shù)組建立位置對(duì)應(yīng)關(guān)系：數(shù)組建立位置對(duì)應(yīng)關(guān)系： 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) 所示的稀疏矩陣的三元組表對(duì)應(yīng)的所示的稀疏矩陣的三元組表對(duì)應(yīng)的num0.n-1num0.n-1和和rposrpos0.n-10.n-1如圖如圖5-55-5所示。所示。 （算法見(jiàn)教科書(shū)）（算法見(jiàn)教科書(shū)）圖圖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快速轉(zhuǎn)置算法如下：快速轉(zhuǎn)置算法如下： 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帶行表的三元組帶行表的三元組) ) 有時(shí)為了方便某些矩陣運(yùn)算，在按行優(yōu)先存儲(chǔ)的三元組有時(shí)為了方便某些矩陣運(yùn)算，在按行優(yōu)先存儲(chǔ)的三元組中，加入一個(gè)行表來(lái)記錄稀疏矩陣中每行的非零元素在三元中，加入一個(gè)行表來(lái)記錄稀疏矩陣中每行的非零元素在三元組

40、表中的起始位置。當(dāng)將行表作為三元組表的一個(gè)新增屬性組表中的起始位置。當(dāng)將行表作為三元組表的一個(gè)新增屬性加以描述時(shí)，就得到了稀疏矩陣的另一種順序存儲(chǔ)結(jié)構(gòu)：帶加以描述時(shí)，就得到了稀疏矩陣的另一種順序存儲(chǔ)結(jié)構(gòu)：帶行表的三元組表。行表的三元組表。稱(chēng)這種稱(chēng)這種“帶行鏈接信息帶行鏈接信息”的三元組表為行邏的三元組表為行邏輯鏈接的順序表。輯鏈接的順序表。其類(lèi)型描述如下：其類(lèi)型描述如下： # #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 下面討論兩個(gè)稀疏矩陣相乘的例子，容易看出這種表示下面討論兩個(gè)稀疏矩陣相乘的例子，容易看出這種表示方法的優(yōu)越性：方法的優(yōu)越性： 若設(shè)若設(shè) Q=M*N 其中，其中，M是是m1*n1矩陣，矩陣，N是是m2*n2矩陣。矩陣。 當(dāng)當(dāng)n1=m2時(shí)有：時(shí)有： 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 廣義表也是線性表的推廣，是一種多層次的線性結(jié)構(gòu)，廣義表也是線性表的推廣，是一種多層次的線性結(jié)構(gòu)，線性表線性表中的元素僅限于原子項(xiàng)，即不可以再分；中的元素僅限于原子項(xiàng)，即不可以再分； 而廣義表中的元素既可以是原子項(xiàng)，也可以是子表（另一個(gè)線而廣義表中的元素既可以是原子項(xiàng)，也可以是子表（另一個(gè)線性表）。性表）。主要用于人工智能領(lǐng)域的表處理語(yǔ)言主要用于人工智能領(lǐng)域的表處理語(yǔ)言L

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

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

45、B是一個(gè)只含有原子是一個(gè)只含有原子e e的表，其長(zhǎng)度為的表，其長(zhǎng)度為l l； 。 3 3）C=(aC=(a，(b(b，c c，d) d) C是長(zhǎng)度為是長(zhǎng)度為2的廣義表，第一項(xiàng)為原子，第二項(xiàng)為子表。的廣義表，第一項(xiàng)為原子，第二項(xiàng)為子表。 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 中只含有一個(gè)元素，該元素是一個(gè)表，中只含有一個(gè)元素，該元素是一個(gè)表，E E的長(zhǎng)度為的長(zhǎng)度為l l。 6 6）F=(aF=(a，F(xiàn))=(aF)=(a，(a(a，(

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

47、 B(a,A(b,c) E(a,E(a,E（）) （3）將廣義表用樹(shù)和圖來(lái)描述將廣義表用樹(shù)和圖來(lái)描述 （層次關(guān)系）層次關(guān)系） 上面提到的廣義表上面提到的廣義表A、B、C的描述見(jiàn)圖的描述見(jiàn)圖5-8。 （次序關(guān)系）（次序關(guān)系）2021-12-2345 廣義表中數(shù)據(jù)元素的最大層次為表的深度。數(shù)據(jù)元素的層次廣義表中數(shù)據(jù)元素的最大層次為表的深度。數(shù)據(jù)元素的層次就是包括該元素韻括號(hào)對(duì)就是包括該元素韻括號(hào)對(duì) 的數(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。 （次序關(guān)系）（次序關(guān)系）eabcdabcdeabbcaaEDABCCBA圖圖 5-8 廣義表的圖形表示廣義表的圖形表示 從圖從圖5-8可以看出：廣義表的圖形表示像倒著畫(huà)的一棵樹(shù)，可以看出：廣義表的圖形表示像倒著畫(huà)的一棵樹(shù)，樹(shù)根結(jié)點(diǎn)代表整個(gè)廣義表，各層樹(shù)枝結(jié)點(diǎn)代表相應(yīng)的子表，樹(shù)葉樹(shù)根結(jié)點(diǎn)代表整個(gè)廣義表，各層樹(shù)枝結(jié)點(diǎn)代表相應(yīng)的子表，樹(shù)葉結(jié)點(diǎn)代表單元素或空表（如結(jié)點(diǎn)代表單元素或空表（如A表）。表）。 2021-12-2346 一個(gè)廣義表的深度是指該廣義表一個(gè)廣義表的深度是指該廣義表展開(kāi)后所含展開(kāi)后所含的的。例如，例如，A=(b,c)的深度為的深度為1，B=(A,d)的深度為的深

49、度為2，C=(f,B,h)的深度為的深度為3;廣義表兼有線性結(jié)構(gòu)和層次結(jié)構(gòu)的特性，歸納如下：廣義表兼有線性結(jié)構(gòu)和層次結(jié)構(gòu)的特性，歸納如下：(1) (1) 廣義表中的數(shù)據(jù)元素有固定的相對(duì)次序；廣義表中的數(shù)據(jù)元素有固定的相對(duì)次序；(2) (2) 廣義表的長(zhǎng)度定義為最外層括弧中包含的數(shù)據(jù)元素個(gè)數(shù)；廣義表的長(zhǎng)度定義為最外層括弧中包含的數(shù)據(jù)元素個(gè)數(shù)；(3) (3) 廣義表的深度定義為廣義表書(shū)寫(xiě)形式中括弧的最大重?cái)?shù)，因此廣義表的深度定義為廣義表書(shū)寫(xiě)形式中括弧的最大重?cái)?shù)，因此空表的深度為空表的深度為1 1，因?yàn)橐粋€(gè)單元素不是廣義表，所以從定義上講沒(méi)有，因?yàn)橐粋€(gè)單元素不是廣義表，所以從定義上講沒(méi)有深度可言，但

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

51、廣義表，見(jiàn)圖）純表：與樹(shù)對(duì)應(yīng)的廣義表，見(jiàn)圖5-8的的(c) 、(d)、 (e) 。（3）再入表：與圖對(duì)應(yīng)的廣義表再入表：與圖對(duì)應(yīng)的廣義表(允許結(jié)點(diǎn)共享允許結(jié)點(diǎn)共享)，（4）遞歸表：允許有遞歸關(guān)系的廣義表，例如遞歸表：允許有遞歸關(guān)系的廣義表，例如E=(a,E)。 這四種表的關(guān)系滿(mǎn)足：遞歸表這四種表的關(guān)系滿(mǎn)足：遞歸表 再入表再入表 純表純表 線性表線性表 BACbacAbcBaAbc再入表再入表2021-12-2348 5.3.2 廣義表的存儲(chǔ)結(jié)構(gòu)由于廣義表的元素類(lèi)型不一定相同，由于廣義表的元素類(lèi)型不一定相同，表中的數(shù)據(jù)元素可以是單元素表中的數(shù)據(jù)元素可以是單元素（原子項(xiàng)），也可以是廣義表，（原子項(xiàng)

52、），也可以是廣義表，因此，難以用順序結(jié)構(gòu)存儲(chǔ)表中元因此，難以用順序結(jié)構(gòu)存儲(chǔ)表中元素，通常采用鏈接存儲(chǔ)方法來(lái)存儲(chǔ)廣義表中元素，并稱(chēng)之為廣義鏈素，通常采用鏈接存儲(chǔ)方法來(lái)存儲(chǔ)廣義表中元素，并稱(chēng)之為廣義鏈表。表。需要兩種結(jié)構(gòu)的結(jié)點(diǎn)：需要兩種結(jié)構(gòu)的結(jié)點(diǎn)：(1) (1) 表結(jié)點(diǎn)：用以表示廣義表。由三個(gè)域組成：標(biāo)志域表結(jié)點(diǎn)：用以表示廣義表。由三個(gè)域組成：標(biāo)志域tagtag、指向指向表頭的指針域表頭的指針域sublistsublist和指向下一個(gè)結(jié)點(diǎn)的指針域和指向下一個(gè)結(jié)點(diǎn)的指針域linklink。如圖如圖5-9(5-9(a)a)所示。所示。 (2) 原子結(jié)點(diǎn)：用以表示原子項(xiàng)。由三個(gè)域組成：標(biāo)志域原子結(jié)點(diǎn)：用

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

54、義表(a,(b,c,d)的鏈表存儲(chǔ)結(jié)構(gòu)圖的鏈表存儲(chǔ)結(jié)構(gòu)圖 二叉樹(shù)二叉樹(shù)2021-12-2350廣義表的鏈?zhǔn)浇Y(jié)構(gòu)描述如下：廣義表的鏈?zhǔn)浇Y(jié)構(gòu)描述如下：typedef char ElemType;typedef struct glnode int tag; union ElemType data; struct glnode *sublist; val; struct glnode *link; GListNode; 可將一個(gè)廣義表看成一棵樹(shù)，為了方便存儲(chǔ)，通常將其轉(zhuǎn)換可將一個(gè)廣義表看成一棵樹(shù)，為了方便存儲(chǔ)，通常將其轉(zhuǎn)換成一棵二叉樹(shù)成一棵二叉樹(shù) 。廣義表廣義表C轉(zhuǎn)換成二叉樹(shù)過(guò)程轉(zhuǎn)換成二叉樹(shù)過(guò)程 如圖

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

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

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

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

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

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