数据结构与算法实验指导书.docx
- 文档编号:4288865
- 上传时间:2023-05-06
- 格式:DOCX
- 页数:23
- 大小:20.61KB
数据结构与算法实验指导书.docx
《数据结构与算法实验指导书.docx》由会员分享,可在线阅读,更多相关《数据结构与算法实验指导书.docx(23页珍藏版)》请在冰点文库上搜索。
数据结构与算法实验指导书
数据结构与算法
实验指导书
山东师范大学数学科学学院
实验大纲
序号
实验
名称
内容
提要
每组
人数
实验
时数
实验
要求
实验
类别
备注
1
抽象数据类型的实现
求圆的面积、周长等
1
3
必做
设计
2
线性表的基本操作
在线性表中插入、删除、查找结点
1
3
必做
设计
3
栈和队列及其应用
利用栈或队列解决实际问题
1
6
必做
设计
4
树和二叉树的建立及应用
二叉树的建立、插入、删除、周游
1
9
必做
设计
5
查找算法的实现
利用检索算法进行查找
1
6
必做
设计
6
内排序算法的实现
用某个排序算法进行排序
1
3
必做
设计
7
图的建立及应用
图的建立等
1
3
必做
设计
8
综合实验
学生管理、订票系统等
1
3
必做
综合
实验一:
抽象数据类型的实现
一、实验目的:
1、了解抽象数据类型的表示和实现方法
2、会用C语言中已存在的数据类型来说明新的结构。
3、能用已实现的操作来组合新的操作。
4、熟悉C语言的程序设计
二、实验内容
输入圆的半径,输出圆的面积和周长。
设计一个圆的抽象数据类型,并定义求圆的面积和周长的两个操作,输入数据是圆的半径r,圆的面积S=πr2,圆的周长L=2πr。
圆的类型定义:
structcircle{
floatr;
floatarea;
floatcirm;}
typedefstructcircle*Circle;
操作:
floatarea(Circlec)
求圆的面积
floatcircmn(Circlec)
求圆的周长
三、实验步骤
1、启动TC
2、输入下面程序:
structcircle{
floatr;
floatarea;
floatperimeter;};
typedefstructcircle*Circle;
floatarea(Circlec)
{
c->area=3.14*c->r*c->r;
returnc->area;
}
floatperimeter(Circlec)
{
c->perimeter=2*3.14*c->r;
returnc->perimeter;
}
main()
{structcirclec;
printf(“pleaseinputaradiustor”);
scanf(“%f”,&c.r);
printf(“theareas=%f\n”,area(&c));
printf(“theperimeter=%f\n”,perimeter(&c));
}
3、运行程序、查错。
实验二线性表的基本操作
一、实验目的:
1、掌握线性表的两种存储结构
2、掌握线性表在两种存储结构上建立、插入、删除、查找结点的基本操作
3、会利用线性表解决实际问题
二、实验内容
设有n个人围坐在一个圆桌周围,从第s个人开始报数,数到第m个人出列,然后从出列的下一个人重新开始报数,数到第m的人又出列。
。
。
。
。
如此反复直到所有的人全部出列为止。
三、实验步骤
1、启动TC
2、输入下面程序
/*josephus_clist.c*/
/*Josephus问题:
循环链接表实现*/
#include
#include
#defineFALSE0
#defineTRUE1
typedefintDataType;/*定义元素类型为整型,也可定义为其他类型*/
structNode;/*单链表结点类型*/
typedefstructNode*PNode;/结点指针类型*/
structNode/*单链表结点结构*/
{DataTypeinfo;
PNodelink;
};
typedefstructNode*LinkList;
typedefLinkList*PLinkList;
intinit_clist(PLinkListpclist,intn)
/*用1,2,……,n为*pclist所示的循环表初始化*/
{PNodep,q;
inti;
q=(PNode)malloc(sizeof(structNode));
if(q==NULL)return(FALSE);
*pclist=q;
q->info=1;
q->link=q;
if(n==1)return(TRUE);
for(i=2;i {p=(PNode)malloc(sizeof(structNode)); if(p==NULL)return(FALSE); p->info=i; p->link=q->link; q->link=p; q=p; } return(TRUE); } voidjosephus_clist(PLinkListpclist,ints,intm) {PNodep,pre; inti; p=*pclist; /*找第s个元素*/ if(s==1) {pre=p; p=p->link; while(p! =*pclist) { pre=p; p=p->link; } } elsefor(i=1;i { pre=p; p=p->link; } while(p! =p->link)/*当链表中结点个数大于1时*/ {for(i=1;i {pre=p; p=p->link; } printf(“outelement: %d\n”,p->info);/*输出该结点*/ if(*pclist==p)/*该结点是第一个结点时,删除时需特殊处理一下*/ *pclist=p->link; pre->link=p->link;/*删除该结点*/ free(p); p=pre->link; } printf(“outelement: %d\n”,p->info);/*输出最后一个结点*/ *pclist=NULL; free(p); } main() {LinkListjos_clist; intn,s,m; /*输入所需各参数的值*/ do{ printf(“\npleaseinputthevaluesofn=“); scanf(“%d”,&n); }while(n<1); do{ printf(“pleaseinputthevaluesofs=“); scanf(“%d”,&s); }while(s<1); do{ printf(“pleaseinputthevaluesofm=“); scanf(“%d”,&m); }while(m<1); if(init_clist(&jos_clist,n)) josephus_clist(&jos_clist,s,m); else printf(“Outofspace! \n”); } 3、编译、链接、运行、查错。 实验三栈和队列及其应用 一、实验目的 1、掌握栈和队列的存储结构及在两种存储结构上的基本操作 2、会利用栈和队列解决实际问题 二、实验内容 Fibonacci数列1,1,2,3,5,8,13,21, 输入n的值,输出前n个元素的值 三、实验步骤 1、启动TC2.0 2、输入下面程序 #include structSeqStack { intMAXNUM; intt; int*s; }; typedefstructSeqStack*PSeqStack; PSeqStackcreatEmptyStack_seq(intm) { PSeqStackpastack=(PSeqStack)malloc(sizeof(structSeqStack)); if(pastack! =NULL){ pastack->s=(int*)malloc(sizeof(int)*m); if(pastack->s){ pastack->MAXNUM=m; pastack->t=-1; return(pastack); } elsefree(pastack); } printf("Outofspace! ! \n"); returnNULL; } voidpush_seq(PSeqStackpastack,intx) /*在栈中压入一元素x*/ {if(pastack->t>=pastack->MAXNUM-1) printf("Overflow! \n"); else {pastack->t=pastack->t+1; pastack->s[pastack->t]=x; } } voidpop_seq(PSeqStackpastack) /*删除栈顶元素*/ {if(pastack->t==-1) printf("Underflow! \n"); else pastack->t=pastack->t-1; } inttop_seq(PSeqStackpastack) /*当pastack所指的栈不为空栈时,求栈顶元素的值*/ {if(pastack->t==-1) printf("Itisempty! \n"); else return(pastack->s[pastack->t]); } main() {inti,n,a,temp; PSeqStackpst; scanf("%d",&n); pst=creatEmptyStack_seq(n); push_seq(pst,1); push_seq(pst,1); printf("%d,%d,",1,1); i=1; while(i<=n){ temp=top_seq(pst); pop_seq(pst); a=top_seq(pst); pop_seq(pst); a+=temp; push_seq(pst,temp); push_seq(pst,a); printf("%d,",a); i++; } }_ 3、运行程序 实验四树和二叉树的建立及应用 一、实验目的: 1、掌握树特别是二叉树的建立、插入、删除、周游等算法 2、掌握二叉树的存储方法 3、会利用树结构解决实际问题 二、实验内容 计算一棵二叉树的叶结点数。 用链表存储一棵二叉树,对每个结点判断是否是叶结点,用变量m记录叶结点的个数。 输入一棵二叉树,输出该二叉树的叶结点个数。 三、实验步骤 1、启动TC2.0 2、输入下面程序 #include intm=0; typedefintDataType; structBinTreeNode; typedefstructBinTreeNode*PBinTreeNode; typedefstructBinTreeNode*PBinTree; structBinTreeNode {DataTypeinfo; PBinTreeNodellink; PBinTreeNoderlink; }; PBinTreeCreateBinTree(void) {PBinTreebt; DataTypex; scanf("%d",&x); if(x==-1)bt=NULL; else {bt=(PBinTreeNode)malloc(sizeof(structBinTreeNode)); bt->info=x; bt->llink=CreateBinTree(); bt->rlink=CreateBinTree(); } returnbt; } intcountleaf(PBinTreebt) { if(bt==NULL)return0; if(bt->llink==NULL&&bt->rlink==NULL) m++; countleaf(bt->llink); countleaf(bt->rlink); } main() { PBinTreebt; bt=CreateBinTree(); countleaf(bt); printf("thecountofleafis%d\n",m); } 3、调试程序、运行程序。 4、输入数据: 124–1–1–1357–1–18–1–16–1–1 输出数据: thecountofleafis4 实验五查找算法的实现 一、实验目的: 1、掌握字典的存储结构 2、掌握字典的检索算法 3、会利用字典结构解决实际问题 二、实验内容 根据学生的学号,查找某个学生的信息 三、实验步骤 1、启动TC2。 0 2、输入下面程序 #include typedefstruct {intnum; charname[10]; charsex; floatscore; }DicElement; typedefstruct {intm; DicElement*element; }HashDictionary; inth(intkey) {returnkey%13;} HashDictionary*createEmptyDictionary(intm) {inti; HashDictionary*phd=(HashDictionary*)malloc(sizeof(HashDictionary)); if(phd! =NULL){ phd->element=(DicElement*)malloc(sizeof(DicElement)*m); if(phd->element){ phd->m=m; for(i=0;i phd->element[i].num=0;/*初始化*/ return(phd); } elsefree(phd); } printf("Outofspace! ! \n");/*存储分配失败*/ returnNULL; } intlinearInsert(HashDictionary*phash,DicElementele){ intposition; if(linearSearch(phash,ele.num,&position)==1) /*散列表中已有关键码为key的结点*/ printf("Find\n"); elseif(position! =-1) phash->element[position]=ele;/*插入结点*/ elsereturn(0);/*散列表溢出*/ return (1); } intlinearSearch(HashDictionary*phash,intnum,int*position) {intd,inc; d=h(num);/*d为散列地址,散列函数为h(key)*/ for(inc=0;inc {if(phash->element[d].num==num) {*position=d;/*检索成功*/ return (1);} else if(phash->element[d].num==0) {*position=d;/*检索失败,找到插入位置*/ return(0);} d=(d+1)%phash->m;} *position=-1;/*散列表溢出*/ return(0);} main() {HashDictionary*phd; intm,i,num,p; DicElementelem; phd=createEmptyDictionary(100); printf("inputthenumberofstudent"); scanf("%d",&m); for(i=1;i<=m;i++) {printf("num,name,sexandscore"); scanf("%d",&elem.num); scanf("%s",elem.name); fflush(stdin); scanf("%c",&elem.sex); scanf("%f",&elem.score); linearInsert(phd,elem); } printf("inputthenumtosearch"); scanf("%d",&num); linearSearch(phd,num,&p); printf("%d,%s,%c,%f\n",phd->element[p].num,phd->element[p].name,phd->element[p].sex,phd->element[p].score); } 3、运行程序 实验六内排序算法的实现 一、实验目的: 1、理解排序的基本概念 2、掌握几种排序的方法 3、会比较不同排序方法的优劣 二、实验内容 试通过随机数据比较各算法的关键字移动次数和所用时间。 1、启动TC2.0 2、输入下面程序 #include #include #include typedefintKeyType; typedefintDataType; typedefstruct{ KeyTypekey; DataTypeinfo; }RecordNode; typedefstruct{ intn; RecordNode*record; }SortObject; voidselectSort(SortObject*pvector) {/*按递增序进行直接选择排序*/ inti,j,k,m=0; RecordNodetemp; floatt; t=clock(); for(i=0;i {/*做n-1趟选择排序*/ k=i; for(j=i+1;j if(pvector->record[j].key k=j; if(k! =i) {/*记录Rk与Ri互换*/ temp=pvector->record[i]; pvector->record[i]=pvector->record[k]; pvector->record[k]=temp; m++; } } printf("\nthenumberofmoveis%d\n",m); printf("thetimeofsortis%fs\n",(clock()-t)/CLK_TCK); } main() {inti; SortObjecta; randomize(); printf("inputanumber"); scanf("%d",&a.n); a.record=(RecordNode*)malloc(sizeof(RecordNode)*a.n); for(i=0;i {a.record[i].key=random(1000); printf("%d",a.record[i].key); } selectSort(&a); for(i=0;i printf("%d",a.record[i].key); } 3、运行 实验七图的建立及应用 一、实验目的: 1、掌握图的存储结构 2、掌握图的基本操作 3、会利用图结构解决实际问题 二、实验内容 若要在n个城市之间建设通信网络,只需要架设n-1条线路即可。 如何用最低的经济代价建设这个通信网。 三、实验步骤 1、启动TC2。 0 2、输入下面程序 #include #defineMAXNUM32767 typedefcharVexType; typedefintAdjType; typedefstruct{ intn;/*图的顶点个数*/ VexType*vexs;/*顶点信息*/ AdjType**arcs;/*边信息*/ }GraphMatrix; typedefstruct{ intstart_vex,stop_vex;/*边的起点和终点*/ AdjTypeweight;/*边的权*/ }Edge; /*Prim算法*/ voidprim(GraphMatrix*pgraph,Edge*mst) {inti,j,min,vx,vy; floatweight,minweight; Edgeedge; for(i=0;i {mst[i].start_vex=0; mst[i].stop_vex=i+1; mst[i].weight=pgraph->arcs[0][i+1]; } for(i=0;i {/*共选n-1条边*/ minweight=MAXNUM; min=i; for(j=i;j /*从所有边(vx,vy)(vx∈U,vy∈V-U)中选出最短的边*/ if(mst[j].weight {minweight=mst[j].weight; min=j;} /*mst[min]是最短的边(vx,vy)(vx∈U,vy
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 算法 实验 指导书
![提示](https://static.bingdoc.com/images/bang_tan.gif)