数据结构及算法试验参考指导书样本.docx
- 文档编号:7539443
- 上传时间:2023-05-11
- 格式:DOCX
- 页数:36
- 大小:71.72KB
数据结构及算法试验参考指导书样本.docx
《数据结构及算法试验参考指导书样本.docx》由会员分享,可在线阅读,更多相关《数据结构及算法试验参考指导书样本.docx(36页珍藏版)》请在冰点文库上搜索。
数据结构及算法试验参考指导书样本
数据结构及算法试验参考指导书
《数据结构与算法》
实验报告
綦娜娜编
哈尔滨理工大学荣成学院
实验一顺序表的实现和应用
一、实验目的
1、掌握顺序表的定义;
2、掌握顺序表的基本操作,如查找、插入、删除及排序等。
二、实验内容
1、编写函数,实现在顺序表中查找值为x的元素的位置的简单顺序查找算法,编写主函数验证此算法,并分析算法的时间复杂度
2、编写函数,实现在顺序表中删除第i个位置上的元素,编写主函数验证此算法,并分析算法的时间复杂度
3、编写函数,实现在顺序表中第i个位置上插入值为x的元素,编写主函数验证此算法,并分析算法的时间复杂度
4、编写函数,实现在顺序表中将所有偶数排在所有奇数前面,编写主函数验证此算法,并分析算法的时间复杂度
三、实验提示
1、#include<>
#defineMAXSIZE20
typedefstruct{
intdata[MAXSIZE];
intlast;
}list;
/*编写函数,实现在顺序表中查找值为x的元素的位置的简单顺序查找算法,编写主函数验证此算法,并分析算法的时间复杂度*/
intlocate(list*l,intx)
{
//代码
inti;
for(i=0;i
if(l->data[i]==x)
returni+1;
return-1;
}
main()
{
listb;
intx,i,p;
=10;
for(i=0;i<;i++)
[i]=i+2;
printf("请输入x的值:
");
scanf("%d",&x);
p=locate(&b,x);
if(p==-1)
printf("no!
");
else
printf("position=%d\n",p);
}
时间复杂度T(n)=O(n);
2、#include<>
#defineMAXSIZE20
typedefstruct{
intdata[MAXSIZE];
intlast;
}list;
/*编写函数,实现在顺序表中删除第i个位置上的元素,编写主函数验证此算法,并分析算法的时间复杂度*/
intdelete(list*l,inti)
{
intj,k,p;//定义一个用来保存被删原素;
if(i>=0&&i
{
for(j=0;j
if(j==i-1)//匹配
{
p=l->data[j];//保存被删原素;
for(k=j;k
{
l->data[k]=l->data[k+1];
}
break;//退出循环
}
l->last=l->last-1;
returnp;//对于此题来说可以输出p;
}
return0;
}
main()
{
listb;
intx,i;
=10;
for(i=0;i<;i++)
[i]=i+2;
printf("请输入x的值:
");
scanf("%d",&x);
if(delete(&b,x)!
=0)
{
for(i=0;i<;i++)
printf("%3d",[i]);
}
else
printf("Error!
");
}
//时间复杂度T(n)=O(n);
3、#include<>
#defineMAXSIZE20
typedefstruct{
intdata[MAXSIZE];
intlast;
}list;
/*编写函数,实现在顺序表中第i个位置上插入值为x的元素,编写主函数验证此算法,并分析算法的时间复杂度*/
intinsert(list*l,intx,inti)
{
intj,k;
if(i<=l->last+1&&i>0)
{
if(i==l->last+1)//特殊值last+1要插入到整个数组之后
{
l->data[l->last]=x;
}
else
{
for(j=0;j
{
if(j==i-1)//匹配
{
for(k=l->last;k>j;k--)//将所选插入位置之后原素后移
{
l->data[k]=l->data[k-1];
}
l->data[j]=x;//把x赋值给所选位置
break;
}
}
}
l->last=l->last+1;//数值长度加一
return1;
}
return0;//无效位置
}
main()
{
listb;
intx,i;
=10;
for(i=0;i<;i++)
[i]=i+2;
printf("请输入x的值:
");
scanf("%d",&x);
if(insert(&b,66,x)!
=0)
{
for(i=0;i<;i++)
printf("%3d",[i]);
}
else
printf("Error!
");
}
//时间复杂度T(n)=O(n);
4、
#include<>
#defineMAXSIZE20
typedefstruct{
intdata[MAXSIZE];
intlast;
}list;
/*编写函数,实现在顺序表中将所有偶数排在所有奇数前面,编写主函数验证此算法,并分析算法的时间复杂度*/
voidfun(list*l)
{//这个代码有点晦涩,但空间时间复杂度是鸡儿低
inti,ou=0,temp;//i计数,ou代表偶数个数
for(i=0;i
{
if(l->data[i]%2==0)//判断是不是偶数,如果是偶数的话和当前第ou个位置的原素交换位置
{
temp=l->data[ou];
l->data[ou]=l->data[i];
l->data[i]=temp;
ou+=1;//偶数个数加一
}
}
printf("当前数组中偶数有%d个,奇数有%d个:
\n",ou,l->last-ou);
}
main()
{
listb;
inti=0,m=0;
=10;
printf("请输入数组元素的值:
\n");
for(i=0;i<;i++)
{
printf("[%d]=",i);
scanf("%d",&[i]);
}
fun(&b);
for(i=0;i<;i++)
printf("%3d",[i]);
}
//时间复杂度为T(n)=O(n);
四、实验报告要求
1、撰写实验报告;
2、对实验中出现的问题和结果进行总结。
实验二链表的实现和应用
一、实验目的
1、掌握链表的定义;
2、掌握链表的基本操作,如查找、插入、删除、排序等。
二、实验内容
1、单链表的创建
2、单链表的查找
3、单链表的排序
4、单链表的删除
5、链表的应用--约瑟夫环问题
三、实验提示
1、//创建单链表,要求:
结点个数为n个,每个节点数据域的值必须小于m。
编辑主函数验证之。
#include<>
#include<>
typedefstructaa
{intdata;
structaa*next;
}NODE;
NODE*Creatlink(intn,intm)
{
inti;
NODE*tou,*p;//tou头结点
tou=(NODE*)malloc(sizeof(NODE));//创建并初始化头结点
tou->next=NULL;
tou->data=n;
printf("请输入%d个小鱼%d的数,中间用空格隔开:
\n",n,m);
for(i=0;i { p=(NODE*)malloc(sizeof(NODE)); scanf("%d",&p->data); if(p->data>=m) { printf("输入的第%d个数据大于%d,GG\n",i+1,m); exit(0);//程序强制中断, } p->next=tou->next; tou->next=p; } returntou; } outlink(NODE*h) {NODE*p; p=h->next; printf("\n\nTHELIST: \n\nHEAD"); while(p) {printf("->%d",p->data); p=p->next; } printf("\n"); } main() {NODE*head; head=Creatlink(8,22); outlink(head); } 2、//查找值为ch的节点在链表中是否出现,如果存在,返回在链表中位序,如果不存在返回0 #include<> #include<> #defineN8 typedefstructlist {intdata; structlist*next; }SLIST; SLIST*creatlist(char*); voidoutlist(SLIST*); intfun(SLIST*h,charch) { inti; SLIST*p; p=h->next;//p赋值为寿元节点 for(i=0;i { if(p->data==ch) returni+1; p=p->next; } return0; } main() {SLIST*head;intk;charch; chara[N]={'m','p','g','a','w','x','r','d'}; head=creatlist(a); outlist(head); printf("Enteraletter: "); scanf("%c",&ch); k=fun(head,ch); if(k==0)printf("\nNotfound! \n"); elseprintf("Thesequencenumberis: %d\n",k); } SLIST*creatlist(char*a) { inti; SLIST*tou,*p; tou=(SLIST*)malloc(sizeof(SLIST));//创建并初始化头结点 tou->data=N; tou->next=NULL; for(i=0;i { p=(SLIST*)malloc(sizeof(SLIST)); p->data=a[i]; p->next=tou->next; tou->next=p; } returntou; } voidoutlist(SLIST*h) {SLIST*p; p=h->next; if(p==NULL)printf("\nThelistisNULL! \n"); else {printf("\nHead"); do {printf("->%c",p->data);p=p->next;} while(p! =NULL); printf("->End\n"); } } 3、//去偶操作,链表中各节点按数据域递增有序链接,函数fun的功能是,删除链表中数据域值相同的节点,使之只保留一个 #include<> #include<> #defineN8 typedefstructlist {intdata; structlist*next; }SLIST; voidfun(SLIST*h) { SLIST*p,*shanchu;//用于遍历的指针p,用于删除的指针shanchu p=h->next;/p为寿元节点 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;inti; h=p=(SLIST*)malloc(sizeof(SLIST)); for(i=0;i {q=(SLIST*)malloc(sizeof(SLIST)); q->data=a[i];p->next=q;p=q; } p->next=0; returnh; } voidoutlist(SLIST*h) {SLIST*p; p=h->next; if(p==NULL)printf("\nThelistisNULL! \n"); else {printf("\nHead"); do{printf("->%d",p->data);p=p->next;}while(p! =NULL); printf("->End\n"); } } main() {SLIST*head;inta[N]={1,2,2,3,4,4,4,5}; head=creatlist(a); printf("\nThelistbeforedeleting: \n");outlist(head); fun(head); printf("\nThelistafterdeleting: \n");outlist(head); } 4、//在main函数中多次调用fun函数,每调用一次fun函数,输出链表尾部节点中的数据,并释放该节点,使得链表缩短。 #include<> #include<> #defineN8 typedefstructlist {intdata; structlist*next; }SLIST; voidfun(SLIST*p) { SLIST*bianli,*shanchu;//遍历,删除 bianli=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;inti; h=p=(SLIST*)malloc(sizeof(SLIST)); for(i=0;i {q=(SLIST*)malloc(sizeof(SLIST)); q->data=a[i];p->next=q;p=q; } p->next=0; returnh; } voidoutlist(SLIST*h) {SLIST*p; p=h->next; if(p==NULL)printf("\nThelistisNULL! \n"); else {printf("\nHead"); do{printf("->%d",p->data);p=p->next;}while(p! =NULL); printf("->End\n"); } } main() {SLIST*head; inta[N]={11,12,15,18,19,22,25,29}; head=creatlist(a); printf("\nOutputfromhead: \n");outlist(head); printf("\nOutputfromtail: \n"); while(head->next! =NULL){ fun(head); printf("\n\n"); printf("\nOutputfromheadagain: \n");outlist(head); } } 5、实现约瑟夫环函数(选做) #include<> #include<> typedefstructlist {intdata; structlist*next; }SLIST; SLIST*creatlist(intm) { inti; SLIST*tou,*p,*wei;//头指针生成节点指针尾指针 tou=(SLIST*)malloc(sizeof(SLIST));//头节点 wei=tou; printf("请输入%d个数用空格隔开: \n",m); for(i=0;i { p=(SLIST*)malloc(sizeof(SLIST)); scanf("%d",&p->data); wei->next=p; wei=p; } wei->next=tou->next;//令最后一个原素指向首元结点成环 returntou; } voidoutlist(SLIST*h,intm,intc) { inti; SLIST*p,*shanchu;//用于遍历的指针p,用于删除的指针shanchu p=h->next;//p指向首元结点 while(p! =p->next)//当环中只剩下一个原素时结束 { for(i=1;i { p=p->next; } shanchu=p->next;//shanchu指向当前要剔除的节点 printf("%d",shanchu->data); p->next=shanchu->next;//将shanchu指针指向的节点出环 free(shanchu); p=p->next; } printf("%d",p->data);//输出最后的一个节点的内容 free(p); free(h); } main() {SLIST*head; intm,c; printf("请分别输入m和c的值: "); scanf("%d,%d",&m,&c); head=creatlist(m); outlist(head,m,c); } 四、实验报告要求 1、撰写实验报告; 2、对实验中出现的问题和结果进行总结。 实验三栈的实现和应用 一、实验目的 1、掌握栈的建立方法; 2、掌握栈的基本操作,如入栈、出栈、判断空栈等; 3、栈的应用。 二、实验内容 1、顺序栈的初始化 2、判断栈是否为空 3、顺序栈出栈 4、顺序栈入栈 5、栈的应用--汉诺塔 三、实验提示 1、栈的基本操作,按提示将函数补充完整 #include<> #include<> #defineSTACK_MAX100 typedefstruct{ inttop; intdata[STACK_MAX]; }stack; voidinit(stack*st)/*初始化顺序栈*/ { st->top=0; } intEmpty(stack*st)/*判断栈是否为空*/ { if(st->top==0) return0;//空0 else return1;//非空1 } intpop(stack*st)/*出栈*/ { returnst->data[--st->top]; } voidpush(stack*st,intdata)/*入栈*/ { st->data[st->top++]=data; } intmain(void) { stackst; init(&st); push(&st,5); push(&st,6); printf("%d",pop(&st)); return0; } 2、#include<> voidmain() { voidhanoi(intn,charone,chartwo,charthree); /*对hanoi函数的声明*/ intm; printf("inputthenumberofdiskes: "); scanf("%d",&m); printf("Thesteptomoveing%ddiskes: \n",m); hanoi(m,'A','B','C'); } voidhanoi(intn,charone,chartwo,charthree) /*定义hanoi函数,将n个盘从one座借助two座,移到three座*/ { statick=1;//定义静态变量k用来标明走了多少步 voidmove(charx,chary);//因为move函数定义在该函数的后边且之前咩有声明在此需要提前声明才能使用 if(n==1)//当第一个座上仅剩一个盘的时候将此盘移到第三个上 { printf("第%d步: ",k++);//输出是第多少步 move(one,three);//移动 } else { hanoi(n-1,one,three,two);//将前n-1个盘从第一个座移到二个座上,第三个座当桥
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 算法 试验 参考 指导书 样本