《数据结构》课程设计报告-目录及正文.doc

四号黑体，固定值22磅，段前段后0行页边距设置：上2.5cm，下2.5 cm，左2.5 cm，右2.5 cm；装订线0.5 cm，装订位置为左边；页眉1.7 cm，页脚2.0 cm。页脚设置为：插入页码，居中。三号黑体，居中，固定值22磅，段前段后1行。目 录1 问题描述1四号宋体，左缩进2字符，固定值22磅，段前段后0行2 需求分析13 概要设计131抽象数据类型定义132模块划分24 详细设计341数据类型的定义342主要模块的算法描述35 测试分析56 课程设计总结6参考文献6附录（源程序清单）71 问题描述设计一个简单学生宿舍系统程序，可以输入记录并建立数据文件，数据文件按关键字（姓名、学号、房号）进行排序(冒泡、选择、插入排序等任选一种),能够显示记录,可以查找记录，用折半查找法实现按姓名、学号、房号查询,能够打印任一查询结果,可以删除记录,能够实现连续操作。2 需求分析1. 程序采用交互工作方式，也就是说要有一个人性化的操作界面。将每一种操作赋给一个数字，通过输入不同的数字来实现不同的操作。这样这样使人一看就能明白怎样实现不同的操作。全使用 提示选择方式，只需要输入你要使用方式的代号即可。2. 系统本无任何信息数据，要建立数据文件，需开发一个信息录入功能，即首先创建一个学员线性表，同时我们可以将数据暂时保存在内存中。 3. 录入或修改：录入或修改某学生的住宿信息；建立相应的录入和修改函数，然后在主函数中调用，从而实现录入或修改某学生的住宿信息。 4. 排序和查询：本系统按关键字（姓名、学号、房号）进行冒泡排序，采用二分查找方式分别实现按关键字（姓名、学号、房号）查询功能；对不同的关键字建立不同的函数，在函数中调用，通过调用不同的函数来实现不同关键字的查询。统计纪录中的所有纪录的个数，当添加一个纪录时加一，当删除一个纪录时减一。然后在主函数中打印出来，从而实现纪录数据的统计。 5. 另外，为了完善系统，我们又添加了删除功能和退出功能。3 概要设计31定义了一个结构体来储存学生信息：typedef struct char S_name31; /学生姓名 char S_number16; /学生学号char sex8; /性别 int D_number; /学生所在寝室的宿舍号 int Total; /学生总数 StudentM,St;3. 2本程序所包含的16 个函数为： （1）主函数main(); （2）菜单函数Menu(); （3）判断学号是否重复函数S_number_Judge(Student S,int t); （4）添加学生信息函数Add(Student S); （5）修改学生信息函数Alter(Student S); （6）删除学生信息函数Delete(Student S); （7）显示所有学生信息函数Display_All(Student S); （8）按照寝室号从小到大排序函数Sort_D_number(Student S);（9）.按姓名从小到大排序函数Sort_S_name(Student S)（10）按照学号从小到大排序函数Sort_S_number(Student S); （11）根据学生姓名查找函数Query_S_name(Student S); （12）根据学生学号查找函数Query_S_number(Student S); （13）根据寝室号查找函数Query_D_number(Student S) （14）存储函数Save(Student S); （15）加载函数Load(Student S); （16）判断在退出程序时是否保存函数Judge_Save(int i,Student S);3. 3函数间关系： 利用主函数调用其他的各个函数。添加数据纪录函数Add()，删除数据信息函数 Delete ()，修改函数Alter ()这些函数都是在同一等级上的函数，是平行关系。按宿舍号，姓名，学号排序函数 Sort_D_number (),Sort_S_name (),Sort_S_numbe ()；这些函数都是排序函数中的子函数，他们之间是平行的关系。按宿舍号，姓名，学号查询函数 Query_D_number（），Query_S_name（）, Query_D_number（）,是查询函数的子函数，他们之间是平行关系。 4 详细设计41数据类型的定义（1）迷宫类型#define M 6#define N 8int mazeM+2N+2;（2）栈类型（3）队列类型42主要模块的算法描述（给出主要模块的算法描述,用流程图或伪代码表示，若用流程图表示，请注意：图与表以章节组编号。如“图4.1 创建交通图算法流程图”表示第4章（第4部分）的第1幅图。图与表应有相应的标题名称，图的标题置于图的下方居中，表的标题名称置于表的上方居中；编号与图表名称之间空一个字的位置，如“图2.1 实验系统流程示意图”。图、表的标题用五号宋体字居中，表格内容用五号宋体字。）该题主要分为两步：（1）利用栈实现迷宫求解；（2）利用队列实现迷宫求解。该题由我和XX同学合作完成，我主要负责：（1）利用栈实现迷宫求解。（1）主函数void main()int x,mazeM+2N+2=1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,0,1,0,0,0,0,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,0,0,1,1,0,0,0,1,1,0,1,1,0,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1; /*构造一个迷宫*/item move8=0,1,1,1,1,0,1,-1,0,-1,-1,-1,-1,0,-1,1; /*坐标增量数组move的初始化*/while(1)printf(1 迷宫求解（采用栈实现）n2 迷宫求解（采用队列实现）n3 退出n);（2）利用栈实现迷宫求解算法的伪码描述如下：int mazepath_stack(int mazeM+2N+2,item move8)/*若迷宫maze中存在从入口(1,1)到出口(M,N)的通道，则求得一条存放在栈中，并返回1；否则返回0*/ 栈初始化； 将入口点坐标及到达该点的方向（设为-1）入栈； while（栈不空） 栈顶元素出栈； 求出下一个要试探的方向d+； while（还有剩余试探方向） if（d方向可走） 则 （x，y，d）入栈； 求新点坐标（i，j）； 将新点（i，j）切换为当前点（x，y）； if （点（x，y）为出口点）结束； else 重置d=0； else d+； （3）栈的操作void InitStack(SqStack *s) /*栈的初始化*/ int StackEmpty(SqStack s) /*判栈空*/ 另一个同学的报告中4.2就为：该题主要分为两步：（1）利用栈实现迷宫求解；（2）利用队列实现迷宫求解。该题由我和XX同学合作完成，我主要负责：（2）利用队列实现迷宫求解。（1）主函数void main()int x,mazeM+2N+2=1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,0,1,0,0,0,0,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,0,0,1,1,0,0,0,1,1,0,1,1,0,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1; /*构造一个迷宫*/item move8=0,1,1,1,1,0,1,-1,0,-1,-1,-1,-1,0,-1,1; /*坐标增量数组move的初始化*/while(1)printf(1 迷宫求解（采用栈实现）n2 迷宫求解（采用队列实现）n3 退出n);（2）利用队列实现迷宫求解void printpath(SqQueue q) /*输出迷宫路径*/ int mazepath_queue(int mazeM+2N+2,item move8)/*采用队列的迷宫算法。MazeM+2N+2表示迷宫数组，move8表示坐标增量数组*/ （3）队列的操作void InitQueue(SqQueue *q) /*队列的初始化*/ int QueueEmpty(SqQueue q) /*判队空*/ 5 测试分析主界面菜单如下：对添加信息功能的实现：显示学生信息：按姓名查询：按学号查询：按宿舍号查询：按寝室号从小到大排序：按学号大小排序：按姓名排序：退出系统：根据测试分析要将程序的各个模块组合在一起实现，要用到switch()语句。这样能使程序更加完整完善。排序时都使用的是冒泡排序法。这种方法比较繁琐。时间复杂度为O(n)。在按姓名查找时使用了顺序查找，但如果有重名现象就不能准确的找出学生的信息。按学号和宿舍号查找时使用了折半查找。查找前必须先对其排序，因为折半查找是对有序表的查找。6 课程设计总结课程设计已经结束了，总体来讲做得还不错.通过这次课程设计使我充分的理解了管理系统基本原理，在这次的课程设计中不仅检验了我所学习的知识，也培养了我如何去把握一件事情，如何去做一件事情，又如何完成一件事情。在设计过程中，遇到不懂的就和同学们探讨，学习。学会了运筹帷幄，学会了宽容，学会了理解，也学会了做人与处世。课程设计是我们专业课程知识综合应用的实践训练，着是我们迈向社会，从事职业工作前一个必不少的过程”千里之行始于足下”，通过这次课程设计，我深深体会到这句千古名言的真正含义我今天认真的进行课程设计，学会脚踏实地迈开这一步，就是为明天能稳健地在社会大潮中奔跑打下坚实的基础通过这次设计，本人在多方面都有所提高。通过这次实际训练从而培养和提高学生独立工作能力，巩固与扩充了数据结构等课程所学的内容，同时各科相关的课程都有了全面的复习，独立思考的能力也有了提高。体会了学以致用、突出自己劳动成果的喜悦心情，从中发现自己平时学习的不足和薄弱环节，从而加以弥补。在此感谢我们的数据结构老师黄同城以及课程设计老师黄磊.，老师严谨细致、一丝不苟的作风一直是我工作、学习中的榜样；老师循循善诱的教导和不拘一格的思路给予我无尽的启迪都离不开老师您的细心指导。而您开朗的个性和宽容的态度，帮助我能够很顺利的完成了这次课程设计。同时感谢对我帮助过的同学们，谢谢你们对我的帮助和支持，让我感受到同学的友谊。 由于设计能力有限，在设计过程中难免出现错误，恳请老师们多多指教,我十分乐意接受你们的批评与指正，将万分感谢。参考文献1 黄同成，黄俊民，董建寅数据结构M北京：中国电力出版社，20082 董建寅，黄俊民，黄同成数据结构实验指导与题解M北京：中国电力出版社，20083 严蔚敏，吴伟民. 数据结构（C语言版）M. 北京：清华大学出版社，20024 刘振鹏，张晓莉，郝杰数据结构M北京：中国铁道出版社，2003附录（源程序清单）#include#include#include#define M 100 int dirty=0; /用来判断是否已保存操作 /定义一个存储学生相关信息的结构体 typedef struct char S_name31; /学生姓名 char S_number16; /学生学号 char S_sex15;/学生性别 int D_number; /学生所在寝室的宿舍号 int Total; /学生总数 StudentM,St;void Menu();void Sort_S_number(S);/判断学号是否与表中所存学号重复 void S_number_Judge(Student S,int t) int i; for(i=1;iTotal)-1;i+) while(strcmp(Si.S_number,St.S_number)=0) printf(学号输入失败,该学号已存在,请重新输入学号!n); printf(请输入学生的学号(15个字符以内):); scanf(%s,St.S_number); getchar(); i=1; /添加学生信息函数 void Add(Student S) char ch;printf(请输入学生的学号(15个字符以内):); scanf(%s,SS-Total.S_number); getchar();printf(请输入学生姓名(30个字符以内):); scanf(%s,S+(S-Total).S_name); getchar(); printf(请输入学生的性别：); scanf(%s,SS-Total.S_sex); S_number_Judge(S,S-Total);/判断输入的学号是否与表中所存在的学号重复 printf(请输入宿舍号码:); scanf(%d,&SS-Total.D_number); getchar(); dirty=1; printf(添加成功!nn); printf(是否继续添加学生信息？请输入N(n)或者Y(y):); ch=getchar(); if(ch=y|ch=Y) Add(S); else Menu(); /修改学生信息函数 void Alter(Student S) int i; int flag=0; /用来判断表中是否存在所要修改的学生的信息 char name20; printf(请输入你要修改学生的姓名:); scanf(%s,name); getchar(); for(i=1;iTotal;i+) if(strcmp(Si.S_name,name)=0) flag=i; if(!flag) printf(你所要修改的学生信息在表中不存在！n); else printf(新信息如下:n); printf(请输入学生姓名(30个字符以内):); scanf(%s,Sflag.S_name); getchar(); printf(请输入学生的学号(15个字符以内):); scanf(%s,Sflag.S_number); getchar(); S_number_Judge(S,flag); printf(请输入学生的性别:); scanf(%s,Sflag.S_sex); printf(请输入宿舍号:); scanf(%d,&Sflag.D_number); getchar(); dirty=1; printf(修改成功!n); putchar(n); /删除学生信息 void Delete(Student S) int i,j; int flag=0; /用来判断表中是否存在所要删除的学生的信息 char name20; printf(请输入你要删除学生的姓名:); scanf(%s,name); getchar(); for(i=1;iTotal;i+) if(strcmp(Si.S_name,name)=0) flag=i; if(!flag) printf(你所要删除的学生在表中不存在！); else for(i=flag;iTotal;i+) j=i+1; strcpy(Si.S_name,Sj.S_name); strcpy(Si.S_number,Sj.S_number); Si.D_number=Sj.D_number; (S-Total)-; dirty=1; printf(删除成功!); printf(nn); /显示所有学生信息函数 void Display_All(Student S) int i; printf(nn);printf(nn);printf(全体学生信息如下:n); printf(n);printf(学生姓名 学生学号 学生性别 宿舍号n); for(i=1;iTotal;i+) printf( %s %s %s %dn,Si.S_name,Si.S_number,Si.S_sex,Si.D_number); printf(nn); /按姓名排序（冒泡法）void Sort_S_name(Student S) int i,j,t; char name30; char number15; for(i=1;iTotal;i+) for(j=i;jTotal;j+) if(strcmp(Si.S_name,Sj.S_name)0) strcpy(name,Si.S_name); strcpy(number,Si.S_number); t=Si.D_number; strcpy(Si.S_name,Sj.S_name);strcpy(Si.S_number,Sj.S_number); Si.D_number=Sj.D_number; strcpy(Sj.S_name,name); strcpy(Sj.S_number,number); Sj.D_number=t; printf(nn);/排序函数按照寝室号从小到大排序(冒泡法) void Sort_D_number(Student S) int i,j, t;char name30; char number15;for(i=1;iTotal;i+) for(j=i;jTotal;j+) if(Si.D_numberSj.D_number) strcpy(name,Si.S_name); strcpy(number,Si.S_number); t=Si.D_number; strcpy(Si.S_name,Sj.S_name); strcpy(Si.S_number,Sj.S_number); Si.D_number=Sj.D_number; strcpy(Sj.S_name,name); strcpy(Sj.S_number,number); Sj.D_number=t; /排序函数按照学号从小到大排序(冒泡法) void Sort_S_number(Student S) int i,j,t; char name30; char number15; for(i=1;iTotal;i+) for(j=i;jTotal;j+) if(strcmp(Si.S_number,Sj.S_number)0) strcpy(name,Si.S_name); strcpy(number,Si.S_number); t=Si.D_number; strcpy(Si.S_name,Sj.S_name);strcpy(Si.S_number,Sj.S_number); Si.D_number=Sj.D_number; strcpy(Sj.S_name,name); strcpy(Sj.S_number,number); Sj.D_number=t; printf(nn);/查询函数以姓名为关键字进行查询(顺序查找) void Query_S_name(Student S) int i,j=0; char name31; printf(请输入你要查找的学生的姓名(30个字符以内):); scanf(%s,name); getchar(); printf(n所查找学生信息如下:n); printf(学生姓名 学生学号 性别 宿舍号n); for(i=1;iTotal;i+) if(strcmp(name,Si.S_name)=0) printf(%s %s %s %dn,Si.S_name,Si.S_number,Si.S_sex,Si.D_number); j=1; if(!j) printf(n查找失败,表中不存在该学生的信息!nn); printf(nn); /查询函数以学号为关键字进行查询(折半查找) void Query_S_number(Student S) int j,high,low,mid; char number15; j=0; low=1; high=S-Total; printf(请输入你要查找学生的学号:); scanf(%s,number); Sort_S_number(S); /将表中原数据按照学号从小到大排序 printf(n所查找学生信息如下:n); printf(学生姓名 学生学号 性别 宿舍号n); if(strcmp(number,S1.S_number)=0&strcmp(number,SS-Total.S_number)=0) while(low0) low=mid+1; else high=mid-1; if(!j) printf(n查找失败,表中不存在该学生的信息!nn); printf(nn); /查询函数以寝室号为关键字进行查询(折半查找) void Query_D_number(Student S) int i,j,m,n,low,high,mid; j=0; low=1; high=S-Total; printf(请输入你要查询的寝室号:); scanf(%d,&i); getchar(); Sort_D_number(S);/将表中原数据按照寝室号从小到大排序 printf(n所查找寝室信息如下:n); printf(学生姓名 学生学号 性别 宿舍号n); if(i=S1.D_number&iTotal.D_number) while(lowS-Total) break; if(n0) while(Sn.D_number=i) printf(%s %s %S %dn,Sn.S_name,Sn.S_number,Sn.S_sex,Sn.D_number); n-; if(nSmid.D_number) low=mid+1; else high=mid-1; if(!j) printf(n查找失败,表中不存在该寝室的信息!nn); printf(nn);/存储函数 void Save(Student S) St Std;FILE *fp; int i; int flag1=0,flag2=0; if(fp=fopen(宿舍学生信息记录.txt,w)=NULL) /判断存储是否成功 printf(打开文件失败!nn); flag1=1; exit(0); /结束程序 for(i=1;iTotal;i+) if(fwrite(&Si,sizeof(Std),1,fp)!=1) printf(数据写入错误nn); flag2=1; exit(0); if(!flag1&!flag2) printf(数据存储成功!nn); dirty=0; fclose(fp); /加载记录函数 void Load(Student S) St Std; FILE *fp; if(fp=fopen(宿舍学生信息记录.txt,r)=NULL) printf(打开文件失败!nn); exit(0); while(!feof(fp) fread(&S+(S-Total),sizeof(Std),1,fp); fclose(fp); printf(加载数据成功！nn); (S-Total)-; /由于读取问题，表中个数要减去 /退出程序时判断是否保存函数 void Judge_Save(int i,Student S) char ch; if(i) printf(表中数据已改变，是否保存后再退出(Y/N)?:); ch=getchar(); getchar(); while(ch!=n&ch!=N&ch!=y&ch!=Y) printf(请输入N(n)或者Y(y):); ch=getchar(); getchar(); if(ch=y|ch=Y)