【正文】 pe))。 hdata=d。hnext=NULL。t=h。 } else/*建立其余節(jié)點*/ { s=(nodetype *)malloc(sizeof(nodetype))。 sdata=d。snext=NULL。tnext=s。 t=s。/*始終指向生成的單鏈表的最后一個節(jié)點*/ } i++。 } return h。}void disp(nodetype *h)/*輸出由h指向的單鏈表的所有data域之值*/{ nodetype *p=h。 printf(輸出一個單鏈表:\n )。 if(p==NULL) printf(空表)。 while (p!=NULL) { printf(%d ,pdata)。 p=pnext。 } printf(\n)。}int len(nodetype *h)/*返回單鏈表的長度*/{ int i=0。 nodetype *p=h。 while(p!=NULL) { p=pnext。 i++。 } return i。}nodetype find(nodetype *h,int i)/*返回第i個節(jié)點的指針*/{ nodetype *p=h。 int j=1。 if(ilen(h)||i=0) return NULL。/*i上溢或下溢*/ else { while (p!=NULLamp。amp。ji)/*查找第i個節(jié)點，并由p指向該節(jié)點*/ { j++。 p=pnext。 } return p。 }}nodetype *ins(nodetype *h,int i,elemtype x)/*單鏈表head中第i個節(jié)點(i=0)之后插入一個data域為x的節(jié)點*/{ nodetype *p,*s。 s=(nodetype *)malloc(sizeof(nodetype))。/*創(chuàng)建節(jié)點s*/ sdata=x。 snext=NULL。 if(i==0)/*i=0:s作為單鏈表的第一個節(jié)點*/ { snext=h。 h=s。 } else { p=find(h,i)。/*查找第i個節(jié)點，并由p指向該節(jié)點*/ if(p!=NULL) { snext=pnext。 pnext=s。 } else printf(輸入的i值不正確\n)。 } return h。}nodetype *del(nodetype *n,int i)/*刪除第i個節(jié)點*/{ nodetype *p=h,*s。 int j=1。 if(i==1)/*刪除第一個節(jié)點*/ { h=hnext。 free(p)。 } else { p=find(h,i1)。/*查找第i1個節(jié)點，并由p指向該節(jié)點*/ if(p!=NULLamp。amp。pnext!=NULL) { s=pnext。/*s指向要刪除的節(jié)點*/ pnext=snext。 free(s)。 } else printf(輸入的i值不正確\n)。 } return h。}void dispose(nodetype *h)/*釋放單鏈表的所有節(jié)點占有的空間*/{ nodetype *pa=h,*pb。 if(pa!=NULL) { pb=panext。 if(pb=NULL)/*只有一個節(jié)點的情況*/ free(pa)。 else { while(pb!=NULL)/*有兩個及兩個以上的節(jié)點的情況*/ { free(pa)。 pa=pb。 pb=pbnext。 } free(pa)。 } }}/*試寫一算法，對單鏈表實現(xiàn)就地逆置*/includeincludenodetype *invert(nodetype *h)/*實現(xiàn)單鏈表逆置*/{ nodetype *p,*q,*r。 if(len(h)=1) { printf(逆置的單鏈表至少有2個節(jié)點\n)。 return NULL。 } else { p=h。 q=pnext。 while(q!=NULL) { r=qnext。 qnext=p。 p=q。q=r。 } hnext=NULL。 h=p。 return h。 }}void main(){ nodetype *head。 head=create()。 disp(head)。 head=invert(head)。 disp(head)。}/*運行結(jié)果建立一個單鏈表 輸入第1節(jié)點data域值：1輸入第2節(jié)點data域值：2輸入第1節(jié)點data域值：3輸入第1節(jié)點data域值：4輸入第1節(jié)點data域值：5輸入第1節(jié)點data域值：0輸出一個單鏈表1 2 3 4 5 輸出一個單鏈表5 4 3 2 1 *//*設(shè)線性表A=（a1,a2,…,am）,B=(b1,b2,…,bn),試寫一個按下列規(guī)則合并A，B為線性表C的算法，即使得C=（a1,b1,…,am,bm,bm+1,…,bm） 當(dāng)m=n時，或者C=(a1,b1,…,an,bn,an+1,…,am) 當(dāng)mn時。線性表A，B和C均以單鏈表做存儲結(jié)構(gòu)，且C表利用A表和B表中的結(jié)點空間構(gòu)成。注意：單鏈表的長度值m和n均未顯示存儲*/includenodetype *bine(nodetype *ha,nodetype *hb){ nodetype *hc=ha,*pa=ha,*pb=hb,*q,*r。 if(len(pa)!=len(pb)) { printf(兩個單鏈表長度不同\n)。 return NULL。 } while(pa!=NULL) { q=panext。 r=pbnext。 panext=pb。 pbnext=q。 pa=q。 pb=r。 } return(hc)。}void main(){ nodetype *heada,*headb,*headc。 heada=create()。 headb=create()。 headc=bine(heada,headb)。 disp(headc)。}includenodetype *connect(nodetype *h1,nodetype *h2){ nodetype *pa=h1,*pb=h2,*h3,*pc。 h3=(nodetype *)malloc(sizeof(nodetype))。/*創(chuàng)建哨兵*/ pc=h3。/*pc總是指向生成的新單鏈表的最后一個節(jié)點*/ while(pa!=NULLamp。amp。pb!=NULL) if(padatapbdata) { pcnext=pa。pc=pa。 pa=panext。 } else if(padatapbdata) { pcnext=pb。pc=pb。 pb=pbnext。 } else/*padata=pbdata的情況*/ { pcnext=pa。pc=pa。 pa=panext。pb=pbnext。 } if(pa!=NULL) pcnext=pa。/*h1單鏈表還有節(jié)點時*/ if(pb!=NULL) pcnext=pb。/*h2單鏈表還有節(jié)點時*/ pc=h3。/*刪除哨兵*/ h3=h3next。 free(pc)。 return h3。}void main(){ nodetype *head1,*head2,*head3。 head1=create()。 head2=create()。 disp(head1)。 disp(head2)。 head3=connect(head1,head2)。 disp(head3)。}includeincludetypedef struct dnode{ int data。 struct dnode *link。}dlist。dlist *xor(dlist *p1,dlist *p2)/*在c/c++中異或運算符不能對地址進(jìn)行異或運算，所以先將地址值轉(zhuǎn)換為長整形，然后進(jìn)行異或運算，再將結(jié)果強(qiáng)制轉(zhuǎn)換成地址。這是本函數(shù)的功能*/{ int add1,add2,add3。 add1=(long)p1。 add2=(long)p2。 add3=add1^add2。 return(dlist *)add3。}dlist *create(dlist **e){ int i=1,x。 dlist *head,*r,*s,*pre。 printf(創(chuàng)建一個雙鏈表(以0結(jié)束)\n)。 while(1) { printf( 輸入第%d節(jié)點值: ,i)。 scanf(%d,amp。x)。 if(x==0)/*生成最后一個節(jié)點的link值后退出循環(huán)*/ { prelink=xor(r,NULL)。 /*將slink置為前后節(jié)點地址之異或*/ *e=pre。 break。 } s=(dlist *)malloc(sizeof(dlist))。/*創(chuàng)建一個節(jié)點*/ sdata=x。 if(i==1)/*是第一個節(jié)點的情況*/ { pre=head=s。r=NULL。/*r為當(dāng)前節(jié)點的前一個節(jié)點*/ } else { prelink=xor(r,s)。 /*將slink置為前后節(jié)點地址之異或*/ r=pre。 pre=s。 } i++。 } return head。}void order(dlist *h,dlist *e){ dlist *pre=NULL,*pre1,*p=h。 printf(遍歷節(jié)點序列: )。 if(h==NULL) printf(空表\n)。 else { while(p!=e)/*遍歷最后一節(jié)點前的所有節(jié)點*/ { printf(%d ,pdata)。 pre1=p。 p=xor(pre,plink)。/*為下一個節(jié)點的地址*/ pre=pre1。 } printf(%d ,edata)。 printf(\n)。 }}void main(){ dlist *h,*e。 int i。 h=create(amp。e)。 printf(從左向右)。 order(h,e)。 printf(從右向左)。 order(e,h)。}/*運行結(jié)果:創(chuàng)建一個雙鏈表(以0結(jié)束) 輸入第1節(jié)點值:3輸入第1節(jié)點值:5輸入第1節(jié)點值:8輸入第1節(jié)點值:2輸入第1節(jié)點值:6輸入第1節(jié)點值:0從左向右遍歷節(jié)點序列: 3 5 8 2 6 從右向左遍歷節(jié)點序列: 6 2 8 5 3 */第三章 棧和隊列：includedefine MaxLen 20/*順序棧存放的最多元素個數(shù)為Maxlen1*/typedef char elemtype。typedef struct sqstack{ elemtype data[MaxLen]。 int top。}stack。void init(stack *st)/*初始化棧st*/{ sttop=0。}int push(stack *st,elemtype x)/*入棧*/{ if(sttop==MaxLen1) { printf(棧溢出\n)。 ret