數(shù)組和廣義表

1、關(guān)于數(shù)組與廣義表第一張，PPT共八十五頁，創(chuàng)作于2022年6月第5章 數(shù)組與廣義表 本章主要內(nèi)容一、數(shù)組的存儲結(jié)構(gòu)及其地址變換二、特殊矩陣的壓縮存儲及其地址變換三、稀疏矩陣的存儲結(jié)構(gòu)與算法四、廣義表的存儲結(jié)構(gòu)與算法第二張，PPT共八十五頁，創(chuàng)作于2022年6月5.1 數(shù)組 數(shù)組是線性表的直接推廣 。如果線性表的元素又是具有相同數(shù)據(jù)類型的線性表，這種線性表就是二維數(shù)組，若在二維數(shù)組中，元素還是線性表，即得到三維數(shù)組，依次類推可以得到n維數(shù)組。 本節(jié)主要討論數(shù)組的有關(guān)概念、存儲結(jié)構(gòu)及地址變換。 第三張，PPT共八十五頁，創(chuàng)作于2022年6月511 數(shù)組類型與存儲結(jié)構(gòu)一、二維數(shù)組 一個m行n列的二維

2、數(shù)組如下表所示： 第四張，PPT共八十五頁，創(chuàng)作于2022年6月數(shù)組類型與存儲結(jié)構(gòu) 令i =（ai1，ai2，ai,n）(i=1,2,m) ，每行作為一個元素，則A=(1 ,2 ,m) 是一個元素為線性表的線性表。若令j = (a1j，a2j，am j)T (j=1,2,n),每列作為一個元素，則A=(1,2,n)也是一個元素為線性表的線性表?；谶@一原因，而把數(shù)組看成是線性表的推廣。 第五張，PPT共八十五頁，創(chuàng)作于2022年6月數(shù)組類型與存儲結(jié)構(gòu) 數(shù)組是一個具有固定格式、固定個數(shù)的數(shù)據(jù)元素構(gòu)成的有序集合，每一個數(shù)據(jù)元素有唯一的一對下標標識（i，j），因此，在數(shù)組中不能做插入、刪除操作。在高

3、級語言中，數(shù)組一旦被定義，每一維的下標上下界都不能改變。對數(shù)組可以施加的操作主要有以下兩種：（1）取值操作：給定下標，讀其對應(yīng)的數(shù)據(jù)元素。（2）賦值操作：給定下標，存儲或修改與其相對應(yīng)的數(shù)據(jù)元素。 第六張，PPT共八十五頁，創(chuàng)作于2022年6月數(shù)組類型與存儲結(jié)構(gòu) 由含n個下標（0jibi1，i=1,2,n）且具有相同類型的 個數(shù)據(jù)元素構(gòu)成的集合稱為一個n維數(shù)組，bi稱為第i維的長度。數(shù)組中的每個元素對應(yīng)于一組下標（ ），受到n個關(guān)系的約束。固定n-1個下標，讓另一個下標變換就是一個一維數(shù)組。在n個關(guān)系中，對于任意元素（0jibi2）都有一個直接后繼。n維數(shù)組的ADT定義。 只包含4種操作： I

4、nitArray(&A，n，b1，b2，,bn)：初始化數(shù)組。 DestroyArray(&A)：撤銷數(shù)組。 Value(A，&e，j1，j2，jn)。取某個數(shù)據(jù)元素的值 Assign(&A，e，j1，j2，jn)：為數(shù)據(jù)元素賦值。 第七張，PPT共八十五頁，創(chuàng)作于2022年6月數(shù)組的內(nèi)存映象一、二維數(shù)組的存儲結(jié)構(gòu)及地址變換1、以行為主序順序存儲。用一塊連續(xù)存儲空間逐行順序存儲數(shù)組元素。例如：一個mn數(shù)組按行存儲表示如下圖： 第八張，PPT共八十五頁，創(chuàng)作于2022年6月數(shù)組的內(nèi)存映象2、以列為主序順序存儲。用連續(xù)存儲空間逐列順序存儲數(shù)組元素。例如：mn數(shù)組按列順序存儲，如下圖所示：第九張，P

5、PT共八十五頁，創(chuàng)作于2022年6月512 數(shù)組的內(nèi)存映象3、地址變換設(shè)二維數(shù)組Amn順序存儲在連續(xù)區(qū)域中，基地址為LOC(a11)，每個數(shù)組元素占據(jù)L個地址單元，現(xiàn)在考察由元素aij的下標求其存儲地址的計算公式為：對于“以行為主序”的存儲方式，因為數(shù)組元素aij的前面有i-1行，每一行有n個元素數(shù)，在第i行中，它的前面還有j-1個元素，所以有： LOC(aij) = LOC(a11) + ( (i-1)n + j-1 )L 。在C語言中，對數(shù)組的每一維下標，規(guī)定下界從0開始，所以可改為：LOC(aij) = LOC(a00) + ( in + j )L。第十張，PPT共八十五頁，創(chuàng)作于202

6、2年6月數(shù)組的內(nèi)存映象對于“以列為主序”的存儲方式，數(shù)組元素aij的前面有j-1列，每一列有m個元素數(shù)，在第j列中，它的前面還有i-1個元素，所以有： LOC(aij) = LOC(a11) + ( (j-1)m + i-1 )L。當(dāng)下界從0開始是，應(yīng)改為：LOC(aij) = LOC(a00) + ( jm + i )L。對一般的二維數(shù)組，設(shè)數(shù)組Ac1.d1 c2.d2，下標的上、下界可以是任何整數(shù)，則aij的物理地址計算公式為：行主序：LOC(aij)=LOC(a c1 c2)+( (i- c1)( d2 - c2 + 1)+ (j- c2) )L。列主序：LOC(aij)=LOC(a c

7、1 c2)+( (j- c2)( d1 c1 + 1)+ (i- c1) )L。 第十一張，PPT共八十五頁，創(chuàng)作于2022年6月數(shù)組的內(nèi)存映象二、n維數(shù)組 LOC( )=LOC( )+(d2-c2+1)(d3-c3+1)(dn-cn+1)(j1-c1 )+(d3-c3+1)(d4-c4+1)(dn-cn+1)(j2-c2) +(dn-cn+1)jn-1-cn-1) + (jn-cn )L= LOC( ) + ( )L例如：三維數(shù)組Amnp，元素aijk其物理地址為：LOC(aijk)=LOC(a111)+( ( i-1)np+ (j-1)p +k-1)L 第十二張，PPT共八十五頁，創(chuàng)作于2

8、022年6月數(shù)組的內(nèi)存映象舉例。若矩陣Amn 中存在某個元素aij滿足：aij是第i行中最小值且是第j列中的最大值，則稱該元素為矩陣A的一個鞍點。試編寫一個算法，找出A中的所有鞍點。解決此問題的基本思想是：在矩陣A中求出每一行的最小值元素，然后判斷該元素它是否是它所在列中的最大值，是則打印出，否則不輸出，接著處理下一行。設(shè)矩陣A用一個二維數(shù)組表示。 第十三張，PPT共八十五頁，創(chuàng)作于2022年6月數(shù)組的內(nèi)存映象算法如下：void saddle (int A ,int m, int n) / m,n是矩陣A的行數(shù)和列數(shù) int i,j,min; for (i=0;im;i+) / 按行處理 mi

9、n=Ai0; for (j=1; jn; j+) if (Aijmin ) min=Aij; k=j; / 找第i行最小值 for (p=0;papk; p+) / 檢測該行中的每一個最小值是否是鞍點 if ( p=m) printf (%d,%d,%dn, i ,k,min); / if /for/ 第十四張，PPT共八十五頁，創(chuàng)作于2022年6月5.2 特殊矩陣的壓縮存儲521 對稱矩陣一、對稱矩陣的壓縮存儲對稱矩陣：n階方陣中，若aij=aji，其中1i,jn，則稱該矩陣為對稱矩陣。如下圖所示的矩陣是一個階對稱矩陣。第十五張，PPT共八十五頁，創(chuàng)作于2022年6月特殊矩陣的壓縮存儲對稱矩

10、陣的元素關(guān)于主對角線對稱，因此只需存儲上三角或下三角部分即可。例如：上圖（a）給出的5階對稱矩陣存儲到一個一維數(shù)組如下圖（b）所示。第十六張，PPT共八十五頁，創(chuàng)作于2022年6月對稱矩陣的壓縮存儲將一個對稱矩陣只存儲下三角（或上三角）部分的元素aij，此時有ji且1in，對于上三角部分的元素aij和它對應(yīng)的aji相等，因此當(dāng)訪問的元素在上三角時，直接去訪問與其對應(yīng)的下三角元素即可。這樣，原來需要n2個存儲單元，現(xiàn)在只需要 個，可節(jié)約 個存儲單元。第十七張，PPT共八十五頁，創(chuàng)作于2022年6月對稱矩陣的壓縮存儲采用以行為主序的方法順序存儲到一個一維數(shù)組中。因為下三角中共有個 元素，設(shè)存儲結(jié)構(gòu)

11、為一維數(shù)組。A ，如下圖所示。 第十八張，PPT共八十五頁，創(chuàng)作于2022年6月對稱矩陣的壓縮存儲二、地址變換設(shè)矩陣的下三角部分的元素aij，下標滿足條件：ij且1in，存儲到一維數(shù)組A的第k個元素Ak中， 則有： 第十九張，PPT共八十五頁，創(chuàng)作于2022年6月522 三角矩陣一、下三角矩陣的壓縮存儲形如下圖所示的矩陣稱為下三角矩陣。主對角線上方所有元素等于同一個常數(shù)C。第二十張，PPT共八十五頁，創(chuàng)作于2022年6月一、下三角矩陣的壓縮存儲下三角矩陣的壓縮存儲與對稱矩陣的壓縮存儲類似。例如：下圖所給給出一個下三角矩陣存儲結(jié)構(gòu)。第二十一張，PPT共八十五頁，創(chuàng)作于2022年6月下三角矩陣的壓

12、縮存儲下三角矩陣壓縮存儲的地址變換用一維數(shù)組A 。存儲下三角矩陣。如下圖所示： 設(shè)aji 存放在Ak中，則k與i、j的對應(yīng)關(guān)系有如下公式：當(dāng)ij時， k= 當(dāng)ij 時第二十四張，PPT共八十五頁，創(chuàng)作于2022年6月523 帶狀矩陣n階矩陣A稱為帶狀矩陣，如果存在最小正數(shù)m，滿足當(dāng)i-jm時，aij =0，這時稱w=2n-1為矩陣A的帶寬。例如下圖是一個w=3(m=2)的帶狀矩陣。 第二十五張，PPT共八十五頁，創(chuàng)作于2022年6月帶狀矩陣帶狀矩陣A采用壓縮存儲有兩種方法。第一種方法：將A壓縮到一個n行w列的二維數(shù)組B中，如下圖所示。當(dāng)某行非零元素的個數(shù)小于帶寬w時，先存放非零元素然后補零。第

13、二十六張，PPT共八十五頁，創(chuàng)作于2022年6月帶狀矩陣另一種壓縮方法是將帶狀矩陣壓縮到一維數(shù)組中去，按以行為主序存儲，順序存放非零元素，如下圖所示，按此規(guī)律，可得到相應(yīng)的映象函數(shù)。如當(dāng)w=3時，映象函數(shù)為：k=2（i-1)+j-1 第二十七張，PPT共八十五頁，創(chuàng)作于2022年6月5.3 稀疏矩陣當(dāng)m*n矩陣中有t個非零元素且tm*n時，這樣的矩陣稱為稀疏矩陣。 稀疏矩陣壓縮存儲方法是僅存放非零元素。由于非零元素分布沒有規(guī)律，為了能找到相應(yīng)的元素，所以僅存儲非零元素的值是不夠的，還必須記下它們所在的行號和列號。為此采取如下方法：將非零元素所在的行、列以及它的值構(gòu)成一個三元組（i,j,v），然

14、后將這些三元組按某種規(guī)律順序存儲，這種方法可以節(jié)約大量的存儲空間。 第二十八張，PPT共八十五頁，創(chuàng)作于2022年6月稀疏矩陣稀疏矩陣的ADT定義對稀疏矩陣的操作只定義一下8種：創(chuàng)建稀疏矩陣。 CreareSMatrix（&M）撤銷稀疏矩陣。 DetroySMatrix（&M）輸出稀疏矩陣。 PrintSMatrix（M）復(fù)制稀疏矩陣。 CopySMatrix（M , &T）稀疏矩陣加法。 AddSMatrix（M , N , &T）稀疏矩陣減法。 SubtractSMatrix（M , N , &T）稀疏矩陣乘法。MultSMatrix（M , N , &T）稀疏矩陣轉(zhuǎn)置。 Transpos

15、eSMatrix（M , &T）第二十九張，PPT共八十五頁，創(chuàng)作于2022年6月531 稀疏矩陣的三元組存儲與轉(zhuǎn)置、乘法一、稀疏矩陣的三元組存儲表示 將稀疏矩陣每個非0元素的值以及行下標、列下標構(gòu)成的三元組按行優(yōu)先順序存儲，同一行中列號按從小到大排列成一個線性表，稱這種存儲方法為三元組表示。例如，設(shè)稀疏矩陣如下圖 (a)所示，對應(yīng)的三元組存儲結(jié)構(gòu)如圖 (b)所示。 第三十張，PPT共八十五頁，創(chuàng)作于2022年6月稀疏矩陣的三元組存儲與轉(zhuǎn)置、乘法存儲結(jié)構(gòu)的定義：define MAXSIZE 1024 / 非0元素的個數(shù)數(shù)typedef struct / 定義三元組元素結(jié)構(gòu) int i , j;

16、 / 非零元素的行號和列號 ElemType e ; / 非零元素的值 Triple ; / 三元組類型typedef struct SPNode dataMAXSIZE+1; / 三元組順序表int mu , nu , tu ; / 矩陣的行、列及非零元素的個數(shù) TSMatrix ; / 三元組表的存儲類型 第三十一張，PPT共八十五頁，創(chuàng)作于2022年6月稀疏矩陣的三元組存儲與轉(zhuǎn)置、乘法二、稀疏矩陣的算法實現(xiàn)1矩陣的轉(zhuǎn)置設(shè)TSMatrix A表示一個mn的稀疏矩陣，其轉(zhuǎn)置TSMatrix B是一個nm的稀疏矩陣。轉(zhuǎn)置算法基本思想：A的行、列轉(zhuǎn)化成B的列、行；在A.data中依次找第一列的、

17、第二列的、直到最后一列，并將找到的每個三元組的行、列交換后順序存儲到B.data中。 第三十二張，PPT共八十五頁，創(chuàng)作于2022年6月稀疏矩陣的三元組存儲與轉(zhuǎn)置、乘法算法描述如下：void TransposeSMatrix ( TSMatrix A , TSMatrix &B) B.mu=A.nu; B.nu=A.mu; B.tu=A.tu ; / 復(fù)制行、列數(shù)及元素個數(shù) if ( B.tu ) / 有非零元素則轉(zhuǎn)換 q=1; for ( col = 1; col = A.nu ; col+ ) / 按A的列序轉(zhuǎn)換 for ( p=1; ptu0) return OK; / Transpos

18、eSMatrix 第三十三張，PPT共八十五頁，創(chuàng)作于2022年6月稀疏矩陣的三元組存儲與轉(zhuǎn)置、乘法算法性能分析。設(shè)m、n是原矩陣的行數(shù)和列數(shù)，t是稀疏矩陣的非零元素個數(shù)。該算法的時間主要耗費在二重循環(huán)上，所以時間復(fù)雜性為O(n*t)。顯然當(dāng)非零元素的個數(shù)t和m*n同數(shù)量級時，算法的時間復(fù)雜度為O(m*n2)。與通常存儲方式下矩陣轉(zhuǎn)置算法相比，可能節(jié)約了一定量的存儲空間，但算法的時間性能更差一些。 第三十四張，PPT共八十五頁，創(chuàng)作于2022年6月稀疏矩陣的三元組存儲與轉(zhuǎn)置、乘法2帶列邏輯連接的三元組順序存儲與改進的轉(zhuǎn)置算法引入兩個向量：numn+1和cpotn+1，其中numcol表示矩陣A

19、中第col列的非零元素的個數(shù)（為了方便下標均從1開始），cpotcol的初始值表示矩陣A中的第col列的第一個非零元素在B.data中的位置。于是cpot的初始值為：cpot1=1；cpotcol=cpotcol-1+numcol-1； 2coln 第三十五張，PPT共八十五頁，創(chuàng)作于2022年6月稀疏矩陣的三元組存儲與轉(zhuǎn)置、乘法例如。下圖（a）所給矩陣A的num和cpot的數(shù)組值如右圖所示。改進的稀疏矩陣轉(zhuǎn)置算法稱為快速轉(zhuǎn)置。算法思想：依次掃描A.data，當(dāng)掃描到一個col列元素時，直接將其存放在B.data的cpotcol位置上，且cpotcol加，cpotcol中始終是下一個col列元

20、素在B.data中的位置。第三十六張，PPT共八十五頁，創(chuàng)作于2022年6月稀疏矩陣的三元組存儲與轉(zhuǎn)置、乘法快速轉(zhuǎn)置算法如下：Status FastTransposeSMatrix ( TSMatri x A , TSMatrix &B ) B.mu=A.nu ; B.nu=A.mu ; B.tu=A.tu ; / 稀疏矩陣的行、列及元素個數(shù) if ( B.tu0 ) / 有非零元素則轉(zhuǎn)換 for ( i = 1 ; i = A.nu ; i+ ) numi=0; for (i= 1 ; i = A.tu ; i+ ) / 求矩陣A中每一列非零元素的個數(shù) j = A.datai.j ; num

21、j+; cpot1 = 1 ; / 求矩陣A中每一列第一個非零元素在B.data中的位置for ( i = 2 ; i = A.nu ; i+ ) cpoti= cpoti-1+numi-1; for ( i =1; i = A.tu ; i+) / 掃描三元組表 j =A.datai.j ; / 當(dāng)前三元組的列號 k = cpotj ; / 當(dāng)前三元組在B.data中的位置 B.datak.i = A.datai.j ; B.datak.j = A.datai.i ; B.datak.v = A.datai.v ;cpotj+; / for i / if (B.tu) return B; /

22、 返回的是轉(zhuǎn)置矩陣的指針 / FastTransposeSMatrix 第三十七張，PPT共八十五頁，創(chuàng)作于2022年6月稀疏矩陣的三元組存儲與轉(zhuǎn)置、乘法算法的時間復(fù)雜度分析：上述算法中有四個循環(huán)，分別執(zhí)行n，t，n-1，t次，在每個循環(huán)中，每次迭代的時間是一個常量，因此總的計算量是O（n+t）。所需要的存儲空間比前一個算法多了兩個向量，空間復(fù)雜度為O（t）。 第三十八張，PPT共八十五頁，創(chuàng)作于2022年6月2帶行邏輯連接的三元組順序存儲與乘積算法已知稀疏矩陣A(m1 n1)和B(m2 n2)，求乘積C(m1 n2)。例如：稀疏矩陣A、B、C及它們對應(yīng)的三元組順序表A.data、B.data

23、、C.data如下圖 (a)和(b)所示。 第三十九張，PPT共八十五頁，創(chuàng)作于2022年6月帶行邏輯連接的三元組順序存儲與乘積算法由矩陣乘法規(guī)則知：Ci，j=Ai,1B1,j+Ai,2B2,j+Ai,nBn,j =當(dāng)A的元素Ai,k的列號與B的元素Bk,p的行號相等時才能相乘，且當(dāng)兩項都不為零時，乘積中的這一項才不為零。為運算方便設(shè)一個累加器：datatype tempn+1；用來存放當(dāng)前行中cij的值，當(dāng)前行中所有元素全部計算出之后，再存放到C.data中去。 第四十張，PPT共八十五頁，創(chuàng)作于2022年6月帶行邏輯連接的三元組順序存儲與乘積算法為了便于在B.data中尋找B中的第k行的第

24、一個非零元素，與前面類似，引入numn和rpotn兩個向量。numk表示矩陣B中第k行的非零元素的個數(shù)；rpotk表示第k行的第一個非零元素在B.data中的位置。于是有：rpot1=1rpotk=rpotk-1+numk-1 2kn第四十一張，PPT共八十五頁，創(chuàng)作于2022年6月帶行邏輯連接的三元組順序存儲與乘積算法例如，下圖（a）的矩陣B的其numn 和rpotn 的值如右邊的表所示。k1234num k 2020cpot k 1335第四十二張，PPT共八十五頁，創(chuàng)作于2022年6月帶行邏輯連接的三元組順序存儲與乘積算法稀疏矩陣存儲結(jié)構(gòu)定義：# define MAXSIZE 1024

25、/ 稀疏矩陣非0元素最大個數(shù)# define MAXRC 100 / 稀疏矩陣的最大行數(shù)typedef struct / 定義帶行邏輯連接的三元組順序表類型 Triple data MAXSIZE+1 ; int rpotMAXRC+1 int mu , nu , tu ; RLSMatrix 稀疏矩陣乘法的算算步驟：初始化。清理一些單元，準備按行順序存放乘積矩陣;求B的numn和rpotn數(shù)組值;做矩陣乘法。將A.data中三元組的列值與B.data中三元組的行值相等的非零元素相乘，并將具有相同下標的乘積元素相加。第四十三張，PPT共八十五頁，創(chuàng)作于2022年6月帶行邏輯連接的三元組順序存儲

26、與乘積算法稀疏矩陣乘法的算法描述：Status MatrixMultiply (RLSMatrix *A, RLSMatrix *B, RLSMatrix &C) / 求稀疏矩陣C=AB int p , q , i , j , k , r ; ElemType ctempn+1; int numB.nu+1; if (A.nu != B.mu) return ERROR ; / A的列與B的行不相等 C.mu = A.mu ; C.nu = B.nu ; C.tu = 0 ; if (A.tu*B.tu != 0 ) for ( i =1 ; i = B.mu ; i+ ) numi=0; /

27、 求矩陣B中每一行非零元素的個數(shù)for ( k =1 ; k = B.tu ; k+) i = B.datak.i ;numi+; rpot1=1; / 求矩陣B中每一行第一個非零元素在B.data中的位置for (i=2 ; i= B.mu ; i+ ) rpoti = rpoti-1 + numi-1 ;第四十四張，PPT共八十五頁，創(chuàng)作于2022年6月帶行邏輯連接的三元組順序存儲與乘積算法r = 0 ; / 當(dāng)前C中非零元素的個數(shù) p=1; / 指示A.data中當(dāng)前非零元素的位置 for ( i= 1; i= A.mu; i+) for ( j =1 ; j = B.nu ; j+)

28、tempj=0; / cij的累加器初始化 while (A.datap.i = = i ) / 求第i行的 k = A.datap.j; / A中當(dāng)前非零元的列號 if (kB.mu) t = rpotk+1 ; else t = B.tu+1; / 確定B中第k行的非零元素在B.data中的下限位置 for (q = rpotk ; qt ; q+ ) / B中第k行的每一個非零元素 j = B.dataq.j ; tempj + = A.datap.e * B.dataq.e p+; / while for (j=1;jnu;j+) if (tempj ) r+; C.datar= i

29、, j , tempj ; /for iC.tu = r ; returnOK ; / MulSMatrix 第四十五張，PPT共八十五頁，創(chuàng)作于2022年6月帶行邏輯連接的三元組順序存儲與乘積算法算法的時間性能分析。求num的時間復(fù)雜度為O(B.nu+B.tu)；求rpot 時間復(fù)雜度為O(B.mu)；求temp時間復(fù)雜度為O(A.mu*B.nu)；求C的所有非零元素的時間復(fù)雜度為O(A.tu*B.tu / B.mu)；壓縮存儲時間復(fù)雜度為O(A.mu*B.nu)；所以總的時間復(fù)雜度為O(A.mu*B.nu+(A.tu*B.tu) / B.nu )。 第四十六張，PPT共八十五頁，創(chuàng)作于20

30、22年6月532 稀疏矩陣的十字鏈表存儲與求和一、十字鏈表存儲結(jié)構(gòu) 基本思想：每個非零元素用一個結(jié)點存儲，結(jié)點由5個域組成，如下圖所示。其中： i域存儲非零元素的行號， j域存儲非零元素的列號， e域存儲元素的值，right是橫向鏈表指針域，down是縱向鏈表指針域。 第四十七張，PPT共八十五頁，創(chuàng)作于2022年6月稀疏矩陣的十字鏈表存儲與求和存儲方法：將稀疏矩陣的每一行的非0元素結(jié)點按列號從小到大的順序，由right指針拉成一個帶表頭結(jié)點的行單鏈表。每一列的非0元素按行號從小到大的順序，由down指針拉成一個帶表頭結(jié)點的列單鏈表。每個非零元素aij，既是第i個行鏈表中的一個結(jié)點，又是第j個

31、列鏈表中的一個結(jié)點。所有行鏈表的頭指針用一個指針數(shù)組rheadm存放，所有列鏈表的頭指針用指針數(shù)組cheadn存放。 第四十八張，PPT共八十五頁，創(chuàng)作于2022年6月稀疏矩陣的十字鏈表存儲與求和存儲結(jié)構(gòu)定義：typedef struct OLNnode / 十字鏈表的結(jié)點結(jié)構(gòu)int row , col ; / 元素的行號與列號域ElemtType e ; / 數(shù)據(jù)元素域 struct OLNode *down , *right ; / 行、列鏈表指針域 OLNode , *OLink ; typedef struct / 定義行、列鏈表頭結(jié)點指針數(shù)組OLink *rhead , *chead

32、 ; / 行、列鏈表頭結(jié)點指針數(shù)組 int mu , nu , tu ; / 行數(shù)、列數(shù)、非0元素個數(shù)域 CrossList ; 第四十九張，PPT共八十五頁，創(chuàng)作于2022年6月稀疏矩陣的十字鏈表存儲與求和例如。稀疏矩陣A的十字鏈表存儲結(jié)構(gòu)如下圖所示。 第五十張，PPT共八十五頁，創(chuàng)作于2022年6月稀疏矩陣的十字鏈表存儲與求和二、基于十字鏈表存儲結(jié)構(gòu)的稀疏矩陣求和算法。1建立稀疏矩陣的十字鏈表算法步驟：（1）輸入矩陣M的行數(shù)m、列數(shù)n和非0元素個數(shù)r。（2）申請行、列頭指針數(shù)組空間，并初始化為空指針。（3）逐個輸入非0元素的形如（i,j,aij）的三元組，建立三元組結(jié)點，分別插入到行鏈表和

33、列鏈表中，直到所有非0元素的的三元組輸入完為止。第五十一張，PPT共八十五頁，創(chuàng)作于2022年6月稀疏矩陣的十字鏈表存儲與求和算法描述如下：status CreateSMatrixOL (CrossList &M ) / 創(chuàng)建十字鏈表針if ( M ) free ( M ) ;scanf (“%d ,%d, %d”, &m , &n , &t ) ; M.rhead = (OLink *)malloc(m+1)*(sizeof (OLink); / 申請行頭指針數(shù)組空間 if ( !M.rhead ) exit ( OVERFLOW ) ;M.chead = (OLink *)malloc(n

34、+1)*(sizeof (OLink); / 申請列頭指針數(shù)組空間 if ( !M.chead ) exit ( OVERFLOW ) ; M.rhead = M.chead = NULL ; / 行、列頭指針數(shù)置空 for( k =1; k i = i ; p-j = j ; p-e = e ; / 生成結(jié)點if ( M.rheadi = = NULL | M.rheadi-j j ) / 在第i個鏈表插入結(jié)點 第五十二張，PPT共八十五頁，創(chuàng)作于2022年6月稀疏矩陣的十字鏈表存儲與求和 p-right = M.rheadi；M.rheadi = p ; else / 在第i個行鏈表找插入

35、位置 for (q = M.chead; (q-right) & q.right-j right ；p-right = q-right ; q-right = p ; / 插入結(jié)點if ( M.cheadj = = NULL | M.rheadj-i i ) / 在第j個列鏈表插入結(jié)點 p-down = M.cheadj；M.cheadj = p ; else / 在第j個列鏈表找插入位置 for (q = M.cheadj; (q-down) & q.down-i doen ；p-down = q-right ; q-down = p ; / 插入結(jié)點 return OK ; 上述算法的時間

36、復(fù)雜度為O(ts)，其中s=max(m,n)。 第五十三張，PPT共八十五頁，創(chuàng)作于2022年6月稀疏矩陣的十字鏈表存儲與求和基于十字鏈表的稀疏矩陣求和已知兩個稀疏矩陣A和B，分別采用十字鏈表存儲，計算C=A+B，C也采用十字鏈表方式存儲，并且在A的基礎(chǔ)上形成C。對于求C=A-B，可表示成C=A+（-B）矩陣加法規(guī)則：只有當(dāng)A與B的行數(shù)和列數(shù)相等時二者才能相加，且cij = aij + bij。 第五十四張，PPT共八十五頁，創(chuàng)作于2022年6月稀疏矩陣的十字鏈表存儲與求和以下假定將B加到A上。設(shè)pa和pb分別指向A和B的十字鏈表中行號相同的兩個結(jié)點，對應(yīng)元素相加時分為下列4種情況：(1) 若

37、pa-j = pb-j且pa-e + pb-e 0，則只要用aij+bij的值改寫pa所指結(jié)點的數(shù)據(jù)域即可。(2) 若pa-j=pb-j且pa-e + pb-e =0，則需要在矩陣A的十字鏈表中刪除pa所指結(jié)點，此時需改變該行鏈表中前趨結(jié)點的right域，以及該列鏈表中前趨結(jié)點的down域。(3) 若pa-j j且pa-j0（即不是表頭結(jié)點），則只需要將pa指針向右推進一步，繼續(xù)進行比較。(4) 若pa-jpb-j或pa-j0（即是表頭結(jié)點），則需要在矩陣A的十字鏈表中插入一個pb所指結(jié)點。 第五十五張，PPT共八十五頁，創(chuàng)作于2022年6月稀疏矩陣的十字鏈表存儲與求和算法描述如下：statu

38、s AddMatrix (CrossList &A , CrossList B) / 求稀疏矩陣的乘積AB OLNode *p, *q,*pa,*pb,*ca,*cb,*qa; if (A.mu != B.mu | A.nu != B.nu ) return ERROR ; ca = A.rhead1 ; / 初始化ca指向A的第一個結(jié)點 cb = B.rhead1 ; / 初始化cb指向B的第一個結(jié)點 do pa = ca-right; / pa指向A矩陣當(dāng)前行中第一個結(jié)點 qa = ca; / qa指向pa的前驅(qū) pb=cb-right; / pb指向B矩陣當(dāng)前行中第一個結(jié)點 while

39、(pb-j != 0 ) / 當(dāng)前行沒有處理完 if (pa-j j & pa-j !=0 ) / 第三種情況 qa=pa; pa=pa-right; else if (pa-j pb-j | pa-j = =0 ) / 第四種情況 p= malloc(sizeof(MNode); p-i = pb- i ; p-j = pb-j; p-e = pb-e ; p-right = pa ; qa-right = p ; / 新結(jié)點插入*pa的前面 pa=p; / 新結(jié)點還要插到列鏈表的合適位置，先找位置，再插入 q = Find_JH (Ha,p-col); / 從列鏈表的頭結(jié)點找起第五十六張，

40、PPT共八十五頁，創(chuàng)作于2022年6月稀疏矩陣的十字鏈表存儲與求和 while (q-down-i != 0 & q-down-i i ) q=q-down; p-down=q-down; / 插在*q的后面 q-down=p ; pb=pb-right; / end if else / 第一、二種情況 x= pa-v_next.v+ pb-v_next.v; if (x= =0) / 第二種情況 qa-right = pa-right; / 從行鏈中刪除q= Find_JH (Ha,pa-col); / 找*pa的列前驅(qū)結(jié)點并刪除 while ( q-down-i i ) q = q-dow

41、n; q-down = pa-down ; free (pa) ; pa = qa; / if (x= =0) else / 第一種情況 pa-e = x ; qa = pa ; pa = pa-right; pb = pb-right; / while ca = ca-next; / ca指向A中下一行的表頭結(jié)點 cb = cb-next; / cb指向B中下一行的表頭結(jié)點 while (ca-i = =0 ) / 當(dāng)還有未處理完的行則繼續(xù) 第五十七張，PPT共八十五頁，創(chuàng)作于2022年6月54 廣義表 5.4.1廣義表的概念與ADT定義一、廣義表的概念與性質(zhì)1廣義表的定義。廣義表是n（n0

42、）個數(shù)據(jù)元素a1，a2，ai，an的有限序列，一般記作：Ls（a1，a2，ai，an）其中：Ls是廣義表的名稱，n稱為廣義表的長度，記為Length(Ls)。每個元素ai（1in）稱為Ls的成員，它們既可以是單個元素，也可以是一個廣義表，分別稱為廣義表Ls的原子和子表。當(dāng)廣義表Ls非空時，稱第一個元素a1為Ls的表頭記為head（Ls），稱其余元素組成的子表（a2，ai，an）為Ls的表尾,記為tail(Ls) 。一個廣義表中的括號嵌套層數(shù)稱為該廣義表的深度,記為Depth(Ls)。廣義表是遞歸定義的。 第五十八張，PPT共八十五頁，創(chuàng)作于2022年6月廣義表例如：下面是一些廣義表的例子。A

43、（），空廣義表，Length(A) =0，Depth(A)=1。B （e），單個原子構(gòu)成的廣義表，Length(B) =1，Depth(B)=1。C （a，（b，c，d），一個原子和一個子表構(gòu)成的廣義表。Length(C) =2，Depth(C)=2。D （A，B，C）= (（），（e），（a，（b，c，d）)，以三個廣義表為元素的廣義表，Length(D) =3，Depth(D)=3。E （a，E）= (a , (a , (a , (a, E ) ) ，這是一個遞歸的廣義表，其長度和深度可以任意大。F （），這是一個由一個空廣義表構(gòu)成的廣義表，Length(F) =1，Depth(F)=2。

44、 第五十九張，PPT共八十五頁，創(chuàng)作于2022年6月廣義表2廣義表的性質(zhì) 廣義表是一種多層次的數(shù)據(jù)結(jié)構(gòu)。廣義表的元素可以是單元素，也可以是子表，而子表的元素還可以是子表?？梢杂脴浣Y(jié)構(gòu)表示廣義表，其中原子用小矩形表示，子表用圓圈表示。例如，上述例子中的廣義表D，畫成樹的形式如下圖所示。 第六十張，PPT共八十五頁，創(chuàng)作于2022年6月廣義表廣義表可以是遞歸的表。廣義表的定義并沒有限制元素的遞歸，即廣義表的元素也可以是其自身的子表。例如表E就是一個遞歸的表。廣義表可以為其他表所共享。例如，廣義表A、B、C是廣義表D的共享子表。在D中可以不必列出子表的值，而用子表的名稱來引用。 第六十一張，PPT共

45、八十五頁，創(chuàng)作于2022年6月廣義表二、廣義表ADT定義 1初始化廣義表InitGList ( &L )。2創(chuàng)建廣義表CreateGLists(&L , S) 。3撤消廣義表DestroyGList ( &L )。4復(fù)制廣義表CopyGList(&T ，L ) 。5判斷廣義表是否空EmptyGList(&L)。6求廣義表的長度GListLength( L )。7求廣義表的深度GListDepth( L )。8在廣義表L中查找數(shù)據(jù)元素GListLocate (L ，x)。9插入一個元素InsertFirst (&L ，e )。10刪除一個元素DeleteFirstge (&L ，&e )。11取

46、表頭GetHead ( L )。 12取表尾GetTail ( L )。 13遍歷廣義表TraverseGList ( L , visit( ) )。 第六十二張，PPT共八十五頁，創(chuàng)作于2022年6月廣義表廣義表操作舉例。對前面所給出的廣義表A、B、C、D、E、F有。GetHead（B） e , GetTail（B）（）;GetHead（C） a , GetTail（C）（b，c，d）;GetHead（D） A , GetTail（D）（B，C）;GetHead（E） a , GetTail（E）（E）;GetHead（F）（） GetTail（F）（）。 第六十三張，PPT共八十五頁，創(chuàng)作

47、于2022年6月542 廣義表的存儲一、頭尾表示法 廣義表中的數(shù)據(jù)元素既可能是廣義表，也可能是原子，相應(yīng)地在頭尾表示法中，結(jié)點的結(jié)構(gòu)形式有兩種：一種是子表結(jié)點，用以表示子表；另一種是原子結(jié)點，用以表示原子。在表結(jié)點中應(yīng)該包括一個指向表頭的指針和指向表尾的指針；而在原子結(jié)點中應(yīng)該包括所表示原子的元素值。為了區(qū)分這兩類結(jié)點，在結(jié)點中還要設(shè)置一個標志域，如果標志為1，則表示該結(jié)點為子表結(jié)點；如果標志為0，則表示該結(jié)點為原子結(jié)點。結(jié)點結(jié)構(gòu)如圖所示： 第六十四張，PPT共八十五頁，創(chuàng)作于2022年6月廣義表的存儲存儲結(jié)構(gòu)定義：typedef enum ATOM, LIST Elemtag; / ATOM

48、=0表示單元素；LIST=1表示子表typedef struct GLNode Elemtag tag ; / 標志域，用于區(qū)分元素結(jié)點和表結(jié)點 union / 元素結(jié)點和表結(jié)點的聯(lián)合部分 AtomType atom ; / atom是元素結(jié)點的值域 struct struct GLNode *hp, *tp ; ptr; / ptr是表結(jié)點的指針域，ptr.hp和ptr.tp分別指向表頭和表尾 *GList; / 廣義表類型 第六十五張，PPT共八十五頁，創(chuàng)作于2022年6月廣義表的存儲舉例對前面所給的廣義表A、B、C、D、E、F，存儲結(jié)構(gòu)如下圖所示。 D （A，B，C）= (（），（e），

49、（a，（b，c，d）)第六十六張，PPT共八十五頁，創(chuàng)作于2022年6月廣義表的存儲二、孩子兄弟表示法兩種結(jié)點形式：一種是有孩子結(jié)點，用以表示列表；另一種是無孩子結(jié)點，用以表示單元素。在有孩子結(jié)點中包括一個指向第一個孩子（長子）的指針和一個指向兄弟的指針；而在無孩子結(jié)點中包括一個指向兄弟的指針和該元素的元素值。為了能區(qū)分這兩類結(jié)點，在結(jié)點中還要設(shè)置一個標志域。如果標志為1，則表示該結(jié)點為有孩子結(jié)點；如果標志為0，則表示該結(jié)點為無孩子結(jié)點。結(jié)點結(jié)構(gòu)如圖所示。 第六十七張，PPT共八十五頁，創(chuàng)作于2022年6月廣義表的存儲存儲結(jié)構(gòu)定義：typedef enum ATOM, LIST Elemtag

50、; / ATOM=0：單元素；LIST=1：子表typedef struct GLNode Elemtag tag ; / 標志域，用于區(qū)分元素結(jié)點和表結(jié)點 union / 元素結(jié)點和表結(jié)點的聯(lián)合部分 AtomType atom; / 元素結(jié)點的值域 struct GLNode *hp; / 表結(jié)點的表頭指針 ; struct GLNode *tp; / 指向下一個結(jié)點 *GList; / 廣義表類型 第六十八張，PPT共八十五頁，創(chuàng)作于2022年6月廣義表的存儲舉例對于前面所給的廣義表A、B、C、D、E、F，孩子兄弟表示法如下圖所示。 D （A，B，C）= (（），（e），（a，（b，c，d

51、）)第六十九張，PPT共八十五頁，創(chuàng)作于2022年6月543 廣義表的基本操作算法算法思想：假設(shè)廣義表以串S的形式給出，當(dāng)廣義表為空時，即S=( )，此時直接返回L=NULL。當(dāng)廣義表為不空時，S=(a1 , a2 , , an )，其中ai(i=1,2,n)為S的子串表示的子表。建立廣義表S就是建立n個子表結(jié)點拉成的鏈表。第i個（1in）表結(jié)點的tp指針指向第i+1個表結(jié)點，第n個表結(jié)點的tp指針為NULL。第i個表結(jié)點的hp指針指向由ai建立的子表。由此可見，建立廣義表S轉(zhuǎn)化為建立子表ai（1in）的問題。而建立子表ai（1in）的過程與建立廣義表S的過程完全相同，這顯然是一個遞歸問題。對

52、每個ai又分三種情況：（1）ai是帶括號的空串；（2）ai是長度為1的單字符串；（3）ai是長度大于1的字符串。前兩種情況就是遞歸的終結(jié)狀態(tài)，第三種情況是遞歸調(diào)用。 第七十張，PPT共八十五頁，創(chuàng)作于2022年6月廣義表的基本操作算法遞歸過程如下：基本項：置空廣義表， 當(dāng)S為空表串時； 建立原子結(jié)點子表， 當(dāng)S為單字符串時；歸納項：假定S =(a1 , a2 , , an )，sub=s1,s2,sn是S脫去的最外層括號之后的字符串，其中si(i=1,2,n)是非空的字符串，對每個si建立一個表結(jié)點，結(jié)點的hp指針域指向由si建立的子表，tp指針指向由si+1（itag = ATOM ; L-

53、atom = S; / 創(chuàng)建原子結(jié)點 else L-tag = LIST; p = L ; / 重復(fù)建立n個子表 SubString (sub , S , 2 , StrLength (S )-2 ) ; / 脫去外層括號 do sever ( sub , hsub ) ; / 從sub中分離出表頭串 CreateGList (p-ptr.hp , hsub) ; q = p ; if (!StrEmpty (sub) / 表尾不空 if (!(p = (GList)malloc(sizeof(GLNode) exit (OVERFLOW); p-tag = LIST ; q-ptr.tp =

54、 p; while (!StrEmpty (sub) ); q-ptr.tp = NULL; return OK ; 第七十二張，PPT共八十五頁，創(chuàng)作于2022年6月廣義表的基本操作算法status sever(SString &str , SString &hstr) n = StrLength(str); i= 1; k = 0 ; for (i = 1, k = 0; i = n | k != 0; +i) ch = SubStr (ch , str , i ,1 ); if (ch = = ( ) +k; else if (ch = = ) -k; if (i tag = = 1)

55、p = L-hp; return p; GList GetTail(GList L) if ( L-tag = = 1) p = L-tp; return p; 第七十四張，PPT共八十五頁，創(chuàng)作于2022年6月廣義表的基本操作算法三、求廣義表的深度設(shè)廣義表LS=(a1 , a2 , , an )，求廣義表深度的遞歸形式如下：基本項： Depth (LS) = 1， 當(dāng)LS為空廣義表； Depth (LS) = 0 ， 當(dāng)LS為原子時；歸納項： Depth (LS) = 1 + max Depth (si) | 1=i=1 。算法描述：int GListDepth ( GList L ) if

56、 (! L) return 1; / 空表深度為1 if ( L-tag = = ATOM ) return 0; / 單元素深度為0 for ( max = 0 , p =L ; p ; p = p-ptr.tp) dep = GListDepth ( p-ptr.hp ) ; / 求以p-ptr.hp尾頭指針的子表深度 if (dep max) max = dep; return max +1; / 非空表的深度是各元素的深度的最大值加1 第七十五張，PPT共八十五頁，創(chuàng)作于2022年6月廣義表的基本操作算法四、求廣義表的長度算法思想：只需統(tǒng)計最頂層的表結(jié)點個數(shù)即可。算法描述：int GL

57、istLength ( GList L ) if ( L ) return 1+ GListLength ( L -tp ) ; else return 0 ; 第七十六張，PPT共八十五頁，創(chuàng)作于2022年6月廣義表的基本操作算法五、復(fù)制廣義表算法思想：將廣義表分成表頭和表尾兩部分，先復(fù)制表頭部分，再復(fù)制表尾部分。若表頭部分是原子，就建立一個原子結(jié)點，若表頭是子表，則又將分成表頭和表尾兩部分處理。表尾一定是子表，又分成表頭和表尾兩部分處理。復(fù)制整個廣義表和復(fù)制子表的過程完全相同。設(shè)復(fù)制后的廣義表為NewLS，遞歸過程如下： 基本項：InitGList (NewLS), 當(dāng)LS為空廣義表，置空表； 歸納項：COPY(GetHead(LS) , GetHead (NewLS) ) / 復(fù)制表頭 COPY(GetTail(LS) , GetTail (NewLS) ) / 復(fù)制表尾 第七十七張，PPT共八十五頁，創(chuàng)作于2022年6月廣義表的基本操作算法 算法過程描述：status Copy