【導讀】頭文件，運行時只需將頭文件與相應算法連接即可。/*設順序表va中的數(shù)據(jù)元素遞增有序。試寫一算法，將x插入到順序表的適當位置上，以保持該表的有序。,bm)均為順序表，A’和B’分別為A和B中除去最大共同前綴后的子表（例。若A’=B’=空表，則A=B;若A’=空表，B’!=空表，或者兩者均不。試寫一個比較A,B大小的算法（請注意：在算

　　

【正文】 { k++。j++。 } if(j==s2len)/*s2 中止時找到了子串 */ break。 else i++。 } else i++。 } if(is1len) return 1。 else return (i+1)。 } void delall(strtype *s1,strtype *s2) { int n。 n=index(s1,s2)。 while(n=0) { del(s1,n,length(s2))。 n=index(s1,s2)。 } diap(s1)。 } void main() { strtype s1,s2。 char str[MaxLen]。 printf(字符串 : )。 gets(str)。 create(amp。s1,str)。 printf(子串 : )。 gets(str)。 create(amp。s2,str)。 delall(amp。s1,amp。s2)。 } 第五章 數(shù)組與廣義表 實現(xiàn)廣義表基本運算的頭文件 如下 : include include include define MaxLen 100 32 typedef struct node/*定義廣義表結構 */ { int tag。/*只取 0（原子節(jié)點）或 1（表節(jié)點） */ struct node *link。/*后繼節(jié)點 */ union { char data。 struct node *slist。/*子表 */ }val。 }gnode。 void disastr(char s[],char hstr[])/*本函數(shù)為輔助建立廣義表的函數(shù)從字符串 s中取出第一個 39。,39。之前的子串賦給hstr,并使 s 成為刪除子串 hstr 和 39。,39。之后的剩余串。若串 s 中沒有字符 39。,39。，則操作后的 hstr 為操作前的 s,而操作后的 s 為空串 */ { int i=0,j=0,k=0,r=0。 char rstr[MaxLen]。 while(s[i]amp。amp。(s[i]!=39。,39。||k)) { if(s[i]==39。(39。) k++。 else if(s[i]==39。)39。) k。 if(s[i]!=39。,39。||s[i]==39。,39。amp。amp。k) { hstr[j]=s[i]。 i++。j++。 } } hstr[j]=39。\039。 if(s[i]==39。,39。) i++。 while(s[i]) { rstr[r]=s[i]。 r++。i++。 } rstr[r]=39。\039。 strcpy(s,rstr)。 } gnode *create(char s[])/*從字符串表示創(chuàng)建廣義表 */ { gnode *p,*q,*r,*gh。 char subs[MaxLen],hstr[MaxLen]。 int len。 len=strlen(s)。 if(!strcmp(s,()))/*空表的情況 */ gh=NULL。 33 else if(len==1)/*原子的情況 */ { gh=(gnode *)malloc(sizeof(gnode))。/*建立一個新節(jié)點 */ ghtag=0。/*構造原子節(jié)點 */ gh=*s。 ghlink=NULL。 } else/*子表的情況 */ { gh=(gnode *)malloc(sizeof(gnode))。/*建立一個新節(jié)點 */ ghtag=1。 p=gh。 s++。/*除掉前面的一個 39。(39。*/ strncpy(subs,s,len2)。 subs[len2]=39。\039。 do { disastr(subs,hstr)。/*將 subs 分為表頭和表尾 */ r=create(hstr)。 p=r。 q=p。 len=strlen(subs)。 if(len0) { p=(gnode *)malloc(sizeof(gnode))。 ptag=1。 qlink=p。 } }while(len0)。 qlink=NULL。 } return(gh)。 } void disp(gnode *h)/*以字符串方式輸出廣義表 */ { gnode *p,*q。 printf(()。 if(h) do { p=h。 q=hlink。 while(qamp。amp。pamp。amp。!ptag)/*為原子且有后繼節(jié)點的情況 */ 34 { printf(%d ,p)。 p=q。 q=qlink。 } if(pamp。amp。!ptag)/*為原子之后繼節(jié)點的情況 */ { printf(%d,p)。 break。 } else/*為子表的情況 */ { if(!p) printf(())。 else disp(p)。 if(q) printf(,)。 h=q。 } }while(h)。 printf())。 } int locate(gnode *p,char x)/*判斷 x 是否在廣義表中 */ { int find=0。 if(p!=NULL) { if(!ptagamp。amp。p==x) return(1)。 else if(ptag) find=locate(p,x)。 if(find) return(1)。 else return(locate(plink,x))。 } else return(0)。 } 練習 /*復制廣義表 */ include void gcope(gnode *p,gnode *q) { 35 if(p=NULL)。 q=NULL。 else { q=(gnode *)malloc(sizeof(gnode))。/*創(chuàng)建一個節(jié)點 */ qtag=ptag。 if(ptag==0) q=p。/*原子節(jié)點直接復制 */ else { gcopy(p,q)。 gcopy(plink,qlink)。 } } } void main() { gnode *p,*q。 char str[MaxLen]。 printf(輸入廣義表表達式 : )。 scanf(%s,str)。 p=create(str)。 printf(原來的廣義表 : )。 disp(p)。 gcopy(p,q)。 printf(\n 復制的廣義表 : )。 disp(q)。 printf(\n)。 } 練習 /*判別廣義表是否相等的遞歸算法 */ include int same(gnode *p,gnode *q) { int flag=1。 if(p!=NULLamp。amp。q!=NULL) { if(ptag==0amp。amp。ptag!=0) if(p!=q) flag=0。 else if(ptag==1amp。amp。qtag==1) flag=same(p,q)。 else flag=0。 if(flag) 36 flag=same(plink,qlink)。 } else { if(p==NULLamp。amp。q!=NULL) flag=0。 if(p!=NULLamp。amp。q==NULL) flag=1。 } return (flag)。 } void main() { gnode e,*g1,*g2,*g3。 g1=create((a,(b,c,d),e,((f))))。 g2=create((a,(b,c,d),e,((f))))。 g3=create((a,(b),(c,d),e,(f)))。 printf(廣義表 g1: )。 disp(g1)。 printf(\n)。 printf(廣義表 g2: )。 disp(g2)。 printf(\n)。 printf(廣義表 g3: )。 disp(g3)。 printf(\n)。 printf(g1 與 g2:)。 printf((same(g1,g2)==0)?不同 : 相同 )。 printf(\n)。 printf(g1 與 g3:)。 printf((same(g1,g3)==0)?不同 : 相同 )。 } 練習 /*逆置廣義表 */ include void reverse(gnode *p,gnode *amp。q) { gnode *r,*s,*t,*b。 if(p==NULL) q=NULL。 else { if(ptag==0)/*為原子的情況 */ { 37 s=(gnode *)malloc(sizeof(gnode))。/*復制該原子節(jié)點 */ stag=0。 s=NULL。 s=p。 q=s。 } else/*為表的情況 */ { reverse(p,s)。/*處理表頭 */ if(plink!=NULL) { reverse(plink,t)。/*產生表尾的逆置廣義表 t*/ b=(gnode *)malloc(sizeof(gnode))。/*給表頭加上一個子表節(jié)點 */ btag=1。 blink=NULL。 b=s。 q=t。r=t。 while(rlink!=NULL)/*找到第一層的 最后一個節(jié)點 */ r=rlink。 rlink=b。/*連接 */ } else/*plink=NULL*/ { q=(gnode *)malloc(sizeof(gnode))。/*創(chuàng)建表頭節(jié)點 q*/ q=tag=1。 qlink=NULL。 q=s。 } } } } void main() { gnode *g1,*g2。 g1=create(((a,b),c,(d,e)))。 printf(廣義表 g1: )。 disp(g1)。 printf(\n)。 reverse(g1,g2)。 printf(由 g1 逆置為 g2\n)。 printf(廣義表 g1: )。 disp(g2)。 printf(\n)。 } 38 練習 /*刪除 x 項 */ include void delall(gnode *p,char x,gnode amp。*q) { gnode *s,*t。 if(p==NULL) q=NULL。 else { if(ptag==0)/*為原子節(jié)點的情況 */ { if(p!=x) { q=(gnode *)malloc(sizeof(gnode))。/*復制到原子節(jié)點 */ qtag=0。 q=p。 qlink=NULL。 } else q=NULL。/*返回空表 */ } else { delall(p,x,s)。/*刪除線性表頭中的 x 得到 s*/ if(s==NULL)/*新表的表頭為空的情況 */ { p=plink。 if(p!=NULL) { delall(p,x,t)。/*從表尾的表頭產生 t*/ q=(gnode *)malloc(sizeof(gnode))。 /*創(chuàng)建整個新表的表頭節(jié)點 q*/ qtag=1。 qlink=NULL。 q=t。/*將 t 作為新表