C语言数据结构实习报告-哈夫曼编码-学生信息管理系统.docVIP

西 安 邮 电 大 学 （计算机学院）数据结构与算法课程设计报告题 目：哈夫曼编码/学生信息管理系统 专业名称： 班 级： 学生姓名： 学号（8位）： 指导教师： 设计起止时间 28一. 设计目的 1.通过设计实现哈夫曼编译码，进一步加深对树的应用与操作能力2.通过设计一个小型的管理系统，来进一步加深、巩固C语言程序设计以及数据结构与算法课程中所学习的基本理论知识，用理论联系实际；进一步培养自身综合分析问题、解决问题的能力； 3.掌握C语言程序的基本结构和基本的数据的结构；熟悉C语言编辑、编译、调试、运行的过程； 4.了解程序设计的一般方法，结构化程序设计思想；熟悉常用的程序结构与算法，提升自身实践操作能力2. 设计内容1. 求数据的哈夫曼编码哈夫曼树又叫最优二叉树，可以来构造最优编码，用于信息传输、数据压缩等方面。本次设计主要是实现哈夫曼树的构造，以及求哈夫曼编码，达到可以根据用户的需求输入任意个字符及其权值，之后便可以给出各个字符的编码值的要求。2.学生信息管理系统应用C语言程序设计以及数据结构与算法课程中的结构体、函数、指针、文件、链表等内容，设计一套完整学生信息管理系统，满足对一个班的或者更多的学生基本信息进行输入、输出、查询、删除等管理的要求。本系统设计，主要运用了链表，用链表来完成各项功能，并对文件进行写入于读取操作，将学生的基本信息全部从一个指定的文件中导出并显示出来，然后运用其它函数模块依次进行增加、修改、查询、删除，并随时可以保存和显示已有学生的信息。三设计方案概要设计 1 求哈夫曼编码设计（l）初始化。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树。（2）编码。利用已建好的Huffman树，从叶子结点开始，沿着结点的双亲追溯到根节点，追溯过程中，每上升一层，左分支得到0，右分支得到1，。将得到的编码依次保存到数组里去，最后把字符及编码输出出来2. 学生信息管理系统功能模块图；注册学生信息管理系统从文件导入学生信息并显示序号学号姓名性别修改学生信息查询学生信息删除学生信息显示已录入信息序号查找学号查找 管理员用户注册、登陆3. 哈夫曼编码程序各个模块详细的功能描述选择函数：在数组ht的前i-1项中选取出双亲为零，且权值最小的两个结点创建哈夫曼树函数： 通过初始化结点，接受用户录入的信息，构建出哈夫曼树。求哈夫曼编码函数：通过对结点遍历，及对其双亲的追溯，给出各个数据的哈夫曼编码4. 学生信息管理系统各个模块详细的功能描述 登陆模块：用户可以选择注册、登陆、退出功能。只有注册，并成功登陆后方可进行学生信息管理。 显示模块：可以将已指定的文件中的学生信息、修改后的学生信息全部显示出来。 增加模块：可以在此功能中增加任意多个学生信息，并保存 修改模块：可以对你输入要修改的序号的学生信息，进行修改 ，并保存到文件中 查询模块：可以对你根据序号、或者学号查询对应同学的相信信息 删除模块：可以对你输入要删除的序号的学生信息，进行删除详细设计1 功能函数的调用关系图；哈夫曼编码程序主要函数有：选择函数：select(HuffmanTree ht,int n,int *s1,int *s2) 创建哈夫曼树函数：CrtHuffmanTree(HuffmanTree ht,int n) 求哈夫曼编码函数：CrtHuffmanCodel(HuffmanTree ht,int n)主函数其调用关系如下调用调用求哈夫曼编码：CrtHuffmanCodel()创建哈夫曼树CrtHuffmanTree()调用选择函数select()学生信息管理系统主要包含以下函数：1.登陆函数：denglu(); 2.注册函数：zhuce(); 3.显示函数：DispList(LinkList L )；4.增加信息函数：ListInsert(LinkList L);5.修改函数：Modily(LinkList L) ;6.删除函数：ListDelete(LinkList L)7.查询函数：GetElem(LinkList L);它们调用的关系如下图：主函数调用DispList(LinkList L )调用ListInsert(LinkList L)调用Modily(LinkList L) 调用Denglu()调用ListDelete(LinkList L)调用zhuce() 调用denglu()调用GetElem(LinkList L);2 哈夫曼编码的流程图开始请输入字符及其权值是否继续录入是结束否请输出各字符及其编码3.学生信息管理系统各功能函数的数据流程图； 登陆函数：开始是否有该系统的账号及密码是用户名及密码是否正确注册否登陆成功进行信息管理登陆是否结束 显示函数：开始读文件是否有学生信息存在是读取文件内容并显示新建学生信息否结束 增加学生信息函数： 是否继续修改开始请输入学生信息是否继续录入是结束否 删除函数：开始输入要删除的序号存在输出该同学信息结束不存在判断是否存在该同学是否继续删除 确认后进行删除是否 查找函数： 开始按序号、学号查找q-xuhao=p-xuhaoq-xuehao=p-xuehao显示该学生全部信息结束否是是否 修改函数：开始输入要修改学号存在输出该同学信息结束不存在判断是否存在该同学是否继续修改根据选择，进行修改是否 4.哈夫曼编码的重点设计及编码 利用已建好的Huffman树，从叶子结点开始，沿着结点的双亲追溯到根节点，追溯过程中，每上升一层，左分支得到0，右分支得到1。将得到的编码依次保存到数组里去，最后把字符及编码输出出来。详细设计见源程序中CrtHuffmanCodel(HuffmanTree ht,int n) 学生信息管理系统的重点设计及编码。1.运用链表操作实现用户注册、登陆功能。首先定义一个包含用户名及密码的结构体，在内存中申请一段空间将用户的注册的账户名、密码依次保存到对应节点中去，并保存至文件中去；当用户登录时，通过调取文件中的信息，并依次进行比对，仅有用户名及密码完全与注册时相同时，才可进入管理系统进行信息管理操作，有效保障了信息的安全性。 详细代码见附录源程序中函数zhuce（），denglu(）4 测试数据及运行结果1 哈夫曼编码程序运行结果2.学生信息管理系统正常测试数据和运行结果登陆界面注册界面显示已经导入的学生信息增加学生信息删除学生信息修改学生信息2 异常测试数据及运行结果在求哈夫曼编码中由于输入的字符无法识别导致运算出错由于没有按照要求输入Y/N导致删除函数陷入死循环由于恶意注册的不合法用户信息，导致系统无法正常打开 运行五调试情况，设计技巧及体会1对哈夫曼编码程序的评价及改进方案评价：该程序设计较为良好，能根据用户输入的字符及其权值，构造出对应的二叉树，并求出各个字符对应的哈夫曼编码并打印出来。不足：只是输出字符的对应的哈夫曼编码，没有形象地打印出用户输入权值对应的最优二叉树；选择select()函数应用的是较为低级的两次循环遍历法，方才找出较小的两个元素，增加了程序的时间复杂度。改进方案：应用更高级简单的选择算法，降低该程序的时间复杂度；编写输出函数，以便于打印出较为形象直观的二叉树形式。2.对学生管理系统的评价及改进方案评价：该程序总体设计完好，可以满足用户的注册、登陆、增加、查询、删除、修改学生信息的使用要求。尤其对登陆界面管理员用户注册、密码功能的设置，有效的保证了信息的安全性；并且使用链表来进行储存密码、验证密码保证了正确率；从文件中读入学生信息设计比较好，可以很方便地大批量的增加与删除、修改学生信息；操作简单，方便用户使用。不足：页面不够美观，尤其管理界面视觉效果较差；健壮性不够，当用户不按照提示或者失误的操作后容易导致运行错误甚至，系统崩溃；可输入的学生信息种类不够多，仅有学号、姓名等；功能不够完善，无法为用户提供排序，分类筛选等功能。改进方案：调用C语言的图形设计中的颜色、图案设计程序，让操作界面美观，提升用户体验；完善程序中的条件判断种类，以识别错误的操作，及时终止程序，防止运行失败的出现，增强程序的健壮性、容错性、可操作性；增加程序的功能，进一步设计用学生序号、学号等排序操作，以更方便用户；增大输入学生信息的信息种类，完善学生的信息，如增加家庭住址、联系方式等。3.体会此次C语言数据结构与算法课程实习，是我在老师的指导下第一次完成一个完整系统的设计，也是第一次用C语言写下了超过500行的代码；同时这次实习是一次对以往学习的程序设计知识掌握情况的检验，也是对所学知识的应用、巩固与提高。实习刚开始由于基础不是太扎实，对算法的掌握不够深入，常常犯一些错误，诸如加错标点符号；数组的下标越界、混乱，或是指针超出范围等。我在老师的指导下，慢慢地学会了如何自我调试程序，如何寻找错误的地方，从而提高了学习的效率，学到了很多通过这次实习，我在一次又一次地对错误的更正中，对设计思路的调整中，以及与老师、同学交流过程中，进一步掌握了程序设计的思想方法、设计理念，对C语言程序设计、数据结构与算法，尤其对链表、文件的操作与应用有了更深刻的认识。那一次次为“叮叮”响起的错误报告而抓耳挠腮，一次次为一条语句的设计而争执不下，以及当自己的设计在屏幕上显示时的喜悦，这些都是实习的收获与进步，更是一段段难忘的记忆。六参考文献1 谭浩强著.C语言设计（第三版）.北京：清华大学出版社，20052 王曙燕主编.数据结构与算法.北京：人民邮电出版社，20133 王曙燕主编.数据结构与算法.北京：人民邮电出版社，20134 Ellis Horowitz ,Sartaj Sahni ,Susan Anderson-Freed著 朱仲涛译.数据结构基础(C语言版)（第2版）.北京：清华大学出版社，2009七附录：1.哈夫曼编码的实现#define N 30#define M 2*N-1#include#include#includetypedef structint weight;int Parent,Lchild,Rchild;char ch;HTNode,HuffmanTreeN+1;void select(HuffmanTree ht,int n,int *s1,int *s2) int i; int m1,m2; m1=m2=32767; for(i=0;i=n;i+) if(hti.weight m1&hti.Parent=0) m1=hti.weight ; *s1=i; for(i=0;i=m1&hti.weightm2&hti.Parent=0) if(i!=*s1) m2=hti.weight ; *s2=i; void CrtHuffmanTree(HuffmanTree ht,int n)int i,s1,s2;int m=2*n-1;for( i=1;i=n;i+) printf(请输入第%d个字符及其权值n,i); scanf(%c,%d, &hti.ch,&hti.weight); for( i=1;i=n;i+)hti.Parent=0;hti.Lchild=0; hti.Rchild=0; for(i=n+1;i=m;i+)hti.weight=0;hti.Parent=0;hti.Lchild=0; hti.Rchild=0; for(i=n+1;i=m;i+)select(ht,i-1,&s1,&s2);hti.weight=hts1.weight+hts2.weight;hti.Lchild=s1;hti.Rchild=s2;hts1.Parent=i;hts2.Parent=i;void CrtHuffmanCodel(HuffmanTree ht,int n)int start,i,c,p;int m=2*n-1;char cdN；for(i=1;i=n;i+)start=n-1;c=i;p=hti.Parent;while(p!=0)-start;if(htp.Lchild=c)cdstart=0;elsecdstart=1; c=p;p=htp.Parent; printf(字符%c的编码为n,hti.ch); for(int j=start;j=n-1;j+)printf(%c,cdj);printf(n);void main()HuffmanTree ht;int n; printf(需要输入的字符个数为nn);scanf(%d,&n); CrtHuffmanTree(ht,n); CrtHuffmanCodel(ht,n);2.小型学生管理系统源代码#include #include #include #include #include#define N 20/定义结构体 typedef struct LNode long xuehao; /学号 int xuhao; /班级序号char nameN; /学生姓名 char sex; /性别 struct LNode *next;Node, *LinkList;typedef struct lnode char yhmN; char mmN; struct lnode *next;node, *linklist;void Save(linklist L) linklist p; FILE *fp;fp=fopen(data.txt,wt); if(fp=NULL) printf(注册失败n); getchar(); else for(p=L-next;p!=NULL;p=p-next) fprintf(fp,%s %s,&p-yhm,&p-mm); fputc(n,fp); fclose(fp); linklist Read( ) FILE *fp; linklist L;node *s; fp=fopen(data.txt,rt); L=(linklist)malloc(sizeof(node); L-next=NULL; while(!feof(fp) s=(linklist)malloc(sizeof(node); fscanf(fp,%s %s,s-yhm,s-mm); s-next=L-next; L-next=s; fclose(fp);return L; mima();/对登陆页面密码函数的声明int zhuce( )/新用户注册函数char temp1N,temp2N,temp3N; linklist L,p; node *s; int flag=1; L=Read();p=L-next; while(p-next!=NULL) p=p-next; printf(输入要注册的用户名：n); fflush(stdin);/清空缓存 s=(node*)malloc(sizeof(node); scanf(%s,s-yhm); printf(请输入密码：n); fflush(stdin); gets(temp1);printf(请再次输入密码以确认：n);fflush(stdin);gets(temp2);if(!strcmp(temp1,temp2) strcpy(s-mm,temp1); s-next=p-next; p-next=s; Save(L); printf(nnt 注册成功，请登陆nn); return 1;elseprintf(前后密码不一致，请再次输入密码确认n);gets(temp3);if(!strcmp(temp1,temp3)strcpy(s-mm,temp1); s-next=L-next; L-next=s;printf(注册成功n); Save(L); mima(); return 1;else printf(注册失败n);return 1;return 1;int zhuhanshu();/管理系统主函数的声明int denglu( )/登陆函数linklist L,p;L=Read();char s1N,s2N;printf(请输入管理员用户名：n); fflush(stdin);gets(s1); printf(请管理员输入密码：n); fflush(stdin); gets(s2);p=L-next;while(p!=NULL) if(strcmp(p-yhm,s1)=0&strcmp(s2,p-mm)=0) system(cls); printf(nnt 登陆成功，系统正在打开中nn); zhuhanshu(); break; p=p-next; printf(登陆失败，用户名或者密码错误n);return 0;mima()/登陆页面函数system(cls);int i;doprintf(nnntt 欢迎登陆此学生信息管理系统：nn); printf(- 1.新管理员用户注册nn); printf(- 2.用户登陆nn); printf(- 0.退出系统n);scanf(%d,&i);if(i=0&inext=NULL; while(flag) printf(请输入第%d个同学信息n,i); s=(Node*)malloc(sizeof(Node); printf(n请输入该同学的班内序号：n); scanf(%d,&s-xuhao); printf(n请输入该同学的学号：n); scanf(%8d,&s-xuehao); printf(n请输入该同学的姓名：n); scanf(%s,s-name); printf(n请输入该同学的性别 ：n); scanf(%s,&s-sex); s-next=L-next; L-next=s; i+; printf(是否继续录入？Y/Nn); getchar(); scanf(%c,&c) ; if(c=N|c=n) flag=0; printf( 共%d个学生信息录入已完成n,i-1);return L;/从文件中读入学生信息LinkList read( )FILE *fp; LinkList L;Node *s; int i=0;fp=fopen(tonggong.txt,rt);L=(LinkList)malloc(sizeof(Node);L-next=NULL; while(!feof(fp)s=(LinkList)malloc(sizeof(Node); fscanf(fp,%3d %8d %s %s,&s-xuhao,&s-xuehao,s-name,&s-sex); s-next=L-next; L-next=s; i+;fclose(fp);printf(已经成功导入%d个同学信息n,i);return L;/把录入的信息保存在文件里 void save(LinkList L) FILE *fp; LinkList p;fp=fopen(tonggong.txt,wt); if(fp=NULL) printf(写文件错误！n); getchar(); else for(p=L-next;p-next!=NULL;p=p-next) fprintf(fp,%4d %8d %s %s,p-xuhao,p-xuehao,&p-name,&p-sex); fputc(n,fp); fprintf(fp,%4d %8d %s %s,p-xuhao,p-xuehao,&p-name,&p-sex); printf(信息保存成功！按任意键返回！n); getchar(); fclose(fp);/显示存放的学生信息void DispList( LinkList L)FILE *fp; system(cls); if(fp=fopen(tonggong.txt,rt)=NULL) printf(暂时没有学生信息请录入！n); L=CreateFromHead(); else L=read(); LinkList p=L-next;printf(已经录入的同学的信息为:n);printf(序号t 学号tt 姓名t 性别t n);while (p!=NULL) printf(%dt 0%7dt %st %st n,p-xuhao,p-xuehao,&p-name,&p-sex); p=p-next;printf(n);/增加学生信息void ListInsert(LinkList L)system(cls); Node *s,*p; /为 找到L的最后节点 int flag=1;int i=1;int m=0;char c;p=L-next;while(p-next!=NULL) p=p-next; while(flag) printf(请输入增加的第%d个同学信息n,i); s=(Node*)malloc(sizeof(Node); printf(n请输入该同学的班内序号：n); scanf(%d,&s-xuhao); printf(n请输入该同学的学号：n); scanf(%8d,&s-xuehao); printf(n请输入该同学的姓名：n); scanf(%s,s-name); printf(n请输入该同学的性别 ：n); scanf(%s,&s-sex); s-next=p-next; p-next=s; i+; printf(是否继续录入？Y/Nn); getchar(); scanf(%c,&c) ; if(c=N|c=n) flag=0; printf( 共%d个学生信息录入已完成n,i-1); save(L);/删除学生信息 int ListDelete(LinkList L) LinkList p,s;int m;int n=1;/能不能找到学生的判断标志 int flag=1; char c,d;while(flag) printf(n请输入你想删除的学生的序号:n);getchar();scanf(%d,&m);p=L-next;while(p-next!=NULL) if (p-next-xuhao=m) n=2;printf(你要删除的学生的信息如下：n); printf(序号t 学号tt 姓名t 性别t n); printf(%dt 0%7dt %st %st n,p-next-xuhao,p-next-xuehao,&p-next-name,&p-next-sex); printf(你确认将此同学信息删除？是Y/否Nn); getchar(); scanf(%c,&d) ; if(d=Y|d=y) s=p-next;/找到要删除的学生 p-next=s-next; /从单链表中删除*p结点 free(s); printf(删除完成：n); save(L); break; else return 0; p=p-next; if(n=1)printf(n对不起，班内没有要找的同学.n); return 0; printf(是否继续继续删除？是Y/否Nn); flushall(); scanf(%c,&c) ; if(c=N|c=n) flag=0；return 1;/查找学生信息int GetElem(LinkList L) system(cls); LinkList q,p; int m; printf(nn *欢迎使用学生信息管理系统查询功能*n); printf( 你想要的查找的方式是？ 请输入序号，并按回车键n); printf( 1.按班内序号查找学生n); printf( 2.按学号查找学生n); printf( 3.退出查找，返回主菜单n); scanf(%d,&m); if(m0&mxuhao=9999; p-xuehao=999; switch(m) case 1: printf(请输入学生的班内序号n) ; scanf(%d,&p-xuhao); break; case 2: printf(n请输入该同学的学号：n); scanf(%d,&p-xuehao); break; case 3: return 0; break; for(q=L-next;q!=NULL;q=q-next) if (q-xuhao=p-xuhao|q-xuehao=p-xuehao) printf(你所查找的学生是：n); printf(序号t 学号tt 姓名t 性别t n); printf(%dt 0%7dt %st %st n,q-xuhao,q-xuehao,&q-name,&q-sex); p-xuhao=q-xuhao;p-xuehao=q-xuehao; if(p-xuhao=9999|p-xuehao=999)printf(n对不起，班内没有要找的同学.n); return 0; else printf(n对不起，没有你输入的选项,请重新输入.n); return 0;/修改学生信息 int Modily(LinkList L) system(cls); LinkList p; char m,n; int q=1;/能不能找到学生的判断标志 int flag=1; char c; printf(nn*欢迎使用学生信息管理系统修改功能*n);while(flag) printf(n请输入你想修改的学生的序号:n); scanf(%d,&n); p=L-next; while(p!=NULL) if (p-xuhao=n) q=2;/表示找到要修改的同志 printf(你要修改的学生的信息如下：n); printf(序号t 学号tt 姓名t 性别t n); printf