【正文】 8. 編寫程序，實(shí)現(xiàn)操作： long Locate(char *pE, TGListNode0 **pNodes,TTraverseMode tm=PreOrder)=0。 4. 給出一個(gè) 3元多項(xiàng)式P(x1,x2,x3)=10x15x22x3+2x15x2x3+3x15+x12x22x3+x12x2x3+x22x3+10 寫出它的廣義表表達(dá)式（邏輯表示），并畫出相應(yīng)的分枝單鏈表存貯結(jié)構(gòu)圖。 ? 廣義表的存儲(chǔ)結(jié)構(gòu)是復(fù)雜的 ， 一般都采用鏈?zhǔn)浇Y(jié)構(gòu) 。 如果結(jié)合表的聯(lián)合運(yùn)算 (∪ )， 就可以實(shí)現(xiàn)對(duì)表的重組和加工 ， 所以 ， 這兩種操作往往被做為廣義表的標(biāo)準(zhǔn)操作 。 此外 ， 廣義表的元素也很特別 ， 每個(gè)元素的結(jié)構(gòu)都可能不同 ， 而且也可以是廣義表 。 顯然 ， 這是個(gè)遞歸定義 。 因此 ， 總可以用廣義表表示任意 n叉樹 。 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)式，也可能是基本元素。一種直觀的數(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ù)域。 } 167。 //復(fù)制以 pNode為頭結(jié)點(diǎn)的表 ， 新表的頭結(jié)點(diǎn)指針為 p q=ppSub。 } 在該程序的支持下 ， 可方便實(shí)現(xiàn)求尾操作： TGListNode0 *TGList::GetTail(TGListNode0 *pNode) {//返回以 pNode為頭結(jié)點(diǎn)的表 （ 即 pNode對(duì)應(yīng)的子表 ） 的尾 （ 一個(gè)新表 ） 的頭結(jié)點(diǎn)指針 TGListNode *p,*q。 //置 q已訪問(wèn)標(biāo)志； if (qtag==0) ppElem=qpElem。 if (pRear!=NULL) pRearnext= p。 pno=qno。 q = (TGListNode *)pH。 TGListNode0 *TGList::Copy(TGListNode0 *pH, long amp。//返回所創(chuàng)建的表的頭結(jié)點(diǎn) . }// 167。 //新生成的結(jié)點(diǎn)進(jìn)棧 firstList=0。 } //如果當(dāng)前創(chuàng)建的結(jié)點(diǎn)是所屬表中第一個(gè)結(jié)點(diǎn) ,則建立子表關(guān)系 ,即令最近生成的結(jié)點(diǎn)的 pSub指向它 if (firstList) s[top]pSub=p。pname[1]=0。 if (gListExpr[k]=‘A’ amp。 continue。 break。)39。 kn1) { k++。 //總頭結(jié)點(diǎn)進(jìn)棧 k++。 hvisited = 0。 h=new TGListNode。) return NULL。 || gListExpr[0]39。 char firstList。 下面是具體的程序 。 顯然 ， 記錄的次序和訪問(wèn)次序相反 ， 所以應(yīng)該使用棧來(lái)記錄 ， 即每創(chuàng)建一個(gè)結(jié)點(diǎn) ， 就將其壓入棧中 。 首先 ， 我們采用從左到右依次讀取表達(dá)式中每個(gè)成分 （ 符號(hào) ） 的方式 。為了簡(jiǎn)化問(wèn)題，突出主題，我們這里規(guī)定，廣義表表達(dá)式中，每個(gè)成分是一個(gè)字符，各成分間沒(méi)有間隔（空格），廣義表名字用大寫字母，單元素用小寫字母。 廣義表的串行 化與逆串行化 廣義表的串行化是指根據(jù)廣義表 （ 內(nèi)存 ） 結(jié)構(gòu) ， 輸出對(duì)應(yīng)的廣義表表達(dá)式 。 //求出以 q為總頭結(jié)點(diǎn)的廣義表 （ 即 q對(duì)應(yīng)的子表 ） 的深度 if (dep dep0) dep =dep0。 dep=0。該問(wèn)題的解決 ， 實(shí)質(zhì)上類似于遍歷問(wèn)題 ， 下面是具體的程序 。 } 167。 } //while return k。 while (q!=NULL) { if (qvisited==0) //若 q未被訪問(wèn) { qvisited = 1。 long TGList::Cluster(TGListNode *pH, char **pE, long amp。 i=n。 遍歷操作 下面以深度優(yōu)先遍歷操作說(shuō)明廣義表的遍歷的實(shí)現(xiàn) 。 b) 在廣義表結(jié)點(diǎn)中增設(shè)一個(gè) “ 已訪問(wèn) ” 標(biāo)志位 。 解決的方法是為每個(gè)結(jié)點(diǎn)設(shè)立一個(gè)訪問(wèn)標(biāo)志 ， 每訪問(wèn)一個(gè)結(jié)點(diǎn) ， 就將其訪問(wèn)標(biāo)志置為 “ 已訪問(wèn) ” 。 對(duì)這類涉及整個(gè)表或元素內(nèi)部結(jié)構(gòu)的操作的實(shí)現(xiàn)，有一個(gè)重要問(wèn)題需注意：循環(huán)問(wèn)題。 167。 }。 主要不同之處 ，是在類中設(shè)立一個(gè)指向廣義表頭結(jié)點(diǎn)的指針 head。 A 上面這些操作 ， 我們?cè)?TGListNode的父類中沒(méi)有定義 ，這是為了簡(jiǎn)化問(wèn)題 。若本結(jié)點(diǎn)不是子表 ， 則返回空 。 若本結(jié)點(diǎn)為子表 ， 則返回空 。 SetNext(TGListNode0 *p)：為本結(jié)點(diǎn)代表的元素設(shè)置后繼結(jié)點(diǎn) 。 U 這實(shí)質(zhì)上是線性表的求后繼的操作 。}。 virtual TGListNode *GetParent(){return parent。 virtual TGListNode *GetSub(){return pSub。 virtual char *GetVal(){return pElem。 virtual TGListNode *GetNext(){return next。//指向結(jié)點(diǎn)對(duì)應(yīng)的元素內(nèi)容 。 結(jié)點(diǎn)對(duì)象 首先我們?cè)O(shè)置廣義表元素結(jié)點(diǎn)類TGListNode，每個(gè)TGListNode型對(duì)象，代表構(gòu)成廣義表的一個(gè)元素，它是前面介紹的抽象類TGListNode0的派生類，其數(shù)據(jù)部分是我們?cè)诮榻B存儲(chǔ)結(jié)構(gòu)時(shí)介紹的類。 這樣設(shè)置原因有二：一是為了遞歸實(shí)現(xiàn)的方便；二是為了增強(qiáng)靈活性 。 ? DeleteNode(long sn1=1， long sn2=1, TGListNode0 **pNodes)： 在對(duì)應(yīng)結(jié)點(diǎn)的子表中刪除第 sn1~sn2個(gè)元素 ， 并將被刪元素的地址存入數(shù)組 pNodes， 返回實(shí)際被刪元素的個(gè)數(shù) 。 這里 ，pNode的層號(hào)為 1， pNode的父結(jié)點(diǎn)層號(hào)為 2， 余類推 。 ? Cluster(TGListNode0 *pNode , TGListNode0 **pNodes,TTraverseMode tm=PreOrder)：串行化 （ 聚集 ） 操作 。 Tm指出查找的方式 （ 前序或?qū)有?） 。 若是 ， 則返回 p的層號(hào) （ 相對(duì)與本結(jié)點(diǎn) ） ，否則返回 0。 ? GetFirstFather(TGListNode0 *pNode)：返回結(jié)點(diǎn) pNode對(duì)應(yīng)的父結(jié)點(diǎn)中的第一個(gè)結(jié)點(diǎn) 。 由于我們這里設(shè)計(jì)的是與具體存儲(chǔ)實(shí)現(xiàn)無(wú)關(guān)的抽象操作 ， 所以 ， 這樣處理可很好地顧及各種具體的存儲(chǔ)實(shí)現(xiàn) 。 該操作就是要返回元素結(jié)點(diǎn)所對(duì)應(yīng)的表的對(duì)象指針 。 當(dāng)不使用時(shí) ， 系統(tǒng)負(fù)責(zé)將其撤銷 。 若無(wú)子表 ， 或無(wú)序號(hào)為 idx的子表 ， 則返回空 。 ? GetHead(TGListNode0 *pNode)：返回 pNode的子表的頭所對(duì)應(yīng)的結(jié)點(diǎn)的指針 。 ? GetDepth(TGListNode0 *pNode)：返回 pNode的子表的深度 。 virtual TGListNode0 *DeleteNode(long sn=1)=0。 virtuallongCluster(TGListNode0*pNode,TGListNode0**pNodes, TTraverseMode tm=PreOrder)=0。 virtualTGListNode0 *GetNextFather(TGListNode0 *pNode)=0。 virtual TGList0 *GetList(TGListNode0 *pNode)=0。 virtual TGListNode0 *Copy(TGListNode0 *pH, long amp。由于我們采用了結(jié)點(diǎn)簡(jiǎn)單接口（前面指出的方式 a），所以，關(guān)于結(jié)點(diǎn)所代表的子表的操作接口大都放在這里的廣義表接口實(shí)現(xiàn)。 TGListNode *pSub。 之所以這樣 ， 是考慮到這些量與具體的存儲(chǔ)結(jié)構(gòu)密切相關(guān) ， 在抽象結(jié)構(gòu)中給出會(huì)影響靈活性 。 ? GetTag()：返回本結(jié)點(diǎn)的標(biāo)志 。 ? GetName()：返回本結(jié)點(diǎn)的名字串的指針 。 }。 }。 }。}。 //超前聲明 （ 因?yàn)樵谙旅媛暶鞯?TGListNode0中用到此類 ） class TGListNode0 //廣義表結(jié)點(diǎn)類 { public: //protected: char tag。我們這里選擇方式 a，下面是具體的定義。 對(duì)這種關(guān)聯(lián)關(guān)系復(fù)雜的結(jié)點(diǎn)的接口的設(shè)計(jì) ， 一般的方法都 “ 左右為難 ” 。 167。 這里我們用 union實(shí)現(xiàn)共享 。 pElem：指向結(jié)點(diǎn)對(duì)應(yīng)的元素內(nèi)容 （ 地址 ） 。 tag：廣義表元素結(jié)點(diǎn)種類標(biāo)志 ， 它表明對(duì)應(yīng)結(jié)點(diǎn)是單元素 (0)還是表 (1)。 union { char *pElem。廣義表的這種存儲(chǔ)結(jié)構(gòu)看上去比較復(fù)雜，其實(shí)只有一種結(jié)構(gòu)：廣義表結(jié)點(diǎn)TGListNode，其定義如下。 (d)如果不共享單元素內(nèi)容 ， 且單元素內(nèi)容的長(zhǎng)度相等 （ 或差別不大 ） ， 則可將單元素內(nèi)容直接放到元素頭結(jié)點(diǎn)中 。 具體地講 ， 廣義表 Ls=(α 1,α 2, … , α n)的分枝單鏈表存貯方法為： (a) 為每個(gè) α i設(shè)置一個(gè)結(jié)點(diǎn) Hi，稱其為 α i的頭結(jié)點(diǎn)，其結(jié)構(gòu)為： tag：指示 αi是單元素還是廣義表 (我們?cè)O(shè) tag為 0時(shí)表示 αi為單元素 ） 。 對(duì)廣義表的幾個(gè)邏輯特性 ， 若有的與具體問(wèn)題無(wú)關(guān) ， 則在選擇存貯結(jié)構(gòu)時(shí)就不必考慮 ， 以簡(jiǎn)化存貯結(jié)構(gòu) 。“ 廣義 ” 的順序存儲(chǔ)，是指按順序存儲(chǔ)方法存儲(chǔ)廣義表表達(dá)式，即廣義表表達(dá)式中的括號(hào)、基本元素都存儲(chǔ)在一片連續(xù)空間內(nèi)。 167。 167。一個(gè)復(fù)合元素 ， 在某一層上被當(dāng)作元素 ， 但就它本身的結(jié)構(gòu)而言 ， 也是廣義表 ， 因此也代表一個(gè)數(shù)據(jù)對(duì)象 （ 數(shù)據(jù)元素的集合 ） 。 不過(guò) ， 廣義表的層次性與樹不同 ， 在樹中 ， 任一元素只直屬一個(gè)元素 。 ? 從定義看出，廣義表具有下列特性 ? 宏觀線性性 ：對(duì)任意廣義表，若不考慮它的元素的內(nèi)部結(jié)構(gòu)，則它是一個(gè)線性表，即它的直接元素之間是線性關(guān)系。 所示的廣義表圖 ， 深度優(yōu)先遍歷結(jié)果為： L A B a b C c D d e E 如果只訪問(wèn)單元素 ， 則結(jié)果為： a b c d e 對(duì) 錯(cuò)誤 ！ 未找到引用源 。 L A C D E B a b c d e