




版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、8.1 8.1 廣義表的定義廣義表的定義第第8 8章章 廣義表廣義表8.2 8.2 廣義表的存儲(chǔ)結(jié)構(gòu)廣義表的存儲(chǔ)結(jié)構(gòu)8.3 8.3 廣義表的運(yùn)算廣義表的運(yùn)算本章小結(jié)本章小結(jié)8.1 8.1 廣義表的定義廣義表的定義 廣義表簡(jiǎn)稱表廣義表簡(jiǎn)稱表,它是線性表的推廣。一個(gè)廣義它是線性表的推廣。一個(gè)廣義表是表是n(n0)個(gè)元素的一個(gè)序列個(gè)元素的一個(gè)序列,若若n=0時(shí)則稱為空時(shí)則稱為空表。設(shè)表。設(shè)ai為廣義表的第為廣義表的第i個(gè)元素個(gè)元素,則廣義表則廣義表GL的一的一般表示與線性表相同:般表示與線性表相同: GL=(a1,a2,ai,an) 其中其中n表示廣義表的長(zhǎng)度表示廣義表的長(zhǎng)度,即廣義表中所含元即廣義
2、表中所含元素的個(gè)數(shù)素的個(gè)數(shù),n0。如果。如果ai是單個(gè)數(shù)據(jù)元素是單個(gè)數(shù)據(jù)元素,則則ai是廣是廣義表義表GL的原子;如果的原子;如果ai是一個(gè)廣義表是一個(gè)廣義表,則則ai是廣義是廣義表表GL的子表。的子表。 廣義表具有如下重要的特性:廣義表具有如下重要的特性: (1)廣義表中的數(shù)據(jù)元素有相對(duì)次序;廣義表中的數(shù)據(jù)元素有相對(duì)次序; (2)廣義表的長(zhǎng)度定義為最外層包含元素個(gè)數(shù);廣義表的長(zhǎng)度定義為最外層包含元素個(gè)數(shù); (3)廣義表的深度定義為所含括弧的重?cái)?shù)。其中廣義表的深度定義為所含括弧的重?cái)?shù)。其中,原原子的深度為子的深度為0,空表的深度為空表的深度為1; (4)廣義表可以共享;一個(gè)廣義表可以為其他廣義
3、廣義表可以共享;一個(gè)廣義表可以為其他廣義表共享;這種共享廣義表稱為再入表;表共享;這種共享廣義表稱為再入表; (5)廣義表可以是一個(gè)遞歸的表。一個(gè)廣義表可以廣義表可以是一個(gè)遞歸的表。一個(gè)廣義表可以是自已的子表。這種廣義表稱為遞歸表。遞歸表的是自已的子表。這種廣義表稱為遞歸表。遞歸表的深度是無(wú)窮值深度是無(wú)窮值,長(zhǎng)度是有限值;長(zhǎng)度是有限值; (6)任何一個(gè)非空廣義表任何一個(gè)非空廣義表GL均可分解為表頭均可分解為表頭head(GL) = a1和表尾和表尾tail(GL) = ( a2,an) 兩部分。兩部分。 為了簡(jiǎn)單起見(jiàn)為了簡(jiǎn)單起見(jiàn),下面討論的廣義表不包括前面定下面討論的廣義表不包括前面定義的再入
4、表和遞歸表義的再入表和遞歸表,即只討論一般的廣義表。另即只討論一般的廣義表。另外外,我們規(guī)定用小寫(xiě)字母表示原子我們規(guī)定用小寫(xiě)字母表示原子,用大寫(xiě)字母表示用大寫(xiě)字母表示廣義表的表名。例如:廣義表的表名。例如: A=() B=(e) C=(a,(b,c,d) D=(A,B,C)=(),(e),(a,(b,c,d) E=(a,(a,b),(a,b),c) 如果把每個(gè)表的名字如果把每個(gè)表的名字(若有的話若有的話)寫(xiě)在其表的前面寫(xiě)在其表的前面,則則上面的上面的5個(gè)廣義表可相應(yīng)地表示如下:個(gè)廣義表可相應(yīng)地表示如下: A() B(e) C(a,(b,c,d) D(A(),B(e),C(a,(b,c,d) E
5、(a,(a,b),(a,b),c) 若用圓圈和方框分別表示表和單元素若用圓圈和方框分別表示表和單元素,并用線段把表并用線段把表和它的元素和它的元素(元素結(jié)點(diǎn)應(yīng)在其表結(jié)點(diǎn)的下方元素結(jié)點(diǎn)應(yīng)在其表結(jié)點(diǎn)的下方)連接起來(lái)連接起來(lái),則則可得到一個(gè)廣義表的圖形表示。例如可得到一個(gè)廣義表的圖形表示。例如,上面五個(gè)廣義表上面五個(gè)廣義表的圖形表示如下圖所示。的圖形表示如下圖所示。 c a b a b E d e a b c D A B C d b c C a B e A a A() B(e) C(a,(b,c,d) D(A(),B(e),C(a,(b,c,d)E(a,(a,b),(a,b),c)8.2 8.2 廣
6、義表的存儲(chǔ)結(jié)構(gòu)廣義表的存儲(chǔ)結(jié)構(gòu) 廣義表是一種遞歸的數(shù)據(jù)結(jié)構(gòu)廣義表是一種遞歸的數(shù)據(jù)結(jié)構(gòu),因此很難為每個(gè)因此很難為每個(gè)廣義表分配固定大小的存儲(chǔ)空間廣義表分配固定大小的存儲(chǔ)空間,所以其存儲(chǔ)結(jié)構(gòu)只所以其存儲(chǔ)結(jié)構(gòu)只好采用動(dòng)態(tài)鏈?zhǔn)浇Y(jié)構(gòu)。好采用動(dòng)態(tài)鏈?zhǔn)浇Y(jié)構(gòu)。 我們將一個(gè)廣義表看成一棵樹(shù)我們將一個(gè)廣義表看成一棵樹(shù),為了方便存儲(chǔ)為了方便存儲(chǔ),將將其轉(zhuǎn)換成一棵二叉樹(shù)。其轉(zhuǎn)換過(guò)程已在第其轉(zhuǎn)換成一棵二叉樹(shù)。其轉(zhuǎn)換過(guò)程已在第6章中介紹章中介紹過(guò)過(guò),這里以示例中的廣義表這里以示例中的廣義表C說(shuō)明其轉(zhuǎn)換過(guò)程。如下說(shuō)明其轉(zhuǎn)換過(guò)程。如下圖所示圖所示,左邊的圖表示轉(zhuǎn)換的中間狀態(tài)左邊的圖表示轉(zhuǎn)換的中間狀態(tài),右邊的圖表示右邊的圖表示
7、轉(zhuǎn)換的最終狀態(tài)轉(zhuǎn)換的最終狀態(tài),即一棵二叉樹(shù)。從二叉樹(shù)中看到即一棵二叉樹(shù)。從二叉樹(shù)中看到,有有兩類(lèi)結(jié)點(diǎn)兩類(lèi)結(jié)點(diǎn),一類(lèi)為圓圈結(jié)點(diǎn)一類(lèi)為圓圈結(jié)點(diǎn),在這里對(duì)應(yīng)子表;另一類(lèi)在這里對(duì)應(yīng)子表;另一類(lèi)為方形結(jié)點(diǎn)為方形結(jié)點(diǎn),在這里對(duì)應(yīng)原子。在這里對(duì)應(yīng)原子。 C a b c d C a b c d C 1 0 a 1 0 b 0 c 0 d 廣義表的存儲(chǔ)結(jié)構(gòu)廣義表的存儲(chǔ)結(jié)構(gòu) typedef struct lnode int tag; /*結(jié)點(diǎn)類(lèi)型標(biāo)識(shí)結(jié)點(diǎn)類(lèi)型標(biāo)識(shí)*/ union ElemType data; struct lnode *sublist; val; struct lnode *link;/*指向下一
8、個(gè)元素指向下一個(gè)元素*/ GLNode;/*廣義表結(jié)點(diǎn)類(lèi)型定義廣義表結(jié)點(diǎn)類(lèi)型定義*/廣義表的兩種基本情況廣義表的兩種基本情況 : g1 1 g2 1 * * * * * * 第 1 個(gè)元素 第 2 個(gè)元素 第 n 個(gè)元素 (a)空表 (b)非空表 為原子的情況為原子的情況 : g3 0 a 8.3 8.3 廣義表的運(yùn)算廣義表的運(yùn)算1. 求廣義表的長(zhǎng)度求廣義表的長(zhǎng)度 在廣義表中在廣義表中,同一層次的每個(gè)結(jié)點(diǎn)是通過(guò)同一層次的每個(gè)結(jié)點(diǎn)是通過(guò)link域鏈域鏈接起來(lái)的接起來(lái)的,所以可把它看做是由所以可把它看做是由link域鏈接起來(lái)的單域鏈接起來(lái)的單鏈表。這樣鏈表。這樣,求廣義表的長(zhǎng)度就是求單鏈表的長(zhǎng)度求
9、廣義表的長(zhǎng)度就是求單鏈表的長(zhǎng)度,可可以采用以前介紹過(guò)的求單鏈表長(zhǎng)度的方法求其長(zhǎng)度。以采用以前介紹過(guò)的求單鏈表長(zhǎng)度的方法求其長(zhǎng)度。求廣義表長(zhǎng)度的非遞歸算法如下:求廣義表長(zhǎng)度的非遞歸算法如下: int GLLength(GLNode *g) /*g為一個(gè)廣義表頭結(jié)點(diǎn)的指針為一個(gè)廣義表頭結(jié)點(diǎn)的指針*/ int n=0; g=g-val.sublist;/*g指向廣義表的第一個(gè)元素指向廣義表的第一個(gè)元素*/ while (g!=NULL) n+; g=g-link; return n; 2. 求廣義表的深度求廣義表的深度 對(duì)于帶頭結(jié)點(diǎn)的廣義表對(duì)于帶頭結(jié)點(diǎn)的廣義表g,廣義表深度的遞歸定義廣義表深度的遞歸
10、定義是它等于所有子表中表的最大深度加是它等于所有子表中表的最大深度加1。若。若g為原子為原子,其深度為其深度為0。 求廣義表深度的遞歸模型求廣義表深度的遞歸模型f()如下:如下:f(g)= 0 若若g為原子為原子 1 若若g為空表為空表MAXf(subg)+1 其他情況其他情況,subg為為g的子表的子表 int GLDepth(GLNode *g) /*求帶頭結(jié)點(diǎn)的廣義表求帶頭結(jié)點(diǎn)的廣義表g的深度的深度*/ int max=0,dep; if (g-tag=0) return 0; /*為原子時(shí)返回為原子時(shí)返回0*/ g=g-val.sublist; /*g指向第一個(gè)元素指向第一個(gè)元素*/
11、if (g=NULL) return 1; /*為空表時(shí)返回為空表時(shí)返回1*/ while (g!=NULL) /*遍歷表中的每一個(gè)元素遍歷表中的每一個(gè)元素*/ if (g-tag=1) /*元素為子表的情況元素為子表的情況*/ dep=GLDepth(g); /*遞歸調(diào)用求出子表的深度遞歸調(diào)用求出子表的深度*/ if (depmax) max=dep; /*max為同一層所求過(guò)的子表中深度的最大值為同一層所求過(guò)的子表中深度的最大值*/ g=g-link; /*使使g指向下一個(gè)元素指向下一個(gè)元素*/ return(max+1); /*返回表的深度返回表的深度*/3. 建立廣義表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)建
12、立廣義表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 假定廣義表中的元素類(lèi)型假定廣義表中的元素類(lèi)型ElemType為為char類(lèi)型類(lèi)型,每每個(gè)原子的值被限定為英文字母。個(gè)原子的值被限定為英文字母。 并假定廣義表是一個(gè)表達(dá)式并假定廣義表是一個(gè)表達(dá)式,其格式為:元素之間用其格式為:元素之間用一個(gè)逗號(hào)分隔一個(gè)逗號(hào)分隔,表元素的起止符號(hào)分別為左、右圓括號(hào)表元素的起止符號(hào)分別為左、右圓括號(hào),空表在其圓括號(hào)內(nèi)不包含任何字符。例如空表在其圓括號(hào)內(nèi)不包含任何字符。例如“(a,(b,c,d)”就是一個(gè)符合上述規(guī)定的廣義表格式。就是一個(gè)符合上述規(guī)定的廣義表格式。 生成廣義表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的算法如下:生成廣義表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的算法如下:GLNode
13、 *CreatGL(char *&s) GLNode *h;char ch=*s+; /*取一個(gè)掃描字符取一個(gè)掃描字符*/ if (ch!=0) /*串未結(jié)束判斷串未結(jié)束判斷*/ h=(GLNode *)malloc(sizeof(GLNode);/*創(chuàng)建新結(jié)點(diǎn)創(chuàng)建新結(jié)點(diǎn)*/ if (ch=() /*當(dāng)前字符為左括號(hào)時(shí)當(dāng)前字符為左括號(hào)時(shí)*/ h-tag=1; /*新結(jié)點(diǎn)作為表頭結(jié)點(diǎn)新結(jié)點(diǎn)作為表頭結(jié)點(diǎn)*/ h-val.sublist=CreatGL(s); /*遞歸構(gòu)造子表并鏈到表頭結(jié)點(diǎn)遞歸構(gòu)造子表并鏈到表頭結(jié)點(diǎn)*/ else if (ch=) h=NULL; /*遇到遇到)字符字符,子
14、表為空子表為空*/ else h-tag=0; /*新結(jié)點(diǎn)作為原子結(jié)點(diǎn)新結(jié)點(diǎn)作為原子結(jié)點(diǎn)*/ h-val.data=ch; else h=NULL; /*串結(jié)束串結(jié)束,子表為空子表為空*/ ch=*s+; /*取下一個(gè)掃描字符取下一個(gè)掃描字符*/ if (h!=NULL) /*串未結(jié)束判斷串未結(jié)束判斷*/ if (ch=,) /*當(dāng)前字符為當(dāng)前字符為,*/ h-link=CreatGL(s); /*遞歸構(gòu)造后續(xù)子表遞歸構(gòu)造后續(xù)子表*/ else /*串結(jié)束串結(jié)束*/ h-link=NULL; /*處理表的最后一個(gè)元素處理表的最后一個(gè)元素*/ return h; /*返回廣義表指針?lè)祷貜V義表指針
15、*/ 4. 輸出廣義表輸出廣義表 以以h作為帶表頭附加結(jié)點(diǎn)的廣義表的表頭指針作為帶表頭附加結(jié)點(diǎn)的廣義表的表頭指針,打印輸打印輸出該廣義表時(shí)出該廣義表時(shí),需要對(duì)子表進(jìn)行遞歸調(diào)用。輸出一個(gè)廣義需要對(duì)子表進(jìn)行遞歸調(diào)用。輸出一個(gè)廣義表的算法如下:表的算法如下:void DispGL(GLNode *g) /*g為一個(gè)廣義表的頭結(jié)點(diǎn)指針為一個(gè)廣義表的頭結(jié)點(diǎn)指針*/ if (g!=NULL) /*表不為空判斷表不為空判斷*/ if (g-tag=1) /*為表結(jié)點(diǎn)時(shí)為表結(jié)點(diǎn)時(shí)*/ printf(); /*輸出輸出(*/ if (g-val.sublist=NULL) printf(); /*輸出空子表輸出空子表*/ else DispGL(g-val.sublist); /*遞歸輸出子表遞歸輸出子表*/ else printf(%c, g-val.data); /*為原子時(shí)輸出元素值為原子時(shí)輸出元素值*/ if (g-tag=1) printf(); /*為表結(jié)點(diǎn)時(shí)輸出為表結(jié)點(diǎn)時(shí)輸出)*/ if (g-link!=NULL) printf(,); DispGL(g-link); /*遞歸輸出后續(xù)表的內(nèi)容遞歸輸出后續(xù)
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 步行街個(gè)人店鋪?zhàn)赓U合同書(shū)
- 區(qū)商貿(mào)城商鋪?zhàn)赓U合同
- 健身場(chǎng)地租賃合同
- 農(nóng)副產(chǎn)品購(gòu)銷(xiāo)合同
- 土地租賃建房合同
- 借款抵押擔(dān)保合同
- 停車(chē)位代理銷(xiāo)售合同
- 知識(shí)產(chǎn)權(quán)專項(xiàng)法律服務(wù)合同
- 焦作師范高等??茖W(xué)校《高爾夫球具維護(hù)》2023-2024學(xué)年第二學(xué)期期末試卷
- 長(zhǎng)沙航空職業(yè)技術(shù)學(xué)院《廣播電視技術(shù)實(shí)務(wù)》2023-2024學(xué)年第二學(xué)期期末試卷
- 產(chǎn)品不良品(PPM)統(tǒng)計(jì)表格模板
- 品管圈PDCA提高手衛(wèi)生依從性-手衛(wèi)生依從性品
- 2023年廣州市青年教師初中數(shù)學(xué)解題比賽決賽試卷
- 對(duì)折剪紙課件
- 公園棧道棧橋施工方案
- 新中國(guó)成立后的中國(guó)國(guó)防
- 熱烈歡迎領(lǐng)導(dǎo)蒞臨指導(dǎo)ppt模板
- 不規(guī)則抗體篩查與鑒定
- 2023-2024人教版小學(xué)2二年級(jí)數(shù)學(xué)下冊(cè)(全冊(cè))教案【新教材】
- 中國(guó)銀行海爾多聯(lián)機(jī)方案書(shū)
- 小學(xué)《體育與健康》體育基礎(chǔ)理論知識(shí)
評(píng)論
0/150
提交評(píng)論