数据结构课程设计.docx
- 文档编号:14022455
- 上传时间:2023-06-20
- 格式:DOCX
- 页数:26
- 大小:195.67KB
数据结构课程设计.docx
《数据结构课程设计.docx》由会员分享,可在线阅读,更多相关《数据结构课程设计.docx(26页珍藏版)》请在冰点文库上搜索。
数据结构课程设计
一需求分析:
1.问题描述
1.1学生成绩管理系统
利用线性链表实现学生成绩管理系统,具体功能:
输入、输出、插入、删除、查找、追加、读入、显示、保存、拷贝、排序、索引、分类合计、退出,并能在屏幕上输出操作前后的结果。
1.2交通咨询系统设计
设计一个交通咨询系统,能让旅客咨询从任一个城市定点到另一个城市定点之间的最短路径或最低花费或最少时间等问题。
对于不同的咨询要求。
可输入城市间的路程或所需时间或所需花费。
2.基本要求
2.1输入的形式和输入值的范围
1.学生成绩管理系统中每个学生的信息以字符串型的班级、整形的学号、字符串型的姓名、三个整形成绩为单位构成一个记录。
输入形式就是这样的记录。
2.交通咨询系统中是以输入两个顶点的内容,所在矩阵下标及对应权值。
在查询两个顶点之间最短路径时,只需输入两个顶点信息。
2.2输出的形式
1.学生成绩管理系统中,输出也是按照上面表述的记录进行输出。
即每个学生的信息以字符串型的班级、整形的学号、字符串型的姓名、三个整形成绩学生成绩。
2.交通咨询系统中,当输入两个顶点信息时,输出其对应的最短路径以及所经过的路径。
2.3程序所能达到的功能
1.学生成绩管理系统中,算法能通过界面提醒,输入一些学生信息,完成输入、输出、插入、删除、查找、追加、读入、显示、保存、拷贝、排序、索引、分类合计、退出,并能在屏幕上输出操作前后的结果。
2.交通咨询系统中,算法通过Dijkatra算法,可以求最短路径,事先输入一些信息,用矩阵建立一个图,再输入两个顶点信息来求最短路径以及这个最短路径做经过的顶点信息。
二概要设计
1.数据结构
1.学生成绩管理系统中,所用的数据结构是线性链表。
2.交通咨询系统中,所用的数据结构是线性顺序表。
2.程序模块
2.1学生成绩管理系统中的程序模块
1.initlist()初始化带有头结点的单链表;
2.inserLnode(Lnode*L,inti)在单链表中插入数据;
3.createLnode(Lnode*L)创建学生信息系统的包含的信息;
4.deletLnode(Lnode*L)删除学生信息系统中的数据;
5.travellLnode(Lnode*L)遍历学生信息系统;
6.chaxuehao(Lnode*T)通过学号对学生信息系统进行索引遍历;
7.chaclass(Lnode*T)通过班级对学生信息系统进行遍历;
8.sort(Lnode*L)根据成绩对学生信息系统进行排序;
9.xin()以菜单的形式将学生信息输出;
10.chuang()调用函数实现其功能;
2.2交通咨询系统中的程序模块
1.create(Mrapgh&G)建立一个图并用矩阵存储;
2.travell(Mrapgh&G)把建立的矩阵输出出来;
3.locate(Mrapgh&G,charm,charn)用Dijkatra算法求两点最短路径;
4.Dijkatra(Mrapgh&G,intv)Dijkatra算法,求V顶点到所有顶点的最短路径;
3.各模块之间的调用关系以及算法设计
3.1学生成绩管理系统中的模块调用关系
学生管理系统模块如下图1.1所示:
图1.1学生管理系统模块
算法设计:
S1、建立一个带有头结点的单链表;
S2、对点链表进行初始化操作;
S3、输入学生信息,存储在建立好的单链表中,然后执行s8;
S4、插入学生的数据,如果插入位置输入不正确,则从新定位插入;然后执行s8;
S5、根据学号信息删除学生信息,如果输入的学号查找无该生,则重新输入;然后执行s8;
S6、根据班级或学号索引学生信息,如果输入的班级或学号不存在亦或不正确,则从新输入,然后执行s8;
S7、根据学生成绩对学生信息进行排序,本过程采用菜单单元对学生信息进行排序,执行完之后执行s8;
S8、输出学生信息。
3.2交通咨询系统中的算法设计
算法设计:
S1、建立一个交通图用矩阵存储;
S2、输出矩阵表示的交通图;
S3、用Dijkatra算法计算最短路径;
S4、输入两个顶点信息,输出两顶点之间最短路径以及所经过路径。
三详细设计
1.学生成绩管理系统
1.1成绩录入:
intinserLnode(Lnode*L,inti)
{
intj;
Lnode*p,*q;
p=(Lnode*)malloc(sizeof(Lnode));
cin>>p->clas>>p->num>>p->name>>p->score[0]>>p->score[1]>>p->score[2];
q=L;
for(j=0;j
{
q=q->next;
}
if(j>i&&q->next!
=null)
returnnull;
p->next=q->next;
q->next=p;
return1;
}
intcreateLnode(Lnode*L)
{
inti,n;
cout<<"请输入人数:
\n";
cin>>n;
cout<<"请输入班级学号姓名三门成绩:
\n";
for(i=0;i {inserLnode(L,i);} returnn; } 1.2菜单显示: voidxin() { cout<<"******************学生成绩系统********************\n"; cout<<"链表中建立初始数据(a)\n"; cout<<"排序(b)\n"; cout<<"链表中插入一个数据(c)\n"; cout<<"链表中删除元素(d)\n"; cout<<"根据学号汇总学生信息(e)\n"; cout<<"根据班级汇总学生信息(f)\n"; cout<<"浏览学生信息(g)\n"; cout<<"退出系统(z)\n"; } 1.3删除操作: intdeletLnode(Lnode*L) { inti; cout<<"请输入你想删除的数据位置: \n"; cin>>i; intj; Lnode*p,*q; q=L; for(j=0;j { q=q->next; } if(j>i&&q->next! =null) returnnull; p=q->next; q->next=p->next; return1; } 2.交通咨询系统 2.1交通图用矩阵存储: voidcreate(Mrapgh&G)//建立的图并用矩阵存储 { inti,j,m,n,w; cout<<"pleaseinputn: \n"; cin>>G.n; cout<<"pleaseinputzimu\n"; for(i=0;i { cin>>G.data[i]; } for(i=0;i for(j=0;j { if(i==j) G.edges[i][j]=0; else G.edges[i][j]=maxsize; } cout<<"pleaseinpute: \n"; cin>>G.e; cout<<"pleaseinputmnw: \n"; for(i=0;i { cin>>m; cin>>n; cin>>w; G.edges[m][n]=w; } } 2.2Dijkatra算法: voidDijkatra(Mrapgh&G,intv) { inti,j,min,k; intvisit[maxsize]={0}; for(i=0;i {disk[i]=G.edges[v][i];} visit[v]=1; path[v]=-1; for(i=0;i { if(disk[i]! =maxsize&&i! =v) path[i]=v; else path[i]=-1; } for(j=1;j { min=maxsize; for(i=0;i { if(disk[i] {min=disk[i]; k=i;} } visit[k]=1; for(i=0;i { if((visit[i]==0)&&(disk[i]>disk[k]+G.edges[k][i])) {disk[i]=disk[k]+G.edges[k][i]; path[i]=k;} } } } 四测试与分析 1.学生成绩管理系统 1.1学生管理系统测试与结果: 1.对输入的数据进行遍历输出如下图4.1所示: 图4.1对输入的数据进行遍历输出 2.对输入数据进行插入操作结果如下图4.2所示: 图4.2输入数据进行插入操作结果 3.对输入数据进行删除操作结果如下图4.3所示: 图4.3输入数据进行删除操作结果 4.对输入数据进行排序结果如下图4.4所示: 图4.4对输入数据进行排序结果 5.对数据进行索引查找结果图如下图4.5所示: 图4.5对数据进行索引查找结果图 2.交通咨询系统 2.1交通咨询系统测试与结果 实验结果图如下图4.6所示: 图4.6交通咨询系统测试结果图 2.2交通咨询系统结果分析 先是根据a,b,c,d这四个顶点(交通地点)来建立一个4*4的矩阵,矩阵中分别存着相应一个顶点到另一个顶点的权值,自己到自己的距离为0,不直接相连的地方为无穷大。 建立结束,输入两个地点,如上图输入b,a,先根据顶点转换成相应的矩阵的下标,也就是相应的0和1,在根据a下标采用Dijkatra算法求得a到所有顶点的最短路径,在输出时采用堆栈对disk[1]的顶点一次递归输出,再将path[1]的值也就是a到b的最短路径输出即为上图所示结果图。 五总结 本次课程设计,从来是下达任务,到完成,可谓是个非常艰难的任务。 首先,在选题上,不知道自己到底会哪个,感觉哪个都会一点点,又感觉哪个都不太会,正好当时在学最短路径,于是就将最短路径很好的学了一下,算法什么的都找了好多参考资料来领略算法的深层含义。 我主要研究的是Dijkatra算法来求两个顶点之间的最短路径,也就是第二个实验,在整个实验,只要理解Dijkatra算法,理解它的思想才是最重要的,在实验中,刚开始不知道怎么样来求出一个顶点到另一个顶点的所经历的路径,后来听老师讲课说可以设置一个数组变量disk[]来求存储,然后根据递归调用,也就是一个堆栈再求出所经历的路径,可是实施起来也不是那么容易,又看了很多参考资料才做出来。 总之在课程设计过程中,锻炼我的独自思考能力,让我更加熟练的掌握了C++这个软件的使用,对于一些常见的语法出现的问题,能够很快的找出错误根源,也更加理解了Dijkatra算法的含义,同时也锻炼了与他人合作的能力,在设计中我们小组不断发现错误,不断改正,不断领悟,最终的检测调试环节,本身就是在践行“过而能改,善莫大焉”的知行观。 遇到问题就跟小组人员互相帮助。 在今后社会的发展和学习实践过程中,一定要不懈努力,不能遇到问题就想到要退缩,一定要不厌其烦的发现问题所在,然后一一进行解决,只有这样,才能成功的做成想做的事,才能在今后的道路上劈荆斩棘,而不是知难而退,那样永远不可能收获成功,收获喜悦,也永远不可能得到社会及他人对你的认可! 六附录: 源程序清单 1.学生成绩管理系统程序清单: #include #include #include #include #definenull0 typedefstructLnode { charclas[20]; intnum; charname[20]; intscore[3]; structLnode*next; }Lnode; Lnode*initlist() { Lnode*H; H=(Lnode*)malloc(sizeof(Lnode)); if(! H) returnnull; H->next=null; returnH; } intinserLnode(Lnode*L,inti) { intj; Lnode*p,*q; p=(Lnode*)malloc(sizeof(Lnode)); cin>>p->clas>>p->num>>p->name>>p->score[0]>>p->score[1]>>p->score[2]; q=L; for(j=0;j { q=q->next; } if(j>i&&q->next! =null) returnnull; p->next=q->next; q->next=p; return1; } intcreateLnode(Lnode*L) { inti,n; cout<<"请输入人数: \n"; cin>>n; cout<<"请输入班级学号姓名三门成绩: \n"; for(i=0;i { inserLnode(L,i); } returnn; } intdeletLnode(Lnode*L) { inti; cout<<"请输入你想删除的数据位置: \n"; cin>>i; intj; Lnode*p,*q; q=L; for(j=0;j { q=q->next; } if(j>i&&q->next! =null) returnnull; p=q->next; q->next=p->next; return1; } inttravellLnode(Lnode*L) { intj=0; Lnode*q; q=L; cout<<"学生信息如下: \n"; while(q->next! =null) { q=q->next; cout< } return1; } voidchaxuehao(Lnode*T) { Lnode*q=T; intxuehao; cout<<"请输入学号: \n"; cin>>xuehao; printf("学号为%d的学生如下: \n",xuehao); while(q->next! =null) { q=q->next; if(q->num==xuehao) cout< } } voidchaclass(Lnode*T) { Lnode*q=T; charclass1[20]; cout<<"请输入班级: \n"; cin>>class1; while(q->next! =null) { q=q->next; if(strcmp(q->clas,class1)==0) cout< } } voidsort(Lnode*L) { intk,j,i; Lnode*p,*f,*x,*y; f=null; p=L; cout<<"\t1.第一门成绩排序\n"; cout<<"\t2.第二门成绩排序\n"; cout<<"\t3.第三门成绩排序\n"; cout<<"请按序号选择相应操作: "; cin>>k; if(k==1) { while(f! =L->next->next) { for(p=L;p->next->next! =f;p=p->next) { if((p->next->score[0])>(p->next->next->score[0])) { x=p->next; y=p->next->next; p->next=y; x->next=y->next; y->next=x; } } f=p->next; } } if(k==2) { while(f! =L->next->next) { for(p=L;p->next->next! =f;p=p->next) { if((p->next->score[1])>(p->next->next->score[1])) { x=p->next; y=p->next->next; p->next=y; x->next=y->next; y->next=x; } } f=p->next; } } if(k==3) { while(f! =L->next->next) { for(p=L;p->next->next! =f;p=p->next) { if((p->next->score[2])>(p->next->next->score[2])) { x=p->next; y=p->next->next; p->next=y; x->next=y->next; y->next=x; } } f=p->next; } } } voidxin() { cout<<"******************学生成绩系统*********************\n"; cout<<"链表中建立初始数据(a)\n"; cout<<"排序(b)\n"; cout<<"链表中插入一个数据(c)\n"; cout<<"链表中删除元素(d)\n"; cout<<"根据学号汇总学生信息(e)\n"; cout<<"根据班级汇总学生信息(f)\n"; cout<<"浏览学生信息(g)\n"; cout<<"退出系统(z)\n"; } intchuang() { Lnode*T=initlist(); xin(); charinfo; cin>>info; while(info! ='z') { switch(info) { case'a': {createLnode(T);break;} case'b': {sort(T);break;} case'c': { intm; cout<<"请输入在哪个位置插入一个学生信息: \n"; cin>>m; inserLnode(T,m-1); break; } case'd': {deletLnode(T);break;} case'e': {chaxuehao(T);break;} case'f': {chaclass(T);break;} case'g': {travellLnode(T);break;} case'z': return0; } xin(); cin>>info; } return1; } voidmain() { chuang(); } 2.交通咨询系统程序清单: #include #include #definenull0 #definemaxsize500 typedefstruct { intedges[maxsize][maxsize]; chardata[maxsize]; intn,e; }Mrapgh; voidcreate(Mrapgh&G)//建立的图并用矩阵存储 { inti,j,m,n,w; cout<<"pleaseinputn: \n"; cin>>G.n; cout<<"pleaseinputzimu\n"; for(i=0;i { cin>>G.data[i]; } for(i=0;i for(j=0;j { if(i==j) G.edges[i][j]=0; else G.edges[i][j]=maxsize; } cout<<"pleaseinpute: \n"; cin>>G.e; cout<<"pleaseinputmnw: \n"; for(i=0;i { cin>>m; cin>>n; cin>>w; G.edges[m][n]=w; } } voidtravell(Mrapgh&G)//把建立的矩阵输出 { inti,j; for(i=0;i { for(j=0;j cout< cout< } } intpath[maxsize]; intdisk[maxsize]; voidlocate(Mrapgh&G,charm,charn) { voidDijkatra(Mrapgh&G,intv); inti,c,d; for(i=0;i { if(G.data[i]=
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计