惠东住房建设局网站,jsp网站开发难吗,北京网站开发网站建设报价,做网站属于广告公司吗文章目录#xff08;一#xff09;设计描述#xff08;二#xff09;需求分析#xff08;三#xff09;详细设计#xff08;四#xff09;代码实现与测试#xff08;五#xff09;个人总结#xff08;一#xff09;设计描述
1.题目描述 设计一个利用哈夫曼算法的编…
文章目录一设计描述二需求分析三详细设计四代码实现与测试五个人总结一设计描述
1.题目描述 设计一个利用哈夫曼算法的编码和译码系统重复地显示并处理以下项目直到选择退出为止。
1) 输入一串字符然后统计其中各个字符的个数,即每个字符的权值。
2) 进行初始化操作,并建立哈夫曼树
3) 编码利用建好的哈夫曼树生成哈夫曼编码并输出编码
4) 译码即输入每个字符对应的二进制的编码0或1然后输出对应的字符。
5) 结束操作。2.设计目的与要求
1目的 通过布置具有一定难度的实际程序设计项目进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法
2要求
1.要求利用C\C语言来完成系统的设计
2.突出C语言的函数特征以多个函数实现每一个子功能或者C语言面向对象的编程思想
3.画出功能模块图
4.进行简单界面设计能够实现友好的交互
5.具有清晰的程序流程图和数据结构的详细定义
6.熟练掌握C语言或者C语言的各种操作。二需求分析
第一步定义Treecount哈夫曼树节点的个数随后定义两个结构体HTnode和HTcode结构体HTnode储存数据信息即输入的字符data权值weight父结点parent左孩子lchild右孩子rchild。 结构体HTnode储存结果信息即输入的字符dataBT数组储存哈夫曼编码结果start哈夫曼编码的起始位置num统计各个字符的出现的个数即权值input 输入的字符第二步定义字符指针P数组letter[]和数组string[],数组letter用来调用数据 inputdatanumstring[]用来输入字符同时让指针P指向string[];由于数组是单个存储判断字符是否相同用accountnum分别统计字母个数以及每个字符的对应次数即求权值。第三步首先定义两个数组huffnodearray[]分别储存结点与字符然后进行哈夫曼树的初始化然后找到权值最小的两个结点并记录当前下标。由于是逆序输出左右子树的结点位置为2n-1得知左右子树的权值后让左右子树权值进行相加把值赋给一个新的结点。第四步结构体HTcode实例化一个对象begin并定义两个数组huffnodehuffcode调用哈夫曼树并记录编码的位置为n-1倒序编码并记录下标。然后回溯头结点找到左孩子赋值为0找到右孩子赋值为1。然后进行start–倒着计算编码沿着父母结点往上走到结点保存并求出每个叶子节点的哈夫曼编码与编码的起始位。第五步定义数组code数组字符指针q输入0和1的数字组合此时哈夫曼树对应的叶子结点下标为2n-2然后进行译码如果读到0从根结点的左孩子继续读入直到读到1然后继续读入即读到了一个叶子字符即翻译一个字符成功然后进行遍历输出结果。第六步用户选择结束系统
三详细设计
1.实现思想
1.首先要构造一棵哈夫曼树哈夫曼树的结点结构包括权值双亲左右孩子假如由n个字符来构造一棵哈夫曼树则共有结点2n-1个在构造前先初始化初始化操作是把双亲左右孩子的下标值都赋为0然后依次输入每个结点的权值
2.第二步是通过n-1次循环每次先找输入的权值中最小的两个结点把这两个结点的权值相加赋给一个新结点并且这个新结点的左孩子是权值最小的结点右孩子是权值第二小的结点鉴于上述找到的结点都是双亲为0的结点为了下次能正确寻找到剩下结点中权值 最小的两个结点每次循环要把找的权值最小的两个结点的双亲赋值不为0i.就这样通过n-1循环下、操作创建了一棵哈夫曼树其中前n个结点是叶子输入的字符结点后n-1个是度为2的结点
3.编码的思想是逆序编码从叶子结点出发向上回溯如果该结点是回溯到上一个结点的左孩子则在记录编码的数组里存“0”否则存“1”注意是倒着存直到遇到根结点结点双亲为0每一次循环编码到根结点把编码存在编码表中然后开始编码下一个字符叶子
4译码的思想是循环读入一串哈夫曼序列读到“0”从根结点的左孩子继续读读到“1”从右孩子继续如果读到一个结点的左孩子和右孩子是否都为0如果是说明已经读到了一个叶子字符翻译一个字符成功把该叶子结点代表的字符存在一个存储翻译字符的数组中然后继续从根结点开始读直到读完这串哈夫曼序列遇到结束符便退出翻译循环
3.2 创建哈夫曼树图示 已知叶子节点为{10203040}以这4个权值构建树b的过程为 3.实现流程图
四代码实现与测试
#includestdio.h
#includestdlib.h
#includestring.h
#includewindows.h#define Treecount 50 //最大叶结点个数
#define MAXSIZE 500
typedef struct node {char data;int weight;int parent;int lchild;int rchild;
} HTnode;
typedef struct code {char data;int BT[MAXSIZE]; //数组存放字符的哈夫曼编码int start; //该编码在数组中的开始位置char input;int num;
} HTcode;
void Createhufftree(HTnode HuffNode[],int n,HTcode array[]) { // array[]: 用来存储字符及其权值int i,j;int minfirst,minsecond;int Lnode,Rnode;for(i0; i2*n-1; i) {HuffNode[i].data0;HuffNode[i].weight0;HuffNode[i].parent-1;HuffNode[i].lchild-1;HuffNode[i].rchild-1;}for(i0; in-1; i) {minfirstminsecond32767; //给最小和次小的树赋最大值LnodeRnode-1;for(j0; jni; j) {if(HuffNode[j].parent-1 HuffNode[j].weightminfirst) { //每次找出剩下的最小权值并将最小权值赋给次小minfirstminsecond;RnodeLnode;minfirstHuffNode[j].weight;Lnodej; //记录下标} else if(HuffNode[j].parent-1 HuffNode[j].weightminsecond) {minsecondHuffNode[j].weight;Rnodej;}}HuffNode[Lnode].parent ni;HuffNode[Rnode].parent ni;HuffNode[ni].weight HuffNode[Lnode].weightHuffNode[Rnode].weight;HuffNode[ni].lchild Lnode;HuffNode[ni].rchild Rnode;}for(i0; in; i) {HuffNode[i].weightarray[i].num; //将字符个数赋给权值HuffNode[i].dataarray[i].input;}
}
void QQ() {printf(请输入二进制译码启动密码密码错误默认结束即为默认退出);long sercret;scanf(%d,sercret);if(sercret11011) {Sleep(1000);} else {Sleep(1000);printf(非法操作结束系统);exit(-1);}
}
void HuffmanCoding(int n, HTcode array[]) {// array[]: 用来存储字符及其权值HTnode HuffNode[1000];HTcode HuffCode[Treecount];HTcode begin;FILE *fp;fpfopen(D:\\a.txt,w);Createhufftree(HuffNode,n,array);int i, j ;int loc,p;char code[30],*q;for(i0; in; i) {begin.startn-1; //编码的开始位置loci;pHuffNode[loc].parent;while(p!-1) {if(HuffNode[p].lchildloc)begin.BT[begin.start]0;elsebegin.BT[begin.start]1;begin.start--; //倒着计算编码locp; //沿着父母结点往上走到顶点pHuffNode[loc].parent;}for(jbegin.start1; jn; j)HuffCode[i].BT[j]begin.BT[j];HuffCode[i].startbegin.start; // 保存求出的每个叶节点的哈夫曼编码和编码的起始位printf(\n);}printf(各个字符对应的二进制编码(1//0//1//0)如下\n);for(i0; in; i) {printf(字符%c的密文:,HuffNode[i].data);for(jHuffCode[i].start 1; jn; j) //start走过了加一恢复到开始位编码个数小于nprintf(%d, HuffCode[i].BT[j]);printf(\n);}printf(\n);printf(编码成功1s后打印哈夫曼编码\n);Sleep(1000);for(i0; in; i) {for(jHuffCode[i].start1; jn; j) {fprintf(fp,%d,HuffCode[i].BT[j]);}for(jHuffCode[i].start 1; jn; j) {printf(%d, HuffCode[i].BT[j]);}}printf(\n\n);if(i0) {QQ();}// 译码system(cls);printf( ----- ∮哈夫曼译码系统已经就绪 ∮------- \n);printf(各字符的对应的编码如下\n); for(i0; in; i) {printf(字符%c的密文:,HuffNode[i].data);for(jHuffCode[i].start 1; jn; j) //start走过了加一恢复到开始位编码个数小于nprintf(%d, HuffCode[i].BT[j]);printf(\n);}printf( -- 请输入对应的二进制数字 \n);scanf(%s,code);q code;loc 2*n -2; // 哈夫曼树的根节点下标printf(译码成功正在打印译码结果\n);Sleep(2000);while( *q ! NULL) {if( *q 0) {loc i HuffNode[loc].lchild;if(HuffNode[loc].lchild -1 HuffNode[loc].rchild -1) {printf(%c,HuffNode[i].data);fprintf(fp,%c,HuffNode[i].data);loc 2*n - 2;}} else if(*q 1) {loc i HuffNode[loc].rchild;if(HuffNode[loc].lchild -1 HuffNode[loc].rchild -1) {fprintf(fp,%c,HuffNode[i].data);printf(%c,HuffNode[i].data);loc 2*n-2; // 重新从根遍历}} else {printf(非法输入);}q;}printf(\n);fclose(fp);
}
void menu() {system(color F);printf( );printf( \n);printf( ____〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓____ \n);printf( || 哈夫曼编码 || \n);printf( _________☆界面选择如下☆_________ \n);printf( \n);printf( - 1 ☆.编码与译码 \n);printf( - 2 ☆.结束系统 \n);printf(------------ ☆ ☆----------------- \n);printf( ∮请手动输入编号 );
}
void Treeaction() {HTcode letter[50];char string[1000], *p;int i, account0;printf( ----- ∮哈夫曼编码系统已经就绪 ∮------- \n);printf( 》》 请输入你要编码的字符串:);scanf(%s,string);for(i0; i50; i) {letter[i].input0;letter[i].num0;}pstring;while(*p!NULL) {for(i0; iaccount1; i) {if(letter[i].inputNULL) { //letter[i].input存储所有的字符,用letter[i].num存储相同的字符的数量letter[i].input*p;letter[i].num;account; // 统计不同字符的个数break;} else if(letter[i].input*p) {letter[i].num;break;}}p;}printf(\n);printf(不同的明文(字符)个数:%d\n,account);printf(\n);printf(输出输入的字符的权值\n);for(i0; iaccount; i) { //输出不同字符及其所对应的权值printf(当前字符%c的权值为%d,letter[i].input,letter[i].num);printf(\n);}printf(\n);HuffmanCoding(account,letter);}
int main() {int n,flaglist1;char choice;while(flaglist) {menu();scanf(%d,n);switch(n) {case 1:system(cls);Treeaction();printf(\n);printf(2秒后系统进行返回\n) ;Sleep(2000);printf(\n);system(cls);printf(已经返回\n); printf(请根据个人意愿进行操作\n);printf(\n);break;case 2:exit(0);}}return 0;
}五个人总结 通过这次课程设计我收获了很多认清了课程设计的需求更认清了自己。谈起缺点自己代码实现的能力也是破绽百出对相对较难的题目不能冷静解决经常犯一些低级的错误。然无独有偶自己也有优点自己思想上能理解难题并尝试解决难题考虑比较周到。 这次的课程设计难度处于中等地位但实现起来并不没有想象中的那么容易。它需要考虑多种因素必须充分理解题目要求化大难题为多个小难题把具体实现步骤细分认真完成每一步步骤然后综合实现题目对应的问题。 时间如白驹过隙无声滑过指尖。学期即将完结即将大二不免多生感想。回想一年时光自己虽说付出努力然并不能收益众多。深知自己与他人之差距然必须成为优秀者方可日后有一席之地。
我没有科学家的那样的天赋异禀而我却又有一颗积极向上的心以“努力不一定成功但不努力绝不会成功”为座右铭付诸行动与汗水不忘初心厚积薄发。正如诗人王之涣所说:“欲穷千里目更上一层楼。”要有“燕雀安知鸿鹄之志”的眼光实现能力之飞跃思想之迅捷然自己必须十分努力才能看起来毫不费力。 风雨过后才会见到彩虹。你尽管去努力剩下的交给天命。定当不忘学习砥砺前行。肺腑之言溢于言表。
