哈夫曼码编/译码系统

一、题目简介

? ? ? ?编写一个哈夫曼码的编/译码系统，实现对输入的文本信息自动统计并依此为依据建立一个哈夫曼码的编/译码系统。

二、数据结构设计

????????这段代码主要使用了链表和树这两种数据结构来实现哈夫曼编码的功能。以下是对代码中使用的数据结构设计的分析：

链表（Linked List）：

????????在函数tidyCharacter中，使用链表存储字符及其对应的权值。定义了结构体HuffmanTree作为链表节点，其中包含字符（ch）、权值（weight）、标志域（mark），以及指向下一个节点的指针（next）。整个链表的头结点通过linktree类型指针来表示。

typedef struct HuffmanTree {
????char ch; ????????????????// 键值
????int weight, mark; ???????// weight为权值，mark为标志域
????struct HuffmanTree *parent, *lchild, *rchild, *next;
} Hftree, *linktree;

????????通过链表，实现了对输入字符串的字符统计和合并相同字符的功能。

树（Tree）：

????????哈夫曼树是通过链表构建的，其中每个节点都有左孩子（lchild）、右孩子（rchild）、父节点（parent）等指针。在函数createHuffmanTree中，使用排好序的链表构建了哈夫曼树，通过合并权值最小的两个节点创建新的节点，直到最终形成整个哈夫曼树。

typedef struct HuffmanTree {
????char ch; ????????????????// 键值
????int weight, mark; ???????// weight为权值，mark为标志域
????struct HuffmanTree *parent, *lchild, *rchild, *next;
} Hftree, *linktree;

????????上述结构体中，lchild和rchild表示左孩子和右孩子，parent表示父节点。整个哈夫曼树的根节点可以通过返回的linktree指针来获得。

????????通过这两种数据结构的组合，实现了对输入字符串的处理、哈夫曼树的构建以及编码解码的功能。链表用于字符统计和排序，树用于构建哈夫曼树和实现编码解码。

三、算法设计

（1）整理输入的字符串合并相同的项，并求出每个字符在数组中出现的次数；

（2）将整理完的字符串按出现次数从小到大的顺序排列；

（3）用排完序的链表建立哈夫曼树；

（4）对哈夫曼树进行编码；

（5）解码；

（6）释放哈夫曼树所占用的空间。

?四、算法时间复杂度分析

（1）整理输入的字符串，合并相同的项，并求出每个字符在数组中出现的次数(tidyCharacter函数)

????????假设输入字符串的长度为n。在最坏情况下，需要遍历整个输入字符串。在每次循环中，需要在链表中查找相同的字符，最坏情况下需要遍历整个链表。

????????因此，时间复杂度为O(n^2)。

（2）将整理完的字符串按出现次数从小到大的顺序排列(sortNodes函数):

????????假设链表的长度为m。在最坏情况下，需要对链表进行排序。常见排序算法的时间复杂度为O(m*log(m))。

????????因此，时间复杂度为O(m*log(m))。

（3）用排完序的链表建立哈夫曼树(createHuffmanTree函数):

????????如果链表长度为m，则需要执行m-1次循环。在每次循环中，需要查找两个权值最小的节点，时间复杂度为O(m)。

????????因此，总时间复杂度为O(m^2)。

（4）对哈夫曼树进行编码(huffmanCoding函数):

????????假设哈夫曼树的叶子节点数为k。在最坏情况下，需要遍历哈夫曼树的所有叶子节点。每次遍历都可能涉及到向左或向右遍历树的高度，因此时间复杂度为O(k*h)，其中h是树的高度。在哈夫曼树中，h可以被认为是log(k)，因此最坏情况下的总时间复杂度为O(k*log(k))。

（5）解码(decode函数):

????????解码的时间复杂度取决于编码的长度，即输入的二进制字符串的长度为l。在最坏情况下，需要遍历整个二进制字符串。在每次遍历中，需要向左或向右遍历哈夫曼树的高度。

????????所以，总时间复杂度为O(l*h)。

（6）释放哈夫曼树所占用的空间(deleteNodes函数):

????????在最坏情况下，需要递归地删除哈夫曼树的所有节点。如果树的节点数为n，则递归调用次数为n。每次递归需要执行一些常量时间的操作，所以总时间复杂度为O(n)。

????????综上所述，整个程序的时间复杂度主要由哈夫曼树的构建和遍历过程决定，为O(m^2)和O(k*log(k))，其中m是链表的长度，k是哈夫曼树的叶子节点数。程序的实际性能还取决于输入数据的特性。如果链表长度m较小且叶子节点数k也较小，则整体性能可能较好。

五、程序代码

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

#define MAXLEN 100

// 哈夫曼树结点定义
typedef struct HuffmanTree {
    char ch;                 // 键值
    int weight, mark;        // weight为权值，mark为标志域
    struct HuffmanTree *parent, *lchild, *rchild, *next;
} Hftree, *linktree;

// 整理输入的字符串，合并相同的项，并求出每个字符在数组中出现的次数
linktree tidyCharacter(char character[]);

// 将整理完的字符串按出现次数从小到大的顺序排列
linktree sortNodes(linktree tree);

// 用排完序的字符串建立哈夫曼树
linktree createHuffmanTree(linktree tree);

// 对哈夫曼树进行编码
void huffmanCoding(linktree tree);

// 解码
void decode(linktree tree, char code[]);

// 释放哈夫曼树所占用的空间
void deleteNodes(linktree tree);

int main() {
    char character[MAXLEN], code[MAXLEN];

    printf("Enter a string:\n");
    scanf("%99s", character);  //%99s用于通过将字符数组 character 中读取的字符数限制为 99，防止缓冲区溢出。
    printf("\n");

    // 整理输入的字符串，构建链表
    linktree temp = tidyCharacter(character);

    // 将链表按照权值从小到大排序
    linktree ht = sortNodes(temp);

    // 用排序后的链表构建哈夫曼树
    linktree htree = createHuffmanTree(ht);

    // 对哈夫曼树进行编码
    huffmanCoding(htree);

    printf("Enter the binary code for testing decoding:\n\n");
    scanf("%99s", code);
    printf("\n");

    // 解码
    decode(htree, code);
    // 释放哈夫曼树的内存
    deleteNodes(htree);

    return 0;
}

// 整理输入的字符串，合并相同的项，并求出每个字符在数组中出现的次数
linktree tidyCharacter(char character[]) {
    int i = 0;
    linktree tree, ptr, beforeptr, node;

    // 创建链表的头结点
    tree = (linktree)malloc(sizeof(Hftree));
    if (!tree) return NULL;
    tree->next = NULL;

    // 遍历输入的字符串
    for (i = 0; character[i] != '\0' && character[i] != '\n'; i++) {
        ptr = tree;
        beforeptr = tree;

        // 创建新结点
        node = (linktree)malloc(sizeof(Hftree));
        if (!node) return NULL;
        node->next = NULL;
        node->parent = NULL;
        node->lchild = NULL;
        node->rchild = NULL;
        node->mark = 0;
        node->ch = character[i];
        node->weight = 1;

        // 如果链表为空，将新结点连接在头结点后面
        if (tree->next == NULL)
            tree->next = node;
        else {
            ptr = tree->next;
            // 在链表中查找是否已存在相同的字符
            while (ptr && ptr->ch != node->ch) {
                ptr = ptr->next;
                beforeptr = beforeptr->next;
            }
            if (ptr && ptr->ch == node->ch) {
                // 如果找到相同的字符，增加权值并释放新结点
                ptr->weight = ptr->weight + 1;
                free(node);
            } else {
                // 否则，将新结点插入链表后
                node->next = beforeptr->next;
                beforeptr->next = node;
            }
        }
    }
    return tree;
}

// 将整理完的字符串按出现次数从小到大的顺序排列
linktree sortNodes(linktree tree) {
    linktree head, ph, pt, beforeph;

    // 创建新链表的头结点
    head = (linktree)malloc(sizeof(Hftree));
    if (!head) return NULL;
    head->next = NULL;

    ph = head;
    beforeph = head;

    // 将原链表的结点按照权值插入新链表中
    while (tree->next) {
        pt = tree->next;
        tree->next = pt->next;
        pt->next = NULL;

        ph = head->next;
        beforeph = head;

        if (head->next == NULL)
            head->next = pt;
        else {
            while (ph && ph->weight < pt->weight) {
                ph = ph->next;
                beforeph = beforeph->next;
            }
            pt->next = beforeph->next;
            beforeph->next = pt;
        }
    }
    free(tree);
    return head;
}

// 用排完序的链表建立哈夫曼树
linktree createHuffmanTree(linktree tree) {
    linktree p, q, newnode, beforep;

    // 依次取两个权值最小的结点构建哈夫曼树
    for (p = tree->next, q = p->next; p != NULL && q != NULL; p = tree->next, q = p->next) {
        tree->next = q->next;
        q->next = NULL;
        p->next = NULL;

        // 申请新结点作为哈夫曼树的中间结点
        newnode = (linktree)malloc(sizeof(Hftree));
        if (!newnode) return NULL;
        newnode->next = NULL;
        newnode->mark = 0;

        newnode->lchild = p;
        newnode->rchild = q;
        p->parent = newnode;
        q->parent = newnode;
        newnode->weight = p->weight + q->weight;

        p = tree->next;
        beforep = tree;

        // 将新结点插入原链表的相应位置
        if (p != NULL && p->weight >= newnode->weight) {
            newnode->next = beforep->next;
            beforep->next = newnode;
        } else {
            while (p != NULL && p->weight < newnode->weight) {
                p = p->next;
                beforep = beforep->next;
            }
            newnode->next = beforep->next;
            beforep->next = newnode;
        }
    }
    return (tree->next);
}

// 对哈夫曼树进行编码
void huffmanCoding(linktree tree) {
    int index = 0;
    char *code;
    linktree ptr = tree;
    code = (char *)malloc(10 * sizeof(char));

    printf("Huffman Coding\n");      
    if (ptr == NULL) {
        printf("Huffman tree is empty!\n");
        exit(0);
    } else {
        while (ptr->lchild && ptr->rchild && ptr->mark == 0) {
            while (ptr->lchild && ptr->lchild->mark == 0) {
                code[index++] = '0';
                ptr = ptr->lchild;
                if (!ptr->lchild && !ptr->rchild) {
                    ptr->mark = 1;
                    code[index] = '\0';
                    printf("\tw[%c]=%d\t\t\t", ptr->ch, ptr->weight);
                    for (index = 0; code[index] != '\0'; index++)
                        printf("%c", code[index]);
                    printf("\n");
                    ptr = tree;
                    index = 0;
                }
            }
            if (ptr->rchild && ptr->rchild->mark == 0) {
                ptr = ptr->rchild;
                code[index++] = '1';
            }
            if (!ptr->lchild && !ptr->rchild) {
                ptr->mark = 1;
                code[index++] = '\0';
                printf("\tw[%c]=%d\t\t\t", ptr->ch, ptr->weight);
                for (index = 0; code[index] != '\0'; index++)
                    printf("%c", code[index]);
                printf("\n");
                ptr = tree;
                index = 0;
            }
            if (ptr->lchild->mark == 1 && ptr->rchild->mark == 1) {
                ptr->mark = 1;
                ptr = tree;
                index = 0;
            }
        }
    }
    printf("\n");
    free(code);
}

// 解码
void decode(linktree tree, char code[]) {
    int i = 0, j = 0;
    char *char01;
    linktree ptr = tree;
    char01 = (char *)malloc(10 * sizeof(char));

    printf("Decoding corresponding characters of Huffman code\n\n");
    for (j = 0, ptr = tree; code[i] != '\0' && ptr->lchild && ptr->rchild; j = 0, ptr = tree) {
        for (j = 0; code[i] != '\0' && ptr->lchild && ptr->rchild; j++, i++) {
            if (code[i] == '0') {
                ptr = ptr->lchild;
                char01[j] = '0';
            }
            if (code[i] == '1') {
                ptr = ptr->rchild;
                char01[j] = '1';
            }
        }
        if (!ptr->lchild && !ptr->rchild) {
            char01[j] = '\0';
            for (j = 0; char01[j] != '\0'; j++)
                printf("%c", char01[j]);
            printf("\t\t%c\n", ptr->ch);
            
        }
        if (code[i] == '\0' && ptr->lchild && ptr->rchild) {
            char01[j] = '\0';
            printf("No matching characters for the last few 0s and 1s sequence: %s!\n", char01);
            return;
        }
    }
    free(char01);
}

// 释放哈夫曼树所占用的空间
void deleteNodes(linktree tree) {
    linktree ptr = tree;
    if (ptr) {
        deleteNodes(ptr->lchild);
        deleteNodes(ptr->rchild);
        free(ptr);
    }
}