数据结构课程设计学生成绩管理系统部分.docx
《数据结构课程设计学生成绩管理系统部分.docx》由会员分享,可在线阅读,更多相关《数据结构课程设计学生成绩管理系统部分.docx(33页珍藏版)》请在冰点文库上搜索。
数据结构课程设计学生成绩管理系统部分
大连科技学院
数据结构课程设计
题目单链表的基本操作-建立和遍历
学生成绩管理系统-排列
排序问题-选择排序,直接插入排序
学生姓名李易霖 专业班级计算机10-1
指导教师宋丽芳职称 副教授
所在单位信息科学系软件教研室
系主任王立娟
完成日期2012年1月6日
大连科技学院
数据结构课程设计成绩考核表
学生姓名
李易霖
专业班级
计算机10-1
学号
1001020112
题目
单链表的基本操作,学生成绩管理系统,排序问题
考核项目
分值
评分
1
出勤情况
10
2
完成原理分析
10
3
设计分析
10
4
完成代码编写与调试
10
5
独立工作能力、综合运用所学知识分析和解决问题能力及实际工作能力提高的程度
10
6
回答问题
20
7
课程设计报告格式规范性
30
合计
100
总评成绩
注:
总评标准采用优良制:
优秀(90分以上)、良好(80-90)、中等(70-80)、及格(60-70)、不及格(60分以下)
指导教师签字:
课程设计任务书
一、任务及要求
1.设计(研究)内容和要求
研究内容:
单链表的基本操作,学生成绩管理系统,二叉树的运算
任务和要求:
(1)学习数据结构基础知识,掌握数据结构典型的算法的使用。
(2)对指导教师下达的题目进行任务分析。
(3)根据分析结果完成设计。
(4)编程:
在计算机上实现题目的代码实现。
(5)完成对程序的测试和调试。
(6)提交课程设计报告(约二十页),含程序代码及运行结果。
2.原始依据
结合数据结构课程中的基本理论和基本算法,正确分析出数据的逻辑结构,合理地选择相应的存储结构,并能设计出解决问题的有效算法。
提高程序设计和调试能力。
学生通过上机实习,验证自己设计的算法的正确性。
学会有效利用基本调试方法,迅速找出程序代码中的错误并且修改。
二、工作量
2周(10个工作日)时间。
三、计划安排
第1个工作日-第2个工作日:
查找相关资料、书籍,阅读示例文档,选择题目。
第3个工作日:
题目分析,设计算法。
第4个工作日-5个工作日:
功能模块的划分和设计。
第6个工作日:
实现具体数据结构和模块。
第7个工作日-第8个工作日:
程序设计与调试,编写课程设计报告。
第9个工作日:
上交课程设计报告。
第10个工作日:
软件验收、答辩,成绩评定。
指导教师签字:
2011年12月26日
题目一:
单链表的基本操作
1需求分析
1.1问题描述
用学过的方法建立单链表,掌握单链表的建立、插入,查找、删除、逆置等基本算
法和操作。
掌握指针类型的应用和结构体的具体操作,初步掌握采用自底向上,分模块进行的程序的调试与测试。
1.2实现要求
(1)建立单链表
用尾插法建立带头结点的单链表h,从键盘输入各整型数据元素,以“-1”
作为输入结束标志符。
(2)遍历单链表h
依次输出链表中各数据元素。
(3)按序号查找
查找单链表h中第i个元素并输出该元素。
(4)插入
在单链表h的第i个元素位置上插入x数据元素
并遍历单链表h
(5)删除
删除单链表h的第i个数据元素,并返回第i个元素
同时遍历单链表h
(6)求表长
求单链表的表长并输出表长
(7)逆置单链表
逆置带头结点的单链表h,逆置后的单链表利用原表中的结点空间,不重新申请空间,逆置后进行遍历。
(8)将一个元素插入到有序表中使表仍然有序
带头结点的单链表中的数据元素是整型数且有序。
将x插入到顺序表的适当位置上,保持表的有序性,将两个递增的有序表归并成一个递减的有序表,利用原表空间,不能重新申请空间
2.概要设计
2.1逻辑结构设计
逻辑结构:
线性结构
二元组图式
G=(D,S)
D=(q,a,z,w,s,x)
S={r}
R={,,,,}
2.2功能结构设计
图1功能设计图
本人在该小组中主要负责完成建立和遍历模块的功能实现
2.3物理结构设计
物理结构
(1)链式存储示意图如下:
图2链式存储示意图
(2)c语言描述如下:
#include
/*denitionofdatatype*/(
Typedefchardatatype;
typedefstructnode
{datatypedata;
structnode*next;
}linklist;
3算法设计与实现
3.1算法设计
1.用于定义单链表的存储结构的函数LinkList()。
2.用带头结点的尾插法创建链表的函数createList()。
3.用于查找第i位元素的函数get()。
4.用于遍历单链表的函数visit()。
5.用于获得表长的函数lengthList()。
6.用于在第i位元素后插入新元素的函数insert()。
7.用于删除第i位元素的函数delete()。
8.用于逆置单链表的函数reverse()。
9.用于在程序开始输出欢迎和提示信息的函数start()。
10.用于在程序结束时输出提示信息的函数end()。
11.用于调用上述函数的主函数main(),主函数中对各函数的调用次序及方法为:
定义了必要的变量后,先使用system()函数设置操作台背景色;再调用程序开始时的输出函数start();然后调用创建单链表的函数createList()并用相应类型的变量接收它返回的头结点地址;然后询问是否遍历(询问步骤下同),需要的话将刚接收的头结点地址作为参数调用遍历函数visit();遍历后传递头结点的地址调用查找函数get(),该函数具有判断查找位置合法性的功能;查找操作结束后传递头结点地址给inser()调用它(插入操作带有判断插入位置是否合法的功能,故还要调用lengthList()获得表长作为插入函数的另一个参数)插入操作完成后将再次调用遍历函数visit()显示插入结果;结束插入后将头结点地址作为参数调用删除函数delete(),删除成功后将调用遍历函数显示删除后的结果(插入函数也具有判断位置合法性的功能);最后是调用逆置函数reverse(),同样是以头结点为参数。
3.2算法实现与调试
(1)建立单链表:
123456
图3建立单链表
(2)遍历单链表
图4遍历单链表
题目二:
线性表的应用——学生成绩管理
1需求分析
1.1问题描述
编写一个简单的学生信息管理程序,能实现对学生信息的简单管理。
编写一个简单的学生信息管理程序,能实现对学生信息的简单管理。
1.2实现要求
(1)创建成绩链表,学生数据包含学生的学号、姓名和成绩。
(2)可以在指定学号学生前插入学生成绩数据。
(3)可以删除指定学号的学生数据。
(4)可以计算学生的总数。
(5)可以按学号和姓名查找学生。
(6)可以显示所有学生的成绩。
(7)可以把学生成绩按从高到低的顺序排列。
2.概要设计
2.1逻辑结构设计
逻辑结构,线性结构
二元组图式如下:
G=(D,S)
D=(q,a,z,w,s,x)
S={r}
R={,,,,}
图5二元组图式
2.2功能结构设计
图6功能结构设计图
本人在该小组中主要负责完成排列功能实现
2.3物理结构设计
物理结构:
链式存储,c语言描述如下:
#include
#include
#include
#include
typedefstructStudent
{intscore;
charsno[5],sname[8];
}Student;
typedefstructNode
{StudentstudentInfo;
structNode*next;
}LinkList;
3算法设计与实现
3.1算法设计
1.定义学生数据类型stu。
2.定义结点存储类型LinkList。
3.函数声明部分。
4.学生信息的输入函数input()。
5.用带头结点的尾插法建立单链表来存储学生信息的函数createTailList()。
6.遍历单链表显示出学生数据的函数showList(),此函数由罗聪同学编写。
7.按学号查找学生信息的函数getElem(),此函数由贾利洋同学编写。
8.显示单个学生信息的函数showElem(),此函数由罗聪同学编写。
9.按姓名查找学生信息的函数locateElem(),此函数由贾利洋同学编写。
10.求学生总人数(即表长)的函数lengthList(),此函数由华政同学编写。
11.在指定学号前插入学生数据的函数insertElem(),此函数由孟繁章同学编写。
12.删除指定学号学生信息的函数deleteElem(),此函数由华政同学编写。
13.用直接插入法按分数从高到底排序的函数SIS()。
此函数由本人编写。
14.程序开始时的显示函数start()。
15.程序结束时的显示函数end()。
16.调用上述各函数的主函数main(),调用顺序及方法是:
首先定义必要的变量;调用程序开始时的显示函数start();选择后循环语句嵌套选择语句;接着是循环语句中嵌套选择语句和判断语句,根据用户的选择,赋予适当的参数来调用各个功能函数;结束时调用程序结束时的显示函数end()。
3.2算法实现与调试
(1)开始的菜单
图7开始界面
(2)当前学生成绩从高到低排序
图8排序
题目三:
排序问题
1需求分析
1.1问题描述
排序是数据处理中最常见,最基本的操作。
在解决很多实际问题是,都离不开排序。
排序还是另一种基本操作——查找操作的基础,排序可以提高查找的效率。
因此,学习和研究排序方法是计算机程序人员课题之一。
1.2实现要求
利用直接插入和选择排序的方法对一组无序的序列进行排序,使其能正确的按顺序输出
2.概要设计
2.1逻辑结构设计
选择排序:
在要排序的一组数中,选出最小的一个数与第一个位置的数交换,然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止。
直接插入排序:
将一个待排序记录按照排序码的大小插入到一个有序序列的适当位置,使得插入后的序列仍然有序,直到所有的记录全部插入到有序序列中。
2.2功能结构设计
图9功能结构设计图
关键码序列为(42,20,17,27,13,8,17*,48),用直接插入排序算法进行排序。
排序过程如图所示。
2.3物理结构设计
选择排序
第i趟排序开始时,当前有序区和无序区分别为R[1..i-1]和R(1≤i≤n-1)。
该趟排序从当前无序区中选出关键字最小的记录R[k],将它与无序区的第1个记录R交换,使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
这样,n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。
直接插入排序
用函数实现直接插入排序,并输出每趟排序的结果.
输入格式
第一行:
键盘输入待排序关键的个数n
第二行:
输入n个待排序关键字,用空格分隔数据
输出格式
每行输出一趟排序结果,数据之间用一个空格分隔
输入样例
10
5480932671
输出样例
4580932671
4580932671
0458932671
0458932671
0345892671
0234589671
0234568971
0234567891
0123456789
3算法设计与实现
3.1算法设计
功能:
选择排序
输入:
数组名称(也就是数组首地址)、数组中元素个数
*/
voidselect_sort(int*x,intn)
{
inti,j,min,t;
for(i=0;i0~n-2共n-1次*/
{
min=i;/*假设当前下标为i的数最小,比较后再调整*/
for(j=i+1;j{
if(*(x+j)<*(x+min))
{
min=j;/*如果后面的数比前面的小,则记下它的下标*/
}
}
if(min!
=i)/*如果min在循环中改变了,就需要交换数据*/
{
t=*(x+i);
*(x+i)=*(x+min);
*(x+min)=t;
}
}
}
功能:
直接插入排序
输入:
数组名称(也就是数组首地址)、数组中元素个数
*/
voidinsert_sort(int*x,intn)
{
inti,j,t;
for(i=1;i1~n-1共n-1次*/
{
/*
暂存下标为i的数。
注意:
下标从1开始,原因就是开始时
第一个数即下标为0的数,前面没有任何数,单单一个,认为
它是排好顺序的。
*/
t=*(x+I);
for(j=i-1;j>=0&&t<*(x+j);j--)/*注意:
j=i-1,j--,这里就是下标为i的数,在它前面有序列中找插入位置。
*/
{
*(x+j+1)=*(x+j);/*如果满足条件就往后挪。
最坏的情况就是t比下标为0的数都小,它要放在最前面,j==-1,退出循环*/
}
*(x+j+1)=t;/*找到下标为i的数的放置位置*/
}
}
3.2算法实现与调试
1直接插入排序
(1)第一行:
键盘输入待排序关键的个数n
图10输入界面
(2)第二行:
输入n个待排序关键字,用空格分隔数据
图11排序演示图
(3)每行输出一趟排序结果,数据之间用一个空格分隔
2直接选择排序
(1)输入几个字符串,直到输入"!
"结束
图12输入数字
(2)分别以升序和降序排列字符串数组。
图13排序结果
总结
通过这次两周的数据结构课程设计,我学会了许多知识并且提高了自己的动收能力与团队合作能力,在完成这次课程设计的过程中,我认真查找资料。
和队友配合,共同努力完成了这次课程设计。
本次课程设计的主题分为三个,分别为单链表的基本操作,学生成绩管理系统排序问题,通过上机实践,我对这些知识有了更进一步的了解,通过这次课程设计,我的专业知识也丰富了许多。
在程序调试阶段,一个小小的错误就会让程序无法运行,我在这个过程中认真查找错误,最后通过我的不懈努力终于把程序调试成功了。
这次课程设计的过程让我学会了很多,成长了很多,同时也让我看到了自己身上的不足,许多看似简单的问题在自己操作的时候发现并不那么简单。
以后我要继续努力学习专业知识,提高自己的动手能力,不断的丰富自己,完善自己。
参考文献
[1]赵波,霍利等编著.《数据结构实用教程》(C语言版)清华大学出版社,2009.9
[2]唐策善,李龙澍,黄刘生.《数据结构用C语言描述》[M]北京:
高等教育出版社.1999
[3]严蔚敏,吴伟民著.《据结构(C语言版),清华大学出版,1999
[4]陈一华等编.数据结构---使用C语言,电子科技大学出版社,1998
[5]谭浩强.C语言程序设计(第二版).北京:
高等教育出版社,2002
[6]《标准C语言程序设计及应用》周纯杰,刘正林等编著华中科技大学
[7]《C语言课程设计案例精编》姜灵芝,余健编著清华大学出版社
附录全部代码
题目一
#include
#include
#include
/*denitionofdatatype*/
typedefintdatatype;
typedefstructnode
{datatypedata;
structnode*next;
}linklist;
/*functionofcreate*/
linklist*create()
{intx;
linklist*head,*s,*r;
head=(linklist*)malloc(sizeof(linklist));
r=head;
scanf("%d",&x);
while(x!
=-1)
{s=(linklist*)malloc(sizeof(linklist));
s->data=x;
r->next=s;
r=s;
scanf("%d",&x);
}
r->next=NULL;
returnhead;
}
/*functionofvisit*/
voidvisit(linklist*head)
{
linklist*p;
p=head->next;
while(p)
{printf("%d",p->data);
p=p->next;
}
printf("\n");
}
voidmain()
{linklist*h1,*q,*h2;
inti,b=1;
intx;
intin,de,ins;
datatype*e;
while(b)
{inta;
printf("\n\n");
printf("--------------------菜单------------------------\n");
printf("------------------------------------------------\n");
printf("
(1)创建(带头尾插)
(2)遍历(3)查找\n");
printf("(4)插入(无序)(5)删除(6)求表长\n");
printf("(7)逆置(8)插入(有序)(9)归并\n");
printf("(10)退出\n");
printf("------------------------------------------------");
printf("\n请输入功能选项:
");
scanf("%d",&a);
switch(a)
{case1:
printf("Creatlinklisth1:
\n");
h1=create();
break;
case2:
printf("visitLinkListh1:
\n");
visit(h1);
break;
case3:
printf("pleaseinputthestationoflocate:
");
scanf("%d",&i);
q=get(h1,i);
if(q)printf("%d",q->data);
elseprintf("locationiserror");
printf("\n");
break;
case4:
printf("pleaseinputthestationanddataofinsert:
");
scanf("%d,%d",&i,&x);
in=insert(h1,i,x);
printf("\n");
if(in==0)printf("locationiserror");
elsevisit(h1);
printf("\n");
break;
case5:
printf("pleaseinputthestaionofdelete:
");
scanf("%d",&i);
e=(datatype*)malloc(sizeof(datatype));
de=delete(h1,i,e);
if(de==0)printf("locationiserror");
else{visit(h1);printf("thedeleis%d",*e);}
printf("\n");
break;
case6:
printf("\nthetablelong:
%d\n",lengthList(h1));
break;
case7:
reverse(h1);
visit(h1);
break;
case8:
printf("pleaseinputthedataofinsertSort:
");
scanf("%d",&x);
ins=insertSort(h1,x);
printf("\n");
visit(h1);
printf("\n");
break;
case9:
h1=create();
visit(h1);
h2=create();
visit(h2);
visit(meger(h1,h2));
break;
case10:
printf("\n退出\n");
b=0;
break;
}
}
}
题目二
#include
#include
#include
#include
typedefstructStudent{/*学生类型定义*/
intscore;/*成绩*/
charsno[5],sname[8];/*学号,姓名*/
}Student;
typedefstructNode{/*结点类型定义*/
StudentstudentInfo;/*学生信息*/
structNode*next;/*指向后继元素的指针域*/
}LinkList;
voidinsertSort(L