如何在C++中用树实现自定义符号表？及树确定码字疑问解答

Hey Marcus, let's break this down into two clear parts—first building a symbol table with a tree in C++, then unpacking what your professor is asking for with identifying used symbols and generating codewords via a tree.

A symbol table tracks identifiers (variables, functions, etc.) along with their attributes (type, scope, value). A Binary Search Tree (BST) is a great fit here because it lets you insert, search, and delete symbols in O(log n) time (on average), and it keeps symbols sorted lexicographically.

Step 1: Define the Tree Node Structure #

First, create a struct to represent each node in the tree. It'll store the symbol's name, its attributes, and pointers to left/right children:

#include <iostream>
#include <string>

struct SymbolNode {
    std::string symbolName;
    std::string dataType; // e.g., "int", "void function"
    int scopeLevel;       // 0 = global, 1 = local, etc.
    int usageCount;       // We'll use this later for your professor's task
    SymbolNode* left;
    SymbolNode* right;

    // Constructor
    SymbolNode(std::string name, std::string type, int scope)
        : symbolName(name), dataType(type), scopeLevel(scope), usageCount(0), left(nullptr), right(nullptr) {}
};

Step 2: Implement Core Operations #

Add functions to insert symbols, search for them, and traverse the tree to print the table:

Insert a Symbol

SymbolNode* insertSymbol(SymbolNode* root, std::string name, std::string type, int scope) {
    if (root == nullptr) {
        return new SymbolNode(name, type, scope);
    }

    // Insert left if symbol name is lex smaller, right if larger
    if (name < root->symbolName) {
        root->left = insertSymbol(root->left, name, type, scope);
    } else if (name > root->symbolName) {
        root->right = insertSymbol(root->right, name, type, scope);
    } else {
        // Handle duplicate symbols (update or warn)
        std::cout << "Warning: Symbol '" << name << "' already exists in this scope.\n";
    }
    return root;
}

Search for a Symbol

SymbolNode* searchSymbol(SymbolNode* root, std::string name) {
    if (root == nullptr || root->symbolName == name) {
        return root;
    }

    if (name < root->symbolName) {
        return searchSymbol(root->left, name);
    }
    return searchSymbol(root->right, name);
}

Traverse & Print the Symbol Table

In-order traversal will print symbols in lex order:

void printSymbolTable(SymbolNode* root) {
    if (root == nullptr) return;

    printSymbolTable(root->left);
    std::cout << "Symbol: " << root->symbolName 
              << " | Type: " << root->dataType 
              << " | Scope: " << root->scopeLevel 
              << " | Usage Count: " << root->usageCount << "\n";
    printSymbolTable(root->right);
}

Step 3: Test the Implementation #

Here's a quick main function to try it out:

int main() {
    SymbolNode* symbolTableRoot = nullptr;

    // Insert symbols
    symbolTableRoot = insertSymbol(symbolTableRoot, "total", "int", 0);
    symbolTableRoot = insertSymbol(symbolTableRoot, "calculateAvg", "void function", 0);
    symbolTableRoot = insertSymbol(symbolTableRoot, "tempVal", "float", 1);

    // Mark a symbol as used (increment usage count)
    SymbolNode* found = searchSymbol(symbolTableRoot, "total");
    if (found) found->usageCount++;

    // Print the full table
    std::cout << "Symbol Table:\n";
    printSymbolTable(symbolTableRoot);

    // Don't forget to free memory (add a destroyTree function for production code!)
    return 0;
}

Your professor is asking you to do two key things: filter symbols to only those actually used, then map each to a unique codeword using a tree. This is almost certainly referring to Huffman Coding—a common exercise in compilers or data structures.

Step 1: Identify Actually Used Symbols #

First, you need to track which symbols are actively used in your code (not just declared). That's why we added the usageCount field to the node:

• Every time your code references a symbol (e.g., reads/writes a variable, calls a function), increment its usageCount.
• After processing your code, filter out any symbols where usageCount == 0—these are unused and can be ignored.

Step 2: Use a Huffman Tree to Generate Codewords #

A Huffman Tree is a binary tree built to minimize the total length of codewords for symbols, based on their usage frequency (higher frequency = shorter codeword). Here's how it works:

1. Create leaf nodes: For each used symbol, make a leaf node with a weight equal to its usageCount.
2. Build the tree:
   • Repeatedly take the two nodes with the smallest weights.
   • Merge them into a new parent node whose weight is the sum of the two children.
   • Add this parent node back to your list of nodes.
   • Stop when only one node (the root) remains.
3. Assign codewords: Traverse the tree from root to leaf. Assign 0 to left branches and 1 to right branches (or vice versa). The path from root to a leaf is that symbol's unique codeword.

Example

Suppose your used symbols have these frequencies:

• total: 7 uses
• tempVal: 4 uses
• calculateAvg: 2 uses

Building the Huffman Tree:

1. Merge calculateAvg (2) and tempVal (4) into a parent node with weight 6.
2. Merge total (7) and the parent node (6) into the root node with weight 13.

Generating codewords:

• total: Left branch → 0
• tempVal: Right → Left → 10
• calculateAvg: Right → Right → 11

This gives you efficient, unique codewords for each used symbol—exactly what your professor is asking for.

内容的提问来源于stack exchange，提问作者Marcus Kim