算法与数据结构实习.docx
- 文档编号:1910827
- 上传时间:2023-05-02
- 格式:DOCX
- 页数:25
- 大小:21.55KB
算法与数据结构实习.docx
《算法与数据结构实习.docx》由会员分享,可在线阅读,更多相关《算法与数据结构实习.docx(25页珍藏版)》请在冰点文库上搜索。
算法与数据结构实习
《算法与数据结构实习》
指
导
书
(黄海学院09级用)
编写:
唐仕喜
2010年8月28日
教学目的:
通过该实习课程的实践教学,使学生强化《C语言程序设计》课程的知识,并着重培养以下几方面的能力:
C语言程序的编写和调试能力;
根据算法,进行结构化程序设计的能力;
对一些典型的基本应用问题,进行算法设计的能力。
教学要求:
根据大纲要求,完成教材习题部分布置的实习题。
学生应在每个实习前准备好源程序草稿;对必做题要求提交实验报告,实验报告应该给出算法主要部分的源程序;并且提交调试正确的完整程序文件以收集备案。
(选做题不要求提交实验报告)
教学方式:
实习课主要形式是上机实践,根据教学进度完成相应的实习题,教师随实习课进行指导。
考核方式:
该实习课程的考核为考查,成绩为等级制,评分依据实验报告、实习题的源程序。
实验一抽象数据类型的定义与使用
一、实验目的
1、掌握使用TurboC2.0上机处理抽象数据类型的基本方法;
2、掌握抽象数据类型的定义与使用,能结合实例加以理解。
二、实验要求
1、认真设计抽象数据类型,
2、认真思考设计算法。
三、注意事项:
在磁盘上创建一个目录,专门用于存储数据结构实验的程序。
四、实验内容
1.设计实现抽象数据类型“有理数”,基本操作包括有理数的加法、减法、乘法和除法,以及求有理数的分子、分母。
提示:
有理数看作一个对象,而有理数是有限小数或无限循环小数,其一般形式可以看作由分子和分母两个数据项组成,因此可以用类似于表示复数的方法类表示它----即用一个结构体;对于有理数的加法和减法、还要注意通分。
类推:
由此,我们还可以处理类似的对象,例如,日期、时间等对象,具有类似的特性,其操作也具有各自的特点。
同学们可以自行实现它们。
实验二顺序表的操作
一、实验目的
1、掌握使用TurboC2.0上机处理顺序表的基本方法;
2、掌握顺序表的基本操作:
插入、删除、查找以及线性表合并等运算在顺序存储结构和链接存储结构上的运算。
二、实验要求
1、认真阅读和掌握本实验的程序。
2、上机运行本程序。
3、保存和打印出程序的运行结果,并结合程序进行分析。
4、按照你对顺序表的操作需要,重新改写主程序并运行,打印出文件清单和运行结果
三、实验内容
程序1:
顺序表基本操作的实现
这个程序中演示了顺序表的创建、插入、删除和查找,请修改并完成。
程序如下:
#include
#include
/*顺序表的定义:
*/
#defineListSize100
typedefstruct
{intdata[ListSize];/*向量data用于存放表结点*/
intlength;/*当前的表长度*/
}SeqList;
voidmain()
{voidCreateList(SeqList*L,intn);
voidPrintList(SeqList*L,intn);
intLocateList(SeqList*L,intx);
voidInsertList(SeqList*L,intx,inti);
voidDeleteList(SeqList*L,inti);
SeqListL;
inti,x;
intn=10;/*THELENGTHOFLIST*/
L.length=0;
clrscr();
CreateList(&L,n);/*CREATTHELIST*/
PrintList(&L,n);/*PRINTTHELIST*/
printf("INPUTTHERESEARCHELEMENT");
scanf("%d",&x);
i=LocateList(&L,x);
printf("theresearchpositionis%d\n",i);/*顺序表查找*/
printf("inputthepositionofinsert:
\n");
scanf("%d",&i);
printf("inputthevalueofinsert\n");
scanf("%d",&x);
InsertList(&L,x,i);/*顺序表插入*/
PrintList(&L,n);/*打印顺序表*/
printf("inputthepositionofdelete\n");
scanf("%d",&i);
DeleteList(&L,i);/*顺序表删除*/
PrintList(&L,n);
getch();/*打印顺序表*/
}
/*顺序表的建立:
*/
voidCreateList(SeqList*L,intn)
{inti;
printf("pleaseinputnnumbers\n");
for(i=1;i<=n;i++)
{scanf("%d",&L->data[i]);
}
L->length=n;
}
/*顺序表的打印:
*/
voidPrintList(SeqList*L,intn)
{inti;
printf("thesqlistis\n");
for(i=1;i<=n;i++)
printf("%d",L->data[i]);
}
/*顺序表的查找:
*/
intLocateList(SeqList*L,intx)
{
请完成代码
}
/*顺序表的插入:
*/
voidInsertList(SeqList*L,intx,inti)
{
请完成代码
}
/*顺序表的删除:
*/
voidDeleteList(SeqList*L,inti)
{
请完成代码
}
实验三单链表操作
一、实验目的
1.掌握握单链表的基本操作:
插入、删除、查找等运算。
二、实验要求
1.认真阅读和掌握本实验的程序。
2.上机运行本程序。
3.保存和打印出程序的运行结果,并结合程序进行分析。
4.按照你对单链表的操作需要,重新改写主程序并运行,打印出文件清单和运行结果
三、实验内容
程序1:
单链表基本操作的实现
这个程序中演示了单链表的创建、插入、删除和查找。
程序如下:
#include
typedefstructnode{
intdata;
structnode*next;
}NODE;
/******************************************/
NODE*Create(){
NODE*p,*head;
intx;
head=(NODE*)malloc(sizeof(NODE));
head->next=NULL;
printf("Inputdata,-1toEnd!
\n");
scanf("%d",&x);
while(x!
=-1){
p=(NODE*)malloc(sizeof(NODE));
p->data=x;
p->next=head->next;
head->next=p;
scanf("%d",&x);
}
return(head);
}
/******************************************/
voidOutput(NODE*head){
NODE*p;
p=head;
printf("BegintodumptheLinkList...\n");
while(p->next!
=NULL){
printf("->%d",p->next->data);
p=p->next;
}
printf("\nTheLinkListended!
\n");
}
/******************************************/
intListlen(NODE*head){
inti=0;
NODE*p=head;
while(p->next!
=NULL){
i++;
p=p->next;
}
return(i);
}
/******************************************/
intGet(NODE*head,inti){
请完成代码
}
/******************************************/
voidDel(NODE*head,inti){
请完成代码
}
/******************************************/
voidIns(NODE*head,inti,inte){
NODE*p=head,*q;
intj=0;
while(p->next&&j 请完成代码 } } /******************************************/ main(){ NODE*head; intlength; inti,element; clrscr(); head=Create(); Output(head); length=Listlen(head); printf("thelengthofthelinkis%d\n",length); printf("inputtheorder: \n"); scanf("%d",&i); element=Get(head,i); printf("theelementoftheorderis%d\n",element); printf("inputthedelposition\n"); scanf("%d",&i); Del(head,i); Output(head); printf("Inputtheinsertposionandelement: \n"); scanf("%d%d",&i,&element); Ins(head,i,element); Output(head); getch(); }_ } 实验四栈的基本操作 一、实验目的 掌握栈的基本操作: 初始化栈、判栈为空、出栈、入栈等运算。 二、实验要求 1.认真阅读和掌握本实验的算法。 2.上机将本算法实现。 3.保存和打印出程序的运行结果,并结合程序进行分析。 三、实验内容 利用栈的基本操作实现将任意一个十进制整数转化为R进制整数 算法为: 1、定义栈的顺序存取结构 2、分别定义栈的基本操作(初始化栈、判栈为空、出栈、入栈等) 3、定义一个函数用来实现上面问题: 十进制整数X和R作为形参 初始化栈 只要X不为0重复做下列动作 将X%R入栈 X=X/R 只要栈不为空重复做下列动作 栈顶出栈 输出栈顶元素 参考程序: #defineMAXSIZE100 #include structstack{ intdata[MAXSIZE]; inttop; }; voidinit(structstack*s){ s->top=-1; } intempty(structstack*s){ if(s->top==-1) return1; else return0; } voidpush(structstack*s,inti){ if(s->top==MAXSIZE-1){ printf("Stackisfull\n"); return; } 请完成代码 } intpop(structstack*s){ if(empty(s)){ printf("stackisempty"); return-1; } 请完成代码 } voidtrans(intnum){ structstacks; intk; init(&s); while(num){ k=num%16; push(&s,k); num=num/16; } while(! empty(&s)){ k=pop(&s); if(k<10) printf("%d",k); else printf("%c",k+55); } printf("\n"); } main(){ intnum; clrscr(); printf("Inputanum,-1toquit: \n"); scanf("%d",&num); while(num! =-1){ trans(num); scanf("%d",&num); } } 实验五队列的基本操作 一、实验目的 掌握队列的基本操作: 初始化队列、判队列为空、出队列、入队列等运算。 二、实验要求 1.认真阅读和掌握本实验的算法。 2.上机将本算法实现。 3.保存和打印出程序的运行结果,并结合程序进行分析。 三、实验内容 利用队列的基本操作实现杨辉三角的输出 算法如下: voidout_number(intn); {init_queue(Q); printf (1); en_queue(Q,s1+s2); for(I=2;I<=n;I++) {s1=0;for(j=1;j<=I-1;j++) {s2=out_queue(Q); printf(s2); en_queue(q,s1+s2); s1=s2; } printf (1); en_queue(Q,1+s2); } 参考程序如下 typedefstruct {int*data; intfront; intrear; } sqqueue; main() { inti,j,m,s1=0,s2=1; sqqueueq; clrscr(); q.data=(int*)malloc(100*sizeof(int)); q.rear=q.front=0; q.data[q.rear]=s2; q.rear++; printf("%40d",s2); for(i=2;i<=8;i++) {s1=0; for(m=1;m<=40-i;m++) printf("%c",''); for(j=1;j<=i-1;j++) {s2=q.data[q.front]; q.front++; printf("%d",s2); q.data[q.rear]=s1+s2; q.rear++; s1=s2; } printf("%d\n",1); q.data[q.rear]=1+s2; q.rear++; } }_ 实验六数组的基本操作 一、实验目的 回顾c语言中数组的定义和基本应用 二、实验要求 1.认真阅读和掌握本实验的程序。 2.上机运行本程序。 3.保存和打印出程序的运行结果,并结合程序进行分析。 三、实验内容 有M个学生,学习N门课程,已知所有学生的各科成绩, 编程: 分别求每个学生的平均成绩和每门课程的平均成绩 参考程序: #defineM5 #defineN4 #include"stdio.h" main() {inti,j; staticfloatscore[M+1][N+1]={{78,85,83,65},{88,91,89,93},{72,65,54,75},{86,88,75,60},{69,60,50,72}}; for(i=0;i {for(j=0;j {score[i][N]+=score[i][j]; score[M][j]+=score[i][j]; } score[i][N]/=N; } for(j=0;j score[M][j]/=M; clrscr(); printf("学生编号课程1课程2课程3课程4个人平均\n"); for(i=0;i {printf("学生%d\t",i+1); for(j=0;j printf("%6.1f\t",score[i][j]); printf("\n"); } for(j=0;j<8*(N+2);j++) printf("-"); printf("\n课程平均"); for(j=0;j printf("%6.1f\t",score[M][j]); printf("\n"); getch(); } 实验七字符串处理 一、实验目的 1、理解字符串的基本概念,字符串的存贮 2、掌握字符串的基本操作。 二、实验要求 1.认真阅读和掌握本实验的算法。 2.上机将本算法实现。 3.保存和打印出程序的运行结果,并结合程序进行分析。 三、实验内容 定义字符串数组、实现字符串处理的基本操作 #include #defineMAXN100 typedefenum{fail,success}status; typedefenum{false,true}boolean; chars[MAXN],s1[MAXN],s2[MAXN]; voidscopy(chars1[],chars2[]) {inti=0; while(s2[i]! ='\0') {s1[i]=s2[i]; i++; } s1[i]='\0'; } intstrlen(chars[]) {inti; for(i=0;s[i]! ='\0';i++); return(i); } statusstrcat(chars1[],chars2[]) {inti,j,k; if((i=strlen(s1))+(j=strlen(s2))>=MAXN) return(fail); for(k=0;k<=j;k++) s1[i+k]=s2[k]; return(success); } statusstrins(chars1[],inti,chars2[]) {intm,n,k; if(i<0||i>(m=strlen(s1))||m+(n=strlen(s2))>MAXN) return(fail); 请完成代码 return(success); } statusstrsub(sl,i,j,s2) charsl[],s2[]; inti,j; {intm,k; if(i<0||i>=(m=strlen(sl))) return(fail); if(j<0||i+j>m) return(fail); 请完成代码 return(success); }……… voidmain() {inti; i=strlen("aassddd"); printf("%d\n",i); scopy(s1,"abcd"); scopy(s2,"hijkl"); printf("%s\n",s1); printf("%s\n",s2); strcat(s1,s2); printf("%s\n",s1); printf("%s\n",s2); strins(s1,4,s2); printf("%s\n",s1); printf("%s\n",s2); ………. } 实验八二叉树操作 一、实验目的 1.进一步掌握指针变量的含义。 2.掌握二叉树的结构特征,以及各种存储结构的特点及使用范围。 3.掌握用指针类型描述、访问和处理二叉树的运算。 二、实验要求 1.认真阅读和掌握本实验的程序。 2.上机运行本程序。 3.保存和打印出程序的运行结果,并结合程序进行分析。 4.按照你二叉树的操作需要,重新改写主程序并运行,打印出文件清单和运行结果 三、实验内容 程序1: 按先序次序输入二叉树中结点的值(一个字符),`0`表示空树,生成二叉树的二叉链表存储结构,a为指向根结点的指针。 然后按中序顺序遍历二叉树。 算法思想: 先访问左子树,再访问根结点,最后访问右子树 参考程序如下: #defineNULL0 typedefstructstu{ chardata; structstu*left,*right; }sn; sn*Create(sn*a) {charch; scanf("%c",&ch); if(ch=='')a=NULL; else{a=(sn*)malloc(sizeof(sn)); if(! a)printf("yuguyuy"); a->data=ch; a->left=Create(a->left); a->right=Create(a->right); } return(a); } voidinc(sn*b) {if(b){inc(b->left); printf("%c",b->data); inc(b->right);} } main() { sn*t,*q; q=NULL; t=Create(q); inc(t); printf("\n"); getch(); }实验数据: abc00de0g00f000(0表示空格) 实验九图的操作 一.实验目的 1.掌握图的基本存储方法。 2.掌握有关图的操作算法并用高级语言编程实现; 3.熟练掌握图的两种搜索路径的遍历方法。 二.实验要求 1.认真阅读和掌握本实验的算法。 2.上机将本算法实现。 3.保存和打印出程序的运行结果,并结合程序进行分析。 4.按照你对图的操作需要,重新改写主程序并运行,打印出文件清单和运行结果 三.实验内容 以邻接矩阵和邻接表的方式存储连通图。 然后分别用深度优先算法遍历邻接矩阵方式存储的图和邻接表方式存储的图。 算法如下: 深度优先遍历的递归算法 (1)深度优先遍历算法 intvisited[MaxVertexNum];//访问标志向量是全局量 voidDFSTraverse(ALGraph*G) {//深度优先遍历以邻接表表示的图G,而以邻接矩阵表示G时,算法完全与此相同 inti; for(i=0;i visited[i]=FALSE;//标志向量初始化 for(i=0;i if(! visited[i])//vi未访问过 DFS(G,i);//以v
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 数据结构 实习
![提示](https://static.bingdoc.com/images/bang_tan.gif)