數(shù)據(jù)結(jié)構(gòu)第五章

1、 !數(shù)組的定義數(shù)組的定義數(shù)組的順序表示和實現(xiàn)數(shù)組的順序表示和實現(xiàn)矩陣的壓縮存儲矩陣的壓縮存儲 第五章第五章 數(shù)組和廣義表數(shù)組和廣義表廣義表的定義廣義表的定義廣義表的存儲結(jié)構(gòu)廣義表的存儲結(jié)構(gòu)一、一、 數(shù)組的定義數(shù)組的定義 2數(shù)組：數(shù)組： 由一組名字相同、下標不同的變量構(gòu)成由一組名字相同、下標不同的變量構(gòu)成 數(shù)組中各元素具有數(shù)組中各元素具有統(tǒng)一的類型統(tǒng)一的類型； 數(shù)組元素的下標一般具有數(shù)組元素的下標一般具有固定的上界和下界，固定的上界和下界，即數(shù)組一即數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。旦被定義，它的維數(shù)和維界就不再改變。數(shù)組的數(shù)組的基本操作比較簡單基本操作比較簡單，除了結(jié)構(gòu)的初始化和銷毀之

2、除了結(jié)構(gòu)的初始化和銷毀之外，只有存取元素和修改元素值的操作。因此一般選外，只有存取元素和修改元素值的操作。因此一般選用用順序存儲順序存儲。二維數(shù)組的特點：二維數(shù)組的特點：3一維數(shù)組的特點：一維數(shù)組的特點：1 1個下標，個下標，a ai i 是是a ai+1i+1的直接前驅(qū)的直接前驅(qū)2 2個下標，個下標，每個元素每個元素ai,j受到兩個關(guān)系受到兩個關(guān)系（行關(guān)系和列關(guān)系）的約束：（行關(guān)系和列關(guān)系）的約束：一個一個mn的二維數(shù)組可以的二維數(shù)組可以看成是看成是m行的一維數(shù)組，或行的一維數(shù)組，或者者n列的一維數(shù)組。列的一維數(shù)組。N N維數(shù)組的特點：維數(shù)組的特點：n n個下標，個下標，每個元素受到每個元素

3、受到n n個關(guān)系約束個關(guān)系約束一個一個n維數(shù)組可以看成是維數(shù)組可以看成是由若干個由若干個n1維數(shù)組組成的線性表。維數(shù)組組成的線性表。1, 11 , 10, 11, 111101, 00100.nmmmnnnmaaaaaaaaaA二、二、 數(shù)組的運算數(shù)組的運算 4給定一組下標，存取相應(yīng)的數(shù)據(jù)元素給定一組下標，存取相應(yīng)的數(shù)據(jù)元素; ;給定一組下標，修改數(shù)據(jù)元素的值給定一組下標，修改數(shù)據(jù)元素的值. . !數(shù)組的定義數(shù)組的定義數(shù)組的順序表示和實現(xiàn)數(shù)組的順序表示和實現(xiàn)矩陣的壓縮存儲矩陣的壓縮存儲 第五章第五章 數(shù)組和廣義表數(shù)組和廣義表廣義表的定義廣義表的定義廣義表的存儲結(jié)構(gòu)廣義表的存儲結(jié)構(gòu)一、次序約定一

4、、次序約定61以行序為主序以行序為主序 存放規(guī)則：具體實現(xiàn)時，按行號從小到大的順序，先將第存放規(guī)則：具體實現(xiàn)時，按行號從小到大的順序，先將第一行中元素全部存放好，再存放第二行元素，第三行元素，一行中元素全部存放好，再存放第二行元素，第三行元素，依次類推依次類推 在在BASIC語言、語言、 PASCAL語言、語言、 C/C+語語言等高級語言程序設(shè)計中，都是按行優(yōu)先順序存放的。言等高級語言程序設(shè)計中，都是按行優(yōu)先順序存放的。71以行序為主序以行序為主序 0 0a a0000 1 1a a01012 2a a0202n-1n-1a a0,n-10,n-1n na a1010 2n-12n-1a a1

5、,n-11,n-1m m* *n-1n-1a am-1,n-1m-1,n-1第第0行行第第1行行82以列序為主序以列序為主序 0 0a a0000 1 1A A10102 2A A2020m-1m-1A Am-1,0m-1,0m ma a0101 2m-12m-1A Am-1,-1m-1,-1m m* *n-1n-1a am-1,n-1m-1,n-1第第0列列第第1列列二維數(shù)組地址計算通式：設(shè)一般的二維數(shù)組是二維數(shù)組地址計算通式：設(shè)一般的二維數(shù)組是AcAc1 1.d.d1 1, c, c2 2.d.d2 2 93.3.任一元素的地址計算任一元素的地址計算（意義：數(shù)組中的任一元素可隨機存?。ㄒ?/p>

6、義：數(shù)組中的任一元素可隨機存?。簞t則列優(yōu)先列優(yōu)先存儲的通式為：存儲的通式為：LOC(aij)=LOC(ac1，c2)+(j-c2)*(d1-c1+1)+i-c1)*L ac1,c2 ac1,d2 aij ad1,c2 ad1,d2 Amn=單個元單個元素長度素長度aij之前的之前的行數(shù)行數(shù)數(shù)組基址數(shù)組基址總列數(shù)，即總列數(shù)，即第第2 2維長度維長度aij本行前面本行前面的元素個數(shù)的元素個數(shù)已知三要素已知三要素開始結(jié)點的存放地址（即基地址）開始結(jié)點的存放地址（即基地址）維數(shù)和每維的上、下界；維數(shù)和每維的上、下界；每個數(shù)組元素所占用的單元數(shù)每個數(shù)組元素所占用的單元數(shù)則則行優(yōu)先行優(yōu)先存儲時的地址公式

7、為：存儲時的地址公式為：LOC(aij)=LOC(ac1，c2)+(i-c1)*(d2-c2+1)+j-c2)*L例例2：已知二維數(shù)組已知二維數(shù)組Am,m按行存儲的元素地址公式是：按行存儲的元素地址公式是： Loc(aij)= Loc(a11)+(i-1)*m+(j-1)*K , 請問按列存儲的公式請問按列存儲的公式相同嗎？相同嗎？答：盡管是方陣，但公式仍不同。應(yīng)為：答：盡管是方陣，但公式仍不同。應(yīng)為： Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*K 10例例1軟考題軟考題：一個二維數(shù)組一個二維數(shù)組A，行下標的范圍是，行下標的范圍是1到到6，列，列下標的范圍是下標的范圍是0

8、到到7，每個數(shù)組元素用相鄰的，每個數(shù)組元素用相鄰的6個字節(jié)存儲，存?zhèn)€字節(jié)存儲，存儲器按字節(jié)編址。那么，這個數(shù)組的占儲器按字節(jié)編址。那么，這個數(shù)組的占 個字節(jié)。個字節(jié)。 288答：答： Volume=m*n*L=(6-1+1)*(7- 0 +1)*6=48*6=28811例例3 ：考研題考研題 ：設(shè)數(shù)組設(shè)數(shù)組a160, 170的基地址為的基地址為2048，每個元素占，每個元素占2個存儲單元，若以列序為主序順序存儲，個存儲單元，若以列序為主序順序存儲，則元素則元素a32,58的存儲地址為的存儲地址為 。根據(jù)列優(yōu)先公式根據(jù)列優(yōu)先公式 Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*K

9、得：得：LOC(a32,58)=2048+(58-1)*60+(32-1)*28950答：請注意審題！答：請注意審題！想一想：若數(shù)組是想一想：若數(shù)組是a059, 069，結(jié)果是否仍為結(jié)果是否仍為8950？N維數(shù)組任一元素的地址計算維數(shù)組任一元素的地址計算Loc(jLoc(j1 1,j,j2 2, ,j jn n)=LOC(0,0,)=LOC(0,0,0)0)12niii1jC其中其中Cn=L, Ci-1=biCi， 1in每個元素長度每個元素長度數(shù)組基址數(shù)組基址前面若干元素占用前面若干元素占用的地址字節(jié)總數(shù)的地址字節(jié)總數(shù)第第i i維長度維長度與所存元素個數(shù)有關(guān)的系數(shù)，與所存元素個數(shù)有關(guān)的系數(shù)，

10、可用遞推法求出可用遞推法求出低維低維優(yōu)先的地址計算公式：優(yōu)先的地址計算公式：三維數(shù)組且列優(yōu)先時的元素地址三維數(shù)組且列優(yōu)先時的元素地址要會計算！要會計算！13例例4：【考研資格考試考研資格考試】假設(shè)有三維數(shù)組假設(shè)有三維數(shù)組A798，每個元素，每個元素用相鄰的用相鄰的6個字節(jié)存儲，存儲器按字節(jié)編址。已知個字節(jié)存儲，存儲器按字節(jié)編址。已知A的起始存的起始存儲位置（基地址）為儲位置（基地址）為1000，元素，元素A536的第一個字節(jié)地址的第一個字節(jié)地址為多少？為多少？答：答： 元素元素A536的第的第1個字節(jié)地址個字節(jié)地址 1000 +（5*9*8+3*8+6)*6=3448 二、二、N維數(shù)組的順序存

11、儲表示維數(shù)組的順序存儲表示14#define MAX_ARRAY_DIM 8 /假設(shè)最大維數(shù)為假設(shè)最大維數(shù)為8 8 typedef struct ElemType *base; /數(shù)組元素基址數(shù)組元素基址 int dim; /數(shù)組維數(shù)數(shù)組維數(shù) int *bound; /數(shù)組數(shù)組各維長度信息保存區(qū)各維長度信息保存區(qū)基址基址 int *constants ; /數(shù)組數(shù)組映像函數(shù)常量映像函數(shù)常量的基址的基址 Array;即即Ci信息保存區(qū)信息保存區(qū)數(shù)組的基本操作函數(shù)說明（有數(shù)組的基本操作函數(shù)說明（有5個）個）（請閱讀教材（請閱讀教材P93-95P93-95） !數(shù)組的定義數(shù)組的定義數(shù)組的順序表示和實

12、現(xiàn)數(shù)組的順序表示和實現(xiàn)矩陣的壓縮存儲矩陣的壓縮存儲 第五章第五章 數(shù)組和廣義表數(shù)組和廣義表廣義表的定義廣義表的定義廣義表的存儲結(jié)構(gòu)廣義表的存儲結(jié)構(gòu)一、對稱矩陣壓縮一、對稱矩陣壓縮對稱矩陣對稱矩陣v定義：定義：若一個若一個n階方陣階方陣A中元素滿足下列條件：中元素滿足下列條件：aij=aji 其中其中 0 i, jn-1 ， 則稱則稱A為對稱矩陣。為對稱矩陣。1 12 9 0 12 0 5 11 9 5 7 32 0 11 32 4 A=v壓縮存儲原則：對稱的兩個元素可以共用一個存壓縮存儲原則：對稱的兩個元素可以共用一個存儲單元，只需存放主對角線及主對角線以下的元儲單元，只需存放主對角線及主對角

13、線以下的元素，這樣僅需素，這樣僅需 n(n+1)/2個存貯單元，將近節(jié)約一個存貯單元，將近節(jié)約一半存貯單元。半存貯單元。S012345678911209570113241 12 9 0 12 0 5 11 9 5 7 32 0 11 32 4 A=vS與與A的對應(yīng)關(guān)系如下：的對應(yīng)關(guān)系如下：jiijjjijiik當當2) 1(2) 1(二、下（上）三角矩陣壓縮二、下（上）三角矩陣壓縮下（上）三角稱矩陣下（上）三角稱矩陣v定義：定義：矩陣下（上）三角部分元素是隨機的，而上（下）矩陣下（上）三角部分元素是隨機的，而上（下）三角部分元素全部相同（為某常數(shù)三角部分元素全部相同（為某常數(shù)C）或全為）或全為

14、0。1 0 0 0 12 0 0 09 5 7 0 0 11 32 4 A=v壓縮存儲原則：下三角矩陣的壓縮存放與對稱矩壓縮存儲原則：下三角矩陣的壓縮存放與對稱矩陣存放類似，但必須多一個存儲單元存放上三角陣存放類似，但必須多一個存儲單元存放上三角部分元素，使用的存儲單元數(shù)目為部分元素，使用的存儲單元數(shù)目為n(n+1)/2+1。S11209570113240123456789101 0 0 0 12 0 0 09 5 7 0 0 11 32 4 A=0vS與與A的對應(yīng)關(guān)系如下：的對應(yīng)關(guān)系如下：jinnjijiik當當2) 1(2) 1(思考一下：上三思考一下：上三角矩陣角矩陣A壓縮到壓縮到S后的

15、對應(yīng)關(guān)系后的對應(yīng)關(guān)系如何？如何？三、對角矩陣壓縮三、對角矩陣壓縮對角矩陣對角矩陣v定義：若矩陣中所有非零元素都集中在以主對角線為中定義：若矩陣中所有非零元素都集中在以主對角線為中心的帶狀區(qū)域中，區(qū)域外的值全為心的帶狀區(qū)域中，區(qū)域外的值全為0，則稱為對角矩陣。，則稱為對角矩陣。常見的有三對角矩陣、五對角矩陣、七對角矩陣等。常見的有三對角矩陣、五對角矩陣、七對角矩陣等。1 11 0 0 0 12 0 5 0 00 5 7 6 0 0 0 32 4 2 A=0 0 0 4 3 v壓縮存儲原則：在一個壓縮存儲原則：在一個nn的三對角矩陣中，只的三對角矩陣中，只有有n+n-1+n-1個非零元素，故只需個

16、非零元素，故只需3n-2個存儲單元個存儲單元即可，零元已不占用存儲單元。故可將即可，零元已不占用存儲單元。故可將nn三對角三對角矩陣矩陣A壓縮存放到只有壓縮存放到只有3n-2個存儲單元的個存儲單元的s向量中。向量中。四、稀疏矩陣壓縮存儲四、稀疏矩陣壓縮存儲稀疏矩陣稀疏矩陣v定義：非零元較零元少，且分布沒有一定規(guī)律的矩陣定義：非零元較零元少，且分布沒有一定規(guī)律的矩陣0 12 9 0 0 00 0 0 0 0 0 -3 0 0 0 14 00 0 24 0 0 0 0 18 0 0 0 0 0 12 9 0 0 00 0 0 0 0 0 -3 0 0 0 14 00 0 24 0 0 0 0 18

17、 0 0 0 0 ije121213931-3351443245218v壓縮存儲原則：只存儲非零元。壓縮存儲原則：只存儲非零元。需要一個一維數(shù)組存放每一個非零元素，需要一個一維數(shù)組存放每一個非零元素，并記錄每個非零元素的行號、列標、元素并記錄每個非零元素的行號、列標、元素值。（也要求按行（列）優(yōu)先存儲）值。（也要求按行（列）優(yōu)先存儲）0 12 9 0 0 0 00 0 0 0 0 0 0 -3 0 0 0 14 0 00 0 24 0 0 0 0 0 18 0 0 0 0 00 0 0 0 0 0 0問題：問題：下面這個矩陣與上頁的矩陣是否一樣，壓下面這個矩陣與上頁的矩陣是否一樣，壓縮存儲后得

18、到的一維組數(shù)值是否一樣？縮存儲后得到的一維組數(shù)值是否一樣？所以，壓縮后除了存儲所以，壓縮后除了存儲非零元素外，還需要存非零元素外，還需要存儲原矩陣的行號和列標。儲原矩陣的行號和列標。#define MAXSIZE 100typedef struct int i, j; Elemtype e; Triple;類型定義：類型定義：Typedef struct Triple dataMAXESIZE; /存放非零元素存放非零元素 int mu,nu; /存放對應(yīng)矩陣的行號、列標存放對應(yīng)矩陣的行號、列標 int tu; /記錄非零元素的個數(shù)記錄非零元素的個數(shù)TSMatrix;舉例：稀疏矩陣的舉例：稀疏

19、矩陣的轉(zhuǎn)置運算轉(zhuǎn)置運算280 12 9 0 0 00 0 0 0 0 0-3 0 0 0 14 00 0 24 0 0 00 18 0 0 0 00 0 3 0 012 0 0 0 18 9 0 0 24 0 0 0 0 0 00 0 14 0 0 0 0 0 0 0 13-32112251831934245314已知已知三三元元組組表表M.data求求三三元元組組表表T.data轉(zhuǎn)置轉(zhuǎn)置MT目的：目的：121213931-3351443245218Tij=Mji？若采用三元組壓縮技術(shù)存儲稀疏矩陣，只要把每若采用三元組壓縮技術(shù)存儲稀疏矩陣，只要把每個元素的個元素的行下標和列下標互換行下標和列下

20、標互換，就完成了對該矩，就完成了對該矩陣的轉(zhuǎn)置運算，這種說法正確嗎？陣的轉(zhuǎn)置運算，這種說法正確嗎？ 提問：提問：121213931-3351443245218211231913-353143424251813-32112251831934245314ijij互換互換答：答：肯定不正確！肯定不正確！i j e i j e i j e （1 1）每個元素的行下標和列下標互換（即三元組中的）每個元素的行下標和列下標互換（即三元組中的i i和和j j互換互換）；）；（2 2）T T的總行數(shù)的總行數(shù)mumu和總列數(shù)和總列數(shù)nunu也要也要互換；互換；（3 3）重排重排三元組內(nèi)各元素順序三元組內(nèi)各元素順序

21、，使轉(zhuǎn)置后的三元組也按行，使轉(zhuǎn)置后的三元組也按行（或列）為主序有規(guī)律的排列。（或列）為主序有規(guī)律的排列。上述（上述（1 1）和（）和（2 2）容易實現(xiàn)，難點在）容易實現(xiàn)，難點在（3 3）。轉(zhuǎn)置運算的主要三個操作：轉(zhuǎn)置運算的主要三個操作：有兩種實現(xiàn)有兩種實現(xiàn)轉(zhuǎn)置的方法轉(zhuǎn)置的方法壓縮轉(zhuǎn)置壓縮轉(zhuǎn)置快速快速( (壓縮壓縮) )轉(zhuǎn)置轉(zhuǎn)置T.data.i=M.data.j;T.data.j=M.data.i;T.data.e=M.data.e;T.mu=M.nu;T.nu=M.mu;已知已知三三元元組組表表M.data求求三三元元組組表表T.data121213931-3351443245218i j e

22、 q1234 p1234方法方法1 1：壓縮轉(zhuǎn)置壓縮轉(zhuǎn)置思路：思路：反復(fù)掃描反復(fù)掃描M M表表（記為（記為M.dataM.data）中的中的列序列序（j=1j=1n n），），依次進行轉(zhuǎn)置存儲到依次進行轉(zhuǎn)置存儲到T T表中。表中。 1 3 -3 2 1 12 2 5 18 3 1 9 5 3 14 3 4 24i j e q=1; for(col=1;col=M.nu;col+) for(p=1;p=M.tu;p+) if(M.datap.j=col) T.dataq.i=M.datap.j; T.dataq.j=M.datap.i; T.dataq.e=M.datap.e; q+; 算法中主

23、要程序段：算法中主要程序段：方法方法2 2 快速轉(zhuǎn)置快速轉(zhuǎn)置思路：思路：依次依次把把M.dataM.data中的元素直接送入中的元素直接送入T.dataT.data的恰的恰當位置上（當位置上（即三元組的即三元組的p p指針不回溯指針不回溯）。）。關(guān)鍵：關(guān)鍵：怎樣尋找怎樣尋找T.dataT.data的的“恰當恰當”位置？位置？求求三三元元組組表表T.data121213931-3351443245218i j e q1234 p1234 3 1 9 2 1 12 1 3 -3 5 3 14 3 4 24 2 5 18已知已知三三元元組組表表M.datai j e 如果能如果能預(yù)知預(yù)知M矩陣矩陣每

24、一列每一列( (即即T的每一行的每一行) )的的非零元素個數(shù)非零元素個數(shù)，就能很快得知每，就能很快得知每一列的第一一列的第一個非零元素個非零元素在在T.dataT.data中的中的位置位置，則掃描，則掃描M.data時便可以將每個元素準確定位時便可以將每個元素準確定位解決思路：解決思路：1 1）先確定先確定M M中每一列第一個非零元在中每一列第一個非零元在T T中位置中位置 實現(xiàn)：設(shè)兩個數(shù)組實現(xiàn)：設(shè)兩個數(shù)組 cpotcol: cpotcol:指示指示M M中第中第colcol列第一個非零元在列第一個非零元在T T 中的位置中的位置 numcol: numcol:表示矩陣表示矩陣M M中第中第c

25、olcol列中非零元個數(shù)列中非零元個數(shù)設(shè)計步驟：設(shè)計步驟：col123456numcol122010cpotcol1121213931-3351443245218i j e 已知已知三三元元組組表表M.data顯然有：顯然有：cpot1=1;cpotcol=cpotcol-1+numcol-1;24667 /求求numcol: for(p=1;p=M.tu;p+) col=M.datap.j; numcol+; /求求cpotcol cpot1=1; for(col=2;col=M.nu;col+) cpotcol=cpotcol-1+numcol-1; 部分程序段：部分程序段：2 2）再到再

26、到M M中從頭到尾掃描每一個元素，按其列值和中從頭到尾掃描每一個元素，按其列值和cpotcolcpotcol的值存放在的值存放在T T中；中；設(shè)計步驟：設(shè)計步驟：求求三三元元組組表表T.data121213931-3351443245218i j e q1234 p1234 3 1 9 2 1 12 1 3 -3 5 3 14已知已知三三元元組組表表M.datai j e col123456cpotcol12466756求求三三元元組組表表T.data121213931-3351443245218i j e q1234 p1234 3 1 9 2 1 12 1 3 -3 5 3 14已知已知三

27、三元元組組表表M.datai j e col123456cpotcol23567756設(shè)計中一個技巧：每存入一個列為設(shè)計中一個技巧：每存入一個列為colcol的元素，其的元素，其cpotcolcpotcol值值+1+1，使其不再固定指向本列第一個非零使其不再固定指向本列第一個非零元素，而是預(yù)備給同列的元素，而是預(yù)備給同列的下一非零元素定位下一非零元素定位之用之用 3 4 24 2 5 18 1 2 4 6 6 7部分程序段：部分程序段： for(p=1;p=M.tu;p+) col=M.datap.j; q=cpotcol; T.dataq.i=M.datap.j; T.dataq.j=M.d

28、atap.i; T.dataq.e=M.datap.e; cpotcol+; 求該元素在求該元素在T T中的位置中的位置元素轉(zhuǎn)置元素轉(zhuǎn)置技巧應(yīng)用技巧應(yīng)用1. 1. 與常規(guī)算法相比，附加了生成輔助向量表的工作。增開了與常規(guī)算法相比，附加了生成輔助向量表的工作。增開了2 2個長度為列長的數(shù)組個長度為列長的數(shù)組( (num 和和cpos ）。傳統(tǒng)轉(zhuǎn)置：傳統(tǒng)轉(zhuǎn)置：O(muO(mu* *nu) nu) 壓縮轉(zhuǎn)置：壓縮轉(zhuǎn)置：O(muO(mu* *tu) tu) 壓縮快速轉(zhuǎn)置：壓縮快速轉(zhuǎn)置：O(nu+tu)O(nu+tu)2. 2. 從時間上，此算法用了從時間上，此算法用了4 4個并列的單循環(huán)個并列的單循環(huán)

29、，而且其中前，而且其中前3 3個個單循環(huán)都是用來產(chǎn)生輔助向量表的。單循環(huán)都是用來產(chǎn)生輔助向量表的。 該算法的時間復(fù)雜度該算法的時間復(fù)雜度nu+tu+nu+tu=O(nu+tunu+tu+nu+tu=O(nu+tu）討論：最惡劣情況是矩陣中全為非零元素，此時討論：最惡劣情況是矩陣中全為非零元素，此時tu=nutu=nu* *mumu而此時的時間復(fù)雜度也只是而此時的時間復(fù)雜度也只是O(muO(mu* *nu)nu)，并未超過傳統(tǒng)轉(zhuǎn)置算，并未超過傳統(tǒng)轉(zhuǎn)置算法的時間復(fù)雜度。法的時間復(fù)雜度。小結(jié)：小結(jié)：增設(shè)輔助向量，犧牲空間增設(shè)輔助向量，犧牲空間效率換取時間效率。效率換取時間效率?？焖俎D(zhuǎn)置算法的效率分析

30、快速轉(zhuǎn)置算法的效率分析： !數(shù)組的定義數(shù)組的定義數(shù)組的順序表示和實現(xiàn)數(shù)組的順序表示和實現(xiàn)矩陣的壓縮存儲矩陣的壓縮存儲 第五章第五章 數(shù)組和廣義表數(shù)組和廣義表廣義表的定義廣義表的定義廣義表的存儲結(jié)構(gòu)廣義表的存儲結(jié)構(gòu)42廣義表是線性表的推廣，也稱為列表（廣義表是線性表的推廣，也稱為列表（lists）記為：記為： LS = ( a1 , a2 , ， an ) 廣義表名廣義表名 表頭表頭(Head） 表尾表尾 (Tail)1、定義：、定義：用小寫字母表示原子類型，用用小寫字母表示原子類型，用大寫字母大寫字母表示列表。表示列表。第一個元素是第一個元素是表頭表頭，而其余元素組成的表稱為，而其余元素組成的

31、表稱為表尾表尾；n n是表長是表長在廣義表中約定：在廣義表中約定：特別提示：任何一個非空表，表頭特別提示：任何一個非空表，表頭可能是原子，也可能是列表；但可能是原子，也可能是列表；但表表尾一定是列表！尾一定是列表！432、特點：、特點： 有次序性有次序性 有長度有長度 有深度有深度 可遞歸可遞歸 可共享可共享一個直接前驅(qū)和一個直接后繼一個直接前驅(qū)和一個直接后繼表中元素個數(shù)表中元素個數(shù)表中括號的重數(shù)表中括號的重數(shù)自己可以作為自己的子表自己可以作為自己的子表可以為其他廣義表所共享可以為其他廣義表所共享討論：廣義表與線性表的區(qū)別和聯(lián)系？討論：廣義表與線性表的區(qū)別和聯(lián)系？ 廣義表中元素既可以是原子類型

32、，也可以是列表；廣義表中元素既可以是原子類型，也可以是列表；當每個元素都為原子且類型相同時，就是線性表。當每個元素都為原子且類型相同時，就是線性表。44E=(a,E)=(a,(a,E)= (a,(a,(a,.)，E為遞歸表為遞歸表1）A =( )2）B = ( e ) 3）C =( a ,( b , c , d ) ) 4）D=( A , B ,C )5）E=(a, E)例例1：求下列廣義表的長度。求下列廣義表的長度。n=0，因為因為A A是空表是空表n=1，表中元素表中元素e e是原子是原子n=2，a a 為原子，為原子，(b,c,d)(b,c,d)為子表為子表n=3，3 3個元素都是子表個

33、元素都是子表n=2，a a 為原子，為原子，E E為子表為子表D=(A,B,C)=( ),(e),(a,(b,c,d)，共享表，共享表453.3.兩種重要的基本操作：兩種重要的基本操作：GetHead ( L) 取表頭取表頭(可能是原子或列表可能是原子或列表) 初始條件：廣義表初始條件：廣義表L L存在。存在。 操作結(jié)果：取廣義表操作結(jié)果：取廣義表L L的頭。的頭。 GetTail ( L ) 取表尾取表尾(一定是列表一定是列表) 初始條件：廣義表初始條件：廣義表L L存在。存在。 操作結(jié)果：取廣義表操作結(jié)果：取廣義表L L的尾。的尾。461. GetTail【(b, k, p, h)】 ; 2. GetHead【( (a,b), (c,d) )】 ; 3. GetTail【( (a,b), (c,d) )】 ; 4. GetTail【 GetHead【(a,b),(c,d)】 ;例：例：求下列廣義表操作的結(jié)果（嚴題集求下列廣義表操作的結(jié)果