投稿
  1. 首页
  2. 软件运维

求哈夫曼编码

蒙牛三聚氰胺 • 2023-5-25 • 软件运维 • 阅读 11

求哈夫曼编码,第1张

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

////////////////////姿颤//////////////////////////////////////////////////////////

/*定义赫夫曼树结点的结构体变量，存放结点的权值、字符、双亲、坐孩子和右孩子*/

typedef struct{

int weight

char ch//增加一个域用于存放该节点的字符

int parent,lchild,rchild

}HTNode,*HuffmanTree

typedef char **HuffmanCode//指向赫夫曼编码的指针

//////////////////////////////////////////////////////////////////////////////

/*本程序用到的函数原型*/

void welcome() //打印 *** 作选择界面

void HuffmanCoding(HuffmanTree &,char *,int *,int)//建立赫夫曼树的算法

void select(HuffmanTree HT,int j,int *s1,int *s2)//从目前已建好的赫夫曼树中选择parent为0且weight最小的两个结点

void Init()//输入n个字符及其对应的权值，根据权值建立哈夫曼树

void Coding()//编码

void Decoding()//译塌册卜码

void Print_code()//打印译码好的代码文件

void Print_tree()//以凹凸表形式打印哈夫曼树

int Read_tree(HuffmanTree &)//从文件中读入赫夫曼树

void find(HuffmanTree &HT,char *code,char *text,int i,int m)//译码时根据01字符串寻找相应叶子节点的递归算法

void Convert_tree(unsigned char T[100][100],int s,int *i,int j)//将内存中的赫夫曼树转换团穗成凹凸表形式的赫夫曼树

HuffmanTree HT//全局变量，指向存放赫夫曼树的存储空间

int n=0//全局变量，存放赫夫曼树叶子结点的数目

int main()

{

char select

while(1)

{

welcome()

scanf("%c",&select)

switch(select)

{

case 'i':

case 'I':Init()break

case 'c':

case 'C':Coding()break

case 'd':

case 'D':Decoding()break

case 'p':

case 'P':Print_code()break

case 't':

case 'T':Print_tree()break

case 'e':

case 'E':exit(1)

default :printf("Input error!\n")

}

getchar()

}

return 0

}

void welcome() //打印 *** 作选择界面

{

printf("*-----------------------------------------------------*\n")

printf("|What do you want to do? |\n")

printf("|-----------------------------------------------------|\n")

printf("| |\n")

printf("| I--------------------------Init the Huffman tree. |\n")

printf("| C--------------------------Code your file. |\n")

printf("| D--------------------------Decode the code.|\n")

printf("| P--------------------------Print the codefile. |\n")

printf("| T--------------------------Print the Huffman tree. |\n")

printf("| |\n")

printf("*-----------------------------------------------------*\n")

}

//////////////////////////////////////////////////////////////////////////////////////

/*初始化函数，输入n个字符及其对应的权值，根据权值建立哈夫曼树，并将其存于文件hfmtree中*/

void Init()

{

FILE *fp

int i,n,w[52]//w数组存放n个字符的权值

char character[52]//存放n个字符

printf("\n输入字符个数 n:")

scanf("%d",&n) //输入字符集大小

printf("输入%d个字符及其对应的权值:\n",n)

for (i=0i<ni++)

{

char b=getchar()

scanf("%c",&character[i])

scanf("%d",&w[i]) //输入n个字符和对应的权值

}

HuffmanCoding(HT,character,w,n) //建立赫夫曼树

if((fp=fopen("hfmtree.txt","w"))==NULL)

printf("Open file hfmtree.txt error!\n")

for (i=1i<=2*n-1i++)

{

if(fwrite(&HT[i],sizeof(HTNode),1,fp)!=1) //将建立的赫夫曼树存入文件hfmtree.txt中

printf("File write error!\n")

}

printf("\n建立赫夫曼树成功，已将其存于文件hfmtree.txt中\n")

fclose(fp)

}

///////////////////////////////////////////////////////////////////////////////////

//////建立赫夫曼树的算法///////////////////////////////////////////////////////////

void HuffmanCoding(HuffmanTree &HT,char *character,int *w,int n)

{

int m,i,s1,s2

HuffmanTree p

if(n<=1) return

m=2*n-1

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

for(p=HT+1,i=1i<=n++i,++p,++character,++w)

{p->ch=*characterp->weight=*wp->parent=0p->lchild=0p->rchild=0}

for(i<=m++i,++p) {p->ch=0p->weight=0p->parent=0p->lchild=0p->rchild=0}

for(i=n+1i<=m++i)

{

select(HT,i-1,&s1,&s2)

HT[s1].parent=iHT[s2].parent=i

HT[i].lchild=s1HT[i].rchild=s2

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

}

}

///////////////////////////////////////////////////////////////////////////////

/*从HT[1]到HT[j]中选择parent为0且weight最小的两个结点，用s1和s2返回其序号*/

void select(HuffmanTree HT,int j,int *s1,int *s2)

{

int i

//找weight最小的结点

for (i=1i<=ji++)

if (HT[i].parent==0)

{*s1=ibreak}

for (i<=ji++)

if ((HT[i].parent==0)&&(HT[i].weight<HT[*s1].weight))

*s1=i

HT[*s1].parent=1

//找weight次小的结点

for (i=1i<=ji++)

if (HT[i].parent==0)

{*s2=ibreak}

for (i<=ji++)

if ((HT[i].parent==0)&&(i!=*s1)&&(HT[i].weight<HT[*s2].weight))

*s2=i

}

///////////////////////////////////////////////////////////////////////////////

/*对文件tobetrans中的正文进行编码，然后将结果存入文件codefile中*/

void Coding()

{

FILE *fp,*fw

int i,f,c,start

char *cd

HuffmanCode HC

if(n==0)

n=Read_tree(HT)//从文件hfmtree.txt中读入赫夫曼树,返回叶子结点数

/////以下程序段求赫夫曼树中各叶子节点的字符对应的的编码，并存于HC指向的空间中

{

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

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

cd[n-1]='\0'

for(i=1i<=n++i)

{

start=n-1

for(c=i,f=HT[i].parentf!=0c=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)

}

/////////////////////////////////////////////////////////////////////////////////////

if((fp=fopen("tobetrans.txt","rb"))==NULL)

printf("Open file tobetrans.txt error!\n")

if((fw=fopen("codefile.txt","wb+"))==NULL)

printf("Open file codefile.txt error!\n")

char temp

fscanf(fp,"%c",&temp)//从文件读入第一个字符

while(!feof(fp))

{

for(i=1i<=ni++)

if(HT[i].ch==temp) break //在赫夫曼树中查找字符所在的位置

for(int r=0HC[i][r]!='\0'r++) //将字符对应的编码存入文件

fputc(HC[i][r],fw)

fscanf(fp,"%c",&temp) //从文件读入下一个字符

}

fclose(fw)

fclose(fp)

printf("\n对文件hfmtree.txt编码成功,结果已存入codefile.txt中。\n\n")

}

/////////////////////////////////////////////////////////////////////////

/*将文件codefile中的代码进行译码，结果存入文件textfile中*/

void Decoding()

{

FILE *fp,*fw

int m,i

char *code,*text,*p

if(n==0)

n=Read_tree(HT)//从文件hfmtree.txt中读入赫夫曼树,返回叶子结点数

if((fp=fopen("codefile.txt","rb"))==NULL)

printf("Open file codefile.txt error!\n")

if((fw=fopen("textfile.txt","wb+"))==NULL)

printf("Open file textfile.txt error!\n")

code=(char *)malloc(sizeof(char))

fscanf(fp,"%c",code) //从文件读入一个字符

for(i=1!feof(fp)i++)

{

code=(char *)realloc(code,(i+1)*sizeof(char))//增加空间

fscanf(fp,"%c",&code[i])//从文件读入下一个字符

}

code[i-1]='\0'

/////////到此codefile.txt文件中的字符已全部读入，存放在code数组中

text=(char *)malloc(100*sizeof(char))

p=text

m=2*n-1

if(*code=='0')

find(HT,code,text,HT[m].lchild,m) //从根节点的左子树去找

else

find(HT,code,text,HT[m].rchild,m) //从根节点的右子树去找

for(i=0p[i]!='\0'i++) //把译码好的字符存入文件textfile.txt中

fputc(p[i],fw)

fclose(fp)

fclose(fw)

printf("\n对codefile.txt文件译码成功，结果已存入textfile.txt文件。\n\n")

}

//////////////////////////////////////////////////////////////////////////////////////////////////////

/*将文件codefi1e以紧凑格式显示在终端上,每行50个代码。同时将此字符形式的编码文件写入文件codeprint中。*/

void Print_code()

{

FILE *fp,*fw

char temp

int i

if((fp=fopen("codefile.txt","rb"))==NULL)

printf("Open file codefile.txt error!\n")

if((fw=fopen("codeprint.txt","wb+"))==NULL)

printf("Open file codeprint.txt error!\n")

printf("\n文件codefi1e以紧凑格式显示如下:\n")

fscanf(fp,"%c",&temp) //从文件读入一个字符

for (i=1!feof(fp)i++)

{

printf("%c",temp)

if(i%50==0) printf("\n")

fputc(temp,fw) //将该字符存入文件codeprint.txt中

fscanf(fp,"%c",&temp) //从文件读入一个字符

}

printf("\n\n此字符形式的编码已写入文件codeprint.txt中.\n\n")

fclose(fp)

fclose(fw)

}

//////////////////////////////////////////////////////////////////////////////////////////////////

/*将已在内存中的哈夫曼树以凹凸表形式显示在屏幕上，同时将此字符形式的哈夫曼树写入文件treeprint中。*/

void Print_tree()

{

unsigned char T[100][100]

int i,j,m=0

FILE *fp

if(n==0)

n=Read_tree(HT)//从文件hfmtree.txt中读入赫夫曼树,返回叶子结点数

Convert_tree(T,0,&m,2*n-1)//将内存中的赫夫曼树转换成凹凸表形式的树，存于数组T中

if((fp=fopen("treeprint.txt","wb+"))==NULL)

printf("Open file treeprint.txt error!\n")

printf("\n以凹凸表形式打印已建好的赫夫曼树：\n")

for(i=1i<=2*n-1i++)

{

for (j=0T[i][j]!=0j++)

{

if(T[i][j]==' ') {printf(" ")fputc(T[i][j],fp)}

else

{printf("%d",T[i][j])fprintf(fp,"%d\n",T[i][j])}

}

printf("\n")

}

fclose(fp)

printf("\n此字符形式的哈夫曼树已写入文件treeprint.txt中.\n\n")

}

//////////////////////////////////////////////////////////////////////////////////

/*从文件hfmtree.txt中读入赫夫曼树，返回叶子节点数*/

int Read_tree(HuffmanTree &HT)

{

FILE *fp

int i,n

HT=(HuffmanTree)malloc(sizeof(HTNode))

if((fp=fopen("hfmtree.txt","r"))==NULL)

printf("Open file hfmtree.txt error!\n")

for (i=1!feof(fp)i++)

{

HT=(HuffmanTree)realloc(HT,(i+1)*sizeof(HTNode))//增加空间

fread(&HT[i],sizeof(HTNode),1,fp)//读入一个节点信息

}

fclose(fp)

n=(i-1)/2

return n

}

////////////////////////////////////////////////////////////////

/*译码时根据01字符串寻找相应叶子节点的递归算法*/

void find(HuffmanTree &HT,char *code,char *text,int i,int m)

{

if(*code!='\0') //若译码未结束

{

code++

if(HT[i].lchild==0&&HT[i].rchild==0) //若找到叶子节点

{

*text=HT[i].ch//将叶子节点的字符存入text中

text++

if((*code=='0'))

find(HT,code,text,HT[m].lchild,m)//继续从根节点的左子树找

else

find(HT,code,text,HT[m].rchild,m)//继续从根节点的右子树找

}

else //如果不是叶子节点

if(*code=='0')

find(HT,code,text,HT[i].lchild,m) //从该节点的左子树去找

else

find(HT,code,text,HT[i].rchild,m) //从该节点的右子树去找

}

else

*text='\0'//译码结束

}

////////////////////////////////////////////////////////////////////////

/*将内存中的赫夫曼树转换成凹凸表形式的赫夫曼树*/

void Convert_tree(unsigned char T[100][100],int s,int *i,int j)

{

int k,l

l=++(*i)

for(k=0k<sk++)

T[l][k]=' '

T[l][k]=HT[j].weight

if(HT[j].lchild)

Convert_tree(T,s+1,i,HT[j].lchild)

if(HT[j].rchild)

Convert_tree(T,s+1,i,HT[j].rchild)

T[l][++k]='\0'

}

自己改改吧！

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include <ctype.h>激备顷

#include<limits.h>

int function1(char ch,char *s)

{

int i

for(i=0s[i]!='\0'i++)

{

if(ch==s[i])return 0

}

return 1

}

typedef struct

{

unsigned int weight

unsigned int parent,lchild,rchild

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

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

// algo6-1.cpp 求赫夫曼编码。实现算法6.12的程序

int min(HuffmanTree t,int i)

{

// 函数void select()调用

int j,flag

unsigned int k=UINT_MAX// 取k为不小于可能的值

for(j=1j<=ij++)

if(t[j].weight<k&&t[j].parent==0)

k=t[j].weight,flag=j

t[flag].parent=1

return flag

}

void select(HuffmanTree t,int i,int &s1,int &s2)

{

// s1为最小的两个值明陆中序号小的那个

s1=min(t,i)

s2=min(t,i)

/* if(s1>s2)

{

j=s1

s1=s2

s2=j

}*/

}

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n) // 算法6.12

{

// w存放n个字符的权值(均>0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC

int m,i,s1,s2,start

unsigned 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=1i<=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+1i<=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].rchild=s1

HT[i].lchild=s2

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

// printf("HT[%d].lchild:%d HT[%d].rchild:%d\n",i,s2,i,s1)

}

// 从叶子到根逆向求每个字符的赫夫曼编码

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

// 分配n个字符编码的头指针向量([0]不用)

cd=(char*)malloc(n*sizeof(char))// 分配求编码的工作空间

cd[n-1]='\0'// 编码结束符

for(i=1i<=ni++)

{

// 逐个字符求赫夫曼编码

start=n-1// 编码结束符位置

for(c=i,f=HT[i].parentf!=0c=f,f=HT[f].parent)

// 从叶子到根逆向求编码

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

cd[--start]='1'

else

cd[--start]='0'

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

// 为第i个字符编码分配空间

strcpy(HC[i],&cd[start])// 从cd复制编码(串)到HC

}

free(cd)// 释放工作空间

}

void swap1(int *a ,int *b)

{

int t

t=*a

*a=*b

*b=t

}

void swap2(char *a,char *b)

{

char ch

ch=*a

*a=*b

*b=ch

}

int main(void)

{

HuffmanTree HT

HuffmanCode HC

char *s1,*s2

int i,j=0,n,count,*m,t,flag=1

scanf("%d",&n)

getchar()

s1=(char*)malloc((n+n)*sizeof(char))

s2=(char*)malloc(n*sizeof(char))

memset(s2,'\0',n*sizeof(char))

gets(s1)

count=strlen(s1)

for(i=0i<counti++)

{

if(!isspace(*(s1+i)))

{

if(function1(*(s1+i),s2))

{

*(s2+j)=*(s1+i)

j++

}

}

else

}

m=(int*)malloc(j*sizeof(int))

for(i=0i<ji++)

*(m+i)=0

for(t=0t<jt++)

{

for(i=0i<counti++)

{

if(*(s2+t)==*(s1+i))

*(m+t)+=1

}

}

for(i=0i<ji++)

while(flag)

{

flag = 0

for (t=0t<j-1t++)

{

if(*(m+t)<*(m+t+1))

{

swap1(m+t,m+t+1)

swap2(s2+t,s2+t+1)

flag=1

}

}

}

HuffmanCoding(HT,HC,m,j)

for(i=1,t=0i<=ji++,t++)

{

printf("%c %d %s\n",*(s2+t),*(m+t),HC[i])

}

return 0

}

/* algo6-1.c 求哈夫曼编码。实现算法6.12的程序 */

//------------------- 公用的常量和类型 ----------------------------

#include<stdio.h>

#include <malloc.h>

#include <stdlib.h>

#include <string.h>

/毁败/函数结果状态代码

#defineTRUE1

#defineFALSE0

#defineOK1

#defineERROR0

#defineINFEASIBLE-1

#defineOVERFLOW-2

#defineUINT_MAX 1000

typedef intStatus

/* c6-7.h 哈夫曼银茄树和哈夫曼编码的存储表示 */

typedef struct HTNode

{

char leaf

unsigned int weight

unsigned int parent,lchild,rchild

}HTNode,*HuffmanTree/* 动态分配数组存储哈夫曼编码表 */

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

typedef struct Node

{

char leaf

unsigned int weight

struct Node * next

}LeafNode,*LeafLink

typedef struct

{

LeafLink head

unsigned len

}LeafLinkList

int min1(HuffmanTree t,int i)

{ /* 函数void select()调用 */

int j,flag

unsigned int k=UINT_MAX/* 取k为不小于可能的值 */

for(j=1j<=ij++)

if(t[j].weight<k&&t[j].parent==0)

k=t[j].weight,flag=j

t[flag].parent=1

return flag

}

void select(HuffmanTree t,int i,int *s1,int *s2)

{ /* s1为最小的两个值中序号小的那个 */

int j

*s1=min1(t,i)

*s2=min1(t,i)

if(*s1>*s2)

{

j=*s1

*s1=*s2

*s2=j

}

}

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC, LeafLinkList L) /* 算法6.12 */

{ /* w存放n个字符纤搏颤的权值(权值均需大于0),构造哈夫曼树HT,并求出n个字符的哈夫曼编码HC*/

int m,i,s1,s2,start

int n=L.len

unsigned c,f

LeafLink ptr

HuffmanTree p

char *cd

if(n<=1)

return

m=2*n-1

printf("表长为%d\t哈夫曼树含节点数为%d\n",n,m)

HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode))/* 0号单元未用 */

ptr=L.head->next

for(p=HT+1,i=1i<=n++i,++p,ptr=ptr->next)

{

(*p).leaf=ptr->leaf

printf("%d\t",(*p).leaf)

(*p).weight=ptr->weight

printf("%d\n",(*p).weight)

(*p).parent=0

(*p).lchild=0

(*p).rchild=0

}

for(i<=m++i,++p)

{

(*p).parent=0

(*p).leaf=0

}

for(i=n+1i<=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=1i<=ni++)

{ /* 逐个字符求哈夫曼编码 */

start=n-1/* 编码结束符位置 */

for(c=i,f=HT[i].parentf!=0c=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)/* 释放工作空间 */

for(i=1i<=ni++)

{

printf("%c编码为%s:\n",HT[i].leaf,HC[i])

}

}

void InitLeafList(LeafLinkList &L)

{

L.head=(LeafLink)malloc(sizeof(LeafLink))

L.head->next=NULL

L.len=0

}

void PrintList(LeafLinkList L)

{

LeafLink p

p=L.head->next

printf("打印链表\n")

printf("表长为%d\n",L.len)

while(p!=NULL)

{

printf("%c or %d,%u\t",p->leaf,p->leaf,p->weight)

printf("打印一个节点\n")

p=p->next

}

printf("打印结束\n")

printf("\n")

}

void EnLeafList(LeafLinkList &L,char ch)

{

LeafLink p,pre,temp

int flag=0

pre=p=L.head

printf("%d即为%c******\n\n",ch,ch)

if(p->next==NULL)//p->next=NULL则为第一次插入 *** 作

{

printf("第一次插入\n")

temp=(LeafLink)malloc(sizeof(LeafNode))

temp->leaf=ch

temp->weight=1

temp->next=NULL

p->next=temp

L.len++

}

else

{

p=p->next

while(p!=NULL)

{

if(ch==p->leaf)

{

p->weight++

printf("加权\n")

p=NULL

flag=1

} //权重加一

else if(ch<p->leaf) //插入

{

printf("插入A\n")

temp=(LeafLink)malloc(sizeof(LeafNode))

temp->leaf=ch

temp->weight=1

temp->next=p

pre->next=temp

L.len++

flag=1

p=NULL

}

else //继续寻找插入点

{

pre=p

p=p->next

}

}

if(p==NULL&&flag!=1) //若p=NULL则插到链尾

{

printf("插入B\n")

temp=(LeafLink)malloc(sizeof(LeafNode))

temp->leaf=ch

temp->weight=1

temp->next=NULL

pre->next=temp

L.len++

}

}

}

void EnCoding()

{

FILE *fp,*fr,*fc

HuffmanTree HT

HuffmanCode HC

int i,n

LeafLinkList L

InitLeafList(L)

char filename[15]

char ch

printf("请输入文件名:\n ")

scanf("%s",filename)

if( !(fp=fopen(filename,"r")) )

{

printf("打开文件失败，请输入正确的文件名!! ")

exit(0)

}

ch=getchar()//接收执行scanf语句时最后输入的回车符

printf("文件已经打开\n")

while(!feof(fp))

{

ch=fgetc(fp)

if(ch==-1)

{

printf("结束统计\n")

}

else

{

EnLeafList(L,ch)

}

}

PrintList(L)

HuffmanCoding(HT,HC, L)

n=L.len

for(i=1i<=ni++)

{

puts(HC[i])

}

char TreeName[15]

printf("把哈夫曼树存入文件，请输入文件名:\n ")

scanf("%s",TreeName)

if( !(fr=fopen(TreeName,"wb")) )

{

printf("打开文件失败，请输入正确的文件名!! ")

exit(0)

}

ch=getchar()//接收执行scanf语句时最后输入的回车符

printf("文件已经打开\n")

//把哈夫曼树存入文件

printf("%d\n",n)

printf("把树的长度先存入\n")

putw(n,fr) //把树的长度先存入

for(i=1i<=2*n-1i++)

if(fwrite(&HT[i],sizeof(struct HTNode),1,fr)!=1)

printf("文件写入出错\n")

fclose(fr)

printf("打印原来的树\n")

for(i=1i<=2*n-1i++)

printf("%c %u %u %u %u\n",HT[i].leaf ,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild )

fclose(fr)

printf("把编码结果存入文件，请输入文件名:\n ")

char CodeFileName[15]

scanf("%s",CodeFileName)

if( !(fc=fopen(CodeFileName,"wb")) )

{

printf("打开文件失败，请输入正确的文件名!! ")

exit(0)

}

ch=getchar() //接收执行scanf语句时最后输入的回车符

printf("待编码的文件位置指针重新指向开始位置\n")

printf("对待编码文件进行编码，编码同步显示，并将结果存入指定的文件\n")

rewind(fp)

while(!feof(fp))

{

ch=fgetc(fp)

printf("%c\n",ch)

if(ch==-1)

{

printf("结束编码\n")

}

else

{

for(int tap=0,i=1tap==0&&i<=n)//查找，该叶子对应的编码串

{

if(ch==HT[i].leaf) //找到，打印出对应的编码，并存入文件

{

printf("%s\n",HC[i])

fputs(HC[i],fc) //将编码字符串存入文件

tap=1

}

else

{

i++

}

}

}

}

fclose(fp) //关闭文件

fclose(fc) //关闭文件

}

int decode(FILE *fc,HuffmanTree HT,int n)

{

while(!feof(fc))

{

char ch=fgetc(fc)

if(ch=='0')

{

n=HT[n].lchild

if(HT[n].leaf!=0)

{

printf("%c",HT[n].leaf)

return OK

}

else

{

decode(fc,HT,n)

return OK

}

}

else if(ch=='1')

{

n=HT[n].rchild

if(HT[n].leaf!=0)

{

printf("%c",HT[n].leaf)

return OK

}

else

{

decode(fc,HT,n)

return OK

}

}

else return OK

}

return ERROR

}

void Decoding() //解码文件，并将结果显示出来

{

FILE *fc,*fr

char CodeFileName[15],ch,TreeName[15]

int i

printf("解码文件，请输入文件名(如*.dat):\n ")

scanf("%s",CodeFileName)

if( !(fc=fopen(CodeFileName,"r")) )

{

printf("打开文件失败，请输入正确的文件名!! ")

exit(0)

}

ch=getchar()//接收执行scanf语句时最后输入的回车符

printf("存放编码结果文件已经打开\n")

//读入哈夫曼树

HuffmanTree HT

printf("取出对应的哈夫曼树文件，请输入文件名,\n")

scanf("%s",TreeName)

if( !(fr=fopen(TreeName,"rb")) ) //打开存放哈夫曼树的文件

{

printf("打开文件失败，请输入正确的文件名!! ")

exit(0)

}

int n=getw(fr) //将叶子数目取出

printf("叶子数目%d\n",n)

HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode)) /* 然后分配空间，0号单元未用 */

for(i=1i<=2*n-1i++)

if(fread(&HT[i],sizeof(struct HTNode),1,fr)!=1)

printf("文件读出出错\n")

int length=2*n-1//总长度

printf("总结点数目为：%d\n",n)

printf("该文件译码后得到的源文件为：\n")

printf("**************************************\n")

while(!feof(fc))

{

decode(fc,HT,length)

}

printf("**************************************\n")

printf("\n\n")

}

int PreOrderPrint(HuffmanTree HT,int n,int count)

{

if(HT[n].lchild)

{

for(int i=0i<counti++)

printf(" ")

printf("%u\n",HT[n].weight)

if( PreOrderPrint(HT,HT[n].lchild, ++count) )

if (PreOrderPrint(HT,HT[n].rchild, ++count))

return OK

return ERROR

}

else return OK

}

void PrintTree()

{

//读入哈夫曼树

FILE *fr

char TreeName[15]

HuffmanTree HT

printf("取出对应的哈夫曼树文件(如*.dat)，请输入文件名,\n")

scanf("%s",TreeName)

if( !(fr=fopen(TreeName,"rb")) ) //打开存放哈夫曼树的文件

{

printf("打开文件失败，请输入正确的文件名!! ")

exit(0)

}

int n=getw(fr) //将叶子数目取出

printf("含叶子数%d\n",n)

HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode)) /* 然后分配空间，0号单元未用 */

for(int i=1i<=2*n-1i++)

if(fread(&HT[i],sizeof(struct HTNode),1,fr)!=1)

printf("文件读出出错\n")

int count=0

n=2*n-1

printf("总结点数目为；%d\n",n)

printf("哈夫曼树的存储形式为：\n")

for(i=1i<=ni++)

{

printf("%c,%u,%u,%u,%u\n",HT[i].leaf,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild)

}

printf("哈夫曼树的凹入表形式为：\n")

PreOrderPrint(HT,n,count)

}

void PrintCodeFile()

{

FILE *fc

printf("打印编码后的文件，请输入文件名(如*.dat):\n ")

char CodeFileName[15]

scanf("%s",CodeFileName)

if( !(fc=fopen(CodeFileName,"r")) )

{

printf("打开文件失败，请输入正确的文件名!! ")

exit(0)

}

char ch=getchar()//接收执行scanf语句时最后输入的回车符

printf("打印编码后的文件，打印方法一\n")

int flag=1

while(!feof(fc))

{

ch=fgetc(fc)

if(ch==-1)

{

printf("结束打印\n")

}

else

{

printf("%c",ch)

if(flag<=49)

flag++

else

{

flag=1

printf("\n")

}

}

}

printf("打印编码后的文件，打印方法二\n")

rewind(fc)

char str[50]

while(!feof(fc))

{

fgets(str,51,fc)

puts(str)

}

fclose(fc) //关闭文件

}

void Initialization()//系统初始化

{

printf("**************************************\n")

printf("*编码文件请输入e\n*译码文件请输入d\n*打印编码后的文件请输入p\n*打印哈夫曼树请输入t\n*结束请输入q \n")

printf("**************************************\n")

printf("\n\n\t\t字符:\n\n\n")

printf("**************************************\n")

printf("* 输入一个字符:e,d,p,t or q *\n")

printf("**************************************\n")

}

int read(char cmd)

{

int i,flag=0

char choice[10]={'e','E','d','D','p','P','T','t','Q','q'}

for(i=0i<10i++)

{

if(cmd==choice[i]) flag++

}

if(flag==1) return FALSE

else return TRUE

}

void ReadCommand(char &cmd) // 读入 *** 作命令符

{

do

{

cmd=getchar()

}

while(read(cmd))

}

void Interpret(char cmd) //解释执行 *** 作命令

{

switch(cmd)

{

case 'e':case'E':

EnCoding()

Initialization()

break

case 'd':case'D':

Decoding()

Initialization()

break

case 'p':case'P':

PrintCodeFile()

Initialization()

break

case't':case'T':

PrintTree() // Print()

Initialization()

break

case 'q': case'Q':exit(0)

break

default: printf("Error\n")break

}

}

void main() //用户驱式

{

char cmd

Initialization() //初始化

do

{

ReadCommand(cmd)//读入一个 *** 作命令符

Interpret(cmd) //解释执行 *** 作命令符

}

while(cmd!='q'&&cmd!='Q')

EnCoding()

Decoding()

}

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/yw/12479583.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
蒙牛三聚氰胺 蒙牛三聚氰胺 一级用户组
0 0
上一篇 2023-05-25
下一篇 2023-05-25

发表评论

登录后才能评论

评论列表（0条）

保存