哈夫曼编码和译码系统 数据结构实验题目 急求!!!!!
这个有个Huffman编码与解码的网页链接,有详细文档和源码~也可以在这个网站上面搜索,刚才也搜到很多关于Huffman程序源码和开发文档,一个干货满满的博客
#include
#include
#include
#include
#include
#include
#define INF 10000
using namespace std;
//------哈夫曼树的存储表示------
typedef struct
{
char data; //结点的字符
int weight; //结点的权值
int parent,lchild,rchild; //结点的双亲,左孩子,右孩子下标
}HTNode,*HFMTree;
HFMTree HT;
//------哈夫曼编码表的存储表示------
typedef char** HFMcode; //动态分配数组存储哈夫曼编码表
HFMcode HC;
int N; //字符集个数
//函数声明
void hello(); //欢迎界面
void func(); //具体功能函数
void initHFM(HFMTree &,int); //构造哈夫曼树
void select(HFMTree,int,int&); //构造哈弗曼树的子函数--选择结点
void creatHFMcode(HFMTree,HFMcode &,int); //求哈夫曼编码
void add_code_to_file(HFMTree,HFMcode,int); //将初始哈夫曼编码存入文件hfmTree中
void Encoding(); //编码
void Decoding(); //译码
void Print(); //显示编码
//函数定义
void hello()
{
cout<<"*****该系统可实现如下功能*****
"
<<"I.初始化构造哈夫曼树和哈弗曼编码并存在文件中
"
<<"E.利用已建好的哈夫曼树对文件中的正文进行编码
"
<<"D.利用已建好的哈夫曼树将文件中的代码进行译码
"
<<"P.将编码文件显示在终端上面并保存在文件中
"
<<"T.打印哈弗曼树
"
<<"O.退出系统"<<endl;
func();
}
void func()
{
cout<<"输入相应字母,实现对应功能:";
char c;
cin>>c;
switch(c)
{
case'I':case'i':cout>N;initHFM(HT,N);break;
case'E':case'e':Encoding();break;
case'D':case'd':Decoding();break;
case'P':case'p':Print();break;
case'T':case't':;
case'O':case'o':case'0':exit(0);
default:cout<<"输入有误,请重新输入
";
func();break;
}
}
void initHFM(HFMTree &HT,int n)
{//构造哈弗曼树和哈弗曼编码
if(n<=1)
{
cerr<<"构造失败,请继续操作"<<endl;
hello();
}
int m=2*n-1;
HT=new HTNode[m+1]; //0号单元未用,所以需要动态分配m+1个二单元
for(int i=1;i<=m;i++)
HT[i].lchild=HT[i].parent=HT[i].rchild=0;
cout<<"请输入前"<<n<<"个单元叶子结点的字符:";
getchar();
for(int i=1;i<=n;i++)
HT[i].data=getchar(); //输入前n个单元叶子结点的字符
cout<<"请输入前"<<n<<"个单元叶子结点的权值:";
getchar();
for(int i=1;i<=n;i++)
cin>>HT[i].weight; //输入前n个单元叶子结点的权值
for(int i=n+1;i<=m;i++)
{//用过n-1次的选择,删除,合并来创建哈夫曼树
int s1,s2;
select(HT,i-1,s1);select(HT,i-1,s2);
//在HT[k](1<=k<=i-1)中选择两个其双亲域为0且权值最小的点,并返回他们的序号s1,s2
HT[i].lchild=s1;HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
creatHFMcode(HT,HC,n); //求哈夫曼编码
add_code_to_file(HT,HC,n); //将初始哈夫曼编码存入文件中
cout<<"构造成功,请继续操作
";
hello();
}
void select(HFMTree HT,int x,int &s)
{
int minn=INF;
for(int j=1;j<=x;j++)
{
if(HT[j].parent)
continue;
else
{
if(minn>HT[j].weight)
{
minn=HT[j].weight;
s=j;
}
}
}
HT[s].parent=x+1;
}
void creatHFMcode(HFMTree HT,HFMcode &HC,int n)
{//从叶子到根逆向求每个字符的哈夫曼编码,存储在编码表HC中
HC=new char*[n+1]; //分配存储n个字符编码的动态数组空间
char *cd=new char[n]; //分配临时存放每个字符编码的动态数组空间
cd[n-1]='\0'; //编码结束符
for(int i=1;i<=n;i++) //逐个字符求哈夫曼编码
{
int start=n-1; //start开始时指向最后,及编码结束符位置
int c=i,f=HT[i].parent; //f指向c的双亲结点
while(f!=0)
{
--start;
if(HT[f].lchild==c)
cd[start]='0';
else cd[start]='1';
c=f;
f=HT[f].parent;
}
HC[i]=new char[n-start];
strcpy(HC[i],&cd[start]);
}
delete cd;
}
void add_code_to_file(HFMTree HT,HFMcode HC,int n)
{//将初始哈夫曼编码存入文件hfmTree中
ofstream out;
out.open("hfmTree.txt",ios::out);
out<<left;
out<<setw(4)<<"字符"<<':'<<"编码"<<endl;
for(int i=1;i<=n;i++)
out<<' '<<HT[i].data<<" :"<<HC[i]<<'
';
out.close();
}
void Encoding()
{
ofstream out1;
out1.open("ToBeTran.txt",ios::out);
out1<<"THIS PROGRAM IS MY FAVORITE";
out1.close();
ifstream in;
in.open("ToBeTran.txt",ios::in);
char str[1000];
in.getline(str,999);
ofstream out2;
out2.open("CodeFile.txt",ios::out);
for(int i=0;str[i]!='\0';i++)
{
for(int j=1;j<=N;j++)
{
if(str[i]==HT[j].data)
{out2<<HC[j];out2<<' ';}
}
}
out2.close();
in.close();
cout<<"编码成功,请继续操作
";
hello();
}
void Decoding()
{
ifstream in;
in.open("CodeFile.txt",ios::in);
char str[1000];
in.getline(str,999);
for(int i=0;str[i]!='\0';)
{
char s[N];
int j=i;
int t=0;
while(str[j]!=' ')
{
s[t]=str[j];
t++;
j++;
i++;
}
s[t]='\0';
//cout<<s<<' ';
for(int x=1;x<=N;x++)
if(strcmp(s,HC[x])==0)
cout<<HT[x].data;
i++;
}
in.close();
cout<<"
译码成功,请继续操作
";
hello();
}
void Print()
{
ifstream in;
in.open("CodeFile.txt",ios::in);
char str[1000];
in.getline(str,999);
ofstream out;
out.open("CodePrin.txt",ios::out);
int t=0;
for(int i=0;str[i]!='\0';i++)
{
if(str[i]!=' ')
{
cout<<str[i];
t++;
out<<str[i];
if(t%50==0)
cout<<'
';
}
}
in.close();
out.close();
cout<<"
显示完毕并保存成功,请按回车键继续操作
";
getchar();getchar();
hello();
}
int main()
{
hello();
return 0;
}
#include <stdlib.h>
#include <string.h>
#define N 100
#define M 2*N-1
typedef char * HuffmanCode[2*M];//haffman编码
typedef struct
{
int weight;//权值
int parent;//父节节点
int LChild;//左子节点
int RChild;//右子节点
}HTNode,Huffman[M+1];//huffman树
typedef struct Node
{
int weight; //叶子结点的权值
char c; //叶子结点
int num; //叶子结点的二进制码的长度
}WNode,WeightNode[N];
/***产生叶子结点的字符和权值***/
void CreateWeight(char ch[],int *s,WeightNode CW,int *p)
{
int i,j,k;
int tag;
*p=0;//叶子节点个数
//统计字符出现个数,放入CW
for(i=0;ch[i]!='\0';i++)
{
tag=1;
for(j=0;j<i;j++)
if(ch[j]==ch[i])
{
tag=0;
break;
}
if(tag)
{
CW[++*p].c=ch[i];
CW[*p].weight=1;
for(k=i+1;ch[k]!='\0';k++)
if(ch[i]==ch[k])
CW[*p].weight++;//权值累加
}
}
*s=i;//字符串长度
}
/********创建HuffmanTree********/
void CreateHuffmanTree(Huffman ht,WeightNode w,int n)
{
int i,j;
int s1,s2;
//初始化哈夫曼树
for(i=1;i<=n;i++)
{
ht[i].weight =w[i].weight;
ht[i].parent=0;
ht[i].LChild=0;
ht[i].RChild=0;
}
for(i=n+1;i<=2*n-1;i++)
{
ht[i].weight=0;
ht[i].parent=0;
ht[i].LChild=0;
ht[i].RChild=0;
}
for(i=n+1;i<=2*n-1;i++)
{
for(j=1;j<=i-1;j++)
if(!ht[j].parent)
break;
s1=j; //找到第一个双亲不为零的结点
for(;j<=i-1;j++)
if(!ht[j].parent)
s1=ht[s1].weight>ht[j].weight?j:s1;
ht[s1].parent=i;
ht[i].LChild=s1;
for(j=1;j<=i-1;j++)
if(!ht[j].parent)
break;
s2=j; //找到第二个双亲不为零的结点
for(;j<=i-1;j++)
if(!ht[j].parent)
s2=ht[s2].weight>ht[j].weight?j:s2;
ht[s2].parent=i;
ht[i].RChild=s2;
ht[i].weight=ht[s1].weight+ht[s2].weight;//权值累加
}
}
/***********叶子结点的编码***********/
void CrtHuffmanNodeCode(Huffman ht,char ch[],HuffmanCode h,WeightNode weight,int m,int n)
{
int i,c,p,start;
char *cd;
cd=(char *)malloc(n*sizeof(char));
cd[n-1]='\0';//末尾置0
for(i=1;i<=n;i++)
{
start=n-1; //cd串每次从末尾开始
c=i;
p=ht[i].parent;//p在n+1至2n-1
while(p) //沿父亲方向遍历,直到为0
{
start--;//依次向前置值
if(ht[p].LChild==c)//与左子相同,置0
cd[start]='0';
else //否则置1
cd[start]='1';
c=p;
p=ht[p].parent;
}
weight[i].num=n-start; //二进制码的长度(包含末尾0)
h[i]=(char *)malloc((n-start)*sizeof(char));
strcpy(h[i],&cd[start]);//将二进制字符串拷贝到指针数组h中
}
free(cd);//释放cd内存
system("pause");
}
/*********所有字符的编码*********/
void CrtHuffmanCode(char ch[],HuffmanCode h,HuffmanCode hc,WeightNode weight,int n,int m)
{
int i,k;
for(i=0;i<m;i++)
{
for(k=1;k<=n;k++) /*从weight[k].c中查找与ch[i]相等的下标K*/
if(ch[i]==weight[k].c)
break;
hc[i]=(char *)malloc((weight[k].num)*sizeof(char));
strcpy(hc[i],h[k]); //拷贝二进制编码
}
}
/*****解码*****/
void TrsHuffmanTree(Huffman ht,WeightNode w,HuffmanCode hc,int n,int m)
{
int i=0,j,p;
printf("***StringInformation***\n");
while(i<m)
{
p=2*n-1;//从父亲节点向下遍历直到叶子节点
for(j=0;hc[i][j]!='\0';j++)
{
if(hc[i][j]=='0')
p=ht[p].LChild;
else
p=ht[p].RChild;
}
printf("%c",w[p].c); /*打印原信息*/
i++;
}
}
/*****释放huffman编码内存*****/
void FreeHuffmanCode(HuffmanCode h,HuffmanCode hc,int n,int m)
{
int i;
for(i=1;i<=n;i++)//释放叶子结点的编码
free(h[i]);
for(i=0;i<m;i++) //释放所有结点的编码
free(hc[i]);
}
void main()
{
int i,n=0; /*n为叶子结点的个数*/
int m=0; /*m为字符串ch[]的长度*/
char ch[N]; /*ch[N]存放输入的字符串*/
Huffman ht; /*Huffman二叉数 */
HuffmanCode h,hc; /*h存放叶子结点的编码,hc 存放所有结点的编码*/
WeightNode weight; /*存放叶子结点的信息*/
printf("\t***HuffmanCoding***\n");
printf("please input information :");
gets(ch); /*输入字符串*/
CreateWeight(ch,&m,weight,&n); /*产生叶子结点信息,m为字符串ch[]的长度*/
printf("***WeightInformation***\n Node ");
for(i=1;i<=n;i++) /*输出叶子结点的字符与权值*/
printf("%c ",weight[i].c);
printf("\nWeight ");
for(i=1;i<=n;i++)
printf("%d ",weight[i].weight);
CreateHuffmanTree(ht,weight,n); /*产生Huffman树*/
printf("\n***HuffamnTreeInformation***\n");
printf("\ti\tweight\tparent\tLChild\tRChild\n");
for(i=1;i<=2*n-1;i++) /*打印Huffman树的信息*/
printf("\t%d\t%d\t%d\t%d\t%d\n",i,ht[i].weight,ht[i].parent,ht[i].LChild,ht[i].RChild);
CrtHuffmanNodeCode(ht,ch,h,weight,m,n); /*叶子结点的编码*/
printf(" ***NodeCode***\n"); /*打印叶子结点的编码*/
for(i=1;i<=n;i++)
{
printf("\t%c:",weight[i].c);
printf("%s\n",h[i]);
}
CrtHuffmanCode(ch,h,hc,weight,n,m); /*所有字符的编码*/
printf("***StringCode***\n"); /*打印字符串的编码*/
for(i=0;i<m;i++)
printf("%s",hc[i]);
system("pause");
TrsHuffmanTree(ht,weight,hc,n,m); /*解码*/
FreeHuffmanCode(h,hc,n,m);
system("pause");
}
我这里有详细的设计,说明,流程图和源代码,
给个邮箱,我发给你
=========================================
已经发给你了.看看是否符合要求
哈夫曼编码和译码怎么算
统计字符出现的频率:首先需要统计待编码的字符在文本中出现的频率。构建哈夫曼树:根据字符频率构建哈夫曼树,频率越高的字符离根节点越近。分配编码:从根节点开始,向左走为0,向右走为1,将每个字符分配一个唯一的二进制编码。生成编码表:将每个字符及其对应的编码记录在编码表中。2 哈夫曼译码:根...
数据结构(C语言)-哈夫曼(Huffman)树编码译码操作
编码过程涉及编写encoding函数,将原始输入字符串转换为Huffman编码串,译码方法的时间复杂度为O(n)。下面是一个简化的C语言实现步骤:定义顺序存储的哈夫曼结点和编码数组统计字符频次合并频率最低的结点,形成新结点重复合并直至生成哈夫曼树使用队列进行递归遍历哈夫曼树生成编码实现encoding函数进行编码转换编...
哈夫曼编码与译码(C语言版)
在一次实验课程中,我被要求实现哈夫曼树、哈夫曼编码与译码的C语言版本。代码虽然在当时时间紧迫下完成,但仍有优化空间。重要的是,我处理的是基于频率统计的变长编码,即哈夫曼编码,它利用哈夫曼树将高频字符编码成短码,低频字符编码成长码,以实现数据压缩。实验内容包括统计字符频率、构建哈夫曼树、...
哈夫曼编码\/译码器
void Decoding(HuffmanTree HT, char ch[] , int n){ \/\/对指定的存储由赫夫曼编码表示的信息的文件进行译码,翻译成相应的字符表示,并存储到指定文件 int p,i = 1; char code[1000],c; char CodeFile_Name[100],TextFile_Name[100]; \/\/存储用户指定文件的文件名 p = 2 * n - 1; FILE *CodeFile...
哈夫曼编码器与译码器
void Decoding(HuffmanTree HT, char ch[] , int n){ \/\/对指定的存储由赫夫曼编码表示的信息的文件进行译码,翻译成相应的字符表示,并存储到指定文件 int p,i = 1; char code[1000],c; char CodeFile_Name[100],TextFile_Name[100]; \/\/存储用户指定文件的文件名 p = 2 * n - 1; FILE *Code...
用c语言完成:1.哈夫曼编码\/译码器2.内部排序算法的性能分析
1.哈夫曼编码\/译码器【问题描述】设计一个利用哈夫曼算法的编码和译码系统,重复地显示并处理以下项目,直到选择退出为止。【基本要求】(1)初始化:键盘输入字符集大小n、n个字符和n个... 1.哈夫曼编码\/译码器【问题描述】 设计一个利用哈夫曼算法的编码和译码系统,重复地显示并处理以下项目,直到选择退出为止。【...
赫\/哈夫曼编\/译码器(1)
对于双工信道(即可以双向传输信息的信道),每端都需要一个完整的编\/译码系统。试为这样的信息收发站写一个哈夫曼码的编\/译码系统.[设计要求]利用二叉树的顺序存储结构表示,要求系统具有初始化,编码,译码,打印代码文件和打印赫夫曼树的功能.本系统将每一个要求的功能都作为一个独立的模块,值得注意的是,系统会自动...
C++课程设计:哈夫曼编码器
C++课程设计:哈夫曼编码器 【问题描述】:利用哈夫曼树实现编码并译码的系统。【基本要求】:从终端读入一段字符集,系统自动统计出字符的个数n以及各个字符出现的次数w作为权值,建立哈夫曼树,并将哈夫曼树以... 【问题描述】:利用哈夫曼树实现编码并译码的系统。【基本要求】:从终端读入一段字符集,系统自动统计...
急求:数据结构课程设计_赫夫曼编\\译码系统
你好,这个以前帮别人写过,相关的设计,流程图,算法说明和全部代码已经发给你了。刚才给你发Mail的那个信箱就是我的,如果满意请加分哦:)
题目:哈夫曼编码,译码系统
\/* 哈夫曼编码*\/ include "graphics.h"include "stdlib.h"include "Stdio.h"include "Conio.h"define MAX 53 char bmfile[10];char a[100];typedef struct {char c,s[10];}MM;MM mm[53];typedef struct \/*以数组存储哈夫曼树时的结点类型*\/ {char ch;int w,lcd,rcd,pt; \/*...
庾悦银杏: 我帮你测试了,这个可以满足你的要求! #include #include #define max 50 struct a { int weight; int parent,lchild,rchild; }; struct b { char cd[max]; int start; }; void main() { struct a ht[2*max]; struct b hcd[max],d; int i,k,n,c,s1,s2,m1,m2,f; printf("输入n:"); scanf("%d",&n); for(i=1;i
裕安区18659506963: 哈夫曼编/译码器 数据结构实践题 - ?
庾悦银杏: 展开全部#include#include typedef struct { char character; unsigned int weight; unsigned int parent,lchild,rchild; }HTNode,*HuffmanTree; typedef char **HuffmanCode; char *c; HuffmanTree HT; HuffmanCode HC; void menu() //定义菜单函数 { printf...
裕安区18659506963: 写个哈夫曼编码译码程序 数据结构 c++ - ?
庾悦银杏: #include #include #includetypedef struct { int weight; int parent,lchild,rchild; char data; }HTNode,*HuffmanTree; typedef char **HuffmanCode; void tongji(char *a,int *w,char *d,int &n) { int j=0; for(int i=0;i if(a[i]==d[k]) { w[k]++; break; } } if(k==j){ d[j]=a[i];...
裕安区18659506963: 求高手帮编写用数据结构实现哈夫曼树的编码和译码的程序(c++)最好能有300行 急用 - ?
庾悦银杏: #include<iostream.h>#include<string.h>#define maxsize 100#define n 5#define m 2*n-1 int start=0; typedef struct { int weight; int parent,lchild,rchild; }htnode; typedef htnode huffmantree[maxsize]; // 动态分配数组存储赫夫曼树 int min(huffmantree t,...
裕安区18659506963: 我们有个数据结构的哈夫曼编码解码的课程设计,你能帮帮我吗 - ?
庾悦银杏: 树和哈夫曼树实验报告一.实验目的练习树和哈夫曼树的有关操作,和各个算法程序,理解哈夫曼树的编码和译码二.实验环境 Microsoft visual c++三.实
裕安区18659506963: 哈夫曼树和哈夫曼编码 - ?
庾悦银杏: 给定n个权值作为n的叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree).哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近. 哈夫曼树(霍夫曼树)又称为最...
裕安区18659506963: .哈夫曼树、编码、译码 - ?
庾悦银杏: 生成哈夫曼树的代码如下: #define INT_MAX 10000 #define ENCODING_LENGTH 1000 #include "stdio.h" #include "string.h" #include "malloc.h" typedef enum{none,left_child,right_child} Which;//标记是左孩子还是右孩子 ...
裕安区18659506963: Huffman编码C语言实现 - ?
庾悦银杏: 说明:本程序是依据严蔚敏的数据结构(C语言版)上的代码实现的.#pragmaonce#include<stdio.h>#include<tchar.h>#include<stdlib.h>#define MAX 100 typedefstruct{ //节点 int weight; int parent, lchild, rchild; }HTNode, *HuffmanTree; ...
裕安区18659506963: 数据结构 最优二叉树 - ?
庾悦银杏: 这是我们的作业题,自己写 的……(可能输入的格式跟你要的不一致,自己改一下) 如果有什么不懂的就问我,我可以把其中所有相关的文件发给你 ^^ 注:1、 初始化创建哈夫曼树有三种选择,其中选择编译课本测试数据时和编译源文件是,...
裕安区18659506963: 急!哈夫曼编码算法的实现!@!!明天上午就要要的!~~~结果给的正确,加积分!!! - ?
庾悦银杏: typedef struct{ unsigned int weight;//权值 unsigned int parent,lchild,rchild; }HTNode, *HuffmanTree;//动态分配数组存储哈夫曼树 typedef char * *HuffmanCode;//动态分配数组存储哈夫曼编码表 void HoffmanCoding(HuffmanTree &HT,...