霍夫曼编码用c语言实现

2023-02-22 04:52:02Python015

霍夫曼编码用c语言实现,第1张

以前写的，证明最优子结构，随便一本算法书上就有.

#include<stdio.h>

#include<stdlib.h>

#define

NIL

-2

#define

Size_Max_bm

#define

left(i)

(2*(i)+1)

#define

right(i)

(2*(i)+2)

#define

swap(a,b)

{cjys

tt=(a)(a)=(b)(b)=t}

#define

parent(i)

((i)%2?((i)-1)/2:((i)-2)/2)typedef

struct

cjys

{

char

int

struct

cjys

*left

struct

cjys

*right

}cjystypedef

struct

cjdl

{

int

size

int

leapsize

cjys

}cjdl

cjys

*fpnn(void)

void

input(cjdl

*p)

cjys

*fpnn(void)

void

zxdwh(cjys

*p,

int

leapsize)

void

rd(cjdl

*p,

cjys

tp)

cjys

cd(cjdl

*p)

void

hbs(cjdl

*p)

cjys

*cjs(cjdl

*p)

void

bls(cjys

*p,int

*jl,

int

void

disp(char

*tp,

cjys

*p)int

main()

{

cjdl

char

x[255]

cjys

*re=NULL

int

jl[Size_Max_bm]

input(&p)

re=cjs(&p)

printf("对照编码图为:\n")

bls(re,jl,0)

freopen("CON","r",stdin)

printf("输入Huffman码(VLC):")

scanf("%s",x)

disp(x,re)

system("pause")

}

void

input(cjdl

*p)

{

int

cjys

*tp

tp=fpnn()

printf("输入字母个数:")

scanf("%d",

&p->size)

p->p=malloc(sizeof(cjys)*p->size)

p->leapsize=0

for(i

p->sizei++)

{

printf("输入第%d字母:",i+1),scanf("

%c",&tp->sj)

printf("输入出现次数(频率整数):"),scanf("%d",&tp->pl)

rd(p,*tp)

}

free(tp)

}

cjys

*fpnn(void)

{

cjys

*p=NULL

p=malloc(sizeof(cjys))

p->left=NULL

p->right=NULL

return

}

void

zxdwh(cjys

*p,

int

leapsize)

{

int

l=left(i),

r=right(i),

mini=i

if(l<leapsize

p[l].pl<p[mini].pl)

mini=l

if(r<leapsize

p[r].pl<p[mini].pl)

mini=r

if(mini

{

swap(p[i],p[mini])

zxdwh(p,mini,leapsize)

}

void

rd(cjdl

*p,

cjys

tp)

{

if(p->leapsize

p->size)

{

printf("队列已满!")

exit(0)

}

p->p[p->leapsize]=tp

int

j=p->leapsize,k=parent(j)

while(k>=0

p->p[j].pl

p->p[k].pl)

{

swap(p->p[j],p->p[k])

j=k

k=parent(j)

}

p->leapsize++

}

cjys

cd(cjdl

*p)

{

if(p->leapsize

{

printf("队列已空!")

exit(0)

}

cjys

tp=p->p[0]

p->leapsize--

p->p[0]=p->p[p->leapsize]

zxdwh(p->p,0,p->leapsize)

return

}

void

hbs(cjdl

*p)

{

cjys

*p1=NULL,

*p2=NULL

cjys

p1=fpnn()

p2=fpnn()

*p1=cd(p)

*p2=cd(p)

tp.left=p1

tp.right=p2

tp.pl=p1->pl+p2->pl

tp.sj=NIL

rd(p,tp)

}cjys

*cjs(cjdl

*p)

{

int

n=p->leapsize

cjys

*tp=NULL

tp=fpnn()

for(i

n-1

i++)

hbs(p)

*tp=p->p[0]

return

}

void

bls(cjys

*p,

int

*jl,

int

{

if(p

NULL)

return

if(p->sj!=NIL)

{

int

printf("%c:",p->sj)

for(i2

i2++)

printf("%d",jl[i2])

printf("\n")

}

jl[i]=0

bls(p->left,jl,i+1)

jl[i]=1

bls(p->right,jl,i+1)

}

void

disp(char

*tp,

cjys

*p)

{

cjys

*ttp=NULL

int

pd=0

while(1)

{

ttp=p

while(1)

{

if(ttp->sj

NIL)

{

printf("%c",ttp->sj)

break

}

if(*tp

'\0')

{

pd=1

break

}

if(*tp++

'0'

)

ttp=ttp->left

else

ttp=ttp->right

}

if(pd)

break

}

说明：本程序是依据严蔚敏的数据结构（C语言版）上的代码实现的。

#pragmaonce

#include<stdio.h>

#include<tchar.h>

#include<stdlib.h>

#define MAX 100

typedefstruct{//节点

int weight

int parent, lchild, rchild

}HTNode, *HuffmanTree

typedefchar **HuffmanCode //字符串数组，用于存储叶子节点的编码

void SelectMinNode(HuffmanTree &HT, int m, int &i1, int &i2) //找出权值最小的两个节点对应的数组下标

{

HuffmanTree p = HT

int s1, s2

s1 = s2 = MAX

i1 = i2 = 1

for(int i=1i<=mi++)

{

if(!(p+i)->parent)

{

if((p+i)->weight <s1)

{

i2 = i

s1 = (p+i)->weight

}

for(int i=1i<=mi++)

{

if(!(p+i)->parent &&i!=i2)

{

if((p+i)->weight <s2)

{

i1 = i

s2 = (p+i)->weight

}

void StrCopy(char *p, char *q, int start) //从字符数组中第start个字符开始复制

{

char *c1, *c2

c1 = p

while(q[start] != '\0')

{

*c1 = q[start]

c1++

start++

}

*c1 = q[start]//别忘了将‘\n’复制过来

}

void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n)

{ //HT赫夫曼树节点数组，HC存储赫夫曼编码，*w 节点权值数组的首地址，n节点个数

int i, i1, i2, m

HuffmanTree p

if(n<=1) return

m = 2 * n -1//n个叶子节点的赫夫曼树的节点总数为2n-1，可以结合树的度为n-1自己证明。

HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode))//数组首元素不使用，故多分配一个空间

p = HT + 1

for(i=1i<=n++i,++p,++w) //n个叶子节点初始化

{

p->weight = *w

p->lchild = 0

p->rchild = 0

p->parent = 0

}

for(i<=m++i,++p) //非叶子节点初始化

{

p->weight = 0

p->lchild = 0

p->rchild = 0

p->parent = 0

}

for(i=n+1i<=m++i) //对非叶子节点重新计算

{

SelectMinNode(HT, i-1, i1, i2)

HT[i1].parent = i

HT[i2].parent = i

HT[i].lchild = i1

HT[i].rchild = i2

HT[i].weight = HT[i1].weight + HT[i2].weight

}

///从叶子节点到根节点求赫夫曼编码

char* cd

int start, c, f

HC = (HuffmanCode)malloc((n+1)*sizeof(char*))//分配字符指针数组，同样多分配一个

cd = (char*)malloc(n*sizeof(char))//零时变量，用于存储当前叶子节点的赫夫曼编码

cd[n-1] = '\0'

for(int 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))

StrCopy(HC[i], cd, start)//将存储的编码copy给HC的第i个数组

}

free(cd)

}

void PrintHuffmanCode(HuffmanTree HT, HuffmanCode HC, int n) //打印各节点的赫夫曼编码

{

HuffmanCode p

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

{

p = HC

printf("The weight %d HuffmanCode is: ", HT[i])

while(*p[i]!='\0')

{

printf("%c",*p[i])

p[i]++

}

printf("\n")

}

void main()

{

int n = 8

HuffmanTree HT

HuffmanCode HC

int a[8] = {5, 29, 7, 8, 14, 23, 3, 11}//信号源的概率分布，即P={p0, p1,…, pK-1}

HuffmanCoding(HT, HC, a, n)

PrintHuffmanCode(HT, HC, n)

system("pause")}

#include <stdio.h>

#include <conio.h>

#include <string.h>

#include <malloc.h>

#define NULL 0

#define OK 1

#define ERROR 0

#define OVERFLOW -2

#define MAX_NUM 10000

#define MAX 60

typedef int Status

typedef char **HuffmanCode

typedef struct{

unsigned intweight

unsigned intparent,lchild,rchild

}HTNode,*HuffmanTree

typedef struct{

HuffmanTree HT

char *c

int longth

HuffmanCode HC

}Huffman

void Select(HuffmanTree HT,int end,int *s1,int *s2)

{

int i

int min1=MAX_NUM

int min2

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

{

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

{

*s1=i

min1=HT[i].weight

}

min2=MAX_NUM

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

{

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

{

*s2=i

min2=HT[i].weight

}

Huffman HuffmanCoding(Huffman Hfm)

{

/*---------------------------------*/

int i,n,m,s1,s2,start

int c,f

char *cd

n=Hfm.longth

if(n<=1) return Hfm

m=2*n-1

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

{

Select(Hfm.HT,i-1,&s1,&s2)

Hfm.HT[s1].parent=i

Hfm.HT[s2].parent=i

Hfm.HT[i].lchild=s1

Hfm.HT[i].rchild=s2

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

}

/*------------------------------------------*/

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

{

if(c==Hfm.HT[f].lchild) cd[--start]='0'

else cd[--start]='1'

}

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

strcpy(Hfm.HC[i],&cd[start])

}

free(cd)

return Hfm

}

Huffman InputHuffman(Huffman Hfm)

{

int i,n

clrscr()

printf("\n\n\t\t********************Initial*********************\n")

printf("\tThe chars and weights will be saved in the file \"hfmTree\"\n")

printf("Please input the number of the chars: ")

scanf("%d",&n)

Hfm.HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode))

Hfm.c=(char *)malloc((n+1)*sizeof(char))

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

{

printf("Please input the char: ")

scanf("%s",&Hfm.c[i])

printf("Please input the weight of the char: ")

scanf("%d",&Hfm.HT[i].weight)

Hfm.HT[i].parent=0

Hfm.HT[i].lchild=0

Hfm.HT[i].rchild=0

}

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

{

Hfm.HT[i].weight=0

Hfm.HT[i].parent=0

Hfm.HT[i].lchild=0

Hfm.HT[i].rchild=0

}

Hfm.longth=n

return Hfm

}

Huffman InitHuffman(Huffman Hfm)

{

int n,i

FILE *fp

fp=fopen("hfmTree","rt")

if(fp==NULL)

{

Hfm=InputHuffman(Hfm)

fp=fopen("hfmTree","wt")

fprintf(fp,"%d\n",Hfm.longth)

for(i=1i<=Hfm.longthi++)

fprintf(fp,"%c %d",Hfm.c[i],Hfm.HT[i].weight)

rewind(fp)

}

else

{

fscanf(fp,"%d\n",&n)

Hfm.c=(char *)malloc((n+1)*sizeof(char))

Hfm.HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode))

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

fscanf(fp,"%s %d",&Hfm.c[i],&Hfm.HT[i].weight)

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

{

Hfm.HT[i].parent=0

Hfm.HT[i].lchild=0

Hfm.HT[i].rchild=0

}

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

{

Hfm.HT[i].weight=0

Hfm.HT[i].parent=0

Hfm.HT[i].lchild=0

Hfm.HT[i].rchild=0

}

Hfm.longth=n

}

fclose(fp)

Hfm=HuffmanCoding(Hfm)

return Hfm

}

void Output(Huffman Hfm)

{

int i,n

n=Hfm.longth

printf("\n\n******************Output the code of the chars****************\n\n")

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

{

printf("\n")

printf("Char: %c\t",Hfm.c[i])

printf("Weight: %d\t",Hfm.HT[i].weight)

printf("Code: ")

puts(Hfm.HC[i])

}

void Encoding(Huffman Hfm)

{

int i=0,j=0,n

char ch[MAX]

FILE *fp,*ffp

n=Hfm.longth

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

if((ffp=fopen("ToBeTran","rt"))==NULL)

{

printf("\nPlease input the sentence: ")

scanf("%s",&ch)

printf("\n")

fp=fopen("CodeFile","wt+")

}

else

{

fscanf(ffp,"%s",ch)

fclose(ffp)

}

while(ch[j])

{

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

if(ch[j]==Hfm.c[i])

{

printf("%s",Hfm.HC[i])

fprintf(fp,"%s",Hfm.HC[i])

break

}

j++

}

rewind(fp)

fclose(fp)

}

void Decoding(Huffman Hfm)

{

HuffmanTree p

int i,n

int j=0

char d[50]

FILE *fp

n=Hfm.longth

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

if((fp=fopen("CodeFile","rt"))==NULL)

{

printf("Please input the code:")

scanf("%s",&d)

}

else

{

fscanf(fp,"%s",d)

fclose(fp)

}

printf("\nThe file is : ")

fp=fopen("TextFile","wt+")

while(d[j])

{

p=&Hfm.HT[2*n-1]

while(p->lchild||p->rchild)

{

if(d[j]=='0')

{ i=p->lchild p=&Hfm.HT[i]}

else

{ i=p->rchild p=&Hfm.HT[i]}

j++

}

printf("%c",Hfm.c[i])

fprintf(fp,"%c",Hfm.c[i])

}

fclose(fp)

}

Huffman RebuildHuffman(Huffman Hfm)

{

int n,i

FILE *fp

fp=fopen("hfmTree","wt")

Hfm=InputHuffman(Hfm)

fprintf(fp,"%d\n",Hfm.longth)

for(i=1i<=Hfm.longthi++)

fprintf(fp,"%c %d",Hfm.c[i],Hfm.HT[i].weight)

rewind(fp)

fclose(fp)

Hfm=HuffmanCoding(Hfm)

return Hfm

}

int main()

{

Huffman Hfm

char choice='a'

Hfm=InitHuffman(Hfm)

while(choice!='q')

{

clrscr()

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

printf("\t\t\ta. Encoding:\n\n")

printf("\t\t\tb. Decoding:\n\n")

printf("\t\t\tc. Print all codes:\n\n")

printf("\t\t\td. Rebuild the huffmantree:\n\n")

printf("\t\t\tq. Quit...\n\n")

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

printf("Please enter your choice: ")

scanf("%s",&choice)

switch(choice)

{

case 'a':

clrscr()

Encoding(Hfm)

printf("\n\n*******Please enter anykey to continue*******\n")

getch()break

case 'b':

clrscr()

Decoding(Hfm)

printf("\n\n*******Please enter anykey to continue********\n")

getch()break

case 'c':

clrscr()

Output(Hfm)

printf("\n\n*******Please enter anykey to continue********\n")

getch()break

case 'd':

clrscr()

Hfm=RebuildHuffman(Hfm)

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

getch()break

case 'q':

break

default:

printf(" Your choice is wrong!\n Please enter anykey to choice again!\n")

getch()break

}

return 0

}

引用:

http://hi.baidu.com/dench/blog/item/16af5e22a1d9eda64723e834.html

节点数组叶子字符队列

# 上一篇：java常用api面试题有哪些？

# 下一篇：电脑缺少上网的驱动怎么解决电脑缺少上网的驱动怎么办

推荐阅读

热门文章

最新发布

标签列表

霍夫曼编码 用c语言实现

给您推荐相同类型的内容：

霍夫曼编码用c语言实现