数据结构课程设计论文.doc

辽宁工业大学课 程 设 计 说 明 书题目： 数据结构与算法课程设计 学院（系）： 理学院 专业班级： 计算092班 学 号： 090901036 学生姓名： 纪尚宸 指导教师： 佟玉军 教师职称： 副教授 起止时间： 2011.7.82011.7.13 课程设计（论文）任务及评语院（系）：电子与信息工程 教研室： 软件工程学 号090901036学生姓名纪尚宸专业班级计算092班课程设计（论文）题目数据结构与算法课程设计课程设计（论文）任务1从十个题目中选择一个题目,，要求每个题目用标准的C语言程序实现，另外,完成思考题一题，思考题须写出相应的类C算法即可。2每个题目编写源程序时，要求有主菜单,每个子功能定义为相应的子函数，在主函数中调用各子函数，程序结构清晰。3 根据题目,选择合适的逻辑结构和存储结构。4 输入的数据由键盘输入。5 分析算法的时间复杂度，要求算法的效率尽可能高。6 验证排序算法的稳定性。指导教师评语及成绩成绩： 指导教师签字： 2011年 7月15日 辽宁工业大学数据结构课程设计说明书（论文）目 录第一章 课程设计目的与要求-11.1课程设计目的- 11.2 课程设计的实验环境-11.3课程设计的预备知识- 11.4 课程设计要求-1第二章 课程设计内容-2 2.1 题目的选择-2 2.2 题目的具体实现-2 2.3 思考题解析 -15总结-16参考文献-171辽宁工业大学数据结构课程设计说明书（论文）第1章 课程设计目的与要求1.1 课程设计目的 本设计实践是 “C语言程序设计”课程学习的一个关键环节。它是根据教学计划的要求，在教师的指导下，对学生实施程序设计训练的必要过程，是对前期课堂学习内容的综合应用及其效果的检验和提高。其目的在于培养学生综合运用理论知识来分析和解决实际问题的能力、以及严谨的科学态度和良好的程序设计习惯。本次设计实践，要求设计者基于结构化程序设计思想和所用C语言开发环境与工具，并运用“软件工程”和“数据结构”中的有关概念和方法，针对具体设计题和要求，分析功能要求，划分功能模块，用链表结构设计功能模块函数，以菜单方式调用相应功能模块来实现信息和数据处理。1.2 课程设计的实验环境 WindowsXP，Microsoft Visual C+ 6.0。1.3 课程设计的预备知识 C语言程序设计、数据结构。1.4 课程设计要求（1）认真查找资料，分析每个题目应选择的数据结构（逻辑结构和物理结构）；（2）按时到实验室调试程序，遵守实验室的规章制度，爱护设备；（3）每个题目编写源程序时，每个子功能定义为相应的子函数，在主函数中调用各子函数，程序结构清晰，有必要的注释，可读性强。（4）程序健壮性强，当数据输入错误时，要进行相应的处理； （5）分析算法的时间复杂度，要求算法的效率尽可能高；（6）对于排序算法，要验证排序算法的稳定性。第2章 课程设计内容2.1题目的选择6、学生成绩管理系统2.2 题目的具体实现一题目应实现的具体功能；（1）录入学生成绩信息并保存； （2）可查询显示所有学生的个人信息； （3）可查询显示所有学生的所学课程信息；（4）按学号或姓名查询成绩信息； （5）能添加、删除和修改学生的成绩信息；二题目所选择的数据结构及存储结构采用链表来存储学生的姓名，性别成绩等。三完整的源程序#include #include #include #include #include #define MAX 80 void input(); void sort(); void display(); void insert(); void del(); void average(); void find(); void save(); void read(); void del_file(); void average(); void modify(); int now_no=0; struct student int no; char name20; char sex4; float score1; float score2; float score3; float sort; float ave; float sum; ; struct student stuMAX,*p; main()/*主函数*/ int as; start: printf(nttt欢迎使用学生成绩管理系统n); /*一下为功能选择模块*/ do printf(ntttt1.录入学生成绩信息并保存ntttt2.显示所有学生的信息ntttt3.成绩排序信息ntttt4.添加学生信息ntttt5.删除学生信息ntttt6.修改学生信息ntttt7.查询学生信息ntttt8.从文件读入学生信息ntttt9.删除文件中学生信息ntttt10.保存学生信息ntttt11.退出n); printf(tttt选择功能选项:); fflush(stdin); scanf(%d,&as); switch(as) case 1:system(cls);input();break; case 2:system(cls);display();break; case 3:system(cls);sort();break; case 4:system(cls);insert();break; case 5:system(cls);del();break; case 6:system(cls);modify();break; case 7:system(cls);find();break; case 8:system(cls);read();break; case 9:system(cls);del_file();break; case 10:system(cls);save();break; case 11:system(exit);exit(0); default:system(cls);goto start; while(1); /*至此功能选择结束*/ void input()/*原始数据录入模块*/ int i=0; char ch; do printf(tttt1.录入学员信息n输入第%d个学员的信息n,i+1); printf(n输入学生编号:); scanf(%d,&stui.no); fflush(stdin); printf(n输入学员姓名:); fflush(stdin); gets(); printf(n输入学员性别:); fflush(stdin); gets(stui.sex); printf(n输入学员成绩1:); fflush(stdin); scanf(%f,&stui.score1); printf(n输入学员成绩2:); fflush(stdin); scanf(%f,&stui.score2); printf(n输入学员成绩3:); fflush(stdin); scanf(%f,&stui.score3); printf(nn); i+; now_no=i; printf(是否继续输入?(Y/N); fflush(stdin); ch=getch(); system(cls); while(ch!=n&ch!=N); system(cls); void sort()/*排序数据函数*/ struct student temp; int i,j; average(); for(i=1;inow_no;i+) for(j=1;j=now_no-i;j+) if(stuj-1.avestuj.ave) temp=stuj; stuj=stuj-1; stuj-1=temp; void display()/*显示数据函数*/ int i; char as; average(); do printf(ttt班级学员信息列表n); printf(t编号t姓名t性别t成绩1t成绩2t成绩3t平均值n); for(i=0;inow_no&0;i+)printf(t%dt%st%st%.2ft%.2ft%.2ft%.2fn,stui.no,,stui.sex,stui.score1,stui.score2,stui.score3,stui.ave); printf(tt按任意键返回主菜单.); fflush(stdin); as=getch(); while(!as); system(cls); void insert()/*插入数据函数*/ char ch; do printf(ntt输入新插入学员队信息n); printf(n输入学生编号:); scanf(%d,&stunow_no.no); fflush(stdin); printf(n输入学员姓名:); fflush(stdin); gets(stunow_); printf(n输入学员性别:); fflush(stdin); gets(stunow_no.sex); printf(n输入学员成绩1:); fflush(stdin); scanf(%f,&stunow_no.score1); printf(n输入学员成绩2:); fflush(stdin); scanf(%f,&stunow_no.score2); printf(n输入学员成绩3:); fflush(stdin); scanf(%f,&stunow_no.score3); printf(nn); now_no=now_no+1; sort(); printf(是否继续输入?(Y/N); fflush(stdin); ch=getch(); system(cls); while(ch!=n&ch!=N); void del()/*删除数据函数*/ int inum,i,j; printf(输入要删除学员的编号:); fflush(stdin); scanf(%d,&inum); for(i=0;inow_no;i+) if(stui.no=inum) if(i=now_no)now_no-=1; else stui=stunow_no-1; now_no-=1; sort(); break; system(cls); void save()/*保存数据函数*/ FILE *fp; int i; char filepath20; printf(输入要保存的文件路径:); fflush(stdin); gets(filepath); if(fp=fopen(filepath,w)=NULL) printf(n保存失败!); exit(0); for(i=0;inow_no;i+) stui.sum=stui.score1+stui.score2+stui.score3; stui.ave=stui.sum/3; fprintf(fp,t%dt%st%st%.2ft%.2ft%.2ft%.2fn,stui.no,,stui.sex,stui.score1,stui.score2,stui.score3,stui.ave); fclose(fp); printf(学生信息已保存在%s中!n,filepath); system(pause); system(cls); void find()/*查询函数*/ int i; char str20,as; do printf(输入要查询的学生姓名:); fflush(stdin); gets(str); for(i=0;inow_no;i+) if(!strcmp(,str) printf(t编号t姓名t性别t成绩1t成绩2t成绩3t平均值n); printf(t%dt%st%st%.2ft%.2ft%.2ft%.2fn,stui.no,,stui.sex,stui.score1,stui.score2,stui.score3,stui.ave); printf(tt按任意键返回主菜单.); fflush(stdin); as=getch(); while(!as); system(cls); void average()/*求平均数*/ int i; for(i=0;inow_no;i+) stui.sum=stui.score1+stui.score2+stui.score3; stui.ave=stui.sum/3; void modify()/*修改数据函数*/ int i; char str20,as; printf(输入要修改的学生姓名:); fflush(stdin); gets(str); for(i=0;inow_no;i+) if(!strcmp(,str) system(cls); printf(ntt输入新插入学员队信息n); printf(n输入学生编号:); fflush(stdin); scanf(%d,&stui.no); printf(n输入学员性别:); fflush(stdin); gets(stui.sex); printf(n输入学员成绩1:); fflush(stdin); scanf(%f,&stui.score1); printf(n输入学员成绩2:); fflush(stdin); scanf(%f,&stui.score2); printf(n输入学员成绩3:); fflush(stdin); scanf(%f,&stui.score3); printf(nn); sort(); break; system(cls); void read() FILE *fp; int i; char filepath20; printf(输入要读入的文件路径:); fflush(stdin); gets(filepath); if(fp=fopen(filepath,r)=NULL) printf(找不到%s文件!n,filepath); system(pause); exit(0); now_no=0; for(i=0;iMAX&!feof(fp);i+) fscanf(fp,t%dt%st%st%ft%ft%ft%fn,&stui.no,,stui.sex,&stui.score1,&stui.score2,&stui.score3,&stui.ave); now_no+; fclose(fp); printf(保存的在文件%s中的所有信息已经读入!n,filepath); system(pause); system(cls); void del_file() FILE *fp; char filepath20; printf(输入要删除的文件路径:); fflush(stdin); gets(filepath); fp=fopen(filepath,w); fclose(fp); printf(保存的在文件%s中的所有信息已经删除!n,filepath); system(pause); system(cls); 四程序的输入和输出菜单界面输入两个学生信息：插入一个新的学生信息：显示所有学生信息：查询学生信息：删除及修改学生信息：（确定删除后将自动返回主界面）修改时输入学生的姓名：修改学生的信息：退出：五调试中的问题及解决：1)结构体的存储取第一次输入时使用的是fprintf和fread，在读取后存入的过程中，程序出现了数据溢出后强制跳出的现象。后经过调试及查阅相关资料发现bug的原因是fprintf和fread不配套，后将fread改为fscanf后程序运行正常。2) 编程时要注意细节，比如说链表末尾的指针要为NULL，如果以写的方式打开一个文件，不做写入数据操作，原文件里的信息将被删除。对于函数要考虑输入参数的各种取值情况。调试时要有耐心，当输出和期望的不同时，仔细分析程序的运行过程，通过在原程序中加入一些辅助显示函数，找出出错的地方。2.3 思考题解析所选的思考题：编写一个算法，构造一棵哈夫曼树，并求出其带权路径长度。要求： 对其进行解答，写出类C算法即可。程序如下： HUFFMAN(hufmtree tree)int i,j,p1,p2;float small1,small2,f;for(i=0;im;i+)treei.parent=0; treei.lchild=0; treei.rchild=0; treei.weught=0;for(i=0;in;i+)scanf(%f,&f); treei.weight=f;for(i=n;im;i+)p1=0;p2=0; small1=maxval;small2=maxval;for(j=0;ji