C++实现BST统计文本四字符组合时出现异常字符问题排查

我有托尔金《指环王：护戒使者》的纯文本（已去除逗号、句号、连字符等标点，且全为小写），希望用二叉搜索树（BST）统计文本中所有含空格的四字符组合的出现次数。编写代码后发现，打印的四字符组合中出现了原文本不存在的字符（如ˇ、ń），已通过Notepad++确认原文本无此类字符，现寻求问题原因及解决办法。

相关代码 #

#include <iostream>
#include <fstream>
#include <string>
//#include <windows.h>   ///for checking results in slow-mo

using namespace std;

struct node
{
    string key;
    int count;
    node *left;
    node *right;
    node *parent;
};

node *dummy;

node *Add(node* &r, const string& k, node* par=nullptr)
{
    if(!r)
    {
        r = new node;
        r->key = k;
        r->count = 1;
        r->left = r->right = nullptr;
        r->parent = par;
        return r;
    }

    if(r->key == k)
    {
        r->count++;
        return r;
    }

    if(r->key > k) return Add(r->left, k, r);
    return Add(r->right, k, r);
}

void CountOccurrences(node* &root, const string& filename)
{
    ifstream file(filename);
    if (!file)
    {
        cerr << "Cannot open file: " << filename << endl;
        return;
    }

    string fourChars;
    char currentChar;
    while (file.get(currentChar))
    {
        fourChars += currentChar;

        if (fourChars.length() == 4)
        {
            Add(root, fourChars);
            fourChars.erase(0, 1);  // Usuwa pierwszy znak, przechodząc do kolejnej czwórki
        }
    }

    file.close();
}

void InOrderTraversal(node* r)
{
    if (!r) return;
    InOrderTraversal(r->left);
    cout << "Czworka: |" << r->key << "| Liczba wystapien: " << r->count << endl;
    //Sleep(100);   /// for checking results in slow-mo
    InOrderTraversal(r->right);
}

int main()
{
    node *root = nullptr;
    dummy = new node;
    dummy->right = nullptr;

    string filename = "The_Fellowship_Of_The_Ring.txt";

    CountOccurrences(dummy->right, filename);

    InOrderTraversal(dummy->right);

    return 0;
}

问题原因 #

• 编码读取不匹配：原文本大概率是UTF-8编码（可能带BOM），但ifstream默认以本地系统编码（如Windows的GBK）读取，导致多字节UTF-8字符被拆分成单个char，生成无效乱码。
• char类型截断：UTF-8中部分特殊字符占2-4字节，用单字节char读取会截断这些字符，产生不存在的乱码字符。
• 未过滤无效字符：代码没有过滤文件中的隐藏控制字符（如UTF-8 BOM标记），这类字符被读入后混入四字符组合，导致出现异常字符。
• 冗余指针逻辑：dummy节点属于多余设计，虽不直接导致乱码，但增加了指针操作的复杂度。

解决办法 #

1. 统一编码与读取方式 #

• 用Notepad++将文本保存为UTF-8无BOM格式，消除隐藏的BOM标记。
• 修改文件读取逻辑，按二进制方式读取完整内容，避免编码转换错误：

  void CountOccurrences(node* &root, const string& filename)
  {
      ifstream file(filename, ios::binary);
      if (!file)
      {
          cerr << "Cannot open file: " << filename << endl;
          return;
      }
  
      // 一次性读取全部内容
      string content((istreambuf_iterator<char>(file)), istreambuf_iterator<char>());
      file.close();
  
      string fourChars;
      for (char currentChar : content)
      {
          // 过滤仅保留小写字母和空格
          if ((currentChar >= 'a' && currentChar <= 'z') || currentChar == ' ')
          {
              fourChars += currentChar;
              if (fourChars.length() == 4)
              {
                  // 仅统计包含空格的四字符组合
                  if (fourChars.find(' ') != string::npos)
                  {
                      Add(root, fourChars);
                  }
                  fourChars.erase(0, 1);
              }
          }
      }
  }
  

2. 过滤非目标字符 #

在读取字符时，只保留小写字母和空格，直接排除所有其他字符（包括控制字符、乱码片段），确保四字符组合仅包含合法内容。

3. 移除冗余指针逻辑 #

删除dummy节点，直接使用root指针操作BST，简化代码：

int main()
{
    node *root = nullptr;
    string filename = "The_Fellowship_Of_The_Ring.txt";

    CountOccurrences(root, filename);
    InOrderTraversal(root);

    return 0;
}

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