实验目的：
要求通过课程设计的实践，在数据结构的表示、数据结构的选择及应用、算法设计与实现等方面加深对数据结构课程基本内容的理解和综合运用能力的提高。
实验内容：
1．从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树并将它存于文件hfmTree中.将已在内存中的哈夫曼树以直观的方式（比如树）显示在终端上；
2．利用已经建好的哈夫曼树，对一段字符文本进行编码，然后将结果以紧凑格式显示在终端上，每行50个代码。
3．利用已建好的哈夫曼树将上一步获得的编码进行译码，并输出结果。
实验要求：
(1)界面友好，函数功能要划分好
(2)程序要加必要的注释
(3)要提供程序测试方案
(4)程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。
实验时间：6学时
实验地点：知行楼306
实验过程及结果：
1、哈夫曼树的创建。
2、哈夫曼编码的实现。
3、根据上述两步中的哈夫曼树和哈夫曼编码，输入一段字符文本，给出其对应的哈夫曼编码序列。
4、根据已建好的哈夫曼树，对上一步所获得的编码序列进行译码并输出。
Huffman树的基本实现
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 5;
const int maxn = 10;
typedef struct {
char data;
int w;
int f;
int l;
int r;
}HTNode;
typedef struct node {
char cd[N];
int start;
node(){
start=N-1;
}
}Hcode;
HTNode huffman[maxn];
Hcode code[maxn];
void create(int n0) {
for (int i = n0 + 1; i < 2 * n0; i++) {
int min1 = inf, min2 = inf;
int lnode = -1, rnode = -1;
for (int j = 1; j < i; j++) {
if (huffman[j].f == -1) {
if (huffman[j].w < min1) {
min1 = huffman[j].w;
lnode = j;
}
else if (huffman[j].w < min2) {
min2 = huffman[j].w;
rnode = j;
}
}
}
//printf("%d %d\n",lnode,rnode);
huffman[i].w = min1 + min2;
huffman[i].l = lnode; huffman[i].r = rnode;
huffman[lnode].f = huffman[rnode].f = i;
huffman[i].f = -1;
//printf("i:left%d right:%d father:%d weight:%d data:%c \n",huffman[i].l,huffman[i].r,huffman[i].f,huffman[i].w,huffman[i].data);
}
for (int i = 1; i < 2 * n0; i++) {
printf("i:%d left:%d right:%d father:%d weight:%d data:%c \n", i, huffman[i].l, huffman[i].r, huffman[i].f, huffman[i].w, huffman[i].data);
}
}
void build(int n) {
for (int i = 1; i <= n; i++) {
huffman[i].f = -1;
huffman[i].l = huffman[i].r = huffman[i].f = -1;
scanf("%d",&huffman[i].w);
scanf(" %c",&huffman[i].data);
//printf("i:left%d right:%d father:%d weight:%d data:%c \n",huffman[i].l,huffman[i].r,huffman[i].f,huffman[i].w,huffman[i].data);
}
}
void makecode(int n0) {
printf("字符编码:\n");
for (int i = 1; i <= n0; i++) {
int c = i;
int f = huffman[i].f;
while (f != -1) {
if (huffman[f].l==c) {
code[i].cd[code[i].start--] = '0';
}
else {
code[i].cd[code[i].start--] = '1';
}
c = f;
f = huffman[c].f;
}
printf("%c: %s\n",huffman[i].data, code[i].cd + code[i].start + 1);
}
}
char ret[1000][1000];
int cnt=0;
void match(char a[],int n0){
for (int j=0 ; j<strlen(a); j++ )
for (int i = 1; i <= n0; i++){
if(huffman[i].data==a[j]){
printf("%s",code[i].cd + code[i].start + 1);
strcpy(ret[cnt],code[i].cd + code[i].start + 1);
cnt++;
break;
}
}
puts("");
}
/* 6 a b c d e f abcdef */
void re(int n0){
for(int i=0;i<cnt;i++){
for(int j=1;j<=n0;j++){
if(!strcmp(ret[i],code[j].cd+code[j].start + 1)){
printf("%c",huffman[j].data);
}
}
}
}
void _again(int n0){
char str[1000];
printf("\n请输入一串01序列，本程序即将进行解密\n");
scanf("%s",str);
int rt=2*n0-1;
printf("根节点编号%d\n",rt);
for(int i=0;i<strlen(str);i++){
if(str[i]=='0'){
rt=huffman[rt].l;
}else{
rt=huffman[rt].r;
}
if(huffman[rt].l==-1&&huffman[rt].r==-1){
printf("%c",huffman[rt].data);
rt=2*n0-1;
}
}
}
int main() {
int n;
printf("请输入字符数量:\n");
scanf("%d",&n);
build(n);
create(n);
makecode(n);
printf("请输入编码序列:\n");
char ins[1000];
scanf("%s",ins);
match(ins,n);
re(n);
_again(n);
}
2019/11/29
huffman更新，输入一篇文章，对每个单词编码，然后对文章编码解码。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 30;
const int maxn = 1000;
typedef struct {
char data;
double weight;
int father;
int lchild;
int rchild;
}HTNode;
typedef struct node {
char cd[N];
int start;
node(){
start=N-1;
}
}Hcode;
HTNode huffman[maxn];
Hcode code[maxn];
char page[10000];
void create(int n0) {//开始建立huffman树
n0--;
for (int i = n0 + 1; i < 2 * n0; i++) {//建立分支节点
double min1 = 1000, min2 = 1000;
int lnode = -1, rnode = -1;
for (int j = 1; j < i; j++) {
if (huffman[j].father == -1) {//该节点尚未合并
if (huffman[j].weight < min1) {//找最小值并且记录它数组对应的下标
min1 = huffman[j].weight;
lnode = j;
}
else if (huffman[j].weight < min2) {//找第二最小值并且记录他数组下标
min2 = huffman[j].weight;
rnode = j;
}
}
}
huffman[i].weight = min1 + min2;//合并
huffman[i].lchild = lnode; huffman[i].rchild = rnode;//设置分支节点的左右孩子
huffman[lnode].father = huffman[rnode].father = i;//左右孩子的父亲节点为该分支
huffman[i].father = -1;//分支节点暂时没有父节点
}
for (int i = 1; i < 2 * n0; i++) {//存到文件并且在显示屏上面打印
printf("i:%d left:%d right:%d father:%d weight:%lf data:%c \n", i, huffman[i].lchild, huffman[i].rchild, huffman[i].father, huffman[i].weight, huffman[i].data);
}
printf("创建成功\n");
}
int n=1;
void build() {
int statis1[26]={0};//统计小写字母出现的次数
int statis2[26]={0};//统计大写字母出现的次数
int symbol[10]={0};//统计符号出现的次数
for(int i=0;i<strlen(page);i++){
if(page[i]>='a'&&page[i]<='z'){
statis1[page[i]-'a']++;
}else if(page[i]>='A'&&page[i]<='Z'){
statis2[page[i]-'A']++;
} else{
switch(page[i]){
case '.':symbol[0]++;break;
case ',':symbol[1]++;break;
case '!':symbol[2]++;break;
case '-':symbol[3]++;break;
case ' ':symbol[4]++;break;
default:symbol[5]++;break;
}
}
}
int N=strlen(page);
for(int i=0;i<26;i++){
if(statis1[i]>=1){
huffman[n].father=huffman[n].lchild=huffman[n].rchild=-1;
huffman[n].weight=((double)statis1[i]*1.0/strlen(page))*100;
cout<<char(i+'a')<<"出现次数: "<<statis1[i]<<" 权值"<<huffman[n].weight<<endl;
huffman[n++].data=i+'a';
}
}
for(int i=0;i<26;i++){
if(statis2[i]>=1){
huffman[n].father=huffman[n].lchild=huffman[n].rchild=-1;
huffman[n].weight=((double)statis2[i]*1.0/strlen(page))*100;
cout<<char(i+'A')<<"出现次数: "<<statis2[i]<<" 权值"<<huffman[n].weight<<endl;
huffman[n++].data=i+'A';
}
}
for(int i=0;i<=5;i++){
if(symbol[i]>=1){
huffman[n].father=huffman[n].lchild=huffman[n].rchild=-1;
huffman[n].weight=((double)symbol[i]/N)*100;
cout<<"出现次数: "<<symbol[i]<<" 权值"<<huffman[n].weight<<endl;
if(i==0)huffman[n++].data='.';
else if(i==1)huffman[n++].data=',';
else if(i==2)huffman[n++].data='!';
else if(i==3)huffman[n++].data='-';
else if(i==4)huffman[n++].data=' ';
else huffman[n++].data=96;
}
}
}
void makecode(int n0) {
n0--;
printf("字符编码:\n");
for (int i = 1; i <= n0; i++) {//对叶子节点进行编码
int c = i;//拿到当前叶子节点对应数组下标的编号
int f = huffman[i].father;//拿到它的父亲节点
while (f != -1) {//不为根节点，到根节点时编码结束
if (huffman[f].lchild==c) {//判断该节点是在他父亲节点的左子树还是右子树，左子树编码0，右子树编码1
code[i].cd[code[i].start--] = '0';
}
else {
code[i].cd[code[i].start--] = '1';
}
c = f;//c变成当前节点的父节点
f = huffman[c].father;//每次f拿到当前节点的父节点，不断地向根节点靠近
}
printf("%c: %s\n",huffman[i].data, code[i].cd + code[i].start + 1);//输出该叶子节点的编码
}
}
char ret[10000];//存字符
int _count;
void match(char a[],int n0){//根据输入给出的字符串和叶子节点做匹配，然后输出即可
n0--;
_count=0;
printf("编码为:\n");
cout<<strlen(a)<<endl;
for (int j=0 ; j<strlen(a); j++ )//遍历输入的字符串
for (int i = 1; i <= n0; i++){//遍历叶子节点找输入的字符对应的01串
if(huffman[i].data==a[j]){//找对对应的字符
strcat(ret,code[i].cd + code[i].start + 1);//将他追加复制到res数组(因为要50个没换一行)
//cout<<(code[i].cd + code[i].start + 1)<<endl;
break;//结束多余的扫描
}
}
cout<<ret<<endl;
}
void _again(int n0){//对输入的字符串从根节点往下面找，找到一个字符把根节点重置一下
n0--;
char str[1000000];
printf("\n本程序将自动到文件中找01序列，本程序即将进行解密\n");
FILE *fin=fopen("C:\\Users\\mayn\\Desktop\\T\\read.txt","r");
fscanf(fin,"%s",str);
int rt=2*n0-1;//先拿到根节点数组下标再说
printf("根节点编号%d\n",rt);
printf("解码为:\n");
for(int i=0;i<strlen(str);i++){//遍历输入的01序列
if(str[i]=='0'){//0表示往根节点左孩子走
rt=huffman[rt].lchild;
}else{//1表示往根节点右孩子走
rt=huffman[rt].rchild;
}
if(huffman[rt].lchild==-1&&huffman[rt].rchild==-1){//到达叶子节点，输出对应字符，再将根基的重置一下
printf("%c",huffman[rt].data);
rt=2*n0-1;
}
}
}
int main() {
printf("请输入一篇英语文章\n");
gets(page);
build();
cout<<n<<endl;
create(n);
makecode(n);
printf("请输入编码序列:\n");
char ins[10000];
gets(ins);
match(ins,n);
_again(n);
}
黑框无法读入太多字符，所以改从文件读入01序列。
京公网安备 11010502036488号