【正文】 q。 } 下面是具體的程序 。 i++) if (Ai未訪問 ) if (Ai是單元素 ) { 訪問 Ai。 對型如 A(A1,A2, … , An) 的廣義表 ， 遍歷過程為： PreTraversal(A) { for (i=1。 至于廣度優(yōu)先遍歷 ， 留作練習(xí) 。 167。 這種方式的特點(diǎn)是易按元素標(biāo)識定位 （ 已知元素結(jié)點(diǎn)的指針時 ， 可直接訪問該元素的“ 已訪問 ” 標(biāo)志 ） ， 但初始化問題不易解決 。 這種方法容易進(jìn)行初始化 （ 將所有元素都置為 “ 未訪問 ” ） ， 但不易按元素標(biāo)識定位 （ 已知元素標(biāo)識 ， 訪問對應(yīng)的已訪問數(shù)組元素值 ） 。 這種處理方法又存在一個問題 ， 就是訪問標(biāo)志如何設(shè)置 。 這樣 ， 處理廣義表時 ， 若不知道遞歸元素是否已被處理 ， 就可能導(dǎo)致無限循環(huán) 。 廣義表是允許遞歸的 ， 即某表的元素中 ， 可以包含自己 （ 以自己為元素 ） 。涉及整個表或元素內(nèi)部結(jié)構(gòu)的操 作 主 要 有 GetDepth() 、GetFather()、 Locate()、 Cluster()、IsMenber()等 。 一般問題 如果拋開廣義表元素的內(nèi)部結(jié)構(gòu) ， 廣義表就相當(dāng)于線性表 ，因此 ， 廣義表的不涉及元素內(nèi)部結(jié)構(gòu)的操作的實(shí)現(xiàn) ， 與普通線性表類似 。 廣義表操作 的實(shí)現(xiàn) * 本節(jié)通過幾個有代表性的算法的實(shí)現(xiàn)，說明廣義表的相關(guān)算法實(shí)現(xiàn)方法。 至于操作的實(shí)現(xiàn)，我們放在下節(jié)中討論。 //指向廣義表的頭結(jié)點(diǎn) public: //下面是在 TGList0中定義的函數(shù)的聲明（不含“ =0”部分）。 為了處理方便，為每個獨(dú)立的廣義表設(shè)置一個頭結(jié)點(diǎn)，令它的 pSup指向廣義表中第一個元素對應(yīng)的結(jié)點(diǎn)，如圖 80所示。 分枝單鏈表對象 由于廣義表結(jié)構(gòu)信息已包含在結(jié)點(diǎn)類 TGListNode中 ，故針對分枝單鏈表的廣義表類的形式 ， 與前面給出的TGList0類似 。 如果要考慮接口的統(tǒng)一 ， 這些操作就需要在父類中定義了 。 ? SetParent (TGListNode *p)： 為本結(jié)點(diǎn)設(shè)置父表 ，相當(dāng)于強(qiáng)行將本結(jié)點(diǎn)作為以 pP結(jié)點(diǎn)的子表 。 ? SetSub(TGListNode *p)： 為本元素結(jié)點(diǎn)設(shè)置子表 ，即將以 pH為頭的表設(shè)置為本結(jié)點(diǎn)的子表 。 ? GetSub()：返回本結(jié)點(diǎn)對應(yīng)的子表的頭結(jié)點(diǎn)的地址 。 這里 ， 將結(jié)點(diǎn)內(nèi)容看作字節(jié)流 （ char型 ） 。 GetVal()：返回本結(jié)點(diǎn)對應(yīng)的元素的內(nèi)容的地址 。 注意 ， 這與在表中插入一個結(jié)點(diǎn)是不同 。 對確需同時提供兩個關(guān)系的直接訪問的應(yīng)用 ， 可從該類派生新類 ， 在新類中增加相應(yīng)的關(guān)系的數(shù)據(jù)表示 。 對于非順序存儲結(jié)構(gòu) ， 每個元素都應(yīng)設(shè)立表示后繼或前驅(qū)關(guān)系的數(shù)據(jù)域 ，因此 ， 該操作是對具體的存儲結(jié)構(gòu)的后繼關(guān)系的數(shù)據(jù)表示的抽象 。 GetNext()：返回本結(jié)點(diǎn)代表的元素的后繼元素所對應(yīng)的結(jié)點(diǎn)的指針 。 }。tag=1。}。}。}。}。}。}。}。 }。 TGListNode *pSub。 union { char *pElem。 struct TGListNode : public TGListNode0 { TGListNode *next。 167。 當(dāng)然 ， 如果每個成員函數(shù)都帶結(jié)點(diǎn)指針參數(shù) ， 則它們都可以設(shè)置到結(jié)點(diǎn)類中 ！ 這也是一種不錯的選擇 ！ 167。 A 我們看到 ， 這里的 TGList0類中大多數(shù)成員函數(shù)都有一個廣義表結(jié)點(diǎn)指針作為參數(shù) 。 U 廣義表具有線性表的某些特征 ， 這是因?yàn)?， 對某個 （ 層 ） 廣義表而言 ， 它的直接元素之間呈線性關(guān)系 。 sn可正可負(fù) ， 具體含義同前（ 線性表 ） 。 ? InsertNode(TGListNode *p, long sn)： 在本表中的第 sn個結(jié)點(diǎn)之前插入結(jié)點(diǎn) p。 ? ClusterSeniors(TGListNode0*pNode,TGListNode0 **pNodes, TTraverseMode tm=PreOrder, int startLevel=1, int endLevel=1)：按遍歷方式 tm， 將結(jié)點(diǎn) pNode對應(yīng)的子表中的層號在 startLevel和 endLevel之間的結(jié)點(diǎn)的地址 ， 存入數(shù)組 pNodes， 返回數(shù)組中元素個數(shù) 。按遍歷方式 tm， 將以 pNode為頭結(jié)點(diǎn)的表中的各元素結(jié)點(diǎn)的地址 ， 存入數(shù)組 pNodes中 ， 返回數(shù)組中元素的個數(shù) 。 按遍歷方式 tm， 將以pNode為頭結(jié)點(diǎn)的表中的各元素結(jié)點(diǎn)的值的地址 ， 存入數(shù)組 e中 ，返回數(shù)組中元素的個數(shù) 。返回值為所找到的結(jié)點(diǎn)的數(shù)目 。 ? Locate(char *pE, TGListNode0 **pNodes, TTraverseMode tm=PreOrder)：在本表中查找內(nèi)容的地址為 pE的結(jié)點(diǎn) ， 將它們的地址存入數(shù)組 pNodes。 ? DeleteNode(long sn=1)：在對應(yīng)結(jié)點(diǎn)的子表中刪除第 sn個元素 ， 并將其地址返回 。 ? IsMenber(TGListNode *p)： 檢查結(jié)點(diǎn) p是否是本結(jié)點(diǎn) （ 對象本身 ） 的成員 。 ? GetNextFather(TGListNode0 *pNode)：返回結(jié)點(diǎn) pNode對應(yīng)的父結(jié)點(diǎn)中的下一個結(jié)點(diǎn) 。 將元素 elem所屬的子表所對應(yīng)的元素（ 的結(jié)點(diǎn) ） ， 稱為 elem的父元素 （ 結(jié)點(diǎn) ） 。 ? GetFathers(TGListNode0 *pNode, TGListNode0 **fathers)：將結(jié)點(diǎn) pNode的各父結(jié)點(diǎn)的指針存入 fathers數(shù)組中 。 例如 ， 若表的頭是表（ 尾 肯 定 是 表 ） ， 則通過 GetList(GetHead()) 或GetList(GetTail())， 可繼續(xù)按表處理頭或尾 。 一旦獲得表對象指針 ， 就可繼續(xù)按表對象（ TGList0） 訪問子表 ， 因此 ， 凡是返回表結(jié)點(diǎn) (TGListNode0)的操作 ， 都可以借助該操作 ， 轉(zhuǎn)化為表對象 (TGList0)。 當(dāng)元素為表的時候 ， 元素的結(jié)點(diǎn)就對應(yīng)該表 。 U GetList操作主要用于語法上的轉(zhuǎn)換 。 若 pNode原來沒有對應(yīng)表對象 ， 則返回的表對象是新創(chuàng)建的臨時對象 ， 只一次使用有效 。 ? GetList(TGListNode0 *pNode)：返回結(jié)點(diǎn) pNode所對應(yīng)的子表對象指針 。 ? GetSub(TGListNode0 *pNode ,long idx) ：返回結(jié)點(diǎn)pNode對應(yīng)的子表中的序號為 idx的結(jié)點(diǎn) 。 ? GetTail(TGListNode0 *pNode)：返回 pNode的子表的尾的第一個結(jié)點(diǎn)的指針 。 所復(fù)制的結(jié)點(diǎn)總數(shù)返回到 k中 （ 調(diào)用時 k值應(yīng)為 0） 。 ? Copy(TGListNode0 *pH, long amp。 ? GetLen(TGListNode0 *pNode)：返回 pNode的子表的長度 。 virtuallongDeleteNode(longsn1=1,longsn2=1,TGListNode0**pNodes)=0。 virtual TGListNode0 *InsertNode(TGListNode0 *p,long sn)=0。 virtuallongClusterJuniors(TGListNode0*pNode,TGListNode0 **pNodes,TTraverseModetm=PreOrder,intstartLevel=1,int endLevel=1)=0。 virtual long Cluster(TGListNode0 *pNode , char **e, TTraverseMode tm=PreOrder)=0。 virtual long IsMenber(TGListNode0 *p)=0。 virtualTGListNode0 *GetFirstFather(TGListNode0 *pNode)=0。 virtual TGListNode0 *GetElemNode(long idx)=0。 virtual TGListNode0 *GetTail(TGListNode0 *pNode)=0。k)=0。 virtual long GetDepth(TGListNode0 *pNode)=0。廣義表接口具體定義如下。 廣義表接口 廣義表接口是關(guān)于整個廣義表（或廣義表系列）的操作 /訪問規(guī)范。 } //下面是 TGListNode0中定義的成員函數(shù)的原形 … … }。 union { char *pElem。 對具體的存儲結(jié)構(gòu)下的廣義表結(jié)點(diǎn) ， 應(yīng)該從該類派生 。 A 在該類中 ， 我們沒有設(shè)置用于描述結(jié)點(diǎn)間關(guān)系的量 ， 如指示同層中下個元素的 next， 指示子表的 pSub等 。 ? SetTag(char mTag)：為本元素結(jié)點(diǎn)設(shè)置標(biāo)志 。 ? SetNo(unsigned long mNo)：為本元素結(jié)點(diǎn)設(shè)置編號 。 ? SetName(char *mName)：為本元素結(jié)點(diǎn)設(shè)置 （ 復(fù)制 ）名字 。 ? IsList()： 若本結(jié)點(diǎn)是非單元素結(jié)點(diǎn) ， 則返回假（ 0） ， 否則返回真 （ 1） 。 }。 void SetTag(char mTag) {tag=mTag。 char GetTag(){ return tag。 void SetNo(unsigned long mNo) {no=mNo。 unsigned long GetNo(){ return no。 voidSetName(char*mName){strncpy(name,mName, CNST_SizeListNodeName)。 char *GetName(){ return name。 //結(jié)點(diǎn)編號 public: char IsList() {return tag。 //結(jié)點(diǎn)標(biāo)識： 0單元素 ， 其他 廣義表 char name[CNST_SizeListNodeName]。 class TGList0。 enum TTraverseMode {PreOrder, LevelOrder}。方式 a比較簡潔，對一些涉及到表的全局的操作，也容易處理，但不自然不靈活；方式 b比較自然，并且使用靈活，但結(jié)點(diǎn)的接口變得復(fù)雜，而且對于一些涉及全局的操作（例如，對子表，若要在子表所在的整個表中查找，就是個全局操作問題）也不好處理，運(yùn)行（被使用）效率也不及方式 a。一般有兩種方法 （ 策略 ） ： (a)結(jié)點(diǎn)觀點(diǎn)：本著 “ 本地原則 ” ， 重點(diǎn)提供對結(jié)點(diǎn)自己的屬性的訪問 ， 而對表的操作 ， 專門設(shè)立 “ 表對象 ” ， 將它們放在表對象中； (b)表觀點(diǎn)：將結(jié)點(diǎn)看作子表 （ 當(dāng)然也是廣義表 ） 的代表 ， 將廣義表的大部分操作都設(shè)置在結(jié)點(diǎn)上 。 廣義表結(jié)點(diǎn)比較復(fù)雜 ， 具有遞歸性 ， 即它本身既可以是基本元素 ， 也可以是子表的代表 。 廣義表元 素接口 首先我們考慮廣義表元素的抽象模型。從廣義特點(diǎn)出發(fā)，我們將訪問接口分為兩部分：廣義表元素（結(jié)點(diǎn)）接口和廣義表接口。 廣義表對象模型 * 這里，我們將廣義表作為一種抽象對象，建立它的訪問接口。