数据结构实验(二)

Mikkob

845人浏览 · 2025-11-09 13:55:38

Mikkob · 2025-11-09 13:55:38 发布

实验四基于哈夫曼树的数据压缩算法

实验目的

1.掌握哈夫曼树的构造算法。

2.掌握哈夫曼编码的构造算法。

要求：

输入一串字符串，根据给定的字符串中字符出现的频率建立相应的哈夫曼树，构造哈夫曼编码表，在此基础上可以对压缩文件进行压缩(即编码)，同时可以对压缩后的二进制编码文件进行解压(即译码)。

输入要求多组数据，每组数据 1 行，为一个字符串(只考虑 26 个小写字母即可 )。当输入字符串为“0”时，输入结束

输出要求每组数据输出 2n+3 行(n 为输入串中字符类别的个数)。第 1 行为统计出来的字符出现频率(只输出存在的字符，格式为:字符:频度)，每两组字符之间用一个空格分隔，字符按照 ASCI 码从小到大的顺序排列。第 2 行至第 2n 行为哈夫曼树的存储结构的终态( 如主教材 139 页表 5.2( b),一行当中的数据用空格分隔)。第 2n+1 行为每个字符的哈夫曼编码(只输出存在的字符。格式为:字符:编码 )，每两组字符之间用一个空格分隔，字符按照 ASCI 码从小到大的顺序排列。第

2n+2 行为编码后的字符串，第 2n+3 行为解码后的字符串(与输入的字符串相同)。

实验原理

实验原理：哈夫曼树是一种带权路径长度最短的二叉树，用于数据压缩编码。其基本思想是根据字符出现的频率构建一棵二叉树，频率越高的字符离根节点越近，编码长度越短，从而实现数据的高效压缩。

在本实验中，首先统计输入字符串中每个字符出现的次数，然后根据这些次数构建哈夫曼树。接着，通过遍历哈夫曼树为每个字符生成唯一的哈夫曼编码。最后，利用生成的哈夫曼编码对输入字符串进行编码，实现数据压缩。同时，也可以通过哈夫曼树对编码后的字符串进行解码，恢复原始字符串

算法步骤：

统计字符频率：遍历输入字符串，统计每个字符出现的次数，存储在一个结构体数组中。
构建哈夫曼树：

将所有字符及其频率作为叶子节点，构建一个初始的森林

不断选择权值最小的两个节点，合并为一个新节点，新节点的权值为两个子节点权值之和，直到森林中只剩下一棵树，即哈夫曼树

生成哈夫曼编码：从根节点开始，对哈夫曼树进行遍历。向左子树走编码为 ‘0’，向右子树走编码为 ‘1’，直到叶子节点，记录每个叶子节点对应的字符编码
编码字符串：根据生成的哈夫曼编码，对输入字符串中的每个字符进行编码，得到编码后的字符串
解码字符串：根据哈夫曼树，从根节点开始，按照编码字符串中的 ‘0’ 和 ‘1’ 依次遍历哈夫曼树，直到到达叶子节点，输出对应的字符，完成解码。

算法实现关键：

结构体定义：定义结构体来存储字符及其出现次数，以及哈夫曼树节点的相关信息，包括权值、父节点、左右子节点、是否访问、字符、编码字符串、编码长度和节点编号等。
排序算法：使用冒泡排序算法对字符信息结构体数组按照出现次数和字典序进行排序。
选择最小权值节点：通过遍历哈夫曼树节点数组，选择两个权值最小且未被处理过的节点，用于构建哈夫曼树。
递归生成编码：使用递归函数，根据哈夫曼树的结构，为每个字符生成哈夫曼编码。

通过以上算法和步骤，实现了基于哈夫曼树的数据压缩算法，包括哈夫曼树的构建、哈夫曼编码的生成、字符串的编码和解码等功能

实验内容

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

typedef struct {
    char character;
    int count;
} CharCount;

// 全局声明字符信息数组
CharCount charInfoArray[10000];

// 按照字符出现次数从大到小对结构体数组进行排序（冒泡排序）
void sortByCount(CharCount* charInfos) {
    CharCount temp;
    int i, j;
    for (j = 0; j < 26; j++) {
        for (i = 0; i < 25; i++) {
            if (charInfos[i].count < charInfos[i + 1].count) {
                temp = charInfos[i];
                charInfos[i] = charInfos[i + 1];
                charInfos[i + 1] = temp;
            }
        }
    }
}

void sortByCharacter(CharCount* charInfos, int validCharCount) {
    CharCount temp;
    int i, j;
    for (j = 0; j < 26; j++) {
        for (i = 0; i < 25; i++) {
            if (charInfos[i].character > charInfos[i + 1].character && charInfos[i + 1].count > 0) {
                temp = charInfos[i];
                charInfos[i] = charInfos[i + 1];
                charInfos[i + 1] = temp;
            }
        }
    }
}

// 哈夫曼树节点结构体定义
typedef struct HuffmanTreeNode {
    int weight;
    int parent;
    int leftChild;
    int rightChild;
    int visited;
    char character;
    char codeStr[60];
    int codeLength;
    int nodeNum;
} HuffmanTreeNode, *HuffmanTree;

// 从哈夫曼树节点数组中选择两个权重最小且未被处理过的节点
void selectMinWeightNodes(HuffmanTree huffmanTree, int nodeCount, int* selectedIndex1, int* selectedIndex2) {
    int i;
    HuffmanTreeNode node1, node2;
    int index1, index2;
    index1 = index2 = 0;
    node1 = huffmanTree[1];
    node1.weight = 999999;
    for (i = 1; i <= nodeCount; i++) {
        if (huffmanTree[i].weight <= node1.weight && huffmanTree[i].visited == 0) {
            node1 = huffmanTree[i];
            index1 = i;
        }
    }
    node2 = huffmanTree[2];
    node2.weight = 999999;
    for (i = 1; i <= nodeCount; i++) {
        if (huffmanTree[i].weight <= node2.weight && index1!= i && huffmanTree[i].visited == 0) {
            node2 = huffmanTree[i];
            index2 = i;
        }
    }

    if (node1.weight == node2.weight && huffmanTree[index1].nodeNum > huffmanTree[index2].nodeNum) {
        int tempIndex;
        tempIndex = index1;
        index1 = index2;
        index2 = tempIndex;
    }

    *selectedIndex1 = index1;
    *selectedIndex2 = index2;
    huffmanTree[*selectedIndex1].visited = 1;
    huffmanTree[*selectedIndex2].visited = 1;
}

// 递归生成哈夫曼编码字符串
void generateCode(HuffmanTree huffmanTree, int currentLength, char code[], int nodeIndex, char codeChar) {
    int i;
    for (i = 0; i < currentLength - 1; i++) {
        huffmanTree[nodeIndex].codeStr[i] = code[i];
    }
    huffmanTree[nodeIndex].codeStr[i] = codeChar;
    huffmanTree[nodeIndex].codeStr[i + 1] = '\0';

    if (huffmanTree[nodeIndex].leftChild!= 0) {
        generateCode(huffmanTree, currentLength + 1, huffmanTree[nodeIndex].codeStr, huffmanTree[nodeIndex].leftChild, '0');
    }
    if (huffmanTree[nodeIndex].rightChild!= 0) {
        generateCode(huffmanTree, currentLength + 1, huffmanTree[nodeIndex].codeStr, huffmanTree[nodeIndex].rightChild, '1');
    }
}

// 构建哈夫曼树
void createHuffmanTree(HuffmanTree* huffmanTree, int distinctCharCount, char* inputStr, int validCharCount) {
    int selectedIndex1, selectedIndex2;
    if (distinctCharCount <= 1) {
        return;
    }
    int totalNodeCount = 2 * distinctCharCount - 1;
    *huffmanTree = (HuffmanTree)malloc((totalNodeCount + 1) * sizeof(HuffmanTreeNode));

    for (int i = 1; i <= totalNodeCount; i++) {
        (*huffmanTree)[i].parent = 0;
        (*huffmanTree)[i].leftChild = 0;
        (*huffmanTree)[i].rightChild = 0;
        (*huffmanTree)[i].visited = 0;
        (*huffmanTree)[i].codeLength = 0;
        (*huffmanTree)[i].nodeNum = i;
        (*huffmanTree)[i].weight = 0;
    }

    for (int i = 1; i <= distinctCharCount; i++) {
        (*huffmanTree)[i].weight = charInfoArray[i - 1].count;
        (*huffmanTree)[i].character = charInfoArray[i - 1].character;
    }

    for (int i = distinctCharCount + 1; i <= totalNodeCount; i++) {
        selectMinWeightNodes(*huffmanTree, i - 1, &selectedIndex1, &selectedIndex2);
        (*huffmanTree)[selectedIndex1].parent = i;
        (*huffmanTree)[selectedIndex2].parent = i;
        (*huffmanTree)[i].leftChild = selectedIndex1;
        (*huffmanTree)[i].rightChild = selectedIndex2;
        (*huffmanTree)[i].weight = (*huffmanTree)[selectedIndex1].weight + (*huffmanTree)[selectedIndex2].weight;
    }

    int rootCodeLength = (*huffmanTree)[totalNodeCount].codeLength;
    (*huffmanTree)[totalNodeCount].codeStr[rootCodeLength] = '1';

    if ((*huffmanTree)[totalNodeCount].leftChild) {
        generateCode(*huffmanTree, 1, "", (*huffmanTree)[totalNodeCount].leftChild, '0');
    }

    if ((*huffmanTree)[totalNodeCount].rightChild) {
        generateCode(*huffmanTree, 1, "", (*huffmanTree)[totalNodeCount].rightChild, '1');
    }
}

int main() {
    HuffmanTree huffmanTree;
    int inputStrLength, distinctCharCount, inputCount = 0;
    char inputStrings[100][7000], singleInputStr[7000];

    while (1) {
        scanf("%s", inputStrings[inputCount]);
        if (inputStrings[inputCount][0] == '0' && inputStrings[inputCount][1] == '\0') {
            break;
        }
        inputCount++;
    }

    for (int currentInputIndex = 0; currentInputIndex < inputCount; currentInputIndex++) {
        distinctCharCount = 0;

        // 初始化字符出现次数信息
        for (int i = 0; i < 27; i++) {
            charInfoArray[i].count = 0;
            charInfoArray[i].character = 'a' + i;
        }

        inputStrLength = strlen(inputStrings[currentInputIndex]);

        // 统计每个字符在当前输入字符串中的出现次数
        for (int i = 0; i < inputStrLength; i++) {
            charInfoArray[inputStrings[currentInputIndex][i] - 'a'].count++;
            singleInputStr[i] = inputStrings[currentInputIndex][i];
            singleInputStr[i + 1] = '\0';
        }

        sortByCount(charInfoArray);

        // 统计不同字符的个数
        for (int i = 0; i < 26; i++) {
            if (charInfoArray[i].count!= 0) {
                distinctCharCount++;
            }
        }

        sortByCharacter(charInfoArray, distinctCharCount);

        createHuffmanTree(&huffmanTree, distinctCharCount, inputStrings[currentInputIndex], distinctCharCount);

        if (distinctCharCount == 1) {
            huffmanTree = (HuffmanTree)malloc(3 * sizeof(HuffmanTreeNode));
            huffmanTree[1].weight = inputStrLength;
            huffmanTree[1].parent = huffmanTree[1].leftChild = huffmanTree[1].rightChild = 0;
            huffmanTree[1].character = inputStrings[currentInputIndex][0];
            huffmanTree[1].codeStr[0] = '0';
            huffmanTree[1].codeStr[1] = '\0';
        }

        int printCount = 0;

        // 输出每个出现过的字符及其出现次数
        for (int i = 0; i < 26; i++) {
            if (charInfoArray[i].count > 0) {
                printCount++;
                printf("%c:%d", charInfoArray[i].character, charInfoArray[i].count);
                if (printCount == distinctCharCount) {
                    printf("\n");
                } else {
                    printf(" ");
                }
            }
        }

        // 输出哈夫曼树各节点的相关信息
        for (int i = 1; i <= 2 * distinctCharCount - 1; i++) {
            printf("%d %d %d %d %d\n", i, huffmanTree[i].weight, huffmanTree[i].parent, huffmanTree[i].leftChild, huffmanTree[i].rightChild);
        }

        // 输出每个字符对应的哈夫曼编码
        for (int i = 1; i < distinctCharCount; i++) {
            printf("%c:%s ", huffmanTree[i].character, huffmanTree[i].codeStr);
        }
        printf("%c:%s\n", huffmanTree[distinctCharCount].character, huffmanTree[distinctCharCount].codeStr);

        // 使用哈夫曼编码对输入字符串进行编码并输出编码结果
        for (int i = 0; i < inputStrLength; i++) {
            for (int p = 1; p <= distinctCharCount; p++) {
                if (huffmanTree[p].character == inputStrings[currentInputIndex][i]) {
                    printf("%s", huffmanTree[p].codeStr);
                }
            }
        }
        printf("\n");

        // 输出原始输入字符串
        printf("%s\n", inputStrings[currentInputIndex]);

        // 释放哈夫曼树内存
        free(huffmanTree);
    }

    return 0;
}

按照指定示例输入得到结果

实验五基于二叉树的表达式求值算法

实验目的

目的： 1.掌握二叉树的二叉链表存储表示和二叉树的遍历等基本算法。 2.掌握根据中缀表达式创建表达式树的算法。 3.掌握基于表达式树的表达式求值算法。要求：输入一个表达式(表达式中的数均为小于 10 的正整数)，利用二叉树来表示该表达式，创建表达式树，然后利用二叉树的遍历操作求表达式的值。输入要求多组数据。每组数据 1 行，为一个表达式，表达式以“=”结尾。当输入只有一个“=”时，输入结束。输出要求每组数据输出 1 行，为表达式的值

实验原理

1表达式树的构建原理

中缀表达式到表达式树的转换：中缀表达式是我们常见的数学表达式形式，但计算机在计算时，将其转换为表达式树结构更便于处理。转换过程基于操作符的优先级和结合性规则。操作符优先级决定了计算的先后顺序，例如乘法和除法通常优先于加法和减法。结合性规则确定了具有相同优先级的操作符的计算顺序，如从左到右**。**

算法步骤：

1扫描中缀表达式，从左到右依次处理每个字符

2如果遇到操作数，创建一个只包含该操作数的二叉树节点，并将其压入操作数栈（这里使用节点树栈模拟）

3如果遇到操作符，比较其与运算符栈栈顶操作符的优先级

4如果当前操作符优先级高于栈顶操作符（或栈为空或栈顶为 ‘(’），将当前操作符压入运算符栈

5如果当前操作符优先级低于或等于栈顶操作符，从操作数栈弹出两个节点（先弹出的作为右子节点，后弹出的作为左子节点），从运算符栈弹出一个操作符，创建一个以该操作符为根节点，左右子节点为刚刚弹出的两个操作数节点的新二叉树节点，然后将新节点压入操作数栈

6当遇到括号时，左括号直接压入运算符栈，右括号则表示括号内表达式处理完毕，从运算符栈弹出操作符，从操作数栈弹出操作数，构建子树，直到遇到左括号，将左括号弹出

7处理完整个表达式后，运算符栈中剩余的操作符依次弹出，与操作数栈中的节点构建表达式树，直到运算符栈为空

**2 ** 基于表达式树的求值原理

后序遍历计算表达式值：表达式树构建完成后，通过后序遍历计算表达式的值。后序遍历的顺序是先访问左子树，再访问右子树，最后访问根节点，这与表达式的计算顺序（先计算子表达式，再计算根操作符）相匹配。

算法步骤：

1从根节点开始递归遍历表达式树

2如果当前节点是叶子节点（即操作数节点），直接返回该节点的值

3如果当前节点是操作符节点，先递归计算其左子树和右子树的值，然后根据操作符对左右子树的值进行相应的运算（如加法、减法、乘法、除法），并返回计算结果。

3****操作符优先级处理

通过预定义的优先级二维数组 Precede，可以快速获取两个操作符之间的优先级关系。在构建表达式树时，根据这个优先级关系决定操作符的入栈、出栈和构建子树的时机，确保表达式树的构建符合数学运算规则

整体流程：

程序首先读取输入的中缀表达式，在 CreateTree 函数中按照上述算法构建表达式树。然后，在 caculate 函数中通过后序遍历表达式树计算表达式的值。最后，根据要求输出结果。如果输入多个表达式，程序会依次处理每个表达式，将结果存储（修改后的代码使用数组存储结果），在遇到单独的 “=” 时，统一输出所有表达式的结果，实现了多表达式求值的功能。

实验内容

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

#define MAX 1000

char Precede[7][7] = {
    {'>','>','<','<','<','>','>'},
    {'>','>','<','<','<','>','>'},
    {'>','>','>','>','<','>','>'},
    {'>','>','>','>','<','>','>'},
    {'<','<','<','<','<','=','0'},
    {'>','>','>','>','0','>','>'},
    {'<','<','<','<','<','0','='}
};

typedef struct tree {
    int data;
    struct tree* lchild, * rchild;
} BitNode, * Bittree;

typedef struct stack {
    int* base;
    int* top;
    int stacksize;
} SqStack1; // 运算符栈

typedef struct stack2 {
    Bittree* base;
    Bittree* top;
    int stacksize;
} SqStack2; // 节点树栈

typedef struct resultStack {
    int* base;
    int* top;
    int stacksize;
} ResultStack; // 结果栈

void InitStack1(SqStack1* S) {
    S->base = (int*)calloc(MAX, sizeof(int));
    if (!S->base) {
        printf("内存分配失败\n");
        exit(0);
    }
    S->top = S->base;
    S->stacksize = MAX;
}

void InitStack2(SqStack2* S) {
    S->base = (Bittree*)calloc(MAX, sizeof(Bittree));
    if (!S->base) {
        printf("内存分配失败\n");
        exit(0);
    }
    S->top = S->base;
    S->stacksize = MAX;
}

void InitResultStack(ResultStack* S) {
    S->base = (int*)calloc(MAX, sizeof(int));
    if (!S->base) {
        printf("内存分配失败\n");
        exit(0);
    }
    S->top = S->base;
    S->stacksize = MAX;
}

void Push1(SqStack1* S, int ch) {
    if (S->top - S->base == S->stacksize) {
        printf("栈满了\n");
        exit(0);
    }
    *S->top++ = ch;
}

void Push2(SqStack2* S, Bittree tree) {
    if (S->top - S->base == S->stacksize) {
        printf("栈满了\n");
        exit(0);
    }
    *S->top++ = tree;
}

void PushResult(ResultStack* S, int result) {
    if (S->top - S->base == S->stacksize) {
        printf("结果栈满了\n");
        exit(0);
    }
    *S->top++ = result;
}

int Pop1(SqStack1* S) {
    int result;
    if (S->base == S->top) {
        printf("栈空\n");
        exit(0);
    }
    result = *--S->top;
    return result;
}

Bittree Pop2(SqStack2* S) {
    Bittree result;
    if (S->base == S->top) {
        printf("栈空\n");
        exit(0);
    }
    result = *--S->top;
    return result;
}

int PopResult(ResultStack* S) {
    int result;
    if (S->base == S->top) {
        printf("结果栈空\n");
        exit(0);
    }
    result = *--S->top;
    return result;
}

Bittree Gettop1(SqStack1* S) {
    return *(S->top - 1);
}

Bittree Gettop2(SqStack2* S) {
    return *(S->top - 1);
}

int sub(char ch) {
    switch (ch) {
        case '+': return 0;
        case '-': return 1;
        case '*': return 2;
        case '/': return 3;
        case '(': return 4;
        case ')': return 5;
        case '=': return 6;
    }
}

char Getpre(char ch1, char ch2) {
    return Precede[sub(ch1)][sub(ch2)];
}

int operate(int x1, int x2, int theta) {
    switch (theta) {
        case '+': return x1 + x2;
        case '-': return x1 - x2;
        case '*': return x1 * x2;
        case '/': return x1 / x2;
    }
}

Bittree createtreenode(BitNode* a, BitNode* b, int data) {
    Bittree tree = (Bittree)malloc(sizeof(BitNode));
    tree->data = data;
    tree->lchild = a;
    tree->rchild = b;
    return tree;
}

int StackEmpty1(SqStack1* s) {
    return s->top == s->base;
}

int StackEmpty2(SqStack2* s) {
    return s->top == s->base;
}

SqStack2* CreateTree(char* str) {
    SqStack1* OPRT = (SqStack1*)malloc(sizeof(SqStack1));
    SqStack2* OPND = (SqStack2*)malloc(sizeof(SqStack2));
    InitStack1(OPRT);
    InitStack2(OPND);
    Push1(OPRT, '=');
    int length = strlen(str);
    int i = 0;
    int theta;

    while ((str[i]!= '\0' || Gettop1(OPRT)!= '=') &&!StackEmpty1(OPRT)) {
        if (str[i] >= '0' && str[i] <= '9') {
            int x1 = 0;
            while (str[i] >= '0' && str[i] <= '9') {
                x1 = x1 * 10 + str[i] - '0';
                i++;
            }
            Bittree tree1 = createtreenode(NULL, NULL, x1);
            Push2(OPND, tree1);
        } else if (str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '/' || str[i] == '(' || str[i] == ')' || str[i] == '=') {
            switch (Getpre(Gettop1(OPRT), str[i])) {
                case '>':
                    theta = Pop1(OPRT);
                    Bittree a, b;
                    b = Pop2(OPND);
                    a = Pop2(OPND);
                    Bittree t = createtreenode(a, b, theta);
                    Push2(OPND, t);
                    break;
                case '=':
                    Pop1(OPRT);
                    i++;
                    break;
                case '<':
                    Push1(OPRT, str[i]);
                    i++;
                    break;
            }
        } else {
            printf("输入非法\n");
            exit(0);
        }
    }
    return OPND;
}

int caculate(Bittree tree) {
    int lchild = 0, rchild = 0;
    if (tree == NULL) {
        printf("Invalid expression\n");
        exit(0);
    }
    if (tree->lchild == NULL && tree->rchild == NULL) {
        return tree->data;
    } else {
        lchild = caculate(tree->lchild);
        rchild = caculate(tree->rchild);
        return operate(lchild, rchild, tree->data);
    }
}

int main() {
    char str[MAX];
    int resultArray[MAX];  // 辅助数组用于存储结果
    int resultCount = 0;    // 记录结果数量

    while (1) {
        gets(str);
        if (strcmp(str, "=") == 0) {
            break;
        }
        SqStack2* OPND = CreateTree(str);
        Bittree tree = Gettop2(OPND);
        int result = caculate(tree);
        resultArray[resultCount++] = result;
    }

    // 正序输出结果
    for (int i = 0; i < resultCount; i++) {
        printf("%d\n", resultArray[i]);
    }

    return 0;
}

示例输入及结果

DAMO开发者矩阵

DAMO开发者矩阵，由阿里巴巴达摩院和中国互联网协会联合发起，致力于探讨最前沿的技术趋势与应用成果，搭建高质量的交流与分享平台，推动技术创新与产业应用链接，围绕“人工智能与新型计算”构建开放共享的开发者生态。

更多推荐

使用概率图路径规划的机器人路径规划研究Octave（Matlab代码实现）

针对复杂未知环境下传统机器人路径规划算法适应性差、避障稳定性弱、全局搜索效率低的问题，本文开展基于概率图的机器人路径规划方法研究。概率图路径规划依托概率路线图建模思想，通过环境随机采样、节点连通性构建、最优路径检索的核心逻辑，摆脱了传统算法对环境精准建模的依赖，具备强环境适配性与高运算效率。本文系统阐述概率图路径规划的核心理论、运行机制与技术优势，基于Octave仿真平台搭建多场景机器人运动规划仿