*******************
实践教学
*******************
兰州理工大学
计算机与通信学院
2012年春季学期
算法与数据结构课程设计
题 目： 学籍管理 专业班级： 10级软件工程基地班
姓 名：
学 号： 10500233 指导教师： 王旭阳 成 绩：
目 录
摘 要 ...................................................................................................................... 1 1. 2. 3. 4. 5. 6.
采用类C语言定义相关的数据类型 .......................................................... 2 各模块的伪码算法 ...................................................................................... 2 函数的调用关系图 ...................................................................................... 6 调试分析 ...................................................................................................... 7 测试结果 ...................................................................................................... 7 源程序（带注释） ..................................................................................... 11
总 结 .................................................................................................................... 27 参考文献 ................................................................................................................ 28 致 谢 .................................................................................................................... 29 附件Ⅰ 任务一源程序代码 .................................................................................. 30
摘 要
学籍管理系统设计涉及学生信息的录入，显示，查找，删除，修改，统计，保存，退出等功能，从而能够对信息进行处理。程序中运用了相关类的知识，同时定义了一定数量的数据及成员函数。程序使用了数组记录统计的相关数据，运用了指针实现相应功能函数的功能，运用了student ,school两个类实现面向对象的要求。程序的完成涉及到程序的分析，模块的分解，程序的控制，程序的调试。
关键词：学籍管理；数据结构；C++；程序控制
1
1. 采用类c语言定义相关的数据类型
类：student 数据成员
编号，姓名，年龄，专业，性别，籍贯，民族，生日，政治面貌，身份证，数学成绩，英语成绩，计算机成绩 类：school 成员函数
录入函数Input()：输入编号到计算机的成绩；
统计函数count()：统计各科的总成绩，计算平均成绩，统计各科的及格率； 查询函数found()：按学号或姓名查找学生的记录； 修改函数mend()：修改指定学号学生成绩记录； 删除函数del()：删除指定学号学生记录； 输出函数show()：输出班级所有学生成绩记录；
2. 各模块的伪码算法
2.1定义类： class student {
protected: variable； public: student *next; student(){ } ~student(){ }
char* getname(){ return name; } int getnumber(){ return number;} double getscore(int i) { return score[i];}
float getg(){ return (score[0]+score[1]+score[2]+score[3]+score[4]+score[5]); }
2
input：data； output：data。 2.2保存函数 void school::save() {
student *p; p=head;
ofstream os(\"student.txt\ if (school::getkey()==1) {
while(p->next) {
(p->next)->output(os); p=p->next; } }
school::setkey(0); }
2.3修改函数 void school::mend() {
student *p; int num=-1,n; char name[20]=\"^\"; if(n==1) 学号 if(n==2) 姓名
if( !find(&p,num,name) ) (p->next)->output(); (p->next)->input(); school::setkey(1);
3
}
2.4查找函数 void school::found() {
student *p; int num=-1,n=9; char name[20]=\"^\"; if(n==1) ：学号 if(n==2) ：姓名 if(!find(&p,num,name) ) (p->next)->output(); }
2.5初始化函数 //初始化函数 void school::begin() {
student *p,*p2; p=head; clear(); long t;
ifstream is(\"student.txt\ if(!is) {
ofstream os(\"student.txt\ os.close(); return ; }
int num=-1; while(1) {
4
num=-1; t=is.tellg(); is>>num; is.seekg(t); if(num<0) { is.close(); return; }
p2=new student; p2->input(is); p->next=p2; p2->next=NULL; p=p->next; } }
2.6清空函数： void school::clear() {
student *p,*p2; p=head->next; while( p ) { p2=p; p=p->next; delete p2; } }
5
3. 函数的调用关系图
系统组织结构图： 系统功能结构图 ：
初
始
化
程
序
输
入 退出 姓名查找 按要求逐步输入学生信息 选择修改方式 开始 选择菜单序号 录入信息 显 示信息 查找信息 删 除信息 修 改信息 统 计成绩 报 存信息 退 出 编号查询 输入学生信息 1 主程序 2 菜单程序 显示 查找 6
保存！ 保存 删除 修改 统计 退出
4. 调试分析
a、调试中遇到的问题及对问题的解决方法
此次课程设计所研究的问题不是很难，即进行学籍管理，所以总的高度比较顺利。但在最初的设计过程中犯了一个致命的错误，即没有很好的进行整体布局，也没有定义统一的函数接口，以致程序的结构与函数的混乱。当各模块组合在一起的时候更是无没进行调试。故只有一切从头开始，重新分配任务，以及统一定义各函数的接口。
在调试的过程中发现当输入错误的时会发生想不到的错误，为了避免这样意外的发生，写了一个判断函数judge()以及输入函数input()对其进行改进。
当一段相同的代码在程序中多次使用并且功能相对单一时，有必要将其写成一个函数，以减少工作量，并且使程序具有更好的可读性。在编写程序的过程中，及时对重要和难懂的程序段写注释是一个很好的习惯，无论是以后的测试还是以后的维护都能够节省相当多的时间。
调试时最先进行各函数的调试，确保无误时再进行各模块的调试，最后才是将各模块组合在一起测试完整的程序。在调试的过程中不断地进行改进、完善。
在序能够正确运行的基础上，再对各函数进行格式的优化，加强程序的结构性，并增强程序的可读性，包括给运行界面增加相应的操作提示等，使操作界面简单而又美观。
b、算法的时间复杂度和空间复杂度
本算法采用类对象的列表，假设实例化为n，则其时间复杂度和空间复杂度都是 O(n)。
5. 测试结果
5.1 主菜单:
7
5.2录入信息界面
8
5.3显示信息界面：
5.4查找学生界面：
9
5.5修改学生信息界面：
5.6统计成绩界面：
10
5.7保存学生信息界面：
6. 源程序（带注释）
#include #include class student { protected: int number; int age; char name[20]; char sex[6]; 11 char zhy[20]; char place[20]; char nation[6]; char birth[20]; char party[10]; char id[20]; float score[6]; public: student *next; student(){ } ~student(){ } char* getname(){ return name; } int getnumber(){ return number;} double getscore(int i) { return score[i];} float getg(){ return (score[0]+score[1]+score[2]+score[3]+score[4]+score[5]); } void input() { int e=1; cout<<\"\\\按提示输入:\"< cout<<\"\\输入年龄: \"; cin>>age; cout<<\"\\输入姓名: \"; cin>>name; do { cout<<\"\\输入性别: \"; cin>>sex; if(strcmp(sex,\"男\")==0 || strcmp(sex,\"女\")==0) 12 { cout<<\"\\输入专业: \"; cin>>zhy; cout<<\"\\输入籍贯: \"; cin>>place; cout<<\"\\输入民族: \"; cin>>nation; cout<<\"\\输入生日: \"; cin>>birth; cout<<\"\\输入政治面貌: \"; cin>>party; cout<<\"\\输入身份证号: \"; cin>>id; cout<<\"\\输入数学分数: \"; cin>>score[0]; cout<<\"\\输入英语分数: \"; cin>>score[1]; cout<<\"\\输入计算机分数: \"; cin>>score[2]; cout<<\"\\输入语文分数：\"; cin>>score[3]; cout<<\"\\输入算法与数据结构分数：\"; cin>>score[4]; cout<<\"\\输入物理分数：\"; cin>>score[5]; e=0; } else { cout<<\"\\\无此性别类型!重新输入!\"< e=1; } }while(e); return ; } void input(ifstream & is) { is>>number>>age>>name>>sex>>zhy>>place>>nation>>birth>>party>>id >>score[0]>>score[1]>>score[2]>>score[3]>>score[4]>>score[5]; is.get(); } void output() { cout<<\" 学生基本信息如下:\"< <<\" 总分:\"< os< public: school(){ head=new student; head->next=NULL; key=0; } ~school(){ delete head; } void input(); void mend(); 15 void del(); int find(student **p,int num,char *pn=\"^\"); void found(); void show(); void count(); void save(); void begin(); void clear(); char mainmenu(); int getkey(){ return key;} void setkey(int k){ key=k; } private: student *head; int key; }; //录入函数 void school::input() { student *p,*p2=NULL; p=head; int n; while(p->next) p=p->next; while(n) { p2=new student; p2->input(); p->next=p2; p2->next=NULL; p=p->next; 16 school::setkey(1); cout<<\"\\\按1继续,按0返回 : \"; cin>>n; } } //子查找函数 int school::find(student **p1,int num,char *pn) { student *p; p=head; while(p->next) { (*p1)=p; if( (p->next)->getnumber()==num||!strcmp( (p->next)->getname(),pn ) ) return 1; p=p->next; } return 0; } //查找函数 void school::found() { student *p; int num=-1,n=9; char name[20]=\"^\"; do { cout<<\"\\1:按学号查找,2:按姓名查找: \"; cin>>n; }while(n<1||n>2); 17 if(n==1) { cout<<\"\\\输入学号: \"; cin>>num; } if(n==2) { cout<<\"\\\输入姓名: \"; cin>>name; } if(!find(&p,num,name) ) { cout<<\"\\找不到你要查找的内容!\"< //删除函数 void school::del() { student *p,*p2; int num; cout<<\"\\\输入学号: \"; cin>>num; if( !find(&p,num,\"^\") ) { cout<<\"\\找不到你要删除的内容!\"< 18 p2=p->next; p->next=p2->next; delete p2; school::setkey(1); } //显示函数 void school::show() { student *p; p=head; while(p->next) { (p->next)->output(); p=p->next; } } //修改函数 void school::mend() { student *p; int num=-1,n; char name[20]=\"^\"; do { cout<<\"\\1:按学号修改,2:按姓名修改: \"; cin>>n; }while(n<1||n>2); if(n==1) { cout<<\"\\\输入学号: \"; 19 cin>>num; } if(n==2) { cout<<\"\\\输入姓名: \"; cin>>name; } if( !find(&p,num,name) ) { cout<<\"\\找不到你要修改的内容!\"< //保存函数 void school::save() { student *p; p=head; ofstream os(\"student.txt\ if (school::getkey()==1) { while(p->next) { (p->next)->output(os); p=p->next; } } 20 cout<<\"\\\文件已保存! \"< student *p,*p2; p=head; clear(); long t; ifstream is(\"student.txt\ if(!is) { ofstream os(\"student.txt\ os.close(); return ; } int num=-1; while(1) { num=-1; t=is.tellg(); is>>num; is.seekg(t); if(num<0) { is.close(); return; } p2=new student; 21 p2->input(is); p->next=p2; p2->next=NULL; p=p->next; } } //清空函数 void school::clear() { student *p,*p2; p=head->next; while( p ) { p2=p; p=p->next; delete p2; } } //统计函数 void school::count() { student *p; p=head; int n=0; double g[6]={0,0,0,0,0,0}; float j[6]={0,0,0,0,0,0}; while(p->next) { p=p->next; n++; 22 for(int i=0;i<6;i++) { g[i]=g[i]+( p->getscore(i) ); (p->getscore(i) )>=60? j[i]++ : 0 ; } } cout<<\"\\\\b\\b\\b\\b数学总分:\"< //主选菜单函数 char school::mainmenu() { char n[6]; cout<<\"\\n\\n ☆☆☆☆欢迎进入高校学籍管理系统☆☆☆☆\"< <<\"* * 3: 查找学生信息 * *\"< school pp; int k=1; char n; pp.begin(); while(k==1) { n=pp.mainmenu(); switch(n) { case '1':pp.input(); break; case '2':pp.show(); break; case '3':pp.found(); break; case '4':pp.del(); break; case '5':pp.mend(); break; case '6':pp.count(); break; 24 case '7':pp.save(); break; case '0': if(pp.getkey()==1) { cout<<\"\\\是否保存? 1 : 保存 0:不保存 : \"; cin>>k; if(k==1) pp.save(); } pp.clear(); k=0; break; } } } 25 26 总 结 数据结构课程设计是我们在本阶段学完理论课程之后对自己该方面的能力的一次很好的检验，从开始的算法思路到运行调试后的可用程序，都是一个很好的学习和锻炼的过程。使我们巩固了原有的理论知识，培养了我们灵活运用所学过的知识来分析、解决实际问题的能力。 通过本次课程设计过程我会到了许多知识，这也是在大学里第一次比较完整的完成一个小项目，虽然过程中遇到了许多困难，在同学和老师的帮助下一一克服了。通过不断的发现问题，总结问题和解决问题的过程，使我在此次毕业设计活动中不断的提高，和得到了宝贵的经验。 我的课程设计题目是学籍管理。它主要用到了链表、查找等相关知识。在这两个周的课程设计中,通过该题目的设计过程,我加深了对链表的理解,对链表结点的添加、查找、删除基本运算的实现有所掌握,对课本中所学的各种数据结构进一步理解和掌握。 在完成该课程设计的过程中我遇到了很多麻烦，但是通过查找相关资料以及虚心向别人请教，逐步解决了所有问题。该过程培养了我自主动手，独立研究的能力，为今后在学习工作中能更好的发展打下了一定的基础。 三个周的课程设计虽然短暂，但是确实使我受益匪浅。 27 参考文献 1 严蔚敏，吴伟民.《数据结构（C语言版）》.清华大学出版社. 2 严蔚敏，吴伟民.《数据结构题集（C语言版）》.清华大学出版社. 3 《DATA STRUCTURE WITH C++》. William Ford,William Topp .清华大学出版社（影印版）. 4 谭浩强.《c语言程序设计》. 清华大学出版社. 5数据结构与算法分析（Java版） , A Practical Introduction to Data Structures and Algorithm Analysis Java Edition Clifford A. Shaffer , 张铭,刘晓丹译 电子工业出版社 2001 年1月 6陈雪飞《C++实例入门》，中国青年出版社，2004年5月出版 7谭浩强编，《C++面向对象程序设计》，清华大学出版社，2005年7月出版 8李师贤等译，《C++精髓》，机械工业出版社，2002年8月出版 9韩滨 魏海萍，《C++类库使用手册》，电子工业出版社，2007年7月出版 10陈灿煌，《C++彻底研究》 中国青年出版社，2005年9月出版。 28 致 谢 由于以前对C语言以及C++语言的接触并不是很多，对它的开发环境也不是非常了解，所以在程序的开发过程中遇到了很多的困难，但经过同学和老师的帮助，逐渐克服了困难，并从中学到了很多编程方面的知识。在这里我要感谢我的C语言，C++老师和算法老师。但是由于经验方面的原因，以及对学籍管理方面的操作流程了解不够深刻，该系统还有许多不尽如人意的地方和功能上的缺陷，这些都有待于进一步改善。 论文完成的前提是指导老师王旭阳老师给我提供了舒适的工作、学习环境，并给予我悉心的关怀与指导。在些表示衷心地感谢。老师认真负责的工作态度、严谨的治学风格，使我深受启发；开发的同时，和同学们之间的相互探讨也使我获益匪浅。几个月的时间内，我除基本学会开发C语言和C++语言应用程序外更重要的是学到了兢兢业业，奋发向上的精神，这种精神是我今后人生前进道路上的一种力量。所以我再次感谢我的老师和我周围的同学们。 29 附件Ⅰ 任务一源程序代码 #include //„„„„„„„„„„„„„„„„邻接矩阵定义„„„„„„„„ typedef struct ArcCell { int adj; char *info; }ArcCell,AdjMatrix[max][max]; typedef struct { char vexs[max]; AdjMatrix arcs; int vexnum,arcnum; }MGraph_L; //^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ int localvex(MGraph_L G,char v)//返回V的位置 { int i=0; while(G.vexs[i]!=v) ++i; 30 return i; } int creatMGraph_L(MGraph_L &G)//创建图用邻接矩阵表示 { char v1,v2; int i,j,w; cout<<\"„„„„创建无向图„„„„\"< cout<<\"输入顶点\"< for(i=0;i!=G.vexnum;++i) for(j=0;j!=G.vexnum;++j) { G.arcs[i][j].adj=int_max; G.arcs[i][j].info=NULL; } for(int k=0;k!=G.arcnum;++k) { cout<<\"输入一条边依附的顶点和权:(a b 3)不包括“()”\"< 31 cout<<\"图G邻接矩阵创建成功！\"< for(i=0;i!=G.vexnum;++i) { for(j=0;j!=G.vexnum;++j) cout< typedef struct arcnode//弧结点 { int adjvex;//该弧指向的顶点的位置 struct arcnode *nextarc;//弧尾相同的下一条弧 char *info;//该弧信息 }arcnode; typedef struct vnode//邻接链表顶点头接点 { char data;//结点信息 arcnode *firstarc;//指向第一条依附该结点的弧的指针 }vnode,adjlist; typedef struct//图的定义 { adjlist vertices[max]; int vexnum,arcnum; 32 int kind; }algraph; //„„„„„„„„„„„„„„„„队列定义„„„„„„„„ typedef struct qnode { int data; struct qnode *next; }qnode,*queueptr; typedef struct { queueptr front; queueptr rear; }linkqueue; //„„„„„„„„„„„„„„„„„„„„„„„„„„„ typedef struct acr { int pre;//弧的一结点 int bak;//弧另一结点 int weight;//弧的权 }edg; int creatadj(algraph &gra,MGraph_L G)//用邻接表存储图 { int i=0,j=0; arcnode *arc,*tem,*p; for(i=0;i!=G.vexnum;++i) { gra.vertices[i].data=G.vexs[i]; gra.vertices[i].firstarc=NULL; } 33 for(i=0;i!=G.vexnum;++i) { for(j=0;j!=G.vexnum;++j) { if(gra.vertices[i].firstarc==NULL) { if(G.arcs[i][j].adj!=int_max&&j!=G.vexnum) { arc=(arcnode *)malloc(sizeof(arcnode)); arc->adjvex=j; gra.vertices[i].firstarc=arc; arc->nextarc=NULL; p=arc; ++j; while(G.arcs[i][j].adj!=int_max&&j!=G.vexnum) { tem=(arcnode *)malloc(sizeof(arcnode)); tem->adjvex=j; gra.vertices[i].firstarc=tem; tem->nextarc=arc; arc=tem; ++j; } --j; } } else { if(G.arcs[i][j].adj!=int_max&&j!=G.vexnum) { 34 arc=(arcnode *)malloc(sizeof(arcnode)); arc->adjvex=j; p->nextarc=arc; arc->nextarc=NULL; p=arc; } } } } gra.vexnum=G.vexnum; gra.arcnum=G.arcnum; cout<<\"图G邻接表创建成功！\"< for(i=0;i!=gra.vexnum;++i) { arcnode *p; cout< cout< cout< int firstadjvex(algraph gra,vnode v)//返回依附顶点V的第一个点 //即以V为尾的第一个结点 { if(v.firstarc!=NULL) return v.firstarc->adjvex; } int nextadjvex(algraph gra,vnode v,int w)//返回依附顶点V的相对于W的下一个顶点 { arcnode *p; p=v.firstarc; while(p!=NULL&&p->adjvex!=w) { p=p->nextarc; } if(p->adjvex==w&&p->nextarc!=NULL) { p=p->nextarc; return p->adjvex; } if(p->adjvex==w&&p->nextarc==NULL) return -10; } int initqueue(linkqueue &q)//初始化队列 { q.rear=(queueptr)malloc(sizeof(qnode)); q.front=q.rear; if(!q.front) return 0; q.front->next=NULL; 36 return 1; } int enqueue(linkqueue &q,int e)//入队 { queueptr p; p=(queueptr)malloc(sizeof(qnode)); if(!p) return 0; p->data=e; p->next=NULL; q.rear->next=p; q.rear=p; return 1; } int dequeue(linkqueue &q,int &e)//出队 { queueptr p; if(q.front==q.rear) return 0; p=q.front->next; e=p->data; q.front->next=p->next; if(q.rear==p) q.rear=q.front; free(p); return 1; } int queueempty(linkqueue q)//判断队为空 { if(q.front==q.rear) return 1; 37 return 0; } void bfstra(algraph gra)//广度优先遍历 { int i,e; linkqueue q; for(i=0;i!=gra.vexnum;++i) visited[i]=0; initqueue(q); for(i=0;i!=gra.vexnum;++i) if(!visited[i]) { visited[i]=1; cout< for(we=firstadjvex(gra,gra.vertices[e]);we>=0;we=nextadjvex(gra,gra.vertices[e],we)) { if(!visited[we]) { visited[we]=1; cout< int dfs(algraph gra,int i) { visited[i]=1; int we1; cout< if(visited[we]==0) dfs(gra,we); we=we1; } return 1; } int dfstra(algraph gra) { int i,j; for(i=0;i!=gra.vexnum;++i) { visited[i]=0; } for(j=0;j!=gra.vexnum;++j) { if(visited[j]==0) dfs(gra,j); } return 0; } 39 int bfstra_fen(algraph gra)//求连通分量 { int i,j; for(i=0;i!=gra.vexnum;++i) visited[i]=0; for(j=0;j!=gra.vexnum;++j) { if(visited[j]==0) { dfs(gra,j); cout< int adjvex; int lowcost; }closedge; int prim(int g[][max],int n) //最小生成树PRIM算法 { int lowcost[max],prevex[max]; //LOWCOST[]存储当前集合U分别到剩余结点的最短路径 //prevex[]存储最短路径在U中的结点 int i,j,k,min; for(i=2;i<=n;i++) //n个顶点，n-1条边 { 40 lowcost[i]=g[1][i]; //初始化 prevex[i]=1; //顶点未加入到最小生成树中 } lowcost[1]=0; //标志顶点1加入U集合 for(i=2;i<=n;i++) //形成n-1条边的生成树 { min=inf; k=0; for(j=2;j<=n;j++) //寻找满足边的一个顶点在U,另一个顶点在V的最小边 if((lowcost[j] printf(\"(%d,%d)%d\\lowcost[k]=0; //顶点k加入U for(j=2;j<=n;j++) //修改由顶点k到其他顶点边的权值 if(g[k][j] printf(\"\\n\"); } return 0; } int acrvisited[100];//kruscal弧标记数组 int find(int acrvisited[],int f) { while(acrvisited[f]>0) 41 f=acrvisited[f]; return f; } void kruscal_arc(MGraph_L G,algraph gra) { edg edgs[20]; int i,j,k=0; for(i=0;i!=G.vexnum;++i) for(j=i;j!=G.vexnum;++j) { if(G.arcs[i][j].adj!=10000) { edgs[k].pre=i; edgs[k].bak=j; edgs[k].weight=G.arcs[i][j].adj; ++k; } } int x,y,m,n; int buf,edf; for(i=0;i!=gra.arcnum;++i) acrvisited[i]=0; for(j=0;j!=G.arcnum;++j) { m=10000; for(i=0;i!=G.arcnum;++i) { if(edgs[i].weight 42 x=edgs[i].pre; y=edgs[i].bak; n=i; } } buf=find(acrvisited,x); edf=find(acrvisited,y); edgs[n].weight=10000; if(buf!=edf) { acrvisited[buf]=edf; cout<<\"(\"< algraph gra; MGraph_L G; int i,d,g[20][20]; char a='a'; d=creatMGraph_L(G); creatadj(gra,G); vnode v; cout< cout<<\"„„„„„„„菜单„„„„„„„„\"< cout<<\"邻接矩阵显示如下：\"< for(i=0;i!=gra.vexnum;++i) { visited[i]=0; } cout<<\"深度优先遍历：\"; dfstra(gra); cout< } cout< 45 system(\"pause\"); return 0; } 46 因篇幅问题不能全部显示，请点此查看更多更全内容