❶ 怎麼樣用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';
}
}