1、數據結構代碼p20，例 2-1void union (list &la, listlb)la_len= listlength (la); lb_len= listlength (lb);for (i=1;i= lb_len;i+)getelem (lb,i,e);if(!locateelem(la,e,equal) listinsert(la,+ la_len,e);p21,例 2-2,將void mergelist(list la,listlb,list&lc)initlist(lc);i=j=1;k=0;la_len=listlength(la);lb_len=listle

2、ngth (lb);while(i=la_len)&(j=lb_len)getelem(la,i,ai);getelem(lb,j,bj);if(ai= bj)listinsert(lc,+k, ai);+i;else listinsert(lc,+k, bj);+jwhile (i=la_len) getelem(la, i+, ai);listinsert(lc, +k, ai);while (j=lb_len) getelem(lb, i+, bj);listinsert(lc, +k, bj); p22,線性表的順序存儲結構#define list_init_size 100

3、#define listincrement 10 typedefstruct elemtype *elem; /* 線性表占用的數組空間*/int length；intlistsize; sqlist ；p23,線性表順序存儲結構上的基本運算初始化操作status inilist_sq(sqlist &l) l.elem=(elemtype*) malloc (list_init_size*sizeof (elemtype); if(!l.elem) exit(overflow); l.length=0; l.listsize=list_init_size; return ok; p2

4、4,在順序表里插入一個元素status listinsert_sq(sqlist&l, inti, elemtype e) if(i=l.length+1) return error; if(l.length=l.listsize) newbase=(elemtype*) realloc (l.elem, (l.listsize+listincrement)*sizeof (elemtype); if(!newbase)exit(overflow); l.elem=newbase; l.listsize+=listincrement; q=&(l.elemi-1); for(p

5、=&(l.eleml.length-1);p=q;-p) *(p+1)=*p; *q=e; +l.length; return ok ； p24,在順序表里刪除一個元素status listdelete_sq(sqlist&l,inti,elemtype&e) if( (il.length) ) return error; p=&(l.elemi-1); e=*p; q=l.elem+l.length-1; for(+p; p=q; +p) *(p-1)=*p; -l.length; return ok; p25,在順序表里查找一個元素intlocatelem_

6、sq(sqlistl,elemtype e, status(*compare)(elemtype, elemtype) i=1; p=l.elem; while (i=l.length& !(*compare)(*p+,e) +i; if (i=l.length) return i; else return 0; p26,順序表的合并voidmergelist_sq(sqlist la, sqlistlb, sqlist&lc ) pa=la.elem; pb=lb.elem; lc.listsize=lc.length=la.length+lb.length; pc=lc.e

7、lem=(elemtype*) malloc (lc.listsize*sizeof (elemtpe); if (!lc.elem) exit (overflow); pa_last=la.elem+la.length-1; pb_last=lb.elem+lb.length-1; while (pa=pa_last &pb=pb_last) if (*pa=*pb) *pc+=*pa+; else *pc+=*pb+; while(pa=pa_last) *pc+=*pa+; while(pbnext; j=1; while (p & jnext; +j; if ( !p

8、| ji) return error; e=p-data; return ok; p29,在單鏈表中插入一個元素status listinsert_l(linklist &l, int i, elmetype e ) p=l;j=0; while( p & jnext; +j; if( !p | ji-1) return error; s=(linklist) malloc(sizeof (lnode); s-data=e; s-next=p-next; p-next=s; return ok; p30,在單鏈表中刪除一個元素status listdelete_l(linkli

9、st &l, int i, elemtype &e) p=l;j=0; while ( p-next & jnext; +j; if ( !(p-next) | ji-1) return error ; q = p-next; p-next=q-next; e = q-data; free(q); return ok; p30,建立單鏈表void createlist_l(linklist &l, int n) l=(linklist) malloc(sizeof(lnode); l-next=null; for(i=n; i0; -i) p=(linklist

10、)malloc(sizeof(lnode); scanf(&p-data); p-next=l-next; l-next=p; p31,合并單鏈表void mergelist_l(linklist &la,linklist&lb,linklist &lc) pa=la-next; pb=lb-next; lc=pc=la; while( pa &pb) if( pa-data data) pc-next=pa; pc=pa; pa=pa-next; else pc-next=pb; pc=pb; pb=pb-next; pc-next= pa ? pa

11、:pb; free(lb); p31,線性表的靜態單鏈表存儲結構#define maxsize 1000 typedef struct elemtype data; int cur; component,slinklistmaxsize; p32,定位函數int locateelem_sl(slinklist s, elemtype e) i=s0.cur; while(i& si.data!=e) i=si.cur; return i; p33, void initespace_sl(slinklist &space) for(i=0; i= s.stacksize) s.b

12、ase=(selemtype*) realloc (s.base, (s.stacksize+stackincrement)*sizeof(selemtype); if(!s.base) exit(overflow); s.top=s.base+s.stacksize; s.stacksize+=stackincrement; *s.top+=e; return ok; 出棧status pop(sqstack&s, selemtype&e) if(s.top= =s.base) return error; e=*-s.top; return ok; p48,轉換為 8 進制v

13、oid conversion () initstack(s); scanf( “%d ”,&n);while(n) push(s, n % 8 ); n=n / 8; while( !stackempty(s) pop(s,e); printf(“%d ”,e); p55,移動圓盤void hanoi(intn,charx,chary,char z) /* 將塔座 x上按直徑由小到大且至上而下編號為 1 至 n 的 n 個圓盤按規則搬到塔座z上，y可用作輔助塔座*/if(n=1)move(x,1,z); /* 將編號為 1 的圓盤從 x移動 z */else hanoi(n-1,x,z

14、,y); /* 將 x上編號為 1 至 n-1 的圓盤移到 y,z作輔助塔 */move(x,n,z); /* 將編號為 n 的圓盤從 x移到 z */hanoi(n-1,y,x,z); /* 將 y上編號為 1 至 n-1 的圓盤移動到 z，x作輔助塔*/ p61,鏈式隊列的定義define true 1define false 0typedefstructqnode qelemtype data; structqnode *next; qnode, *queueptr; typedefstruct queueptr front; queueptr rear; linkqueue; p62,

15、初始化status initqueue(linkqueue&q) q.front = q.rear = (queueptr) malloc(sizeof(qnode); if(!q.front) exit ( overflow); q.front -next = null; return ok; 銷毀隊列status destroyqueue(linkqueue&q) while(q.front) q.rear = q.front-next; free (q.front); q.front = q.rear; return ok; 入隊操作status enqueue (lin

16、kqueue&q, qelemtype e) p= (queueptr) malloc(sizeof(qnode); if (!p) exit ( overflow); p-data = e; p-next = null; q.rear - next =p; q.rear = p; return ok; 出隊操作status dequeue (linkqueue&q, qelemtype&e) if ( q.front = q.rear) return error; p=q.front-next; e=p-data; q.front-next =p-next; if (

17、q.rear = p) q.rear = q.front; free(p); return ok; p64，循環對列定義#define maxqsize 100 /* 隊列的最大長度 */ typedefstruct qelemtype *base; /* 隊列的元素空間 */ int front; /* 頭指針指示器 * int rear; /* 尾指針指示器 */ sqqueue; 初始化操作status initqueue (sqqueue&q) q.base = (qelemtype* )malloc(maxqsize * sizeof (qelemtype); if ( !

18、q. base) exit (overflow); q. front = q. rear = 0; return ok; 入隊操作status enqueue (sqqueue&q, qelemtype e) if (q. rear+ 1) % maxqsize = q. front) return error; q.baseq.rear = e; q.rear = (q. rear + 1) % maxqsize; return ok; ）出隊操作status dequeue (sqqueue&q, qelemtype&e) if (q. front = = q. r

19、ear) return error; e = q. baseq. front; q. front = (q. front + 1) % maxqsize; return ok; 求隊列長度intqueuelength (sqqueue q) return (q. rear - q. front + maxqsize) % maxqsize; p93/-數組的順序存儲表示include # define max_array_dim 8 typedefstruct elemtype *base; / 數組元素基址int dim; / 數組維數int *bounds; / 數組維數基址int *co

20、nstants; / 數組映像函數常量基址array; p98,三元數組順序表存儲# definemaxsize 12500 typedefstruct inti, j ; elemtypee ; triple ; typedef union triple data maxsize+1 ; int mu, nu, tu ; tsmatrix ; p99，矩陣轉置status transposesmatrix( tsmatrix m, tsmatrix& t ) t.mu=m.nu; t.nu=m.mu; t.tu=m.tu; if(t.tu ) q=1; for( col=1; col

21、=m.nu; +col) for( p=1; p=m.tu; +p ) if(m.datap.j = col ) t.dataq.i = m.datap.j ; t.dataq.j = m.datap.i ; t.dataq.e = m.datap.e ; + q; return ok; / transposesmatrix p100 status fasttransposesmatrix( tsmatrix m, tsmatrix&t ) / 采用三元組順序表存儲表示，求稀疏矩陣m 的轉置矩陣 t。t.mu=m.nu; t.nu=m.mu; t.tu=m.tu; if(t.tu) f

22、or(col=1;colm.nu；col+) numcol=0; for(t=1; t=m.nu;+t) +numm.datat.j; / 求 m 中每一列含非零元個數。copt1=1; / 求第 col 列中第一個非零元在b.data 中的序號for(col=2;col=m.nu; +col) cpotcol=cpotcol-1+numcol-1; for(p=1; pdata ) ) 5 if ( preordertraverse ( t-lchild , visit ) ) 6 if ( preordertraverse ( t-rchild, visit ) ) return ok;

23、7 return error; 8 9 else return ok; 10 中序遍歷status inordertraverse ( bitree t, status ( * visit ) ( telemtype e ) ) 1 2 if ( t ) 3 4 if ( inordertraverse ( t-lchild , visit ) ) 5 if ( visit ( t-data ) ) 6 if ( inordertraverse ( t-rchild, visit ) ) return ok; 7 return error; 8 9 else return ok; 10 p13

24、1,中序遍歷二叉樹status inordertraverse(bitree t, status ( * visit ) ( telemtype e ) ) initstack( s ); push ( s, t ); while( !stackempty ( s ) ) while ( gettop ( s, p ) &p) push ( s, p-lchild ); pop ( s, p ); if ( !stackempty ( s ) ) pop ( s, p ); if ( !visit ( p-data ) ) return error; push ( s, p-rchil

25、d ); / if / while return ok; / inordertraverse status inordertraverse( bitree t, status ( *visit ) ( telemtype e ) ) initstack( s ); p=t; while ( p | !stackempty ( s ) ) if ( p ) push ( s, p ); p=p-lchild; else pop ( s, p ); if ( !visit ( p-data ) ) return error; p=p-rchild; return ok; void preorder

26、(bitree root) /* 先序遍歷輸出二叉樹中的葉子結點, root 為指向二叉樹根結點的指針*/ if (root! =null) if (root -lchild=null & root -rchild=null)printf (root -data); /* 輸出葉子結點*/preorder(root -lchild); /* 先序遍歷左子樹*/preorder(root -rchild); /* 先序遍歷右子樹*/ 統計葉子結點數目leafcount是保存葉子結點數目的全局變量, 調用之前初始化值為0 */void leaf(bitree root)if(root! =

27、null)leaf(root-lchild); leaf(root-rchild); if (root -lchild=null & root -rchild=null)leafcount+; /* 采用遞歸算法，如果是空樹，返回0；如果只有一個結點，返回1；否則為左右子樹的葉子結點數之和*/int leaf(bitree root)intleafcount; if(root=null) leafcount =0; else if(root-lchild=null)&(root-rchild=null)leafcount =1; else leafcount =leaf(root-lchild)+leaf(root-rchild); /* 葉子數為左右子樹的葉子數目之和*/returnleafcount; p131,建立二叉鏈表方式存儲的二叉樹status createbitree(bitree&t ) scanf ( &ch ); if ( ch = ) t = null;else if ( !( t=( bitnode * ) malloc (sizeof(bitnode ) ) ) ) exit ( overflow ); t-data=ch; c