【正文】 。 7．編寫程序，輸出（內(nèi)存結(jié)構(gòu)）廣義表的表達(dá)式。 5．編寫廣義表的廣度優(yōu)先遍歷程序。 A1 = (banana, pear, orange, (apple)) A2 = ((apple, pear), orange) A2 = (pear, (peach, (plum, apple), fig), apple, date) 3. 畫出 L=A(a, B(c, C(a, b), d), E(e,F(f)) )的廣義表圖，并分別給出其深度優(yōu)先和廣度優(yōu)先遍歷結(jié)果。 本章給出的分枝單鏈表是廣義表的一種通用的存儲方法 ， 完整地描述了廣義表的主要特性 。 本章給出的設(shè)計 ， 就是力求兼顧這些方面 。 ? 廣義表的接口設(shè)計也很復(fù)雜 。 ? 求頭和求尾是兩項(xiàng)重要的操作 ， 通過這兩個操作的配合 ， 可以訪問到表中任意元素 。 事實(shí)上 ， 廣義表中 ， 元素分兩大類 ， 一類是單元素 ， 與其他數(shù)據(jù)結(jié)構(gòu)下的元素類似 ， 另一類是非單元素 ， 為復(fù)合元素量 ， 即由單元素復(fù)合而成的元素 。 本章小結(jié) ? 廣義表是一種很特殊的數(shù)據(jù)結(jié)構(gòu) ， 從某一層的各元素的關(guān)系看 ， 是線性表 ， 但從分層結(jié)構(gòu)看與樹類似 （ 無共享結(jié)點(diǎn)時是樹 ， 有共享結(jié)點(diǎn)但不同出現(xiàn)看作相同時為單純的層次結(jié)構(gòu) ） ， 所以從整體看 ， 它仍然是一種受限的結(jié)構(gòu) ， 不象圖結(jié)構(gòu)那樣結(jié)點(diǎn)關(guān)系沒有限制 。 例如 ， 對圖 80， 它的廣義表表示為： W1(W11(W111(W1111, W1112)), W12(W121,W122(W1221)), W13(W131, W132, W133)) 層次結(jié)構(gòu)是不含循環(huán) （ 遞歸 ） 的 。 W1 W12 W121 W122 W111 W11 W131 W132 W133 W13 W1112 W1221 W1111 圖 8 0一個家族結(jié)構(gòu)的樹表示 對這種層次結(jié)構(gòu) ， 我們采用下面的表示法： 對層次結(jié)構(gòu)中任一結(jié)點(diǎn) X(設(shè) A為結(jié)點(diǎn)名稱 )， 若 X無下屬結(jié)點(diǎn) (X是單元素 )， 則將 X的廣義表示為： X …… 當(dāng) X不是最高層 ， (X) …… 當(dāng) X是最高層 若 X有下屬結(jié)點(diǎn) （ X是子表 ） ， 則 X的廣義表表示為 “ X(X1, X2, … , Xn) 這里 , X1, X2, … , Xn為 X的 n個下屬結(jié)點(diǎn) （ n0） 對應(yīng)的廣義表表示 。 例如 ， 我們在第一章給出的家族樹就是一種層次結(jié)構(gòu) 。 層次結(jié)構(gòu)的表示 n叉樹是一種層次結(jié)構(gòu) ， 故 n叉樹是一種廣義表 ， 但反之未必 ， 因?yàn)?n叉樹的定義中排除了樹結(jié)點(diǎn)的共享性 。并且將各二元組按指數(shù)降序排列，則所成結(jié)構(gòu)為廣義表，這就是 m元多項(xiàng)式的廣義表表示 對上式有： P=((A3,5), (A2,1), (A1,0) ) //以 x1為主變量 A3=( (A32,3), (A31,2) ) //以 x2為主變量 A3=( 5x33+ x3) x23+(2x34) x22 A2=((A21, 4)) //以 x2為主變量 A2 = (3 x32 )x24 A1=((A11, 1), (100,0)) //以 x2為主變量 A1=x2x3 A32=((5,3), (1,1)) //以 x3為主變量 A32=5x33+ x3 A31=((2,4)) //以 x3為主變量 A31=2x34 A21=((3,2)) //以 x3為主變量 A21= 3x32 A11=((1,1)) //以 x3為主變量 A11=x3 從該例子看出，用廣義表表示具體對象，關(guān)鍵是分層，即以某種方式（抓住某個因素）先將對象組織為一個線性結(jié)構(gòu)，然后，再按同樣方式細(xì)化線性結(jié)構(gòu)中各元素。 對任意一個 m元多項(xiàng)式 ， 都可以任選一個變元 （ 稱為第 1變元或主變元 ） ， 按此變元合并同類項(xiàng) ， 使該 m元多項(xiàng)式變?yōu)槿缦滦问剑? 這里 ， enen1… e1， Ai為關(guān)于變元 x2… xm的 (m1)元多項(xiàng)式 ，i=1,2,… n， 下步可對 Ai選 x2為主變元進(jìn)行類似的處理，如此進(jìn)行，最后一回選 xm為主變元，對各個以 xm1為主變元的多項(xiàng)式進(jìn)行同樣的處理。 但這種表示法有下列幾個方面的缺陷： ① 結(jié)點(diǎn)的結(jié)構(gòu)隨多項(xiàng)式的變數(shù)元數(shù)目而變化 ， 這造成了概念上的不美觀 ， 缺少通用性； ② 不適合某些應(yīng)用要求的操作的實(shí)現(xiàn) ， 如某些操作要求將m個變元中某個變元視為主變元 ， 其它變元視為常量 ， 而在處理主變元的系數(shù)時 ， 又將它視為一個 (m1) 元多項(xiàng)式進(jìn)行處理 。 多元多項(xiàng)式的表示 多元多項(xiàng)式具有多個變元 ，例如下面是一個三元多項(xiàng)式 P(x1,x2, x3)= x15x23x3+2x15x22x34+5x15x23x33+3x1x24x32+x2x3+100 用計算機(jī)處理這種多項(xiàng)式時，就要考慮選取合適的數(shù)據(jù)結(jié)構(gòu)。 廣義表結(jié)構(gòu)的應(yīng)用 廣義表最適合描述遞歸結(jié)構(gòu)和分層結(jié)構(gòu)，如分層索引結(jié)構(gòu)（如圖書的目錄、計算機(jī)操作系統(tǒng)中的文件目錄結(jié)構(gòu)）及其它一些多叉樹形結(jié)構(gòu)，下面用幾個典型的例子說明。 return p。 //下面三句將 pNode的復(fù)制品中的第一個元素刪除 ppSub=qnext。 p=(TGListNode *)Copy(pNode,k)。 long k=0。 //令 q指向 pH的同層中的下一個結(jié)點(diǎn) } //while return pH0。 else ppSub=(TGListNode *)Copy(qpSub, k)。 qvisited = 1。 else pH0=p。 strcpy(pname, qname)。 pvisited=0。 //新申請一個結(jié)點(diǎn) ， 作為 q的復(fù)制品 ptag=qtag。 while (q!=NULL) { if (qvisited==0) //若 q未被訪問 { k++。 pRear=NULL。k) {//復(fù)制以 pH為頭結(jié)點(diǎn)的表 ， 返回新復(fù)制的表的頭結(jié)點(diǎn)指針 TGListNode *q, *p,*pH0, *pRear。具體程序如下。 廣義表的 復(fù)制與求尾 廣義表的復(fù)制，也是生成結(jié)構(gòu)與內(nèi)容完全相同的另一個表。 return h。 }//switch }。 s[top]=p。 else if (pre!=NULL) prenext = p。pname[1]=0。 } else //當(dāng)前創(chuàng)建的結(jié)點(diǎn)是單元素 { ptag=0。 pname[0]=gListExpr[k]。amp。 pnext=NULL。 default: //讀到表名湖或單元素 ,創(chuàng)建新結(jié)點(diǎn) p = new TGListNode。: //左括號后的結(jié)點(diǎn) ， 是上個結(jié)點(diǎn)的第一個子表 firstList=1。 case 39。 firstList=0。: pre=s[top]。: //讀到逗號或右括號時 ,出棧 case 39。 switch (gListExpr[k]) { case 39。amp。 firstList=1。s[top]=h。 pre=NULL。 hname[1]=0。//生成一個結(jié)點(diǎn) ,用作廣義表的總頭結(jié)點(diǎn) htag=1。//棧頂指示器置 0， 表示空棧 . k=0。 //第一個字符不是大寫字母時 ， 或第二個字符不是左括號時 ，認(rèn)為非法 ， 返回空 s = new TGListNode *[n]。(39。Z39。A39。 if (n=3)return NULL。 TGListNode *h,*pre,*p, **s。 TGListNode *TGList::GListExprToGListStruct(int *gListExpr, int n) { //gListExpr: 一維數(shù)組 ， 存放廣義表表達(dá)式 。當(dāng)前出棧的結(jié)點(diǎn)(比如說 p)，對下次創(chuàng)建的結(jié)點(diǎn) (比如說 q)而言，是同層中的前驅(qū)，所以，當(dāng)下次創(chuàng)建結(jié)點(diǎn)時，應(yīng)令 p的 next指向 q。 那么，如何控制棧的進(jìn)出？對新創(chuàng)建的結(jié)點(diǎn)，不管是元素結(jié)點(diǎn)還是頭結(jié)點(diǎn)，均進(jìn)棧，當(dāng)讀到逗號或左括號時，表示最前面一個結(jié)點(diǎn)已完全處理完，所以最前面的結(jié)點(diǎn)應(yīng)出棧。 為此 ， 結(jié)點(diǎn)創(chuàng)建后 ，要記錄到容易訪問到的地方 。 顯然 ， 當(dāng)讀到的是表名 ， 則創(chuàng)建該表的頭結(jié)點(diǎn)；如果讀到的是單元素 ， 則創(chuàng)建元素結(jié)點(diǎn) 。 例如 ， 下面的表達(dá)式就是一個滿足我們這里規(guī)定的廣義表表達(dá)式： A(a, B(b,C(d)),e,F(G(h,i))) 下面考慮實(shí)現(xiàn)方法 。此外，還假設(shè)表達(dá)式無錯誤。 我們假定廣義表表達(dá)式是帶名字的，即每個表（子表）前都有一個名字。 這種串行化可以通過改造廣義表遍歷算法實(shí)現(xiàn) 。 //pH的深度等于它的各直接結(jié)點(diǎn)的最大深度加 1 } 167。 //保留最大深度 q = qnext。 //單元素結(jié)點(diǎn)的深度定義為 0 else dep0=GetDepth(q)。 q = ((TGListNode *)pH)pSub。 if (pH==NULL) return 0。 long TGList::GetDepth(TGListNode0 *pH) {//求以 pH為總頭結(jié)點(diǎn)的廣義表的深度 ， 并返回其 TGListNode *q。這是個遞歸定義 ， 所以用遞歸算法解決很自然 。 計數(shù) ? 統(tǒng)計計數(shù)操作有求深度 、 求層號 、 求結(jié)點(diǎn)（ 元素 ） 個數(shù) （ 包括求滿足指定條件的結(jié)點(diǎn)個數(shù) ） 等 。 //置各結(jié)點(diǎn)的訪問標(biāo)記為 “ 未訪問 ” return Cluster(pH, pE,k)。 }//Cluster() long TGList::Cluster(TGListNode *pH, char **pE) {//該程序封裝上面的帶 k參數(shù)的 Cluster()， 以簡化接口 long k=0。 //遍歷 q的子表 } q = qnext。 //置 q已訪問標(biāo)志； if (qtag==0) pE[k++]=qname。 q = pH。k) {//深度優(yōu)先遍歷以 pH為頭結(jié)點(diǎn)的廣義表 ， //將遍歷到的元素結(jié)點(diǎn) （ 單元素結(jié)點(diǎn) ） 的值的地址存入一維數(shù)組 pE， 返回遍歷到的單元素結(jié)點(diǎn)個數(shù) TGListNode *