?? huffman樹.cpp
字號:
/*
作者：李美學(xué)
學(xué)號：1050320125
單位：哈爾濱工業(yè)大學(xué)
版權(quán)：免費
創(chuàng)作日期：2007-5-2
程序功能：對文件進(jìn)行Huffman編碼和解碼。
聯(lián)系方式：limeixue8506@126.com
注釋：本程序只能對含有大小寫英文字母、逗號、
句號、感嘆號，空格符和換行符的文件進(jìn)行編碼。
******************************************
*/
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#define MAX_STACK ((1<<14) -1) //定義宏最大支持16k的編碼文件
struct node //定義結(jié)構(gòu)體
{
char data; //數(shù)據(jù)的字符表示形式
int weight; //定義數(shù)據(jù)的權(quán)重
struct node *left; //在Huffman樹中指向左子樹的指針
struct node *right; //在Huffman樹中指向右子樹的指針
struct node *father; //在Huffman樹中指向父節(jié)點的指針
};
struct node *root = NULL; //定義指向Huffman樹伍的根節(jié)點的指針
int stack[MAX_STACK]; //數(shù)組做堆棧使用
int top = 0; //棧頂
struct node leave[31] = { //定義數(shù)據(jù)及權(quán)重
{'a', 82, NULL, NULL, NULL}, //定義a -- z的字符及權(quán)重
{'b', 15, NULL, NULL, NULL},
{'c', 28, NULL, NULL, NULL},
{'d', 43, NULL, NULL, NULL},
{'e', 127, NULL, NULL, NULL},
{'f', 22, NULL, NULL, NULL},
{'g', 20, NULL, NULL, NULL},
{'h', 61, NULL, NULL, NULL},
{'i', 70, NULL, NULL, NULL},
{'j', 2, NULL, NULL, NULL},
{'k', 8, NULL, NULL, NULL},
{'l', 40, NULL, NULL, NULL},
{'m', 24, NULL, NULL, NULL},
{'n', 67, NULL, NULL, NULL},
{'o', 75, NULL, NULL, NULL},
{'p', 19, NULL, NULL, NULL},
{'q', 1, NULL, NULL, NULL},
{'r', 60, NULL, NULL, NULL},
{'s', 63, NULL, NULL, NULL},
{'t', 91, NULL, NULL, NULL},
{'u', 28, NULL, NULL, NULL},
{'v', 10, NULL, NULL, NULL},
{'w', 24, NULL, NULL, NULL},
{'x', 2, NULL, NULL, NULL},
{'y', 20, NULL, NULL, NULL},
{'z', 1, NULL, NULL, NULL},
{',', 30, NULL, NULL, NULL}, //定義,的字符及權(quán)重
{'.', 20, NULL, NULL, NULL}, //定義.的字符及權(quán)重
{'!', 10, NULL, NULL, NULL}, //定義!的字符及權(quán)重
{' ', 162, NULL, NULL, NULL}, //定義空格的字符及權(quán)重
{'\n',16, NULL, NULL, NULL} //定義換行的字符及權(quán)重
};
int n = 31; //記錄數(shù)組leave[]的大小
FILE *in, *out; //定義全局文件指針
void zerostack( )/*堆棧清零函數(shù)*/
{
int i;
for(i = 0; i < 80; i++)
stack[i] = 0;
top = 0;
}
void push(int x)/*壓棧函數(shù)*/
{
stack[top] = x;
top++;
}
int pop( )/*出棧函數(shù)*/
{
if(!top)
{
printf("棧是空的！\n");
return -1;
}
top--;
return top;
}
void printstack() /*打印堆棧內(nèi)容函數(shù)*/
{
int i;
for(i = top - 1; i >= 0; i--)
printf("%d",stack[i]);
}
struct node *copy(int m) /*將數(shù)組leave[]的第m個元素的內(nèi)容復(fù)制到新開辟的節(jié)點中去,返回新節(jié)點的指針*/
{
struct node *p;
p = (struct node *)malloc(sizeof(struct node)); //申請結(jié)構(gòu)體指針
if(p == NULL)
{
printf("No enough memory !\n");
exit(0);
}
p->data = leave[m].data;
p->weight = leave[m].weight;
p->left = leave[m].left;
p->right = leave[m].right;
p->father = leave[m].father;
if(leave[m].left != NULL)
(leave[m].left)->father = p;
if(leave[m].right != NULL)
(leave[m].right)->father = p;
return p;
}
int searchmin() /*尋找數(shù)組leave[]中權(quán)最小的元素*/
{
int i = 0, t = 0;
int min = leave[0].weight;
for(i = 0; i < n; i++)
{
if(min > leave[i].weight)
{
min = leave[i].weight;
t = i;
}
}
return t;
}
void del(int m) /*刪除數(shù)組leave[]中的第m個元素*/
{
int i;
for(i = m; i < n - 1; i++)
{
leave[i] = leave[i + 1];
}
n--;
}
void add(struct node *p)/*在數(shù)組leave[]中加入*p所指向的結(jié)點*/
{
leave[n].data = p->data;
leave[n].weight = p->weight;
leave[n].left = p->left;
leave[n].right = p->right;
leave[n].father = p->father;
p->left->father = &leave[n];
p->right->father = &leave[n];
n++;
free(p);
}
struct node *link(struct node *p1, struct node *p2)/*建立新節(jié)點,并聯(lián)結(jié)p1與p2所指向的節(jié)點*/
{
struct node *p;
p = (struct node *)malloc(sizeof(struct node)); //申請結(jié)構(gòu)體指針
if(p == NULL)
{
printf("No enough memory !\n");
exit(0);
}
p->left = NULL;
p->right = NULL;
p->left = p1;
p1->father = p;
p->right = p2;
p2->father = p;
p->data = 0;
p->weight = (p1->weight) + (p2->weight); //新節(jié)點的權(quán)是兩節(jié)點權(quán)的和
return p;
}
struct node *maketree()/*生成Huffman樹,返回樹的根*/
{
int i = 0, j = 0;
struct node *p, *p1, *p2;
while(n >1)
{
i = searchmin(); //函數(shù)調(diào)用
p1 = copy(i);
del(i);
j = searchmin(); //函數(shù)調(diào)用
p2 = copy(j);
del(j);
p = link(p1, p2); //函數(shù)調(diào)用
add(p);
}
leave[0].father = NULL;
return (&leave[0]);
}
struct node *search(struct node *p, char data) /*查找節(jié)點函數(shù)*/
{
static struct node *q = NULL;
struct node *old;
if(p != NULL)
{
if(p->data == data || p->data == (data + 32)) //大寫字母與小寫字母都一起當(dāng)小寫字母處理
{
q = p;
}
else
{
q = search(p->left, data); //遞歸調(diào)用
q = search(p->right, data);
}
}
old = q;
q= NULL;
return old;
}
void code(char data, int x, FILE *out )/*找到指定的節(jié)點后進(jìn)行編碼*/
{
int i;
char ch;
struct node *old, *p;
p = search(root, data);
if(p == NULL)
{
printf("字符%c未定義!\n", data);
return;
}
old = p;
zerostack();
while(p->father != NULL)
{
if(p == p->father->left)
push(0);
if(p == p->father->right)
push(1);
p = p->father;
}
if(x == 0)
{
for(i = top -1; i >= 0; i--)
{
ch = (char)(stack[i] + 48);
fputc(ch, out);
}
}
if(x == 1)
{
if(old->data != ' ' && old->data != '\n')
printf("\ndata = %c\tweight = %d\tcode = ", old->data, old->weight);
else if (old->data == ' ') //對空格字符的特殊處理
printf("\ndata = space\tweight = %d\tcode = ", old->weight);
else //對換行字符的特殊處理
printf("\ndata = Enter\tweight = %d\tcode = ", old->weight);
printstack();
}
zerostack();
}
int trace(int x, FILE *out)/*在堆棧中給定編碼,按編碼找到對應(yīng)的節(jié)點,x為堆棧中編碼的起始為*/
{
struct node *p, *old;
int i = x;
p = root;
while(p != NULL)
{
old = p;
if(!stack[i])
p = p->left;
else
p = p->right;
i++;
}
fputc(old->data, out);
return (i-1);
}
void encode()/*編碼函數(shù)*/
{
char ch;
char infile[20], outfile[20];
printf("\n請輸入被編碼文件的文件名和存放編碼文件的文件名:\n");
scanf("%s", infile);
scanf("%s", outfile);
in = fopen(infile, "r");
out = fopen(outfile, "w");
if(in == NULL || out == NULL)
{
printf("文件打開失敗!\n");
exit(0);
}
while((ch = fgetc(in)) != EOF)
code(ch, 0, out);
fclose(in); //關(guān)閉文件
fclose(out);
}
void decode() /*解碼函數(shù)*/
{
int x , i = 0;
char ch, infile[20], outfile[20];
printf("\n請輸入編碼文件名和存放還原文件名:\n");
scanf("%s", infile);
scanf("%s", outfile);
in = fopen(infile, "r");
out = fopen(outfile, "w");
if(in == NULL || out == NULL)
{
printf("文件打開失敗!\n");
exit(0);
}
zerostack();
while((ch = fgetc(in)) != EOF)
{
if(ch == '0')
push(0);
else if(ch == '1')
push(1);
else //對換行符不做任何處理
;
}
for(x = 0; x <top; )
x = trace(x, out);
fclose(in); //關(guān)閉文件
fclose(out);
}
void view()/*打印數(shù)據(jù)項及其編碼*/
{
char ch;
for(ch = 'a'; ch <= 'z'; ch++)
code(ch, 1, NULL);
code(',', 1, NULL);
code('.', 1, NULL);
code('!', 1, NULL);
code(' ', 1, NULL);
code('\n', 1, NULL);
}
char display()
{
char c;
do{
printf("\n請選擇:\n");
printf("1---查看字符和其相應(yīng)編碼.\n");
printf("2---編碼文件.\n");
printf("3---解碼文件.\n");
printf("4---退出程序.\n");
c = getche();
}while(c < '1' || c > '4');
return c;
}
void preorder(struct node *root)/*遍歷Huffman數(shù)*/
{
static struct node *q = NULL;
if(root != NULL)
{
if((root->data >= 'a' && root->data <= 'z' ) || root->data ==',' || root->data == '.' || root->data == ' ' || root->data =='!' || root->data =='\n')
printf("\ndata:%c\tweight:%d", root->data, root->weight);
preorder(root->left);
preorder(root->right);
}
}
void Exit()
{
printf("\n謝謝使用!\n");
exit(0);
}
main()
{
char choice;
printf("歡迎使用!");
root = maketree();
while(1)
{
choice = display();
switch(choice)
{
case '1':
view();
break;
case '2':
encode();
printf("編碼成功！\n");
break;
case '3':
decode();
printf("解碼成功！\n");
break;
case '4':
Exit();
default:
break;
}
}
return 0;
}?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -