【正文】 Init_OL(M,m,n)。 coutinput i j e(e=0退出):\n。 while(1) { cinije。 if(!Insert_OL(M,i,j,e)) break。 }}5．十字鏈的遍歷操作函數(shù)void Print_OL(CrossList M)的作用是，以三元組形式輸出用十字鏈表表示的稀疏矩陣M的所有非零元素及其所在的行、列下標。void Print_OL(CrossList M){ int i。 Olink p。 for(i=0。i。i++) for(p=[i]。p。p=pright) cout39。(39。pi39。 39。pj39。 39。pe)\n。}6．十字鏈表存儲的稀疏矩陣矩陣的輸入輸出演示程序void main(){ CrossList MM。 int y=1。 while(y==1) { Create_OL(MM)。 coutyour input is:\n。 Print_OL(MM)。 cout繼續(xù)嗎(y=1/no=2)?。 ciny。 }}運行結(jié)果為：Create Cross Matrix:輸入行數(shù)和列數(shù)m n:4 6↙input i j e(e=0退出):0 2 9↙1 1 5↙1 5 1↙2 0 4↙2 5 2↙3 3 8↙0 0 0↙your input is:(0 2 9)(1 1 5)(1 5 1)(2 0 4)(2 5 2)(3 3 8)繼續(xù)嗎(y=1/no=2)?1Create Cross Matrix:輸入行數(shù)和列數(shù)m n:4 6↙input i j e(e=0退出):3 3 8↙2 0 4↙1 1 5↙0 2 9↙1 5 1↙2 5 2↙0 0 0↙your input is:(0 2 9)(1 1 5)(1 5 1)(2 0 4)(2 5 2)(3 3 8)繼續(xù)嗎(y=1/no=2)? 廣義表廣義表是n(n≥0)個數(shù)據(jù)元素a1,a2,a3,…,an的有限序列，記為：LS=。其中，LS稱為廣義表的表名，n稱為廣義表LS的長度，當n為0時稱LS為空表，ai(i=1,2,3,…,n)稱為廣義表的元素。廣義表中的元素既可以是單個元素稱為原子（通常用小寫字母表示），也可以是廣義表稱為子表（通常用大寫字母表示），當LS非空時稱第一個元素a1為廣義表LS的表頭(Head)，而(a2,a3,…,an)稱為廣義表LS的表尾(Tail)。廣義表中括號的最大重數(shù)稱為該廣義表的深度。顯然，廣義表是一種遞歸定義的數(shù)據(jù)結(jié)構(gòu)，雖然它也是線性結(jié)構(gòu)但是它與線性表有著明顯的差別。廣義表的這一特點在處理具有層次特點的線性結(jié)構(gòu)問題時有著獨特的功能?！尽壳髲V義表的長度、深度、表頭和表尾（如果存在）。（1）A=()A是一個空表，長度為0，深度為1，不存在表頭和表尾。（2）B=(e)B是一個廣義表，只有一個原子e，長度為1，深度為1，表頭為原子e，表尾為空表()。（3）C=(a,(b,c,d))C是一個廣義表，有兩個元素，第一個a為原子，第二個(b,c,d)為子表，所以長度為2，深度為2，它的表頭為a,表尾為((b,c,d)) 。（4）D=(A，B，C)D=((),(e),(a,(b,c,d)))是廣義表，長度為3，深度為3，表頭為A=()，表尾為(B,C)= ((e),(a,(b,c,d)))。（5）E=(a,E)E=(a,(a,(a,…)))是一個廣義表，長度為2，深度為無限大，表頭為a，表尾為(E)。1．廣義表的幾個重要特點（1）廣義表中的元素還可以是廣義表，可見它是一個多層次結(jié)構(gòu)。用□表示原子，用○表示廣義表，可以用圖形形象地將[](a)。（2）一個廣義表可以為其它廣義表共享。如[]中的廣義表D。（3）廣義表可以是一個遞歸定義的廣義表，如[]中的廣義表E。此時深度為無限大，(b)所示。（4）非空廣義表的表尾還是一個廣義表，且表尾的深度≤原表的深度，表尾的長度比原表少一；而表頭可以是原子，也可以是子表。注意：廣義表（）和（（））是兩個不同的廣義表。前者為空表而后者非空，其長度為1深度為2。2．廣義表的基本操作廣義表的基本操作主要有：（1）初始化InitGList(amp。L) 其功能是創(chuàng)建一個空表L；（2）創(chuàng)建CreateGList(amp。L,S) 其操作結(jié)果為，由廣義表串S創(chuàng)建廣義表L；（3）復(fù)制CopyGList(amp。T,L) 該操作的結(jié)果是由廣義表L復(fù)制得到廣義表T；（4）求長度GetLength(L) 該操作的功能是返回廣義表L的長度；（5）求深度GetDepth(L) 該操作的功能是返回廣義表L的深度；（6）求表頭Head(L) 該操作的功能是返回廣義表L的表頭；（7）求表尾Tail(L) 該操作的功能是返回廣義表L的表尾；（8）插入操作InsertFirst_GL(amp。L,e) 該操作插入元素e作為廣義表L的第一個元素；（9）刪除操作DeleteFirst_GL(amp。L,amp。e) 該操作的結(jié)果是，刪除廣義表L的第一個元素，并用e返回其值；（10）遍歷操作Traverse_GL(L) 該操作的功能是依次輸出L中的每個數(shù)據(jù)元素?！尽壳笙铝袑V義表進行基本操作的結(jié)果：（1）Head【((a,b),(c,d))】；（2）Head【Tail【((a,b),(c,d))】】；（3）Tail【Head【((a,b),(c,d))】】；（4）Tail【Head【Tail【((a,b),(c,d))】】】；（5）Head【Tail【Head【((a,b),(c,d))】】】。（說明：用【】作為基本操作的函數(shù)符號以示區(qū)別。）解：（1）Head【((a,b),(c,d))】=(a,b)（2）Head【Tail【((a,b),(c,d))】】=Head【((c,d))】=(c,d)（3）Tail【Head【((a,b),(c,d))】】=Tail【(a,b)】=(b)（4）Tail【Head【Tail【((a,b),(c,d))】】】=Tail【Head【((c,d))】】=Tail【(c,d)】=(d)（5）Head【Tail【Head【((a,b),(c,d))】】】=Head【Tail【(a,b)】】=Head【(b)】=b廣義表通常采用鏈式存儲結(jié)構(gòu)，每個數(shù)據(jù)元素可用一個結(jié)點來表示，為了區(qū)分該結(jié)點是原子或子表，在結(jié)點中設(shè)置一個標志域tag，當tag=0時表示結(jié)點為原子結(jié)點，tag=1時表示結(jié)點為子表結(jié)點。對于子表結(jié)點，設(shè)置指向頭表的指針域hp和指向表尾的指針域tp；而對于原子結(jié)則設(shè)置數(shù)據(jù)域atom。例如，對于[]中的廣義表：（1）A=()。（2）B=(e)。（3）C=(a,(b,c,d))。（4）D=((),(e),(a,(b,c,d)))。（5）E=(a,E)。由于廣義表本身是遞歸定義的，所以廣義表的存儲結(jié)構(gòu)也用遞歸的方式來定義是必然的。在C++語言中用以下結(jié)構(gòu)類型來表示廣義表。typedef char AtomType。 //定義廣義表的數(shù)據(jù)域data的類型為charenum ElemTag{ATOM,LIST}。 //定義結(jié)點標志域tag的類型為枚舉(enum)類型ElemTag其中，ElemTag為枚舉類型(enum)，該類型變量的值只能是ATOM（其值為0表示原子）或LIST（其值為1表示廣義表）。typedef struct GLNode //定義結(jié)點的結(jié)構(gòu)類型GLNode{ ElemTag tag。 union //定義結(jié)點信息域Data的類型為共同體類型(union) { AtomType data。 //定義結(jié)點的數(shù)據(jù)域data的類型為AtomType struct{GLNode *hp,*tp。}ptr。 //定義廣義表的表頭 (hp)、表尾 (tp)指針域ptr的類型為無名結(jié)構(gòu)體 }Data。}*GList。 //定義廣義表類型GList由于廣義表的存儲結(jié)構(gòu)類型是遞歸定義的，在廣義表基本操作的算法中采用遞歸的方法較為簡單。本節(jié)中有關(guān)廣義表的所有基本操作均采用遞歸的方法進行處理。1．求廣義表GL的深度的遞歸算法int GListDepth(GList GL)該操作的算法的思想是，先用遞歸算法算出廣義表GL中所有子表的深度的最大值max，再返回該廣義表GL的深度max+1。算法的程序?qū)崿F(xiàn)如下：int GListDepth(GList GL){ int max,dep。 GList pp。 if(!GL)return(1)。 //空表的深度為1 if(GLtag==ATOM)return(0)。 //原子的深度為0 for(max=0,pp=GL。pp。pp=pp) //計算所有子表的最大深度max { dep=GListDepth(pp)。 if(depmax) max=dep。 } return(max+1)。 //返回廣義表GL的深度max+1}2．求廣義表GL的長度的遞歸算法int GListLength(GList GL)該算法的遞歸過程是，廣義表GL的長度值=GL的尾表的長度值+1。其程序?qū)崿F(xiàn)代碼如下：int GListLength(GList GL){ int h。 if(!GL) h=0。 else h=GListLength(GL)+1。 return(h)。}3．將廣義表L復(fù)制到廣義表T的遞歸算法void CopyGList(GList amp。T,GList L)該算法的遞歸過程是，先復(fù)制廣義表的標志域(tag)再根據(jù)其值的不同情況復(fù)制廣義表的數(shù)據(jù)域(data)或指針域(ptr)中的表頭和表尾。其程序?qū)崿F(xiàn)代碼如下：void CopyGList(GList amp。T,GList L) //用遞歸方法完成由廣義表L復(fù)制得到廣義表T的操作{ if(!L)T=NULL。 else { T=new GLNode。 Ttag=Ltag。 if(Ltag==ATOM) T=L。 else { CopyGList(T,L)。 //復(fù)制廣義表L的表頭到T CopyGList(T,L)。 //復(fù)制廣義表L的表尾到T } }}4．由廣義表字符序列str創(chuàng)建廣義鏈表L的遞歸算法：void CreateGList(GListamp。 L,AtomType* str)(1) 函數(shù)void Sever(AtomType* amp。str,AtomType* amp。hstr)的功能是，從str中取出所有括號”()”之外的第一個逗號39。,39。之前的子字符串賦給hstr，并且使str成為刪去子串hstr和39。,39。之后的剩余串。若str中沒有逗號39。,39。，則將str復(fù)制到hstr中并使str=NULL。比如：操作前str=”((a),b),(((c))),(d,e),((f))”，操作后的結(jié)果為str=”(((c))),(d,e),((f))”，hstr=”((a),b)”。void Sever(AtomType* amp。str,AtomType* amp。hstr){ int i,j=0,k。 AtomType ch。 for(i=0,k=0。(ch=str[i])amp。amp。(ch!=39。,39。||k!=0)。i++) // k表示”(”的重數(shù) {//程序從str中逐個復(fù)制字符到htsr中，直到遇見”()”之外的第一個逗號39。,39?；騭tr結(jié)束為止 hstr[i]=ch。 if(ch==39。(39。)k++。 else if(ch==39。)39。)k。 } hstr[i]=39。\039。 if(ch==39。,39。) while(str[j++]=str[++i])。 //從str中刪除hstr else str[0]=39。\039。}(2) 用遞歸算法由str創(chuàng)建廣義鏈表L的過程是：1）如果str=”()”，L=NULL返回，否則先建立一個結(jié)點(GLNode)使L指向該結(jié)點，執(zhí)行2）。2）如果str中只有原子(ATOM)數(shù)據(jù)，則Ltag=ATOM。 L=str[0]。返回，否則執(zhí)行3）。3）Ltag=LIST。 p=L。取str中所有子表組成的串sub，執(zhí)行4）。4）逐個創(chuàng)建p的每一個子廣義鏈表。其程序?qū)崿F(xiàn)代碼如下：void CreateGList(GListamp。 L,AtomType* amp。str){ int n=0,i,j。 GList p。 while(str[n])n++。 AtomType* hstr=new AtomType[n+1]。 AtomType* sub=new AtomType[n+1]。 if(str[0]==39。(39。amp。amp。str[1]==39。)39。amp。amp。!str[2]) L=NU