数据结构 实验报告-3

第一题 哈夫曼编码：

一、实验内容：

给定一段文字，如果我们统计出字母出现的频率，是可以根据哈夫曼算法给出一套编码，使得用此编码压缩原文可以得到最短的编码总长。然而哈夫曼编码并不是唯一的。例如对字符串"aaaxuaxz"，容易得到字母 ‘a’、‘x’、‘u’、‘z’ 的出现频率对应为 4、2、1、1。我们可以设计编码 {‘a’=0, ‘x’=10, ‘u’=110, ‘z’=111}，也可以用另一套 {‘a’=1, ‘x’=01, ‘u’=001, ‘z’=000}，还可以用 {‘a’=0, ‘x’=11, ‘u’=100, ‘z’=101}，三套编码都可以把原文压缩到 14 个字节。但是 {‘a’=0, ‘x’=01, ‘u’=011, ‘z’=001} 就不是哈夫曼编码，因为用这套编码压缩得到 00001011001001 后，解码的结果不唯一，“aaaxuaxz” 和 “aazuaxax” 都可以对应解码的结果。本题就请你判断任一套编码是否哈夫曼编码。

二、实验目的：

掌握哈夫曼算法；

三、程序清单：

▶

Code

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
 
void xz(int a[], int l, int r) {
    int flag = 1;
    for (int i = l; i <= r && flag; ++i) {
        flag = 0;
        for (int j = l; j < r - (i - l); ++j) {
            if (a[j] > a[j + 1]) {
                flag = 1;
                int tem = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tem;
            }
        }
    }
}

int main() {
    int n;
    char cc;
    scanf("%d", &n);
    int Huffnum = 0, Huffqueue[3000] = { 0 }, top = 0, q[3000] = { 0 };
    for (int i = 0; i < n; ++i) {
        getchar();
        scanf("%c %d", &cc, &Huffqueue[top++]);
        q[top - 1] = Huffqueue[top - 1];
    }

    int head = 0;
    xz(Huffqueue, head, n - 1);
    while (top != head + 1) {
        int n1 = Huffqueue[head];
        Huffqueue[head] = 0;
        int n2 = Huffqueue[++head];
        Huffqueue[head] = 0;
        Huffqueue[head] = n1 + n2;
        xz(Huffqueue, head, n - 1);
        Huffnum += n1 + n2;
    }
    int m;
    scanf("%d", &m);
 
    for (int k = 0; k < m; k++) {
        char code[3000][66] = { 0 };
        int Ohuffnum = 0;
        for (int i = 0; i < n; ++i) {
            getchar();
            scanf("%c %s", &cc, code[i]);
            Ohuffnum += (int)strlen(code[i]) * q[i];
        }
        if (Ohuffnum != Huffnum) {
            printf("No\n");
        }
        else if (Ohuffnum == Huffnum) {
            int flag = 1;
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n && j != i; ++j) {
                    if (strlen(code[i]) <= strlen(code[j]) && strncmp(code[i], code[j], strlen(code[i])) == 0) {
                        flag = 0;
                        break;
                    }
                    else if (strlen(code[i]) > strlen(code[j]) && strncmp(code[i], code[j], strlen(code[j])) == 0) {
                        flag = 0;
                        break;
                    }
                }
                if (!flag) break;
            }
            if (!flag)printf("No\n");
            else printf("Yes\n");
             
        }
    }
    return 0;
}

四、调试步骤：

1. 输入题中的测试数据；
2. 检查程序输出与预期输出的差距，分析错误在程序的哪个部分；
3. 更改程序，再次测试，直到程序输出符合预期；

第二题 线索二叉树的建立和遍历：

一、实验内容：

本题要求实现对建立中序线索二叉树和中序遍历中序线索二叉树。

二、实验目的：

掌握二叉树的建立以及遍历；

三、程序清单：

▶

Code

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

typedef struct node {
    char data;
    struct node* Left;
    struct node* Right;
    int Zuo;
    int You;
} BiThreadNode, * BiThreadTree;
BiThreadNode* pre; 

BiThreadTree Creat() {
    BiThreadNode* T;
    char ch;
    if ((ch = getchar()) == '@')
        T = NULL;
    else {
        T = (BiThreadNode*)malloc(sizeof(BiThreadNode));
        T->data = ch;
        T->Left = Creat();
        T->Right = Creat();
    }
    return T;
}

void InThreading(BiThreadTree T) {
    if (T != NULL) {
        InThreading(T->Left);
        if (T->Left == NULL) {
            T->Zuo = 1;
            T->Left = pre;
        }
        else
            T->Zuo = 0;
        if (pre->Right == NULL) {
            pre->You = 1;
            pre->Right = T;
        }
        else
            pre->You = 0;
        pre = T;
        InThreading(T->Right);
    }
}

BiThreadNode* CreateInThrTree(BiThreadTree T) {
    BiThreadNode* ThrHead; 
    ThrHead = (BiThreadNode*)malloc(sizeof(BiThreadNode));
    ThrHead->You = 1;
    ThrHead->Right = ThrHead; 
    ThrHead->Zuo = 0;
    if (T == NULL)
        ThrHead->Left = ThrHead; 
    else {
        ThrHead->Left = T;
        pre = ThrHead; 
        InThreading(T);
        pre->Right = ThrHead; 
        pre->You = 1;
        ThrHead->Right = pre;
    }
    return ThrHead;
}

void ThrInOrderTraverse(BiThreadTree ThrHead) {
    BiThreadNode* temp = ThrHead->Left; 
    while (temp != ThrHead) {
        while (temp->Zuo == 0)
            temp = temp->Left; 
        printf("%c  %d  %d\n", temp->data, temp->Zuo, temp->You);
        while (temp->You == 1 && temp->Right != ThrHead) {
            temp = temp->Right;
            printf("%c  %d  %d\n", temp->data, temp->Zuo, temp->You);
        }
        temp = temp->Right; 
    }
}

int main() {
    BiThreadTree root;
    root = Creat();
    BiThreadNode* ThrHead = CreateInThrTree(root);
    ThrInOrderTraverse(ThrHead);
    return 0;
}

四、调试步骤：

1. 输入题中的测试数据；
2. 检查程序输出与预期输出的差距，分析错误在程序的哪个部分；
3. 更改程序，再次测试，直到程序输出符合预期；