哈夫曼编码课程设计
⑴ C++课程设计“基于哈夫曼编码的数据压缩/解压程序”
This may be help:
http://www.diybl.com/course/3_program/c++/cppjs/20071024/79743.html
⑵ C++课程设计：哈夫曼编码器
#include <iostream.h>
#include <iomanip.h>
#include <string.h>
#include <malloc.h>
#include <stdio.h>
//typedef int TElemType;
const int UINT_MAX = 1000;
typedef struct
{
int weight;
int parent, lchild, rchild;
} HTNode, *HuffmanTree;
typedef char **HuffmanCode;
//-----------全局变量-----------------------
HuffmanTree HT;
HuffmanCode HC;
int *w, i, j, n;
char *z;
int flag = 0;
int numb = 0;
// -----------------求赫夫曼编码-----------------------
int min(HuffmanTree t, int i)
{
// 函数void select()调用
int j, flag;
int k = UINT_MAX; // 取k为不小于可能的值
for (j = 1; j <= i; j++)
if (t[j].weight < k && t[j].parent == 0)
k = t[j].weight, flag = j;
t[flag].parent = 1;
return flag;
}
//--------------------slect函数----------------------
void select(HuffmanTree t, int i, int &s1, int &s2)
{
// s1为最小的两个值中序号小的那个
int j;
s1 = min(t, i);
s2 = min(t, i);
if (s1 > s2)
{
j = s1;
s1 = s2;
s2 = j;
}
}
// --------------算法6.12--------------------------
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n)
{
// w存放n个字符的权值(均>0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC
int m, i, s1, s2, start;
//unsigned c,f;
int c, f;
HuffmanTree p;
char *cd;
if (n <= 1)
return ;
//检测结点数是否可以构成树
m = 2 * n - 1;
HT = (HuffmanTree)malloc((m + 1) *sizeof(HTNode)); // 0号单元未用
for (p = HT + 1, i = 1; i <= n; ++i, ++p, ++w)
{
p->weight = *w;
p->parent = 0;
p->lchild = 0;
p->rchild = 0;
}
for (; i <= m; ++i, ++p)
p->parent = 0;
for (i = n + 1; i <= m; ++i)
// 建赫夫曼树
{
// 在HT[1~i-1]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2
select(HT, i - 1, s1, s2);
HT[s1].parent = HT[s2].parent = i;
HT[i].lchild = s1;
HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
}
// 从叶子到根逆向求每个字符的赫夫曼编码
HC = (HuffmanCode)malloc((n + 1) *sizeof(char*));
// 分配n个字符编码的头指针向量([0]不用)
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));
// 为第i个字符编码分配空间
strcpy(HC[i], &cd[start]); // 从cd复制编码(串)到HC
}
free(cd); // 释放工作空间
}
//--------------初始化赫夫曼链表---------------------------------
void Initialization()
{
flag = 1;
int num;
int num2;
cout << "下面初始化赫夫曼链表" << endl << "数请输入结点的个n：";
cin >> num;
n = num;
w = (int*)malloc(n *sizeof(int));
z = (char*)malloc(n *sizeof(char));
cout << "\n请依次输入" << n << "个字符(字符型)\n注意:必须以回车结束：" <<
endl;
char base[2];
for (i = 0; i < n; i++)
{
cout << "第" << i + 1 << "个字符:" << endl;
gets(base);
*(z + i) = *base;
}
for (i = 0; i <= n - 1; i++)
{
cout << setw(6) << *(z + i);
}
cout << "\n请依次输入" << n << "个权值(\n注意:必须以回车结束)：" << endl;
for (i = 0; i <= n - 1; i++)
{
cout << endl << "第" << i + 1 << "个字符的权值:";
cin >> num2;
*(w + i) = num2;
}
HuffmanCoding(HT, HC, w, n);
//------------------------打印编码-------------------------------------------
cout << "字符对应的编码为:" << endl;
for (i = 1; i <= n; i++)
{
//cout<<"字符"<<*(z+i-1)<<"的编码";
puts(HC[i]);
}
//--------------------------将赫夫曼编码写入文件------------------------
cout << "下面将赫夫曼编码写入文件" << endl << "...................." << endl;
FILE *htmTree;
char r[] =
{
' ', '\0'
};
if ((htmTree = fopen("htmTree.txt", "w")) == NULL)
{
cout << "can not open file" << endl;
return ;
}
fputs(z, htmTree);
for (i = 0; i < n + 1; i++)
{
fprintf(htmTree, "%6d", *(w + i));
fputs(r, htmTree);
}
for (i = 1; i <= n; i++)
{
fputs(HC[i], htmTree);
fputs(r, htmTree);
}
fclose(htmTree);
cout << "已将字符与对应编码写入根目录下文件htmTree.txt中" << endl << endl;
}
//---------------------获取报文并写入文件---------------------------------
void InputCode()
{
//cout<<"请输入你想要编码的字符"<<endl;
FILE *tobetran;
char str[100];
if ((tobetran = fopen("tobetran.txt", "w")) == NULL)
{
cout << "不能打开文件" << endl;
return ;
}
cout << "请输入你想要编码的字符" << endl;
gets(str);
fputs(str, tobetran);
cout << "获取报文成功" << endl;
fclose(tobetran);
}
//---------------------编码函数---------------------------------
void Encoding()
{
cout << "下面对目录下文件tobetran.txt中的字符进行编码" << endl;
FILE *tobetran, *codefile;
if ((tobetran = fopen("tobetran.txt", "rb")) == NULL)
{
cout << "不能打开文件" << endl;
}
if ((codefile = fopen("codefile.txt", "wb")) == NULL)
{
cout << "不能打开文件" << endl;
}
char *tran;
i = 99;
tran = (char*)malloc(100 *sizeof(char));
while (i == 99)
{
if (fgets(tran, 100, tobetran) == NULL)
{
cout << "不能打开文件" << endl;
break;
}
for (i = 0; *(tran + i) != '\0'; i++)
{
for (j = 0; j <= n; j++)
{
if (*(z + j - 1) == *(tran + i))
{
fputs(HC[j], codefile);
if (j > n)
{
cout << "字符错误，无法编码!" << endl;
break;
}
}
}
}
}
cout << "编码工作完成" << endl << "编码写入目录下的codefile.txt中" << endl <<
endl;
fclose(tobetran);
fclose(codefile);
free(tran);
}
//-----------------译码函数---------------------------------
void Decoding()
{
cout << "下面对根目录下文件codefile.txt中的字符进行译码" << endl;
FILE *codef, *txtfile;
if ((txtfile = fopen("Textfile.txt", "w")) == NULL)
{
cout << "不能打开文件" << endl;
}
//txtfile=fopen("Textfile.txt","w");
if ((codef = fopen("codefile.txt", "r")) == NULL)
{
cout << "不能打开文件" << endl;
}
//codef=fopen("codefile.txt","r");
char *work, *work2, i2;
int i4 = 0, i, i3;
unsigned long length = 10000;
work = (char*)malloc(length *sizeof(char));
fgets(work, length, codef);
work2 = (char*)malloc(length *sizeof(char));
i3 = 2 * n - 1;
for (i = 0; *(work + i - 1) != '\0'; i++)
{
i2 = *(work + i);
if (HT[i3].lchild == 0)
{
*(work2 + i4) = *(z + i3 - 1);
i4++;
i3 = 2 * n - 1;
i--;
}
else if (i2 == '0')
i3 = HT[i3].lchild;
else if (i2 == '1')
i3 = HT[i3].rchild;
}
*(work2 + i4) = '\0';
fputs(work2, txtfile);
cout << "译码完成" << endl << "内容写入根目录下的文件txtfile.txt中" << endl
<< endl;
cout << work2;
free(work);
free(work2);
fclose(txtfile);
fclose(codef);
}
//-----------------------打印编码的函数----------------------
void Code_printing()
{
cout << "下面打印根目录下文件CodePrin.txt中编码字符" << endl;
FILE *CodePrin, *codefile;
if ((CodePrin = fopen("CodePrin.txt", "w")) == NULL)
{
cout << "不能打开文件" << endl;
return ;
}
if ((codefile = fopen("codefile.txt", "r")) == NULL)
{
cout << "不能打开文件" << endl;
return ;
}
char *work3;
work3 = (char*)malloc(51 *sizeof(char));
do
{
if (fgets(work3, 51, codefile) == NULL)
{
cout << "不能读取文件" << endl;
break;
}
fputs(work3, CodePrin);
puts(work3);
}
while (strlen(work3) == 50);
free(work3);
/* int iNum=2,num=2;
while((num=fscanf(codefile,"%d",iNum))!=NULL)
{
printf("%d",iNum);
fprintf(CodePrin,"%d",iNum);
}
*/
cout << "打印工作结束" << endl << endl;
fclose(CodePrin);
fclose(codefile);
}
//------------------------打印赫夫曼树的函数-----------------------
void coprint(HuffmanTree start, HuffmanTree HT)
{
if (start != HT)
{
FILE *TreePrint;
if ((TreePrint = fopen("TreePrint.txt", "a")) == NULL)
{
cout << "创建文件失败" << endl;
return ;
}
numb++; //该变量为已被声明为全局变量
coprint(HT + start->rchild, HT);
cout << setw(5 *numb) << start->weight << endl;
fprintf(TreePrint, "%d\n", start->weight);
coprint(HT + start->lchild, HT);
numb--;
fclose(TreePrint);
}
}
void Tree_printing(HuffmanTree HT, int w)
{
HuffmanTree p;
p = HT + w;
cout << "下面打印赫夫曼树" << endl;
coprint(p, HT);
cout << "打印工作结束" << endl;
}
/*//------------------------------tongjipin
void tongji(HuffmanTree &HT, HuffmanCode &HC)
{
char str[254], st[254];
int cnt[27];
// char *p;
int temp[27], k;
for (int i = 1; i <= 26; i++)
{
temp[i] = 0;
}
flag = 1;
char base;
int n = 0; //总数
cout << "请输入字符串：" << endl;
while (1)
{
cin >> base;
if (base != '\0')
{
st[n] = base;
n++;
}
else
st[n] = '\0';
break;
}
for (int t = 0; st[t] != '\0'; t++)
{
if (st[t] >= 'A' && st[t] <= 'Z')
{
k = st[t] - 64;
temp[k]++;
}
}
j = 0;
for (i = 1, j = 0; i <= 26; i++)
{
if (temp[i] != 0)
{
j++;
str[j] = i + 64;
cnt[j] = temp[i];
}
}
w = (int*)malloc(n *sizeof(int)); //pin
z = (char*)malloc(n *sizeof(char)); //zifu
z = str;
w = cnt;
for (t = 1; t <= n; t++)
{
cout << "字符:" << str[t] << " 频度:" << cnt[t] << endl;
}
// char base[2];
// for(i=0;i<=n-1;i++)
// {
// cout<<setw(6)<<*(z+i);
// }
// cin>>num2;
// *(w+i)=num2;
HuffmanCoding(HT, HC, w, n);
//------------------------打印编码-------------------------------------------
cout << "字符对应的编码为:" << endl;
for (i = 1; i <= n; i++)
{
//cout<<"字符"<<*(z+i-1)<<"的编码";
puts(HC[i]);
}
//--------------------------将赫夫曼编码写入文件------------------------
cout << "下面将赫夫曼编码写入文件" << endl << "...................." << endl;
FILE *htmTree;
char r[] =
{
' ', '\0'
};
if ((htmTree = fopen("htmTree.txt", "w")) == NULL)
{
cout << "can not open file" << endl;
return ;
}
fputs(z, htmTree);
for (i = 0; i < n + 1; i++)
{
fprintf(htmTree, "%6d", *(w + i));
fputs(r, htmTree);
}
for (i = 1; i <= n; i++)
{
fputs(HC[i], htmTree);
fputs(r, htmTree);
}
fclose(htmTree);
cout << "已将字符与对应编码写入根目录下文件htmTree.txt中" << endl << endl;
}*/
//------------------------主函数------------------------------------
void main()
{
char choice;
while (choice != 'q')
{
cout << "\n******************************" << endl;
cout << " 欢迎使用赫夫曼编码解码系统" << endl;
cout << "******************************" << endl;
cout << "(1)要初始化赫夫曼链表请输入'i'" << endl;
cout << "(2)输入要编码的字符'w'" << endl;
cout << "(3)要编码请输入'e'" << endl;
cout << "(4)要译码请输入'd'" << endl;
cout << "(5)要打印编码请输入'p'" << endl;
cout << "(6)要打印赫夫曼树请输入't'" << endl;
cout << "(7)要离开请输入'q'" << endl;
//cout << "(8)统计频度'a'" << endl;
// if(flag==0)cout<<"\n请先初始化赫夫曼链表,输入'i'"<<endl;
cin >> choice;
switch (choice)
{
case 'i':
Initialization();
break;
case 'w':
InputCode();
break;
case 'e':
Encoding();
break;
case 'd':
Decoding();
break;
case 'p':
Code_printing();
break;
case 't':
Tree_printing(HT, 2 *n - 1);
break;
case 'q':
break;
// case 'a':
// tongji(HT, HC);
default:
cout << "input error" << endl;
}
}
free(z);
free(w);
free(HT);
}
⑶ 我们有个数据结构的哈夫曼编码解码的课程设计，你能帮帮我吗
树和哈夫曼树实验报告
一．实验目的
练习树和哈夫曼树的有关操作，和各个算法程序，理解哈夫曼树的编码和译码
二．实验环境
Microsoft visual c++
三．实验问题描述
1. 问题描述：建立一棵用二叉链表方式存储的二叉树，并对其进行遍历（先序、中序和后序），打印输出遍历结果。
基本要求：从键盘接受输入先序序列，以二叉链表作为存储结构，建立二叉树（以先序来建立），并将此二叉树按照“树状形式”打印输出，然后对其进行遍历（先序、中序和后序），最后将遍历结果打印输出。在遍历算法中要求至少有一种遍历采用非递归方法。
测试数据：
ABCØØDEØGØØFØØØ（其中Ø表示空格字符）
输出结果为：
先序：ABCDEGF
先序：CBEGDFA
先序：CGEFDBA
2. 问题描述：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接受端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。
基本要求：(至少完成功能1-2）
一个完整的系统应具有以下功能：
I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。
基本要求：
E：编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。
D：译码（Decoding )。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。
P：印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrint中。
T：印哈夫曼树（TreePrinting）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。
测试数据：
设权值w=（5，29，7，8，14，23，3，11），n=8。
按照字符‘0’或‘1’确定找左孩子或右孩子，则权值对应的编码为：
5：0001，29：11，7：1110，8：1111
14：110，23：01，3：0000，11：001
用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”。
四．实验主要程序流
实验题目一主要程序：
1．
void CreatBiTree(BitTree *bt)//用扩展先序遍历序列创建二叉树，如果是#当前树根置为空，否则申请一个新节点//
{
char ch;
ch=getchar();
if(ch=='.')*bt=NULL;
else
{
*bt=(BitTree)malloc(sizeof(BitNode));
(*bt)->data=ch;
CreatBiTree(&((*bt)->LChild));
CreatBiTree(&((*bt)->RChild));
}
}
2．void Visit(char ch)//访问根节点
{
printf("%c ",ch);
}
3．
void PreOrder(BitTree root)
{
if (root!=NULL)
{
Visit(root ->data);
PreOrder(root ->LChild);
PreOrder(root ->RChild);
}
}
4． void InOrder(BitTree root)
{
if (root!=NULL)
{
InOrder(root ->LChild);
Visit(root ->data);
InOrder(root ->RChild);
}
}
5．int PostTreeDepth(BitTree bt) //后序遍历求二叉树的高度递归算法//
{
int hl,hr,max;
if(bt!=NULL)
{
hl=PostTreeDepth(bt->LChild); //求左子树的深度
hr=PostTreeDepth(bt->RChild); //求右子树的深度
max=hl>hr?hl:hr; //得到左、右子树深度较大者
return(max+1); //返回树的深度
}
else return(0); //如果是空树，则返回0
}
6．void PrintTree(BitTree Boot,int nLayer) //按竖向树状打印的二叉树 //
{
int i;
if(Boot==NULL) return;
PrintTree(Boot->RChild,nLayer+1);
for(i=0;i<nLayer;i++)
printf(" ");
printf("%c\n",Boot->data);
PrintTree(Boot->LChild,nLayer+1);
}
7．void main()
{
BitTree T;
int h;
int layer;
int treeleaf;
layer=0;
printf("请输入二叉树中的元素(以扩展先序遍历序列输入,其中.代表空子树):\n");
CreatBiTree(&T);
printf("先序遍历序列为:");
PreOrder(T);
printf("\n中序遍历序列为:");
InOrder(T);
printf("\n后序遍历序列为:");
PostOrder(T);
h=PostTreeDepth(T);
printf("\此二叉树的深度为:%d\n",h);
printf("此二叉树的横向显示为：\n");
PrintTree(T,layer);
}
实验二主要程序流：
1．int main(){
HuffmanTree huftree;
char Choose;
while(1){
cout<<"\n**********************欢迎使用哈夫曼编码/译码系统**********************\n";
cout<<"*您可以进行以下操作: *\n";
cout<<"*1.建立哈夫曼树 *\n";
cout<<"*2.编码(源文已在文件ToBeTra中，或键盘输入) *\n";
cout<<"* 3.译码(码文已在文件CodeFile中) *\n";
cout<<"* 4.显示码文 *\n";
cout<<"* 5.显示哈夫曼树 *\n";
cout<<"* 6.退出 *\n"; cout<<"***********************************************************************\n";
cout<<"请选择一个操作:";
cin>>Choose;
switch(Choose)
{
case '1':
huftree.CreateHuffmanTree();
break;
case '2':
huftree.Encoder();
break;
case '3':
huftree.Decoder();
break;
case '4':
huftree.PrintCodeFile();
break;
case '5':
huftree.PrintHuffmanTree();
break;
case '6':
cout<<"\n**********************感谢使用本系统!*******************\n\n";
system("pause");
return 0;
}//switch
}//while
}//main
2．// 建立哈夫曼树函数
// 函数功能：建立哈夫曼树（调用键盘建立哈夫曼树或调用从文件建立哈夫曼树的函数）
void HuffmanTree::CreateHuffmanTree()
{char Choose;
cout<<"你要从文件中读入哈夫曼树(按1)，还是从键盘输入哈夫曼树(按2)？";
cin>>Choose;
if(Choose=='2') { //键盘输入建立哈夫曼树 CreateHuffmanTreeFromKeyboard();
}//choose=='2'
else { //从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树
CreateHuffmanTreeFromFile();
}
}
3. // 从键盘建立哈夫曼树函数
// 函数功能：从键盘建立哈夫曼树
//函数参数：无
//参数返回值：无
void HuffmanTree::CreateHuffmanTreeFromKeyboard(){
int Num;
cout<<"\n请输入源码字符集个数：";
cin>>Num;
if (Num<=1) {
cout<<"无法建立少于2个叶子结点的哈夫曼树。\n\n";
return;
}
LeafNum=Num;
Node=new HuffmanNode[2*Num-1];
for(int i=0;i<Num;i++) {//读入哈夫曼树的叶子结点信息
cout<<"请输入第"<<i+1<<"个字符值";
getchar();
Node[i].sourcecode=getchar(); //源文的字符存入字符数组Info[]
getchar();
cout<<"请输入该字符的权值或频度";
cin>>Node[i].weight; //源文的字符权重存入Node[].weight
Node[i].parent=-1;
Node[i].lchild=-1;
Node[i].rchild=-1;
Node[i].code="\0";
}
for(int j=Num;j<2*Num-1;j++) {//循环建立哈夫曼树内部结点
int pos1,pos2;
int max1,max2;
pos2=pos1=j;
max2=max1=numeric_limits<int>::max( );
//在所有子树的根结点中，选权重最小的两个根结点，pos1最后应指向权重最小的根结点的下标
//pos2最后应指向权重第二小的根结点的下标
//max1存放当前找到的权重最小的根结点的权重
//max2存放当前找到的权重第二小的根结点的权重
for(int k=j-1;k>=0;k--) {
if (Node[k].parent==-1){//如果是某棵子树的根结点
if (Node[k].weight<max1){ //发现比当前最大值还大的权重
max2=max1;
max1=Node[k].weight;
pos2=pos1;
pos1=k;
}
else
if(Node[k].weight<max2){ //发现比当前次大值还大的次大权重
max2=Node[k].weight;
pos2=k;
}
}//if (Node[j].parent==-1)
} //for
//在下标i处新构造一个哈夫曼树的内部结点，其左、右孩子就是以上pos1、pos2所指向的结点
Node[pos1].parent=j;
Node[pos2].parent=j;
Node[j].lchild=pos1;
Node[j].rchild=pos2;
Node[j].parent=-1;
Node[j].weight=Node[pos1].weight+Node[pos2].weight;
} //for
//产生所有叶子结点中字符的编码
for (int m=0;m<Num;m++) {
//产生Node[i].sourcecode的编码，存入Node[i].code中
int j=m;
int j1;
while(Node[j].parent!=-1) { //从叶结点开始往根结点走，每往上走一层，就产生一位编码存入code[]
j1=Node[j].parent;
if(Node[j1].lchild==j)
Node[m].code.insert(0,"0");
else
Node[m].code.insert(0,"1");
j=j1; }}
cout<<"哈夫曼树已成功构造完成。\n";
//把建立好的哈夫曼树写入文件hfmTree.dat
char ch;
cout<<"是否要替换原来的哈夫曼树文件(Y/N):";
cin>>ch;
if (ch!='y'&&ch!='Y') return;
ofstream fop;
fop.open("hfmTree.dat",ios::out|ios::binary|ios::trunc); //打开文件
if(fop.fail()) {
cout<<"\n哈夫曼树文件打开失败，无法将哈夫曼树写入hfmTree.dat文件。\n";
return;
}
fop.write((char*)&Num,sizeof(Num)); //先写入哈夫曼树的叶子结点个数
for(int n=0;n<2*Num-1;n++) { //最后写入哈夫曼树的各个结点（存储在Node[]中）
fop.write((char*)&Node[n],sizeof(Node[n]));
flush(cout); }
fop.close(); //关闭文件
cout<<"\n哈夫曼树已成功写入hfmTree.dat文件。\n";}
4. // 从文件建立哈夫曼树函数
// 函数功能：从文件建立哈夫曼树
//函数参数：无
//参数返回值：无
void HuffmanTree::CreateHuffmanTreeFromFile(){
ifstream fip;
fip.open("hfmTree.dat",ios::binary|ios::in);
if(fip.fail()) {
cout<<"哈夫曼树文件hfmTree.dat打开失败，无法建立哈夫曼树。\n";
return;
}
fip.read((char*)&LeafNum,sizeof(LeafNum));
if (LeafNum<=1) {
cout<<"哈夫曼树文件中的数据有误，叶子结点个数少于2个，无法建立哈夫曼树。\n";
fip.close();
return;
}
Node=new HuffmanNode[2*LeafNum-1];
for(int i=0;i<2*LeafNum-1;i++)
fip.read((char*)&Node[i],sizeof(Node[i]));
fip.close();
cout<<"哈夫曼树已从文件成功构造完成。\n";
}
5. // 编码函数
// 函数功能：为哈夫曼树编码
//函数参数：无
//参数返回值：无
void HuffmanTree::Encoder()
{
if(Node==NULL) { //内存没有哈夫曼树，则从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树
CreateHuffmanTreeFromFile();
if (LeafNum<=1) {
cout<<"内存无哈夫曼树。操作撤销。\n\n";
return;
}
}//if
char *SourceText; //字符串数组，用于存放源文
//让用户选择源文是从键盘输入，还是从源文文件ToBeTran.txt中读入
char Choose;
cout<<"你要从文件中读入源文(按1)，还是从键盘输入源文(按2)？";
cin>>Choose;
if(Choose=='1') {
ifstream fip1("ToBeTran.txt");
if(fip1.fail()) {
cout<<"源文文件打开失败!无法继续执行。\n";
return;
}
char ch;
int k=0;
while(fip1.get(ch)) k++; //第一次读文件只统计文件中有多少个字符，将字符数存入k
fip1.close();
SourceText=new char[k+1]; //申请存放源文的字符数组空间
ifstream fip2("ToBeTran.txt"); //第二次读源文文件，把内容写入SourceText[]
k=0;
while(fip2.get(ch)) SourceText[k++]=ch;
fip2.close();
SourceText[k]='\0';
}
else { //从键盘输入源文
string SourceBuff;
cin.ignore();
cout<<"请输入需要编码的源文(可输入任意长，按回车键结束):\n";
getline(cin,SourceBuff,'\n');
int k=0;
while(SourceBuff[k]!='\0')
k++;
SourceText=new char[k+1];
k=0;
while(SourceBuff[k]!='\0') {
SourceText[k]=SourceBuff[k];
k++;
}
SourceText[k]='\0';
}
cout<<"需编码的源文为：";
cout<<SourceText<<endl;
//开始译码
ofstream fop("CodeFile.dat",ios::trunc); //打开码文存放文件
int k=0;
while(SourceText[k]!='\0') //源文串中从第一个字符开始逐个编码
{
int i;
for(i=0;i<LeafNum;i++){ //找到当前要编码的源文的字符在哈夫曼树Node[]中的下标
if(Node[i].sourcecode==SourceText[k]) { //将对应编码写入码文文件
fop<<Node[i].code;
break;
};
}
if (i>=LeafNum) {
cout<<"源文中存在不可编码的字符。无法继续执行。\n"<<endl;
fop.close();
return;
}
k++; //源文串中的字符后移一个
}
fop.close();
cout<<"已完成编码，码文已写入文件CodeFile.dat中。\n\n";
}
6. // 译码函数
// 函数功能：对哈夫曼树进行译码
//函数参数：无
//参数返回值：无
void HuffmanTree::Decoder()
{//如果内存没有哈夫曼树，则从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树
if(Node==NULL)
{
CreateHuffmanTreeFromFile();
if (LeafNum<=1) {
cout<<"内存无哈夫曼树。操作撤销。\n\n";
return;
}
}
//将码文从文件CodeFile.dat中读入 CodeStr[]
ifstream fip1("CodeFile.dat");
if(fip1.fail()) {
cout<<"没有码文，无法译码。\n";
return;
}
char* CodeStr;
int k=0;
char ch;
while(fip1.get(ch)){
k++;
}
fip1.close();
CodeStr=new char[k+1];
ifstream fip2("CodeFile.dat");
k=0;
while(fip2.get(ch))
CodeStr[k++]=ch;
fip2.close();
CodeStr[k]='\0';
cout<<"经译码得到的源文为：";
ofstream fop("TextFile.dat");
int j=LeafNum*2-1-1; //j指向哈夫曼树的根
int i=0; //码文从第一个符号开始，顺着哈夫曼树由根下行，按码文的当前符号决定下行到左孩子还是右孩子
while(CodeStr[i]!='\0') { //下行到哈夫曼树的叶子结点处，则译出叶子结点对应的源文字符
if(CodeStr[i]=='0')
j=Node[j].lchild;
else
j=Node[j].rchild;
if(Node[j].rchild==-1) { //因为哈夫曼树没有度为1的结点，所以此条件等同于Node[j]为叶结点
cout<<Node[j].sourcecode; //屏幕输出译出的一个源文字符
fop<<Node[j].sourcecode;
j=LeafNum*2-1-1; //j再指向哈夫曼树的根
}
i++;
}
fop.close();
cout<<"\n译码成功且已存到文件TextFile.dat中。\n\n";
}
7. // 输出码文函数
// 函数功能：从文件中输出哈夫曼树的码文
//函数参数：无
//参数返回值：无
void HuffmanTree::PrintCodeFile()
{
char ch;
int i=1;
ifstream fip("CodeFile.dat");
ofstream fop("CodePrin.dat");
if(fip.fail())
{
cout<<"没有码文文件，无法显示码文文件内容。\n";
return;
}
while(fip.get(ch))
{cout<<ch;
fop<<ch;
if(i==50)
{
cout<<endl;
fop<<endl;
i=0;
}
i++;
}
cout<<endl;
fop<<endl;
fip.close();
fop.close();
}
8. // 输出函数
// 函数功能：从内存或文件中直接输出哈夫曼树
//函数参数：无
//参数返回值：无
void HuffmanTree::PrintHuffmanTree()
{
//如果内存没有哈夫曼树，则从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树
if(Node==NULL)
{
CreateHuffmanTreeFromFile();
if (LeafNum<=1) {
cout<<"内存无哈夫曼树。操作撤销。\n\n";
return; }}
ofstream fop("TreePrint.dat",ios_base::trunc);
fop.close();
PrintHuffmanTree_aoru(2*LeafNum-1-1);
return;
}
⑷ 急求哈夫曼编码/译码器（80）课程设计，望高手帮忙
我给你个差不多的，你自己修改一下就可以用了
/************Huffman编码和译码****************/
#include<stdio.h>
#include<malloc.h>
#include<string.h>
#include<stdlib.h>
typedef struct
{
int weight;
char ch;
int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef struct
{
char ch;
char *chs;
}HuffmanCode;
typedef struct
{
char ch;
int weight;
}sw;
typedef struct
{
HuffmanTree HT;
HuffmanCode *HC;
}huf;
void select(HTNode * HT,int n,int *n1,int *n2)
{
int i=1; int n3;
while(HT[i].parent!=0)
i++;
*n1=i;
i++;
while(HT[i].parent!=0) i++;
*n2=i;
if(HT[*n1].weight<HT[*n2].weight)
{ n3=*n1;*n1=*n2;*n2=n3;}
for(i++;i<=n;i++)
{
if(HT[i].parent==0)
{ if(HT[i].weight<HT[*n1].weight)
*n1=i;
else if(HT[i].weight<HT[*n2].weight)
*n2=i;
}
}
}
huf * HuffmanCoding(HuffmanTree HT,HuffmanCode *HC,sw *w,int n,huf *HUF)
{int m,i,s1,s2,start,c,f;
HuffmanTree p;
char *cd;
if(n<=1) return 0;
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(p=HT+1,i=1;i<=n;i++,p++,w++)
{p->weight=w->weight;p->ch=w->ch;p->parent=0;p->lchild=0;p->rchild=0;}
for(;i<=m;i++,p++)
{p->weight=0;p->ch='^';p->parent=0;p->lchild=0;p->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;
}
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].ch=HT[i].ch;
HC[i].chs=(char*)malloc((n-start)*sizeof(char));
strcpy(HC[i].chs,&cd[start]);
printf("%c %-10s\n",HC[i].ch,HC[i].chs);
}
HUF->HT=HT;
HUF->HC=HC;
return HUF;
}
char * convert(char *chars,char *chars1,HuffmanCode *hc,int n)
{
char *p=chars; int i;
strcpy(chars1,"");
while(*p)
{
i=1; while(hc[i].ch!=*p&&i<=n) i++;
strcat(chars1,hc[i].chs); p++;
}
printf("the chars translate are:%s\n",chars1);
return chars1;
}
void transcode(HuffmanTree ht,char *chars2,char*chars3)
{
int i=1,p; char *q=chars2;char *r=chars3;
while(ht[i].parent!=0) i++;
p=i;
while(*q)
{
while(ht[p].lchild!=0 && *q)
{
if(*q=='0')
p=ht[p].lchild;
else p=ht[p].rchild;
q++;
}
if(ht[p].lchild==0)
{*r=ht[p].ch;r++;}
p=i;
}
*r='\0';
printf("the chars are:");
puts(chars3);
}
void input(int *n,sw *w)
{
int i;
printf("input the mount of char:");
scanf("%d",n);
for(i=1;i<=*n;i++,w++)
{printf("input the %dth char and weight:",i);
fflush(stdin);
scanf("%c%d",&w->ch,&w->weight);
}
}
void main(void)
{HTNode HT;
HuffmanCode HC,*hc;
HuffmanTree ht;
huf *HUF,huf2;
int n;
sw w[40];
char ch,inchar[500],outchar[1000];
char *abc;
char *p=inchar;
input(&n,w);
HUF=HuffmanCoding(&HT,&HC,w,n,&huf2);
printf("input chars to translate,ends of '#':");
fflush(stdin);//清除流,解决输入干扰
ch=getchar();
while(ch!='#')
{*p=ch;
p++;
ch=getchar();
}
*p='\0';
hc=HUF->HC;
ht=HUF->HT;
abc=convert(inchar,outchar,hc,n);
transcode(ht,abc,outchar);
}
⑸ 求个哈夫曼编码的设计与实现（数据结构课程设计）拜托各位了 3Q
#include<string.h> #include<stdlib.h> #include<stdio.h> int m,s1,s2; typedef struct { unsigned int weight; unsigned int parent,lchild,rchild; }HTNode,*HuffmanTree; typedef char *HuffmanCode; void Select(HuffmanTree HT,int n) { int i,j; for(i = 1;i <= n;i++) if(![i].parent){s1 = i;break;} for(j = i+1;j <= n;j++) if(!HT[j].parent){s2 = j;break;} for(i = 1;i <= n;i++) if((HT[s1].weight>HT[i].weight)&&(!HT[i].parent)&&(s2!=i))s1=i; for(j = 1;j <= n;j++) if((HT[s2].weight>HT[j].weight)&&(!HT[j].parent)&&(s1!=j))s2=j; } void HuffmanCoding(HuffmanTree &HT, HuffmanCode HC[], int *w, int n) { int i, j; char *cd; int p; int cdlen; 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=n+1; i<=m; i++) { HT[i].weight=0; HT[i].parent=0; HT[i].lchild=0; HT[i].rchild=0; } puts("\n哈夫曼树的构造过程如下所示："); printf("HT初态:\n 结点 weight parent lchild rchild"); for (i=1; i<=m; i++) printf("\n%4d%8d%8d%8d%8d",i,HT[i].weight, HT[i].parent,HT[i].lchild, HT[i].rchild); printf(" 按任意键，继续 ..."); getchar(); for (i=n+1; i<=m; i++) { Select(HT, i-1); 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("\nselect: s1=%d s2=%d\n", s1, s2); printf(" 结点 weight parent lchild rchild"); for (j=1; j<=i; j++) printf("\n%4d%8d%8d%8d%8d",j,HT[j].weight, HT[j].parent,HT[j].lchild, HT[j].rchild); printf(" 按任意键，继续 ..."); getchar(); } cd = (char *)malloc(n*sizeof(char)); p = m; cdlen = 0; for (i=1; i<=m; ++i) HT[i].weight = 0; while (p) { if (HT[p].weight==0) { HT[p].weight = 1; if (HT[p].lchild != 0) { p = HT[p].lchild; cd[cdlen++] ='0'; } else if (HT[p].rchild == 0) { HC[p] = (char *)malloc((cdlen+1) * sizeof(char)); cd[cdlen] ='\0'; strcpy(HC[p], cd); } } else if (HT[p].weight==1) { HT[p].weight = 2; if (HT[p].rchild != 0) { p = HT[p].rchild; cd[cdlen++] ='1'; } } else { HT[p].weight = 0; p = HT[p].parent; --cdlen; } } } void main() { HuffmanTree HT;HuffmanCode *HC;int *w,n,i; puts("输入结点数:"); scanf("%d",&n); HC = (HuffmanCode *)malloc(n*sizeof(HuffmanCode)); w = (int *)malloc(n*sizeof(int)); printf("输入%d个结点的权值\n",n); for(i = 0;i < n;i++) scanf("%d",&w[i]); HuffmanCoding(HT,HC,w,n); puts("\n各结点的哈夫曼编码:"); for(i = 1;i <= n;i++) printf("%2d(%4d):%s\n",i,w[i-1],HC[i]); getchar(); }
⑹ 急！！高分求关于 哈夫曼编码 课程设计程序
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
int m,s1,s2;
typedef struct {
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树
typedef char *HuffmanCode; //动态分配数组存储哈夫曼编码表
void Select(HuffmanTree HT,int n) {
int i,j;
for(i = 1;i <= n;i++)
if(!HT[i].parent){s1 = i;break;}
for(j = i+1;j <= n;j++)
if(!HT[j].parent){s2 = j;break;}
for(i = 1;i <= n;i++)
if((HT[s1].weight>HT[i].weight)&&(!HT[i].parent)&&(s2!=i))s1=i;
for(j = 1;j <= n;j++)
if((HT[s2].weight>HT[j].weight)&&(!HT[j].parent)&&(s1!=j))s2=j;
}
void HuffmanCoding(HuffmanTree &HT, HuffmanCode HC[], int *w, int n) {
// 算法6.13
// w存放n个字符的权值(均>0)，构造哈夫曼树HT，
// 并求出n个字符的哈夫曼编码HC
int i, j;
char *cd;
int p;
int cdlen;
if (n<=1) return;
m = 2 * n - 1;
HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); // 0号单元未用
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=n+1; i<=m; i++) { //初始化
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
puts("\n哈夫曼树的构造过程如下所示：");
printf("HT初态:\n 结点 weight parent lchild rchild");
for (i=1; i<=m; i++)
printf("\n%4d%8d%8d%8d%8d",i,HT[i].weight,
HT[i].parent,HT[i].lchild, HT[i].rchild);
printf(" 按任意键，继续 ...");
getchar();
for (i=n+1; i<=m; i++) { // 建哈夫曼树
// 在HT[1..i-1]中选择parent为0且weight最小的两个结点，
// 其序号分别为s1和s2。
Select(HT, i-1);
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("\nselect: s1=%d s2=%d\n", s1, s2);
printf(" 结点 weight parent lchild rchild");
for (j=1; j<=i; j++)
printf("\n%4d%8d%8d%8d%8d",j,HT[j].weight,
HT[j].parent,HT[j].lchild, HT[j].rchild);
printf(" 按任意键，继续 ...");
getchar();
}
//------无栈非递归遍历哈夫曼树，求哈夫曼编码
cd = (char *)malloc(n*sizeof(char)); // 分配求编码的工作空间
p = m; cdlen = 0;
for (i=1; i<=m; ++i) // 遍历哈夫曼树时用作结点状态标志
HT[i].weight = 0;
while (p) {
if (HT[p].weight==0) { // 向左
HT[p].weight = 1;
if (HT[p].lchild != 0) { p = HT[p].lchild; cd[cdlen++] ='0'; }
else if (HT[p].rchild == 0) { // 登记叶子结点的字符的编码
HC[p] = (char *)malloc((cdlen+1) * sizeof(char));
cd[cdlen] ='\0'; strcpy(HC[p], cd); // 复制编码(串)
}
} else if (HT[p].weight==1) { // 向右
HT[p].weight = 2;
if (HT[p].rchild != 0) { p = HT[p].rchild; cd[cdlen++] ='1'; }
} else { // HT[p].weight==2，退回退到父结点，编码长度减1
HT[p].weight = 0; p = HT[p].parent; --cdlen;
}
}
} // HuffmanCoding
void main() {
HuffmanTree HT;HuffmanCode *HC;int *w,n,i;
puts("输入结点数:");
scanf("%d",&n);
HC = (HuffmanCode *)malloc(n*sizeof(HuffmanCode));
w = (int *)malloc(n*sizeof(int));
printf("输入%d个结点的权值\n",n);
for(i = 0;i < n;i++)
scanf("%d",&w[i]);
HuffmanCoding(HT,HC,w,n);
puts("\n各结点的哈夫曼编码:");
for(i = 1;i <= n;i++)
printf("%2d(%4d):%s\n",i,w[i-1],HC[i]);
getchar();
}
⑺ 急求数据结构课程设计-赫夫曼编码
你看看这里，我回答过一次了，应该对你的问题有所帮助，呵呵~
http://..com/question/40858673.html
⑻ Huffman编码课程设计
具体代码可以参考：
http://blog.csdn.net/yong369044325/article/details/7829896
上述代码是从控制台输入字符的。
然后将编码结果输出版到控制台，权故你可以将这部分稍加修改，
使其从文件读取待编码字符，编码结果输出到另一个文件。
⑼ 求一个<哈夫曼编码>数据结构课程设计（C语言版）
我帮你测试了，这个可以满足你的要求！#include<stdio.h>
#include<stdlib.h>
#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<=n;i++)
{
printf("输入权值:");
scanf("%d",&ht[i].weight);
ht[i].parent=0;
}
for(;i<=2*n-1;i++)
ht[i].parent=ht[i].lchild=ht[i].rchild=0;
for(i=n+1;i<=2*n-1;i++)
{
m1=m2=30000;
s1=s2=0;
for(k=1;k<=i-1;k++)
{
if(ht[k].parent==0 && ht[k].weight<m1)
{
m2=m1;
s2=s1;
m1=ht[k].weight;
s1=k;
}
else if(ht[k].parent==0 && ht[k].weight<m2)
{
m2=ht[k].weight;
s2=k;
}
}
ht[s1].parent=ht[s2].parent=i;
ht[i].lchild=s1;
ht[i].rchild=s2;
ht[i].weight=ht[s1].weight+ht[s2].weight;
}
for(i=1;i<=n;i++)
{
d.start=n-1;
c=i;
f=ht[i].parent;
while(f)
{
if(ht[f].lchild==c)d.cd[--d.start]='0';
else d.cd[--d.start]='1';
c=f;
f=ht[f].parent;
}
hcd[i]=d;
}
printf("输出哈夫编码:");
for(i=1;i<=n;i++)
{
printf("%d ",ht[i].weight);
for(k=hcd[i].start;k<n-1;k++)
printf("%c",hcd[i].cd[k]);
printf(" ");
}
printf("\n");
}