【正文】 ， 可以包含自己 （ 以自己為元素 ） 。 在存儲結(jié)構(gòu)中 ， 這種情況表現(xiàn)為：從某個結(jié)點出發(fā) ， 順著某條鏈路 ， 可以返回到自己位置 。 這樣 ， 處理廣義表時 ， 若不知道遞歸元素是否已被處理 ， 就可能導(dǎo)致無限循環(huán) 。 解決的方法是為每個結(jié)點設(shè)立一個訪問標(biāo)志 ， 每訪問一個結(jié)點 ， 就將其訪問標(biāo)志置為 “ 已訪問 ” 。 這種處理方法又存在一個問題 ， 就是訪問標(biāo)志如何設(shè)置 。 有兩種方法： a) 設(shè)立一個線性結(jié)構(gòu) （ 一維數(shù)組 ， 稱為已訪問數(shù)組 ） ， 使每個元素對應(yīng)一個廣義表元素 （ 結(jié)點 ） ， 其值表示是否已訪問 。 這種方法容易進(jìn)行初始化 （ 將所有元素都置為 “ 未訪問 ” ） ， 但不易按元素標(biāo)識定位 （ 已知元素標(biāo)識 ， 訪問對應(yīng)的已訪問數(shù)組元素值 ） 。 b) 在廣義表結(jié)點中增設(shè)一個 “ 已訪問 ” 標(biāo)志位 。 這種方式的特點是易按元素標(biāo)識定位 （ 已知元素結(jié)點的指針時 ， 可直接訪問該元素的“ 已訪問 ” 標(biāo)志 ） ， 但初始化問題不易解決 。 可以在建立廣義表結(jié)構(gòu)（ 或插入新結(jié)點 ） 時 ， 將結(jié)點的 “ 已訪問 ” 標(biāo)志置為 “ 未訪問 ” ， 但是 ， 當(dāng)要重新初始化為 “ 未訪問 ” 時 ， 問題就沒那么容易了 ， 因為 ，此時的初始化已相當(dāng)于廣義表的遍歷 ！ 由于廣義表是遞歸結(jié)構(gòu)，所以相關(guān)算法采用遞歸法實現(xiàn)比較方便。 167。 遍歷操作 下面以深度優(yōu)先遍歷操作說明廣義表的遍歷的實現(xiàn) 。 至于廣度優(yōu)先遍歷 ， 留作練習(xí) 。 廣義表的深度優(yōu)先遍歷的含義與圖或樹的深度優(yōu)先遍歷類似。 對型如 A(A1,A2, … , An) 的廣義表 ， 遍歷過程為： PreTraversal(A) { for (i=1。 i=n。 i++) if (Ai未訪問 ) if (Ai是單元素 ) { 訪問 Ai。 為 Ai置已訪問標(biāo)志； } else PreTraversal(Ai)。 } 下面是具體的程序 。 long TGList::Cluster(TGListNode *pH, char **pE, long amp。k) {//深度優(yōu)先遍歷以 pH為頭結(jié)點的廣義表 ， //將遍歷到的元素結(jié)點 （ 單元素結(jié)點 ） 的值的地址存入一維數(shù)組 pE， 返回遍歷到的單元素結(jié)點個數(shù) TGListNode *q。 if (pH==NULL) return 0。 q = pH。 while (q!=NULL) { if (qvisited==0) //若 q未被訪問 { qvisited = 1。 //置 q已訪問標(biāo)志； if (qtag==0) pE[k++]=qname。 else Cluster(qpSub, pE, k)。 //遍歷 q的子表 } q = qnext。 } //while return k。 }//Cluster() long TGList::Cluster(TGListNode *pH, char **pE) {//該程序封裝上面的帶 k參數(shù)的 Cluster()， 以簡化接口 long k=0。 SetVisitTag(pH,0)。 //置各結(jié)點的訪問標(biāo)記為 “ 未訪問 ” return Cluster(pH, pE,k)。 } 167。 計數(shù) ? 統(tǒng)計計數(shù)操作有求深度 、 求層號 、 求結(jié)點（ 元素 ） 個數(shù) （ 包括求滿足指定條件的結(jié)點個數(shù) ） 等 。 ? 廣義表的深度定義為它的各直接結(jié)點中深度最大者的深度值加 1。這是個遞歸定義 ， 所以用遞歸算法解決很自然 。該問題的解決 ， 實質(zhì)上類似于遍歷問題 ， 下面是具體的程序 。 long TGList::GetDepth(TGListNode0 *pH) {//求以 pH為總頭結(jié)點的廣義表的深度 ， 并返回其 TGListNode *q。 long dep, dep0。 if (pH==NULL) return 0。 dep=0。 q = ((TGListNode *)pH)pSub。//令 q指向廣義表 pH的第一個元素結(jié)點 while (q!=NULL) //依次求出 pH的各直接元素結(jié)點的深度 { if (qtag==0) dep0=0。 //單元素結(jié)點的深度定義為 0 else dep0=GetDepth(q)。 //求出以 q為總頭結(jié)點的廣義表 （ 即 q對應(yīng)的子表 ） 的深度 if (dep dep0) dep =dep0。 //保留最大深度 q = qnext。 //令 q指向 pH的下個直接元素結(jié)點 } //while return dep+1。 //pH的深度等于它的各直接結(jié)點的最大深度加 1 } 167。 廣義表的串行 化與逆串行化 廣義表的串行化是指根據(jù)廣義表 （ 內(nèi)存 ） 結(jié)構(gòu) ， 輸出對應(yīng)的廣義表表達(dá)式 。 這種串行化可以通過改造廣義表遍歷算法實現(xiàn) 。 這里我們只介紹逆串行化 ， 即根據(jù)廣義表表達(dá)式 ， 創(chuàng)建 （ 內(nèi)存結(jié)構(gòu) ）廣義表 。 我們假定廣義表表達(dá)式是帶名字的，即每個表（子表）前都有一個名字。為了簡化問題，突出主題，我們這里規(guī)定，廣義表表達(dá)式中，每個成分是一個字符，各成分間沒有間隔（空格），廣義表名字用大寫字母，單元素用小寫字母。此外，還假設(shè)表達(dá)式無錯誤。在實際使用中，一般需對表達(dá)式進(jìn)行預(yù)處理，使其符合這里的假設(shè)。 例如 ， 下面的表達(dá)式就是一個滿足我們這里規(guī)定的廣義表表達(dá)式： A(a, B(b,C(d)),e,F(G(h,i))) 下面考慮實現(xiàn)方法 。 首先 ， 我們采用從左到右依次讀取表達(dá)式中每個成分 （ 符號 ） 的方式 。 顯然 ， 當(dāng)讀到的是表名 ， 則創(chuàng)建該表的頭結(jié)點；如果讀到的是單元素 ， 則創(chuàng)建元素結(jié)點 。 每創(chuàng)建一個結(jié)點 ， 就需要將它鏈到相應(yīng)的單鏈表中 (next鏈 ， 鏈接同層中各結(jié)點 )， 此外 ， 若創(chuàng)建的結(jié)點是某子表中第一個結(jié)點 ，則還要令該子表的頭結(jié)點的 pSub指向它 。 為此 ， 結(jié)點創(chuàng)建后 ，要記錄到容易訪問到的地方 。 顯然 ， 記錄的次序和訪問次序相反 ， 所以應(yīng)該使用棧來記錄 ， 即每創(chuàng)建一個結(jié)點 ， 就將其壓入棧中 。 那么，如何控制棧的進(jìn)出？對新創(chuàng)建的結(jié)點，不管是元素結(jié)點還是頭結(jié)點，均進(jìn)棧，當(dāng)讀到逗號或左括號時，表示最前面一個結(jié)點已完全處理完，所以最前面的結(jié)點應(yīng)出棧。此時，最前面結(jié)點就在棧頂，所以可以直接出棧。當(dāng)前出棧的結(jié)點(比如說 p)，對下次創(chuàng)建的結(jié)點 (比如說 q)而言，是同層中的前驅(qū)，所以，當(dāng)下次創(chuàng)建結(jié)點時，應(yīng)令 p的 next指向 q。 下面是具體的程序 。 TGListNode *TGList::GListExprToGListStruct(int *gListExpr, int n) { //gListExpr: 一維數(shù)組 ， 存放廣義表表達(dá)式 。 //在 gListExpr中 ， 假定結(jié)點用單個英文字母表示 ， 各符號間也不留空 ， 表達(dá)式中無語法錯誤 //返回所創(chuàng)建的廣義表的頭結(jié)點指針 long k, top。 TGListNode *h,*pre,*p, **s。 char firstList。 if (n=3)return NULL。 //表達(dá)式中成分?jǐn)?shù)目不足 4時 ， 認(rèn)為是空表 if (gListExpr[0]39。A39。 || gListExpr[0]39。Z39。 || gListExpr[1]!=39。(39。) return NULL。 //第一個字符不是大寫字母時 ， 或第二個字符不是左括號時 ，認(rèn)為非法 ， 返回空 s = new TGListNode *[n]。 //申請?？臻g top=0。//棧頂指示器置 0， 表示空棧 . k=0。 h=new TGListNode。//生成一個結(jié)點 ,用作廣義表的總頭結(jié)點 htag=1。 hname[0]=gListExpr[k]。 hname[1]=0。 hvisited = 0。 pre=NULL。 top++。s[top]=h。 //總頭結(jié)點進(jìn)棧 k++。 firstList=1。//firstList為 最左結(jié)點 標(biāo)志 ,值為 1時 , 表示表達(dá)式中上個符號是左括號 , //當(dāng)前的成分為某表 L的最左結(jié)點 ,則 L的 pSub應(yīng)該指向該結(jié)點 while (top0 amp。amp。 kn1) { k++。 switch (gListExpr[k]) { case 39。,39。: //讀到逗號或右括號時 ,出棧 case 39。)39。: pre=s[top]。 top。 firstList=0。 break。 case 39。(39。: //左括號后的結(jié)點 ， 是上個結(jié)點的第一個子表 firstList=1。 continue。 default: //讀到表名湖或單元素 ,創(chuàng)建新結(jié)點 p = new TGListNode。 pvisited = 0。 pnext=NULL。 if (gListExpr[k]=‘A’ amp。amp。 gListExpr[k]=‘Z’) //規(guī)定子子表名為大寫字母 { ptag=1。 pname[0]=gListExpr[k]。pname[1]=0。 } else //當(dāng)前創(chuàng)建的結(jié)點是單元素 { ptag=0。 pname[0]=gListExpr[k]。pname[1]=0。 } //如果當(dāng)前創(chuàng)建的結(jié)點是所屬表中第一個結(jié)點 ,則建立子表關(guān)系 ,即令最近生成的結(jié)點的 pSub指向它 if (firstList) s[top]pSub=p。 else if (pre!=NULL) prenext = p。//建立 next鏈 ,pre為當(dāng)前生成的結(jié)點的左兄弟的指針 top++。 s[top]=p。 //新生成的結(jié)點進(jìn)棧 firstList=0。 }//switch }。 head=h。 return h。//返回所創(chuàng)建的表的頭結(jié)點 . }// 167。 廣義表的 復(fù)制與求尾 廣義表的