数据结构与算法实验指导书

1、数据结构与算法实验报告綦娜娜 编哈尔滨理工大学荣成学院实验一顺序表的实现和应用一、实验目的1、 掌握顺序表的定义；2、 掌握顺序表的基本操作，如查找、插入、删除及排序等。二、实验内容1、 编写函数，实现在顺序表中查找值为x的元素的位置的简单顺序查找算法，编写主函数验证此算法，并分析算法的时间复杂度2、 编写函数，实现在顺序表中删除第i个位置上的元素，编写主函数验证此算法，并 分析算法的时间复杂度3、 编写函数，实现在顺序表中第i个位置上插入值为x的元素，编写主函数验证此算法，并分析算法的时间复杂度4、 编写函数，实现在顺序表中将所有偶数排在所有奇数前面，编写主函数验证此算 法，并分析算法的时间

2、复杂度三、实验提示1、#inelude <stdio.h>#define MAXSIZE 20typedef structint dataMAXSIZE;int last;list;/*编写函数，实现在顺序表中查找值为x的元素的位置的简单顺序查找算法，编写主函数验证此算法，并分析算法的时间复杂度*/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;/*编写函数，实现在顺序表中删除第 i个位置上的元素，编写主函数验证此算法，并分析算法的时间复杂度*/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+)/ 遍历数组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退出循环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;/*编写函数，实现在顺序表中第i个位置上插入值为x的元素，编写主函数验证此算法，并分析算法的时间复杂度*/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要插入到整个数组之后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;/ 数值长度加一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;/*编写函数，实现在顺序表中将所有偶数排在所有奇数前面，编写主函数验证此算法并分析算法的时间复杂度*/void fun( list *l)/这个代码有点晦涩，但空间时间复杂度是鸡儿低int i,ou=0,temp;/i计数，ou代表偶数个数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;/循环/判断是不是偶数，如果:偶数的话和当前第/偶数个数加一printf("当前数组中偶数有%d个,奇数有%d个:n",ou,l->last-ou);main () list b;int i=0,m=0;b.last=10;printf（"请输入数组元素的值：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青输人数组兀素的荷：L, datab, dataib, data2b. data3=4ba dnt良4=5b- data5=6b. data=7b. dataT=Sb. data8=9b. datag=10二Hi 駅:且中偶数有5个，奇数有5个：2 468 103 719 SPres旦 any key to】 continue/时间复杂度为T(n)=0(n);四、实验报告要求1、撰写实验报告；2、对实验中出现的问题和结果进行总结实验二 链表的实现和应用一、实验目的1、掌握链表的定义；2、 掌握链表的

12、基本操作，如查找、插入、删除、排序等。二、实验内容1、单链表的创建2、单链表的查找3、单链表的排序4、单链表的删除5、链表的应用-约瑟夫环问题三、实验提示1、/创建单链表，要求：结点个数为n个，每个节点数据域的值必须小于m。编辑主函数验证之。#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);/ 创建并初始化头结点tou-> next=NULL;tou->data=n;printf("请输入%d个小鱼%d的数，中间用空格隔开：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个数据大于 %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个数据大于22：GGPress any ksy to continue2、/查找值为ch的节点在链表中是否出现，如果存在，返回在链表中位序，如果不存 在返回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赋值为寿元节点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); / 创建并初始化头结点

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、/去偶操作，链表中各节点按数据域递增有序链接，函数fun的功能是，删

20、除链表中 数据域值相同的节点，使之只保留一个#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为寿元节点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函数中多次调用fun函数，每调用一次fun函数，输出链表尾部节点中的 数据，并释放该节点，使得链表缩短。#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、实现约瑟夫环函数（选做）#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;/头指针 生成节点指针 尾指针tou=(SLIST*)malloc(sizeof(SLIST); / 头节点wei=tou;printf("请输入%d个数用空格隔开：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;/令最后一个原素指向首元结点成环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指向首元结点/当环中只剩下一个原素时结束/根据输入的c剔除节点/sha nchu指向当前要剔除的节点II将shanchu指针指向的节点出环/输出最后的一个节点的内容");scan f("%d,%d",&m,&c);head=creatlist(m);outlist(head,m,c);四、实验报告要求1、撰写实验报告；2、对实验中出现的问题和结果进行总结实验三 栈的实现和应用一、实验目的1、掌握栈的建立方法；2、掌握栈的基本

33、操作，如入栈、出栈、判断空栈等；3、栈的应用。二、实验内容1、顺序栈的初始化2、判断栈是否为空3、顺序栈出栈4、顺序栈入栈5、栈的应用-汉诺塔三、实验提示1、栈的基本操作，按提示将函数补充完整 #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函数的声明 */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函数将n个盘从one座借助two座，移到three座*/static k=1;II疋义静态变量k用来标明走了多少步void move(char x,char y);II因为move函数定义在该函数的后边且之前咩有声明在此需要提前声明才能使用if(n=1)II当第一个座上仅剩一个盘的时候将此盘移到第三个上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函数*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、对实验中出现的问题和结果进行总结实验四队列的实现和应用一、实验目的1、掌握队列的建立方法；2、 掌握队列的基本操作，如出队、入队、判断队空等；3、队列的应用。二、实验内容1、顺序队列的初始化2、判断队列是否为空3、顺序队列出队4、顺序队列入队5、队列的应用-回文判断三、实验提示1、/队列的基本操作，按提示将函数补充完整#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("当前队列已经空了 。")；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计数，zhan代表应往栈里边传几个原素，dui代表应从第几个原素开始往队列传值，k计算数组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,