數(shù)據(jù)結(jié)構(gòu)的語言算法

1、數(shù)據(jù)結(jié)構(gòu)的語言算法 以下數(shù)據(jù)結(jié)構(gòu)算法由C語言編譯，并在TC上運(yùn)行通過，其中，擴(kuò)展名為”.CPP”的為頭文件，運(yùn)行時(shí)只需將頭文件與相應(yīng)算法連接即可。第一章 緒論（預(yù)備知識）練習(xí)1.16/*試寫一算法,自大至小輸出順序讀入的三個(gè)整數(shù)X,Y和Z的值*/62#include void swap(int *x,int *y,int *z) int t; if(*x*y) t=*x;*x=*y;*y=t; if(*y*z) t=*y;*y=*z;*z=t; if(*x*y) t=*x;*x=*y;*y=t; main()int a,b,c;scanf(%d,%d,%d,&a,&b,&c);swap(&a,

2、&b,&c);printf(%d %d %d,a,b,c);第二章 線性表1順序表實(shí)現(xiàn)順序表基本算法的頭文件sq.cpp為：#include#define MaxLen 50/*順序表中最多元素個(gè)數(shù)*/typedef int elemtype;typedef elemtype sqlistMaxLen;int create(sqlist A)/*創(chuàng)建線形表*/ int i,n; printf(創(chuàng)建一個(gè)順序表：n); printf(輸入元素個(gè)數(shù)：); scanf(%d,&n); for(i=0;in;i+) printf(輸入第%d個(gè)元素值:,i+1); scanf(%d,&Ai); retur

3、n n;void disp(sqlist A,int n)/*輸出一個(gè)順序表*/ int i; printf(輸出一個(gè)順序表: n); if(n=0) printf(空表); for(i=0;in;i+) printf(%d ,Ai); printf(n);int ins(sqlist A,int n,int i,elemtype x)/*在順序表第i個(gè)元素前插入一個(gè)元素x,若i=0,則新元素作為第一個(gè)元素,若i=1,則插入在最后*/ int j; if(in) printf(i值下溢或上溢n); else for(j=n-1;j=i;j-) Aj+1=Aj; /*將第i個(gè)元素及其后的元素后移

4、*/ Ai=x;n+;/*順序表長度加1*/ return n;int del(sqlist A,int n,int i)/*在順序表中刪除第i個(gè)元素*/ int j; if(in) printf(i值下溢或上溢n); else for(j=i-1;jn;j+) Aj=Aj+1; /*將第i個(gè)元素之后的元素前移覆蓋Ai*/ n-; /*順序表長度減1*/ return n;int find(sqlist A,int n,elemtype x)/*在一個(gè)有n個(gè)元素的順序表A中查找元素值為x的元素*/ int i=0; while(i=n&Ai!=x) i+; if(i=An-1) An=x; /

5、*若x大于最后的元素，則將其插入到最后*/ else i=0; while(xAi) i+;/*查找插入位置i*/ for(j=n;j=i;j-) Aj+1=Aj; /*移出插入x的位置*/ Ai=x; return (n+1);/*順序表長度增1*/void main() sqlist A; int n; n=create(A); disp(A,n); n=insert(A,n,10);/*插入元素10*/ disp(A,n); getch();/*運(yùn)行結(jié)果：創(chuàng)建一個(gè)順序表 輸入元素個(gè)數(shù)：3 輸入第1個(gè)元素值：6輸入第1個(gè)元素值：9輸入第1個(gè)元素值：14輸出一個(gè)順序表6 9 14輸出一個(gè)順序

6、表6 9 10 14 */練習(xí)2.12/*設(shè)A=（a1,am）和B=(b1,bm)均為順序表，A和B分別為A和B中除去最大共同前綴后的子表（例如，A=（x,y,y,z,x,z）,B=(x,y,y,z,y,x,x,z),則兩者中最大的共同前綴為（x,y,y,z），在兩表中除去最大的共同前綴后的子表分別為A=(x,z)和B=(y,x,x,z)。若A=B=空表，則A=B;若A=空表，B!=空表，或者兩者均不為空表，且A的首元小于B的首元，則AB。試寫一個(gè)比較A,B大小的算法（請注意：在算法中，不要破壞原表A和B，并且，也不一定先求得A和B才能進(jìn)行比較）*/#includesq.cppint comp

7、(sqlist A,int na,sqlist B,int nb) int i=0,j=0;while(ina&jnb&Ai+=Bj+);/*比較相同部分*/i-;j-;if(i=na&j=nb) return 0;/*a=b*/if(i=na&j!=nb) return -1;/*ab*/if(AiBj)return 1;else return -1;void main() sqlist A,B;int na,nb,n;na=create(A);nb=create(B);n=comp(A,na,B,nb);switch(n)case 0:printf(A=Bn); break;case 1:

8、printf(ABn); break;case -1:printf(AB*/練習(xí)2.16/*刪除A中第i個(gè)元素起的k個(gè)元素*/#includesq.cppint delk(sqlist A,int *n,int i,int k)int j;if(i*n)printf(i,k參數(shù)不正確n);return 0;elsefor(j=i+k-1;j*n;j+)Aj-k=Aj;(*n)-=k;return 1;void main()sqlist A;int n,i,k;n=create(A);disp(A,n);printf(輸入i,k:);scanf(%d %d,&i,&k);if(delk(A,&n

9、,i,k)=1)disp(A,n); getch(); /*運(yùn)行結(jié)果：創(chuàng)建一個(gè)順序表 輸入元素個(gè)數(shù)：5輸入第1個(gè)元素值：1輸入第1個(gè)元素值：2輸入第1個(gè)元素值：3輸入第1個(gè)元素值：4輸入第1個(gè)元素值：5輸出一個(gè)順序表1 2 3 4 5輸入I,k:2 2輸出一個(gè)順序表1 4 5 */ 練習(xí)2.21/*試寫一算法,實(shí)現(xiàn)順序表的就地逆置,即利用原表的存儲空間將線性表(a1,a2,.,an)逆置為(an,an-1,.,a1).*/#includesq.cppvoid invert(sqlist A,int n) int m=n/2,i; /*m為長度的一半即n2*/ elemtype temp; fo

10、r(i=0;i=0&j=0)if(Ai-1Bj-1)i-;elseif(Ai-1Bj-1)j-;else/*Ai-1=Bj-1*/Ck+=Ai-1;i-;j-;return k-1;void main()sqlist A,B,C;int na,nb,nc;na=create(A);disp(A,na);nb=create(B);disp(B,nb);nc=intersect(A,na,B,nb,C);disp(C,nc);/*習(xí)題2.25*/*假設(shè)以兩個(gè)元素依值遞增有序排列的線性表A和B分別表示兩個(gè)集合(即同一表中的元素值各不相同),現(xiàn)要求另開辟空間構(gòu)成一個(gè)線性表C,其元素為A和B中元素的交集

11、,且表C中的元素也依值遞增有序排列.試對順序表編寫求C的算法*/#includesq.cppint unions(sqlist A,int na,sqlist B,int nb,sqlist C)int i=0,j=0,k=0;while(ina&jnb)if(AiBj)Ck+=Bj+;else/*Ai=Bi*/Ck+=Ai;i+;j+;if(ina)/*A還有元素*/for(j=i;jna;j+)Ck+=Aj;else if(jnb)/*B還有元素*/for(i=j;inb;i+)Ck+=Bi;return k;void main()sqlist A,B,C;int na,nb,nc;na=

12、create(A);disp(A,na);nb=create(B);disp(B,nb);nc=unions(A,na,B,nb,C);disp(C,nc);2. 線性表實(shí)現(xiàn)線性表基本算法的頭文件slink.cpp為：#include#includetypedef int elemtype;/*定義數(shù)據(jù)域的類型*/typedef struct linknode/*定義節(jié)點(diǎn)類型*/ elemtype data; struct linknode *next;nodetype;nodetype *create()/*建立單鏈表，由用戶輸入各節(jié)點(diǎn)data域之值，以0表示輸入結(jié)束*/ elemtype

13、d; nodetype *h=NULL,*s,*t; int i=1; peintf(建立一個(gè)單鏈表n); while(1) printf( 輸入第%d個(gè)節(jié)點(diǎn)data域值:,i); scanf(%d,&d); if(d=0) break;/*以0表示輸入結(jié)束*/ if(i=1)/*建立第一個(gè)節(jié)點(diǎn)*/ h=(nodetype *)malloc(sizeof(nodetype); h-data=d;h-next=NULL;t=h; else/*建立其余節(jié)點(diǎn)*/ s=(nodetype *)malloc(sizeof(nodetype); s-data=d;s-next=NULL;t-next=s;

14、 t=s;/*始終指向生成的單鏈表的最后一個(gè)節(jié)點(diǎn)*/ i+; return h;void disp(nodetype *h)/*輸出由h指向的單鏈表的所有data域之值*/ nodetype *p=h; printf(輸出一個(gè)單鏈表:n ); if(p=NULL) printf(空表); while (p!=NULL) printf(%d ,p-data); p=p-next; printf(n);int len(nodetype *h)/*返回單鏈表的長度*/ int i=0; nodetype *p=h; while(p!=NULL) p=p-next; i+; return i;node

15、type find(nodetype *h,int i)/*返回第i個(gè)節(jié)點(diǎn)的指針*/ nodetype *p=h; int j=1; if(ilen(h)|i=0) return NULL;/*i上溢或下溢*/ else while (p!=NULL&jnext; return p; nodetype *ins(nodetype *h,int i,elemtype x)/*單鏈表head中第i個(gè)節(jié)點(diǎn)(i=0)之后插入一個(gè)data域?yàn)閤的節(jié)點(diǎn)*/ nodetype *p,*s; s=(nodetype *)malloc(sizeof(nodetype);/*創(chuàng)建節(jié)點(diǎn)s*/ s-data=x; s

16、-next=NULL; if(i=0)/*i=0:s作為單鏈表的第一個(gè)節(jié)點(diǎn)*/ s-next=h; h=s; else p=find(h,i);/*查找第i個(gè)節(jié)點(diǎn)，并由p指向該節(jié)點(diǎn)*/ if(p!=NULL) s-next=p-next; p-next=s; else printf(輸入的i值不正確n); return h;nodetype *del(nodetype *n,int i)/*刪除第i個(gè)節(jié)點(diǎn)*/ nodetype *p=h,*s; int j=1; if(i=1)/*刪除第一個(gè)節(jié)點(diǎn)*/ h=h-next; free(p); else p=find(h,i-1);/*查找第i-1個(gè)

17、節(jié)點(diǎn)，并由p指向該節(jié)點(diǎn)*/ if(p!=NULL&p-next!=NULL) s=p-next;/*s指向要?jiǎng)h除的節(jié)點(diǎn)*/ p-next=s-next; free(s); else printf(輸入的i值不正確n); return h;void dispose(nodetype *h)/*釋放單鏈表的所有節(jié)點(diǎn)占有的空間*/ nodetype *pa=h,*pb; if(pa!=NULL) pb=pa-next; if(pb=NULL)/*只有一個(gè)節(jié)點(diǎn)的情況*/ free(pa); else while(pb!=NULL)/*有兩個(gè)及兩個(gè)以上的節(jié)點(diǎn)的情況*/ free(pa); pa=pb;

18、pb=pb-next; free(pa); 練習(xí)2.22/*試寫一算法，對單鏈表實(shí)現(xiàn)就地逆置*/#includeslink.cpp#includenodetype *invert(nodetype *h)/*實(shí)現(xiàn)單鏈表逆置*/nodetype *p,*q,*r;if(len(h)next;while(q!=NULL)r=q-next;q-next=p;p=q;q=r;h-next=NULL;h=p;return h;void main()nodetype *head;head=create();disp(head);head=invert(head);disp(head);/*運(yùn)行結(jié)果建立一個(gè)

19、單鏈表 輸入第1節(jié)點(diǎn)data域值：1輸入第2節(jié)點(diǎn)data域值：2輸入第1節(jié)點(diǎn)data域值：3輸入第1節(jié)點(diǎn)data域值：4輸入第1節(jié)點(diǎn)data域值：5輸入第1節(jié)點(diǎn)data域值：0輸出一個(gè)單鏈表1 2 3 4 5 輸出一個(gè)單鏈表5 4 3 2 1 */練習(xí)2.23/*設(shè)線性表A=（a1,a2,am）,B=(b1,b2,bn),試寫一個(gè)按下列規(guī)則合并A，B為線性表C的算法，即使得C=（a1,b1,am,bm,bm+1,bm） 當(dāng)mn時(shí)。線性表A，B和C均以單鏈表做存儲結(jié)構(gòu)，且C表利用A表和B表中的結(jié)點(diǎn)空間構(gòu)成。注意：單鏈表的長度值m和n均未顯示存儲*/#includeslink.cppnodetyp

20、e *combine(nodetype *ha,nodetype *hb)nodetype *hc=ha,*pa=ha,*pb=hb,*q,*r;if(len(pa)!=len(pb)printf(兩個(gè)單鏈表長度不同n);return NULL;while(pa!=NULL)q=pa-next;r=pb-next;pa-next=pb;pb-next=q;pa=q;pb=r;return(hc);void main()nodetype *heada,*headb,*headc;heada=create();headb=create();headc=combine(heada,headb);di

21、sp(headc);練習(xí)2.26#includeslink.cppnodetype *connect(nodetype *h1,nodetype *h2)nodetype *pa=h1,*pb=h2,*h3,*pc;h3=(nodetype *)malloc(sizeof(nodetype);/*創(chuàng)建哨兵*/pc=h3;/*pc總是指向生成的新單鏈表的最后一個(gè)節(jié)點(diǎn)*/while(pa!=NULL&pb!=NULL)if(pa-datadata)pc-next=pa;pc=pa;pa=pa-next;elseif(pa-datapb-data)pc-next=pb;pc=pb;pb=pb-nex

22、t;else/*pa-data=pb-data的情況*/pc-next=pa;pc=pa;pa=pa-next;pb=pb-next;if(pa!=NULL) pc-next=pa;/*h1單鏈表還有節(jié)點(diǎn)時(shí)*/if(pb!=NULL) pc-next=pb;/*h2單鏈表還有節(jié)點(diǎn)時(shí)*/pc=h3;/*刪除哨兵*/h3=h3-next;free(pc);return h3;void main()nodetype *head1,*head2,*head3;head1=create();head2=create();disp(head1);disp(head2);head3=connect(head

23、1,head2);disp(head3);練習(xí)2.34#include#includetypedef struct dnodeint data;struct dnode *link;dlist;dlist *xor(dlist *p1,dlist *p2)/*在c/c+中異或運(yùn)算符不能對地址進(jìn)行異或運(yùn)算，所以先將地址值轉(zhuǎn)換為長整形，然后進(jìn)行異或運(yùn)算，再將結(jié)果強(qiáng)制轉(zhuǎn)換成地址。這是本函數(shù)的功能*/int add1,add2,add3;add1=(long)p1;add2=(long)p2;add3=add1add2;return(dlist *)add3;dlist *create(dlist *

24、e)int i=1,x;dlist *head,*r,*s,*pre;printf(創(chuàng)建一個(gè)雙鏈表(以0結(jié)束)n);while(1)printf( 輸入第%d節(jié)點(diǎn)值: ,i);scanf(%d,&x);if(x=0)/*生成最后一個(gè)節(jié)點(diǎn)的link值后退出循環(huán)*/pre-link=xor(r,NULL);/*將s-link置為前后節(jié)點(diǎn)地址之異或*/*e=pre;break;s=(dlist *)malloc(sizeof(dlist);/*創(chuàng)建一個(gè)節(jié)點(diǎn)*/s-data=x;if(i=1)/*是第一個(gè)節(jié)點(diǎn)的情況*/pre=head=s;r=NULL;/*r為當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)*/elsepre-

25、link=xor(r,s);/*將s-link置為前后節(jié)點(diǎn)地址之異或*/r=pre;pre=s;i+;return head;void order(dlist *h,dlist *e)dlist *pre=NULL,*pre1,*p=h;printf(遍歷節(jié)點(diǎn)序列: );if(h=NULL)printf(空表n);elsewhile(p!=e)/*遍歷最后一節(jié)點(diǎn)前的所有節(jié)點(diǎn)*/printf(%d ,p-data);pre1=p;p=xor(pre,p-link);/*為下一個(gè)節(jié)點(diǎn)的地址*/pre=pre1;printf(%d ,e-data);printf(n);void main()dlis

26、t *h,*e;int i;h=create(&e);printf(從左向右);order(h,e);printf(從右向左);order(e,h);/*運(yùn)行結(jié)果:創(chuàng)建一個(gè)雙鏈表(以0結(jié)束) 輸入第1節(jié)點(diǎn)值:3輸入第1節(jié)點(diǎn)值:5輸入第1節(jié)點(diǎn)值:8輸入第1節(jié)點(diǎn)值:2輸入第1節(jié)點(diǎn)值:6輸入第1節(jié)點(diǎn)值:0從左向右遍歷節(jié)點(diǎn)序列: 3 5 8 2 6 從右向左遍歷節(jié)點(diǎn)序列: 6 2 8 5 3 */第三章 棧和隊(duì)列實(shí)現(xiàn)?；舅惴ǖ念^文件stack.cpp為：#include#define MaxLen 20/*順序棧存放的最多元素個(gè)數(shù)為Maxlen-1*/typedef char elemtype;ty

27、pedef struct sqstackelemtype dataMaxLen;int top;stack;void init(stack *st)/*初始化棧st*/st-top=0;int push(stack *st,elemtype x)/*入棧*/if(st-top=MaxLen-1)printf(棧溢出n);return 0;elsest-top+;st-datast-top=x;return 1;int pop(stack *st,elemtype *x)/*退棧*/if(st-top=0)printf(棧下溢出n);return 0;else*x=st-datast-top;s

28、t-top-;return 1;int empty(stack *st)/*判斷?？?/if(st-top=0)return 1;elsereturn 0;int gettop(stack *st,elemtype *x)/*獲取棧頂元素*/if(st-top=0)printf(棧下溢出n);return 0;else*x=st-datast-top;return 1;void disp(stack *st)/*輸出棧的所有元素*/int i;for(i=st-top;i0;i-)printf(%d ,st-datai);printf(n);/*練習(xí)3.19*/*假設(shè)一個(gè)算術(shù)表達(dá)式中可以包含三

29、種括號，圓括號(和)、方括號和和花括號和,且這三種括號可按任意的次序嵌套使用(如:.(.).).編寫判別給定表達(dá)式中所含括號是否正確配對出現(xiàn)的算法(已知表達(dá)式已存入數(shù)據(jù)元素為字符的順序表中*/*輸入：a+b+(c+d)+e+f*/#includestack.cpp#includeint correct(char *str)stack st;char x;int i,ok=1;init(&st);for(i=0;stri!=0;i+)switch(stri)case(:push(&st,();break;case:push(&st,);break;case:push(&st,);break;ca

30、se):if(!(pop(&st,&x)&x=()ok=0;break;case:if(!(pop(&st,&x)&x=)ok=0;break;case:if(!(pop(&st,&x)&x=)ok=0;break;if(!ok) break;if(empty(&st)&ok)return 1;elsereturn 0;void main()char *str;str=(char*)malloc(100*sizeof(char);printf(str: );scanf(%s,str);if(correct(str)printf(表達(dá)式括號匹配n);elseprintf(表達(dá)式括號不匹配n);

31、getch();練習(xí)3.21#include#define MaxLen 100int trans(char str,char exp)int stMaxLen;/*作為棧使用*/char ch;int i=0,t=0,top=-1;/*t作為exp的下標(biāo)，top作為st的下標(biāo)，i作為str的下標(biāo)*/while(ch=stri+)!=0)if(ch=0 & ch=0 & ch=0 & sttop!=()expt=sttop;top-;t+;top+;sttop=ch;else if(ch=*|ch=/)while (sttop=* | sttop=/)expt=sttop;top-;t+;to

32、p+;sttop=ch;while(top=0)expt=sttop;t+;top-;expt=0;return 1;int compvalue(char exp,int *n)int stMaxLen,d;/*作為棧使用*/char ch;int t=0,top=-1;/*t作為exp的下標(biāo)，top作為st的下標(biāo)*/while (ch=expt+1)!=0)if(ch=0 & ch=9)/*為數(shù)字字符時(shí)轉(zhuǎn)換為數(shù)字*/d=0;dod=10*d+ch-0;while(ch=expt+)!=#);top+;sttop=d;/*數(shù)字進(jìn)棧*/else /*為運(yùn)算符時(shí)，計(jì)算并退棧*/switch(ch)

33、case+:sttop-1=sttop-1+sttop;break;case-:sttop-1=sttop-1-sttop;break;case*:sttop-1=sttop-1*sttop;break;case/:if(sttop!=0) sttop-1=sttop-1/sttop;elsereturn 0;/*除0錯(cuò)誤*/break;top-;(*n)=sttop;return 1;void main()char strMaxLen;/*存儲原算術(shù)表達(dá)式*/char expMaxLen;/*存儲轉(zhuǎn)換成的波蘭表達(dá)式*/int n;printf(算術(shù)表達(dá)式: );scanf(%s,&str);

34、if(trans(str,exp)=0)printf(原算術(shù)表達(dá)式不正確n);elseprintf(波蘭表達(dá)式: %dn,exp);if(compvalue(exp,&n)=1)printf(計(jì)算結(jié)果: %dn,n);elseprintf(計(jì)算錯(cuò)誤n);練習(xí)3.27/*已知Ackerman函數(shù)的定義如下：Akm(m,n)=n+1(m=0),akm(m-1,1)(m!=0,n=0) akm(m-1),akm(m,n-1)(m!=0,n!=0)1.寫出遞歸算法；2。寫出非遞歸算法；3。根據(jù)非遞歸算法，畫出求akm(2,1)時(shí)棧的變化過程*/#include#define MaxLen 5000/*

35、此數(shù)應(yīng)足夠大，因?yàn)閙和n值的較小增長會引起函數(shù)值的極快增長，用的棧的空間也很大*/int f1(int m,int n)if(m=0)return n+1;elseif(n=0) return f1(m-1,1);elsereturn f1(m-1,f1(m,n-1);int no(int m,int n)if(m=0)return 1;else if(n=0)return 2;else return 3;int f2(int m,int n)int stMaxLen4,top=1,m1,n1;sttop0=no(m,n);sttop1=0;/*初值0進(jìn)棧*/sttop2=m;/*初值m進(jìn)棧*

36、/sttop3=n;/*初值n進(jìn)棧*/do /*開始循環(huán)*/if(sttop1=0)if(sttop0=3)top+;sttop1=0;sttop2=sttop-12;sttop3=sttop-13-1;sttop0=no(sttop2,sttop3);else if(sttop0=2)top+;sttop1=0;sttop2=sttop-12-1;sttop3=1;sttop0=no(sttop2,sttop3);if(sttop0=1)sttop1=sttop3+1;if(top=1&sttop1!=0&sttop-10=2)sttop-11=sttop1;top-;else if(top

37、=1&sttop1!=0&sttop-10=3)n1=sttop1;m1=sttop-12-1;top-;sttop1=0;sttop2=m1;sttop3=n1;sttop0=no(sttop2,sttop3);if(top=1&sttop1!=0)/*棧中已有一個(gè)元素，且已計(jì)算出值，則退出循環(huán)*/break;while(top=1);return (st11);void main()int n,m;printf(input m n:);scanf(%d %d,&m,&n);printf(digui c(%d,%d)=%dn,m,n,f1(m,n);printf(feidigui c(%d,

38、%d)=%dn,m,n,f2(m,n);system(pause);/*輸入：3 8回車digui c(3,8)=2045feidigui c(3,8)=2045*/練習(xí)3.28/*假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針指向隊(duì)尾結(jié)點(diǎn)（注意不設(shè)頭指針），試編寫相應(yīng)的隊(duì)列初始化、入隊(duì)列和出隊(duì)列的算法*/#include#define MaxSize 6typedef char queueMaxSize;int rear=0,len=0;/*隊(duì)列初態(tài)*/int enqueue(queue qu,char x)if(len=MaxSize)/*隊(duì)滿，上溢出*/return 0;elserear=(rear+1)%MaxSize;qurear=x;len+;/*隊(duì)列長度增1*/return 1;int dequeue(queue qu,char *x)int front;if(len=0)/*隊(duì)列為空時(shí)下溢出*/return 0;elsefront=(rear-len+1+MaxSize)%MaxSize;*x=qufront;len-;/*隊(duì)列長度減1*/return 1;void main()char x;queue qu;print