c语言实现的哈夫曼树编译码系统

❶ 怎么样用c语言程序编码哈夫曼树

#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=0; s[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=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;
}

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=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].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=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]='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=0; i<count; i++)
{
if(!isspace(*(s1+i)))
{
if(function1(*(s1+i),s2))
{
*(s2+j)=*(s1+i);
j++;
}
}
else;
}
m=(int*)malloc(j*sizeof(int));
for(i=0; i<j; i++)
*(m+i)=0;
for(t=0; t<j; t++)
{
for(i=0; i<count; i++)
{
if(*(s2+t)==*(s1+i))
*(m+t)+=1;
}
}
for(i=0;i<j;i++)
while(flag)
{
flag = 0;
for (t=0; t<j-1; t++)
{
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=0; i<=j; i++,t++)
{
printf("%c %d %s\n",*(s2+t),*(m+t),HC[i]);

}
return 0;
}

❷ 怎样用c语言实现霍夫曼编解码

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <conio.h>

typedef struct {
unsigned int weight;
unsigned int parent,lchild,rchild;
} HTNode,*HuffmanTree;/*动态分配数组存储哈夫曼树*/
typedef char **HuffmanCode;/*动态分配数组存储哈夫曼编码表*/

typedef struct {
unsigned int s1;
unsigned int s2;
} MinCode;
MinCode Select(HuffmanTree HT,int n);

HuffmanCode HuffmanCoding(HuffmanTree HT,HuffmanCode HC,int *w,int n)
{ /* w存放n个字符的权值(均>0),构造哈夫曼树HT,并求出n个字符的哈夫曼编码HC.*/
int i,s1=0,s2=0;
HuffmanTree p;
char *cd;
int f,c,start,m;
MinCode min;
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /*0号单元未用*/
for(p=HT,i=0;i<=n;i++,p++,w++)
{
p->weight=*w;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
for(;i<=m;i++,p++)
{
p->weight=0;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
for(i=n+1;i<=m;i++){ /*建哈夫曼树*/
/*在HT[1..i-1]选择parent为0且weight最小的两个结点，其序号分别为s1和s2.*/
min=Select(HT,i-1);
s1=min.s1;
s2=min.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 *)); /*分配n个字符编码的头指针向量*/
cd=(char *)malloc(n*sizeof(char *)); /*分配求编码的工作空间*/
cd[n-1]='\0'; /*编码结束符*/
for(i=0;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); /*释放工作空间*/
return HC;
}

MinCode Select(HuffmanTree HT,int n)
{
int min,secmin;
int temp;
int i,s1,s2,tempi;
MinCode code;
s1=1;s2=1;
for(i=0;i<=n;i++)
if(HT[i].parent==0)
{
min=HT[i].weight;
s1=i;
break;
}
tempi=i++;
for(;i<=n;i++)
if(HT[i].weight<min&&HT[i].parent==0)
{
min=HT[i].weight;
s1=i;
}
for(i=tempi;i<=n;i++)
if(HT[i].parent==0&&i!=s1)
{
secmin=HT[i].weight;
s2=i;
break;
}
for(i=0;i<=n;i++)
if(HT[i].weight<secmin&&i!=s1&&HT[i].parent==0)
{
secmin=HT[i].weight;
s2=i;
}
if(s1>s2)
{
temp=s1;
s1=s2;
s2=temp;
}
code.s1=s1;
code.s2=s2;
return code;
}

void main()
{
HuffmanTree HT=NULL;
HuffmanCode HC=NULL;
int i,n=27;
char c[27]={' ','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
int w[27]={186,64,13,22,32,103,21,15,47,57,1,5,32,20,57,63,15,1,48,51,80,23,8,18,1,16,1};
HC=HuffmanCoding(HT,HC,w,n);
printf("HuffmanCode:\n");
printf("Char\t\tWeight\t\tCode\n");
for(i=0;i<=n-1;i++)
printf("%c\t\t%d\t\t%s\n",c[i],w[i],HC[i]);
{
char cs[128];
char results[64];
char buf[64];
int ps=0,pe=1;
results[0]=0;
printf("Input code:\n");
scanf("%s",cs);
while (cs[ps]!=0) {
strncpy(buf,&cs[ps],pe-ps); /*返回字符*/
buf[pe-ps]=0;
for(i=0;i<n;i++)
{
if (strcmp(buf,HC[i])==0)
{
int len=strlen(results);
results[len]=c[i];
results[len+1]=0;
ps=pe;
pe++;
break;
}
}
if (cs[pe]==0) break;
pe++;
}
printf("RESULT: %s",results);
}
getch();
}

❸ 哈夫曼编码C语言实现

我写了一个注释较为完整且压缩、解压缩比较全面的：

#include <stdio.h>
#include <conio.h>

#define MAX_FILE 5000/* 假设的文件最大长度 */
#define MAXLIST 256/* 最大MAP值 */
#define MAX_HOFFMAN_LENGTH 50/* 哈夫曼编码长度 */
char dictionary[MAXLIST][2]={0};/* Hash映射,[][0]为权值,[][1]为字符 */
char fileContent[MAX_FILE];/* 处理的字符串大小 */
int Hoffman[MAXLIST][MAX_HOFFMAN_LENGTH]={2};/* 哈夫曼编码序列 */
char HoffmanList[MAXLIST]={0};/* 哈夫曼编码对应的字符有序序列 */
char HoffFileCode[MAX_FILE]={0};/* 哈夫曼编码字符串序列 */
char HoffFile[MAX_FILE]={0};
/* 编码到假设的文件的哈夫曼压缩格式： 依次存储 原字符串长度(1字节存储:可扩展到2字节)、哈夫曼编码数(1字节)、每个哈夫曼编码的长度序列、每个哈夫曼编码对应的字符序列、编码过的哈夫曼字符串 */

char GetFile[MAX_FILE]={0};/* 解码序列 */

void ShellSort(char pData[MAXLIST][2],int Count)/* Shell排序，用于准备有序化要构造的编码权值构造哈夫曼树做准备 */
{
int step[4]={9,5,3,1};/* 增量序列 */

int iTemp,cTemp;
int k,s,w,i,j;
for(i=0;i<4;i++)
{
k=step[i];
s=-k;
for(j=k;j<Count;j++)
{iTemp=pData[j][0];
cTemp=pData[j][1];
w=j-k;
if(s==0)
{
s=-k;
s++;
pData[s][0]=iTemp;
pData[s][1]=cTemp;
}
while((iTemp<pData[w][0])&&(w>=0)&&(w<=Count))
{
pData[w+k][0]=pData[w][0];/* 权值交换 */
pData[w+k][1]=pData[w][1];/* 字符交换 */
w=w-k;
}
pData[w+k][0]=iTemp;
pData[w+k][1]=cTemp;
}
}
}

struct TNode/* 哈夫曼树结点 */
{
struct TNode* pNode;
struct TNode* lNode;
struct TNode* rNode;
char dictionary;
char weight;

};

void TNode_init(struct TNode*tn,char dic,char wei)
{
tn->pNode=0;
tn->lNode=0;
tn->rNode=0;
tn->dictionary=dic;
tn->weight=wei;
}
struct LNode/* 链表结点,用于存储哈夫曼树结点,进而构造哈夫曼树(保证每一步链表结点包含的哈夫曼结点都是有序的) */
{
struct LNode* prev;
struct LNode* next;
struct TNode* tnode;

};

void LNode_init(struct LNode* ln)
{
ln->prev=ln->next=0;
ln->tnode=0;
}

int len=0;/* 哈夫曼编码数 */
int deep=-1;/* 深度 */
void Preorder(struct TNode * p);/* 前序遍历 */
void byLeft(struct TNode*p)/* 经由左结点 */
{
deep++;
Hoffman[len][deep]=0;
Preorder(p);

Hoffman[len][deep]=2;
deep--;
}
void byRight(struct TNode*p)/* 经由右结点 */
{

deep++;
Hoffman[len][deep]=1;
Preorder(p);

Hoffman[len][deep]=2;
deep--;
}
void Preorder(struct TNode * p)
{

int i;
if(p->lNode!=0)/* 当左子结点非空则遍历 */
{

byLeft(p->lNode);
}
if(p->rNode!=0)/* 当右子结点非空则遍历 */
{
byRight(p->rNode);
}

if((p->lNode==0)&&(p->rNode==0))/* 当左右结点都为空，则增加哈夫曼编码数到另一个记录 */
{

Hoffman[len][deep+1]=2;
i=0;
for(;Hoffman[len][i]!=2;i++)
{
Hoffman[len+1][i]=Hoffman[len][i];
}
Hoffman[len+1][i]=2;

HoffmanList[len]=p->dictionary;

len++;
}

}

char generateOne(int k)/* 产生k个连续1的二进制串,比如111,1111,111111,用于编码进假设的文件 */
{
char c=0;
for(;k!=0;k--)
{
c|=(1<<(k-1));

}
return c;
}

int compareBits(char b1,char b2,char c,int l,int d)/* 判断由 [b1,b2] 组成的16位二进制数以d为起点,是否是长度为l的c二进制串（哈夫曼编码）的前缀 */
{
unsigned char t=(((((0x00ff&b1)<<8)|(0x00ff&b2))>>(8-d))&0x00ff);
return (((t)&((generateOne(l)<<(8-l))&0xff))==((c<<(8-l))&0xff));
}

int main()
{
struct LNode* t,*p;
struct LNode* head;
struct TNode *tempTNode,*k1;
int i=0,j,k;
unsigned short fileLen=0;
int len=0,l,b1,b2,d;
char c;
int code[500],h=0;
int codeLen=0,total=0;
/* 或许假定的文件字符串向量中的字符串 */

printf("please Enter string to be pressed:");
scanf("%s",&fileContent);

/* Hash进dictionary */

for(;fileContent[i]!='\0';i++,fileLen++)
{

++dictionary[fileContent[i]][0];
dictionary[fileContent[i]][1]=fileContent[i];
}

/* 把Hash了的dictionary向前靠拢 */

{

for(i=0;i!=MAXLIST;i++)
{

if(dictionary[i][0]!=0)
{
dictionary[len][0]=dictionary[i][0];
dictionary[len][1]=dictionary[i][1];
len++;
}
}
}
printf("the number of Huffman's codes:%d\n",len);
/* 对dictionary按权值进行排序 */

ShellSort(dictionary,len);

/* 构造链表,链表中放有序dictionary权值的树结点 */
head=(struct LNode*)malloc(sizeof(struct LNode)),p=head;
LNode_init(head);
head->next=(struct LNode*)malloc(sizeof(struct LNode));
LNode_init(head->next);

tempTNode=(struct TNode*)malloc(sizeof(struct LNode));
TNode_init(tempTNode,dictionary[0][1],dictionary[0][0]);
head->tnode=tempTNode;

{
for(i=0;i!=len-1;i++)
{
p->next->prev=p->next;
p=p->next;

p->next=(struct LNode*)malloc(sizeof(struct LNode));
LNode_init(p->next);

tempTNode=(struct TNode*)malloc(sizeof(struct TNode)) ;
TNode_init(tempTNode,dictionary[i+1][1],dictionary[i+1][0]);
p->tnode=tempTNode;
}
}
free(p->next);
p->next=0;

/* 每次最小权值的前面两个链表结点中的树结点组成一个子树,子树有合权值,子数的根按权值排序进链表*/

for(p=head;p->next!=0;)
{

p->tnode->pNode=(struct TNode*)malloc(sizeof(struct TNode)) ;
TNode_init(p->tnode->pNode,'\0',(p->tnode->weight)+(p->next->tnode->weight));

p->next->tnode->pNode=p->tnode->pNode;
p->tnode->pNode->lNode=p->tnode;
p->tnode->pNode->rNode=p->next->tnode;
head=p->next;
free(p);
p=head;
p->tnode=p->tnode->pNode;
for(t=head;t->next!=0;t=t->next)
{
if(t->tnode->weight>t->next->tnode->weight)
{
k1=t->tnode;
t->tnode=t->next->tnode;
t->next->tnode=k1;
}
}

}

/* 前序遍历构造哈夫曼编码 */
Preorder(p->tnode);

{
for(i=0;i!=len;i++)
dictionary[HoffmanList[i]][0]=i;
}
/* 存储字符串的哈夫曼压缩编码串,并且打包文件格式 */

{
for(i=0;i!=fileLen;i++)
{
int j=dictionary[fileContent[i]][0];
for(k=0;Hoffman[j][k]!=2;k++)
{

HoffFileCode[codeLen]|=(Hoffman[j][k]<<(7-total%8));
code[h++]=Hoffman[j][k];

if(((total+1)%8)==0)
{
HoffFile[1+len*3+1+codeLen]=HoffFileCode[codeLen];
codeLen++;
}
total++;
}

}
}
HoffFile[1+len*3+1+codeLen]=HoffFileCode[codeLen];
HoffFile[0]=(fileLen);

/* 解压缩假定的文件HoffFile成为原字符串序列 */
printf("Huffman's code list:\n");
HoffFile[1]=len;

{
for(i=0,j=0;i!=len;i++,j=0)
{

for(;Hoffman[i][j]!=2;j++);

HoffFile[i+2]=j;
HoffFile[i+2+2*len]=HoffmanList[i];

for( k=0;k!=j;k++)
{

printf("%d",Hoffman[i][k]);
HoffFile[i+2+len]|=(Hoffman[i][k]<<(j-1-k));

}
printf(":%d\n",HoffmanList[i]);

}
}

{
for(i=0,j=0;i!=(HoffFile[0]&0xff);i++)
{
for(k=0;k!=HoffFile[1];k++)
{

l=HoffFile[2+k],d=j%8,b1=HoffFile[j/8+2+HoffFile[1]*3],b2=HoffFile[j/8+1+2+HoffFile[1]*3];

c=HoffFile[HoffFile[1]+2+k];

if(compareBits(b1,b2,c,l,d))
{

j+=HoffFile[2+k];

GetFile[i]=HoffFile[2+HoffFile[1]*2+k];

break;

}
}

}
}
{
printf("Huffman code List Pressed :\n");
for(i=0;i!=h;i++)
{
printf("%c",code[i]);
if((i+1)%8==0)
printf(" ");
}
}
printf("\n");

{
printf("Huffman code packaged:\n");
for(i=0;i!=HoffFile[0]+HoffFile[1]*3;i++)
{
printf("%c",HoffFile[i]);
}
printf("\n");
}

printf("The initial len :%d\n",fileLen);
printf("The string len pressed:%d\n",(h)/8+1);
printf("The rate%.2f\%",((h/8.0+1)/fileLen)*100);

{

printf("The number of bytes:%d\n",(HoffFile[0]&0xff));
printf("The string decoded:");
for(i=0;i!=(HoffFile[0]&0xff);i++)
{
printf("%c",GetFile[i]);
}

printf("\n");

}
getch();
return 1;
}

❹ c语言版 哈弗曼编码和译码

哈弗曼编码涵义是将一窜数字或者字母按哈弗曼数的形式编码，并使得这窜字符中的每个数字或者字母都能被唯一的“0，1”序列来编码，而且没有相同的前缀，这是一种非等长的编码方式。如果你觉得这样解释很难听懂的话就举个例子：如果用计算机发信息，只能用0和1，但是每个字母的使用频度又不一样，比如a ,i,o,e等这些字母使用的就多些，而z,v这样的字母使用的就少一些，如果所有字母都用等长的0,1序列来编码的话会造成浪费，那么我们就把常用的字母用少点的0,1，进行编码（比如用两个或三个），不常用的再用多点0,1编码，但是还不能造成油相同前缀的情况，这会使计算机无法识别，比如E用010，z用01001，计算机就只能识别出前面三个是E，而后面就抛弃或者识别出别的字母。哈弗曼编码就是出于这样的条件下产生的。也许这样的形容还是很抽象，那么再具体点。加入a,b,c,d,e使用的频度分别是10,7,5,5,3那么就可以构造哈弗曼数：从树顶到树根，假如左边是0，右边是1，那么就能得到他们的哈弗曼编码(就是从上到下，到达他们字母经过的路径)，分别是：a:00;b:11;c:10;d:011;e:010;你可以发现他们全部没有相同的前缀。具体的编码方式我可以大致的跟你说下，因为我还在上班所以无法使用自己的电脑进行编译，怕写的有错误，你拿到一个待编码的数据肯定有标识符（即上面的a,b,c），还有所带的权值（即3,5,5等）你需要用哈弗曼算法构造出哈弗曼编码，即每次取最小的两个数当作叶子，来生成树根（树根的值等于他们的和），整数据就少了一个，直到最后两个数相加的值作为最终的树根。然后从上往下，左边为0右边为1，到达每个树叶（即是标识符的位置），那么路径的编码就是他的哈弗曼编码。以上是算法，建议你可以用一个结构体（带标识符，权值，哈弗曼编码（编码暂时为空）），用一个vector（C++里面的数据类型）装载他们并按照权值大小进行排序，然后通过哈弗曼算法（另用一个函数来计算）创建一个哈弗曼数，并计算出它的哈弗曼编码并写到结构体中，这样就把字符进行了哈弗曼压缩。这就是整个过程

❺ 哈夫曼编/译器(c语言)

用C语言实现的哈夫曼编码的完整代码

#define N 7 /*叶子数目,需要时更改此值即可*/
#define M 2*N-1 /*节点总数*/

typedef struct
{
char bits[N];/*编码存储，位串*/
int start; /*编码在位串中的位置*/
}codetype;

typedef struct
{
float weight;
int lchild,rchild,parent;
}hufmtree;

void HUFFMAN(tree1)
hufmtree tree1[];
{
int i,j,p1,p2;
float small1,small2,f;
hufmtree *tree;
tree=tree1;
for(i=0;i<M;i++) /*初始化*/
{
tree[i].parent=0;
tree[i].lchild=0;
tree[i].rchild=0;
tree[i].weight=0.0;
}
printf("please input a possible data weight:\n"); /*输入信源数据*/
for(i=0;i<N;i++) /*输入前n个节点的权值*/
{
scanf("%f",&f);
tree[i].weight=f;
}
for(i=N;i<M;i++) /* 进行n-1次合并，产生n-1个新的节点*/
{
p1=0,p2=0;
small1=1;small2=1;
for(j=0;j<=i-1;j++) /*从所有的节点中，选出两个权值最小的根节点*/
if(tree[j].parent==0) /*parent值为0，则显示根节点，否则便是非根节点*/
if(tree[j].weight<small1)
{
small2=small1; /*改变最小权，次小权及对应的位置*/
small1=tree[j].weight;
p2=p1; /*p1、p2记住这两个根节点在向量tree中的下标*/
p1=j;
}
else if(tree[j].weight<small2)
{
small2=tree[j].weight;/*次小权及位置*/
p2=j;
}
tree[p1].parent=i+1; /*节点分量与下标之间差值为1*/
tree[p2].parent=i+1; /*节点的标号i+1*/
tree[i].lchild=p1+1; /*最小值根节点是新节点的左孩子，分量标号是其下标加1*/
tree[i].rchild=p2+1; /*次小权根节点是新节点的右孩子*/
tree[i].weight=tree[p1].weight+tree[p2].weight;
}
}/*HUFFMANTREE()*/

void HUFFMANCODE(code1,tree1) /*根据哈夫曼树求出哈夫曼编码*/
codetype code1[]; /*求出的哈夫曼编码所在*/
hufmtree tree1[];/*已知的哈夫曼树*/
{
int i,j,c,p;
codetype cd;/*缓冲变量*/
codetype *code;
hufmtree *tree;
code=code1;
tree=tree1;
for(i=0;i<N;i++)
{
cd.start=N;
c=i+1; /*从叶节点出发向上回溯*/
p=tree[i].parent;/*tree[p-1]是tree[i]的双亲*/
while(p!=0)
{
cd.start--;
if(tree[p-1].lchild==c)
cd.bits[cd.start]='0'; /*tree[i]是左子树。生成代码'0'*/
else
cd.bits[cd.start]='1'; /*否则tree[i]是右子树。生成代码'1'*/
c=p;
p=tree[p-1].parent;
}
code[i]=cd; /*第i+1个字符的编码存入code[i]*/
}
} /*HUFFMANCODE*/

#include "stdio.h"
main()
{
int k1,k2;
hufmtree tree_fina[M];
hufmtree *p11=tree_fina;
codetype code_fina[N];
codetype *p21=code_fina;
HUFFMAN(p11); /*建立huffman树*/
HUFFMANCODE(p21,p11); /*haffman码*/
for(k1=0;k1<N;k1++) /*输出编码*/
{
printf("number %d haffmancode: ",k1+1);
for(k2=code_fina[k1].start;k2<N;k2++)
printf(" %c",code_fina[k1].bits[k2]);
printf("\n");
}
}

说明：本程序运用C语言中结构化程序的思想，将程序分为函数模块的方法逐一实现。程序分为2个函数模块HUFFMAN(tree1)、HUFFMANCODE(code1,tree1)，和主体函数main；程序结构清楚，运行正常，正常实现哈夫曼编码。拱你参考吧

❻ 哈夫曼树及哈夫曼编码的C程序实现(数据结构题)

去年做的课程设计，有什么不合要求的自己改改

#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();
}

❼ 用C++实现哈夫曼编码译码

#include<iostream>
#include<fstream>
#include<string>

using namespace std;

typedef struct HuffmanNode{//结点结构
int weight;
int parent,lchild,rchild;
}*HfmNode;

struct HuffmanTree{//哈弗曼树
HfmNode Node;
char *Info;//存储字符，也可放在结点结构里定义
int LeafNum;//叶结点数量
};

HuffmanTree T;//连接各模块变量
/****************初始化(建立哈夫曼树)函数********************/

void Initialization() //初始化
{
int WeightNum;
int i,j,pos1,pos2,max1,max2; //
int choice;
cout<<endl;
cout<<"***************** 建树方案目录*********************"<<endl;
cout<<"| |"<<endl;
cout<<"| 方案1:输入N个字符和N个权值进行建树 |"<<endl;
cout<<"| 方案2:以文档中字符和并以各字符出现的 |"<<endl;
cout<<"| 频度作为权值进行建树 |"<<endl;
cout<<"***************************************************"<<endl;
lp: cout<<"选择(输入对应方案序号):";cin>>choice;
/********************建树方案1 ************************************/
if(choice==1){

cout<<"输入字符个数:";
cin>>WeightNum;

T.Node=new HuffmanNode[2*WeightNum-1]; //WeightNum权值对应的哈夫曼树中的结点总数为2*WeightNum-1个
T.Info=new char[2*WeightNum-1];//实际只需要申请WeightNum-1；但为了实现要求（5）所以所有结点都由字符域
for(i=0;i<WeightNum;i++)
{
cout<<"请输入第"<<i+1<<"个字符值";

cin.get ();
T.Info[i]=cin.get ();
cout<<"请输入该字符的权值或频度";
cin>>T.Node[i].weight; //输入权值
T.Node[i].parent=-1; //为根结点
T.Node[i].lchild=-1; //无左孩子
T.Node[i].rchild=-1; //无右孩子
}
}
/***********************建树方案2*******************************************************/
else if(choice==2)
{
char ch, *st,*name;
st=new char[128];//128为ASCII码总数
name=new char[20];
cout<<"请输入文档名称:";cin>>name;
cout<<endl;
cout<<"提示：请确认此文件存在或检查文件名是否正确输入!"<<endl;
cout<<endl;
system("pause");
ifstream infile(name);
if(!infile)
{
cout<<"文件打开失败!"<<endl;//为什么字符个数统计与字符归类无法同时进行？？？？
exit(1);
}
i=0;
int k=0;//统计字符种类
while(infile.get (ch))
{

for(int j=0;j<=i;j++)
{
if(st[j]==ch) {break;}

else if(j==i){
st[k]=ch;
++k;
break;
}
}
i++;
}

infile.close();
int *count;
count=new int[k];
for(int m=0;m<k;m++)
count[m]=0;

ifstream infile1(name);
if(!infile1)
{
cout<<"文件打开失败!"<<endl;
exit(1);
}
while(infile1.get (ch))//统计各字符在文档中出现的次数
{

for(int j=0;j<=k;j++)
if(st[j]==ch) count[j]++;
}

infile1.close();
WeightNum=k;

T.Node=new HuffmanNode[2*WeightNum-1];
T.Info=new char[2*WeightNum-1];
for(i=0;i<WeightNum;i++)
{
T.Info[i]=st[i];
T.Node[i].weight=count[i]; //输入权值
T.Node[i].parent=-1; //为根结点
T.Node[i].lchild=-1; //无左孩子
T.Node[i].rchild=-1; //无右孩子
}
delete st;
delete name;
delete count;
}

else {
goto lp;
}
/***************************************************************************/
for(i=WeightNum;i<2*WeightNum-1;i++) //建立哈弗曼树
{
pos1=-1;
pos2=-1; //分别用来存放当前最小值和次小值的所在单元编号
max1=32767; //32767为整型数的最大值
max2=32767; //分别用来存放当前找到的最小值和次小值

for(j=0;j<i;j++) //在跟节点中选出权值最小的两个
if(T.Node[j].parent==-1) //是否为根结点
if(T.Node[j].weight<max1)
{
max2=max1;
max1=T.Node[j].weight;
pos2=pos1; //修改次小值所在单元编号
pos1=j; //修改最小值所在单元编号
}
else
if(T.Node[j].weight<max2) //比原最小值大但比原次小值要小
{
max2=T.Node[j].weight; //存放次小值
pos2=j; //修改次小值所在的单元编号
}
//for
T.Node[pos1].parent=i; //修改根节点位置
T.Node[pos2].parent=i;
T.Node[i].lchild=pos1; //修改儿子节点位置
T.Node[i].rchild=pos2;
T.Node[i].parent=-1; //表示新结点应该是根结点
T.Node[i].weight=T.Node[pos1].weight+T.Node[pos2].weight;
}
T.LeafNum=WeightNum;

ofstream outfile("hfmTree.dat");
if(!outfile)
{
cout<<"打开文件失败!"<<endl;
return;
}
outfile.write((char*)&WeightNum,sizeof(WeightNum)); //写入字符个数
for(i=0;i<WeightNum;i++) //把各字符信息写入文件

outfile.write((char*)&T.Info[i],sizeof(T.Info[i]));

for(i=0;i<2*WeightNum-1;i++) //把个节点内容写入文件

outfile.write((char*)&T.Node[i],sizeof(T.Node[i]));

outfile.close();

cout<<"已建立哈夫曼树!"<<endl;

}
/****************编码函数********************/
void Encoding(){

if(T.Node==NULL) //哈夫曼树不在内存，从文件hfmTree中读入
{
ifstream infile0; //以二进制方式打开hfmTree.dat文件
infile0.open("hfmTree.dat",ios::binary|ios::in);
if(infile0.fail())
{
cout<<"文件打开失败！\n";
return;
}
infile0.read((char*)&T.LeafNum,sizeof(T.LeafNum)); //读取叶子数

T.Info=new char[T.LeafNum];
T.Node=new HuffmanNode[2*T.LeafNum-1];

for(int i=0;i<T.LeafNum;i++) //读取字符信息
infile0.read((char*)&T.Info[i],sizeof(T.Info[i]));

for(i=0;i<2*T.LeafNum-1;i++) //读取结点信息
infile0.read((char*)&T.Node[i],sizeof(T.Node[i]));

infile0.close();
}
char *Tree; //用于存储需编码内容
int i=0,k=0;
cout<<" _________________"<<endl;
cout<<" | 测试数据选择: |"<<endl;
cout<<" | |"<<endl;
cout<<" | A:另输入内容测试|"<<endl;
cout<<" | |"<<endl;
cout<<" | B:用ToBeTran文件|"<<endl;
cout<<" | 内容测试! |"<<endl;
cout<<" |_________________|"<<endl;
cout<<"你的选择(不分大小写):";
char c;
cin>>c;// tag
if(c=='A'||c=='a')
{
string ch;
cout<<"请输入测试数据(输入完毕按两次回车):"<<endl;

cin.ignore();//跳过tag 处输入的字符<--........................*//否则运行结果很意外y因为c也被添加至string中
getline(cin,ch,'\n'); //回车键作为输入结束条件。所以输入结束时按两次回车，
//第一次作为分界符，第二次通知流对象cin已输入一行字符

while(ch[k]!='\0')//统计输入字符个数
k++;

Tree=new char[k+1];
k=0;
while(ch[k]!='\0')//将输入的内容存到Tree中
{
Tree[k]=ch[k];
k++;
}
Tree[k]='\0';

cout<<"需编码内容为:";
cout<<Tree<<endl;

}

else{
ifstream infile1("ToBeTran.txt");
if(!infile1)
{
cout<<"文件打开失败!\n";
return;
}
char ch;
int k=0;
// infile1>>noskipws;
while(infile1.get(ch))
{
k++; //计算ToBeTran中正文长度，以便确定Tree的空间大小
}
infile1.close();
Tree=new char[k+1];
ifstream infile2("ToBeTran.txt");

k=0;
// infile2>>noskipws;
while(infile2.get(ch))
{
Tree[k]=ch; //读取文件内容，并存到Tree中
k++;
}
infile2.close();

Tree[k]='\0';//结束标志

cout<<"需编码内容为:";
cout<<Tree<<endl;
}

ofstream outfile("CodeFile.txt"); //存储编码后的代码,并覆盖原文件
if(T.Node==NULL) //还未建哈夫曼树
{
cout<<"警告+提示：请先建树!\n";
return;
}
char *code;
code=new char[T.LeafNum]; //为所产生编码分配容量为T.LeafNum的存储空间
k=0;
while(Tree[k]!='\0')
{
int j,start=0;
for(i=0;i<T.LeafNum;i++)
if(T.Info[i]==Tree[k]) //求出该文字所在单元的编号
break;
j=i;
while(T.Node[j].parent!=-1) //结点j非树根
{
j=T.Node[j].parent; //非结点j的双亲结点
if(T.Node[j].lchild==i) //是左子树，则生成代码0
code[start++]='0';
else //是右子树，则生成代码1
code[start++]='1';
i=j;
}

int m=start-1;
while(m>=0) //存储哈弗曼编码
{

outfile<<code[m];
m--;
}
k++;

}

outfile.close();
cout<<"已编码！且编码形式内容已存到文件CodeFile.txt中!\n\n";
delete Tree;
delete code;
} //Encoding
/****************译码函数********************/
void Decoding()

{

int i=0,k=0;
int j=T.LeafNum*2-1-1; //从根结点开始往下搜索
char* str;
char ch;
ifstream infile1("CodeFile.txt"); //利用已建好的哈夫曼树将文件CodeFile中的代码进行译码
if(!infile1)
{
cout<<"请先编码!\n";
return;
}
cout<<"经译码,原内容为:";

while(infile1.get(ch))
{
k++; //计算CodeFile中代码长度
}
infile1.close();

str=new char[k+1];

ifstream infile2("CodeFile.txt");
k=0;

while(infile2.get(ch))
{
str[k]=ch; //读取文件内容
k++;
}
infile2.close();
str[k]='\0'; //结束标志符
if(T.Node==NULL) //还未建哈夫曼树
{
cout<<"请先编码!\n";
return;
}
ofstream outfile("TextFile.txt"); //将字符形式的编码文件写入文件Textfile中
while(str[i]!='\0')
{
if(str[i]=='0')
j=T.Node[j].lchild; //往左走
else
j=T.Node[j].rchild; //往右走
if(T.Node[j].rchild==-1) //到达叶子结点
{
cout<<T.Info[j]; //输出叶子结点对应的字符

outfile.put(T.Info[j]);
j=T.LeafNum*2-1-1; //存入文件
}
i++;
}
outfile.close();
delete str;

cout<<"\n译码成功且其内容已存到文件TextFile.txt中！\n\n";
}//Decoding
/****************印代码函数********************/

void Print1(){
char ch;
ifstream infile("Codefile.txt");//
if(!infile)
{
cout<<"未进行编码"<<endl;
return;
}
ofstream outfile("CodePrin.txt");//
if(!outfile)
{
cout<<"打开失败!"<<endl;
return;
}
int i=0;
int j=T.LeafNum*2-1-1;
while(infile.get(ch))
{
cout<<ch;
i++;
if(i==50)
{i=0;
cout<<endl;
}
if(ch=='0')
j=T.Node[j].lchild; //往左走
else
j=T.Node[j].rchild; //往右走
if(T.Node[j].rchild==-1) //到达叶子结点
{
//输出叶子结点对应的字符
outfile.put(T.Info[j]); //存入文件

j=T.LeafNum*2-1-1;
}
}
cout<<endl;
infile.close();
outfile.close();
cout<<"相应的字符形式的编码文件已写入CodePrin.txt中!"<<endl;
}//Print()
/****************印哈夫曼树函数********************/
void Tree_Printing(){
if(T.Node==NULL) //未建立哈夫曼树
{
cout<<"请先建立哈夫曼树！\n";
return;
}
cout<<"所建立的哈夫曼树的凹入表形式为："<<endl;
ofstream fop("TreePrint.txt");
cout<<"位置:权值(字符) "<<"左孩子位置(权值) "<<"右孩子位置(权值)\n";
fop<<"位置:权值(字符) "<<"左孩子位置 (权值) "<<"右孩子位置(权值)\n";
int i;
for(i=0;i<T.LeafNum;i++)
{
cout<<i<<":"<<T.Node[i].weight<<"("<<T.Info[i]<<") \n";
fop<<i<<":"<<T.Node[i].weight<<"("<<T.Info[i]<<") \n";
}
for(i=T.LeafNum;i<(2*T.LeafNum-1);i++) //输出哈夫曼树
{
cout<<i<<":"<<T.Node[i].weight<<"(#)"<<"-------"
<<T.Node[i].lchild<<"("<<T.Node[T.Node[i].lchild].weight<<")"<<"------"
<<T.Node[i].rchild<<"("<<T.Node[T.Node[i].rchild].weight<<")"<<endl;

fop<<i<<":"<<T.Node[i].weight<<"(#)"<<"------"
<<T.Node[i].lchild<<"("<<T.Node[T.Node[i].lchild].weight<<")"<<"------"
<<T.Node[i].rchild<<"("<<T.Node[T.Node[i].rchild].weight<<")"<<endl;
}

}
/*

/****************哈夫曼编码表:********************/
void Print(){
cout<<"哈夫曼编码表:"<<endl;

char *code;
code=new char[T.LeafNum];
int i=0;

while(i<T.LeafNum)
{
cout<<T.Info [i]<<":";
int j,start=0;
int k;
k=i;
j=k;
while(T.Node[j].parent!=-1) //结点j非树根
{
j=T.Node[j].parent; //非结点j的双亲结点
if(T.Node[j].lchild==k) //是左子树，则生成代码0
code[start++]='0';
else //是右子树，则生成代码1
code[start++]='1';
k=j;
}
for(int n=start-1;n>=0;n--)
cout<<code[n];

i++;
cout<<endl;
}

delete code;
}
/****************操作界面函数************************************************************/
void Screen_display(){
char ch;
do{
cout<<"*******************************************************************************"<<endl;
cout<<" 哈夫曼编码/译码系统"<<endl;
cout<<endl;
cout<<" 操作指令目录"<<endl;
cout<<endl;
cout<<" I:初始化(建立哈夫曼树) E:编码 D:译码 P:印代码 T:印哈夫曼树 Q:退出系统"<<endl;
cout<<endl;
cout<<"版本:V1.0"<<endl;
cout<<"*******************************************************************************"<<endl;
cout<<endl;

cout<<"输入相应操作的指令(不分大小写):"<<endl;
cin>>ch;
switch(ch)
{
case'I':
case'i':cout<<" 现在进行'初始化'操作:"<<endl;Initialization();break;
case'E':
case'e':cout<<" 现在进行'编码'操作: "<<endl;Encoding();break;
case'D':
case'd':cout<<" 现在进行'译码'操作: "<<endl;Decoding();break;
case'P':
case'p':cout<<" 现在进行'印代码'操作: "<<endl;Print1();break;
case't':
case'T':{Tree_Printing();cout<<endl;Print();break;}
case'Q':
case'q':cout<<"谢谢使用!"<<endl;exit(1);break;
}
}while(1);
}
/****************主函数********************/
void main(){
Screen_display();
}

❽ 用c语言完成：1.哈夫曼编码/译码器2.内部排序算法的性能分析

我把网上的程序修改了一下，并整合了，你看看
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define M 50
#define MAX 100000;

typedef struct
{
int weight;//结点权值
int parent,lchild,rchild;
}HTNODE,*HUFFMANTREE;

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

typedef struct
{
int key; /*关键字*/
}RecordNode; /*排序节点的类型*/

typedef struct
{
RecordNode *record;
int n; /*排序对象的大小*/
}SortObject; //待排序序列

HUFFMANTREE huffmantree(int n,int weight[])//构建哈夫曼树
{
int m1,m2,k;
int i,j,x1,x2;
HUFFMANTREE ht;
ht=(HUFFMANTREE)malloc((2*n)*sizeof(HTNODE));
for(i=1;i<(2*n);i++)//初始化哈夫曼树中各结点的数据，没初始值的赋值为0
{
ht[i].parent=ht[i].lchild=ht[i].rchild=0;
if(i<=n)
ht[i].weight=weight[i];
else
ht[i].weight=0;
}
for(i=1;i<n;i++)//每一重循环从森林中选择最小的两棵树组建成一颗新树
{
m1=m2=MAX;
x1=x2=0;
for(j=1;j<(n+i);j++)
{
if((ht[j].weight<m1)&&(ht[j].parent==0))
{
m2=m1;
x2=x1;
m1=ht[j].weight;
x1=j;
}
else if((ht[j].weight<m2)&&(ht[j].parent==0))
{
m2=ht[j].weight;
x2=j;
}
}
k=n+i;
ht[x1].parent=ht[x2].parent=k;
ht[k].weight=m1+m2;
ht[k].lchild=x1;
ht[k].rchild=x2;
}
return ht;
}

void huffmancoding(int n,HUFFMANCODE hc,HUFFMANTREE ht,char str[])
{
int i,start,child,father;
char *cd;
hc=(HUFFMANCODE)malloc((n+1)*sizeof(char*));//分配n个字符编码的头指针
cd=(char*)malloc(n*sizeof(char));//分配求编码的工作空间
cd[n-1]='\0';//编码结束符
for(i=1;i<=n;++i)//逐个字符求哈夫曼编码
{
start=n-1;
for(child=i,father=ht[i].parent;father!=0;child=father,father=ht[father].parent)/*从叶子结点到根结点求逆向编码*/
if(ht[father].lchild==child)
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=1;i<=n;++i)
{
printf("\n%c的编码:",str[i]);
printf("%s\n",hc[i]);
}
}

void huffman()
{
int i,j,k,m,n;
char str[50];
int weight[50];
HUFFMANCODE hc=NULL;
HUFFMANTREE ht;
fflush(stdin);

printf("\n请输入字符(一次性连续输入所求的字符):");/*如:abcjhjg不要输成ab cj hig,即字符间不加空格*/
gets(str);
for(j=0;j<50;j++)
{
if(str[j]=='\0')
break;
}
n=j;
for(j=n;j>0;j--)
str[j]=str[j-1];
str[n+1]='\0';
for(k=0;k<n;k++)
{
printf("\n请输入%c的权值:",str[k+1]);
scanf("%d",&weight[k]);
}
for(k=n;k>0;k--)
weight[k]=weight[k-1];
weight[0]=0;

ht=huffmantree(n,weight);
huffmancoding(n,hc,ht,str);

}

void InsertSort(SortObject *p,unsigned long *compare,unsigned long *exchange)
{
int i,j,k;
RecordNode temp;
SortObject *pvector;
fflush(stdin);
if((pvector=(SortObject *)malloc(sizeof(SortObject)))==NULL)
{
printf("OverFollow!");
getchar();
exit(1);
}
k=pvector->n;
pvector->record=(RecordNode *)malloc(sizeof(RecordNode)*k);
for(i=0;i<p->n;i++)/* 复制数组*/
pvector->record[i]=p->record[i];
pvector->n=p->n;
*compare=0;
*exchange=0;
for(i=1;i<pvector->n;i++)
{
temp=pvector->record[i];
(*exchange)++;
j=i-1;
while((temp.key<pvector->record[j].key)&&(j>=0))
{
(*compare)++;
(*exchange)++;
pvector->record[j+1]=pvector->record[j];
j--;
}
if(j!=(i-1))
{
pvector->record[j+1]=temp;
(*exchange)++;
}
}
free(pvector);
}

void SelectSort(SortObject *p,unsigned long *compare,unsigned long *exchange)
{
int i,j,k;
RecordNode temp;
SortObject *pvector;
if((pvector=(SortObject *)malloc(sizeof(SortObject)))==NULL)
{
printf("OverFollow!");
getchar();
exit(1);
}
k=pvector->n;
pvector->record=(RecordNode *)malloc(sizeof(RecordNode)*k);
for(i=0;i<p->n;i++)/*复制数组*/
pvector->record[i]=p->record[i];
pvector->n=p->n;
*compare=0;
*exchange=0;
for(i=0;i<pvector->n-1;i++)
{
k=i;
for(j=i+1;j<pvector->n;j++)
{
(*compare)++;
if(pvector->record[j].key<pvector->record[k].key)
k=j;
}
if(k!=i)
{
temp=pvector->record[i];
pvector->record[i]=pvector->record[k];
pvector->record[k]=temp;
( *exchange)+=3;
}
}
free(pvector);
}

void BubbleSort(SortObject *p,unsigned long *compare,unsigned long *exchange)
{
int i,j,noswap,k;
RecordNode temp;
SortObject *pvector;
if((pvector=(SortObject *)malloc(sizeof(SortObject)))==NULL)
{
printf("OverFollow!");
getchar();
exit(1);
}
k=pvector->n;
pvector->record=(RecordNode *)malloc(sizeof(RecordNode)*k);
for(i=0;i<p->n;i++)/* 复制数组*/
pvector->record[i]=p->record[i];
pvector->n=p->n;
*compare=0;
*exchange=0;
for(i=0;i<pvector->n-1;i++)
{
noswap=1;
for(j=0;j<pvector->n-i-1;j++)
{
(*compare)++;
if(pvector->record[j+1].key<pvector->record[j].key)
{
temp=pvector->record[j];
pvector->record[j]=pvector->record[j+1];
pvector->record[j+1]=temp;
(*exchange)+=3;
noswap=0;
}
}
if(noswap) break;
}
free(pvector);
}

void ShellSort(SortObject *p,int d,unsigned long *compare,unsigned long *exchange)
{
int i,j,increment,k;
RecordNode temp;
SortObject *pvector;
if((pvector=(SortObject*)malloc(sizeof(SortObject)))==NULL)
{
printf("OverFollow!");
getchar();
exit(1);
}
k=pvector->n;
pvector->record=(RecordNode *)malloc(sizeof(RecordNode)*k);
for(i=0;i<p->n;i++)/* 复制数组*/
pvector->record[i]=p->record[i];
pvector->n=p->n;
*compare=0;
*exchange=0;
for(increment=d;increment>0;increment/=2)
{
for(i=increment;i<pvector->n;i++)
{
temp=pvector->record[i];
(*exchange)++;
j=i-increment;
while(j>=0&&temp.key<pvector->record[j].key)
{
(*compare)++;
pvector->record[j+increment]=pvector->record[j];
(*exchange)++;
j-=increment;
}
pvector->record[j+increment]=temp;
(*exchange)++;
}
}
free(pvector);
}

void QuickSort(SortObject *pvector,int left,int right,unsigned long *compare,unsigned long *exchange)
{
int i,j;
RecordNode temp;
if(left>=right)
return;
i=left;
j=right;
temp=pvector->record[i];
(*exchange)++;
while(i!=j)
{
while((pvector->record[j].key>=temp.key)&&(j>i))
{
(*compare)++;
j--;
}
if(i<j)
{
pvector->record[i++]=pvector->record[j];
(*exchange)++;
}
while((pvector->record[i].key<=temp.key)&&(j>i))
{
(*compare)++;
i++;
}
if(i<j)
{
pvector->record[j--]=pvector->record[i];
(*exchange)++;
}
}
pvector->record[i]=temp;
(*exchange)++;
QuickSort(pvector,left,i-1,compare,exchange);
QuickSort(pvector,i+1,right,compare,exchange);
}

void SortMethod(void)
{
int i,j,k,l;
unsigned long num[5][10]={0};
unsigned long sum[10]={0};
SortObject *pvector;
fflush(stdin);
printf("请输入待排序的随机数个数：\n");
scanf("%d",&k);
pvector=(SortObject *)malloc(sizeof(SortObject));
for(j=0;j<5;j++)
{
pvector->record=(RecordNode *)malloc(sizeof(RecordNode)*k);
for(i=0;i<k;i++)
pvector->record[i].key=rand();
pvector->n=k;
InsertSort(pvector,&num[j][0],&num[j][1]);
SelectSort(pvector,&num[j][2],&num[j][3]);
BubbleSort(pvector,&num[j][4],&num[j][5]);
ShellSort(pvector,4,&num[j][6],&num[j][7]);
QuickSort(pvector,0,k-1,&num[j][8],&num[j][9]);
}
printf("\n排序比较如下");
for(j=0;j<5;j++)
{
printf("\n\n对%d个数进行排序，结果为：\n",k);
printf("1.插入排序：比较-->%-7ld次 移动-->%-7ld次\n",num[j][0],num[j][1]);
printf("2.选择排序：比较-->%-7ld次 移动-->%-7ld次\n",num[j][2],num[j][3]);
printf("3.冒泡排序：比较-->%-7ld次 移动-->%-7ld次\n",num[j][4],num[j][5]);
printf("4.希尔排序：比较-->%-7ld次 移动-->%-7ld次\n",num[j][6],num[j][7]);
printf("5.快速排序：比较-->%-7ld次 移动-->%-7ld次\n",num[j][8],num[j][9]);
if(j!=5)
printf("按回车继续\n");
getchar();
}
for(j=0;j<5;j++)
{
sum[0]=sum[0]+num[j][0];
sum[1]=sum[1]+num[j][1];
sum[2]=sum[2]+num[j][2];
sum[3]=sum[3]+num[j][3];
sum[4]=sum[4]+num[j][4];
sum[5]=sum[5]+num[j][5];
sum[6]=sum[6]+num[j][6];
sum[7]=sum[7]+num[j][7];
sum[8]=sum[8]+num[j][8];
sum[9]=sum[9]+num[j][9];
}
printf("\n\n对%d个随机数进行5次排序，平均比较次数和平均移动次数为：\n",k);
printf("1.插入排序：平均比较-->%-7ld次 平均移动-->%-7ld次\n",sum[0]/5,sum[1]/5);
printf("2.选择排序：平均比较-->%-7ld次 平均移动-->%-7ld次\n",sum[2]/5,sum[3]/5);
printf("3.冒泡排序：平均比较-->%-7ld次 平均移动-->%-7ld次\n",sum[4]/5,sum[5]/5);
printf("4.希尔排序：平均比较-->%-7ld次 平均移动-->%-7ld次\n",sum[6]/5,sum[7]/5);
printf("5.快速排序：平均比较-->%-7ld次 平均移动-->%-7ld次\n",sum[8]/5,sum[9]/5);
free(pvector);
}

void sort()
{
int i;
while(1)
{
SortMethod();
printf("\n是否继续？\n1.继续\n2.返回菜单\n");
scanf("%d",&i);
if(i==2)break;
fflush(stdin);
getchar();
}
}

void huff()
{
int i;
while(1)
{
huffman();
printf("\n是否继续？\n1.继续\n2.返回菜单\n");
scanf("%d",&i);
if(i==2)break;
fflush(stdin);
getchar();
}
}

main()
{
int i,j,k;
while(1)
{
printf("请选择要运行的功能：\n");
printf("1.哈夫曼编码译码器\n");
printf("2.内部排序性能分析\n");
printf("3.退出该程序\n\n");
printf("你的选择为：");
scanf("%d",&i);
switch(i)
{
case 1:huff();break;
case 2:sort();break;
case 3:exit(0);
default:break;
}
fflush(stdin);
getchar();
system("cls");
}
}

❾ 求：c语言编写的哈夫曼编码系统

#include <stdio.h>
#include <stdlib.h>
#define MaxSize 50
typedef struct{
char c;
int w;
char code[MaxSize];
}HuffCode[MaxSize];
typedef struct{
int Weight;
int LChild,RChild,Parent;
}HTNode,HuffTree[MaxSize];

void HuffmanTree(HuffTree HT,int length,HuffCode hc);
void SelectHTNode(HuffTree HT,int n,int *min1,int *min2);
void HuffmanCode(HuffTree HT,int len,HuffCode hc);
int main(void)
{
HuffTree HT;
HuffCode HC;
int i,len;
printf("\n输入字符串字符数量："); scanf("%d",&len); system("cls");printf("代码数量：%2d\n\n",len);
printf("输入代码及权值(e.g.: \"a 16[回车]\" )：\n");
for(i=1;i <= len;i++)
{
while(getchar() != '\n') NULL;
printf("No.%2d： ",i);
HC[i].c = getchar();
scanf("%d",&HC[i].w);
}
HuffmanTree(HT,len,HC);
HuffmanCode(HT,len,HC);

printf("\n输出Huffman编码：\n");
for(i = 1;i<=len;i++)
{
printf("\n %c :",HC[i].c);
puts(HC[i].code);
}
return 0;
}

void HuffmanTree(HuffTree HT,int length,HuffCode hc)
{
int i,min1,min2;
HT[0].Weight = 65535;
for(i = 1;i <= length;i++)
{
HT[i].Weight = hc[i].w;
HT[i].LChild = HT[i].RChild = HT[i].Parent = -1;
}
for(;i < 2*length;i++)
{
HT[i].LChild = HT[i].RChild = HT[i].Parent = -1;
}

for(i = length+1;i < 2*length;i++)
{
SelectHTNode(HT,i,&min1,&min2);
HT[min1].Parent = i;
HT[min2].Parent = i;
HT[i].LChild = min1;
HT[i].RChild = min2;
HT[i].Weight = HT[min1].Weight + HT[min2].Weight;
}
}
void SelectHTNode(HuffTree HT,int n,int *min1,int *min2)
{
int i;
*min1 = *min2 = 0;
for(i = 1;i < n;i++)
{
if(HT[i].Parent == -1)
{
if(HT[*min1].Weight >= HT[i].Weight)
{
*min2 = *min1;
*min1 = i;
}
else if(HT[*min2].Weight > HT[i].Weight) *min2 = i;
}
}
}

void HuffmanCode(HuffTree HT,int len,HuffCode hc)
{
int i,j,tc,Stack[MaxSize],top = -1;
char flag[MaxSize];
HTNode th;
for(i = 1;i <= len;i++)
{
top = -1;
j = 0;
th = HT[i];
tc = i;
while(th.Parent != -1)
{
Stack[++top] = th.Parent;
if(HT[th.Parent].LChild == tc) {flag[top] = 'L'; tc = th.Parent;}
if(HT[th.Parent].RChild == tc) {flag[top] = 'R'; tc = th.Parent;}
th = HT[Stack[top]];
}
while(top != -1)
{
if(flag[top] == 'L') hc[i].code[j++] ='0';
else hc[i].code[j++] ='1';
Stack[top--];
}
hc[i].code[j] ='\0';
}
}