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

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

2、杂度二、实验提不'1、#include <stdio.h>#define MAXSIZE 20typedef structint dataMAXSIZE;int last;list;/*编写函数，实现在顺序表中查找值为x的元素的位置的简单顺序查找算法，编写主函数验证此算法，并分析算法的时间复杂度 */int locate(list *l,int 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的值：");scanf("%d",&x);p=locate(&b,x);if(p=-1)printf("no!");elseprintf("position=%dn",p);青询人犬的值:5>osition43ress any key to contini_ue请输入K的值！ 100；no! Press any key to continue.时间复杂度T(n)=O(n)；2、#include <stdio.h

4、>#define MAXSIZE 20typedef structint dataMAXSIZE;int last;list;/*编写函数，实现在顺序表中删除第i个位置上的元素，编写主函数验证此算法，并分析算法的时间复杂度*/int delete(list *l,int i)int j,k,p;定义一个用来保存被删原素；if(i>=0&&i<l->last)/只接受有效输入for( j=0;j<l->last;j+)/ 遍历数组if(j=i-1)匹配p=l->dataj; /保存被删原素；for(k=j;k<l->last;

5、k+)/ 前进一位；l->datak=l->datak+1;break;/退出循环l->last=l->last-1;return p;/对于此题来说可以输出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的值：")；scanf("%d",&x);if(delete(&b,x)!=0)for(i=0;i<b.last;i+)printf("%3d",b.data

6、i);elseprintf("Error!");青输入苫的值士 5-2 345 7 89 10 UPress any key to c antinueterror!Press any key to continue时间复杂度T(n)=O(n)；3、#include<stdio.h>#define MAXSIZE 20 typedef structint dataMAXSIZE;int last;list;/*编写函数，实现在顺序表中第i个位置上插入值为x的元素，编写主函数验证此算法，并分析算法的时间复杂度 */int insert(list *l,int x,i

7、nt i)int j,k;if(i<=l->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;retur

8、n 0;/无效位置main()list b;int x,i;b.last=10;for(i=0;i<b.last;i+)b.datai=i+2;printf("请输入x的值：")；scanf("%d",&x);if(insert(&b,66,x)!=0)for(i=0;i<b.last;i+)printf("%3d",b.datai);elseprintf("Error!");请输入x的值；523 45 66 67 89 10 HPress any key to continue请输入H

9、的值；100.Error!Press any key to continue时间复杂度T(n)=O(n)；4、#include <stdio.h>#define MAXSIZE 20typedef structint dataMAXSIZE;int last;list;/*编写函数，实现在顺序表中将所有偶数排在所有奇数前面，编写主函数验证此算法并分析算法的时间复杂度*/void fun(list *l)这个代码有点晦涩，但空间时间复杂度是鸡儿低int i,ou=0,temp;/i计数，ou代表偶数个数专业 word可编辑判断是不是偶数，如果是偶数的话和当前第if(l->dat

10、ai%2=0)ou个位置的原素交换位置temp=l->dataou;l->dataou=l->datai;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.last;i+)printf("b.data%d=",i);I"scanf("%d",

11、&b.datai);fun(&b);for(i=0;i<b.last;i+)printf("%3d",b.datai);,data ,data ,data .data .data .data .data .data .data .dataL=22 =3=4L4=5L - 1 5：67：8g=6 =7=S =9 =10当前数组中偶数有5个,奇毅有5个：246 S 10 3 7 1g 5Preg§ any key to continue-时间复杂度为T(n)=O(n)；四、实验报告要求1、撰写实验报告；2、对实验中出现的问题和结果进行总结专业 w

12、ord可编辑实验二 链表的实现和应用一、实验目的1、掌握链表的定义；2、掌握链表的基本操作，如查找、插入、删除、排序等。二、实验内容1、单链表的创建2、单链表的查找3、单链表的排序4、单链表的删除5、链表的应用-约瑟夫环问题二、实验提不'1、创建单链表，要求：结点个数为n个，每个节点数据域的值必须小于m。编辑主函数验证之。#include <stdio.h>#include <stdlib.h>typedef struct aa int data;struct aa *next; NODE;NODE *Creatlink(int n, int m)int i;N

13、ODE *tou,*p;/tou 头结点tou=(NODE*)malloc(sizeof(NODE);/ 创建并初始化头结点tou->next=NULL;tou->data=n;printf("请输入d个小鱼d的数，中间用空格隔开：n",n,m);for(i=0;i<n;i+)/ 头插法p=(NODE*)malloc(sizeof(NODE);scanf("%d",&p->data);if(p->data>=m)printf("输入的第%d个数据大于 %d,GGn",i+1,m);好像是在头

14、文件exit(0);程序强制中断，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");main() NODE *head;head=Creatlink(8,22);outlink(head);1 23456

15、78 LIST :HEAD ->8 ->7 ->6 ->5 ->4 ->3 ->2 ->1 Press any key to continue.情输入鼻个小鱼22的数.中间用空格隔开:1 2 3 100 5 6 7 8输人的第4个数据大于221GGPress any ksy to continue2、查找值为ch的节点在链表中是否出现，如果存在，返回在链表中位序，如果不存在返回0#include<stdio.h>#include<stdlib.h>#definetypedef struct list int data;st

16、ruct list *next; SLIST;SLIST *creatlist(char *);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->next;return 0;ch;main() SLIST *head;int k; charchar aN='m','p','g','a',W,'x&#

17、39;,'r','d'head=creatlist(a);outlist(head);printf("Enter a letter:");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

18、(sizeof(SLIST);/ 创建并初始化头结点tou->data=N;tou->next=NULL;for(i=0;i<N;i+)/ 前叉法p=(SLIST*)malloc(sizeof(SLIST);p->data=ai;p->next=tou->next;tou->next=p;return tou;void outlist(SLIST *h) SLIST *p;p=h->next;if (p=NULL) printf("nThe list is NULL!n"); else printf("nHead&q

19、uot;);do printf("->%c",p->data); p=p->next; while(p!=NULL);printf("->Endn");lead->d->r->x->w->a->g->p->m->EndWriter a Letter：g 'he sequence nuiriber is : 6 ress any key to continue.Efead->ci->r->i->w>a->g->p->in-&

20、gt;EndEnter a letter：zNot found!Press any key to continue3、去偶操作，链表中各节点按数据域递增有序链接，函数fun的功能是，删除链表中数据域值相同的节点，使之只保留一个专业 word可编辑#include<stdio.h>专业 word可编辑#include <stdlib.h>#define N 8 typedef struct list int data;struct list *next; SLIST; void fun( SLIST *h) 用于遍历的指针 p,用于删除的指针shanchu/p为寿元节点/

21、终止条件/判断是否有重复原素SLIST *p,*shanchu;p=h->next; while(p->next!=NULL) if(p->data=p->next->data)shanchu=p->next;p->next=shanchu->next; free(shanchu);else p=p->next;SLIST *creatlist(int *a) SLIST *h,*p,*q; int i;h=p=(SLIST *)malloc(sizeof(SLIST);for(i=0; i<N; i+) q=(SLIST *)mal

22、loc(sizeof(SLIST); q->data=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 printf("->%d",p->data); p=p->next; while(p!=NULL); printf("->Endn&q

23、uot;);main() SLIST *head;intaN=1,22344,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 :Hgad->l->2->2->3->4->4->4->5->EndThe list after del

24、eting ;Head->P>2->3->4->5->EndPress any key to continue4、在main函数中多次调用fun函数，每调用一次fun函数，输出链表尾部节点中的 数据，并释放该节点，使得链表缩短。#include<stdio.h>#include<stdlib.h>#define N 8 typedef struct list int data;struct list *next; SLIST; void fun( SLIST *p) SLIST *bianli,*shanchu;/ 遍历,删除bian

25、li=p;while(bianli->next->next!=NULL)bianli=bianli->next;输出释放printf("%d",bianli->next->data);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; i<N; i+) q=(SLIST *)malloc(size

26、of(SLIST);q->data=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 printf("->%d",p->data); p=p->next; while(p!=NULL); printf("->Endn");main

27、() 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);专业 word可编辑Output f

28、rom head：Head->15->18->19->22->25->29->EndOutput from tail： 29Output from head 国目日in :EM 25Output froon head again :Head->ll->12->15->18->19->22->End 22Output from had again :Had->ll->12->15->18->19->End19Output from head iftgain :Head->

29、ll->12->15->18->BnriISOutput from head again :Hyad->ll->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

30、continue,5、实现约瑟夫环函数（选做）#include<stdio.h>#include<stdlib.h>typedef struct list int data;struct list *next; SLIST;SLIST *creatlist(int m) int i;SLIST *tou,*p,*wei;/头指针生成节点指针尾指针tou=(SLIST*)malloc(sizeof(SLIST); / 头节点wei=tou;printf("请输入d个数用空格隔开：n",m);for(i=0;i<m;i+)/ 尾插法p=(SLIST

31、*)malloc(sizeof(SLIST);scanf("%d",&p->data);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 ,用于删除的指针专业 word可编辑shanchup=h->next;while(p!=p->next)for(i=1;i<c-1;i+)p=p->next;shanchu

32、=p->next;printf("%d ",shanchu->data);p->next=shanchu->next;free(shanchu);p=p->next;printf("%d",p->data);free(p);free(h);main() SLIST *head;int m,c;printf("请分别输入 m和c的值/p指向首元结点/当环中只剩下一个原素时结束根据输入的c剔除节点/shanchu指向当前要剔除的节点/将shanchu指针指向的节点出环输出最后的一个节点的内容");sca

33、nf("%d,%d",&m,&c);head=creatlist(m);outlist(head,m,c);四、实验报告要求1、撰写实验报告；2、对实验中出现的问题和结果进行总结实验三 栈的实现和应用一、实验目的1、掌握栈的建立方法；2、掌握栈的基本操作，如入栈、出栈、判断空栈等；3、栈的应用。二、实验内容1、顺序栈的初始化2、判断栈是否为空3、顺序栈出栈4、顺序栈入栈5、栈的应用-汉诺塔二、实验提不'1、栈的基本操作，按提示将函数补充完整#include <stdio.h>#include <stdlib.h>#define

34、 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;空 0elsereturn 1;/ 非空 1 int pop(stack *st) /* 出栈 */return st->data-st->top;void push(stack *st,int data) /* 入栈 */st->datast->t

35、op+=data;int main(void)stack st;init(&st);push(&st,5);push(&st,6);printf("%d",pop(&st);return 0;6Press any key to continue2、#include <stdio.h>void main()void hanoi(int n,char one,char two,char three);/*对hanoi函数的声明*/int m;printf("input the number of diskes:")

36、;scanf("%d",&m);printf("The step to moveing %d diskes:n",m);hanoi(m,'A','B','C');void hanoi(int n,char one,char two,char three)/* 定义hanoi函数，将n个盘从one座借助two座，移到three座*/static k=1;定义静态变量k用来标明走了多少步void move(char x,char y);因为move函数定义在该函数的后边且之前咋有声明在此需要提前声明才能

37、使用if(n=1)个上printf(" H%d 步:",k+);move(one,three);elsehanoi(n-1,one,three,two);座当桥梁printf(" H%d 步:",k+);move(one,three);hanoi(n-1,two,one,three);上，第一个盘当桥梁/当第一个座上仅剩一个盘的时候将此盘移到第三/输出是第多少步移动将前n-1个盘从第一个座移到二个座上，第三个/将上边转移到第二个座上的盘转移到第三个盘void move(char x,char y)/*定义move函数*/printf("%c-&

38、gt;%cn",x,y);7：A>B7：C>A5: C-圮 步:Abinput the number of diskes:4 he step to moveing 4 diskes：7：A>C10步:BA11步:C-A>C13步:A>B:A->C:B>Cress any key to continue四、实验报告要求1、撰写实验报告；2、对实验中出现的问题和结果进行总结专业 word可编辑一、实验目的1、掌握队列的建立方法；2、掌握队列的基本操作，如出队、入队、判断队空等；3、队列的应用。二、实验内容1、顺序队列的初始化2、判断队列是否为空3

39、、顺序队列出队4、顺序队列入队5、队列的应用-回文判断二、实验提不'1、队列的基本操作，按提示将函数补充完整#include <stdio.h>#include <stdlib.h>#define STACK_MAX 100typedef structint front, rear;int data1STACK_MAX; Queue;void initQueue (Queue *q) /*初始化队列 */q->front=q->rear=0;int EmptyQueue(Queue *q)/*判断队列空 */if(q->front=q->

40、rear)return 1;/1 代表空elsereturn 0;/0代表非空int DeQueue(Queue *q)/* 出队列 */if(q->rear=q->front)/判断需要出队时队列是否为空printf("当前队列已经空了 。")；exit(0);elsereturn q->data1q->front+; /将队头原素出列然后队头指针加一void InQueue(Queue *q,int data) /* 入队列*/if(q->rear=STACK_MAX)/判断需要入队时队列是否已满printf("当前队列空间已满。

41、")；exit(0);elseq->data1q->rear=data;/ 入队q->rear+;int main()Queue q;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、判断给定

42、的字符序列是否是回文(提示：将一半字符入栈)#include <stdio.h>#include <stdlib.h>#define 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;elser

43、eturn 0;int pop(stack *st) /* 出栈 */if(st->top=0)printf("栈已空！")；exit(0);elsechar c;专业 word可编辑c=st->data-st->top;return (int) c;void push(stack *st,int data)/* 入栈 */if(st->top=STACK_MAX-1)printf("栈已空！")；exit(0);elsest->datast->top+=data;void initQueue (Queue *q) /

44、*初始化队列 */q->front=q->rear=0;int EmptyQueue(Queue *q)/* 判断队列空 */if(q->front=q->rear)return 1;elsereturn 0;int DeQueue(Queue *q)/* 出队列 */return (int)q->data1q->front+;void InQueue(Queue *q,int data) /* 入队列*/q->data1q->rear+=data;int IsHuiWen(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)zhan=k/2;dui=k/2+1;if(k%2=1)zhan=k/2;dui=k/2+2;for(i=0;i<zhan;i+)push(st,ai);for(i=zhan;i<k;i+)InQueue(q,ai);for(i=0;i<k/2;