数据结构实验报告.docx
- 文档编号:1198933
- 上传时间:2023-04-30
- 格式:DOCX
- 页数:51
- 大小:44.41KB
数据结构实验报告.docx
《数据结构实验报告.docx》由会员分享,可在线阅读,更多相关《数据结构实验报告.docx(51页珍藏版)》请在冰点文库上搜索。
数据结构实验报告
本科生实验报告
实验课程数据结构(C语言版)
学院名称成都理工大学
专业名称测控技术与仪器
学生姓名
学生学号
指导教师
实验地点
实验成绩
二〇一五年五月二〇一五年七月
实验一:
成绩的顺序表实现
(1)问题描述
建立自己的成绩表,利用顺序表及链表两种方式实现,要求实现的基本操作有:
插入新成绩,删除成绩,寻找指定科目成绩及输出功能。
(2)数据结构设计
a.逻辑结构设计
以链表形式存储,链表头存姓名、学号,用结构体No1实现,其指针指向存科目、成绩的结构体No2,而No2指向No2类型,以实现多科目存储。
b.物理逻辑设计
链式存储方式
(3)算法设计
a.算法列表
序号
名称
函数表示符
操作说明
1
create
create(Sqlist*m,intn)
创建成绩表
2
insert
insert(NAME1*head,intn,charz[10],doublegra)
插入成绩
3
del
del(NAME1*head,charsm[10])
删除成绩
4
dislayelement
dislayelement(NAME1*head,chars[10])
查询成绩
b.算法描述
本算法中建立了一个数组结构体,结构体中包括课程的成绩和课程的名称。
创建成绩时,依次输入n科课程的成绩和名称,并存储在数组结构体中;插入成绩是增加一个存储空间,存储新插入的成绩;删除成绩是先找到该科目的位置,然后将该位置其后的元素都向前移一位,删除该元素,即删除该科目及成绩;查询成绩是找到该科目的位置,并将它的成绩和名称输出来。
(4)源程序清单
#include
#include
#include
typedefstructstudent
{
charname[10];
charnum[10];
structscore*next;
}NAME1;
typedefstructscore
{
charsub[10];
doublegrade;
structscore*next;
}NAME2;
NAME1*creat1()
{
NAME1*head1;
NAME2*head2,*p,*s;
chargra[10],k[3];
intkey=1,n,i;
head1=(NAME1*)malloc(sizeof(NAME1));
printf("\n输入姓名:
");
gets(head1->name);
printf("\n输入学号:
");
gets(head1->num);
head2=(NAME2*)malloc(sizeof(NAME2));
p=head2;
while(key)
{
printf("\n需要创建节点输入1,否则输入0:
");
gets(k);
n=atoi(k);
if(n!
=0)
{
s=(NAME2*)malloc(sizeof(NAME2));
printf("\n输入科目:
");
gets(gra);
i=0;
while(gra[i]!
=NULL)
{
s->sub[i]=gra[i];
i++;
}
s->sub[i]=NULL;
printf("\n输入成绩:
");
gets(gra);
s->grade=atof(gra);
p->next=s;
p=s;
}
elsekey=0;
}
head2=head2->next;
p->next=NULL;
head1->next=head2;
returnhead1;
}
voiddisplay(NAME1*head)
{
NAME1*p1;
NAME2*p2;
inti=0;
p1=head;
printf("\n%s%s\n",p1->name,p1->num);
p2=head->next;
do{
for(i=0;p2->sub[i]!
=NULL;)
{
printf("%c",p2->sub[i]);
i++;
}
printf("%lf",p2->grade);
printf("");
p2=p2->next;
}while(p2!
=NULL);
}
voidinsert(NAME1*head,intn,charz[10],doublegra)
{
NAME2*s,*p;
inti;
s=(NAME2*)malloc(sizeof(NAME2));
s->grade=gra;
strcpy(s->sub,z);
if(n==1)
{s->next=head->next;
head->next=s;
}
else
{
p=head->next;
for(i=2;i p=p->next; if(p->next==NULL) { p->next=s; s->next=NULL; } else { s->next=p->next; p->next=s; } } } voiddislayelement(NAME1*head,chars[10]) { NAME1*p1; NAME2*p2; p1=head; p2=p1->next; while(p2! =NULL) { if(strcmp(p2->sub,s)==0) { puts(p2->sub); printf("%f",p2->grade); p2=p2->next; } else p2=p2->next; } } voiddel(NAME1*head,charsm[10]) { NAME2*p,*t; p=(NAME2*)malloc(sizeof(NAME2)); t=(NAME2*)malloc(sizeof(NAME2)); t=head->next; if(strcmp(t->sub,sm)==0) head->next=t->next; else { p=t; t=t->next; while(t->next! =NULL) { if(strcmp(t->sub,sm)==0) { p->next=t->next; t=NULL; break; } else { p=p->next; t=t->next; } } if(t! =NULL&&strcmp(t->sub,sm)==0) p->next=NULL; } } intmain(void) { intt; doublegrade; charsub[10]; NAME1*head1; head1=creat1();//输入功能 display(head1);//输出功能 printf("\n"); printf("输入插入位置\nt="); scanf("%d",&t); if(t! =0) { printf("输入插入的科目: "); scanf("%s",sub); printf("输入插入的成绩: "); scanf("%lf",&grade); insert(head1,t,sub,grade); //插入功能 } display(head1);//输出功能 printf("\n"); printf("输入删除的科目: "); scanf("%s",sub); del(head1,sub); //删除功能 display(head1);//输出功能 printf("\n"); printf("输入输出的科目名: "); scanf("%s",sub); dislayelement(head1,sub); //输出特定科目功能 display(head1); return0; } (5)调试记录 输入姓名: ma 输入学号: 2 需要创建节点输入1,否则输入0: 1 输入科目: a 输入成绩: 45 需要创建节点输入1,否则输入0: 1 输入科目: b 输入成绩: 46 需要创建节点输入1,否则输入0: 1 输入科目: c 输入成绩: 56 需要创建节点输入1,否则输入0: 0 ma2 a45.000000b46.000000c56.000000 输入插入位置 t=1 输入插入的科目: d 输入插入的成绩: 54 ma2 d54.000000a45.000000b46.000000c56.000000 输入删除的科目: c ma2 d54.000000a45.000000b46.000000 输入输出的科目名: a a 45.000000 ma2 d54.000000a45.000000b46.000000Pressanykeytocontinue (6)运行说明 运行程序时根据弹出的提示分别执行不同的功能,插入,删除,查询。 实验二: 括号匹配 (1)问题描述 以文件的形式输入一串字符和括号,判断括号是否匹配,并以特殊符号标识出不匹配的括号。 (2)数据结构设计 a.逻辑结构设计 线性结构(栈) b.物理逻辑设计 顺序存储方式(数组) (3)算法设计 a.算法列表 序号 名称 函数表示符 操作说明 1 initstack initstack(D*S) 创建一个空栈 2 gettop gettop(D*S) 取栈顶元素 3 push push(D*S,chare) 入栈 4 pop pop(D*S) 出栈 5 judge judge(D*S) 判断栈是否为空 b.算法描述 用栈的方式实现括号匹配,当遇到左括号时,将左括号入栈,当遇到右括号时,先取栈顶元素看是否与右括号匹配,如果匹配就让栈顶元素出栈,如果不匹配就输出这是第几个括号来标识错误。 (4)源程序清单 #include #include #include #include typedefcharSElemType; #defineSIZE100 #defineSTACKINCREMENT20 typedefcharSElemType; typedefintsize; typedefstruct { SElemType*base; SElemType*top; intsize; }D; initstack(D*S) { S->base=(SElemType*)malloc(SIZE*sizeof(SElemType)); S->top=S->base; S->size=SIZE; returnNULL; } chargettop(D*S) { chare; e=*(S->top-1); returne; } voidpush(D*S,chare) { if(! (S->top-S->base>=S->size)) S->size=S->size+20; *S->top=e; S->top++; } voidpop(D*S) { S->top--; } intjudge(D*S) { if(S->base==S->top) return0; else return1; } intmain(void) { chara[50],*p,q,m; Ds; intt=1,i=0,n,b; FILE*in,*out;//********************* initstack(&s); in=fopen("f1.txt","r"); if(in==NULL) { printf("f1cannotbeopen\n"); exit(0); } out=fopen("f2.txt","w"); if(out==NULL) { printf("f2cannotbeopen\n"); exit(0); } while(! feof(in)) { a[i]=fgetc(in); printf("%c",a[i]); i++; } printf("i=%d: ",i-1); n=i-1;// p=a;//*******p指针指向数组a的首地址 for(i=0;i { q=a[i]; if((q=='(')||(q=='{')||(q=='[')) push(&s,q); elseif(q==')') { printf("\nq=%c",q); m=gettop(&s); printf("m=%c",m); if(m=='(') pop(&s); else t=0; b=i; } elseif(q==']') { printf("\nq=%c",q); m=gettop(&s); printf("m=%c",m); if(m=='[') pop(&s); else t=0; b=i; } elseif(q=='}') { printf("\nq=%c",q); m=gettop(&s); printf("m=%c",m); if(m=='{') pop(&s); else t=0; b=i; } }//**************************************************** if(t==0) printf("\nThe%diswrong.",b+1); if(t==0) printf("\n匹配错误.\n"); elseif(judge(&s)==0) printf("\nRight.\n"); else printf("\nWrong.\n");//*************************** if(t==1) { for(i=0;i fputc(a[i],out); } else { for(i=0;i fputc(a[i],out); for(i=b;i { if(a[i]=='('||a[i]==')'||a[i]=='['||a[i]==']'||a[i]=='{'||a[i]=='}') { fputc('_',out); fputc(a[i],out); } else fputc(a[i],out); } } printf("\n"); fclose(in); fclose(out); return(0); } (5)调试记录 ({{[}]})i=8: q=}m=[ The5iswrong. 匹配错误. Pressanykeytocontinue (6)运行说明 先建一个文本文档,输入一串括号和字符,然后将文件的位置在程序的fopen中来进行修改,运行程序后,如果括号匹配,则会输出“括号匹配”,如果括号不匹配则会输出“匹配错误”。 实验三: 树操作 (1)问题描述 利用链表建立一棵族谱二叉树,要求树的深度不小于3,先序遍历树,依次输出遍历结点,最后输出树深度及所有叶子结点。 (2)数据结构设计 a.逻辑结构设计 非线性结构(树状结构) b.物理逻辑设计 链式存储方式 (3)算法设计 a.算法列表 序号 名称 函数表示符 操作说明 1 *creat T*creat() 创建一棵二叉树 2 preOrder voidpreOrder(T*s) 先序遍历二叉树 3 deep intdeep(T*s) 求树的深度 4 printleaf voidprintleaf(T*s) 输出所有叶子节点 b.算法描述 首先建立一个结构体存储了结点的数据和左右指针,分别指向左孩子和右孩子。 创建二叉树中,用到的是先序输入,输入n个元素和n+1个空,即根据左根右的顺序输入到二叉树中;先序遍历的过程中,若结点数据不为空则把数据元素递归地按先序输出来;树的深度也用到了递归,由根节点出发,从左右子树搜寻,每一次h++,最后输出的深度为子树中最大的深度加根节点即h+1;输出叶子结点是判断它的左右子树是否为空,若不为空,则接着查找判断,若为空,则把叶子结点输出来。 (4)源程序清单 #include #include #defineN5 typedefstructbitree { chardata[N]; structbitree*left; structbitree*right; }T; T*creat() { T*s; charc[2],d[2]; inta,b; s=(T*)malloc(sizeof(T)); printf("\nEnterdata: "); gets(s->data); printf("\n如果'%s'有左子树? 输入1,否则输入0.",s->data); gets(c); a=atoi(c); if(a==0) s->left=NULL; else s->left=creat(); printf("\n如果'%s'有右子树? 输入1,否则输入0.",s->data); gets(d); b=atoi(d); if(b==0) s->right=NULL; else s->right=creat(); returns; }//*************创建 voidpreOrder(T*s) { if(s! =NULL) { printf("%s",s->data); if(s->left! =NULL) preOrder(s->left); if(s->right! =NULL) preOrder(s->right); } }//************先序输出 voidprintleaf(T*s) { if(s! =NULL) { if(s->left! =NULL) printleaf(s->left); if(s->right! =NULL) printleaf(s->right); if(s->left==NULL&&s->right==NULL) printf("%4s",s->data); } }//************输出叶子节点 intdeep(T*s) { inti,j; if(s->left! =NULL) i=deep(s->left); else i=0; if(s->right! =NULL) j=deep(s->right); else j=0; return(i>j? i: j)+1; }//输出树的深度 intmain(void) { T*head; intm; head=creat();//********** printf("\n"); preOrder(head); printf("\n"); printleaf(head); printf("\n"); m=deep(head); printf("\nThedepthis: "); printf("%2d",m); printf("\n"); return(0); } (5)调试记录 。 Enterdata: a 如果'a'有左子树? 输入1,否则输入0.1 Enterdata: b 如果'b'有左子树? 输入1,否则输入0.1 Enterdata: c 如果'c'有左子树? 输入1,否则输入0.0 如果'c'有右子树? 输入1,否则输入0.0 如果'b'有右子树? 输入1,否则输入0.1 Enterdata: d 如果'd'有左子树? 输入1,否则输入0.1 Enterdata: e 如果'e'有左子树? 输入1,否则输入0.0 如果'e'有右子树? 输入1,否则输入0.1 Enterdata: g 如果'g'有左子树? 输入1,否则输入0.0 如果'g'有右子树? 输入1,否则输入0.0 如果'd'有右子树? 输入1,否则输入0.1 Enterdata: f 如果'f'有左子树? 输入1,否则输入0.0 如果'f'有右子树? 输入1,否则输入0.0 如果'a'有右子树? 输入1,否则输入0.0 abcdegf cgf Thedepthis: 5 Pressanykeytocontinue (6)运行说明 创建一棵二叉树时,用到的是先序输入,当输入第一个字符时,判断它是否有左子树,若有的话,输入“1”,然后输入,再次判断;则输入“0”,判断是否有右子树,依次递归来输入整个二叉树。 运行后程序即会输出先序遍历的结果,树的深度以及叶子结点。 实验四: 校园导览图 (1)问题描述 实现校园图的建立(顶点不少于5个),并且实现基于此图的最小生成树算法及最短路径算法。 (2)数据结构设计 a.逻辑结构设计 非线性结构(图形结构) b.物理逻辑设计 顺序存储方式(数组) (3)算法设计 a.算法列表 序号 名称 函数表示符 操作说明 1 output voidoutput(P*s) 输出邻接矩阵 2 outputting voidoutputting(Pa[N],intn) 普里姆
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验 报告