main.cpp

#include <iostream>
#include <fstream>   // 文件读写
#include <string>    
#include <cctype>    // 用于判断字符是否为字母
#include <cstdlib>  //  rand()
#include <ctime>    // 用于初始化随机数种子

using namespace std;  // 替代std::string


struct WordFreq {
    string word;  
    int freq;     //频率
};


WordFreq wordList[10000];  
int wordCount = 0;         // 记录当前有多少个不重复单词



// 1. 用ifstream读取 Input.txt ，返回 string text 
string readFile() {
    string text = "";       
    ifstream inFile;        
    inFile.open("Input.txt"); 


    if (!inFile.is_open()) {
        cout << "错误：找不到 Input.txt 文件！请确保文件在程序同一目录下。" << endl;
        return "";  
    }

    char ch;  // 每次读取一个字符
    while (inFile.get(ch)) {  
        text += ch;  
    }

    inFile.close(); 
    return text;    
}


// 2：分割文本为单词，并存入 wordList（统计频率）
void splitTextToWords(string text) {
    string currentWord = "";  

    // 遍历文本中的每个字符
    for (int i = 0; i < text.length(); i++) {
        char ch = text[i]; 

        // 判断当前字符是否为字母（a-z A-Z）
        if (isalpha(ch)) {// 是字母：追加到当前单词中        
            currentWord += tolower(ch);  
        } else {// 不是字母：单词结束            
            if (currentWord != "") {
                // 检查当前单词是否已经在 wordList 中存在
                int existsIndex = -1;  
                for (int j = 0; j < wordCount; j++) {
                    if (wordList[j].word == currentWord) {
                        existsIndex = j;  
                        break;
                    }
                }

               
                if (existsIndex != -1) {
                    // 单词已存在：频率 +1
                    wordList[existsIndex].freq++;
                } else {
                    // 单词不存在：新增到 wordList 中
                    wordList[wordCount].word = currentWord; 
                    wordList[wordCount].freq = 1;           
                    wordCount++;  // ！！！不重复单词总数 +1
                }

                currentWord = "";  // 重置，准备下一个单词
            }
        }
    }

    // 处理文本最后一个单词（eg：I have a dream没有结束标点）
    if (currentWord != "") {
    	//找单词是否已经存在 
        int existsIndex = -1;
        for (int j = 0; j < wordCount; j++) {
            if (wordList[j].word == currentWord) {
                existsIndex = j;
                break;
            }
        }
        if (existsIndex != -1) {
            wordList[existsIndex].freq++;
        } else {
            wordList[wordCount].word = currentWord;
            wordList[wordCount].freq = 1;
            wordCount++;
        }
    }
}

// 快排的辅助函数
void swap(WordFreq &a, WordFreq &b) {
    WordFreq temp = a;
    a = b;
    b = temp;
}

// 3. 快速排序（按单词字母升序） left\right 都是index 
void quickSortByWord(int left, int right) {
    if (left >= right) return; 

    // 随机索引作为基准 
    int pivotIndex = left + rand() % (right - left + 1);
    // 和开头元素交换
    swap(wordList[left], wordList[pivotIndex]);
    WordFreq pivot = wordList[left];



    int i = left, j = right;
    while (i <= j) {
        // 找到左边第一个比基准大的元素
        while (wordList[i].word < pivot.word) i++;
        // 找到右边第一个比基准小的元素
        while (wordList[j].word > pivot.word) j--;

        // 交换
        if (i <= j) {
            swap(wordList[i], wordList[j]);
            i++;
            j--;
        }
    }

    // 递归排序左右两部分
    quickSortByWord(left, j);
    quickSortByWord(i, right);
}

// 4. 快速排序（按词频降序，词频相同按字母升序）
void quickSortByFreq(int left, int right) {
    if (left >= right) return;  

    // 随机索引作为基准 
    int pivotIndex = left + rand() % (right - left + 1);
    // 和开头元素交换
    swap(wordList[left], wordList[pivotIndex]);
    WordFreq pivot = wordList[left];

    int i = left, j = right;
    while (i <= j) {
        // 频率降序：先比频率，频率相同则按字母升序
        while (
            (wordList[i].freq > pivot.freq) ||  
            (wordList[i].freq == pivot.freq && wordList[i].word < pivot.word)  
        ) i++;

        while (
            (wordList[j].freq < pivot.freq) || 
            (wordList[j].freq == pivot.freq && wordList[j].word > pivot.word)  
        ) j--;

        if (i <= j) {
            swap(wordList[i], wordList[j]);
            i++;
            j--;
        }
    }

    // 递归排序左右两部分
    quickSortByFreq(left, j);
    quickSortByFreq(i, right);
}

// 5：输出按字母排序的词汇表
void printWordSortedList() {
    cout << "==================== 表1（按字母排序）====================" << endl;
    cout << "单词\t\t频率" << endl;  
    cout << "--------------------------------------------------------" << endl;
    for (int i = 0; i < wordCount; i++) {
        cout << wordList[i].word;
        if(wordList[i].word.length() < 8){	//格式冲齐 
        	cout << "\t"; 
		} 
        cout << "\t" << wordList[i].freq << endl;
    }
    cout << endl;
}

// 6：输出按词频排序的词汇表
void printFreqSortedList() {
    cout << "==================== 表2（按词频降序）====================" << endl;
    cout << "单词\t\t频率" << endl;
    cout << "--------------------------------------------------------" << endl;
    for (int i = 0; i < wordCount; i++) {
        cout << wordList[i].word;
        if(wordList[i].word.length() < 8){
        	cout << "\t";
		} 
        cout << "\t" << wordList[i].freq << endl;
    }
    cout << endl;
}


// 主函数：程序入口（按步骤执行所有功能）
int main() {
	
	srand((unsigned int)time(NULL));//设置随机数种子 
	
    cout << "开始生成英文词汇表..." << endl << endl;

    // 1.读取 Input.txt 文件
    string text = readFile();
    if (text == "") {  // 读取失败
        return 1;  
    }
    cout << "成功读取文件，文本长度：" << text.length() << " 个字符" << endl << endl;

    // 2.分割文本为单词并统计频率
    splitTextToWords(text);
    cout << "单词分割完成，共找到 " << wordCount << " 个不同单词" << endl << endl;

    // 3和5 按字母排序并输出
    quickSortByWord(0, wordCount - 1);  // 排序范围：0 到 wordCount-1
    printWordSortedList();

    //4和6按词频排序并输出
    quickSortByFreq(0, wordCount - 1);
    printFreqSortedList();

    cout << "词汇表生成完成！" << endl;
    return 0;
}