數(shù)據(jù)結構與算法實驗指導書

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

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

3、i<b.last;i+)b.datai=i+2;printf("請輸入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.時間復雜度T(n)=O(n);2、#inelude<stdio.h>#

4、define MAXSIZE 20typedef structint dataMAXSIZE;int last;list;/*編寫函數(shù)，實現(xiàn)在順序表中刪除第 i個位置上的元素，編寫主函數(shù)驗證此算法，并分析算法的時間復雜度*/int delete(list *l,int i)int j,k,p;II定義一個用來保存被刪原素；if(i>=0&&i<l->last)II只接受有效輸入for( j=O;j<l->last;j+)/ 遍歷數(shù)組if(j=i-1)/ 匹配p=l->dataj; II保存被刪原素；for(k=j;k<l->las

5、t;k+) II 前進一位；l->datak=l->datak+1;break;II退出循環(huán)l->last=l->last-1;return p;II對于此題來說可以輸出p;return 0;main ()list b;int x,i;b.last=10;for(i=0;i<b.last;i+)b.datai=i+2;printf("請輸入x的值：”)； scan f("%d"，& x);if(delete(&b,x)!=O)for(i=0;i<b .l ast;i+)prin tf("%3d"

6、;,b.datai);elseprin tf("Error!");幘嶽心的庫52345789 10 UPress any key to can ti nue/時間復雜度T(n)=O(n);3、#include<stdio.h>#defi ne MAXSIZE 20 typedef structint dataMAXSIZE;int last;list;/*編寫函數(shù)，實現(xiàn)在順序表中第i個位置上插入值為x的元素，編寫主函數(shù)驗證此算法，并分析算法的時間復雜度*/int in sert(list *l,i nt x,i nt i)int j,k;if(i<=l-&

7、gt;last+1 &&i>0)if(i=l->last+1)/特殊值last+1要插入到整個數(shù)組之后l->datal->last=x;elsefor( j=0;j<l->last;j+)if(j=i-1)/ 匹配for(k=l->last;k>j;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;

8、int x,i;b.last=10;for(i=0;i<b.l ast;i+)b.datai=i+2;printf("請輸入x的值：”)；scan f("%d"，& x);if(in sert(&b,66,x)!=0)for(i=0;i<b .l ast;i+)prin tf("%3d",b.datai); elseprin tf("Error!");請輸入丫的值=52 3 4 5 66 6 789 10 llPress any key to continue/時間復雜度T(n)=O(n);#in

9、 elude<stdio.h>#defi ne MAXSIZE 20typedef structint dataMAXSIZE;int last;list;/*編寫函數(shù)，實現(xiàn)在順序表中將所有偶數(shù)排在所有奇數(shù)前面，編寫主函數(shù)驗證此算法并分析算法的時間復雜度*/void fun( list *l)/這個代碼有點晦澀，但空間時間復雜度是雞兒低int i,ou=0,temp;/i計數(shù)，ou代表偶數(shù)個數(shù)OUfor(i=0;i<l_>last;i+)if(l->datai%2=0)個位置的原素交換位置temp=l->dataou;l->dataou=l->d

10、atai;l->datai=temp;ou+=1;/循環(huán)/判斷是不是偶數(shù)，如果:偶數(shù)的話和當前第/偶數(shù)個數(shù)加一printf("當前數(shù)組中偶數(shù)有%d個,奇數(shù)有%d個:n",ou,l->last-ou);main () list b;int i=0,m=0;b.last=10;printf（"請輸入數(shù)組元素的值：n"）;for(i=0;i<b.l ast;i+)prin tf("b.data%d=",i);scan f("%d", &b.datai);fun(&b);for(i=0;i

11、<b.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 719 SPres旦 any key to】 continue/時間復雜度為T(n)=0(n);四、實驗報告要求1、撰寫實驗報告；2、對實驗中出現(xiàn)的問題和結果進行總結實驗二 鏈表的實現(xiàn)和應用一、實驗目的1、掌握鏈表的定義；2、 掌握鏈表的

12、基本操作，如查找、插入、刪除、排序等。二、實驗內容1、單鏈表的創(chuàng)建2、單鏈表的查找3、單鏈表的排序4、單鏈表的刪除5、鏈表的應用-約瑟夫環(huán)問題三、實驗提示1、/創(chuàng)建單鏈表，要求：結點個數(shù)為n個，每個節(jié)點數(shù)據(jù)域的值必須小于m。編輯主函數(shù)驗證之。#i nclude <stdio.h>#i nclude <stdlib.h>typedef struct aa int data;struct aa *n ext; NODE;NODE *Creatli nk(i ntn, i nt m)int i;NODE *tou,*p;tou 頭結點tou=(NODE*)malloc(siz

13、eof(NODE);/ 創(chuàng)建并初始化頭結點tou-> next=NULL;tou->data=n;printf("請輸入%d個小魚%d的數(shù)，中間用空格隔開：n",n,m);for(i=0;i<n;i+)/ 頭插法p=(NODE*)malloc(sizeof(NODE);scan f("%d"，& p->data);if(p->data>=m)printf("輸入的第%d個數(shù)據(jù)大于 %d,GGn",i+1,m);好像是在頭文件exit(0);/程序強制中斷，stdlib.h 里p->n

14、ext=tou->n ext; tou->n ext=p;return tou;outli nk(NODE *h) NODE *p;p=h->n ext;prin tf("nn THELIST :nnHEAD ”);while(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 2345678pHE LIST :HEAD ->8 ->7 ->

15、;6 ->5 ->4 ->3 ->2 ->1 Press any key to uontinu匚1 2 3 100 5 6 7 8綁入的第4個數(shù)據(jù)大于22：GGPress any ksy to continue2、/查找值為ch的節(jié)點在鏈表中是否出現(xiàn)，如果存在，返回在鏈表中位序，如果不存 在返回0<stdio.h><stdlib.h>#in clude#in clude#defi neN 8typedef struct list int data;struct list*n ext; SLIST;SLIST *creatlist(char

16、*);void outlist(SLIST *);int fun( SLIST *h, char ch)int i;SLIST *p;p=h->next;/p賦值為壽元節(jié)點for(i=0;i<N;i+)if(p->data=ch)return i+1;p=p->n ext;return 0;main () SLIST *head;int k;char ch;char aN='m','p','g','a','w','x','r','d'head=

17、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(sizeof(SLIST); / 創(chuàng)建并初始化頭結點

18、tou->data=N;tou-> next=NULL;for(i=0;i<N;i+)/ 前叉法p=(SLIST*)malloc(sizeof(SLIST);p_>data=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 e

19、xt;do prin tf("->%c",p->data);while(p!=NULL); prin tf("->E ndin ”);Headj>dj>r->x->w->a->g->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的功能是，刪

20、除鏈表中 數(shù)據(jù)域值相同的節(jié)點，使之只保留一個#in clude<stdio.h>#in clude<stdlib.h>#defi neN8typedefstruct list intdata;struct list*n ext; SLIST;void fun( SLIST *h)SLIST *p,*sha nchu;/用于遍歷的指針 p,用于刪除的指針shanchup=h->n ext;/p為壽元節(jié)點while(p-> next!=NULL)/終止條件if(p->data=p->n ext->data)/判斷是否有重復原素sha nchu=

21、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; i<N; i+) q=(SLIST *)malloc(sizeof(SLIST); q->data=ai;p_>n ext=q;p=q;p_>n ext=0;return h;void outlist(SLIST *h) SLIST *p;

22、p=h->n ext;if (p=NULL)prin tf("nThe list is NULL!'n ”);else prin tf("nHead");p=p->n ext; while(p!=NULL);do prin tf("->%d",p->data);prin tf("->E nd'n");mai n()SLIST *head;int aN=1,2,2,3,4,4,4,5;head=creatlist(a);printf("nThe list before d

23、eleting :n");outlist(head);fun( head);printf("nThe list after deleting :n");outlist(head);4、/在ma in函數(shù)中多次調用fun函數(shù)，每調用一次fun函數(shù)，輸出鏈表尾部節(jié)點中的 數(shù)據(jù)，并釋放該節(jié)點，使得鏈表縮短。#i nclude<stdio.h>#i nclude<stdlib.h>#define N 8typedef struct list int data;struct list *n ext; SLIST;void fun( SLIST *p)

24、SLIST *bianli,*shanchu;/ 遍歷，刪除bia nli=p;while(bia nl i-> next-next!=NULL)bia nli=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(S

25、LIST); for(i=0; i<N; i+) q=(SLIST *)malloc(sizeof(SLIST); q->data=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) prin tf("nThe list is NULL!'n ”);else prin tf("nHead");do prin tf("->%d",p->data);p=p->

26、; 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);prin tf("nn");prin tf(&q

27、uot;nO utput from head aga in :n");outlist(head);Output from head：Head->ll->12->15->18->19->22->25->29->EndOutput froBn t®il：29Output from head 也刖in :Hlsad->11->12->15-> 18-> 19->22->25->End25Output froon head again :Head->11->12->

28、;15->18->19->22->End22Output from h呂宣日 again :Head->11->12->15->18->19->Bnd19Output from head iftgain :Head->ll->12->15->18->RndISOutput from head again :Hyad->ll->12->15->End15Ou.tj>ut from head aigain :|Hgid->ll->L2->EndOutput fr

29、om 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<stdio.h>#in elude<stdlib.h>typedef struct list int data;struct list*n ext; SLIST;SLIST *creatlist(int m)int i;S

30、LIST *tou,*p,*wei;/頭指針 生成節(jié)點指針 尾指針tou=(SLIST*)malloc(sizeof(SLIST); / 頭節(jié)點wei=tou;printf("請輸入%d個數(shù)用空格隔開：n”,m);for(i=0;i<m;i+)/ 尾插法p=(SLIST*)malloc(sizeof(SLIST);scan f("%d"，& p->data);wei->n ext=p;wei=p;wei->next=tou->next;/令最后一個原素指向首元結點成環(huán)return tou;void outlist(SLIST

31、*h,i nt m,i nt c)int i;SLIST *p,*shanchu;/用于遍歷的指針p，用于刪除的指針shanchup=h->n ext;while(p!=p-> next)for(i=1;i<c-1;i+)p=p->n 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)

32、;free(h);mai n() SLIST *head;int m,c;printf("請分別輸入 m和c的值/p指向首元結點/當環(huán)中只剩下一個原素時結束/根據(jù)輸入的c剔除節(jié)點/sha nchu指向當前要剔除的節(jié)點II將shanchu指針指向的節(jié)點出環(huán)/輸出最后的一個節(jié)點的內容");scan f("%d,%d",&m,&c);head=creatlist(m);outlist(head,m,c);四、實驗報告要求1、撰寫實驗報告；2、對實驗中出現(xiàn)的問題和結果進行總結實驗三 棧的實現(xiàn)和應用一、實驗目的1、掌握棧的建立方法；2、掌握棧的基本

33、操作，如入棧、出棧、判斷空棧等；3、棧的應用。二、實驗內容1、順序棧的初始化2、判斷棧是否為空3、順序棧出棧4、順序棧入棧5、棧的應用-漢諾塔三、實驗提示1、棧的基本操作，按提示將函數(shù)補充完整 #i nclude <stdio.h>#i nclude <stdlib.h>#defi 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)

34、return 0;elsereturn 1;判斷棧是否為空*/空0/非空1int pop(stack *st)/* 出棧 */retur n st->data-st->top; void push(stack *st,int data) /* 入棧 */ st->datast->top+=data;int main( void)stack st;init(&st);push(&st,5);push(&st,6);prin tf("%d",pop(&st);return 0;6Press any key to conti

35、nue2、#inelude <stdio.h>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','B','C');void

36、 hanoi(int n, char on e,char two,char three)/* 定義hanoi函數(shù)將n個盤從one座借助two座，移到three座*/static k=1;II疋義靜態(tài)變量k用來標明走了多少步void move(char x,char y);II因為move函數(shù)定義在該函數(shù)的后邊且之前咩有聲明在此需要提前聲明才能使用if(n=1)II當?shù)谝粋€座上僅剩一個盤的時候將此盤移到第三個上printf(” 第 %d 步:",k+);move(on e,three);elsehanoi(n-1, on e,three,two);座當橋梁printf("第

37、%d 步:",k+);move(on e,three);hanoi(n-1,two ,on e,three);上，第一個盤當橋梁/輸出是第多少步/移動II將前n-1個盤從第一個座移到二個座上，第三個/將上邊轉移到第二個座上的盤轉移到第三個盤I*定義move函數(shù)*Ivoid move(char x,char y)prin tf("%c->%c n",x,y);input the number of diskes:4第1步 義車 第4步 筆5步 裁參 第了步The step to moveing 4 diskes: A>BA>CB>CA>

38、B C>AC>BA>BA>C步:A>B :A->C :B>C_ BX 第 16 步:B>A 第11 步:C>A 第>CPress any key to continue四、實驗報告要求1、撰寫實驗報告；2、對實驗中出現(xiàn)的問題和結果進行總結實驗四隊列的實現(xiàn)和應用一、實驗目的1、掌握隊列的建立方法；2、 掌握隊列的基本操作，如出隊、入隊、判斷隊空等；3、隊列的應用。二、實驗內容1、順序隊列的初始化2、判斷隊列是否為空3、順序隊列出隊4、順序隊列入隊5、隊列的應用-回文判斷三、實驗提示1、/隊列的基本操作，按提示將函數(shù)補充完整#i nclu

39、de <stdio.h>#i nclude <stdlib.h>#defi ne STACK_MAX 100 typedef structint front, rear;int data1STACK_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 *

40、q)/* 出隊列 */if(q->rear=q->fr ont)/判斷需要出隊時隊列是否為空printf("當前隊列已經(jīng)空了 。")；exit(O);elsereturn q->data1q->front+;/將隊頭原素出列然后隊頭指針加一void InQueue(Queue *q,int data)/* 入隊列 */if(q->rear=STACK_MAX)/判斷需要入隊時隊列是否已滿printf(”當前隊列空間已滿。")；exit(O);elseq->data1q->rear=data;/ 入隊q->rear+;

41、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 continue2、/判斷給定的字符序列是否是回文(提示：將一半字符入棧)#i nclude <stdio.h>#i

42、nclude <stdlib.h>#defi ne STACK_MAX 100typedef structint top;int dataSTACK_MAX; stack;typedef structint front, rear;int data1STACK_MAX; Queue;void in it(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)else初始化順序棧*/判斷棧空*/*出

43、棧*/printf("棧已空!");exit(0);char 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)/*判

44、斷隊列空 */if(q->fron t=q_>rear)return 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代表應往棧里邊傳幾個原素，dui代表應從第幾個原素開始往隊列傳值，k計算數(shù)組a中有多少原素while(ak!='0')k+;if(k%2=0)zha n=k/2;dui=k/2+1;if(k%2=1)zha n=k/2;dui=k/2+2;for(i=0;i<zha n;i+)push(st,ai);for(i=zha n;i<k;i+)In Queue(q,