【正文】 點(diǎn)的后繼數(shù)據(jù)域 。 若本結(jié)點(diǎn)為子表 ， 則返回空 。 ? SetVal(char *pe)：為本元素結(jié)點(diǎn)設(shè)置內(nèi)容 。若本結(jié)點(diǎn)不是子表 ， 則返回空 。 ? GetParent()：返回本結(jié)點(diǎn)所直屬的子表的頭結(jié)點(diǎn)的地址 。 A 上面這些操作 ， 我們?cè)?TGListNode的父類中沒有定義 ，這是為了簡(jiǎn)化問題 。 圖 80 帶總頭結(jié)點(diǎn)的廣義表分枝單鏈表 d 0 1 ^ 0 0 0 ^ b c 1 ^ head a 167。 主要不同之處 ，是在類中設(shè)立一個(gè)指向廣義表頭結(jié)點(diǎn)的指針 head。 class TGList: public TGList0TElem { TGListNode *head。 }。 167。 167。 不涉及元素內(nèi)部結(jié)構(gòu)的操作主要是我們?cè)赥GList0 中 定 義 的 操 作 ， 如InsertNode()、 DeleteNode()等 。 對(duì)這類涉及整個(gè)表或元素內(nèi)部結(jié)構(gòu)的操作的實(shí)現(xiàn)，有一個(gè)重要問題需注意：循環(huán)問題。 在存儲(chǔ)結(jié)構(gòu)中 ， 這種情況表現(xiàn)為：從某個(gè)結(jié)點(diǎn)出發(fā) ， 順著某條鏈路 ， 可以返回到自己位置 。 解決的方法是為每個(gè)結(jié)點(diǎn)設(shè)立一個(gè)訪問標(biāo)志 ， 每訪問一個(gè)結(jié)點(diǎn) ， 就將其訪問標(biāo)志置為 “ 已訪問 ” 。 有兩種方法： a) 設(shè)立一個(gè)線性結(jié)構(gòu) （ 一維數(shù)組 ， 稱為已訪問數(shù)組 ） ， 使每個(gè)元素對(duì)應(yīng)一個(gè)廣義表元素 （ 結(jié)點(diǎn) ） ， 其值表示是否已訪問 。 b) 在廣義表結(jié)點(diǎn)中增設(shè)一個(gè) “ 已訪問 ” 標(biāo)志位 。 可以在建立廣義表結(jié)構(gòu)（ 或插入新結(jié)點(diǎn) ） 時(shí) ， 將結(jié)點(diǎn)的 “ 已訪問 ” 標(biāo)志置為 “ 未訪問 ” ， 但是 ， 當(dāng)要重新初始化為 “ 未訪問 ” 時(shí) ， 問題就沒那么容易了 ， 因?yàn)?，此時(shí)的初始化已相當(dāng)于廣義表的遍歷 ！ 由于廣義表是遞歸結(jié)構(gòu)，所以相關(guān)算法采用遞歸法實(shí)現(xiàn)比較方便。 遍歷操作 下面以深度優(yōu)先遍歷操作說明廣義表的遍歷的實(shí)現(xiàn) 。 廣義表的深度優(yōu)先遍歷的含義與圖或樹的深度優(yōu)先遍歷類似。 i=n。 為 Ai置已訪問標(biāo)志； } else PreTraversal(Ai)。 long TGList::Cluster(TGListNode *pH, char **pE, long amp。 if (pH==NULL) return 0。 while (q!=NULL) { if (qvisited==0) //若 q未被訪問 { qvisited = 1。 else Cluster(qpSub, pE, k)。 } //while return k。 SetVisitTag(pH,0)。 } 167。 ? 廣義表的深度定義為它的各直接結(jié)點(diǎn)中深度最大者的深度值加 1。該問題的解決 ， 實(shí)質(zhì)上類似于遍歷問題 ， 下面是具體的程序 。 long dep, dep0。 dep=0。//令 q指向廣義表 pH的第一個(gè)元素結(jié)點(diǎn) while (q!=NULL) //依次求出 pH的各直接元素結(jié)點(diǎn)的深度 { if (qtag==0) dep0=0。 //求出以 q為總頭結(jié)點(diǎn)的廣義表 （ 即 q對(duì)應(yīng)的子表 ） 的深度 if (dep dep0) dep =dep0。 //令 q指向 pH的下個(gè)直接元素結(jié)點(diǎn) } //while return dep+1。 廣義表的串行 化與逆串行化 廣義表的串行化是指根據(jù)廣義表 （ 內(nèi)存 ） 結(jié)構(gòu) ， 輸出對(duì)應(yīng)的廣義表表達(dá)式 。 這里我們只介紹逆串行化 ， 即根據(jù)廣義表表達(dá)式 ， 創(chuàng)建 （ 內(nèi)存結(jié)構(gòu) ）廣義表 。為了簡(jiǎn)化問題，突出主題，我們這里規(guī)定，廣義表表達(dá)式中，每個(gè)成分是一個(gè)字符，各成分間沒有間隔（空格），廣義表名字用大寫字母，單元素用小寫字母。在實(shí)際使用中，一般需對(duì)表達(dá)式進(jìn)行預(yù)處理，使其符合這里的假設(shè)。 首先 ， 我們采用從左到右依次讀取表達(dá)式中每個(gè)成分 （ 符號(hào) ） 的方式 。 每創(chuàng)建一個(gè)結(jié)點(diǎn) ， 就需要將它鏈到相應(yīng)的單鏈表中 (next鏈 ， 鏈接同層中各結(jié)點(diǎn) )， 此外 ， 若創(chuàng)建的結(jié)點(diǎn)是某子表中第一個(gè)結(jié)點(diǎn) ，則還要令該子表的頭結(jié)點(diǎn)的 pSub指向它 。 顯然 ， 記錄的次序和訪問次序相反 ， 所以應(yīng)該使用棧來記錄 ， 即每創(chuàng)建一個(gè)結(jié)點(diǎn) ， 就將其壓入棧中 。此時(shí)，最前面結(jié)點(diǎn)就在棧頂，所以可以直接出棧。 下面是具體的程序 。 //在 gListExpr中 ， 假定結(jié)點(diǎn)用單個(gè)英文字母表示 ， 各符號(hào)間也不留空 ， 表達(dá)式中無語法錯(cuò)誤 //返回所創(chuàng)建的廣義表的頭結(jié)點(diǎn)指針 long k, top。 char firstList。 //表達(dá)式中成分?jǐn)?shù)目不足 4時(shí) ， 認(rèn)為是空表 if (gListExpr[0]39。 || gListExpr[0]39。 || gListExpr[1]!=39。) return NULL。 //申請(qǐng)?？臻g top=0。 h=new TGListNode。 hname[0]=gListExpr[k]。 hvisited = 0。 top++。 //總頭結(jié)點(diǎn)進(jìn)棧 k++。//firstList為 最左結(jié)點(diǎn) 標(biāo)志 ,值為 1時(shí) , 表示表達(dá)式中上個(gè)符號(hào)是左括號(hào) , //當(dāng)前的成分為某表 L的最左結(jié)點(diǎn) ,則 L的 pSub應(yīng)該指向該結(jié)點(diǎn) while (top0 amp。 kn1) { k++。,39。)39。 top。 break。(39。 continue。 pvisited = 0。 if (gListExpr[k]=‘A’ amp。 gListExpr[k]=‘Z’) //規(guī)定子子表名為大寫字母 { ptag=1。pname[1]=0。 pname[0]=gListExpr[k]。 } //如果當(dāng)前創(chuàng)建的結(jié)點(diǎn)是所屬表中第一個(gè)結(jié)點(diǎn) ,則建立子表關(guān)系 ,即令最近生成的結(jié)點(diǎn)的 pSub指向它 if (firstList) s[top]pSub=p。//建立 next鏈 ,pre為當(dāng)前生成的結(jié)點(diǎn)的左兄弟的指針 top++。 //新生成的結(jié)點(diǎn)進(jìn)棧 firstList=0。 head=h。//返回所創(chuàng)建的表的頭結(jié)點(diǎn) . }// 167。該過程的實(shí)現(xiàn)，實(shí)質(zhì)上也是一種深度優(yōu)先遍歷。 TGListNode0 *TGList::Copy(TGListNode0 *pH, long amp。 if (pH==NULL) return 0。 q = (TGListNode *)pH。 p=new TGListNode。 pno=qno。 pnext=NULL。 if (pRear!=NULL) pRearnext= p。 pRear=p。 //置 q已訪問標(biāo)志； if (qtag==0) ppElem=qpElem。 //復(fù)制 p的子表 } q = qnext。 } 在該程序的支持下 ， 可方便實(shí)現(xiàn)求尾操作： TGListNode0 *TGList::GetTail(TGListNode0 *pNode) {//返回以 pNode為頭結(jié)點(diǎn)的表 （ 即 pNode對(duì)應(yīng)的子表 ） 的尾 （ 一個(gè)新表 ） 的頭結(jié)點(diǎn)指針 TGListNode *p,*q。 if (pNode==NULL || pNodetag==0 || ((TGListNode *)pNode)pSubnext==NULL) return NULL。 //復(fù)制以 pNode為頭結(jié)點(diǎn)的表 ， 新表的頭結(jié)點(diǎn)指針為 p q=ppSub。 delete q。 } 167。 167。一種直觀的數(shù)據(jù)結(jié)構(gòu)是仿照一元多項(xiàng)式的結(jié)構(gòu)，即令多項(xiàng)式每項(xiàng)對(duì)應(yīng)一個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)應(yīng)含一個(gè)系數(shù)域和 m個(gè)（ m為變?cè)獋€(gè)數(shù)）指數(shù)域。這種情況最適合使用廣義表結(jié)構(gòu) 。 11111111 ...)...(eenenmm xAxAxAxxpnn ???? ?? 例如 ， 對(duì)前面給出的 P3(x1,x2,x3)處理如下： P(x1,x2, x3) =x15x23x3+2x15x22x34+5x15x23x33+3x1x24x32+x2x3+100 = (x23x3+2x22x34+5x23x33) x15 + (3x24x32) x1 + (x2x3+100) =( (5x33+ x3) x23+(2x34) x22) x15 + (3x24x32) x1 + (x2x3+100) 將上式中每一項(xiàng)用一個(gè)如下形式的二元組表示： （ 系數(shù) ， 指數(shù) ） 其中， “ 系數(shù) ” 可能是一個(gè)多元多項(xiàng)式，也可能是基本元素。 167。 因此 ， 總可以用廣義表表示任意 n叉樹 。 我們?nèi)砸运鼮槔f明 （ 將它的圖重列于圖 80） 。 顯然 ， 這是個(gè)遞歸定義 。 顯然 ， 若容許層次結(jié)構(gòu)含循環(huán) （ 準(zhǔn)層次結(jié)構(gòu) ） ， 則它的廣義表表示法仍可按上面的定義 。 此外 ， 廣義表的元素也很特別 ， 每個(gè)元素的結(jié)構(gòu)都可能不同 ， 而且也可以是廣義表 。 在其他數(shù)據(jù)結(jié)構(gòu)中 ， 一般不把復(fù)合元素看作元素 ，例如 ， 在樹中 ， 子樹本來也是復(fù)合元素 ， 但一般不認(rèn)為是樹中的元素 。 如果結(jié)合表的聯(lián)合運(yùn)算 (∪ )， 就可以實(shí)現(xiàn)對(duì)表的重組和加工 ， 所以 ， 這兩種操作往往被做為廣義表的標(biāo)準(zhǔn)操作 。 它兼有線性表 、 樹 、 圖的特點(diǎn) ， 所以照顧這方方面面很困難 。 ? 廣義表的存儲(chǔ)結(jié)構(gòu)是復(fù)雜的 ， 一般都采用鏈?zhǔn)浇Y(jié)構(gòu) 。 習(xí) 題 1. 對(duì)下列廣義表系列，分別求出它們的長(zhǎng)度、深度、頭、尾，并畫出存貯結(jié)構(gòu)圖（同名元素或表共享，小寫字母為單元素） ① A=((a,b), (a,c)) ② c=((A,a), (b,c)) ③ D=((a, (b,a)), A) ④ E=(E, a, b) GetHead()和 GetTail()操作，將下列各表中的 apple分離出來。 4. 給出一個(gè) 3元多項(xiàng)式P(x1,x2,x3)=10x15x22x3+2x15x2x3+3x15+x12x22x3+x12x2x3+x22x3+10 寫出它的廣義表表達(dá)式（邏輯表示），并畫出相應(yīng)的分枝單鏈表存貯結(jié)構(gòu)圖。 6．編寫程序，求廣義表中任一指定結(jié)點(diǎn)的層號(hào)（結(jié)點(diǎn)的深度）。 8. 編寫程序，實(shí)現(xiàn)操作： long Locate(char *pE, TGListNode0 **pNodes,TTraverseMode tm=PreOrder)=