devbox
运维做开发
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【数据结构】实验十：哈夫曼编码_哈夫曼编码实验

作者：运维做开发 | 2024-07-21 02:04:24

赞

踩

哈夫曼编码实验

实验十 哈夫曼编码

一、实验目的与要求

1）掌握树、森林与二叉树的转换；

2）掌握哈夫曼树和哈夫曼编码算法的实现；

二、 实验内容

1. 请编程实现如图所示的树转化为二叉树。

2. 编程实现一个哈夫曼编码系统，系统功能包括：

(1) 字符信息统计：读取待编码的源文件SourceFile.txt，统计出现的字符及其频率。

  附：SourceFile.txt文件内容为

 

(2) 建立哈夫曼树：根据统计结果建立哈夫曼树。

(3) 建立哈夫曼码表：利用得到的哈夫曼树，将各字符对应的编码表保存在文件Code.txt中。

(4) 对源文件进行编码：根据哈夫曼码表，将SourceFile.txt中的字符转换成相应的编码文件ResultFile.txt。

实现提示：

(1) 字符信息统计：假设源文件SourceFile.txt中的字符只有大小写英文字母（同一个字母的大小写看作一个字符），则字符统计算法的实现过程可以归纳为：先定义一个含有26个元素的整形数组，用来存储各个字母出现的次数，最后还要排除其中出现次数为0的数组元素。

(2) 建立哈夫曼树：可参考教材算法。

(3) 建立哈夫曼码表：可参考教材算法。

(4) 对源文件进行编码：依次读入文件SourceFile.txt中的字符 c，在编码表 HC 中找到此字符，将字符c转换为编码表中存放的编码串，写入编码文件ResultFile.txt中，直到所有的字符处理完毕为止。

三、实验结果

1）请将调试通过的运行结果截图粘贴在下面，并说明测试用例和运行过程。

2）请将源代码cpp文件压缩上传。

题目1：

测试用例及运行结果：

测试用例输入的树为：

树通过孩子兄弟表示法转化的二叉树为：

测试用例实验结果为：

根据最后三行输出（即二叉树的先序遍历和中序遍历，以及树的层序遍历）可知，输入的树可以转化为二叉树，且存储效果均良好。

运行过程：

首先通过主函数调用的函数顺序可知，运行过程为初始化树->通过输入创建树->preorder输出树->midorder输出树->floororder输出树->销毁树。

初始化树时，不需要做额外操作。

通过输入创建树时，主要使用队列实现。首先初始化每个结点的左孩子和右兄弟均为空，然后把当前结点加入队列。如果当前结点为根结点，则树从当前结点开始。否则，获取队列的队首结点，依次存储其左孩子和右兄弟。

 

preorder输出树时，通过if条件判断当前结点是否为空，然后采用根结点——左孩子——右兄弟的方法递归输出。

midorder输出树时，通过if条件判断当前结点是否为空，然后采用左孩子——根结点——右兄弟的方法递归输出。

floororder输出树时，主要通过队列输出。通过if条件判断当前结点是否为空，输出当前根结点的值，然后进行根结点排队。当队列非空时，先输出根结点e的左孩子p，再输出p的右兄弟，此时容易知道p和p的右兄弟在同一层。

销毁树时，通过if条件判断当前结点是否为空，然后采用左孩子——右兄弟——根结点的方法递归销毁，并依次将结点置为空。

实验代码：

  1. //孩子兄弟表示法存储 
  2. #include <iostream>
  3. #include <cstdio>
  4. #include <malloc.h>
  5. using namespace std;
  6. typedef int ElemType;
  7.  
  8. typedef struct CSNode{
  9. 	ElemType data;
  10. 	struct CSNode *firstchild,*rightsib;
  11. }CSNode,*CSTree;
  12.  
  13. #define OK 1
  14. #define ERROR 0
  15. #define TRUE 1
  16. #define FALSE 0
  17.  
  18. typedef struct QNode{
  19. 	CSTree data;
  20. 	struct QNode *next; 
  21. }QNode;
  22.  
  23. typedef struct LinkQueue{
  24. 	QNode *front,*rear;
  25. }LinkQueue;
  26.  
  27. //构造空队列 
  28. void InitQueue_Sq(LinkQueue &Q){
  29. 	Q.front = Q.rear = NULL;
  30. }
  31.  
  32. //判断是否为空 
  33. int QueueEmpty(const LinkQueue &Q){
  34. 	return (Q.rear == NULL && Q.front == NULL); 
  35. }
  36.  
  37. //插入元素进队尾
  38. void EnQueue_Sq(LinkQueue &Q,CSTree &e){
  39. 	QNode *p=(QNode*)malloc(sizeof(QNode));
  40. 	if(!p){
  41. 		exit(0);
  42. 	}
  43. 	p->data =e;
  44. 	p->next =NULL;
  45. 	if (QueueEmpty(Q)){
  46. 		Q.front =Q.rear =p;
  47. 	}
  48. 	else{
  49. 		Q.rear->next =p;
  50. 		Q.rear=p;
  51. 	}
  52. } 
  53.  
  54.  
  55. //删除元素从队头
  56. CSTree DeQueue_Sq(LinkQueue &Q,CSTree &s){
  57. 	if(QueueEmpty(Q)){
  58. 		return ERROR;
  59. 	}
  60. 	QNode *p=Q.front ;
  61. 	s=p->data;//队头存的数据 
  62. 	if(Q.front==Q.rear){
  63. 		Q.front=Q.rear=NULL;
  64. 	}
  65. 	else{
  66. 		Q.front =p->next;
  67. 	}
  68. 	free(p);
  69. 	return s;
  70. } 
  71.  
  72. //取队头元素
  73. void GetHead_Sq(LinkQueue Q,CSTree &p){
  74. 	if(QueueEmpty(Q)){
  75. 		exit(0);
  76. 	}
  77. 	p=Q.front->data ;
  78. } 
  79.  
  80. //初始化树
  81. void InitTree_CST(CSTree &T){
  82. 	
  83. } 
  84.  
  85. //构造树 
  86. void CreateTree_CST(CSTree &T){
  87. 	T=NULL;
  88. 	LinkQueue Q;
  89. 	InitQueue_Sq(Q);
  90. 	ElemType parent,child;
  91. 	CSTree p,q,r=new CSNode;
  92. 	for(cin>>parent>>child;child!=0;cin>>parent>>child){
  93. 		p=(CSTree)malloc(sizeof(CSNode));
  94. 		p->data=child;
  95. 		p->firstchild =p->rightsib =NULL;
  96. 		EnQueue_Sq(Q,p);//append p to Q
  97. 		if(parent==-1){
  98. 			T=p;//root node
  99. 		}
  100. 		else{
  101. 			GetHead_Sq(Q,q);
  102. 			while(q->data != parent){
  103. 				DeQueue_Sq(Q,q);
  104. 				GetHead_Sq(Q,q);
  105. 			}
  106. 			if(!(q->firstchild )){
  107. 				q->firstchild =p;
  108. 				r=p;
  109. 			}
  110. 			else{
  111. 				r->rightsib =p;
  112. 				r=p;
  113. 			}
  114. 		}
  115. 	} 
  116. }
  117.  
  118. //pre-order output
  119. void PreOrderTraverse_CST(CSTree &T){
  120. 	if(T){
  121. 		cout<<T->data<<" ";
  122. 		PreOrderTraverse_CST(T->firstchild );
  123. 		PreOrderTraverse_CST(T->rightsib );
  124. 	}
  125. }
  126.  
  127. //mid-order output
  128. void MidOrderTraverse_CST(CSTree &T){
  129. 	if(T){
  130. 		MidOrderTraverse_CST(T->firstchild );
  131. 		cout<<T->data<<" ";
  132. 		MidOrderTraverse_CST(T->rightsib );
  133. 	}
  134. }
  135.  
  136. //layer-order output
  137. void FloorTraverse_CST(CSTree &T){
  138. 	LinkQueue Q;
  139. 	InitQueue_Sq(Q);
  140. 	if(T){
  141. 		cout<<T->data <<" ";
  142. 		EnQueue_Sq(Q,T);//根结点排队
  143. 		while(!QueueEmpty(Q)){
  144. 			CSTree e,p;
  145. 			e=(CSTree)malloc(sizeof(CSNode));
  146. 			p=(CSTree)malloc(sizeof(CSNode));
  147. 			DeQueue_Sq(Q,e);
  148. 			p=e->firstchild ;
  149. 			while(p){
  150. 				cout<<p->data<<" ";
  151. 				EnQueue_Sq(Q,p);
  152. 				p=p->rightsib ;
  153. 			}
  154. 		} 
  155. 	}
  156. }
  157.  
  158. //销毁CST
  159. void DestroyTree_CST(CSTree &T){
  160. 	if(T){
  161. 		DestroyTree_CST(T->firstchild );
  162. 		DestroyTree_CST(T->rightsib );
  163. 		free(T);
  164. 		T=NULL;
  165. 	}
  166. } 
  167.  
  168. //主函数 
  169. int main(){
  170. 	CSTree T;
  171. 	InitTree_CST(T);
  172. 	cout<<"Input tree:"<<endl;
  173. 	CreateTree_CST(T);
  174. 	cout<<endl<<"Preordered sequence: ";
  175. 	PreOrderTraverse_CST(T);
  176. 	cout<<endl<<"Midordered sequence: ";
  177. 	MidOrderTraverse_CST(T);
  178. 	cout<<"Floorordered sequence: ";
  179. 	FloorTraverse_CST(T);
  180. 	cout<<endl;
  181. 	DestroyTree_CST(T);
  182. 	return 0;
  183. }

题目2

测试用例及运行结果：

测试用例1：AAABBC

运行结果截图：

 

 

 

 SourceFile.txt内容：

 Code.txt内容：

ResultFile.txt内容：

 

测试用例2：U ARE THE BEST IN MY HEART

运行结果截图：

 

 

 

 

 

 

 

 

SourceFile.txt内容：

Code.txt内容：

 

 ResultFile.txt内容：

 

运行过程：

读取SourceFile.txt文件->统计各个字符出现的频数->基于频数构建Huffman树->基于Huffman树建立Huffman表，即Code.txt文件->基于Huffman表对SourceFile.txt文件进行编码，结果为ResultFile.txt文件。

主要通过终端提示的字母信息进行相应操作。

实验代码：

  1. #include<stdio.h>
  2. #include <malloc.h>
  3. #include <stdlib.h>
  4. #include <string.h>
  5. #define    TRUE    1
  6. #define    FALSE    0
  7. #define    OK        1
  8. #define    ERROR    0
  9. #define    INFEASIBLE    -1
  10. #define    OVERFLOW    -2
  11. typedef int Status;
  12.  
  13. typedef struct HTNode
  14. {
  15. 	char  leaf;
  16. 	unsigned int weight;
  17. 	unsigned int parent, lchild, rchild;
  18. }HTNode, *HuffmanTree;
  19.  
  20. typedef char **HuffmanCode; //动态分配数组存储哈夫曼编码表
  21.  
  22. typedef struct Node
  23. {
  24. 	char leaf;
  25. 	unsigned  int weight;
  26. 	struct Node * next;
  27. }LeafNode, *LeafLink;
  28.  
  29. typedef struct
  30. {
  31. 	LeafLink  head;
  32. 	unsigned  len;
  33. }LeafLinkList;
  34.  
  35. int min1(HuffmanTree t, int i)
  36. { /* 函数void select()调用 */
  37. 	int j, flag;
  38. 	unsigned int k = UINT_MAX; /* 取k为不小于可能的值 */
  39. 	for (j = 1; j <= i; j++)
  40. 		if (t[j].weight<k&&t[j].parent == 0)
  41. 			k = t[j].weight, flag = j;
  42. 	t[flag].parent = 1;
  43. 	return flag;
  44. }
  45.  
  46. void select(HuffmanTree t, int i, int *s1, int *s2)
  47. { /* s1为最小的两个值中序号小的那个 */
  48. 	int j;
  49. 	*s1 = min1(t, i);
  50. 	*s2 = min1(t, i);
  51. 	if (*s1>*s2)
  52. 	{
  53. 		j = *s1;
  54. 		*s1 = *s2;
  55. 		*s2 = j;
  56. 	}
  57. }
  58.  
  59. void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, LeafLinkList L)
  60. { /* w存放n个字符的权值(权值均需大于0),构造哈夫曼树HT,并求出n个字符的哈夫曼编码HC*/
  61. 	int m, i, s1, s2, start;
  62. 	int n = L.len;
  63. 	unsigned c, f;
  64. 	LeafLink ptr;
  65. 	HuffmanTree p;
  66. 	char *cd;
  67. 	if (n <= 1)
  68. 		return;
  69. 	m = 2 * n - 1;
  70. 	printf("表长为%d\t哈夫曼树含节点数为%d\n", n, m);
  71. 	HT = (HuffmanTree)malloc((m + 1)*sizeof(HTNode)); /* 0号单元未用 */
  72. 	ptr = L.head->next;
  73. 	for (p = HT + 1, i = 1; i <= n; ++i, ++p, ptr = ptr->next)
  74. 	{
  75. 		(*p).leaf = ptr->leaf;
  76. 		printf("%d\t", (*p).leaf);
  77. 		(*p).weight = ptr->weight;
  78. 		printf("%d\n", (*p).weight);
  79. 		(*p).parent = 0;
  80. 		(*p).lchild = 0;
  81. 		(*p).rchild = 0;
  82. 	}
  83. 	for (; i <= m; ++i, ++p)
  84. 	{
  85. 		(*p).parent = 0;
  86. 		(*p).leaf = 0;
  87. 	}
  88. 	for (i = n + 1; i <= m; ++i) /* 建哈夫曼树 */
  89. 	{ /* 在HT[1~i-1]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2 */
  90. 		select(HT, i - 1, &s1, &s2);
  91. 		HT[s1].parent = HT[s2].parent = i;
  92. 		HT[i].lchild = s1;
  93. 		HT[i].rchild = s2;
  94. 		HT[i].weight = HT[s1].weight + HT[s2].weight;
  95. 	}
  96. 	/* 从叶子到根逆向求每个字符的哈夫曼编码 */
  97. 	HC = (HuffmanCode)malloc((n + 1)*sizeof(char*));
  98. 	/* 分配n个字符编码的头指针向量([0]不用) */
  99. 	cd = (char*)malloc(n*sizeof(char)); /* 分配求编码的工作空间 */
  100. 	cd[n - 1] = '\0'; /* 编码结束符 */
  101. 	for (i = 1; i <= n; i++)
  102. 	{ /* 逐个字符求哈夫曼编码 */
  103. 		start = n - 1; /* 编码结束符位置 */
  104. 		for (c = i, f = HT[i].parent; f != 0; c = f, f = HT[f].parent)
  105. 			/* 从叶子到根逆向求编码 */
  106. 			if (HT[f].lchild == c)
  107. 				cd[--start] = '0';
  108. 			else
  109. 				cd[--start] = '1';
  110. 		HC[i] = (char*)malloc((n - start)*sizeof(char));
  111. 		/* 为第i个字符编码分配空间 */
  112. 		strcpy(HC[i], &cd[start]); /* 从cd复制编码(串)到HC */
  113. 	}
  114. 	free(cd); /* 释放工作空间 */
  115. 	for (i = 1; i <= n; i++)
  116. 	{
  117. 		printf("%c编码为%s:\n", HT[i].leaf, HC[i]);
  118. 	}
  119. }
  120.  
  121. void InitLeafList(LeafLinkList &L)
  122. {
  123. 	L.head = (LeafLink)malloc(sizeof(LeafLink));
  124. 	L.head->next = NULL;
  125. 	L.len = 0;
  126. }
  127.  
  128. void PrintList(LeafLinkList  L)
  129. {
  130. 	LeafLink  p;
  131. 	p = L.head->next;
  132. 	printf("打印链表\n");
  133. 	printf("表长为%d\n", L.len);
  134. 	while (p != NULL)
  135. 	{
  136. 		printf("%c or %d,%u\t", p->leaf, p->leaf, p->weight);
  137. 		printf("打印一个节点\n");
  138. 		p = p->next;
  139. 	}
  140. 	printf("打印结束\n");
  141. 	printf("\n");
  142. }
  143.  
  144. void EnLeafList(LeafLinkList &L, char ch)
  145. {
  146. 	LeafLink  p, pre, temp;
  147. 	int flag = 0;
  148. 	pre = p = L.head;
  149. 	printf("%d即为%c******\n\n", ch, ch);
  150. 	if (p->next == NULL)    //p->next=NULL则为第一次插入操作
  151. 	{
  152. 		printf("第一次插入\n");
  153. 		temp = (LeafLink)malloc(sizeof(LeafNode));
  154. 		temp->leaf = ch;
  155. 		temp->weight = 1;
  156. 		temp->next = NULL;
  157. 		p->next = temp;
  158. 		L.len++;
  159. 	}
  160. 	else
  161. 	{
  162. 		p = p->next;
  163. 		while (p != NULL)
  164. 		{
  165. 			if (ch == p->leaf)
  166. 			{
  167. 				p->weight++;
  168. 				printf("加权\n");
  169. 				p = NULL;
  170. 				flag = 1;
  171. 			}                                 //权重加一
  172. 			else if (ch<p->leaf)               //插入
  173. 			{
  174. 				printf("插入A\n");
  175. 				temp = (LeafLink)malloc(sizeof(LeafNode));
  176. 				temp->leaf = ch;
  177. 				temp->weight = 1;
  178. 				temp->next = p;
  179. 				pre->next = temp;
  180. 				L.len++;
  181. 				flag = 1;
  182. 				p = NULL;
  183. 			}
  184. 			else                          //继续寻找插入点
  185. 			{
  186. 				pre = p;
  187. 				p = p->next;
  188. 			}
  189. 		}
  190.  
  191. 		if (p == NULL&&flag != 1)  //若p=NULL则插到链尾
  192. 		{
  193. 			printf("插入B\n");
  194. 			temp = (LeafLink)malloc(sizeof(LeafNode));
  195. 			temp->leaf = ch;
  196. 			temp->weight = 1;
  197. 			temp->next = NULL;
  198. 			pre->next = temp;
  199. 			L.len++;
  200. 		}
  201. 	}
  202.  
  203. }
  204.  
  205. void  EnCoding()
  206. {
  207. 	FILE  *fp, *fr, *fc;
  208. 	HuffmanTree HT;
  209. 	HuffmanCode HC;
  210. 	int i, n;
  211. 	LeafLinkList   L;
  212. 	InitLeafList(L);
  213. 	char filename[15];
  214. 	char ch;
  215. 	printf("请输入文件名:\n ");
  216. 	scanf("%s", filename);
  217. 	if (!(fp = fopen(filename, "r")))
  218. 	{
  219. 		printf("打开文件失败，请输入正确的文件名!! ");
  220. 		exit(0);
  221. 	}
  222. 	ch = getchar();             //接收执行scanf语句时最后输入的回车符
  223. 	printf("文件已经打开\n");
  224. 	while (!feof(fp))
  225. 	{
  226.  
  227. 		ch = fgetc(fp);
  228. 		if (ch == -1)
  229. 		{
  230. 			printf("结束统计\n");
  231. 		}
  232. 		else
  233. 		{
  234. 			EnLeafList(L, ch);
  235. 		}
  236. 	}
  237. 	PrintList(L);
  238. 	HuffmanCoding(HT, HC, L);
  239. 	n = L.len;
  240. 	for (i = 1; i <= n; i++)
  241. 	{
  242. 		puts(HC[i]);
  243. 	}
  244. 	char TreeName[15];
  245. 	printf("把哈夫曼树存入文件，请输入文件名:\n ");
  246. 	scanf("%s", TreeName);
  247. 	if (!(fr = fopen(TreeName, "wb")))
  248. 	{
  249. 		printf("打开文件失败，请输入正确的文件名!! ");
  250. 		exit(0);
  251. 	}
  252. 	ch = getchar();     //接收执行scanf语句时最后输入的回车符
  253. 	printf("文件已经打开\n");
  254. 	//把哈夫曼树存入文件
  255. 	printf("%d\n", n);
  256. 	printf("把树的长度先存入\n");
  257. 	_putw(n, fr);      //把树的长度先存入
  258. 	for (i = 1; i <= 2 * n - 1; i++)
  259. 		if (fwrite(&HT[i], sizeof(struct HTNode), 1, fr) != 1)
  260. 			printf("文件写入出错\n");
  261. 	fclose(fr);
  262.  
  263. 	printf("打印原来的树\n");
  264. 	for (i = 1; i <= 2 * n - 1; i++)
  265. 		printf("%c %u  %u  %u %u\n", HT[i].leaf, HT[i].weight, HT[i].parent, HT[i].lchild, HT[i].rchild);
  266. 	fclose(fr);
  267.  
  268. 	printf("把编码结果存入文件，请输入文件名:\n ");
  269. 	char CodeFileName[15];
  270. 	scanf("%s", CodeFileName);
  271. 	if (!(fc = fopen(CodeFileName, "wb")))
  272. 	{
  273. 		printf("打开文件失败，请输入正确的文件名!! ");
  274. 		exit(0);
  275. 	}
  276. 	ch = getchar();        //接收执行scanf语句时最后输入的回车符
  277.  
  278. 	printf("待编码的文件位置指针重新指向开始位置\n");
  279. 	printf("对待编码文件进行编码，编码同步显示，并将结果存入指定的文件\n");
  280. 	rewind(fp);
  281. 	while (!feof(fp))
  282. 	{
  283.  
  284. 		ch = fgetc(fp);
  285. 		printf("%c\n", ch);
  286. 		if (ch == -1)
  287. 		{
  288. 			printf("结束编码\n");
  289. 		}
  290. 		else
  291. 		{
  292. 			for (int tap = 0, i = 1; tap == 0 && i <= n;)        //查找，该叶子对应的编码串
  293. 			{
  294. 				if (ch == HT[i].leaf)                   //找到，打印出对应的编码，并存入文件
  295. 				{
  296. 					printf("%s\n", HC[i]);
  297. 					fputs(HC[i], fc);                   //将编码字符串存入文件
  298.  
  299. 					tap = 1;
  300. 				}
  301. 				else
  302. 				{
  303. 					i++;
  304. 				}
  305. 			}
  306. 		}
  307. 	}
  308. 	fclose(fp);    //关闭文件
  309. 	fclose(fc);    //关闭文件
  310. }
  311.  
  312. int decode(FILE *fc, HuffmanTree HT, int n)
  313. {
  314. 	while (!feof(fc))
  315. 	{
  316. 		char ch = fgetc(fc);
  317. 		if (ch == '0')
  318. 		{
  319. 			n = HT[n].lchild;
  320. 			if (HT[n].leaf != 0)
  321. 			{
  322. 				printf("%c", HT[n].leaf);
  323. 				return OK;
  324. 			}
  325. 			else
  326. 			{
  327. 				decode(fc, HT, n);
  328. 				return OK;
  329. 			}
  330. 		}
  331. 		else if (ch == '1')
  332. 		{
  333. 			n = HT[n].rchild;
  334. 			if (HT[n].leaf != 0)
  335. 			{
  336. 				printf("%c", HT[n].leaf);
  337. 				return OK;
  338. 			}
  339. 			else
  340. 			{
  341. 				decode(fc, HT, n);
  342. 				return OK;
  343. 			}
  344. 		}
  345. 		else return OK;
  346. 	}
  347. 	return ERROR;
  348. }
  349.  
  350. //解码文件
  351. void Decoding()                             
  352. {
  353. 	FILE *fc, *fr;
  354. 	char CodeFileName[15], ch, TreeName[15];
  355. 	int i;
  356. 	printf("解码文件，请输入文件名(如*.dat):\n ");
  357. 	scanf("%s", CodeFileName);
  358. 	if (!(fc = fopen(CodeFileName, "r")))
  359. 	{
  360. 		printf("打开文件失败，请输入正确的文件名!! ");
  361. 		exit(0);
  362. 	}
  363. 	ch = getchar();     //接收执行scanf语句时最后输入的回车符
  364. 	printf("存放编码结果文件已经打开\n");
  365.  
  366. 	//读入哈夫曼树
  367. 	HuffmanTree HT;
  368. 	printf("取出对应的哈夫曼树文件，请输入文件名,\n");
  369. 	scanf("%s", TreeName);
  370. 	if (!(fr = fopen(TreeName, "rb")))         //打开存放哈夫曼树的文件
  371. 	{
  372. 		printf("打开文件失败，请输入正确的文件名!! ");
  373. 		exit(0);
  374. 	}
  375. 	int  n = _getw(fr);                  //将叶子数目取出
  376. 	printf("叶子数目%d\n", n);
  377. 	HT = (HuffmanTree)malloc((2 * n)*sizeof(HTNode));           /* 然后分配空间，0号单元未用 */
  378.  
  379. 	for (i = 1; i <= 2 * n - 1; i++)
  380. 		if (fread(&HT[i], sizeof(struct HTNode), 1, fr) != 1)
  381. 			printf("文件读出出错\n");
  382. 	int length = 2 * n - 1;     //总长度
  383. 	printf("总结点数目为：%d\n", n);
  384. 	printf("该文件译码后得到的源文件为：\n");
  385. 	printf("**************************************\n");
  386. 	while (!feof(fc))
  387. 	{
  388. 		decode(fc, HT, length);
  389. 	}
  390. 	printf("**************************************\n");
  391. 	printf("\n\n");
  392. }
  393.  
  394. int PreOrderPrint(HuffmanTree HT, int n, int count)
  395. {
  396. 	if (HT[n].lchild)
  397. 	{
  398. 		for (int i = 0; i<count; i++)
  399. 			printf("   ");
  400. 		printf("%u\n", HT[n].weight);
  401. 		if (PreOrderPrint(HT, HT[n].lchild, ++count))
  402. 			if (PreOrderPrint(HT, HT[n].rchild, ++count))
  403. 				return OK;
  404. 		return ERROR;
  405. 	}
  406. 	else return OK;
  407. }
  408.  
  409. void PrintTree()
  410. {
  411. 	//读入哈夫曼树
  412. 	FILE *fr;
  413. 	char TreeName[15];
  414. 	HuffmanTree HT;
  415. 	printf("取出对应的哈夫曼树文件(如*.dat)，请输入文件名,\n");
  416. 	scanf("%s", TreeName);
  417. 	if (!(fr = fopen(TreeName, "rb")))         //打开存放哈夫曼树的文件
  418. 	{
  419. 		printf("打开文件失败，请输入正确的文件名!! ");
  420. 		exit(0);
  421. 	}
  422. 	int  n = _getw(fr);                  //将叶子数目取出
  423. 	printf("含叶子数%d\n", n);
  424. 	HT = (HuffmanTree)malloc((2 * n)*sizeof(HTNode));           /* 然后分配空间，0号单元未用 */
  425. 	for (int i = 1; i <= 2 * n - 1; i++)
  426. 		if (fread(&HT[i], sizeof(struct HTNode), 1, fr) != 1)
  427. 			printf("文件读出出错\n");
  428. 	int	count = 0;
  429. 	n = 2 * n - 1;
  430. 	printf("总结点数目为；%d\n", n);
  431. 	printf("哈夫曼树的存储形式为：\n");
  432. 	for (int i = 1; i <= n; i++)
  433. 	{
  434. 		printf("%c,%u,%u,%u,%u\n", HT[i].leaf, HT[i].weight, HT[i].parent, HT[i].lchild, HT[i].rchild);
  435. 	}
  436. 	printf("哈夫曼树的凹入表形式为：\n");
  437. 	PreOrderPrint(HT, n, count);
  438. }
  439.  
  440. void PrintCodeFile()
  441. {
  442. 	FILE *fc;
  443. 	printf("打印编码后的文件，请输入文件名(如*.dat):\n ");
  444. 	char CodeFileName[15];
  445. 	scanf("%s", CodeFileName);
  446. 	if (!(fc = fopen(CodeFileName, "r")))
  447. 	{
  448. 		printf("打开文件失败，请输入正确的文件名!! ");
  449. 		exit(0);
  450. 	}
  451. 	char ch = getchar();     //接收执行scanf语句时最后输入的回车符
  452. 	printf("打印编码后的文件，打印方法一\n");
  453. 	int flag = 1;
  454. 	while (!feof(fc))
  455. 	{
  456. 		ch = fgetc(fc);
  457. 		if (ch == -1)
  458. 		{
  459. 			printf("结束打印\n");
  460. 		}
  461. 		else
  462. 		{
  463. 			printf("%c", ch);
  464. 			if (flag <= 49)
  465. 				flag++;
  466. 			else
  467. 			{
  468. 				flag = 1;
  469. 				printf("\n");
  470. 			}
  471. 		}
  472. 	}
  473. 	printf("打印编码后的文件，打印方法二\n");
  474. 	rewind(fc);
  475. 	char str[50];
  476. 	while (!feof(fc))
  477. 	{
  478. 		fgets(str, 51, fc);
  479. 		puts(str);
  480. 	}
  481. 	fclose(fc);        //关闭文件
  482. }
  483.  
  484. //系统初始化
  485. void Initialization()                    
  486. {
  487. 	printf("**************************************\n");
  488. 	printf("*编码文件请输入e\n*译码文件请输入d\n*打印编码后的文件请输入p\n*打印哈夫曼树请输入t\n*结束请输入q \n");
  489. 	printf("**************************************\n");
  490. 	printf("\n\n\t\t字符:\n\n\n");
  491. 	printf("**************************************\n");
  492. 	printf("* 输入一个字符:e,d,p,t or q *\n");
  493. 	printf("**************************************\n");
  494. }
  495.  
  496. int read(char cmd)
  497. {
  498. 	int i, flag = 0;
  499. 	char choice[10] = { 'e', 'E', 'd', 'D', 'p', 'P', 'T', 't', 'Q', 'q' };
  500. 	for (i = 0; i<10; i++){
  501. 		if (cmd == choice[i])  flag++;
  502. 	}
  503. 	if (flag == 1)     return FALSE;
  504. 	else return TRUE;
  505. }
  506.  
  507. // 读入操作命令符
  508. void ReadCommand(char &cmd)                   
  509. {
  510. 	do{
  511. 		cmd = getchar();
  512. 	} while (read(cmd));
  513. }
  514.  
  515. //解释执行操作命令
  516. void Interpret(char cmd)                    
  517. {
  518. 	switch (cmd)
  519. 	{
  520. 	case 'e':
  521. 	case'E':
  522. 		EnCoding();
  523. 		Initialization();
  524. 		break;
  525. 	case 'd':
  526. 	case'D':
  527. 		Decoding();
  528. 		Initialization();
  529. 		break;
  530. 	case 'p':
  531. 	case'P':
  532. 		PrintCodeFile();
  533. 		Initialization();
  534. 		break;
  535. 	case't':
  536. 	case'T':
  537. 		PrintTree();            
  538. 		Initialization();
  539. 		break;
  540. 	case 'q':
  541. 	case'Q':
  542. 		exit(0);
  543. 		break;
  544. 	default:
  545. 		printf("Error\n");
  546. 		break;
  547. 	}
  548. }
  549.  
  550. //主程序
  551. int main()         
  552. {
  553. 	char cmd;
  554. 	Initialization();   //初始化
  555. 	do{
  556. 		ReadCommand(cmd);     //读入一个操作命令符
  557. 		Interpret(cmd);       //解释执行操作命令符
  558. 	}while(cmd != 'q'&&cmd != 'Q');
  559. 	EnCoding();
  560. 	Decoding();
  561. 	return 0; 
  562. }

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

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

  

闽ICP备14008679号