devbox
天景科技苑
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

哈夫曼编码_哈夫曼编码输入要编码的正文

作者：天景科技苑 | 2024-07-21 02:07:13

赞

踩

哈夫曼编码输入要编码的正文

哈夫曼编码（还有对应的实验报告，在我的上传资源里，可以免费下载））

1.设计内容


1.添加用户登录密码

2.建立哈夫曼树：读入文件(*.souce)，统计文件中字符出现的频度，并以这些字符的频度作为权值，建立哈夫曼树。

3.编码：利用已建立好的哈夫曼树，获得各个字符的哈夫曼编码，并对正文进行编码，然后输出编码结果，并存入文件(*.code)中。

4.译码：利用已建立好的哈夫曼树将文件(*.code)中的代码进行译码，并输出译码结果，并存入文件(*.decode)中。

2．各个模块详细的功能描述。

1.登录：输入初始密码登录进入菜单页面，三次输错密码后自动退出系统。

2.初始化源文件：通过键盘录入要进行压缩的内容，并将输入的内容保存到hfm.souce文件当中。

3.查询字符的编码：统计hfm.souce中不同字符出现的频度，赋予每个字符不同权重，根据权重建立哈夫曼树，然后输出每个字符对应的哈夫曼编码。

4.打印哈弗曼树：依次按照字符，权重，左子树，右子树，双亲打印哈夫曼树。

5.查询编码后文件：从hfm.souce中读出源文件内容，利用建立好的哈夫曼树将该内容进行编码，并保存到hfm.code文件中，输出编码后内容。

6.查询译码后文件：从hfm.code 文件中读出编码后内容，利用哈夫曼树进行译码，将译码后的文件保存到hfm.decode文件中，并输出译码后文件。

7.退出：退出系统

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<conio.h>
  4. #include<windows.h>
  5. #include <graphics.h>
  6. #pragma comment (lib,"Winmm.lib")
  7. #define N 26
  8. #define M 2*N-1
  9. #define MAX 10000
  10. #define MAXSIZE 100
  11. menu();
  12. typedef struct
  13. {
  14. 	char ch;
  15. 	int weight,rchild,lchild,parent;
  16. }hfm;
  17. typedef struct
  18. {
  19.  char bits[N];   //位串
  20.  int start;      //编码在位串中的起始位置
  21.  char ch;        //字符
  22. }codetype;
  23. typedef struct
  24. {
  25.  char ch;   
  26.  int  weight;     
  27. }weighttype;
  28. read_in_f1(weighttype weight[N])
  29. {
  30. 	int i,j,k=0,n=0,m;;
  31. 	char ch,cd[MAX];//cd[MAX]缓冲数组
  32.     FILE *fp;
  33. 		
  34.     if((fp=fopen("hfm.souce","r"))==NULL) 
  35.     {
  36.         printf("not open");
  37.         exit(0);
  38.     }
  39.     while ((ch=fgetc(fp))!=EOF)
  40. 		cd[n++]=ch;
  41. 	for(i=0;i<n;i++)
  42. 	{	m=0;
  43. 		if(cd[i]=='$') continue; 
  44. 		weight[k].ch=cd[i];
  45. 		for(j=i;j<n;j++)
  46. 		{	
  47. 			if(cd[j]==weight[k].ch)
  48. 			{		
  49. 				m++;
  50. 				cd[j]='$';				
  51. 			}
  52. 		}
  53. 		weight[k].weight=m;
  54. 		k++;
  55. 	}
  56.     fclose(fp);
  57.  
  58. }
  59. void create_hfm(hfm HFM[],weighttype weight[N])
  60. {
  61. 	char c;
  62. 	int i,j,f,p1,p2,s1,s2;//p1,p2为最小和次小节点的下标,s1,s2为最小和次小节点的权重
  63. 	for(i=0;i<M;i++)
  64. 	{
  65. 		HFM[i].weight=0;
  66. 		HFM[i].rchild=-1;
  67. 		HFM[i].lchild=-1;
  68. 		HFM[i].parent=0;
  69. 		HFM[i].ch='^';
  70. 	}
  71. 	for(i=0;i<N;i++)
  72. 	{
  73. 		if(weight[i].weight!=0)
  74. 		{
  75. 			HFM[i].ch=weight[i].ch;
  76.             HFM[i].weight=weight[i].weight;
  77. 		}
  78. 	}
  79. 	for(i=N;i<M;i++)
  80. 	{
  81. 		p1=0;p2=0;		s1=s2=MAX;	
  82. 		for(j=0;j<i;j++)
  83. 		{
  84. 			if(HFM[j].parent==0)
  85. 			if(HFM[j].weight<s1)      //找权重最小的节点
  86. 			{
  87. 				s1=HFM[j].weight;	
  88. 				p1=j;
  89. 			}
  90. 	        else if(HFM[j].weight<s2) 
  91. 			{
  92. 				s2=HFM[j].weight;
  93. 				p2=j;                //找权重次小的节点
  94. 			}
  95. 		}
  96. 		HFM[i].weight=HFM[p1].weight+HFM[p2].weight;   //赋新结点权重
  97. 		HFM[i].lchild=p1;       HFM[i].rchild=p2;      //赋新结点左右孩子指针	
  98. 		HFM[p1].parent=i;   	HFM[p2].parent=i;      //改变最小节点和次小节点的双亲指针
  99. 	
  100. 	}
  101.  
  102. }
  103. void hfmcode(codetype code[],hfm HFM[])//根据哈夫曼树求出哈夫曼编码
  104. {
  105. 	int i,j,c,p;
  106.     codetype cd;  //缓冲变量
  107. 	char ch;
  108.     FILE *fp1,*fp2;
  109.     for(i=0;i<N;i++)
  110. 	{
  111. 		cd.start=N;
  112.         cd.ch=HFM[i].ch;
  113.         c=i;               //从叶结点出发向上回溯
  114.         p=HFM[i].parent;   //HFM[p]是HFM[i]的双亲
  115. 		while(p!=0)
  116. 		{
  117. 			cd.start--;
  118. 			if(HFM[p].lchild==c) 		cd.bits[cd.start]='0';   //HFM[i]是左子树，生成代码'0'
  119.             else                        cd.bits[cd.start]='1';   //HFM[i]是右子树，生成代码'1'
  120. 			c=p;
  121.             p=HFM[p].parent;
  122. 		}
  123. 		code[i]=cd;      //第i+1个字符的编码存入code[i]
  124. 	}
  125. 	printf("输出每个字符的哈夫曼编码:\n");
  126. 	for(i=0;i<N;i++)
  127. 	{
  128. 		if(HFM[i].weight!=0)
  129. 		{
  130. 			printf("%c: ",code[i].ch);
  131. 			for(j=code[i].start;j<N;j++)
  132. 			{
  133. 				printf("%c ",code[i].bits[j]);
  134. 			}
  135. 			printf("\n");
  136. 		}
  137. 	}
  138.     if((fp1=fopen("hfm.souce","r"))==NULL) 
  139.     {
  140.         printf("not open");   exit(0);  
  141.     }
  142. 	if((fp2=fopen("hfm.code","wt"))==NULL)
  143. 	{
  144. 		printf("写文件出错！！按任意键退出。");
  145. 		getch();	exit(0);	   		
  146. 	}
  147.     while ((ch=fgetc(fp1))!=EOF)
  148. 	{
  149. 	  for(i=0;i<N;i++)
  150. 	  {
  151. 		if(ch==code[i].ch)
  152. 		{
  153. 			for(j=code[i].start;j<N;j++)
  154. 			{					
  155. 				fprintf(fp2, "%c",code[i].bits[j] ); //向所建文件写一字符串//	printf("%c ",code[i].bits[j]);	                 		  
  156. 			}
  157. 		}		
  158. 	  }
  159. 	}
  160. 	fprintf(fp2, "%d",2);
  161. 	printf("保存成功！！请按任意键继续。\n");
  162.     fclose(fp2);            
  163.     fclose(fp1);
  164. 		printf("按任意键返回主菜单！！！");
  165.     getch();
  166. 	menu();
  167. }
  168. void decode(hfm HFM[M])   //依次读入电文，根据哈夫曼树译码
  169. {
  170. 	int i,j=0,s,g=0;
  171. 	FILE *fp1,*fp2;
  172.     char b[MAX];     
  173.     i=M-1;               //从根结点开始往下搜索
  174. 	if((fp1=fopen("hfm.code","r"))==NULL)
  175. 	{
  176. 		printf("读文件出错！！按任意键退出。");
  177. 	    getch(); 	exit(0);	  		
  178. 	}
  179. 	if((fp2=fopen("hfm.decode","wt"))==NULL)
  180. 	{
  181. 		printf("xie文件出错！！按任意键退出。");
  182. 		getch();  exit(0);	  		
  183. 	}
  184. 	while ((s=fgetc(fp1))!=EOF)
  185. 	{
  186. 		b[g++]=s;
  187. 	}
  188.     printf("译码后的字符为：\n");
  189.     while(b[j]!='2')
  190. 	{	
  191. 		if(b[j]=='0')
  192. 			i=HFM[i].lchild;   //走向左孩子
  193.         else
  194. 			i=HFM[i].rchild;   //走向右孩子
  195. 		if(HFM[i].lchild==-1)  //tree[i]是叶结点
  196. 		{
  197. 			fprintf(fp2, "%c",HFM[i].ch);
  198. 			printf("%c",HFM[i].ch);
  199.             i=M-1;            //回到根结点
  200. 		}
  201. 		j++;
  202. 	}
  203. 	printf("保存成功！！请按任意键继续。\n");
  204. 	fclose(fp2);
  205. 	fclose(fp1);
  206. 	printf("按任意键返回主菜单！！！");
  207.     getch();
  208. 	menu();
  209. }
  210. save_in_f1()//创建文件
  211. {
  212. 	char ch;
  213. 	FILE *fp;
  214. 	if((fp=fopen("hfm.souce","wt"))==NULL)
  215. 	{
  216. 		printf("写文件出错！！按任意键退出。");
  217. 		getch();	exit(0);	
  218. 	}
  219. 		printf("请输入原始文档(以^结束)：\n");
  220. 	while(ch!='^')
  221. 	{
  222. 		ch=getchar();
  223.  
  224. 		fputc(ch,fp); //向所建文件写一字符串  
  225. 	}
  226. 	    printf("保存成功！！请按任意键继续。\n");
  227. 	    fclose(fp);
  228. 	    	printf("按任意键返回主菜单！！！");
  229.     getch();
  230. 	menu();	
  231. }
  232. 	print(hfm HFM[MAX])
  233. 	{
  234. 		int i;
  235. 		printf("字符\t权重\t左子树\t右子树\t双亲\n");
  236. 	    for(i=1;i<M;i++)
  237. 		{
  238. 		   //if(HFM[i].ch=='^') continue;
  239. 		     printf("%c\t%d\t%d\t%d\t%d\n",HFM[i].ch,HFM[i].weight,HFM[i].lchild,HFM[i].rchild,HFM[i].parent);
  240. 		}
  241. 			printf("按任意键返回主菜单！！！");
  242.     getch();
  243. 	menu();
  244. 	}
  245.  
  246.  
  247. printcode()
  248. {
  249. 	FILE *fp;
  250. 	char ch;
  251. 	if((fp=fopen("hfm.code","r"))==NULL)
  252. 	{
  253. 		printf("读文件出错！！按任意键退出。");
  254. 		getch();	exit(0);	   		
  255. 	}
  256.     while ((ch=fgetc(fp))!=EOF)
  257. 	{ 
  258. 		if((ch-48)==2) break;
  259. 	  printf("%d",ch-48);
  260. 	
  261. 	}	
  262.     fclose(fp);	
  263. 		printf("按任意键返回主菜单！！！");
  264.     getch();
  265. 	menu();
  266. }
  267. menu()
  268. {
  269.  
  270. 	system("cls");
  271.  system("color 03" );
  272.     puts("                                                                                        ");
  273.     puts("                                                  ☆ hafuman编码☆        ");
  274.     puts("                                   ═══════════════════════");
  275.     puts("                         ╔═══════════════════════════════╗"); 
  276.     puts("                         ║                     ※1. 初始化源文件                        ║");
  277.     puts("                         ║                                                              ║");
  278.     puts("                         ║                     ※2. 查询字符的编码                      ║");
  279. 	puts("                         ║                                                              ║");
  280.     puts("                         ║                     ※3. 打印哈弗曼树                        ║");
  281. 	puts("                         ║                                                              ║");
  282.     puts("                         ║                     ※4. 查询编码后文件                      ║");
  283. 	puts("                         ║                                                              ║");
  284.     puts("                         ║                     ※5. 查询译码后文件                      ║");
  285. 	puts("                         ║                                                              ║");
  286.     puts("                         ║                     ※6. 退出                                ║");
  287.     puts("                         ║                                                              ║");
  288.     puts("                         ╚═══════════════════════════════╝");
  289. 	 printf("\n\n请选择（1-6）:");
  290.  
  291. }
  292. void mi_ma()//密码验证
  293. {	
  294. 	int   i=0, x = 3;
  295.     int flag = 0;
  296.     char    s[20];
  297. 	char mima[20]="123456";
  298. 	 system("cls");
  299.  system("color 03" );
  300. 	system("color 0a");
  301.     do
  302.     { 
  303. 	  printf("\n\n");
  304.       printf(" ╒═━━━━━━╗\n");
  305.       printf(" ║请您输入密码: ║\n");
  306.       printf(" ╚━━━━━━━╝\n");
  307. 		for(i=0;i<6;i++)
  308. 		{
  309. 			s[i]=getch();
  310.             printf("%c",s[i]);
  311. 		 	printf("\b*");
  312. 		}
  313. 	getch();
  314.     s[6]='\0';
  315.     printf("\n");
  316. 	
  317.  
  318. 	if(!strcmp(s,mima))//进行密码验证
  319.         {
  320.             printf("密码正确！！！！\n\n\n按任意键继续~~~\n");
  321. 			getch();
  322.             flag=1;
  323.             break;
  324.         }
  325.         else
  326.         {
  327.             printf("密码错误，请重新输入:\n");
  328.             x--;
  329.         }
  330.     }
  331.     while(x>0);
  332.     if(!flag)
  333.     {
  334.         printf("你已经输入三次错误密码!");
  335.         exit(0);
  336.     }
  337.  
  338.  
  339. }
  340. main()
  341. {
  342. 	int i;
  343. 	weighttype weight[N]={0};
  344. 	hfm HFM[MAX];
  345. 	
  346. 	codetype code[N]; //存放哈弗曼编码
  347. 	mi_ma();
  348.  
  349. 	menu();
  350. 		while(1)
  351. 	{
  352. loop:
  353. 		fflush(stdin);
  354. 		scanf("%d",&i);
  355. 		
  356. 		    switch(i)
  357. 			{
  358. 		      case 1: 
  359. 		    	save_in_f1();
  360. 		read_in_f1(weight); //获取各个字符的出现的频率
  361.     	create_hfm(HFM,weight);//建立哈弗曼树
  362. 			
  363. 		    	break;
  364. 			 case 2:
  365. 				   	read_in_f1(weight); //获取各个字符的出现的频率
  366.     	create_hfm(HFM,weight);//建立哈弗曼树
  367. 			    hfmcode(code,HFM);//编码
  368. 			    break;
  369. 			  case 3:
  370. 			///	  	read_in_f1(weight); //获取各个字符的出现的频率
  371.     //	create_hfm(HFM,weight);//建立哈弗曼树
  372. 				print(HFM);//输出哈弗曼树
  373. 				break;		   			
  374. 			  case 5:
  375. 				  	read_in_f1(weight); //获取各个字符的出现的频率
  376.     	create_hfm(HFM,weight);//建立哈弗曼树
  377. 			decode(HFM);//解码 
  378. 				break;
  379. 				 case 4:
  380. 					 	read_in_f1(weight); //获取各个字符的出现的频率
  381.     	create_hfm(HFM,weight);//建立哈弗曼树
  382. 			    printcode();
  383. 				break;
  384. 					 case 6:
  385. 						 exit(0);
  386. 		
  387. 				break;
  388. 			  default:printf("您输入的编码不对！请重新输入：\a");
  389. 			    goto loop;
  390. 			}	
  391. 	}
  392. 	
  393.  
  394. }


声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/天景科技苑/article/detail/859288
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号