實(shí)踐要求

1. 問(wèn)題描述

利用哈夫曼編碼進(jìn)行信息通訊可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送端通過(guò)一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼；在接收端將傳來(lái)的數(shù)據(jù)進(jìn)行譯碼(復(fù)原)。對(duì)于雙工信道(即可以雙向傳輸信息的信道)，每端都需要一個(gè)完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫(xiě)一個(gè)哈夫曼碼的編譯碼系統(tǒng)。

2. 基本要求

一個(gè)完整的系統(tǒng)應(yīng)具有以下功能:

1. I 初始化(Initialization)
   從終端讀入字符集大小n，及n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹(shù)，并將它存于文件hfmtree中。
2. C:編碼(Coding)
   利用已建好的哈夫曼樹(shù)(如不在內(nèi)存，則從文件hfmtree中讀 入)，對(duì)文件tobetrans中的正文進(jìn)行編碼，然后將結(jié)果存入codefile中。
3. D:譯碼(Decoding)
   利用已建好的哈夫曼樹(shù)將文件codefile中的代碼進(jìn)行譯 碼，結(jié)果存入文件textfile中。
4. P:印代碼文件(Print)
   將文件codefile以緊湊格式顯示在終端上，每行50個(gè)代 碼。同時(shí)將此字符形式的編碼文件寫(xiě)入文件codeprint中。
5. T:印哈夫曼樹(shù)(Tree print)
   將已在內(nèi)存中的哈夫曼樹(shù)以直觀(guān)的方式 樹(shù)或凹入表行式)顯示在終端上，同時(shí)將此字符形式的哈夫曼樹(shù)寫(xiě)入文件treeprint中。

3. 測(cè)試數(shù)據(jù)

可能出現(xiàn)8種字符，其概率分別為0.05，0.29，0.07，0.80，0.14，0.23，0.03，0.11試設(shè)計(jì)赫夫曼編碼。

3.1 input

請(qǐng)輸入字符串集大小

8

請(qǐng)輸入字符和權(quán)值 //用空格分離

a 5
b 29
c 7
d 8
e 14
f 23
g 3
h 11

3.2 output

若要輸出"abc"這個(gè)字符串的Huffman編碼
(正確的結(jié)果應(yīng)為0001111010)

實(shí)踐報(bào)告

1. 題目分析

說(shuō)明程序設(shè)計(jì)的任務(wù)，強(qiáng)調(diào)的是程序要做什么，此外列出各成員分工

程序設(shè)計(jì)任務(wù)：設(shè)計(jì)一個(gè)Huffman編碼譯碼系統(tǒng)，有I：初始化；C：編碼；D：譯碼；P：印代碼文件；T：印Huffman樹(shù)五個(gè)功能模塊。

2. 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

說(shuō)明程序用到的數(shù)據(jù)結(jié)構(gòu)的定義，主程序的流程及各模塊之間的層次關(guān)系

該程序主要用到的數(shù)據(jù)結(jié)構(gòu)是Huffman樹(shù)（最優(yōu)二叉樹(shù)）

主程序流程圖

3. 程序設(shè)計(jì)

實(shí)現(xiàn)概要設(shè)計(jì)中的數(shù)據(jù)類(lèi)型，對(duì)主程序、模塊及主要操作寫(xiě)出偽代碼，畫(huà)出函數(shù)的調(diào)用關(guān)系

各模塊偽代碼

初始化

編碼

解碼

打印

打印并存入Huffman樹(shù)

各函數(shù)層次關(guān)系圖

Initialization

EnCode

DeCode

Tree

4. 調(diào)試分析

程序復(fù)雜度分析

1. 空間復(fù)雜度
$$o(n)$$
空間復(fù)雜度主要是由節(jié)點(diǎn)的內(nèi)存空間和最小堆的內(nèi)存空間所占據(jù)的空間所決定的，因此總的空間復(fù)雜度為O(n)。
2. 時(shí)間復(fù)雜度
$$O(nlogn)$$
由于建立哈夫曼樹(shù)的過(guò)程中需要使用最小堆來(lái)實(shí)現(xiàn)節(jié)點(diǎn)的排序和合并。最小堆的插入和刪除操作都需要O(logn)的時(shí)間復(fù)雜度，而需要進(jìn)行n-1次操作，因此總的時(shí)間復(fù)雜度為O(nlogn)

所遇到的問(wèn)題的解決方法

• 問(wèn)題1:內(nèi)存泄露問(wèn)題，動(dòng)態(tài)分配的空間未釋放。
  解決:在函數(shù)解放使用free來(lái)釋放動(dòng)態(tài)分配的空間
• 問(wèn)題2:按格式讀取文件信息
  解決:使用buffer和characters兩個(gè)數(shù)組，buffer用于接收所有的txt文件中的內(nèi)容，將buffer中有用的信息賦值給characters。

5. 測(cè)試結(jié)果

列出測(cè)試結(jié)果，包括輸入和輸出

測(cè)試結(jié)果一

先初始化將字符以及其權(quán)值存入txt文件中

再對(duì)其進(jìn)行編碼

對(duì)編碼結(jié)果進(jìn)行解碼

打印Huffman樹(shù)并存入txt中

6. 用戶(hù)使用說(shuō)明

給出主界面及主要功能界面

使用說(shuō)明

首先初始化Huffman樹(shù)，然后進(jìn)行編碼，編碼后可選擇譯碼也可以選擇印代碼文件或者印Huffman樹(shù)。

7. 附錄

源程序文件清單:
huffman.cpp
treeprint.txt
textfile.txt
hfmtree.txt
codefile.txt
codeprint.txt

8. 全部代碼

huffman.cpp

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

using namespace std;

// 定義哈夫曼樹(shù)的節(jié)點(diǎn)結(jié)構(gòu)體
typedef struct node
{
    int weight;         // 權(quán)值
    char character;     // 字符
    struct node *left;  // 左子樹(shù)指針
    struct node *right; // 右子樹(shù)指針
} Node;

// 定義哈夫曼樹(shù)的節(jié)點(diǎn)類(lèi)型
typedef Node *HuffmanTree;

// 定義哈夫曼樹(shù)的節(jié)點(diǎn)最小堆
typedef struct heap
{
    int size;          // 堆的大小
    int capacity;      // 堆的容量
    HuffmanTree *data; // 堆數(shù)據(jù)存儲(chǔ)指針
} MinHeap;

// 初始化最小堆
MinHeap *initMinHeap(int capacity)
{
    // 動(dòng)態(tài)分配最小堆
    MinHeap *heap = (MinHeap *)malloc(sizeof(MinHeap));
    heap->capacity = capacity;
    heap->size = 0;
    heap->data = (HuffmanTree *)malloc(sizeof(HuffmanTree) * capacity);
    return heap;
}

// 最小堆中插入元素
void insert(MinHeap *heap, HuffmanTree node)
{
    if (heap->size >= heap->capacity)
    {
        return; // 如果堆已滿(mǎn)，直接退出
    }
    heap->data[heap->size] = node;  // 將元素插入堆底
    int current = heap->size++;     // 更新堆大小
    int parent = (current - 1) / 2; // 父節(jié)點(diǎn)的下標(biāo)
    // 自下往上調(diào)整堆，直到找到合適的位置插入新元素
    while (parent >= 0 && heap->data[current]->weight < heap->data[parent]->weight)
    {
        // 如果當(dāng)前元素比父節(jié)點(diǎn)的權(quán)值小，則交換兩個(gè)元素的位置
        HuffmanTree temp = heap->data[parent];
        heap->data[parent] = heap->data[current];
        heap->data[current] = temp;
        current = parent;
        parent = (current - 1) / 2;
    }
}

// 從最小堆中取出最小元素
HuffmanTree extractMin(MinHeap *heap)
{
    if (heap->size == 0) // 如果堆為空，直接返回空指針
    {
        return NULL;
    }
    HuffmanTree min = heap->data[0];          // 最小元素即為堆頂元素
    heap->data[0] = heap->data[--heap->size]; // 將堆底元素移到堆頂，并更新堆大小
    int current = 0;                          // 當(dāng)前節(jié)點(diǎn)的下標(biāo)
    int child = current * 2 + 1;              // 當(dāng)前節(jié)點(diǎn)的左孩子的下標(biāo)
    // 自上往下調(diào)整堆，直到找到合適的位置插入堆底元素
    while (child < heap->size) // 當(dāng)前節(jié)點(diǎn)還有孩子節(jié)點(diǎn)
    {
        if (child + 1 < heap->size && heap->data[child + 1]->weight < heap->data[child]->weight)
        {
            child++; // 找到當(dāng)前節(jié)點(diǎn)的左右孩子中較小的一個(gè)
        }
        if (heap->data[child]->weight < heap->data[current]->weight)
        {
            // 將當(dāng)前節(jié)點(diǎn)和較小孩子節(jié)點(diǎn)交換位置
            HuffmanTree temp = heap->data[child];
            heap->data[child] = heap->data[current];
            heap->data[current] = temp;
            current = child;         // 更新當(dāng)前節(jié)點(diǎn)的下標(biāo)
            child = current * 2 + 1; // 更新當(dāng)前節(jié)點(diǎn)的左孩子下標(biāo)
        }
        else
        {
            break; // 如果已經(jīng)滿(mǎn)足最小堆的性質(zhì)，則退出循環(huán)
        }
    }
    return min; // 返回被取出的最小元素
}

// 用最小堆構(gòu)建哈夫曼樹(shù)
HuffmanTree buildHuffmanTree(int *weights, char *characters, int n)
{
    // 初始化最小堆，將每個(gè)字符及其權(quán)重轉(zhuǎn)換成節(jié)點(diǎn)，并插入堆中
    MinHeap *heap = initMinHeap(n);
    for (int i = 0; i < n; i++)
    {
        Node *node = (Node *)malloc(sizeof(Node));
        node->weight = weights[i];
        node->character = characters[i];
        node->left = NULL;
        node->right = NULL;
        insert(heap, node); // 將節(jié)點(diǎn)插入堆中
    }
    // 不斷從最小堆中取出權(quán)重最小的兩個(gè)節(jié)點(diǎn)，合并成一個(gè)新節(jié)點(diǎn)，再插入堆中
    while (heap->size > 1)
    {
        HuffmanTree left = extractMin(heap);  // 取出堆頂節(jié)點(diǎn)，即最小權(quán)重節(jié)點(diǎn)
        HuffmanTree right = extractMin(heap); // 再次取出最小權(quán)重節(jié)點(diǎn)
        Node *parent = (Node *)malloc(sizeof(Node));
        parent->weight = left->weight + right->weight; // 新節(jié)點(diǎn)的權(quán)重為左右節(jié)點(diǎn)的權(quán)重之和
        parent->left = left;                           // 將左節(jié)點(diǎn)作為新節(jié)點(diǎn)的左孩子
        parent->right = right;                         // 將右節(jié)點(diǎn)作為新節(jié)點(diǎn)的右孩子
        insert(heap, parent);                          // 將新節(jié)點(diǎn)插入堆中
    }
    HuffmanTree root = extractMin(heap); // 最后堆中只剩下根節(jié)點(diǎn)，即為哈夫曼樹(shù)的根節(jié)點(diǎn)
    free(heap->data);                    // 釋放堆數(shù)組占用的空間
    free(heap);                          // 釋放最小堆結(jié)構(gòu)體占用的空間
    return root;                         // 返回哈夫曼樹(shù)的根節(jié)點(diǎn)指針
}
// 對(duì)單個(gè)字符進(jìn)行編碼模塊
char *encodeChar(HuffmanTree root, char ch)
{
    static char code[100]; // 申請(qǐng)存儲(chǔ)編碼的空間
    static int index = 0;  // 記錄編碼位數(shù)

    if (root == NULL)
    {
        return NULL;
    }

    if (root->character == ch)
    {
        code[index] = '\0'; // 編碼結(jié)尾
        index = 0;          // 編碼位數(shù)歸零
        return code;
    }

    code[index++] = '0';
    char *leftCode = encodeChar(root->left, ch);
    if (leftCode != NULL)
    {
        return leftCode;
    }

    index--; // 回溯
    code[index++] = '1';
    char *rightCode = encodeChar(root->right, ch);
    if (rightCode != NULL)
    {
        return rightCode;
    }

    index--; // 回溯
    return NULL;
}

// 對(duì)文本進(jìn)行編碼模塊
char *encode(HuffmanTree root, char *text)
{
    char *result = (char *)malloc(strlen(text) * 100 * sizeof(char)); // 申請(qǐng)存儲(chǔ)編碼結(jié)果的空間
    result[0] = '\0';                                                 // 初始化
    for (int i = 0; i < strlen(text); i++)
    {
        char *code = encodeChar(root, text[i]); // 對(duì)單個(gè)字符編碼
        if (code)
        {
            strcat(result, code); // 將編碼拼接到結(jié)果中
        }
    }
    return result;
}

// 初始化函數(shù)
HuffmanTree initialization()
{
    int n; // 字符集大小
    printf("請(qǐng)輸入字符集大?。篭n");
    scanf("%d", &n);
    int *weights = (int *)malloc(sizeof(int) * n);       // 動(dòng)態(tài)分配n個(gè)權(quán)重值
    char *characters = (char *)malloc(sizeof(char) * n); // 動(dòng)態(tài)分配n個(gè)字符
    printf("請(qǐng)輸入字符和權(quán)值：\n");
    for (int i = 0; i < n; i++)
    {
        scanf(" %c %d", &characters[i], &weights[i]);
    }
    HuffmanTree root = buildHuffmanTree(weights, characters, n);
    FILE *fp = fopen("hfmtree.txt", "w");
    fprintf(fp, "%d\n", n);
    for (int i = 0; i < n; i++)
    {
        fprintf(fp, "%c%s", characters[i], i == n - 1 ? "\n" : " ");
    }
    for (int i = 0; i < n; i++)
    {
        fprintf(fp, "%d%s", weights[i], i == n - 1 ? "\n" : " ");
    }
    fclose(fp);
    return root;
}

void EnCodeChar(HuffmanTree root)
{
    FILE *fp;
    char *characters;
    char buffer[100];
    int n;
    // 打開(kāi)文件
    fp = fopen("hfmtree.txt", "r");
    if (fp == NULL)
    {
        printf("文件打開(kāi)失敗\n");
        exit(1);
    }
    // 讀取第一行，獲取字符集大小
    fscanf(fp, "%d", &n);
    // 分配空間
    characters = (char *)malloc(n * sizeof(char));
    // 讀取第二行數(shù)據(jù)
    fgets(buffer, sizeof(characters) * 2, fp);
    fgets(buffer, sizeof(characters) * 2, fp);
    int i = 0;
    int j = 0;
    while (buffer[i] != NULL)
    {
        if (buffer[i] != ' ')
        {
            characters[j] = buffer[i];
            j++;
        }
        i++;
    }
    fclose(fp);
    for (int i = 0; i < n; i++)
    {
        int index = 0;
        char *res = encodeChar(root, characters[i]);
        printf("%c: %s\n", characters[i], res);
    }
}

void EnCode(HuffmanTree root)
{
    char tobetrans[100];
    char *result;
    printf("請(qǐng)輸入一個(gè)字符串：\n");
    scanf("%s", tobetrans); // 讀取輸入的字符串，存儲(chǔ)到字符數(shù)組中
    result = encode(root, tobetrans);
    printf("%s\n", result);
    FILE *fp = fopen("codefile.txt", "w");
    for (int i = 0; i < strlen(result); i++)
    {
        fprintf(fp, "%c", result[i]);
    }
    fclose(fp);
}

char DeCodeChar(HuffmanTree root, char *code)
{
    HuffmanTree p = root;
    while (*code != '\0')
    {
        if (*code == '0')
        {
            p = p->left;
        }
        else if (*code == '1')
        {
            p = p->right;
        }
        if (p->left == NULL && p->right == NULL)
        {
            return p->character;
        }
        code++;
    }
    return '\0';
}

void DeCode(HuffmanTree root)
{
    // 讀取譯碼文件
    FILE *fp_code = fopen("codefile.txt", "r");
    char *code = (char *)malloc(1000 * sizeof(char)); // 申請(qǐng)存儲(chǔ)代碼的空間
    fscanf(fp_code, "%s", code);                      // 讀取代碼
    fclose(fp_code);

    // 譯碼
    char *text = (char *)malloc(1000 * sizeof(char)); // 申請(qǐng)存儲(chǔ)譯文的空間
    int i = 0, j = 0;
    while (code[i] != '\0')
    {
        char *tmp = (char *)malloc(100 * sizeof(char)); // 申請(qǐng)臨時(shí)空間存儲(chǔ)單個(gè)字符的編碼
        int k = 0;
        while (DeCodeChar(root, tmp) == '\0')
        {
            tmp[k++] = code[i++];
        }
        text[j++] = DeCodeChar(root, tmp); // 譯碼并存儲(chǔ)譯文
        free(tmp);                         // 釋放臨時(shí)空間
    }
    text[j] = '\0';
    // 存儲(chǔ)譯文到文件中
    FILE *fp_text = fopen("textfile.txt", "w");
    fprintf(fp_text, "%s", text);
    fclose(fp_text);
    // 釋放申請(qǐng)的空間
    free(code);
    free(text);
}

void Print()
{
    FILE *fp;
    char buffer[100];
    fp = fopen("codefile.txt", "r");
    if (fp == NULL)
    {
        printf("文件打開(kāi)失敗\n");
        exit(1);
    }
    // 讀取數(shù)據(jù)
    fgets(buffer, 100, fp);
    printf("%s", buffer);
    fclose(fp);
    fp = fopen("codeprint.txt", "w");
    for (int i = 0; i < strlen(buffer); i++)
    {
        fprintf(fp, "%c", buffer[i]);
    }
    fclose(fp);
}

// 打印哈夫曼樹(shù)的函數(shù)
void PrintHfmTree(FILE *file, HuffmanTree root, int level, char *prefix, int is_last)
{
    // 如果根節(jié)點(diǎn)為空，則返回
    if (root == NULL)
    {
        return;
    }
    // 打印當(dāng)前節(jié)點(diǎn)的值
    printf("%s", prefix);
    printf(is_last ? "└── " : "├── ");
    printf("(%c:%d)\n", root->character, root->weight);
    fprintf(file, "%s", prefix);
    fprintf(file, is_last ? "└── " : "├── ");
    fprintf(file, "(%c:%d)\n", root->character, root->weight);

    // 更新前綴
    char new_prefix[128];
    sprintf(new_prefix, "%s%s", prefix, is_last ? "    " : "│   ");

    // 遞歸打印左右子樹(shù)
    PrintHfmTree(file, root->left, level + 1, new_prefix, (root->right == NULL));
    PrintHfmTree(file, root->right, level + 1, new_prefix, 1);
}

void Tree(HuffmanTree root)
{
    // 打開(kāi)文件treeprint
    FILE *file = fopen("treeprint.txt", "w");
    // 調(diào)用打印函數(shù)打印哈夫曼樹(shù)并寫(xiě)入文件
    PrintHfmTree(file, root, 0, "", 1);
    // 關(guān)閉文件
    fclose(file);
}

HuffmanTree root = nullptr; // 將huffman樹(shù)根設(shè)置為全局變量

void Window()
{
    char choice;
    char exit_choice;
    while (1)
    {
        printf("請(qǐng)選擇您的操作：\n");
        printf("I. 初始化\n");
        printf("C. 編碼\n");
        printf("D. 譯碼\n");
        printf("P. 印代碼文件\n");
        printf("T. 印哈夫曼樹(shù)\n");
        printf("E. 退出\n");
        scanf(" %c", &choice); // 加上空格忽略換行符

        switch (choice)
        {
        case 'I':
            printf("您選擇了初始化操作。\n");
            root = initialization();
            break;
        case 'C':
            if (root == NULL)
            {
                printf("請(qǐng)先進(jìn)行初始化操作！\n");
                break;
            }
            printf("您選擇了編碼操作。\n");
            EnCode(root);
            break;
        case 'D':
            if (root == NULL)
            {
                printf("請(qǐng)先進(jìn)行初始化操作！\n");
                break;
            }
            printf("您選擇了譯碼操作。\n");
            DeCode(root);
            break;
        case 'P':
            printf("您選擇了打印操作。\n");
            Print();
            break;
        case 'T':
            printf("您選擇了打印操作。\n");
            Tree(root);
            break;
        case 'E':
            printf("您確定要退出嗎？按E鍵確認(rèn)退出，按其他鍵返回上級(jí)菜單。\n");
            scanf(" %c", &exit_choice); // 加上空格忽略換行符
            if (exit_choice == 'E' || exit_choice == 'e')
            {
                printf("謝謝使用，再見(jiàn)！\n");
                return;
            }
            break;
        default:
            printf("無(wú)效的選擇，請(qǐng)重新選擇。\n");
            break;
        }
    }
}

int main()
{
    Window();
    return 0;
}

codefile.txt

0001111010

codeprint.txt

0001111010

hfmtree.txt

8
a b c d e f g h
5 29 7 8 14 23 3 11

textfile.txt

abc

treeprint.txt

└── (
:100)
    ├── (
:42)
    │   ├── (
:19)
    │   │   ├── (
:8)
    │   │   │   ├── (g:3)
    │   │   │   └── (a:5)
    │   │   └── (h:11)
    │   └── (f:23)
    └── (
:58)
        ├── (
:29)
        │   ├── (e:14)
        │   └── (
:15)
        │       ├── (c:7)
        │       └── (d:8)
        └── (b:29)

結(jié)束語(yǔ)

??因?yàn)槭撬惴ㄐ〔?，所以提供的方法和思路可能不是很好，?qǐng)多多包涵~如果有疑問(wèn)歡迎大家留言討論，你如果覺(jué)得這篇文章對(duì)你有幫助可以給我一個(gè)免費(fèi)的贊嗎？我們之間的交流是我最大的動(dòng)力！文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-759720.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)與算法】Huffman編碼/譯碼（C/C++）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！