第六天-------哈夫曼编码附源码

忘是亡心i 2022-05-21 09:54 111阅读 0赞

**一、 目的**

1.掌握哈夫曼树和哈夫曼编码的基本思想和算法的程序实现。

**二、内容**

1、内容

（1）修理牧场：农夫要修理牧场的一段栅栏，他测量了栅栏，发现需要N块木头，每块木头长度为整数Li个长度单位，于是他购买了一条很长的、能锯成N块的木头，即该木头的长度是Li的总和。

但是农夫自己没有锯子，请人锯木头的酬金跟这段木头的长度成正比。为简单起见，不妨就设酬金等于所锯木头的长度。例如，要将长度为20的木头锯成长度为8、7和5的三段，第一次锯木头花费20，将木头锯成12和8；第二次锯木头花费12，将长度为12的木头锯成7和5，总花费为32。如果第一次将木头锯成15和5，则第二次锯木头花费15，总花费为35（大于32）。

请编写程序帮助农夫计算将木头锯成N块的最少花费。

首先输入一个正整数N（N≤104），表示要将木头锯成N块。接着给出N个正整数Li（Li≤50），表示每段木块的长度。输出一个整数，即将木头锯成N块的最少花费。

例如：

输入：

4 5 1 2 1 3 1 1

输出：

\*（2）压缩软件：

给定一篇文章，只含有英文大小写字母和空格，以.txt格式存储，统计该文件中各种字符的频率，对各字符进行Huffman编码，将该文件翻译成Huffman编码文件，再将Huffman编码文件翻译成源文件。

2、主要数据类型与变量

（**必要时，可对数据类型和变量进一步解释或说明，增加可读性**）

1．参考类型定义   //双亲孩子表示法

typedef struct \{

unsignedint  weight;

unsigned int  parent, lchild, rchild;

\} HTNode, \*HuffmanTree;      //动态分配数组存储哈夫曼树

typedef char \* \* HuffmanCode;  //动态分配数组存储哈夫曼编码表

3、算法思想描述

构建哈夫曼树，获得哈夫曼编码。

**三、系统测试**

1、测试方案

测试，最开始并没有用读入文件的操作，只是从控制台输入几个字符，如下：

后来，在别人的帮助下开始读取文件的操作，并成功运行。

2、测试结果

第一次读取文件的时候，在命令行上并没有出现哈夫曼编码，只是将1.txt文件中的字符串输出了。

不过在1.txt中已经将哈夫曼编码写入

第二次执行程序的时候，直接在命令行中输出了字符串的编码

文件中又被写入了一次

**附：程序源代码**

** **

**源代码：**

**DS.h**

** **

\#include <stdio.h>

\#include <stdlib.h>

\#include <string.h>

\#include <math.h>

\#define TRUE 1

\#define FALSE 0

\#define OK 1

\#define ERROR 0

** **

**typedef int Status;**

**HfmTree.h**

\#include "DS.h"

typedef int TElemType;

typedef struct \{

int  weight;                  //权值

int  parent, lchild, rchild;  //有无父节点，左孩子，右孩子

\} HTNode, \*HuffmanTree;            //动态分配数组存储哈夫曼树

typedef char \* \* HuffmanCode;      //动态分配数组存储哈夫曼编码表

void HuffmanCoding(HuffmanTree&HT,HuffmanCode &HC,int \*w, int n);   //构建哈夫曼树，求出哈夫曼编码

void Select(HuffmanTree HT,int n,int&s1, int &s2);                  //选择两个权值最小的节点

void outputfile(HuffmanCode HC,int n,char\*a);                        //字符输出

void inputfile(char \*str);                                            //字符读入

void Huffmans (int w\[\],char \*str,int&n,char\*a);                      //统计文件中各字符的个数

**main.cpp**

\#include "HfmTree.h"

int main()

HuffmanTree HT;

HuffmanCode HC;      //定义哈夫曼树与哈夫曼编码

char str\[99999\],a\[60\];

int w\[60\];

int n;

inputfile(str);           //读入字符串

printf("%s\\n",str);      //将读取到的字符串输出

Huffmans(w,str,n,a);      //统计该字符串中各字符的次数

HuffmanCoding(HT,HC,w,n); //对这些字符进行编码

printf("\\n");

outputfile(HC, n,a);      //将哈夫曼编码输出带文件中

return 0;

**HfmTree.cpp**

\#include "HfmTree.h"

void HuffmanCoding(HuffmanTree&HT,HuffmanCode &HC,int \*o, int n)\{

char \* cd;

int m ,c,f,k=0,start,i,s1,s2;

int w\[60\];

for(i=0;i<60;i++)\{

w\[i\] = 0;

for(i = 0; i<60; i++)\{

if(o\[i\] != 0)\{

w\[k\] = o\[i\];

k++;

if(n<-1) return;

m= 2 \* n - 1;

HT= (HuffmanTree)malloc((m+1)\*sizeof(HTNode));

for( i=1; i<=n; ++i) \{

HT\[i\].weight=w\[i-1\] ;HT\[i\].parent = 0; HT\[i\].lchild = 0; HT\[i\].rchild =0;

for(;i<=m;++i) \{

HT\[i\].weight=0 ;HT\[i\].parent = 0; HT\[i\].lchild = 0; HT\[i\].rchild = 0;

for(i =n+1; i<=m; ++i)\{

Select(HT,i-1,s1,s2);

HT\[s1\].parent =i ; HT\[s2\].parent = i;

HT\[i\].lchild = s1 ; HT\[i\].rchild = s2;

HT\[i\].weight = HT\[s1\].weight+HT\[s2\].weight;

printf("\\n");

HC= (HuffmanCode)malloc((n+1)\*sizeof(char \*));

cd= (char \*)malloc(n\*sizeof(char));

cd\[n-1\] = '\\0';

for(i=1;i<=n;++i)\{

start = n-1;

for(c=i, f = HT\[i\].parent;f!=0 ; c = f, f = HT\[f\].parent)\{

if(HT\[f\].lchild == c)

cd\[ --start \] = '0';

else

cd\[ --start \] = '1';

HC\[i\] = (char \*) malloc((n-start) \* sizeof(char));

strcpy(HC\[i\],&cd\[start\]);

free(cd);

//选择两个权值最小的节点

void Select(HuffmanTree HT,int n,int&s1, int &s2)\{

int i ,w;

s1= s2 = 1;

//选出第一个权值最小的节点

w=100000;

for( i=1 ;i<=n;i++)\{

if(HT\[i\].parent == 0 && w > HT\[i\].weight)\{

w  = HT\[i\].weight;

s1 = i ;

//将权值初始值w重置最大，选出第二个权值最小的节点

w=100000;

for( i=1 ;i<=n;i++)\{

if(HT\[i\].parent == 0  && w>HT\[i\].weight && i != s1 )\{

w  = HT\[i\].weight;

s2 = i ;

//统计字符串str中各字符的个数

void Huffmans (int w\[\],char \*str,int&n,char \*a)\{

int i,j;

n=0;

//将个数初始化为0

for(j=0; j<60;j++)\{

w\[j\] = 0;

//遍历

for(i=0; str\[i\]!='\\0'; i++)\{

if(str\[i\]  ==' ')\{

w\[52\]++;

\}else\{

w\[str\[i\]-65\]++;

for(i=0;i<60;i++)\{

if(w\[i\]!=0) n++;

j=0;

for(i=0;i<60;i++)\{

if(w\[i\] != 0)\{

if(i == 52)

a\[j\] = ' ';

else

a\[j\] = i+65;

j++;

printf("\\n");

//从1.txt中读取字符串

voidinputfile(char \*str)\{

int index  = 0;

char ch;

FILE \*fp;

fp = fopen("1.txt","r");

while((ch = fgetc(fp)) != EOF)\{

str\[index++\] = ch;

str\[index\] = '\\0';

fclose(fp);

//将编码后的字符写入到文件中

voidoutputfile(HuffmanCode HC,int n,char \*a)\{

FILE \*fp;

int i,j;

fp = fopen("1.txt", "a+");

if (fp==0) \{

printf("不能打开文件\\n"); return ;

fseek(fp, 0, SEEK\_END);        //设置文件指针

for(i=1 ; i<=n;i++)\{

fprintf(fp,"\\n");

fprintf(fp,"%c的编码: ",a\[i-1\]);

for(j=0; j<n; j++)\{

if(HC\[i\]\[j\] == '0' || HC\[i\]\[j\] == '1')\{

fprintf(fp,"%c ",HC\[i\]\[j\]);

fclose(fp);

第六天-------哈夫曼编码附源码

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关哈夫曼树、哈夫曼编码详解

相关哈夫曼编码

相关哈夫曼树与哈夫曼编码

相关哈夫曼树和哈夫曼编码

相关哈夫曼编码

相关第六天-------哈夫曼编码附源码

相关哈夫曼编码

相关哈夫曼编码

相关哈夫曼编码

相关哈夫曼编码