#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=1i<=ni++)
if(HT[i].parent==0)
{s1=i
break
}
for(j=i+1j<=nj++)
if(HT[j].parent==0)
{
s2=j
break
}
for(i=1i<=ni++)
{
if(HT[i].parent==0)
if(HT[s1].weight>HT[i].weight)
if(s2!=i)
s1=i
}
for(j=1j<=nj++)
{
if(HT[j].parent==0)
if(HT[s2].weight>HT[j].weight)
if(s1!=j)
s2=j
}
if(s1>s2)
{
int temp=s1
s1=s2
s2=temp
}
}
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=1i<=ni++)
{
HT[i].weight=w[i-1]
HT[i].parent=0
HT[i].lchild=0
HT[i].rchild=0
}
for (i=n+1i<=mi++)
{
HT[i].weight=0
HT[i].parent=0
HT[i].lchild=0
HT[i].rchild=0
}
//添加查看，便于调试
printf("构造过程显示：\n")
for(i=1i<=mi++)
printf("%4d%4d%4d%4d%4d\n",i,HT[i].weight, HT[i].parent,HT[i].lchild, HT[i].rchild)
system("pause")
for(i=n+1i<=mi++)
{
Select(HT,i-1)
HT[s1].parent = iHT[s2].parent = i
HT[i].lchild = s1HT[i].rchild = s2
HT[i].weight = HT[s1].weight + HT[s2].weight
//添加查看，便于调试
/*printf("s1=%d,s2=%d\n",s1,s2)
for(j=1j<=ij++)
printf("%d%4d%4d%4d",j,HT[j].weight,HT[j].parent,HT[j].lchild, HT[j].rchild)
system("pause")
*/
}
cd = (char *)malloc(n*sizeof(char))
p=m
cdlen=0
for(i=1i<=mi++)
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
}
}
}
int main()
{
HuffmanTree HT
HuffmanCode HC
int *w,n,i
printf("请输入节点数：\n")
scanf("%d",&n)
HC = (HuffmanCode)malloc(n*sizeof(HuffmanCode))
w=(int *)malloc(n*sizeof(int))
printf("请输入节点的权值：\n")
for(i=0i<ni++)
scanf("%d",&w[i])
HuffmanCoding(HT,HC,w,n)
printf("输出编码：\n")
for(i=1i<=ni++)
printf("%2d(%4d):%s\n",i,w[i-1],HC[i])
return 0
system("pause")
}
#include <stdio.h>#include <string.h>
#include <stdlib.h>
#define TRUE 1
#define ERROR 0
#define OK 1
#define FALSE 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define Status int
#define MAXLENGTH 128
typedef struct HTnode
{
long weight
int parent
int lchild
int rchild
}HTNode, *HuffmanTree
typedef struct CTnode
{
long weight
char *coded_string
}CharacterTable
typedef char * *HuffmanCode
FILE *fp=NULL
void Analyse (CharacterTable * *character_table, long * *w, char * *chara, int &n)//分析所有不同的字符的权值
{
long *tmpw
char ch, *tmpchara
int i
(*character_table)=(CharacterTable *)malloc(128*sizeof(CharacterTable))//定义存放字母的数组
for(i=0i<128i++)
{
(*character_table)[i].weight=0 //初始化
(*character_table)[i].coded_string=NULL
}
ch=fgetc(fp)
while(!feof(fp))//诺到文件末尾，函数值为真
{
//m=ch
if(ch<128 &&ch>=0)
(*character_table)[ch].weight++//获得各个字母在文件中出现的次数
ch=fgetc(fp)
}
for(i=0, n=0i<128i++)
if((*character_table)[i].weight)
n++//统计有多少不同的字符数
(*w)=(long *)malloc(n*sizeof(long))//deliver the character and the weight to main
(*chara)=(char *)malloc(n*sizeof(char))
tmpw=(*w)
tmpchara=(*chara)
for(i=0i<128i++)
if((*character_table)[i].weight)
{//将权值放入*w数组中
*(*w)=(*character_table)[i].weight
*(*chara)=i//这里i是字符
(*w)++
(*chara)++
}
(*w)=tmpw
(*chara)=tmpchara//指针返回数组头
}
void Select (HuffmanTree *HT, int i, int *Min1, int *Min2)
{
int j, n, tmp1=-1, tmp2=-2
for(n=0n<in++)
{
if(!(*HT)[n].parent)
{
if(tmp1 == -1)
{
tmp1=n
continue
}
if(tmp2 == -2)
{
tmp2=n
if((*HT)[tmp1].weight >(*HT)[tmp2].weight)
{
j=tmp1
tmp1=tmp2
tmp2=j
}
continue
}
if((*HT)[n].weight <(*HT)[tmp2].weight) //scan and change
if((*HT)[n].weight <(*HT)[tmp1].weight)
tmp1=n
else
tmp2=n
}
}
*Min1=tmp1
*Min2=tmp2//tmp[Min2].weight >= tmp[Min1].weight
}
Status Huffman(HuffmanTree *HT, HuffmanCode *HC,long *w, int n)
{
int m, i, Min1, Min2, p1, p2, start, *M1, *M2
char *cd
HuffmanTree *HTp
if(n<1) return ERROR
m=2*n-1
(*HT)=(HTNode *)malloc(m*sizeof(HTNode)) //intialise Hc in main
HTp=HT
for(i=0i<ni++, w++)
{
(*HTp)[i].weight=*w
(*HTp)[i].parent=0
(*HTp)[i].lchild=0
(*HTp)[i].rchild=0
}
for(i<mi++)
{
(*HTp)[i].weight=0
(*HTp)[i].parent=0
(*HTp)[i].lchild=0
(*HTp)[i].rchild=0
}
M1=&Min1
M2=&Min2
for(i=ni<mi++)
{
Select(HT, i, M1, M2)
(*HTp)[Min1].parent=i
(*HTp)[Min2].parent=i
(*HTp)[i].lchild=Min1//左孩子要小一些
(*HTp)[i].rchild=Min2
(*HTp)[i].weight=(*HTp)[Min1].weight + (*HTp)[Min2].weight
}
//coded the weight below
(*HC)=(HuffmanCode)malloc(n*sizeof(char *))
cd=(char *)malloc(n*sizeof(char))
cd[n-1]='\0'
for(i=0i<ni++)
{
start=n-1
for(p1=i, p2=(*HTp)[p1].parentp2!=0p1=p2, p2=(*HTp)[p1].parent)
{
if( (*HTp)[p2].lchild ==p1) //编码, 左孩子为0, 右孩子为1
cd[--start]='0'
else
cd[--start]='1'
}
(*HC)[i]=(char *)malloc((n-start)*sizeof(char))
strcpy((*HC)[i],&cd[start])
} //over
return OK
}
void Weinumber_to_stringnumber(char * *stringnumber, long *w, int leaves)
{//将权值以字符数组形式存放在上米的数组中
char tmp[30]
long i, j, k
int start
for(i=0i<leavesi++)
{
start=29
tmp[start--]='\0'
for(k=w[i], j=k%10k!=0k=k/10, j=k%10)
tmp[start--]=j+'0'
stringnumber[i]=(char *)malloc((29-start)*sizeof(char))
strcpy(stringnumber[i], &tmp[start+1])
}
}
void Save_huffman_weight_dictionary(long *w, char *character, int leaves, HuffmanCode *HC)
{
char * *stringnumber
int i
FILE *fp1
fp1=fopen("weight.txt", "w")
stringnumber=(char * *)malloc(leaves * sizeof(char *))
Weinumber_to_stringnumber(stringnumber, w, leaves)
for(i=0i<leavesi++)
{
fputc(' ', fp1) // for unhuffman add '
fputc(character[i], fp1)
fputc('\t', fp1)
fputs(stringnumber[i], fp1)
fputc('\t', fp1)
fputc('\'', fp1)
fputs((*HC)[i], fp1)
fputc('\'', fp1)
fputc('\n', fp1)
}
fclose(fp1)
}
void Huffman_file_convert(HuffmanCode *HC, CharacterTable *character_table) //fp had opened
{
int i
char ch
FILE *fp2=fopen("coded.txt","w")
for( i=0i<128i++)
if(character_table[i].weight)
{
character_table[i].coded_string=*(*HC)
(*HC)++
}
ch=fgetc(fp)
while(!feof(fp))
{
if( (ch>=0 &&ch<128) &&(character_table[ch].weight) )//it is very importan to add (ch>=0 &&ch<128)
fputs(character_table[ch].coded_string,fp2)
ch=fgetc(fp)
}
fclose(fp2)
}
void fileopen1() //通过指针fp传递信息
{
char filename[100]
do{
printf("\n\n\t请输入要编码的文件:")
scanf("%s", filename)
if ((fp=fopen(filename,"r"))==NULL)
printf("\n\t不能打开此文件! 请重新输入!\n")
}while(!fp)
}
void main()
{
HuffmanTree Ht, *ht//three level pointer
HuffmanCode Hc, *hc
CharacterTable *CT, * *character_table
long *weight, * *w
char * character, * *chara
int leave //the all leaves number
ht=&Ht
hc=&Hc
w=&weight
chara=&character
character_table=&CT
fileopen1()
Analyse(character_table, w, chara, leave)
fseek(fp, 0, 0)//将文件指针还原
Huffman(ht, hc, weight, leave)//构建哈弗曼树！
Save_huffman_weight_dictionary(weight, character, leave, hc)
Huffman_file_convert(hc, CT)
fclose(fp)
}
这是我们的作业题，自己写 的……（可能输入的格式跟你要的不一致，自己改一下）注：1、 初始化创建哈夫曼树有三种选择，其中选择编译课本测试数据时和编译源文件是，调用的输入文件分别是：test.txt和input.txt；字母的哈夫曼编码都保存在文件：hmfTree.txt；
2、 用户自定义模式下，需要编码的文件内容保存在ToBeTran.txt中；课本测试数据和源文件代码分别保存在course.txt和sorse.txt中，在（1）中选择不同的选项，则在编码时调用相应的文件进行编码，编码结果保存在文件CodeFile.txt中。
3、 文件译码时，调用文件CodeFile.txt进行译码，得到的结果保存在文件TextFile.txt中。
4、 打印代码文件：调用CodeFile.txt，结果显示在终端并保存在文件CodePrin.txt中。
5、 打印哈夫曼树：用凹入表形式把哈夫曼树显示在终端，同时将它保存在文件TreePrint..txt中。
#include <stdio.h>
#include<malloc.h>
#include <string.h>
#include<fstream>
#include<iostream>
using namespace std
typedef struct {
unsigned int weight
char ch1
unsigned int parent,lchild,rchild
}HTNode,*HuffmanTree
typedef char **HuffmanCode
typedef struct {
char ch
char code[7]
}codenode,*code
void select(HuffmanTree HT,int n,int &s1,int &s2){//从哈夫曼树中选择出最小的两个节点
for(int i=1i<=ni++)
if(!HT[i].parent){
s1=i break
}
for(i++i<=ni++)
if(!HT[i].parent){
s2=i break
}
if(HT[s1].weight-HT[s2].weight){
int temp temp=s1 s1=s2 s2=temp
}
for(i=1i<=ni++)//对数组进行遍历，寻找最小的两个节点
if(!HT[i].parent){
if(HT[i].weight<HT[s1].weight){
s2=s1 s1=i
}
else if(HT[i].weight<HT[s2].weight&&i!=s1)
s2=i
}
}
void prin(){ //终端输出选择菜单
cout<<"----------------------------------------------------\n\n"
<<" ∣ I---创建哈夫曼树 ∣\n"
<<" ∣∣\n"
<<" ∣ E---文件编码 ∣\n"
<<" ∣∣\n"
<<" ∣ D---文件译码 ∣\n"
<<" ∣∣\n"
<<" ∣ P---打印代码文件 ∣\n"
<<" ∣∣\n"
<<" ∣ T---印哈夫曼树 ∣\n"
<<" ∣∣\n"
<<" ∣ O---哈夫曼树的存储结构 ∣\n"
<<" ∣∣\n"
<<" ∣ Q---退出 ∣\n"
<<"\n-----------------------------------------------------\n\n"
printf("选择菜单功能选项：")
}
void output (HuffmanTree th,int n){//输出哈夫曼树的存储结构
int i=0
cout<<"序号"<<""<<"字符"<<""<<"双亲"<<""<<"左孩子"<<""<<"右孩子"<<""<<"权值"<<endl
for(i<2*n-1i++){
th++
cout<<i<<" "<<th->ch1<<" "<<th->parent<<""<<th->lchild<<""<<th->rchild<<" "<<th->weight <<endl
}
}
void initial(HuffmanTree &HT,HuffmanCode &HC,int w[],int &n,char ch[],int &k){ //创建哈夫曼树
cout<<"----------------------------------------------------\n\n"
<<" ∣ 1---自定义 ∣\n"
<<" ∣∣\n"
<<" ∣ 2---编码课本测试数据 ∣\n"
<<" ∣∣\n"
<<" ∣ 3---编码源程序 ∣\n"
<<"\n-----------------------------------------------------\n\n"
printf("选择菜单功能选项：")
scanf("%d",&k)
if(k==1){
printf("输入需要编码的字符总数: ")
scanf("%d",&n)
printf("\n输入需要编码字符的权值:\n")
for(int d=0d<nd++) {
scanf("%d",&w[d])
}
printf("\n输入需要编码的字符串: ")
scanf("%s",ch)
}
else if(k==2){
ifstream fin2 ("test.txt")
fin2>>n
for(int d=0d<nd++)
fin2>>w[d]
fin2>>ch
fin2.close()
}
else if(k==3){
ifstream fin1 ("input.txt")
fin1>>n
for(int d=0d<nd++)
fin1>>w[d]
fin1>>ch
fin1.close()
}
if(n<=1)
return
int s1,s2,i,num=2*n-1
HuffmanTree p
HT=(HuffmanTree)malloc((num+1)*sizeof(HTNode))
for(p=HT+1,i=1i<=ni++,p++){
p->weight=w[i-1] p->lchild=0 p->parent=0 p->rchild=0p->ch1 =ch[i-1]
}
for(i<=nump++,i++){
p->weight=0 p->lchild=0 p->parent=0 p->rchild=0p->ch1 ='$'
}
for(i=n+1i<=numi++){
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 *))
char * temp=(char *)malloc(n*sizeof(char))
temp[n-1]='\0'
for(i=1i<=ni++){
int start=n-1
for(int f=HT[i].parent,h=ifh=f,f=HT[f].parent)
if(HT[f].lchild==h)
temp[--start]='0'
else
temp[--start]='1'
HC[i]=(char *)malloc((n-start)*sizeof(char))
strcpy(HC[i],&temp[start])
}
ofstream fout ("hfmTree.txt")
fout<<ch<<endl
for(int j=1j<=nj++)
fout<<HC[j]<<endl
fout.close()
free(temp)
}
void encoding(int n,int select){ //编码：对文件TobeTran.txt进行译码
char a[100],b[100][20]
ifstream fin ("hfmTree.txt")
fin>>a
for(int j=0j<nj++) fin>>b[j]
fin.close()
ifstream fin1 ("course.txt")
ifstream fin2 ("sorse.txt")
ifstream fin3 ("ToBeTran.txt")
char s[1000]
if(select==3)
fin2>>s
else if(select==2)
fin1>>s
else fin3>>s
ofstream fout ("CodeFile.txt")
while(s[0]!='\0'){
for(int i=0s[i]!='\n'&&s[i]!='\0'&&i<30i++ ){
for(int g=0a[g]!=s[i]g++)
fout<<b[g]
}
fout<<'\n'
if(select==3)
fin2>>s
else if(select==2)
fin1>>s
else fin3>>s
}
fin3.close()
fin2.close()
fin1.close()
fout.close()
}
void decoding(HuffmanTree ht,int n){ //译码：对CodeFile.txt文件进行译码
ifstream fin ("CodeFile.txt")
ofstream fout ("TextFile.txt")
char s[500]
fin>>s
HuffmanTree head=ht+2*n-1
int i=0
while(s[0]!='\0'){
while(s[i]!='\0'){
if(s[i]=='1') head=ht+head->rchild
else if(s[i]=='0') head=ht+head->lchild
if((head->lchild)==0&&(head->rchild) ==0) {
fout<<(head->ch1)
head=ht+2*n-1
}
i++
}
fout<<' '
i=0
fin>>s
}
fin.close()
fout.close()
}
void Print(){ //打印代码文件，显示在终端，每行50个代码
ifstream fin ("CodeFile.txt")
char s[2000]
int j=0
int i=1
fin>>s
ofstream fout ("CodePrin.txt")
while(s[0]!='\0'){
for(s[j]!='\0'j++){
printf("%c",s[j])
fout<<s[j]
if(i%50==0){
fout<<endl
printf("\n")
}
i++
}
j=0
fin>>s
}
fin.close()
printf("\n")
fout.close()
}
void printTree( HuffmanTree node,HuffmanTree node1, int level ) { //打印哈夫曼树形（在参数的传递上，是文科给自己提出的意见才很好的解决了之后的 *** 作难题^^）
if( node == NULL ) return
if( node1->rchild!=0) {
printTree( node,node+node1->rchild, level + 1 )
}
fstream fout
fout.open ("TreePrint.txt",ios::in | ios::out|ios::ate)//这个挺有用的：在文件末尾加入内容
for( int i = 0i <leveli++ ) {
fout<<"|……"
printf( "……")
}
fout<<node1->weight<<endl
printf( "%d\n", node1->weight )
if( node1->lchild!=0 ) {
printTree( node,node+node1->lchild, level + 1 )
}
fout.close()
}
void main(){
int select
int n
char ch[100]
int w[100]
HuffmanTree HT=NULL
HuffmanCode hc=NULL
prin()
char c='I'
scanf("%c",&c)
while(c!='Q'){
switch(c){
case 'I':
initial(HT,hc,w,n,ch,select)
prin()
break
case 'E':
encoding(n,select)
prin()
break
case 'D':
decoding(HT,n)
prin()
break
case 'P':
Print()
prin()
break
case 'T':
printTree(HT,HT+2*n-1,1)
prin()
break
case 'O':
output(HT,n)
prin()
break
}
scanf("%c",&c)
}
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）