數(shù)據(jù)結(jié)構(gòu)與算法試驗指導(dǎo)書

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

2、法的時間復(fù)雜度三、實驗提示1、#inelude #define MAXSIZE 20typedef structint dataMAXSIZE;int last;list;/*編寫函數(shù)，實現(xiàn)在順序表中查找值為x的元素的位置的簡單順序查找算法，編寫主函數(shù)驗證此算法，并分析算法的時間復(fù)雜度*/in t locate(list *l,i nt 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;ib.l ast;i+)b.datai=i+2;p

3、rintf(請輸入x的值：”);scan f(%d，& x);p=locate(&b,x);if(p=-1)prin tf( no!);elseprin tf(positi on=%dn,p);請蒯人藍的值:5position4Press any key to contintue請輸人藍的值：100；no! Press any key to continue.時間復(fù)雜度T(n)=O(n);2、#inelude#define MAXSIZE 20typedef structint dataMAXSIZE;int last;list;/*編寫函數(shù)，實現(xiàn)在順序表中刪除第 i個位置上的元素，編寫主函數(shù)

4、驗證此算法，并分析算法的時間復(fù)雜度*/int delete(list *l,int i)int j,k,p;II定義一個用來保存被刪原素；if(i=0&ilast)II只接受有效輸入for( j=O;jlast;j+)/遍歷數(shù)組if(j=i-1)/匹配p=l-dataj;/保存被刪原素；for(k=j;klast;k+)/ 前進一位；l-datak=l-datak+1;break;/退出循環(huán)l-last=l-last-1;return p;/對于此題來說可以輸出p;return 0;main ()list b;int x,i;b.last=10;for(i=0;ib.l ast;i+)b.da

5、tai=i+2;printf(請輸入x的值：”)； scan f(%d，& x);if(delete(&b,x)!=O)for(i=0;ib .l ast;i+)prin tf(%3d,b.datai);elseprin tf(Error!);幘嶽心的庫52345789 10 UPress any key to can ti nue/時間復(fù)雜度T(n)=O(n);3、#include#defi ne MAXSIZE 20 typedef structint dataMAXSIZE;int last;list;/*編寫函數(shù)，實現(xiàn)在順序表中第i個位置上插入值為x的元素，編寫主函數(shù)驗證此算法，并分析

6、算法的時間復(fù)雜度 */ int in sert(list *l,i nt x,i nt i)int j,k;if(ilast+1 &i0)if(i=l-last+1)/特殊值last+1 要插入到整個數(shù)組之后l-datal-last=x;elsefor( j=0;jlast;j+)if(j=i-1)/ 匹配for(k=l-last;kj;k-)/將所選插入位置之后原素后移l-datak=l-datak-1;l-data j=x;/把x賦值給所選位置break;l-last=l-last+1;/ 數(shù)值長度加一return 1;return 0;/無效位置main ()list b;int x,i

7、;b.last=10;for(i=0;ib.l ast;i+)b.datai=i+2;printf(請輸入x的值：”)；scan f(%d，& x);if(in sert(&b,66,x)!=0)for(i=0;ib .l ast;i+)prin tf(%3d,b.datai);參考材料for(i=0;ilast;i+)/循環(huán)elseprin tf(Error!);請輸入y的值=52 3 4 5 66 6 789 10 llPress any key to continue/時間復(fù)雜度T(n)=O(n);參考材料#in elude#defi ne MAXSIZE 20typedef struc

8、tint dataMAXSIZE;int last;list;/*編寫函數(shù)，實現(xiàn)在順序表中將所有偶數(shù)排在所有奇數(shù)前面，編寫主函數(shù)驗證此算法并分析算法的時間復(fù)雜度*/void fun( list *l)/這個代碼有點晦澀，但空間時間復(fù)雜度是雞兒低int i,ou=0,temp;/i計數(shù)，ou代表偶數(shù)個數(shù)ouif(l-datai%2=0)個位置的原素交換位置/判斷是不是偶數(shù)，如果是偶數(shù)的話和當前第temp=l-dataou;l-dataou=l-datai;l-datai=temp;ou+=1;/偶數(shù)個數(shù)加一printf(”當前數(shù)組中偶數(shù)有%d個,奇數(shù)有%d個:n,ou,l-last-ou）;ma

9、i n()list b;int i=0,m=0;b.last=1O;printf（請輸入數(shù)組元素的值：n）;for(i=0;ib.l ast;i+)prin tf(b.data%d=,i);scan f(%d, &b.datai);fun(&b);for(i=0;ib.last;i+)prin tf(%3d,b.datai);N青輸人數(shù)組兀素的荷：L, datab, dataib, data2b. data3=4ba dnt良4=5b- data5=6b. data=7b. dataT=Sb. data8=9b. datag=10二Hi 駅:且中偶數(shù)有5個，奇數(shù)有5個：2 468 103 71

10、9 SPres旦 any key to】 continue/時間復(fù)雜度為T(n)=0(n);四、實驗報告要求1、撰寫實驗報告；2、對實驗中出現(xiàn)的問題和結(jié)果進行總結(jié)參考材料實驗二 鏈表的實現(xiàn)和應(yīng)用一、實驗?zāi)康?、掌握鏈表的定義；2、 掌握鏈表的基本操作，如查找、插入、刪除、排序等。二、實驗內(nèi)容1、單鏈表的創(chuàng)建2、單鏈表的查找3、單鏈表的排序4、單鏈表的刪除5、鏈表的應(yīng)用-約瑟夫環(huán)問題三、實驗提示1、/創(chuàng)建單鏈表，要求：結(jié)點個數(shù)為n個，每個節(jié)點數(shù)據(jù)域的值必須小于m。編輯主函數(shù)驗證之。#i nclude #i nclude typedef struct aa int data;struct aa *

11、n ext; NODE;NODE *Creatli nk(i ntn, i nt m)int i;tou頭結(jié)點/創(chuàng)建并初始化頭結(jié)點NODE *tou,*p;tou=(NODE*)malloc(sizeof(NODE);tou- next=NULL;tou-data=n;printf(請輸入%d個小魚%d的數(shù)，中間用空格隔開：n,n,m);for(i=0;idata);if(p-data=m)printf(輸入的第%d個數(shù)據(jù)大于 %d,GGn,i+1,m);好像是在頭文件exit(0);/程序強制中斷，stdlib.h 里p-n ext=tou-n ext; tou-n ext=p;return

12、 tou;outli nk(NODE *h) NODE *p;p=h-n ext;LIST :nnHEAD );prin tf(nn THEwhile(p) prin tf(-%d ”,p-data); p=p-n ext;prin tf(n ”);main () NODE *head;head=Creatli nk(8,22);outl in k(head);1 2345678 LIST :HEAD -8 -7 -6 -5 -4 -3 -2 -1 Press any key to uontiflue.幘輸人&卜小魚匹的飆 中間用空格隔開:1 2 3 100 5 6 7 8綁入的第4個數(shù)據(jù)大于

13、22：GGPress any ksy to continue2、/查找值為ch的節(jié)點在鏈表中是否出現(xiàn)，如果存在，返回在鏈表中位序，如果不存 在返回0#in clude#in clude#defi netypedef struct list int data;struct list*n ext; SLIST;SLIST *creatlist(char *);void outlist(SLIST *);int fun( SLIST *h, char ch)int i;SLIST *p;p=h-next;p賦值為壽元節(jié)for(i=0;idata=ch)return i+1;p=p-n ext;ret

14、urn 0;main ()ch; SLIST *head;int k;charchar aN=m,p,g,a,w,x,r,d;head=creatlist(a);outlist(head);prin tf(E nter a letter:);scan f(%c,&ch);k=fu n( head,ch);if (k=0)prin tf(nNot fou nd!n);elseprin tf(The seque nee nu mber is :%dn ”,k);SLIST *creatlist(char *a)int i;SLIST *tou,*p;tou=(SLIST*)malloc(sizeo

15、f(SLIST); / 創(chuàng)建并初始化頭結(jié)點tou-data=N;tou- next=NULL;for(i=0;idata=ai;p-n ext=tou-n ext;tou-n ext=p;參考材料return tou;void outlist(SLIST *h) SLIST *p;p=h-n ext;if (p=NULL) prin tf(nThe list is NULL!n ”); else prin tf(nH ead);p=p-n ext;do prin tf(-%c,p-data);while(p!=NULL); prin tf(-E ndin ”);Headjdjr-x-w-a-g

16、-p-m-End a lmtter ：gThe sequence nuiriber is :6Prsss any key to continue.五代丑a letter：zNot found!prems 技ny key t口 c口ntinu白3、/去偶操作，鏈表中各節(jié)點按數(shù)據(jù)域遞增有序鏈接，函數(shù)fun的功能是，刪除鏈表中 數(shù)據(jù)域值相同的節(jié)點，使之只保留一個參考材料#in elude參考材料#in elude#defi ne N 8 typedef struct list int data;struct list *n ext; SLIST;voidfun( SLIST *h)SLIST *p,

17、*sha nchu;/用于遍歷的指針p,用于刪除的指針shanchup=h-n ext;/p為壽元節(jié)點while(p- next!=NULL)/終止條件/判斷是否有重復(fù)原素if(p-data=p-n ext-data)sha nchu=p-n ext;p-n ext=sha nchu-n ext;free(sha nchu);elsep=p-n ext;SLIST *creatlist(i nt*a) SLIST *h,*p,*q;int i;h=p=(SLIST *)malloc(sizeof(SLIST);for(i=0; idata=ai;p_n ext=q;p=q;p_n ext=0;

18、return h;void outlist(SLIST *h) SLIST *p;p=h-n ext;if (p=NULL) prin tf(nThe list is NULL!n ”); else while(p!=NULL); prin tf(nHead);do prin tf(-%d,p-data);p=p-n ext;prin tf(-E ndn);mai n() SLIST *head;int aN=1,2,2,3,4,4,4,5;head=creatlist(a);printf(nThe list before deleting :n);fun( head);outlist(hea

19、d);outlist(head);printf(nThe list after deleting :n);參考材料4、/在ma in函數(shù)中多次調(diào)用fun函數(shù)，每調(diào)用一次fun函數(shù)，輸出鏈表尾部節(jié)點中的 數(shù)據(jù)，并釋放該節(jié)點，使得鏈表縮短。#i nclude#i nclude#define N 8typedef struct list int data;struct list *n ext; SLIST;void fun( SLIST *p)SLIST *bianli,*shanchu;/ 遍歷，刪除bia nli=p;while(bia nl i- next-next!=NULL)bia nli

20、=bia nli-n ext;/輸出/釋放prin tf(%d,bia nl i- next-data);sha nchu=bia nl i-n ext;free(sha nchu);bia nli- next=NULL;SLIST *creatlist(i nt*a) SLIST *h,*p,*q;int i;h=p=(SLIST *)malloc(sizeof(SLIST); for(i=0; idata=ai; p_n ext=q; p=q;p_n ext=0;return h;void outlist(SLIST *h) SLIST *p;p=h-n ext;if (p=NULL) p

21、rin tf(nThe list is NULL! n);else prin tf(nHead);do prin tf(-%d,p-data);p=p- next; while(p!=NULL);prin tf(-E ndn);main () SLIST *head;int aN=11,12,15,18,19,22,25,29;head=creatlist(a);prin tf(nO utput from head: n);outlist(head);prin tf(nO utput from tail: n ”);while (head- next != NULL)fun( head);pr

22、in tf(nn);prin tf(nO utput from head aga in :n);outlist(head);Output from head：Head-ll-12-15-18-19-22-25-29-EndOutput froBn til：29Output from head 也刖in :Hlsad-11-12-15- 18- 19-22-25-End25Output froon head again :Head-11-12-15-18-19-22-End22Output from h呂宣日 again :Head-11-12-15-18-19-Bnd19Output from

23、 head iftgain :Head-ll-12-15-18-RndISOutput from head again :Hyad-ll-12-15-End15Ou.tjut from head aigain :|Hgid-ll-L2-EndOutput from head again :Read-U-12-End12Output from head again :Head-K-End11Output from head again :The list is NULL!Press any key to continue,5、實現(xiàn)約瑟夫環(huán)函數(shù)（選做）#in elude#in eludetyped

24、ef struct list int data;struct list*n ext; SLIST;SLIST *creatlist(int m)int i;SLIST *tou,*p,*wei;/頭指針 生成節(jié)點指針 尾指針tou=(SLIST*)malloc(sizeof(SLIST); / 頭節(jié)點wei=tou;printf(請輸入%d個數(shù)用空格隔開：n”,m);for(i=0;idata);wei-n ext=p;wei=p;wei-next=tou-next;/令最后一個原素指向首元結(jié)點成環(huán)return tou;void outlist(SLIST *h,i nt m,i nt c)i

25、nt i;SLIST *p,*shanchu;/用于遍歷的指針p，用于刪除的指針參考材料shanchup=h-n ext;while(p!=p- next)for(i=1;in ext;sha nchu=p-n ext;printf(%d ,shanchu-data); p-n ext=sha nchu-n ext; free(sha nchu);p=p-n ext;prin tf(%d,p-data);free(p);free(h);mai n() SLIST *head;int m,c;printf(請分別輸入 m和c的值/p指向首元結(jié)點/當環(huán)中只剩下一個原素時結(jié)束/根據(jù)輸入的c剔除節(jié)點/

26、sha nchu指向當前要剔除的節(jié)點II將shanchu指針指向的節(jié)點出環(huán)/輸出最后的一個節(jié)點的內(nèi)容);scan f(%d,%d,&m,&c);head=creatlist(m);outlist(head,m,c);四、實驗報告要求1、撰寫實驗報告；2、對實驗中出現(xiàn)的問題和結(jié)果進行總結(jié)實驗三 棧的實現(xiàn)和應(yīng)用一、實驗?zāi)康?、掌握棧的建立方法；判斷空棧等；2、掌握棧的基本操作，如入棧、出棧、3、棧的應(yīng)用。二、實驗內(nèi)容1、順序棧的初始化2、判斷棧是否為空3、順序棧出棧4、順序棧入棧5、棧的應(yīng)用-漢諾塔三、實驗提示1、棧的基本操作，按提示將函數(shù)補充完整#i nclude #i nclude #defi

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

28、tack st;init(&st);push(&st,5);push(&st,6);prin tf(%d,pop(&st);return 0;6Press any key to continue2、#inelude void mai n()void hanoi(int n, char on e,ehar two,ehar three);/*對hanoi函數(shù)的聲明 */int m;prin tf(i nput the nu mber of diskes:);scan f(%d, &m);prin tf(The step to move ing %d diskes:n,m);han oi(m,A,

29、B,C);void hanoi(int n, char on e,char two,char three)/* 定義hanoi函數(shù)將n個盤從one座借助two座，移到three座*/static k=1;/定義靜態(tài)變量k用來標明走了多少步參考材料void move(char x,char y);/因為move函數(shù)定義在該函數(shù)的后邊且之前咩有聲明在此需要提前聲明才能使用if(n=1)個上printf(第 %d 步:,k+); move(on e,three);elsehanoi(n-1, on e,three,two);座當橋梁printf(第 %d 步:,k+); move(on e,thre

30、e);hanoi(n-1,two ,on e,three);上，第一個盤當橋梁/當?shù)谝粋€座上僅剩一個盤的時候?qū)⒋吮P移到第三/輸出是第多少步/移動/將前n-1個盤從第一個座移到二個座上，第三個/將上邊轉(zhuǎn)移到第二個座上的盤轉(zhuǎn)移到第三個盤void move(char x,char y)/*定義move函數(shù)*/prin tf(%c-%c n,x,y);u A A c B c C- e -h - c B A A B t ff-AABACCAAB tst:f:f:1K1K:步步步步步步 u 步涉步啦步步步步井6 1 2 CO 4 5 P6123456*609111111 n hB-pgrgma-i-gET

31、lrjyr?s-Fgrjln nBpgr?gr?gRgr?四、實驗報告要求1、撰寫實驗報告；2、對實驗中出現(xiàn)的問題和結(jié)果進行總結(jié)參考材料實驗四隊列的實現(xiàn)和應(yīng)用一、實驗?zāi)康?、掌握隊列的建立方法；2、 掌握隊列的基本操作，如出隊、入隊、判斷隊空等；3、隊列的應(yīng)用。二、實驗內(nèi)容1、順序隊列的初始化2、判斷隊列是否為空3、順序隊列出隊4、順序隊列入隊5、隊列的應(yīng)用-回文判斷三、實驗提示1、/隊列的基本操作，按提示將函數(shù)補充完整#i nclude #i nclude #defi ne STACK_MAX 100 typedef structint front, rear;int data1STACK_

32、MAX; Queue;void initQueue (Queue *q) /*初始化隊列 */q_fron t=q_rear=O;int EmptyQueue(Queue *q)/* 判斷隊列空 */if(q-fron t=q-rear)return 1;/1 代表空elsereturn 0;/0代表非空int DeQueue(Queue *q)/* 出隊列 */if(q-rear=q-fr ont)/判斷需要出隊時隊列是否為空printf(當前隊列已經(jīng)空了 。)；exit(O);elsereturn q-data1q-front+;/將隊頭原素出列然后隊頭指針加一void InQueue(Q

33、ueue *q,int data)/* 入隊列 */if(q-rear=STACK_MAX)/判斷需要入隊時隊列是否已滿printf(”當前隊列空間已滿。)；exit(O);elseq-data1q-rear=data;/ 入隊q-rear+;int mai n()Queue q;in itQueue( &q);In Queue(&q,1);In Queue(&q,2);In Queue(&q,3);prin tf(%dn,DeQueue(&q);prin tf(%dn,DeQueue( &q);prin tf(%dn,DeQueue(&q);i：ress any key to continu

34、e2、/判斷給定的字符序列是否是回文(提示：將一半字符入棧)#i nclude #i nclude #defi ne STACK_MAX 100typedef structint top;int dataSTACK_MAX; stack;typedef structint 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)

35、/* 出棧 */if(st-top=0)printf(棧已空!);exit(0);elsechar c;c=st_data_st_top;return (int) c;void push(stack *st,int data) /* 入棧 */if(st-top=STACK_MAX-1)printf(棧已空!);exit(O);elsest-datast-top+=data;void initQueue (Queue *q) /* 初始化隊列 */q_fron t=q_rear=O;int EmptyQueue(Queue *q)/* 判斷隊列空 */if(q-fron t=q-rear)re

36、turn 1;elsereturn 0;int DeQueue(Queue *q)/* 出隊列 */retur n (in t)q-data1q-fr on t+;void InQueue(Queue *q,int data) /* 入隊列 */q_data1q_rear+=data;int IsHuiWe n(stack *st,Queue *q,char * a)int i,zhan,dui,k=0;/i計數(shù)，zhan代表應(yīng)往棧里邊傳幾個原素，dui代表應(yīng)從第幾個原素開始往隊列傳值，k計算數(shù)組a中有多少原素while(ak!=0)k+;if(k%2=0)zha n=k/2;dui=k/2+

37、1;if(k%2=1)zha n=k/2;dui=k/2+2;for(i=0;izha n;i+)push(st,ai);for(i=zha n;ik;i+)In Queue(q,ai);for(i=0;ik/2;i+)if(pop(st)!=DeQueue(q)return 0;return 1;int mai n()char a10=a,b,c,d,b,a;stack st;Queue q;init(& st);in itQueue( &q);prin tf(%dn,lsHuiWe n(&st, &q,a);0Press any key to continue四、實驗報告要求1、撰寫實驗報

38、告；2、對實驗中出現(xiàn)的問題和結(jié)果進行總結(jié)參考材料參考材料實驗五二叉樹的遍歷及應(yīng)用一、實驗?zāi)康?.掌握二叉樹的定義；樹的深度計算2 .掌握二叉樹的基本操作，如二叉樹的建立、遍歷、結(jié)點個數(shù)統(tǒng)計二、實驗內(nèi)容用遞歸的方法實現(xiàn)以下算法：1 .以二叉鏈表表示二叉樹，建立一棵二叉樹；2 .輸出二叉樹的中序遍歷結(jié)果；3 .輸出二叉樹的前序遍歷結(jié)果；4 .輸出叉樹的后序遍歷結(jié)果；5 .計算二叉樹的深度；6 .統(tǒng)計二叉樹的結(jié)點個數(shù)；7、二叉樹的層序遍歷結(jié)果。三、實驗提示1、按要求將程序補充完整#in elude #in elude #i nclude #defi ne NULL 0 typedef struct

39、BiTNode char data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;/二叉樹的建立BiTree Create(BiTree T)char ch;/設(shè)置一個接收數(shù)據(jù)的變量sca nf(%c, &ch);if(ch=#)T=NULL;/ 設(shè)置結(jié)束符elseT = (BiTree)malloc(sizeof(BiTNode);/ 生成心節(jié)點T-data = ch;T-lchild = Create(T-lchild);/ 遞歸建立T-rchild = Create(T-rchild);return T;/二叉樹的前序遞歸遍歷 void P

40、reorder(BiTree T)if(T)prin tf(%c ”,T-data);Preorder(T-lchild);Preorder(T-rchild);/統(tǒng)計二叉樹的結(jié)點個數(shù)int Sumleaf(BiTree T)int n;if(T=NULL) retur n 0;elsen=1+Sumleaf(T-lchild)+Sumleaf(T-rchild);return n;/二叉樹的中序遞歸遍歷void zhon gxu(BiTree T)if(T)Preorder(T-lchild);prin tf(%c ”,T-data);Preorder(T-rchild);/二叉樹的后序遞歸遍歷void houxu(BiTree T)if(T)Preorder(T-lchild);Preorder(T-rchild); prin tf(%c ,T-data);/計算二叉樹的深度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-rchild)+1;void