有一說一，我太菜了，編碼花了我十幾個個小時才完成，終究是我不配了，
今天花了點時間，把哈夫曼樹的編碼和譯碼也完成了，在這兒補充更新一下源檔案，
后續會補充一下注釋，
運行結果如下
源檔案：
#include "優先權佇列.h"
#include "哈夫曼的stack.h"
//構造一棵空的二叉樹
void Create(BinaryTree* bt)
{
bt->root = NULL;
}
HFMTNode* NewBTNode(ElemType w, HFMTNode* lC, HFMTNode* rC)
{
HFMTNode* p = (HFMTNode*)malloc(sizeof(HFMTNode));
p->w = w;
p->lChild = lC;
p->rChild = rC;
p->Element = 0;
return p;
}
void MakeTree(BinaryTree* bt,ElemType w, BinaryTree* left, BinaryTree* right)
{
if (left == NULL || right == NULL)
return;
else
{
bt->root = NewBTNode(w, left->root,right->root);
left->root = right->root = NULL;
}
}
//哈夫曼先序遍歷
void PreOrder(HFMTNode* t)
{
if (!t)
return;
printf("%d ", t->w);
PreOrder(t->lChild);
PreOrder(t->rChild);
}
void PreOrderHFMTree(BinaryTree* bt)
{
printf("\n先序遍歷哈夫曼樹的結果為：\n");
PreOrder(bt->root);
}
// 哈夫曼中序遍歷
void InOrder(HFMTNode* t)
{
if (!t)
return;
InOrder(t->lChild);
printf("%d ", t->w);
InOrder(t->rChild);
}
void InOrderHFMTree(BinaryTree* bt)
{
printf("\n中序遍歷哈夫曼樹的結果為：\n");
InOrder(bt->root);
}
//構造哈夫曼樹演算法
void CreateHFMTree(BinaryTree*bt,int w[], int m)
{
PriorityQueue PQ; //定義優先權佇列PQ，用于存放二叉樹根節點指標
BinaryTree x,h,g; //x,y,z為二叉樹變數
int size;
Create(&h);
Create(&g);
CreatePQ(&PQ, m); // 初始化優先權佇列PQ，設優先權值存在于根節點的資料域
for (int i = 0; i < m; i++)
{
if (w[i] != 0)
{
MakeTree(&x, w[i], &h, &g);
Append(&PQ, x.root); //把傳進來的陣列里面的每一個元素都當做權值放入優先權佇列中
}
}
printf("原森林為：\n");
for (int i = 0; i < PQ.n; i++)
{
printf("%d ", PQ.elements[i].w);
}
printf("\n");
while (PQ.n > 1)
{
HFMTNode* X = NewBTNode(0 ,NULL, NULL);
HFMTNode* Y = NewBTNode(0, NULL, NULL);
HFMTNode* Z = NewBTNode(0, NULL, NULL);
Serve(&PQ, X); //取出此時權值最小的
Serve(&PQ, Y); //取出此時權值最小的
//下面進行合并節點操作，再講新的值放入優先權佇列
if (X->w < Y->w)
{
Z->w = X->w + Y->w;
Z->lChild = X;
Z->rChild = Y;
Append(&PQ, Z);
}
else
{
Z->w = X->w + Y->w;
Z->lChild = Y;
Z->rChild = X;
Append(&PQ, Z);
}
}
*bt->root = PQ.elements[0];
}
//進行哈夫曼編碼
HFMTNode* HFMBMFirst(BinaryTree *tree,Stack *S,char * temp,int * index,int *w,int length,int *frequency)
{
int fre = *frequency;
HFMTNode* p = tree->root;
if (!p||(fre>=length))
return NULL;
int k = *index;
while (p->lChild!=NULL)
{
stackPush(S, p);
p = p->lChild;
temp[k++] = '0';
}
*w = p->w;
temp[k] = '\0';
*index = k;
fre++;
*frequency = fre;
return p;
}
HFMTNode* HFMBMNext(HFMTNode* current, Stack* S, char* temp, int* index, int* w, int length, int* frequency)
{
int fre = *frequency;
int k = *index;
HFMTNode* change, * again = current;
HFMTNode* p;
BinaryTree h, i, j;
Create(&h);
Create(&i);
Create(&j);
MakeTree(&h, 'H', &i, &j);
change = h.root;
if (current->rChild && current->Element != 1 && (fre < length))
{
current->Element = 1;
stackPush(S, current);
p = current->rChild;
temp[k++] = '1';
while (p->lChild != NULL)
{
stackPush(S, p);
p = p->lChild;
temp[k++] = '0';
}
*w = p->w;
temp[k] = '\0';
*index = k;
fre++;
*frequency = fre;
return p;
}
else if ((fre < length) && (!stackIsEmpty(S)))
{
stackTop(S, change);
stackPop(S);
if ((change->rChild) && (change->Element != 1) && (fre < length))
{
temp[--k] = '\0';
change->Element = 1;
stackPush(S, change);
p = change->rChild;
temp[k++] = '1';
while (p->lChild != NULL)
{
stackPush(S, p);
p = p->lChild;
temp[k++] = '0';
}
*w = p->w;
temp[k] = '\0';
*index = k;
fre++;
*frequency = fre;
return p;
}
else if (change->rChild && change->Element == 1 && (fre < length))
{
while (change->Element == 1 && (fre < length))
{
stackTop(S, change);
stackPop(S);
temp[--k] = '\0';
}
if ((change->rChild) && (change->Element != 1) && (fre < length))
{
temp[--k] = '\0';
change->Element = 1;
stackPush(S, change);
change = change->rChild;
temp[k++] = '1';
while (change->lChild != NULL)
{
stackPush(S, change);
change = change->lChild;
temp[k++] = '0';
}
}
*w = change->w;
temp[k] = '\0';
*index = k;
fre++;
*frequency = fre;
return change;
}
}
else
{
p = current;
p->w = 0;
return p;
}
}
void HFMBMAll(BinaryTree* bt,int * list,int length, char BMofchar[26][8])
{
char temp[STACKSIZE] = "";
int index = 0;
int w=0;
int frequency = 0;
Stack S;
stackCreate(&S, STACKSIZE);
HFMTNode* current = HFMBMFirst(bt, &S, temp, &index,&w,length,&frequency);
while (current->w!=0)
{
for (int i = 0; i < 26; i++)
{
if (w == list[i])
{
printf("%c的編碼是", i + 97);
puts(temp);
printf("其權重為%d\n\n", w);
for (int j = 0; temp[j] != '\0'; j++)
{
BMofchar[i][j] = temp[j];
}
}
}
current = HFMBMNext(current, &S, temp, &index, &w,length,&frequency);
}
}
void main()
{
int list[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26};
BinaryTree bt,h,i,bt1;
Create(&bt);
Create(&bt1);
Create(&h);
Create(&i);
MakeTree(&bt, 0, &h, &i);
MakeTree(&bt1, 0, &h, &i);
CreateHFMTree(&bt,list, 26);
PreOrderHFMTree(&bt);
InOrderHFMTree(&bt);
printf("\n");
char str[20000];
char BMofchar[26][8] = {};
printf("\n請輸入你想進行哈夫曼編碼的字串：\n");
gets_s(str);
int length = 0;
int num[128] = { 0 };
for (int i = 0; str[i] != '\0'; i++)
{
num[str[i]]++;
}
int list2[26] = { 0 };
for (int i = 97; i < 123; i++)
{
if (num[i] != 0)
list2[i - 97] = num[i];
}
for (int i = 0; i < 26; i++)
{
printf("%c:%d ",i+97, list2[i]);
if (list2[i] != 0)
{
length++;
}
}
printf("\n\n");
CreateHFMTree(&bt1, list2,26);
PreOrderHFMTree(&bt1);
InOrderHFMTree(&bt1);
printf("\n\n");
HFMBMAll(&bt1,list2,length,BMofchar);
//輸出哈夫曼編碼演算法如下：
char AllBM[1000] = "";
char temp1[8] = "";
printf("此時存在已有的編碼為：\n");
for (int i=0; i < 26; i++)
{
if (BMofchar[i][0] != '\0')
puts(BMofchar[i]);
}
/*
for (int i = 0; str[i] != '\0'; i++)
{
printf("%c", str[i]);
}*/
printf("\n");
for (int i = 0; str[i] != '\0'; i++)
{
temp1[0] = str[i];
int direction = int(temp1[0])-97;
for (int num = 0; num < 26; num++)
{
if (num == direction)
{
strcat_s(AllBM, BMofchar[direction]);
//printf("%s ", BMofchar[direction]);
}
}
}
printf("\n");
printf("字符轉換為哈夫曼編碼后的資料為：\n");
puts(AllBM);
printf("\n");
//下面進行哈夫曼譯碼操作：
printf("哈夫曼譯碼之后結果為：\n");
char temp2[8] = "";
char AllYM[1000] = "";
int Y = 0;
char thechar[2] = "";
for (int i = 0; AllBM[i] != '\0'; i++)
{
temp2[Y++] = AllBM[i];
temp2[Y] = '\0';
for (int num = 0; num < 26; num++)
{
if (strcmp(temp2, BMofchar[num])==0)
{
thechar[0] = char(num + 97);
strcat_s(AllYM, thechar);
Y = 0;
}
}
}
puts(AllYM);
}
優先權佇列.h:
#pragma once
#include "HFMBTNODE.h"
typedef struct priorityQueue
{
HFMTNode* elements;
int n;
int maxSize;
}PriorityQueue;
void AdjustUp(HFMTNode heap[], int current)
{
int p = current;
HFMTNode temp;
while (p > 0)
{
if (heap[p].w < heap[(p - 1) / 2].w)
{
temp = heap[p];
heap[p] = heap[(p - 1) / 2];
heap[(p - 1) / 2] = temp;
p = (p - 1) / 2; //將p向上移動至當前考查元素的雙親節點位置
}
else //若p指向的元素不小于其雙親節點，則調整完畢
break;
}
}
void AdjustDown(HFMTNode heap[], int current, int border)
{
int p = current;
int minChild;
HFMTNode temp;
while (2 * p + 1 <= border)
{
if ((2 * p + 2 <= border) && (heap[2 * p + 1].w > heap[2 * p + 2].w))
{
minChild = 2 * p + 2;
}
else
{
minChild = 2 * p + 1;
}
if (heap[p].w <= heap[minChild].w)
{
break;
}
else
{
temp = heap[p];
heap[p] = heap[minChild];
heap[minChild] = temp;
p = minChild;
}
}
}
//創建一個空的優先權佇列
void CreatePQ(PriorityQueue* PQ, int mSize)
{
PQ->maxSize = mSize;
PQ->n = 0;
PQ->elements = (HFMTNode *)malloc(mSize * sizeof(HFMTNode));
}
// 銷毀一個優先權佇列，釋放其占用的空間
void Destory(PriorityQueue* PQ)
{
free(PQ->elements);
PQ->n = 0;
PQ->maxSize = 0;
}
//判斷優先權佇列是否為空
BOOL IsEmpty(PriorityQueue* PQ)
{
if (PQ->n == 0)
return TRUE;
else
return FALSE;
}
//判斷優先權佇列是否已滿
BOOL IsFull(PriorityQueue* PQ)
{
if (PQ->n == PQ->maxSize)
return TRUE;
else
return FALSE;
}
//獲取當前優先權佇列中的元素的數量
int Size(PriorityQueue* PQ)
{
return PQ->n;
}
//在優先權佇列中增加一個新元素x
void Append(PriorityQueue* PQ, HFMTNode *x)
{
if (IsFull(PQ))
return;
PQ->elements[PQ->n] = *x;
PQ->n++;
AdjustUp(PQ->elements, PQ->n - 1);
}
//取出優先級最高的元素，利用引數x回傳，并在優先權佇列中洗掉該元素
void Serve(PriorityQueue* PQ, HFMTNode* x)
{
if (IsEmpty(PQ))
return;
*x = PQ->elements[0];
PQ->n--;
PQ->elements[0] = PQ->elements[PQ->n];
AdjustDown(PQ->elements, 0, PQ->n - 1);
}
哈夫曼的stack.h:
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include "HFMBTNODE.h"
#define STACKSIZE 100
typedef struct Stack
{
int top;
int maxSize;
HFMTNode* element;
}Stack;
void stackCreate(Stack* S, int mSize)
{
S->maxSize = mSize;
S->element = (HFMTNode*)malloc(sizeof(HFMTNode) * mSize);
S->top = -1;
}
void stackDestory(Stack* S)
{
S->maxSize = 0;
S->top = -1;
free(S->element);
}
BOOL stackIsEmpty(Stack* S)
{
return S->top == -1;
}
BOOL stackIsFULL(Stack* S)
{
return S->top == S->maxSize - 1;
}
BOOL stackTop(Stack* S, HFMTNode* x)
{
if (stackIsEmpty(S))
{
return FALSE;
}
*x = S->element[S->top];
return TRUE;
}
BOOL stackPush(Stack* S, HFMTNode *x)
{
if (stackIsFULL(S))
return FALSE;
S->top++;
S->element[S->top] = *x;
return TRUE;
}
BOOL stackPop(Stack* S)
{
if (stackIsEmpty(S))
return FALSE;
S->top--;
return TRUE;
}
void Clear(Stack* S)
{
S->top = 1;
}
HFMBTNODE.h:
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<string>
typedef int ElemType;
typedef int BOOL;
#define TRUE 1
#define FALSE 0
typedef struct hfmTNode
{
int Element;
int w;
struct hfmTNode* lChild;
struct hfmTNode* rChild;
}HFMTNode;
typedef struct binarytree
{
HFMTNode* root;
}BinaryTree;
上半部分介紹了哈夫曼的中序遍歷等
哈夫曼編碼已完成，譯碼已完成，更新完畢，由此結束，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/275169.html
標籤：其他