哈夫曼编码解码的实现及运行截图C语言

哈夫曼编码解码的实现及运行截图（C语言编写）

// HafuManCode.cpp : 定义控制台应用程序的入口点。
//

#include “stdafx.h“



#include
#include
#include 
using namespace std;
#define n 5  //叶子数目
#define m （2*n-1）    //结点总数
#define maxval 10000.0
#define maxsize 100   //哈夫曼编码的最大位数
typedef struct
{
	char ch;
	int weight;
	int lchildrchildparent;
}hufmtree;
typedef struct
{
	char bits[n];   //位串
	int start;      //编码在位串中的起始位置
	char ch;        //字符
}codetype;
void huffman（hufmtree tree[]）;//建立哈夫曼树
void huffmancode（codetype code[]hufmtree tree[]）;//根据哈夫曼树求出哈夫曼编码
void encode（codetype code[]char string[]）;//电文编码
void decode（hufmtree tree[]）;//依次读入电文，根据哈夫曼树译码
void main（）
{
	printf（“                            ——哈夫曼编码——\n“）;
	printf（“总共有%d个字符\n“n）;
	hufmtree tree[m];
	codetype code[n];
	int ij;//循环变量
	huffman（tree）;//建立哈夫曼树
	huffmancode（codetree）;//根据哈夫曼树求出哈夫曼编码
	printf（“【输出每个字符的哈夫曼编码】\n“）;
	for（i=0;i	{
		printf（“%c: “code[i].ch）;
		for（j=code[i].start;j			printf（“%c “code[i].bits[j]）;
		printf（“\n“）;
	}
	printf（“【读入原文，并进行编码】\n“）;
	char string[maxsize];
	gets（string）;
	encode（codestring）;

	printf（“【读入电文，并进行译码】\n“）;
	decode（tree）;//依次读入电文，根据哈夫曼树译码
	getchar（）;
}
void huffman（hufmtree tree[]）//建立哈夫曼树
{
	int ijp1p2;//p1p2分别记住每次合并时权值最小和次小的两个根结点的下标
	int small1small2f;
	char c;
	for（i=0;i	{
		tree[i].parent=0;
		tree[i].lchild=-1;
		tree[i].rchild=-1;
		tree[i].weight=0;
	}
	printf（“【依次读入前%d个结点的字符及权值（中间用空格隔开）】\n“n）;
	for（i=0;i	{
		printf（“输入第%d个字符为和权值“i+1）;
		scanf（“%c %d“&c&f）;
		getchar（）;
		tree[i].ch=c;
		tree[i].weight=f;
	}
	for（i=n;i	{
		p1=0;p2=0;
		small1=9999;small2=9999;   //maxval是float类型的最大值
		for（j=0;j			if（tree[j].parent==0）
				if（tree[j].weight				{
					small2=small1;  //改变最小权、次小权及对应的位置
					small1=tree[j].weight;
					p2=p1;
					p1=j;
				}
				else
					if（tree[j].weight					{
						small2=tree[j].weight;  //改变次小权及位置
						p2=j;
					}
					tree[p1].parent=i;
					tree[p2].parent=i;
					tree[i].lchild=p1;  //最小权根结点是新结点的左孩子
					tree[i].rchild=p2;  //次小权根结点是新结点的右孩子
					tree[i].weight=tree[p1].weight+tree[p2].weight;
	}
}//huffman
void huffmancode（codetype code[]hufmtree tree[]）//根据哈夫曼树求出哈夫曼编码
	//codetype code[]为求出的哈夫曼编码
	//hufmtree tree[]为已知的哈夫曼树
{
	int icp;
	codetype cd;   //缓冲变量
	for（i=0;i	{
		cd.start=n;
		cd.ch=tree[i].ch;
		c=i;       //从叶结点出发向上回溯
		p=tree[i].parent;   //tree[p]是tree[i]的双亲
		while（p!=0）
		{
			cd.start--;
			if（tree[p].lchild==c）
				cd.bits[cd.start]=‘0‘;   //tree[i]是左子树，生成代码‘0‘
			else
				cd.bits[cd.start]=‘1‘;   //tree[i]是右子树，生成代码‘1‘
			c=p;
			p=tree[p].parent;
		}
		code[i]=cd;    //第i+1个字符的编码存入code[i]
	}
}//huffmancode
void encode（codetype code[]char string[]）
{
	printf（“【输出编码结果】\n“）;
	int length=strlen（string）;

	for（int k=0;k	{
		f

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       4286  2015-11-01 16:39  HafuManCode.cpp

     文件      43740  2015-11-01 16:38  运行结果.png

----------- ---------  ---------- -----  ----

                48026                    2