哈夫曼、课程设计ok

课 程 设 计 报 告课程名称 数据结构 课题名称 1.huffman编码 2.班级成绩管理系统 专 业 网络工程 班 级 学 号 姓 名 指导教师 刘铁武 郭芳 邓作杰 2014年 6月15 日 湖南工程学院课 程 设 计 任 务 书课程设计旨在达到以下目标：强化学生编码、调试错误的能力。了解和掌握软件开发流程和项目管理控制。了解当前IT行业及职业人应具备的素质。完全模拟真实软件开发流程和管理，增强团队意识和团队合作精神一 设计内容：问题2：huffman编码对于确定的字符集的电文字符串编码，实现最高的通信效率。编程实现对于给定的输入串及各字符的已知频度，输出其编码方式（各字符的二进制编码）及对应的输出流。测试数据： 字符ABCDEFGHIJKLM频度18664132232103211547571232字符NOPQRSTUVWXYZ频度20576315148518023818116问题3：成绩管理编制一应用软件实现对班级成绩管理。基本功能有学生信息的增删（转入或退学）、查找（从当前点向前或向后双向的）、录入、统计（如总分，及格率等）。建议用双链表实现。二 设计要求：a) 界面友好用户的一些操作前后做出一些必要的提示或确认。所有完成的功能都需要友好，例如：增加失败提示；删除失败和成功提示、删除前的确认；修改失败和成功提示、修改前/后的确认；查找失败提示、查找成功的确认；退出系统时，如果有修改要提示是否保存；其它方面的界面问题；b) 结构清晰： 模块化：对界面（显示）、菜单管理、逻辑管理、文件操作等等代码要独立，必须多个.c文件，用makefile； 封装：一个函数只做一件事，函数功能要单一；一个函数不能超过50行；避免重复、冗余代码； 代码块清晰。c)变量命名规范，变量名应该具有自明性： 常量，枚举和宏定义命名常量名,宏和枚举值由全大写字母组成，单词间通过下划线来界定； 函数的命名：使用动词或者动词名词（动宾词组）的形式，由一个或多个单词组成且以小写字母开头，以后每个单词之间用下划线隔开 变量的命名与定义应当使用名词或者形容词名词，由一个或多个单词组成且以小写字母开头，以后每个单词之间用下划线隔开。d) 注释充分：变量、函数（包括参数、返回值）、代码功能块、一些复杂算法等都需要清晰明了地说明；三其它要求：1选题：每位学生需完成两个课题，其中一个必选，另一个自选，必选题次为，学号/7+1。2课程设计报告内容说明1)需求分析 程序的功能；输入输出的要求。2)概要设计 程序的模块构成以及模块之间的层次结构、各模块的调用关系；每个模块的功能；课题涉及的数据结构和数据库结构；即要存储什么数据，这些数据是什么样的结构，它们之间有什么关系等。3)详细设计 采用C语言定义相关的数据类型；写出各模块的类C码算法；画出各函数的调用关系图、主要函数的流程图。4)调试分析以及设计体会 测试数据：准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果；程序调试中遇到的问题以及解决问题的方法；课程设计过程经验教训、心得体会。5)使用说明 用户使用手册：说明如何使用你编写的程序，详细列出每一步的操作步骤。6)书写格式 见附带说明。7)附录 参考书目； 源程序清单（带注释）3成绩评定：指导老师负责验收程序的运行结果，并结合学生的工作态度、实际动手能力、创新精神和设计报告等进行综合考评，并按优秀、良好、中等、及格和不及格五个等级给出每位同学的课程设计成绩。具体考核标准包含以下几个部分： 平时出勤 （占10%） 系统需求分析、功能设计、数据结构设计及程序总体结构合理与否（占10%） 程序能否完整、准确地运行，个人能否独立、熟练地调试程序（占40%） 设计报告（占30%）注意：不得抄袭他人的报告（或给他人抄袭），一旦发现，成绩为零分。 独立完成情况（占10%）。三进度安排第 17周星期一星期二星期三星期四星期五上午8：0012：00下午14：0017：00第 周星期一星期二星期三星期四星期五上午8：0012：00下午14：0017：00附：课程设计报告装订顺序：封面、任务书、目录、正文、评分、附件（A4大小的图纸及程序清单）。 正文的格式:一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距为22。正文的内容:一、课题的主要功能；二、课题的功能模块的划分（要求画出模块图）；三、主要功能的实现（至少要有一个主要模块的流程图）；四、程序调试；五、总结；六、附件（所有程序的原代码，要求对程序写出必要的注释）。正文总字数要求在5000字以上（不含程序原代码）。目录1课题名称 1-1问题描述71-2概要设计71-3详细设计81-4调试分析91-5心得体会111-6附录122课题名称2-1问题描述182-2概要设计182-3详细设计192-4调试分析242-5心得体会272-6附录283参考文献1.1问题描述 huffman编码对于确定的字符集的电文字符串编码，实现最高的通信效率。编程实现对于给定的输入串及各字符的已知频度，输出其编码方式（各字符的二进制编码）及对应的输出流。测试数据： 字符ABCDEFGHIJKLM频度18664132232103211547571232字符NOPQRSTUVWXYZ频度205763151485180238181161-2概要设计 1-2.1 程序模块及其关系主函数模块编码模块译码模块输入字符串生成哈夫曼编码输入代码串译码并输出程序由主函数模块，编码模块，译码模块组成，主函数模块可调用编码模块，译码模块，编码模块可对字符串进行编码，译码模块可对输入的代码串进行译码并输出。各模块之间的关系示意图如下：1-3详细设计各模块的C算法1. 编码模块：首先通过键盘输入需要键盘的字符串，调用void huffmantree()函数储存字符频度，再调用函数：void huffmantree() /构造哈弗曼树int i,j,k,lnode,rnode;double min1,min2; /分别存放lnode和rnode的两个结点位置 使所有结点的相关域置-1for(i=0;i60;i+) listi.parent=listi.lchild=listi.rchild=-1; for(i=0;i26;i+) listi.weight=fnumi; for(i=0;i26;i+) x1=x2=0; m1=m2=maxvalue; for(j=0;j26+i;j+) if(listj.weightm1&listj.parent=-1) x2=x1; m2=m1; x1=j; m1=listj.weight; else if(listj.weightm2&listj.parent=-1) x2=j; m2=listj.weight; list26+i.lchild=x1; list26+i.rchild=x2; listx1.parent=listx2.parent=26+i; list26+i.weight=listx1.weight+listx2.weight; 2.译码模块先通过键盘输入哈夫曼编码代码串， for(i=0;ilen;i+) / 译码 for(j=0;j26;j+) flag=1; / 判断输入是否合法 for(k1=i,k2=0;k1=i+letterj.len-1&strk1!=0;k1+,k2+) 如果找到对应编码 if(strk1!=letterj.sk2) flag=0; break; if(flag) printf(%c,letterj.c); i+=(letterj.len-1); break; 3.界面设计 int i,j; int ch,len; char str1000; int k1,k2,flag; printf(-huffman 编码译码器-n); printf(n 测试数据（频度）如下所示 ：nA-186tB-64tC-13tD-22tE-32tF-103tG-21tH-15tI-47tJ-57nK-1tL-2tM-32tN-20tO-57tP-63tQ-15tR-1tS-48nT-51tU-80tV-23tW-8tX-18tY-1tZ-16nn); printf(-nn); init(); huffmantree(); printf(n 输入1时执行编码tt); printf( 输入2时执行译码nn); printf( 请选择 ： );1-4调试分析 a）数据测试：b）输入字符串编译的结果如下所示：c）输入01代码译码结果如下所示：d）程序调试过程中遇到的问题;编写完译码函数后进行调试，程序会在译码过程中进入死循环，且无法译出正确字符串。经过仔细观察，发现程序中有一个循环的终止条件本应为stri!=0，却将其误写成了stri!=n,因而无法正常终止循环并译码，改正后实现了译码功能。1-5设计体会 当时拿到这个题目，完全懵了，感觉难度好大。哈夫曼树是怎么一回事，功能是什么我该从何下手。刚开始就花了很多时间通过看课本，上网查询资料去好好理解了下哈夫曼树的含义。此次课程设计，我编写程序的时候遇到了不少问题，在解决这些问题，最终实现课题任务的过程中，我学到了很多东西：首先，在拿到课题之前，要理解课程设计的要求，有哪些要求我们应该要做到的。我在此次课程设计刚开始就没看懂课题的要求，我应该完成怎样的功能。通过查找资料，参考网上的设计流程，这个问题在网上找到了答案。写完刚运行的时候出现了很多问题，尤其内存无法read，通过跟同学的交流请教，逐渐明白过来，然后经过很多次的修改才顺利运行。 就一般情况而言，课程设计要比教学实验复杂一些，设计的知识侧面更深，更广，而且更加实用。通过这次课程设计，培养了我们分析，解决实际问题和编程等动手能力，最终也通过这个方式帮助我们掌握数据结构这门课程。我更加深入了理解了哈夫曼编码的过程，以及利用哈夫曼编码对数据进行压缩的优越性，并且使我能够更熟练地运用树形的数据结构。我也明白了理论与实际结合的重要性，并提高了自己组织数据及编写大型程序的能力和思维方式，培养了基本的，良好的程序设计技能以及合作能力。通过对各个流程的控制，逐渐让我产生了兴趣，在实际编写过程中，和同学们互相讨论让我学到的不仅仅是一些解决问题的方法，我想更是解决问题的思想。课程设计本身也是一种互相学习的过程。从中体会到了在学习中，要严格要求自己，不能因为一点点的成功就骄傲自满，停止不前。我们在实践过程中，遇到问题的时候，我们要能静下来，好好的思考。1-6附录 源代码#include #include #include #define maxvalue 10000 struct cam1 / 哈夫曼编码结构 char c; char s50; / 存储哈夫曼编码 int len; letter30; struct cam2 / huffman 树结构 int weight; /存储权值 int parent,lchild,rchild; /双亲结点位置，左右孩子结点位置list60; void init() int i; for(i=0;i26;i+) letteri.c=A+i; void huffmantree() int i,j; int x1,x2; int m1,m2; /分别存放lnode和rnode的两个结点位置 int fnum26=186,64,13,22,32,103,21,15,47,57,1,2,32,20,57,63,15,1,48,51,80,23,8,18,1,16; /26个字母的频度 for(i=0;i60;i+) listi.parent=listi.lchild=listi.rchild=-1; / 使所有结点的相关域置-1 for(i=0;i26;i+) listi.weight=fnumi; for(i=0;i26;i+) x1=x2=0; m1=m2=maxvalue; /定义最大权值 for(j=0;j26+i;j+) if(listj.weightm1&listj.parent=-1) x2=x1; m2=m1; x1=j; m1=listj.weight; else if(listj.weightm2&listj.parent=-1) x2=j; m2=listj.weight; list26+i.lchild=x1; list26+i.rchild=x2; listx1.parent=listx2.parent=26+i; list26+i.weight=listx1.weight+listx2.weight; void huffmanbianma() / huffman 编码函数 int i,j,start; /字符数组中哈夫曼编码的起始位置 char s100; int p,c,k; int m=1; for(i=0;i26;i+) memset(s,0,sizeof(s); /数组s的初始化为0 start=40; c=i; p=listc.parent; while(p!=-1) if(listp.lchild=c) /如果左子树等于父亲结点则置为0 sstart=0; else sstart=1; start-; c=p; p=listc.parent; for(k=0,j=start+1;j=40;k+,j+) letteri.sk=sj; letteri.sk=0; letteri.len=k; printf( 26个字母的哈夫曼编码如下：n); for(i=0;i %stt,A+i,letteri.s); else printf( %c- %sn,A+i,letteri.s); printf(n); int main() int i,j; int ch,len; char str1000; int k1,k2,flag; printf(-huffman 编码译码器-n); printf(n 测试数据（频度）如下所示 ：nA-186tB-64tC-13tD-22tE-32tF-103tG-21tH-15tI-47tJ-57nK-1tL-2tM-32tN-20tO-57tP-63tQ-15tR-1tS-48nT-51tU-80tV-23tW-8tX-18tY-1tZ-16nn); printf(-nn); init(); huffmantree(); printf(n 输入1时执行编码tt); printf( 输入2时执行译码nn); printf( 请选择 ： ); scanf(%d,&ch); switch(ch) case 1: huffmanbianma(); printf( 请输入一段将要编译的字符串(大写)n); scanf( %s,str); len=strlen(str); for(i=0;ilen;i+) printf( %s,letterstri-A.s); printf(n); printf( 编码结束n); case 2: printf( 请输入一段01代码n); scanf( %s,str); /计算字符串str长度 len=strlen(str); for(i=0;ilen;i+) / 译码 for(j=0;j26;j+) flag=1; for(k1=i,k2=0;k1=i+letterj.len-1&strk1!=0;k1+,k2+) / 寻找对应编码 if(strk1!=letterj.sk2) flag=0; break; if(flag) /flag为1则哈弗曼编码输入合法 printf(%c,letterj.c); i+=(letterj.len-1); break; printf(n); printf( 译码结束n); return 0; 2-1问题描述成绩管理编制一应用软件实现对班级成绩管理。基本功能有学生信息的增删（转入或退学）、查找（从当前点向前或向后双向的）、录入、统计（如总分，及格率等）。建议用双链表实现。2-2概要设计2-2.1程序的模块组成。 主函数 main（） 录入函数 Insert（） 显示函数 Display（） 保存函数 Save（） 删除函数 Delete（） 查询函数 Search（） 统计函数 Count（）2-2.2各个函数的主要功能：录入函数：随时输入数据（学生的各项信息）。显示函数：显示所有学生的信息。删除函数：删除某学生的信息。查找函数：按学号进行查找信息。保存函数：对学生信息进行保存。统计函数：对学生总成绩的统计菜单函数：显示菜单栏以便进行功能选择。2-2.3模块的流程图 2-3详细设计 2-3.1各模块算法及函数 学生信息录入 void Insert() voidSave();printf(请输入要录入学生成绩的个数:n);scanf( %d,&s); fflush(stdin);for(i=0;is;i+)printf(请输入第%d个学生的姓名:n,i+1);scanf( %s,);printf(请输入该学生的学号(1-100):n,i); scanf( %d,&strui.num);printf(请输入学生语文成绩：n );scanf( %d,&strui.score1);printf(请输入学生数学成绩：n );scanf( %d,&strui.score2);printf(请输入学生英语成绩：n );scanf( %d,&strui.score3);fflush(stdin);printf(学生基本信息录入完毕:n);printf(n);wait(按ENTER返回！);Save(); 学生信息显示 void Display()printf(n);printf(*学生基本信息*n);printf(姓名t学号t语文成绩t数学成绩t英语成绩n);for (i=0;is;i+)printf(%st,);printf(%dt,strui.num);printf(%dtt,strui.score1);printf(%dtt,strui.score2);printf(%dttn,strui.score3);printf(n);printf(*n);printf(n);printf(学生信息显示完毕!);printf(n);wait(按ENTER返回!); 学生信息删除void Delete()int i,k;int j=0;printf(请输入要删除的学生学号:n);scanf(%d,&j);for(i=0;is;i+)if(j=strui.num)k=i;break;if(j=0)printf(按任意键继续:n); if(k100)for(i=k;is;i+) /* 用后一个同学的信息覆盖前一个同学的信息 */strcpy( ,strui+1.name);strui.age=strui+1.age;strui.num=strui+1.num;strui.score1=strui+1.score1;strui.score2=strui+1.score2;strui.score3=strui+1.score3;if(s=0)printf( 没有学生信息:n);break;s-; printf(删除成功!);wait(按任意键继续!);elseprintf(没有找到相关信息:n); 学生信息保存void Save()FILE *fp;int i;fp=fopen(student.txt,w); for(i=0;is;i+) fwrite(&strui,sizeof(struct student),1,fp); /向文件中写入数据/system(cls);fclose(fp);printf(n);printf(保存成功!n);printf(n);wait(按ENTER返回主菜单 ); 学生信息查询void Search() FILE *fp;int ch,i,num; system(cls); if(fp=fopen(student.txt,r)=NULL) printf(cannot open filen); exit(0); for(i=0;is;i+) fread(&strui,sizeof(struct student),1,fp);printf( 请输入学号n);scanf(%d,&num);for(i=0;is;i+) if(strui.num=num)break; if(is)printf(查找结果如下:n);printf(n);printf(学号t姓名t语文成绩t数学成绩t英语成绩n); printf(%dt%st%dtt%dtt%dn,strui.num,,strui.score1,strui.score2,strui.score3); elseprintf(您输入的学号不存在!);wait(查询成功!);学生成绩统计void Count()FILE *fp; if(fp=fopen(student.txt,r)=NULL) printf(cannot open filen); exit(0); while(!feof(fp) fread(&strui,sizeof(struct student),1,fp);printf(学号t姓名t语文成绩t数学成绩t英语成绩t总分n);for(i=0;is;i+)strui.sum=strui.score1+strui.score2+strui.score3; printf(%dtt%stt%dtt%dtt%dtt%dn,strui.num,,strui.score1,strui.score2,strui.score3,strui.sum);wait(); void wait(char message10)printf(n%s,message);fflush(stdin);getchar()；2-4调试分析2-4.1登录系统界面2-4.2学生信息录入界面2-4.3学生成绩统计界面2-4.4学生信息显示界面2-4.5数据保存界面2-4.6删除信息界面2-4.7学生信息查找界面2-5心得体会这次课设的模式是一个按学号必做一个,然后自选一个。然而自选的我就选了一个相对容易点的题目，这个在以前也学过。做起来就快些。这个课设就完成的快些。 有人认为这种课程设计很是枯燥无味，但我认为，在编程的过程中会体验到平时体验不到的快乐，还能更加巩固平常我们学到的知识，在学习的过程中还能体验到快乐，何乐不为呢？对数据结构这门课程我觉得是对C语言的更进一步的学习，我觉得在这两周我学到了很多。数据结构对我说学起来还是有点难度。先是上网查找有关的资料，分析题目所需的数据，要用到哪些函数等等。将工作分配到每块是我完成这个设计的主要方法，然而将每块都完成看起来比较轻松，但实际操作起来却是比较麻烦的，一不注意就有了错误，有时还找不到。由于平时对程序方面的知识的积累较为匮乏，所以操作起来真是寸步难行，没办法，只有拿出课本找到相应的知识点，临阵磨枪。 课程设计是培养学生综合运用所学知识，发现、提出、分析和解决实际问题，锻炼实践能力的重要环节，是对学生实际工作能力的具体练习和考察过程。随着科学技术发展的日新日异，当今计算机应用在生活中可以说得是无处不在。因此作为二十一世纪的大学来说把握计算机开发技术是十分重要的。 回顾起此次课程设计，至今我仍感慨颇多，的确，从拿到题目到完成整个编程，从理论到实践，在这两个星期的日子里，学到了很多很多的东西，同时不仅巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。在设计的过程中碰到问题，可以说得是困难重重，这究竟第一次做的，难免会碰到过各种各样的问题，同时在设计的过程中发现了自己的不足之处，对以前所学过的知识理解得不够深刻，把握得不够牢固，比如说结构体通过这次课程设计，更加坚定了以后要好好学习这门课程的信念。培养了独立思考问题的能力，提高了自身的动手能力。在程序的编写过程中，我充分体会了编程工作者的辛苦，因为没一个细微的细节都必须十分的注意。如果稍有不慎，就会全盘皆“输”。而且往往很多时候，程序我自己觉得非常正确，但是就是便以通不过，在查找错误的过程中，面临着否认自己的过程，非常的难受。同时由于自己的经验及各方面的能力的不足，所以进展的速度非常的缓慢，往往一天下来什么都没做成功。这个过程曾给我沉重打击，不过当看到程序没错误能执行出来时，心中的喜悦难以用言语来表达。在开始编写程序的时候，我看到别人的程序功能非常的详细，而且界面非常的漂亮，总希望自己的程序也多一些功能更加的完善。但是渐渐的我发现编写一个优秀的程序决不是一蹴而就的事情，需要长时间的积累和经验，而这个方面又是我的弱项。因此在同学的帮助下，我认识到自己的不足和劣势，不要贪图大而全，只要尽我所能，编制一个实用简单的程序也是一件很不容易的事情。在同学的帮助和自己的努力之下，我终于做出了一个简单的程序。虽然程序的功能简单，而且我想在实际的运用中，肯定会有所不足。因为学生信息管理系统工作的内容非常的丰富，我涉及到的仅仅是学生信息管理的一部分简单内容，离实际的客户需求肯定还有一定的差距。但是它毕竟代表着我对这段时间所学的知识的掌握。由于我的知识浅薄，经验不足及阅历破浅，因此在该程序的设计方面还有很多不足，比如功能过少，只是简单的实现了数据的添加，对数据的删除和查询等操作均为实现，因此需要今后更加深入的学习和努力2-6附录：源代码：#include#include#include|#includestruct student /定义结构类型，类型名为studentchar name10; int age,num,score1,score2,score3,sum;stru100;int s=0;int i;void wait(char message10);/*学生基本信息录入*/void Insert() voidSave();printf(请输入要录入学生成绩的个数:n);scanf( %d,&s); fflush(stdin);for(i=0;is;i+)printf(请输入第%d个学生的姓名:n,i+1);scanf( %s,);printf(请输入该学生的学号(1-100):n,i); scanf( %d,&strui.num);printf(请输入学生语文成绩：n );scanf( %d,&strui.score1);printf(请输入学生数学成绩：n );scanf( %d,&strui.score2);printf(请输入学生英语成绩：n );scanf( %d,&strui.score3);fflush(stdin);printf(学生基本信息录入完毕:n);printf(n);wait(按ENTER返回！);Save();/*学生基本信息显示*/void Display()printf(n);printf(*学生基本信息*n);printf(姓名t学号t语文成绩t数学成绩t英语成绩n);for (i=0;is;i+)printf(%st,);printf(%dt,strui.num);printf(%dtt,strui.score1);printf(%dtt,strui.score2);printf(%dttn,strui.score3);printf(n);printf(*n);printf(n);printf(学生信息显示完毕!);printf(n);wait(按ENTER返回!);/*学生基本信息保存*/void Save()FILE *fp;int i;fp=fopen(student.txt,w); for(i=0;is;i+) fwrite(&strui,sizeof(struct student),1,fp); /向文件中写入数据/system(cls);fclose(fp);printf(n);printf(保存成功!n);printf(n);wait(按ENTER返回主菜单 );/*学生基本信息删除*/void Delete()int i,k;int j=0;printf(请输入要删除的学生学号:n);scanf(%d,&j);for(i=0;is;i+)if(j