运行出现vector下标超出范围

Question

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <map>

using namespace std;

// 哈夫曼树结点
struct HuffNode {
    char ch; // 字符
    int weight; // 权值
    int parent, lchild, rchild; // 父结点、左子结点、右子结点
    string code; // 编码
};
// 比较函数
struct cmp {
    bool operator()(const HuffNode& n1, const HuffNode& n2) {
        return n1.weight > n2.weight;
    }
};
// 建立哈夫曼树
void createHuffTree(vector<HuffNode>& huffTree, const vector<char>& chars, const vector<int>& weights) {
    priority_queue<HuffNode, vector<HuffNode>, cmp> pq; // 小根堆
    size_t n = chars.size();
    huffTree.resize(2 * n - 1); // 初始化哈夫曼树
    for (int i = 0; i < n; i++) {
        huffTree[i].ch = chars[i];
        huffTree[i].weight = weights[i];
        huffTree[i].parent = -1;
        huffTree[i].lchild = -1;
        huffTree[i].rchild = -1;
        pq.push(huffTree[i]);
    }
    for (size_t i = n; i < 2 * n - 1; i++) {
        HuffNode min1 = pq.top(); pq.pop();
        HuffNode min2 = pq.top(); pq.pop();
        huffTree[i].weight = min1.weight + min2.weight;
        huffTree[i].lchild = (min1.weight <= min2.weight) ? (i - n) : (i - n + 1);
        huffTree[i].rchild = (min1.weight > min2.weight) ? (i - n) : (i - n + 1);
        huffTree[i].parent = -1;
        min1.parent = i; min2.parent = i;
        pq.push(huffTree[i]);
    }
}
// 建立哈夫曼编码
void createHuffCode(vector<HuffNode>& huffTree) {
    size_t n = huffTree.size() / 2;
    for (int i = 0; i < n; i++) {
        int j = i;
        while (huffTree[j].parent != -1) {
            if (huffTree[huffTree[j].parent].lchild == j) {
                huffTree[i].code += '0';
            }
            else {
                huffTree[i].code += '1';
            }
            j = huffTree[j].parent;
        }
        reverse(huffTree[i].code.begin(), huffTree[i].code.end());
    }
}
// 哈夫曼编码
void huffEncode(const vector<HuffNode>& huffTree, map<char, string>& codeMap) {
    size_t n = huffTree.size() / 2;
    for (int i = 0; i < n; i++) {
        codeMap[huffTree[i].ch] = huffTree[i].code;
    }
}
// 哈夫曼译码
void huffDecode(const vector<HuffNode>& huffTree, const string& code, string& text) {
    size_t i = huffTree.size() - 1;
    for (char c : code) {
        if (c == '0') {
            i = huffTree[i].lchild;
        }
        else if (c == '1') {
            i = huffTree[i].rchild;
        }
        else { // 编码中存在不能识别的字符
            text = "";
            break;
        }
        if (i < huffTree.size() / 2) { // 当前结点是叶子结点，可输出字符
            text += huffTree[i].ch; // 恢复原字符
            i = huffTree.size() - 1; // 重置为根结点
        }
    }
}

int main() {
    // 初始化数据 
    vector<char> chars = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M',
    'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V','W','X','Y','Z' };
    vector<int> weights = { 186, 64, 13, 22, 32, 103, 21, 15, 47, 57, 1, 5, 32,
    20,18,61,80,15,1,48,51,80,23,8,18,76 };
    size_t n = chars.size();
    // 建立哈夫曼树
    vector<HuffNode> huffTree;
    createHuffTree(huffTree, chars, weights);
    // 建立哈夫曼编码
    createHuffCode(huffTree);
    cout << "Character to code mapping:" << endl;
    for (int i = 0; i < n; i++) {
        cout << chars[i] << "---->" << huffTree[i].code << endl;
    }
    // 测试编码和译码
    string text = "THE PROGRAM IS MY FAVORITE";
    string code;
    map<char, string> codeMap;
    huffEncode(huffTree, codeMap);
    for (char ch : text) {
        code += codeMap[ch];
    }
    cout << "Encoded code length:" << endl;
    cout << code.length() << endl;
    string decodeText;
    huffDecode(huffTree, code, decodeText);
    cout << "Decoded text:" << endl;
    cout << decodeText << endl;
    // 测试调试数据
    chars = { 'A', 'B', 'C', 'D' };
    weights = { 1, 3, 5, 7 };
    n = chars.size();
    createHuffTree(huffTree, chars, weights);
    createHuffCode(huffTree);
    cout << "Character to code mapping:" << endl;
    for (int i = 0; i < n; i++) {
        cout << chars[i] << "---->" << huffTree[i].code << endl;
    }
    string testCode = "111110100";
    huffDecode(huffTree, testCode, decodeText);
    cout << testCode << "---->" << decodeText << endl;
    return 0;
}

Answer 1

huffDecode 中 rchild 和 lchild 的值为 -1 ， 转换成 size_t 变成了很大的数 超过了 vector 7 的范围。