新版數(shù)據(jù)結(jié)構(gòu)及算法實(shí)驗(yàn)指導(dǎo)書資料

1、天天快樂數(shù)據(jù)結(jié)構(gòu)與算法基娜娜 編哈爾濱理工大學(xué)榮成學(xué)院實(shí)驗(yàn)一順序表的實(shí)現(xiàn)和應(yīng)用一、實(shí)驗(yàn)?zāi)康?、掌握順序表的定義；2、掌握順序表的基本操作，如查找、插入、刪除及排序等。二、實(shí)驗(yàn)內(nèi)容1、編寫函數(shù)，實(shí)現(xiàn)在順序表中查找值為x的元素的位置的簡單順序查找算法，編寫主函數(shù)驗(yàn)證此算法，并分析算法的時間復(fù)雜度2、編寫函數(shù)，實(shí)現(xiàn)在順序表中刪除第i個位置上的元素，編寫主函數(shù)驗(yàn)證此算法，并分析算法的時間復(fù)雜度3、編寫函數(shù)，實(shí)現(xiàn)在順序表中第i個位置上插入值為x的元素，編寫主函數(shù)驗(yàn)證此算法，并分析算法的時間復(fù)雜度4、編寫函數(shù)，實(shí)現(xiàn)在順序表中將所有偶數(shù)排在所有奇數(shù)前面，編寫主函數(shù)驗(yàn)證此算法， 并分析算法的時間復(fù)雜度二、實(shí)驗(yàn)

2、提不1、#include #define MAXSIZE 20typedef structint dataMAXSIZE;int last;list;/*編寫函數(shù)，實(shí)現(xiàn)在順序表中查找值為x的元素的位置的簡單順序查找算法，編寫主函數(shù)驗(yàn)證此算法，并分析算法的時間復(fù)雜度*/int locate(list *l,int x)/代碼int i;for(i=0;ilast;i+)if(l-datai=x)return i+1;return -1;main()list b;int x,i,p;b.last=10;for(i=0;iosition4ress any key to contini_ue請輸入K的

3、值！ 100-no! Press any key to continue.時間復(fù)雜度T(n)=O(n)；2、#include #define MAXSIZE 20typedef structint dataMAXSIZE;int last;list;/*編寫函數(shù)，實(shí)現(xiàn)在順序表中刪除第i個位置上的元素，編寫主函數(shù)驗(yàn)證此算法，并分析算法的時間復(fù)雜度*/int delete(list *l,int i)int j,k,p; / if(i=0&ilast) 定義一個用來保存被刪原素;/只接受有效輸入for(j=0;jlast;j+) / if(j=i-1) p=l-dataj;/遍歷數(shù)組 匹配for(

4、k=j;klast;k+)l-data止l-datak+1;保存被刪原素；/前進(jìn)一位;break;l-last=l-last-1;return p; /退出循環(huán)對于此題來說可以輸出p;return 0;main()list b;int x,i;b.last=10;for(i=0;ib.last;i+) b.datai=i+2;printf( 請輸入x的值：)； scanf(%d,&x);if(delete(&b,x)!=0)for(i=0;ib.last;i+)printf(%3d,b.datai);elseprintf(Error!);請輸入其的值,52 3 45 7 8 9 10 UPre

5、ss any key to continueError!Press any key to continue/時間復(fù)雜度T(n)=O(n)；3、#include #define MAXSIZE 20typedef structint dataMAXSIZE;int last;list;/*編寫函數(shù)，實(shí)現(xiàn)在順序表中第i個位置上插入值為x的元素，編寫主函數(shù)驗(yàn)證此算法,并分析算法的時間復(fù)雜度*/int insert(list *l,int x,int i)int j,k;if(ilast+1&i0)if(i=l-last+1)/特殊值last+1要插入到整個數(shù)組之后 l-datal-last=x; e

6、lse for(j=0;jlast;j+)if(j=i-1)/ 匹配for(k=l-last;kj;k-)/將所選插入位置之后原素后移l-datak=l-datak-1;l-dataj=x;/把x賦值給所選位置break;l-last=l-last+1;/ 數(shù)值長度加一return 1; return 0;/無效位置 main() list b; int x,i; b.last=10; for(i=0;ib.last;i+)b.datai=i+2; printf( 請輸入x的值：); scanf(%d,&x); if(insert(&b,66,x)!=0) for(i=0;ib.last;i+

7、) printf(%3d,b.datai); else printf(Error!); 睛輸入丫的值；523 45 66 67 89 10 HPress any key to continueError!Press any key to continue/時間復(fù)雜度T(n)=O(n);4、#include #define MAXSIZE 20typedef structint dataMAXSIZE;int last;list;/*編寫函數(shù)，實(shí)現(xiàn)在順序表中將所有偶數(shù)排在所有奇數(shù)前面，編寫主函數(shù)驗(yàn)證此算法,并分析算法的時間復(fù)雜度*/void fun(list *l)兒低int i,ou=0,te

8、mp;for(i=0;ilast;i+)if(l-datai%2=0)ou個位置的原素交換位置temp=l-dataou;l-dataou=l-datai;l-datai=temp;ou+=1;/這個代碼有點(diǎn)晦澀，但空間時間復(fù)雜度是雞小計(jì)數(shù)，ou代表偶數(shù)個數(shù)/循環(huán)/判斷是不是偶數(shù)，如果是偶數(shù)的話和當(dāng)前第/偶數(shù)個數(shù)加一printf（當(dāng)前數(shù)組中偶數(shù)有 個，奇數(shù)有d個:n,ou,l-last-ou）;main()list b;int i=0,m=0;b.last=10;printf(請輸入數(shù)組元素的值：n);for(i=0;ib.last;i+)printf(b.data%d=,i);scanf(%

9、d,&b.datai);fun(&b);for(i=0;ib.last;i+)printf(%3d,b.datai);IL國的國1.力t入LD-11=2、.廿 32=3：, t -1：3=4b. L La4=5 , Tut、5=66=7% mE7二8t.d=9L L L9=10目前數(shù)組中偶數(shù)有5個,奇數(shù)有衿：2 4 6 S 10 3 7 1 9 EPress any key t口 ccnitinu弓/時間復(fù)雜度為T(n)=O(n)；四、實(shí)驗(yàn)報(bào)告要求1、撰寫實(shí)驗(yàn)報(bào)告;2、對實(shí)驗(yàn)中出現(xiàn)的問題和結(jié)果進(jìn)行總結(jié)。實(shí)驗(yàn)二 鏈表的實(shí)現(xiàn)和應(yīng)用一、實(shí)驗(yàn)?zāi)康?1、掌握鏈表的定義； 2、掌握鏈表的基本操作，如查找、

10、插入、刪除、排序等。 二、實(shí)驗(yàn)內(nèi)容 1、單鏈表的創(chuàng)建 2、單鏈表的查找 3、單鏈表的排序 4、單鏈表的刪除 5、鏈表的應(yīng)用-約瑟夫環(huán)問題 二、實(shí)驗(yàn)提不 1、創(chuàng)建單鏈表，要求：結(jié)點(diǎn)個數(shù)為 n個，每個節(jié)點(diǎn)數(shù)據(jù)域的值必須小于m編輯主函數(shù)驗(yàn)證之。#include #include typedef struct aa int data; struct aa *next; NODE; NODE *Creatlink(int n, int m) int i; NODE *tou,*p;/tou 頭結(jié)點(diǎn)tou=(NODE*)malloc(sizeof(NODE);/ 創(chuàng)建并初始化頭結(jié)點(diǎn)tou-next=NUL

11、L; tou-data=n; printf( 請輸入%外小魚%d的數(shù)，中間用空格隔開：n,n,m); for(i=0;idata); if(p-data=m) printf(輸入的第d個數(shù)據(jù)大于 d,GGn,i+1,m);exit(0);/程序強(qiáng)制中斷，好像是在頭文件stdlib.h 里 p-next=tou-next; tou-next=p; return tou; outlink(NODE *h) NODE *p;p=h-next;printf(nnTHE LIST :nn HEAD );while(p) printf(-%d ,p-data);p=p-next;printf(n);mai

12、n() NODE *head;head=Creatlink(8,22);outlink(head);請輸入個小魚22的數(shù)，中間用空格隔開：12 3 4 5 6 7 3THE LIST :HEAD -3 -7 -6 -5 -4 -3 -2 -1J-ress any key to continuj1 2 3 100 5 6 7 8輸人的第4個數(shù)據(jù)大于22： GGPress any ksy to continue2、查找值為ch的節(jié)點(diǎn)在鏈表中是否出現(xiàn)，如果存在，返回在鏈表中位序，如果不存 在返回0#include #include #define N 8typedef struct list int

13、 data;struct list *next; SLIST;SLIST *creatlist(char *);void outlist(SLIST *);int fun( SLIST *h, char ch)int i;SLIST *p;p=h-next;/p賦值為壽元節(jié)點(diǎn)for(i=0;idata=ch)return i+1;p=p-next; return 0; main() SLIST *head; int k; char ch; char aN=m,p,g,a,W,x,r,d; head=creatlist(a); outlist(head); printf(Enter a lett

14、er:); scanf(%c,&ch); k=fun(head,ch);if (k=0) printf(nNot found!n); else printf(The sequence number is : %dn,k); SLIST *creatlist(char *a) int i; SLIST *tou,*p;tou=(SLIST*)malloc(sizeof(SLIST);/ 創(chuàng)建并初始化頭結(jié)點(diǎn)tou-data=N; tou-next=NULL; for(i=0;idata=ai; p-next=tou-next; tou-next=p; return tou; void outlis

15、t(SLIST *h) SLIST *p; p=h-next; if (p=NULL) printf(nThe list is NULL!n); else printf(nHead); do printf(-%c,p-data); p=p-next; while(p!=NULL); printf(-Endn); 一d-r-x-w-a-g-p-m-EndEnter a letter：gThe sequence nuiriber is : 6Press any key to continue.Head-d-r-i-wa-g-p-m-Bnd inter a letter；zMot found!pre

16、ss 軟ny key t口 continue3、去偶操作，鏈表中各節(jié)點(diǎn)按數(shù)據(jù)域遞增有序鏈接，函數(shù) fun的功能是，刪除鏈表中 數(shù)據(jù)域值相同的節(jié)點(diǎn)，使之只保留一個#include #include #define N 8 typedef struct list int data;struct list *next; SLIST;voidfun( SLIST *h)SLIST *p,*shanchu; p=h-next;while(p-next!=NULL)/用于遍歷的指針p,用于刪除的指針shanchu/p為壽元節(jié)點(diǎn)/終止條件/判斷是否有重復(fù)原素if(p-data=p-next-data)sha

17、nchu=p-next;p-next=shanchu-next; free(shanchu);elsep=p-next;SLIST *creatlist(int *a) SLIST *h,*p,*q; int i;h=p=(SLIST *)malloc(sizeof(SLIST);for(i=0; idata=ai; p-next=q; p=q;p-next=0;return h;void outlist(SLIST *h) SLIST *p;p=h-next;if (p=NULL) printf(nThe list is NULL!n);else printf(nHead);do print

18、f(-%d,p-data); p=p-next; while(p!=NULL); printf(-Endn);main() SLIST *head; int aN=1,2,2,3,4,4,4,5;head=creatlist(a);printf(nThe list before deleting :n); outlist(head);fun(head);printf(nThe list after deleting :n); outlist(head);The list before deleting ：The list after deleting ;Head-P2-3-4-5-EndPre

19、ss any key to continue4、在main函數(shù)中多次調(diào)用fun函數(shù)，每調(diào)用一次fun函數(shù)，輸出鏈表尾部節(jié)點(diǎn)中的 數(shù)據(jù)，并釋放該節(jié)點(diǎn)，使得鏈表縮短。#include #include #define N 8 typedef struct list int data; struct list *next; SLIST; void fun( SLIST *p) SLIST *bianli,*shanchu;/ 遍歷，刪除bianli=p; while(bianli-next-next!=NULL) bianli=bianli-next; printf(%d,bianli-next-d

20、ata);/ 輸出shanchu=bianli-next;free(shanchu);bianli-next=NULL;/釋放SLIST *creatlist(int *a) SLIST *h,*p,*q; int i;h=p=(SLIST *)malloc(sizeof(SLIST);for(i=0; idata=ai; p-next=q; p=q;p-next=0;return h;void outlist(SLIST *h) SLIST *p;p=h-next;if (p=NULL) printf(nThe list is NULL!n);else printf(nHead);do pr

21、intf(-%d,p-data); p=p-next; while(p!=NULL); printf(-Endn);main() SLIST *head;int aN=11,12,15,18,19,22,25,29;head=creatlist(a);printf(nOutput from head:n); outlist(head);printf(nOutput from tail: n);while (head-next != NULL)fun(head);printf(nn);printf(nOutput from head again :n); outlist(head);Output

22、 frcmn head：Head-11-12-15-18-19-22-25-29-EndOutput from tail： 29Output from head 國目日in :Ke3d-ll-12-15-18-19-22-25-End 25Output froon head again :Head-ll-12-15-18-19-22-End 22Output from had again :Had-ll-12-15-18-19-End 19Output from head iftgain :Head-ll-12-15-18-BndISOutput from head again :Hyad-l

23、l-12-15-End15Outj?ut from head aigain :|Hgid-ll-L2-EndOutput from head again :Read-U-12-End12Output from head again :Head-K-End 11Output from head again ：The list is NULL!Press any key to continue,5、實(shí)現(xiàn)約瑟夫環(huán)函數(shù)(選做)#include #include typedef struct list int data;struct list *next; SLIST;SLIST *creatlist(

24、int m)int i;SLIST *tou,*p,*wei;/頭指針 生成節(jié)點(diǎn)指針 尾指針tou=(SLIST*)malloc(sizeof(SLIST);/ 頭節(jié)點(diǎn)wei=tou;printf( 請輸入外數(shù)用空格隔開： for(i=0;idata);wei-next=p;wei=p;wei-next=tou-next;return tou;void outlist(SLIST *h,int m,int c)int i;SLIST *p,*shanchu;p=h-next;while(p!=p-next)for(i=1;inext;shanchu=p-next;printf(%d ,shan

25、chu-data);p-next=shanchu-next;free(shanchu);p=p-next;printf(%d,p-data);free(p);free(h);n,m);/尾插法/令最后一個原素指向首元結(jié)點(diǎn)成環(huán)用于遍歷的指針p,用于刪除的指針shanchu/p指向首元結(jié)點(diǎn)/當(dāng)環(huán)中只剩下一個原素時結(jié)束/根據(jù)輸入的c剔除節(jié)點(diǎn)/shanchu指向當(dāng)前要剔除的節(jié)點(diǎn)/將shanchu指針指向的節(jié)點(diǎn)出環(huán)/輸出最后的一個節(jié)點(diǎn)的內(nèi)容main() SLIST *head;int m,c;printf( 請分別輸入m和c的值：); scanf(%d,%d,&m,&c);head=creatlist(

26、m);outlist(head,m,c);情分別僦人碑1c的值I 8 3請簫人杯藪用空格隔開1 2 3 4 5 6 7 3.3615284 7Press any key to continue四、實(shí)驗(yàn)報(bào)告要求1、撰寫實(shí)驗(yàn)報(bào)告；2、對實(shí)驗(yàn)中出現(xiàn)的問題和結(jié)果進(jìn)行總結(jié)。實(shí)驗(yàn)三 棧的實(shí)現(xiàn)和應(yīng)用天天快樂一、實(shí)驗(yàn)?zāi)康?、掌握棧的建立方法；2、掌握棧的基本操作，如入棧、出棧、判斷空棧等;3、棧的應(yīng)用。二、實(shí)驗(yàn)內(nèi)容1、順序棧的初始化2、判斷棧是否為空3、順序棧出棧4、順序棧入棧5、棧的應(yīng)用-漢諾塔二、實(shí)驗(yàn)提不1、棧的基本操作，按提示將函數(shù)補(bǔ)充完整#include #include #define STACK_

27、MAX 100 typedef structint top;int dataSTACK_MAX; stack;初始化順序棧*/判斷棧是否為空*/空0/非空1void init(stack *st) /*st-top=0;int Empty(stack *st)/*if(st-top=0)return 0;elsereturn 1;int pop(stack *st) /*出棧 */return st-data-st-top;入棧*/void push(stack *st,int data) /*st-datast-top+=data;int main(void)天天快樂stack st;ini

28、t(&st);push(&st,5);push(&st,6);printf(%d,pop(&st);return 0;SPress any key to continue2、#include void main()void hanoi(int n,char one,char two,char three);/* 對hanoi函數(shù)的聲明*/int m;printf(input the number of diskes:);scanf(%d,&m);printf(The step to moveing %d diskes:n,m);hanoi(m,A,B,C);void hanoi(int n,c

29、har one,char two,char three)/* 定義hanoi函數(shù)，將n個盤從 one座借助two座，移到three座*/static k=1;void move(char x,char y);峰有聲明 在此需要提前聲明才能使用if(n=1)到第三個上 printf(第 步:,k+);move(one,three); else hanoi(n-1,one,three,two);三個座當(dāng)橋梁printf(第 步:,k+);move(one,three);hanoi(n-1,two,one,three);個盤上，第一個盤當(dāng)橋梁/定義靜態(tài)變量k用來標(biāo)明走了多少步因?yàn)閙ove函數(shù)定義在該

30、函數(shù)的后邊且之前/當(dāng)?shù)谝粋€座上僅剩一個盤的時候?qū)⒋吮P移/輸出是第多少步/移動/將前n-1個盤從第一個座移到二個座上，第/將上邊轉(zhuǎn)移到第二個座上的盤轉(zhuǎn)移到第三天天快樂void move(char x,char y) /*定義 move函數(shù) */printf(%c-%cn,x,y);input the number of diskes:4The step to moveing 4 diskes：第1步:第2步:第3步:B乂第4歲;A-圮第5步:CA第6步:C 一圮斯步:AB第建:AC第9步:BC第 10 步:BA11:CAC第 13步:ABCPress any key to continue四、實(shí)

31、驗(yàn)報(bào)告要求1、撰寫實(shí)驗(yàn)報(bào)告；2、對實(shí)驗(yàn)中出現(xiàn)的問題和結(jié)果進(jìn)行總結(jié)。實(shí)驗(yàn)四 隊(duì)列的實(shí)現(xiàn)和應(yīng)用天天快樂一、實(shí)驗(yàn)?zāi)康?、掌握隊(duì)列的建立方法；2、掌握隊(duì)列的基本操作，如出隊(duì)、入隊(duì)、判斷隊(duì)空等;3、隊(duì)列的應(yīng)用。二、實(shí)驗(yàn)內(nèi)容1、順序隊(duì)列的初始化2、判斷隊(duì)列是否為空3、順序隊(duì)列出隊(duì)4、順序隊(duì)列入隊(duì)5、隊(duì)列的應(yīng)用-回文判斷二、實(shí)驗(yàn)提不1、隊(duì)列的基本操作，按提示將函數(shù)補(bǔ)充完整#include #include #define STACK_MAX 100 typedef structint front, rear;int data1STACK_MAX; Queue;void initQueue (Queue *q

32、) /*q-front=q-rear=0;int EmptyQueue(Queue *q)/*初始化隊(duì)列*/判斷隊(duì)列空*/if(q-front=q-rear) return 1;else/1代表空return 0;/0代表非空int DeQueue(Queue *q) /* 出隊(duì)列*/判斷需要出隊(duì)時隊(duì)列是否為空if(q-rear=q-front)printf(當(dāng)前隊(duì)列已經(jīng)空了。);exit(0);else天天快樂/將隊(duì)頭原素出列然后隊(duì)頭指針加一return q-data1q-front+;void InQueue(Queue *q,int data) /*if(q-rear=STACK_MAX

33、)printf(當(dāng)前隊(duì)列空間已滿。exit(0); elseq-data1q-rear=data; q-rear+;int main()Queue q;入隊(duì)列*/判斷需要入隊(duì)時隊(duì)列是否已滿);/入隊(duì)initQueue(&q);InQueue(&q,1);InQueue(&q,2);InQueue(&q,3);printf(%dn,DeQueue(&q);printf(%dn,DeQueue(&q);printf(%dn,DeQueue(&q);ress any key to continue2、判斷給定的字符序列是否是回文(提示：將一半字符入棧)#include #include #defin

34、e STACK_MAX 100typedef structint top;int dataSTACK_MAX; stack;typedef struct int front, rear;int data1STACK_MAX; Queue;void init(stack *st) /*st-top=0;int Empty(stack *st)/*if(st-top=0)return 1;elsereturn 0;int pop(stack *st) /*if(st-top=0)初始化順序棧*/判斷?？?/出棧*/printf(棧已空！);exit(0);elsechar c;c=st-data-

35、st-top;return (int ) c;入棧*/void push(stack *st,int data) /*if(st-top=STACK_MAX-1)printf( 棧已空！);exit(0); else st-datast-top+=data;void initQueue (Queue *q) /*初始化隊(duì)列 */q-front=q-rear=0;int EmptyQueue(Queue *q)/* 判斷隊(duì)列空 */if(q-front=q-rear)return 1;elsereturn 0;int DeQueue(Queue *q) /*出隊(duì)列*/return (int)q-

36、data1q-front+;void InQueue(Queue *q,int data) /* 入隊(duì)列*/q-data1q-rear+=data;int IsHuiWen(stack *st,Queue *q,char * a)int i,zhan,dui,k=0;/i計(jì)數(shù)，zhan代表應(yīng)往棧里邊傳幾個原素，dui代表應(yīng)從第幾個原素開始往隊(duì)列傳值，k計(jì)算數(shù)組a口中有多少原素while(ak!=0)k+;if(k%2=0)zhan=k/2;dui=k/2+1;if(k%2=1)zhan=k/2;dui=k/2+2;for(i=0;izhan;i+)push(st,ai);for(i=zhan;

37、ik;i+)InQueue(q,ai);for(i=0;ik/2;i+)if(pop(st)!=DeQueue(q) return 0;return 1;int main()char a10=a,b,c,d,b,a;stack st;Queue q;init(&st);initQueue(&q);printf(%dn,IsHuiWen(&st,&q,a); 0Press any key to continue四、實(shí)驗(yàn)報(bào)告要求1、撰寫實(shí)驗(yàn)報(bào)告；2、對實(shí)驗(yàn)中出現(xiàn)的問題和結(jié)果進(jìn)行總結(jié)。天天快樂天天快樂實(shí)驗(yàn)五二叉樹的遍歷及應(yīng)用一、實(shí)驗(yàn)?zāi)康?掌握二叉樹的定義；.掌握二叉樹的基本操作，如二叉樹的建立、遍歷

38、、結(jié)點(diǎn)個數(shù)統(tǒng)計(jì)、樹的深度計(jì)算等。 二、實(shí)驗(yàn)內(nèi)容用遞歸的方法 實(shí)現(xiàn)以下算法：.以二叉鏈表表示二叉樹，建立一棵二叉樹；.輸出二叉樹的中序遍歷結(jié)果；.輸出二叉樹的前序遍歷結(jié)果；.輸出二叉樹的后序遍歷結(jié)果；.計(jì)算二叉樹的深度；.統(tǒng)計(jì)二叉樹的結(jié)點(diǎn)個數(shù)；7、二叉樹的層序遍歷結(jié)果。二、實(shí)驗(yàn)提不1、/按要求將程序補(bǔ)充完整#include #include #include #define NULL 0typedef struct BiTNodechar data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;二叉樹的建立BiTree Create(BiTree

39、T)char ch;設(shè)置一個接收數(shù)據(jù)的變量scanf(%c,&ch);if(ch=#)T=NULL;設(shè)置結(jié)束符elseT = (BiTree)malloc(sizeof(BiTNode); 生成心節(jié)點(diǎn)T-data = ch;T-lchild = Create(T-lchild);/ 遞歸建立T-rchild = Create(T-rchild);return T;二叉樹的前序遞歸遍歷void Preorder(BiTree T)if(T)printf(%c ,T-data);Preorder(T-lchild);Preorder(T-rchild);統(tǒng)計(jì)二叉樹的結(jié)點(diǎn)個數(shù)int Sumleaf(

40、BiTree T)int n;if(T=NULL) return 0;elsen=1+Sumleaf(T-lchild)+Sumleaf(T-rchild);return n;二叉樹的中序遞歸遍歷void zhongxu(BiTree T)if(T)Preorder(T-lchild);printf(%c ,T-data);Preorder(T-rchild);二叉樹的后序遞歸遍歷void houxu(BiTree T)if(T)Preorder(T-lchild);Preorder(T-rchild); printf(%c ,T-data);計(jì)算二叉樹的深度int Depth(BiTree T)誰大選誰int n;if(T=NULL)return 0;elseif(Depth(T-lchild)Depth(T-rchild) return Depth(T-lchild)+1; elsereturn Depth(T-