基于不同策略的英文单词的词频统计和检索系统（C++）

文章目录

• 准备工作
• 一、实验目的
• 二、设计内容
• 三、测试数据
• 四、源程序清单
• 五、运行结果
• • 5.1 程序运行结果
  • 5.2 文件输出结果
• 六、关键算法
• • 6.1 顺序表的顺序查找
  • 6.2 单链表的顺序查找
  • 6.3 顺序表的折半查找
  • 6.4 排序树查找
  • 6.5 哈希表的开放定址法
  • 6.6 哈希表的链地址法

准备工作

修改源代码中的path环境路径为自己的输入输出文件存放目录的路径，并在其中准备InFile.txt文件及其中的内容

一、实验目的

1、掌握基于线性表、二叉排序树和散列表不同存储结构的查找算法。
2、掌握不同检索策略对应的平均查找长度（ASL）的计算方法，明确不同检索策略的时间性能的差别。

二、设计内容

一篇英文文章存储在一个文本文件中，然后分别基于线性表、二叉排序树和哈希表不同的存储结构，完成单词词频的统计和单词的检索功能。同时计算不同检索策略下的平均查找长度ASL，通过比较ASL的大小，对不同检索策略的时间性能做出相应的比较分析（比较分析要写在实习报告中的“收获和体会”中）。

1. 读取一篇包括标点符号的英文文章（InFile.txt），假设文件中单词的个数最多不超过5000个。从文件中读取单词，过滤掉所有的标点。
2. 分别利用线性表（包括基于顺序表的顺序查找、基于链表的顺序查找、基于顺序表的折半查找）、二叉排序树和哈希表（包括基于开放地址法的哈希查找、基于链地址法的哈希查找）总计6种不同的检索策略构建单词的存储结构。
3. 不论采取哪种检索策略，完成功能均相同。
   （1）词频统计
   当读取一个单词后，若该单词还未出现，则在适当的位置上添加该单词，将其词频计为1；若该单词已经出现过，则将其词频增加1。统计结束后，将所有单词及其频率按照词典顺序写入文本文件中。其中，不同的检索策略分别写入6个不同的文件。
   基于顺序表的顺序查找— OutFile1.txt
   基于链表的顺序查找— OutFile2.txt
   折半查找— OutFile3.txt
   基于二叉排序树的查找— OutFile4.txt
   基于开放地址法的哈希查找— OutFile5.txt
   基于链地址法的哈希查找— OutFile6.txt
   注：如果实现方法正确，6个文件的内容应该是一致的。
   （2）单词检索
   输入一个单词，如果查找成功，则输出该单词对应的频率，同时输出查找成功的平均查找长度ASL和输出查找所花费的时间。如果查找失败，则输出“查找失败”的提示。
   实验提示：不同的检索策略所采取的class="superseo">数据结构不一样，算法实现的过程不一样，但查找结果是一样的。

三、测试数据

本处的InFile.txt中的内容选用了马丁路德金的《I have a dream》

I am happy to join with you today in what will go down in history as the greatest demonstration for freedom in the history of our nation.
Five score years ago, a great American, in whose symbolic shadow we stand today, signed the Emancipation Proclamation. This momentous decree came as a great beacon light of hope to millions of Negro slaves who had been seared in the flames of withering injustice. It came as a joyous daybreak to end the long night of bad captivity.
But one hundred years later, the Negro still is not free. One hundred years later, the life of the Negro is still sadly crippled by the manacles of segregation and the chains of discrimination. One hundred years later, the Negro lives on a lonely island of poverty in the midst of a vast ocean of material prosperity. One hundred years later, the Negro is still languished in the corners of American society and finds himself an exile in his own land. And so we've come here today to dramatize a shameful condition.
In a sense we've come to our nation's capital to cash a check. When the architects of our republic wrote the magnificent words of the Constitution and the Declaration of Independence, they were signing a promissory note to which every American was to fall heir. This note was a promise that all men, yes, black men as well as white men, would be guaranteed the "unalienable Rights" of "Life, Liberty and the pursuit of Happiness." It is obvious today that America has defaulted on this promissory note, insofar as her citizens of color are concerned. Instead of honoring this sacred obligation, America has given the Negro people a bad check, a check which has come back marked "insufficient funds."
But we refuse to believe that the bank of justice is bankrupt. We refuse to believe that there are insufficient funds in the great vaults of opportunity of this nation. And so, we've come to cash this check, a check that will give us upon demand the riches of freedom and the security of justice.
We have also come to this hallowed spot to remind America of the fierce urgency of Now. This is no time to engage in the luxury of cooling off or to take the tranquilizing drug of gradualism. Now is the time to make real the promises of democracy. Now is the time to rise from the dark and desolate valley of segregation to the sunlit path of racial justice. Now is the time to lift our nation from the quicksands of racial injustice to the solid rock of brotherhood. Now is the time to make justice a reality for all of God's children.
It would be fatal for the nation to overlook the urgency of the moment. This sweltering summer of the Negro's legitimate discontent will not pass until there is an invigorating autumn of freedom and equality. Nineteen sixty-three is not an end, but a beginning. And those who hope that the Negro needed to blow off steam and will now be content will have a rude awakening if the nation returns to business as usual. And there will be neither rest nor tranquility in America until the Negro is granted his citizenship rights. The whirlwinds of revolt will continue to shake the foundations of our nation until the bright day of justice emerges.
But there is something that I must say to my people, who stand on the warm threshold which leads into the palace of justice: In the process of gaining our rightful place, we must not be guilty of wrongful deeds. Let us not seek to satisfy our thirst for freedom by drinking from the cup of bitterness and hatred. We must forever conduct our struggle on the high plane of dignity and discipline. We must not allow our creative protest to degenerate into physical violence. Again and again, we must rise to the majestic heights of meeting physical force with soul force.
The marvelous new militancy which has engulfed the Negro community must not lead us to a distrust of all white people, for many of our white brothers, as evidenced by their presence here today, have come to realize that their destiny is tied up with our destiny. And they have come to realize that their freedom is inextricably bound to our freedom.
We cannot walk alone.
And as we walk, we must make the pledge that we shall always march ahead.
We cannot turn back.
There are those who are asking the devotees of civil rights, "When will you be satisfied?" We can never be satisfied as long as the Negro is the victim of the unspeakable horrors of police brutality. We can never be satisfied as long as our bodies, heavy with the fatigue of travel, cannot gain lodging in the motels of the highways and the hotels of the cities. We cannot be satisfied as long as the Negro's basic mobility is from a smaller ghetto to a larger one. We can never be satisfied as long as our children are stripped of their selfhood and robbed of their dignity by signs stating "for whites only." We cannot be satisfied as long as a Negro in Mississippi cannot vote and a Negro in New York believes he has nothing for which to vote. No, no, we are not satisfied, and we will not be satisfied until "justice rolls down like waters, and righteousness like a mighty stream."
I am not unmindful that some of you have come here out of great trials and tribulations. Some of you have come fresh from narrow jail cells. And some of you have come from areas where your quest -- quest for freedom left you battered by the storms of persecution and staggered by the winds of police brutality. You have been the veterans of creative suffering. Continue to work with the faith that unearned suffering is redemptive. Go back to Mississippi, go back to Alabama, go back to South Carolina, go back to Georgia, go back to Louisiana, go back to the slums and ghettos of our northern cities, knowing that somehow this situation can and will be changed.
Let us not wallow in the valley of despair, I say to you today, my friends.
And so even though we face the difficulties of today and tomorrow, I still have a dream. It is a dream deeply rooted in the American dream.
I have a dream that one day this nation will rise up and live out the true meaning of its creed: "We hold these truths to be self-evident, that all men are created equal."
I have a dream that one day on the red hills of Georgia, the sons of former slaves and the sons of former slave owners will be able to sit down together at the table of brotherhood.
I have a dream that one day even the state of Mississippi, a state sweltering with the heat of injustice, sweltering with the heat of oppression, will be transformed into an oasis of freedom and justice.
I have a dream that my four little children will one day live in a nation where they will not be judged by the color of their skin but by the content of their character.
I have a dream today!
I have a dream that one day, down in Alabama, with its vicious racists, with its governor having his lips dripping with the words of "interposition" and "nullification" -- one day right there in Alabama little black boys and black girls will be able to join hands with little white boys and white girls as sisters and brothers.
I have a dream today!
I have a dream that one day every valley shall be exalted, and every hill and mountain shall be made low, the rough places will be made plain, and the crooked places will be made straight; "and the glory of the Lord shall be revealed and all flesh shall see it together."
This is our hope, and this is the faith that I go back to the South with.
With this faith, we will be able to hew out of the mountain of despair a stone of hope. With this faith, we will be able to transform the jangling discords of our nation into a beautiful symphony of brotherhood. With this faith, we will be able to work together, to pray together, to struggle together, to go to jail together, to stand up for freedom together, knowing that we will be free one day.
And this will be the day -- this will be the day when all of God's children will be able to sing with new meaning:
My country 'tis of thee, sweet land of liberty, of thee I sing.
Land where my fathers died, land of the Pilgrim's pride,
From every mountainside, let freedom ring!
And if America is to be a great nation, this must become true.
And so let freedom ring from the prodigious hilltops of New Hampshire.
Let freedom ring from the mighty mountains of New York.
Let freedom ring from the heightening Alleghenies of
Pennsylvania.
Let freedom ring from the snow-capped Rockies of Colorado.
Let freedom ring from the curvaceous slopes of California.
But not only that:
Let freedom ring from Stone Mountain of Georgia.
Let freedom ring from Lookout Mountain of Tennessee.
Let freedom ring from every hill and molehill of Mississippi.
From every mountainside, let freedom ring.
And when this happens, when we allow freedom ring, when we let it ring from every village and every hamlet, from every state and every city, we will be able to speed up that day when all of God's children, black men and white men, Jews and Gentiles, Protestants and Catholics, will be able to join hands and sing in the words of the old Negro spiritual:
Free at last! Free at last!
Thank God Almighty, we are free at last!,

四、源程序清单

/**
 * @file WordFrequencyStatistics.c
 * @author SongBy
 * @brief 基于不同策略的英文单词的词频统计和检索系统
 * @date 2022/04/27
 * @version 0.0.1
 */
#include 
#include 
#include 
#include 

using namespace std;

#define OK 1
#define ERROR 0
#define OVERFLOW (-1)
#define TRUE 1
#define FALSE 0
#define MAXSIZE 5000/*最大表长，存储空间初始分配量*/

typedef int Status;/*Status是函数的类型，其值是函数结果状态代码，如OK等*/

/**
 * 环境路径
 * 即输入和输出的文件的保存位置
 */
string path = R"(C:桌面\WordFrequencyStatisticsWork\)";

/**
 * 单词类
 */
class Word {
private:
    /**
     * 单词名
     */
    string name;
    /**
     * 词频
     */
    int count;
public:
    /**
     * 无参构造函数
     * 将name初始化为空字符串
     * 将count初始化为0
     */
    Word() {
        this->name = "";
        this->count = 0;
    }

    /**
     * 得到单词名
     * @return 单词名
     */
    string getName() const {
        return name;
    }

    /**
     * 设置单词名和词频
     * 将单词名设置为传入字符串
     * 将词频设置为1
     * @param word 单词名
     */
    void setNameAndCount(const string &word) {
        this->name = word;
        this->count = 1;
    }

    /**
     * 得到词频
     * @return 词频
     */
    int getCount() const {
        return count;
    }

    /**
     * 当前单词词频+1
     */
    void CountAdd() {
        (this->count)++;
    }
};

/**
 * 顺序表类
 */
class SequenceList {
private:
    /**
     * 单词数组
     * 长度：MAXSIZE
     */
    Word words[MAXSIZE];
    /**
     * 单词个数
     */
    int length;
    /**
     * 表容量
     */
    int size;
public:
    /**
     * 构造函数
     * 构造顺序表
     * 表长置为MAXSIZE
     * 单词个数置为个数-1（即下标）
     */
    SequenceList() {
        this->size = MAXSIZE;
        this->length = -1;
    }

    /**
     * 按字典排序
     * 将顺序表内的单词按字典顺序排好序
     * @return OK
     */
    Status sortFromDictionary() {
        //标志符
        Status flag = TRUE;
        //临时Word对象
        Word temp;

        /*
         *  冒泡排序
         *  flag: 若发生排序，说明本次遍历仍存在单词按非顺序存放，下次排序仍需遍历扫描整表，flag置为TRUE，循环继续
         *        若未发生排序，说明本次遍历的所有单词均已按顺序排好，无需再遍历，flag置为False，循环结束
         */
        for (int i = 0; (i < length) && (flag == TRUE); i++) {
            //标志符置为FALSE
            flag = FALSE;

            for (int j = 0; j < (length - i); j++) {
                //判断两个单词是否为字典顺序出现，若不是则交换其顺序
                if (words[j].getName().compare(words[j + 1].getName()) > 0) {
                    temp = words[j];
                    words[j] = words[j + 1];
                    words[j + 1] = temp;

                    //若有排序发生，则重置标志符为TRUE
                    flag = TRUE;
                }
            }
        }
        return OK;
    }

    /**
     * 得到顺序表长度
     * @return 表长
     */
    int getLength() const {
        return length;
    }

    /**
     * 向表中输入一个单词
     * @param word 单词名
     * @return OK/ERROR
     */
    Status inputWord(const string &word) {
        //若表已满则提示
        if (length == size - 1) {
            cout << "表已满";
            return ERROR;
        }

        int i = 0;
        //将要查找的单词放在表尾的后继处，即作为哨兵置于末位
        words[length + 1].setNameAndCount(word);

        //带哨兵的顺序查找
        while (word != words[i].getName()) {
            i++;
        }

        //若查找到的单词下标不为哨兵，则说明表内存在该单词，将词频+1即可
        if (i <= length) {
            words[i].CountAdd();
            return OK;
        }

        //若找到的单词下标为哨兵，则说明输入的单词为新单词，将哨兵作为新加入的单词，并让单词个数+1
        length++;

        return OK;
    }

    /**
     * 按字典顺序得到所有单词的详情
     * @return 所有单词名+"    "+词频
     */
    string getAllWord() {
        //先进行排序
        sortFromDictionary();

        //定义字符串存储所有单词详情
        string allWords;

        //循环得到表内所有单词详情，将其拼接在字符串内
        for (int i = 0; i <= length; i++) {
            allWords += words[i].getName() + "    " + to_string(words[i].getCount()) + '\n';
        }

        //返回所有单词详情
        return allWords;
    }

    /**
     * 顺序查找单词
     * @param word 单词名
     * @return 词频/-1
     */
    int sequenceSearch(const string &word) {
        //若表已满则提示
        if (length == size - 1) {
            cout << "表已满";
            return ERROR;
        }

        int i = 0;
        //将要查找的单词放在表尾的后继处
        words[length + 1].setNameAndCount(word);

        //顺序查找单词
        while (word != words[i].getName()) {
            i++;
        }

        //若找到则返回词频
        if (i <= length) {
            return words[i].getCount();
        }

        //若未找到则返回-1
        return -1;
    }

    /**
     * 折半查找单词
     * @param word 单词名
     * @return 词频/-1
     */
    int binarySearch(const string &word) {
        //定义最低下标为记录首位，最高下标为记录末尾
        int low = 0, high = length, mid;

        //若查找未结束
        while (low <= high) {
            //折半，即查找值为范围内的中值
            mid = (low + high) / 2;

            if (word.compare(words[mid].getName()) < 0) {
                //若查找值比中值小，则最高下标调整到中位下标小一位
                high = mid - 1;
            } else if (word.compare(words[mid].getName()) > 0) {
                //若查找值比中值大，则最低下标调整到中位下标大一位
                low = mid + 1;
            } else {
                //若相等则说明mid即为查找到的位置，返回其词频
                return words[mid].getCount();
            }
        }

        //若未查找到则返回-1
        return -1;
    }
};

/**
 * 单链表结点类
 */
class LinkNode {
private:
    /**
     * 数据域
     */
    Word word;
    /**
     * 指针域
     */
    LinkNode *next;
public:
    /**
     * 无参构造函数
     * 构造一个空结点
     * 将其后继初始化为空指针
     */
    LinkNode() {
        this->next = nullptr;
    }

    /**
     * 构造函数
     * 构造一个新单词结点
     * 指针域初始化指向null
     * @param name 单词名
     */
    explicit LinkNode(const string &name) {
        this->word.setNameAndCount(name);
        this->next = nullptr;
    }

    /**
     * 得到结点的单词
     * @return 单词
     */
    Word getWord() const {
        return word;
    }

    /**
     * 单词词频+1
     */
    void addWordCount() {
        word.CountAdd();
    }

    /**
     * 得到该结点的后继
     * @return 后继结点指针
     */
    LinkNode *getNext() const {
        return next;
    }

    /**
     * 设置该结点的后继
     * @param nextNode 指向后继结点的指针
     */
    void setNext(LinkNode *nextNode) {
        this->next = nextNode;
    }
};

/**
 * 单链表类
 */
class LinkList {
private:
    /**
     * 头结点指针
     */
    LinkNode *head;
    /**
     * 链表长度，即单词个数
     */
    int length;
public:
    /**
     * 无参构造函数
     * 头结点初始化为空结点
     * 长度置为0
     */
    LinkList() {
        this->head = new LinkNode();
        this->length = 0;
    }

    /**
     * 得到所有单词的详情
     * @return 所有单词名 + "    " +词频
     */
    string getAllWord() {
        //先进行排序
        sortFromDictionary();

        //定义字符串存储所有单词详情
        string allWord;
        //定义指针指向第一个结点
        LinkNode *searchPtr = head->getNext();

        //循环得到表内所有单词详情，将其拼接在字符串内
        while (searchPtr != nullptr) {
            allWord += searchPtr->getWord().getName() + "    " + to_string(searchPtr->getWord().getCount()) + '\n';

            //指针迭代指向下一结点
            searchPtr = searchPtr->getNext();
        }

        //返回所有单词详情
        return allWord;
    }

    /**
     * 得到单链表内的单词个数，即表长
     * @return 单词个数
     */
    int getLength() const {
        return length;
    }

    /**
     * 向表中输入一个单词
     * @param word 单词名
     * @return OK
     */
    Status inputWord(const string &word) {
        //定义指针指向首元结点
        LinkNode *searchPtr = this->head->getNext();

        //遍历单链表
        while (searchPtr != nullptr) {
            //判断单词是否存在，若存在则词频+1
            if (searchPtr->getWord().getName() == word) {
                searchPtr->addWordCount();
                return OK;
            }

            //指针迭代指向下一结点
            searchPtr = searchPtr->getNext();
        }

        //若未找到，则用头插法新增单词，length+1
        auto *newWord = new LinkNode(word);
        newWord->setNext(head->getNext());
        head->setNext(newWord);
        length++;

        return OK;
    }

    /**
     * 按字典排序
     * @return OK
     */
    Status sortFromDictionary() {
        //定义指针ptr，ptr指针的前驱prePtr，尾指针tail指向已排好序的部分
        LinkNode *prePtr, *ptr, *tail = nullptr;

        //冒泡排序
        while (head->getNext() != tail) {
            //ptr指针指向首元结点
            ptr = head->getNext();
            //prePtr指针指向ptr指针的前驱
            prePtr = head;

            //若ptr指针未运行到已排好序的部分
            while (ptr->getNext() != tail) {
                //比较ptr与其后继的顺序
                if ((ptr->getWord().getName().compare(ptr->getNext()->getWord().getName())) > 0) {
                    //若非顺序则交换ptr与其后继的顺序
                    prePtr->setNext(ptr->getNext());
                    ptr->setNext(prePtr->getNext()->getNext());
                    prePtr->getNext()->setNext(ptr);
                } else {
                    //若顺序则ptr指针后移
                    ptr = ptr->getNext();
                }

                //prePtr指针随ptr指针后移
                prePtr = prePtr->getNext();
            }
            //尾指针指向已排好序的部分
            tail = ptr;
        }

        return OK;
    }

    /**
     * 顺序查找单词
     * @param word 单词名
     * @return 词频/-1
     */
    int sequenceSearch(const string &word) {
        //定义查找指针指向首元结点
        LinkNode *searchPrt = head->getNext();

        //循环扫描整表
        while (searchPrt != nullptr) {
            //若找到则返回其词频
            if (searchPrt->getWord().getName() == word) {
                return searchPrt->getWord().getCount();
            }

            //searchPtr指针迭代
            searchPrt = searchPrt->getNext();
        }

        //若未找到则返回-1
        return -1;
    }
};

/**
 * 哈希表类
 * 顺序表的开放地址法实现
 */
class HashTable {
private:
    /**
     * 哈希表存储单元
     */
    Word words[MAXSIZE];
    /**
     * 哈希表长度
     */
    int length;
    /**
     * 单词个数
     */
    int count;
public:
    /**
     * 无参构造函数
     * length初始化为表长
     * count初始化为0
     */
    HashTable() {
        this->length = MAXSIZE;
        this->count = 0;
    }

    /**
     * 哈希函数（散列函数）
     * 直接以单词传入，先将字符串按26进制转换为整数得到其key值
     * 再对其进行除留余数法
     * @param word 单词字符串
     * @return 地址
     */
    static int Hash(const string &word) {
        //定义变量存储地址
        int address = 0;

        //遍历单词的每个字符，得到其26进制的值并对其除留取余
        for (int i = 0; i < word.length(); i++) {
            address = (address * 26 + (int) word.at(i)) % 4999;
        }

        //返回其地址值
        return address;
    }

    /**
     * 得到表长
     * @return 表长
     */
    int getLength() const {
        return length;
    }

    /**
     * 得到单词个数
     * @return 单词数
     */
    int getCount() const {
        return count;
    }

    /**
     * 得到对应地址的单词
     * @param address 地址
     * @return 单词详情
     */
    Word getWord(int address) {
        return words[address];
    }

    /**
     * 开放地址法
     * 向表中输入一个单词
     * @param word 单词名
     * @return OK
     */
    Status inputWord(const string &word) {
        //计算单词的哈希地址
        int address = Hash(word);

        //若该地址内有单词
        while (!words[address].getName().empty()) {
            //判断地址内是否为该单词，若是则单词个数+1
            if (words[address].getName() == word) {
                words[address].CountAdd();
                return OK;
            }

            //若地址内不是该单词，说明地址冲突，将地址+1再迭代
            address = (address + 1) % length;
        }

        //若地址内无单词，说明该单词未出现过，在该地址内新增一个单词，单词个数+1
        words[address].setNameAndCount(word);
        count++;

        return OK;
    }

    /**
     * 开放定址法的哈希查找
     * @param word
     * @return 地址/-1
     */
    int searchHash(const string &word) {
        //计算单词的哈希地址
        int address = Hash(word);

        //循环判断地址内是否为该单词，若是则结束循环
        while (words[address].getName() != word) {
            //若不是则说明地址冲突，将地址+1再迭代
            address = (address + 1) % length;

            //若地址内无单词，说明该单词不存在与哈希表中，返回-1
            if (words[address].getName().empty() || address == Hash(word)) {
                return -1;
            }
        }

        //若找到则返回其地址值
        return address;
    }

    /**
     * 得到哈希表中的所有单词及其词频
     * @return 所有单词名 + 词频
     */
    string getAllWord() {
        //定义顺序表
        SequenceList L;

        //遍历整表将无序存放的所有单词及其词频存入顺序表内
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < words[i].getCount(); j++) {
                L.inputWord(words[i].getName());
            }
        }

        //在顺序表内进行排序并得到其有序的所有单词详情，并将其结果返回
        return L.getAllWord();
    }
};

/**
 * 哈希表类
 * 顺序表的链地址法实现
 */
class HashLinkTable {
private:
    /**
     * 哈希表存储单元
     */
    LinkNode head[MAXSIZE];
    /**
     * 哈希表长度
     */
    int length;
    /**
     * 单词个数
     */
    int count;
public:
    /**
     * 无参构造函数
     * 将哈希表长度初始化为表长
     * 将单词个数初始化为0
     */
    HashLinkTable() {
        this->length = MAXSIZE;
        this->count = 0;
    }

    /**
     * 哈希函数（散列函数）
     * 直接以单词传入，先将字符串按26进制转换为整数得到其key值
     * 再对其进行除留余数法
     * @param word 单词字符串
     * @return 地址
     */
    static int Hash(const string &word) {
        //定义变量存储地址
        int address = 0;

        //遍历单词的每个字符，得到其26进制的值并对其除留取余
        for (int i = 0; i < word.length(); i++) {
            address = (address * 26 + (int) word.at(i)) % 4999;
        }

        //返回计算得到的地址值
        return address;
    }

    /**
     * 得到表长
     * @return 表长
     */
    int getLength() const {
        return length;
    }

    /**
     * 得到单词个数
     * @return 单词数
     */
    int getCount() const {
        return count;
    }

    /**
     * 链地址法
     * 向表中输入一个单词
     * @param word 单词名
     * @return OK
     */
    Status inputWord(const string &word) {
        //计算该单词的地址值
        int address = Hash(word);
        //定义查找指针指向该地址下的首个单词
        LinkNode *searchPtr;
        searchPtr = head[address].getNext();

        //若查找指针扫描完该地址下的所有单词，说明未在该地址下找到该单词，结束循环
        while (searchPtr != nullptr) {
            //若查找指针找到单词，则让该单词词频+1
            if (searchPtr->getWord().getName() == word) {
                searchPtr->addWordCount();
                return OK;
            }

            //查找指针指向同地址的下一个单词
            searchPtr = searchPtr->getNext();
        }

        //未找到该单词则新增一个单词，以头插法插入该地址下，单词个数+1
        auto *tempWord = new LinkNode(word);
        tempWord->setNext(head[address].getNext());
        head[address].setNext(tempWord);
        count++;

        return OK;
    }

    /**
     * 链地址法的哈希查找
     * @param word
     * @return 地址/null
     */
    LinkNode *searchLinkHash(const string &word) {
        //计算该单词的地址值
        int address = Hash(word);
        //定义查找指针指向该地址下的首个单词
        LinkNode *searchPtr;
        searchPtr = head[address].getNext();

        //若查找指针扫描完该地址下的所有单词，说明未在该地址下找到该单词，结束循环
        while (searchPtr != nullptr) {
            //若查找指针找到该单词，返回其地址
            if (searchPtr->getWord().getName() == word) {
                return searchPtr;
            }

            //查找指针指向同地址的下一个单词
            searchPtr = searchPtr->getNext();
        }

        //未找到则返回空指针
        return nullptr;
    }

    /**
     * 得到哈希表中的所有单词及其词频
     * @return 所有单词名 + 词频
     */
    string getAllWord() {
        //定义顺序表
        SequenceList L;
        //定义结点指针
        LinkNode *ptr;

        //遍历整表将无序存放的所有单词及其词频存入顺序表内
        for (int i = 0; i < length; i++) {
            //ptr指针指向下一个地址的第一个单词
            ptr = head[i].getNext();
            //若该地址下还有单词
            while (ptr != nullptr) {
                //将该单词及其词频存入顺序表
                for (int j = 0; j < ptr->getWord().getCount(); j++) {
                    L.inputWord(ptr->getWord().getName());
                }

                //ptr指针指向同地址下的下一个单词
                ptr = ptr->getNext();
            }
        }

        //在顺序表内进行排序并得到其有序的所有单词详情，并将其结果返回
        return L.getAllWord();
    }
};

/**
 * 树结点类
 */
class TreeNode {
private:
    /**
     * 单词数据
     */
    Word word;
    /**
     * 左子树指针
     */
    TreeNode *leftChild;
    /**
     * 右子树指针
     */
    TreeNode *rightChild;
public:
    /**
     * 无参构造函数
     * 单词初始化默认为空字符串
     * 初始化结点左子树指向null
     * 初始化结点右子树指向null
     */
    TreeNode() {
        this->leftChild = nullptr;
        this->rightChild = nullptr;
    }

    /**
     * 构造函数
     * @param word 单词
     * 设置单词为输入单词
     * 初始化结点左子树指向null
     * 初始化结点右子树指向null
     */
    explicit TreeNode(const string &word) {
        this->word.setNameAndCount(word);
        this->leftChild = nullptr;
        this->rightChild = nullptr;
    }

    /**
     * 得到结点的单词
     * @return 单词
     */
    Word getWord() const {
        return word;
    }

    /**
     * 单词词频+1
     */
    void addWordCount() {
        word.CountAdd();
    }

    /**
     * 得到左子树的根结点
     * @return 左子树根结点
     */
    TreeNode *getLeftChild() const {
        return leftChild;
    }

    /**
     * 设置左子树的根节点
     * @param leftNode 左子树根节点
     */
    void setLeftChild(TreeNode *leftNode) {
        this->leftChild = leftNode;
    }

    /**
     * 得到右子树根节点
     * @return 右子树根节点
     */
    TreeNode *getRightChild() const {
        return rightChild;
    }

    /**
     * 设置右子树的根节点
     * @param leftNode 右子树根节点
     */
    void setRightChild(TreeNode *rightNode) {
        this->rightChild = rightNode;
    }
};

/**
 * 二叉排序树类
 */
class BinarySortTree {
private:
    /**
     * 根节点
     */
    TreeNode *root;
    /**
     * 单词个数
     */
    int count;
public:
    /**
     * 构造函数
     * 根节点指向null
     * 单词个数初始化为0
     */
    BinarySortTree() {
        this->root = nullptr;
        this->count = 0;
    };

    /**
     * 得到根结点
     * @return 根结点地址
     */
    TreeNode *getRoot() const {
        return root;
    }

    /**
     * 得到单词总数
     * @return 单词数
     */
    int getCount() const {
        return count;
    }

    /**
     * 向二叉排序树内输入一个单词
     * @param word 单词
     * @return OK
     */
    Status inputWord(const string &word) {
        //定义查找指针
        TreeNode *find = nullptr;

        //在树内查找该单词，若找到，find指针指向该单词结点，若未找到，find指针指向其插入位置的父结点
        if (searchTree(word, root, find, nullptr) == FALSE) {
            //若树内未找到该单词，说明输入的是一个新单词，新增一个单词结点，单词个数+1
            auto node = new TreeNode(word);
            count++;

            if (find == nullptr) {
                //若树为空，则根节点为新单词
                root = node;
            } else if (word.compare(find->getWord().getName()) < 0) {
                //若树不为空，且该单词顺序在其find指向的单词前，则将其作为find指针指向结点的左子树插入树内
                find->setLeftChild(node);
            } else {
                //若树不为空，且该单词顺序在其find指向的单词后，则将其作为find指针指向结点的右子树插入树内
                find->setRightChild(node);
            }
        } else {
            //若在树内找到该单词，则该单词的词频+1
            find->addWordCount();
        }

        return OK;
    }

    /**
     * 二叉排序树内递归查找结点
     * @param word 要查找的单词
     * @param node 要查找的树的根结点
     * @param find 查找结果指针
     * @param father 查找的树的根结点的父结点
     * @return TRUE / FALSE
     */
    static Status searchTree(const string &word, TreeNode *node, TreeNode *&find, TreeNode *father) {
        if (node == nullptr) {
            //若根节点为null，说明未找到，find指向该根结点的父结点，即与查找单词最接近的单词结点
            find = father;
            //返回FALSE表示查找失败
            return FALSE;
        } else if (word == node->getWord().getName()) {
            //若找到，find指向该单词结点
            find = node;
            //返回TRUE表示查找成功
            return TRUE;
        } else if (word.compare(node->getWord().getName()) < 0) {
            //若根结点的单词顺序在查找单词之前，则在其左子树内继续查找
            return searchTree(word, node->getLeftChild(), find, node);
        } else if (word.compare(node->getWord().getName()) > 0) {
            //若根结点的单词顺序在查找单词之前，则在其右子树内继续查找
            return searchTree(word, node->getRightChild(), find, node);
        }
    }

    /**
     * 传入一棵树的根结点，中序遍历法递归获取这棵树上的所有单词详情
     * @param node 根结点
     * @return 这棵树的所有单词 + "    " + 词频
     */
    static string getTreeWord(TreeNode *node) {
        if (node == nullptr) {
            //若根节点为空，则该树已查找完毕，返回空字符串
            return "";
        }

        //获取其左子树内的所有单词详情（顺序先于该单词），获取该单词的详情，获取其右子树内的所有单词详情（顺序后于该单词）
        return getTreeWord(node->getLeftChild()) + node->getWord().getName() + "    " +
               to_string(node->getWord().getCount()) + '\n' + getTreeWord(node->getRightChild());
    }

    /**
     * 得到该实例的树上的所有单词的详情
     * @return 所有单词名 + "    " +词频
     */
    string getAllWord() {
        return getTreeWord(root);
    }
};

/**
 * 计时器类
 * 单位：微秒
 */
class Timer {
private:
    /**
     * 频率
     * 按其默认方法初始化
     */
    LARGE_INTEGER frequency{};
    /**
     * 开始时间
     * 按其默认方法初始化
     */
    LARGE_INTEGER startTime{};
    /**
     * 使用时间
     */
    long long useTime;
public:
    /**
     * 构造方法
     * 使用时间初始化为0
     * 频率初始化为微秒精度
     */
    Timer() {
        this->useTime = 0;
        QueryPerformanceFrequency(&frequency);
    }

    /**
     * 开始计时
     * 使用时间重置为0
     * 获得开始时间
     */
    void start() {
        useTime = 0;
        QueryPerformanceCounter(&startTime);
    }

    /**
     * 结束及时
     * 记录使用时间
     */
    void end() {
        //定义结束时间
        LARGE_INTEGER endTime;
        //获得结束时间
        QueryPerformanceCounter(&endTime);

        /*
         * 使用时间 = 结束时间 - 开始时间
         * 乘1000000是将使用时间精度从毫秒放大到微秒，以得到精确计时
         * +=是为多次计时准备
         */
        useTime += (endTime.QuadPart - startTime.QuadPart) * 1000000 / frequency.QuadPart;
    }

    /**
     * 得到花费时间
     * @return 花费时间
     */
    double spendTime() const {
        return static_cast<double>(useTime);
    }
};

/**
 * 工具类
 */
class Tool {
private:
    /**
     * 计时器
     */
    Timer timer;
public:
    /**
     * 构造方法
     * timer初始化
     */
    Tool() {
        this->timer = *new Timer();
    }

    /**
     * 主菜单类
     *  *** 作：
     *      线性表结构菜单
     *      二叉树结构菜单
     *      哈希表结构菜单
     *      退出系统
     */
    void mainMenu() {
        system("cls");
        cout << "/*********基于不同策略的英文单词的词频统计和检索系统*********/" << endl;
        cout << "/*******主菜单*******/" << endl;
        cout << "1、基于线性表查找" << endl;
        cout << "2、基于二叉树的查找" << endl;
        cout << "3、基于哈希表的查找" << endl;
        cout << "0.退出系统" << endl;
        cout << "请输入你的 *** 作：";

        switch (operationalValidity(0, 3)) {
            case 1:
                listMenu();
                break;
            case 2:
                treeMenu();
                break;
            case 3:
                hashMenu();
                break;
            case 0:
                cout << "/***谢谢使用***/" << endl;
                exit(0);
        }

    }

    /**
     * 线性表结构菜单
     *  *** 作：
     *      顺序查找 *** 作菜单
     *      顺序表折半查找 *** 作
     *      回到主菜单
     */
    void listMenu() {
        system("cls");
        cout << "/*******基于不同策略的英文单词的词频统计和检索系统*******/" << endl;
        cout << "/*****基于线性表查找的菜单*****/" << endl;
        cout << "1、基于线性表的顺序查找" << endl;
        cout << "2、基于顺序表的折半查找" << endl;
        cout << "0.回到上一层菜单" << endl;
        cout << "请输入你的 *** 作：";

        switch (operationalValidity(0, 2)) {
            case 1:
                sequenceMenu();
                break;
            case 2:
                binarySearchFromSequenceList();
                break;
            case 0:
                mainMenu();
                break;

        }
    }

    /**
     * 顺序查找 *** 作菜单
     *  *** 作：
     *      顺序表顺序查找 *** 作
     *      线性表顺序查找 *** 作
     *      回到线性表结构菜单
     */
    void sequenceMenu() {
        system("cls");
        cout << "/*******基于不同策略的英文单词的词频统计和检索系统*******/" << endl;
        cout << "/***基于线性表的顺序查找菜单***/" << endl;
        cout << "1、基于顺序表的顺序查找" << endl;
        cout << "2、基于单链表的顺序查找" << endl;
        cout << "0.回到上一层菜单" << endl;
        cout << "请输入你的 *** 作：";

        switch (operationalValidity(0, 2)) {
            case 1:
                sequenceSearchFromSequenceList();
                break;
            case 2:
                sequenceSearchFromLinkList();
                break;
            case 0:
                listMenu();
                break;

        }
    }

    /**
     * 二叉树结构菜单
     *  *** 作：
     *      二叉排序树查找 *** 作
     *      回到主菜单
     */
    void treeMenu() {
        system("cls");
        cout << "/*******基于不同策略的英文单词的词频统计和检索系统*******/" << endl;
        cout << "/***基于二叉树的查找菜单***/" << endl;
        cout << "1、基于二叉排序树查找" << endl;
        cout << "0.回到上一层菜单" << endl;
        cout << "请输入你的 *** 作：";

        switch (operationalValidity(0, 1)) {
            case 1:
                searchBinarySortTree();
                break;
            case 0:
                mainMenu();
                break;

        }
    }

    /**
     * 哈希表结构菜单
     *  *** 作：
     *      哈希表开发定址法查找 *** 作
     *      哈希表链地址法查找 *** 作
     *      回到主菜单
     */
    void hashMenu() {
        system("cls");
        cout << "/*******基于不同策略的英文单词的词频统计和检索系统*******/" << endl;
        cout << "/*****基于哈希表查找的菜单*****/" << endl;
        cout << "1、基于哈希表的开放定址法查找" << endl;
        cout << "2、基于哈希表的链地址法查找" << endl;
        cout << "0.回到上一层菜单" << endl;
        cout << "请输入你的 *** 作：";

        switch (operationalValidity(0, 2)) {
            case 1:
                openAddressingSearchFromHashTable();
                break;
            case 2:
                linkAddressingSearchFromHashLinkTable();
                break;
            case 0:
                mainMenu();
                break;

        }
    }


    /**
     *  *** 作合法性检查
     * @param low  *** 作下限
     * @param high  *** 作上限
     * @return 正确的 *** 作
     */
    static int operationalValidity(int low, int high) {
        //定义变量存储用户 *** 作
        int operational;

        do {
            //从键盘输入一个 *** 作
            cin >> operational;

            //判断是否为上下限内的整数 *** 作之一，若是则返回该 *** 作
            for (int i = low; i <= high; i++) {
                if (i == operational) {
                    return i;
                }
            }

            //若不是则继续循环要求重新输入
            cout << "输入不正确，请重新输入：";
        } while (TRUE);
    }

    /**
     * 读入文件并将其拆分为单词，传入结构体中
     * 函数模板，根据传入的结构体来确定使用哪种结构
     * @tparam Structure 结构体类型
     * @param str 结构体名
     * @return OK
     */
    template<typename Structure>
    Status fileInputWords(Structure &str) {
        //文件输入流指针
        fstream filePtr;
        //打开路径下的文件
        filePtr.open(path + "InFile.txt", ios::in);
        //判断是否成功打开文件，若打开失败则退出程序
        if (!filePtr.is_open()) {
            cout << "文件打开失败！" << endl;
            exit(OVERFLOW);
        }

        //定义字符变量
        char c;
        //定义单词字符串变量
        string word;

        //循环读取文件中的字符
        while ((c = (char) filePtr.get()) != EOF) {
            if ((c >= 'a' && c <= 'z') || c == '\'') {
                //若字符为a~z，则将当前字符加入到单词字符串尾
                word += c;
            } else if ((c >= 'A' && c <= 'Z')) {
                //若字符为A~Z，则将其转化为小写字符再加入到单词字符串尾
                c += 32;
                word += c;
            } else if (c == ' ' || c == ',' || c == '.' || c == '-' || c == '!' || c == '?' || c == ';' || c == ':' ||
                       c == '\n') {
                //若字符为分隔符，且字符串内有单词
                if (!word.empty()) {
                    //将该单词传入结构体中
                    str.inputWord(word);
                    //清空字符串中的单词
                    word.clear();
                }
            }
        }

        cout << "文件读入完毕" << endl;
        //关闭文件
        filePtr.close();
        return OK;
    }

    /**
     * 将单词及其频率按字典顺序输出到文件中
     * @tparam Structure 结构体类型
     * @param fileName 路径下的文件名
     * @param str 结构体名
     * @return OK
     */
    template<typename Structure>
    Status wordsOutputFile(const string &fileName, Structure &str) {
        //文件输出流指针
        ofstream filePtr;
        //打开指定路径下的文件
        filePtr.open(fileName, ios::out);
        //判断是否成功打开文件
        if (!filePtr.is_open()) {
            cout << "文件打开失败！" << endl;
            exit(OVERFLOW);
        }

        //写入结构体内的所有单词和词频信息
        filePtr << str.getAllWord() << endl;

        cout << "文件写入完成" << endl;
        //关闭文件
        filePtr.close();
        return OK;
    }

    /**
     * 顺序表的顺序查找 *** 作实现
     */
    void sequenceSearchFromSequenceList() {
        //定义字符串变量存储单词
        string word;
        //定义变量存储单词词频
        int count;
        //构造顺序表
        SequenceList SL;
        cout << "正在读入文件..." << endl;
        //读入文件中的单词并存储到顺序表中
        fileInputWords(SL);

        //得到表长为最后一个单词的下标+1
        auto length = (double) SL.getLength() + 1;

        //循环查找 *** 作直到用户退出
        do {
            cout << "输入0结束查找，请输入要检索的单词：";
            //从键盘接受用户要查找的单词
            cin >> word;
            //若用户选择退出则结束循环
            if (word == "0") {
                break;
            }

            //开始计时
            timer.start();
            //顺序查找单词
            count = SL.sequenceSearch(word);
            //结束计时
            timer.end();

            //根据词频信息是否为-1判断查询结果
            if (count != -1) {
                cout << "查找成功！" << endl;
                //输出单词信息
                cout << "单词：" << word << "\t，词频：" << count << endl;
                /*
                 * 输出平均查找长度和花费时间
                 * 顺序查找的平均查找长度为：(表长+1)/2
                 */
                cout << "平均查找长度：" << (length + 1) / 2 << "\t，检索花费时间：" << timer.spendTime() << "微秒" << endl;
            } else {
                cout << "查找失败！" << endl;
                cout << "单词：" << word << "不存在：" << endl;
            }
        } while (TRUE);

        //设置输出文件路径
        string fileName = path + "OutFile1.txt";
        cout << "将所有单词及其频率按照词典顺序写入文本文件OutFile1.txt中..." << endl;
        //写入词频统计信息
        wordsOutputFile(fileName, SL);
        //等待用户 *** 作
        cout << "按任意键返回主菜单..." << endl;
        system("pause");
        //返回主菜单
        mainMenu();
    }

    /**
     * 单链表的顺序查找 *** 作实现
     */
    void sequenceSearchFromLinkList() {
        //定义字符串变量存储单词
        string word;
        //定义变量存储单词词频
        int count;
        //构造单链表
        LinkList LL;
        cout << "正在读入文件..." << endl;
        //读入文件中的单词并存储到单链表中
        fileInputWords(LL);

        //得到表长
        auto length = (double) LL.getLength();

        //循环查找 *** 作直到用户退出
        do {
            cout << "输入0结束查找，请输入要检索的单词：";
            //从键盘接受用户要查找的单词
            cin >> word;
            //若用户选择退出则结束循环
            if (word == "0") {
                break;
            }

            //开始计时
            timer.start();
            //顺序查找单词
            count = LL.sequenceSearch(word);
            //结束计时
            timer.end();

            //根据词频信息是否为-1判断查询结果
            if (count != -1) {
                cout << "查找成功！" << endl;
                //输出单词信息
                cout << "单词：" << word << "\t，词频：" << count << endl;
                /*
                 * 输出平均查找长度和花费时间
                 * 顺序查找的平均查找长度为：(表长+1)/2
                 */
                cout << "平均查找长度：" << (length + 1) / 2 << "\t，检索花费时间：" << timer.spendTime() << "微秒" << endl;
            } else {
                cout << "查找失败！" << endl;
                cout << "单词：" << word << "不存在：" << endl;
            }
        } while (TRUE);

        //设置输出文件路径
        string fileName = path + "OutFile2.txt";
        cout << "将所有单词及其频率按照词典顺序写入文本文件OutFile2.txt中..." << endl;
        //写入词频统计信息
        wordsOutputFile(fileName, LL);
        //等待用户 *** 作
        cout << "按任意键返回主菜单..." << endl;
        system("pause");
        //返回主菜单
        mainMenu();
    }

    /**
     * 顺序表的折半查找 *** 作实现
     */
    void binarySearchFromSequenceList() {
        //定义字符串变量存储单词
        string word;
        //定义变量存储单词词频
        int count;
        //构造顺序表
        SequenceList SL;
        cout << "正在读入文件..." << endl;
        //读入文件中的单词并存储到顺序表中
        fileInputWords(SL);

        //得到表长为最后一个单词的下标+1
        auto length = (double) SL.getLength() + 1;

        //将顺序表内的单词按字典排序
        SL.sortFromDictionary();

        //循环查找 *** 作直到用户退出
        do {
            cout << "输入0结束查找，请输入要检索的单词：";
            //从键盘接受用户要查找的单词
            cin >> word;
            //若用户选择退出则结束循环
            if (word == "0") {
                break;
            }

            //开始计时
            timer.start();
            //折半查找单词
            count = SL.binarySearch(word);
            //结束计时
            timer.end();

            //根据词频信息是否为-1判断查询结果
            if (count != -1) {
                cout << "查找成功！" << endl;
                //输出单词信息
                cout << "单词：" << word << "\t，词频：" << count << endl;
                /*
                 * 输出平均查找长度和花费时间
                 * 折半查找的平均查找长度为：log2(表长+1)-1
                 */
                cout << "平均查找长度：" << log(length + 1) / log(2) - 1 << "\t，检索花费时间：" << timer.spendTime() << "微秒"
                     << endl;
            } else {
                cout << "查找失败！" << endl;
                cout << "单词：" << word << "不存在" << endl;
            }
        } while (TRUE);

        //设置输出文件路径
        string fileName = path + "OutFile3.txt";
        cout << "将所有单词及其频率按照词典顺序写入文本文件OutFile3.txt中..." << endl;
        //写入词频统计信息
        wordsOutputFile(fileName, SL);
        //等待用户 *** 作
        cout << "按任意键返回主菜单..." << endl;
        system("pause");
        //返回主菜单
        mainMenu();
    }

    /**
     * 二叉排序树查找 *** 作实现
     */
    void searchBinarySortTree() {
        //定义字符串变量存储单词
        string word;
        //定义变量存储单词词频
        int count;
        //申请结点指针，父结点指针
        TreeNode *find, *father;
        //构造二叉树
        BinarySortTree BST;
        cout << "正在读入文件..." << endl;
        //读入文件中的单词并存储到二叉树中
        fileInputWords(BST);

        //得到二叉树内的单词总数
        auto length = (double) BST.getCount();

        //循环查找 *** 作直到用户退出
        do {
            cout << "输入0结束查找，请输入要检索的单词：";
            //从键盘接受用户要查找的单词
            cin >> word;
            //若用户选择退出则结束循环
            if (word == "0") {
                break;
            }

            //开始计时
            timer.start();
            if (BinarySortTree::searchTree(word, BST.getRoot(), find, father) == TRUE) {
                //若查找成功，结束计时
                timer.end();

                //得到单词词频
                count = find->getWord().getCount();

                cout << "查找成功！" << endl;
                //输出单词信息
                cout << "单词：" << word << "\t，词频：" << count << endl;
                /*
                 * 输出平均查找长度和花费时间
                 * 二叉排序树查找的平均查找长度为：(每层高度*该层元素个数)之和 / 节点总数；十分接近于折半查找的平均查找长度
                 */
                cout << "平均查找长度：" << log(length + 1) / log(2) - 1 << "\t，检索花费时间：" << timer.spendTime() << "微秒" << endl;
            } else {
                //查找失败
                cout << "查找失败！" << endl;
                cout << "单词：" << word << "不存在：" << endl;
            }
        } while (TRUE);

        //设置输出文件路径
        string fileName = path + "OutFile4.txt";
        cout << "将所有单词及其频率按照词典顺序写入文本文件OutFile4.txt中..." << endl;
        //写入词频统计信息
        wordsOutputFile(fileName, BST);
        //等待用户 *** 作
        cout << "按任意键返回主菜单..." << endl;
        system("pause");
        //返回主菜单
        mainMenu();
    }

    /**
     * 哈希表的开放定址法查找 *** 作实现
     */
    void openAddressingSearchFromHashTable() {
        //定义字符串变量存储单词
        string word;
        //定义变量存储单词词频
        int count;
        //构造哈希表
        HashTable HT;
        cout << "正在读入文件..." << endl;
        //读入文件中的单词并存储到哈希表中
        fileInputWords(HT);

        //定义装填因子a为哈希表内元素总数/哈希表表长
        double a = (double) HT.getCount() / HT.getLength();

        //循环查找 *** 作直到用户退出
        do {
            cout << "输入0结束查找，请输入要检索的单词：";
            //从键盘接受用户要查找的单词
            cin >> word;
            //若用户选择退出则结束循环
            if (word == "0") {
                break;
            }

            //开始计时
            timer.start();
            //得到查找单词的词频
            count = HT.getWord(HT.searchHash(word)).getCount();
            //结束计时
            timer.end();

            //根据词频信息判断是否查找成功
            if (count != 0) {
                cout << "查找成功！" << endl;
                //输出单词信息
                cout << "单词：" << word << "\t，词频：" << count << endl;
                /*
                 * 输出平均查找长度和花费时间
                 * 哈希表开放定址法的平均查找长度为：(1 + 1 / (1 - 元素数/表长)) / 2
                 */
                cout << "平均查找长度：" << (1 + 1 / (1 - a)) / 2 << "\t，检索花费时间：" << timer.spendTime() << "微秒" << endl;
            } else {
                cout << "查找失败！" << endl;
                cout << "单词：" << word << "不存在：" << endl;
            }
        } while (TRUE);

        //设置输出文件路径
        string fileName = path + "OutFile5.txt";
        cout << "将所有单词及其频率按照词典顺序写入文本文件OutFile5.txt中..." << endl;
        //写入词频统计信息
        wordsOutputFile(fileName, HT);
        //等待用户 *** 作
        cout << "按任意键返回主菜单..." << endl;
        system("pause");
        //返回主菜单
        mainMenu();
    }

    /**
     * 哈希表的链地址法查找 *** 作实现
     */
    void linkAddressingSearchFromHashLinkTable() {
        //定义字符串变量存储单词
        string word;
        //定义链结点指针接收查找结果
        LinkNode *ptr;
        //构造哈希表
        HashLinkTable HLT;
        cout << "正在读入文件..." << endl;
        //读入文件中的单词并存储到哈希表中
        fileInputWords(HLT);

        //定义装填因子a为哈希表内元素总数/哈希表表长
        double a = (double) HLT.getCount() / HLT.getLength();

        //循环查找 *** 作直到用户退出
        do {
            cout << "输入0结束查找，请输入要检索的单词：";
            //从键盘接受用户要查找的单词
            cin >> word;
            //若用户选择退出则结束循环
            if (word == "0") {
                break;
            }

            //开始计时
            timer.start();
            //ptr为查找结果
            ptr = HLT.searchLinkHash(word);
            //结束计时
            timer.end();

            //根据ptr的指向判断查找结果
            if (ptr != nullptr) {
                cout << "查找成功！" << endl;
                //输出单词信息
                cout << "单词：" << word << "\t，词频：" << ptr->getWord().getCount() << endl;
                /*
                 * 输出平均查找长度和花费时间
                 * 哈希表链地址法的平均查找长度为：(1 + (元素数/表长) / 2)
                 */
                cout << "平均查找长度：" << 1 + a / 2 << "\t，检索花费时间：" << timer.spendTime() << "微秒" << endl;
            } else {
                cout << "查找失败！" << endl;
                cout << "单词：" << word << "不存在：" << endl;
            }
        } while (TRUE);

        //设置输出文件路径
        string fileName = path + "OutFile6.txt";
        cout << "将所有单词及其频率按照词典顺序写入文本文件OutFile6.txt中..." << endl;
        //写入词频统计信息
        wordsOutputFile(fileName, HLT);
        //等待用户 *** 作
        cout << "按任意键返回主菜单..." << endl;
        system("pause");
        //返回主菜单
        mainMenu();
    }

};

/**
 * 主函数
 * @return 正常结束：0 / 异常结束：其他值
 */
int main() {
    //定义工具类对象
    Tool run;
    //使用工具类对象启动主菜单
    run.mainMenu();
}

五、运行结果 5.1 程序运行结果

5.2 文件输出结果

'tis    1
a    37
able    8
again    2
ago    1
ahead    1
alabama    3
all    7
alleghenies    1
allow    2
almighty    1
alone    1
also    1
always    1
am    2
america    5
american    4
an    4
and    53
architects    1
are    8
areas    1
as    20
asking    1
at    4
autumn    1
awakening    1
back    9
bad    2
bank    1
bankrupt    1
basic    1
battered    1
be    33
beacon    1
beautiful    1
become    1
been    2
beginning    1
believe    2
believes    1
bitterness    1
black    4
blow    1
bodies    1
bound    1
boys    2
bright    1
brotherhood    3
brothers    2
brutality    2
business    1
but    6
by    8
california    1
came    2
can    4
cannot    6
capital    1
capped    1
captivity    1
carolina    1
cash    2
catholics    1
cells    1
chains    1
changed    1
character    1
check    5
children    5
cities    2
citizens    1
citizenship    1
city    1
civil    1
color    2
colorado    1
come    10
community    1
concerned    1
condition    1
conduct    1
constitution    1
content    2
continue    2
cooling    1
corners    1
country    1
created    1
creative    2
creed    1
crippled    1
crooked    1
cup    1
curvaceous    1
dark    1
day    12
daybreak    1
declaration    1
decree    1
deeds    1
deeply    1
defaulted    1
degenerate    1
demand    1
democracy    1
demonstration    1
desolate    1
despair    2
destiny    2
devotees    1
died    1
difficulties    1
dignity    2
discipline    1
discontent    1
discords    1
discrimination    1
distrust    1
down    4
dramatize    1
dream    11
drinking    1
dripping    1
drug    1
emancipation    1
emerges    1
end    2
engage    1
engulfed    1
equal    1
equality    1
even    2
every    10
evidenced    1
evident    1
exalted    1
exile    1
face    1
faith    5
fall    1
fatal    1
fathers    1
fatigue    1
fierce    1
finds    1
five    1
flames    1
flesh    1
for    9
force    2
forever    1
former    2
foundations    1
four    1
free    5
freedom    20
fresh    1
friends    1
from    18
funds    2
gain    1
gaining    1
gentiles    1
georgia    3
ghetto    1
ghettos    1
girls    2
give    1
given    1
glory    1
go    9
god    1
god's    3
governor    1
gradualism    1
granted    1
great    5
greatest    1
guaranteed    1
guilty    1
had    1
hallowed    1
hamlet    1
hampshire    1
hands    2
happens    1
happiness    1
happy    1
has    5
hatred    1
have    17
having    1
he    1
heat    2
heavy    1
heightening    1
heights    1
heir    1
her    1
here    3
hew    1
high    1
highways    1
hill    2
hills    1
hilltops    1
himself    1
his    3
history    2
hold    1
honoring    1
hope    4
horrors    1
hotels    1
hundred    4
i    15
if    2
in    22
independence    1
inextricably    1
injustice    3
insofar    1
instead    1
insufficient    2
interposition    1
into    4
invigorating    1
is    23
island    1
it    6
its    3
jail    2
jangling    1
jews    1
join    3
joyous    1
judged    1
justice    8
knowing    2
land    4
languished    1
larger    1
last    3
later    4
lead    1
leads    1
left    1
legitimate    1
let    13
liberty    2
life    2
lift    1
light    1
like    2
lips    1
little    3
live    2
lives    1
lodging    1
lonely    1
long    6
lookout    1
lord    1
louisiana    1
low    1
luxury    1
made    3
magnificent    1
majestic    1
make    3
manacles    1
many    1
march    1
marked    1
marvelous    1
material    1
meaning    2
meeting    1
men    6
midst    1
mighty    2
militancy    1
millions    1
mississippi    4
mobility    1
molehill    1
moment    1
momentous    1
motels    1
mountain    4
mountains    1
mountainside    2
must    8
my    5
narrow    1
nation    10
nation's    1
needed    1
negro    13
negro's    2
neither    1
never    3
new    5
night    1
nineteen    1
no    3
nor    1
northern    1
not    13
note    3
nothing    1
now    6
nullification    1
oasis    1
obligation    1
obvious    1
ocean    1
of    99
off    2
old    1
on    5
one    13
only    2
opportunity    1
oppression    1
or    1
our    17
out    3
overlook    1
own    1
owners    1
palace    1
pass    1
path    1
pennsylvania    1
people    3
persecution    1
physical    2
pilgrim's    1
place    1
places    2
plain    1
plane    1
pledge    1
police    2
poverty    1
pray    1
presence    1
pride    1
process    1
proclamation    1
prodigious    1
promise    1
promises    1
promissory    2
prosperity    1
protest    1
protestants    1
pursuit    1
quest    2
quicksands    1
racial    2
racists    1
real    1
reality    1
realize    2
red    1
redemptive    1
refuse    2
remind    1
republic    1
rest    1
returns    1
revealed    1
revolt    1
riches    1
right    1
righteousness    1
rightful    1
rights    3
ring    12
rise    3
robbed    1
rock    1
rockies    1
rolls    1
rooted    1
rough    1
rude    1
sacred    1
sadly    1
satisfied    8
satisfy    1
say    2
score    1
seared    1
security    1
see    1
seek    1
segregation    2
self    1
selfhood    1
sense    1
shadow    1
shake    1
shall    5
shameful    1
signed    1
signing    1
signs    1
sing    3
sisters    1
sit    1
situation    1
sixty    1
skin    1
slave    1
slaves    2
slopes    1
slums    1
smaller    1
snow    1
so    4
society    1
solid    1
some    3
somehow    1
something    1
sons    2
soul    1
south    2
speed    1
spiritual    1
spot    1
staggered    1
stand    3
state    3
stating    1
steam    1
still    4
stone    2
storms    1
straight    1
stream    1
stripped    1
struggle    2
suffering    2
summer    1
sunlit    1
sweet    1
sweltering    3
symbolic    1
symphony    1
table    1
take    1
tennessee    1
thank    1
that    24
the    103
thee    2
their    7
there    6
these    1
they    3
thirst    1
this    20
those    2
though    1
three    1
threshold    1
tied    1
time    5
to    59
today    9
together    7
tomorrow    1
tranquility    1
tranquilizing    1
transform    1
transformed    1
travel    1
trials    1
tribulations    1
true    2
truths    1
turn    1
unalienable    1
unearned    1
unmindful    1
unspeakable    1
until    4
up    4
upon    1
urgency    2
us    4
usual    1
valley    3
vast    1
vaults    1
veterans    1
vicious    1
victim    1
village    1
violence    1
vote    2
walk    2
wallow    1
warm    1
was    2
waters    1
we    30
we've    3
well    1
were    1
what    1
when    7
where    3
which    5
whirlwinds    1
white    6
whites    1
who    4
whose    1
will    27
winds    1
with    16
withering    1
words    3
work    2
would    2
wrongful    1
wrote    1
years    5
yes    1
york    2
you    8
your    1

六、关键算法 6.1 顺序表的顺序查找

/**
 * 顺序查找单词
 * @param word 单词名
 * @return 词频/-1
 */
int sequenceSearch(const string &word) {
    //若表已满则提示
    if (length == size - 1) {
        cout << "表已满";
        return ERROR;
    }

    int i = 0;
    //将要查找的单词放在表尾的后继处
    words[length + 1].setNameAndCount(word);

    //顺序查找单词
    while (word != words[i].getName()) {
        i++;
    }

    //若找到则返回词频
    if (i <= length) {
        return words[i].getCount();
    }

    //若未找到则返回-1
    return -1;
}

6.2 单链表的顺序查找

/**
 * 顺序查找单词
 * @param word 单词名
 * @return 词频/-1
 */
int sequenceSearch(const string &word) {
    //定义查找指针指向首元结点
    LinkNode *searchPrt = head->getNext();

    //循环扫描整表
    while (searchPrt != nullptr) {
        //若找到则返回其词频
        if (searchPrt->getWord().getName() == word) {
            return searchPrt->getWord().getCount();
        }

        //searchPtr指针迭代
        searchPrt = searchPrt->getNext();
    }

    //若未找到则返回-1
    return -1;
}

6.3 顺序表的折半查找

/**
 * 折半查找单词
 * @param word 单词名
 * @return 词频/-1
 */
int binarySearch(const string &word) {
    //定义最低下标为记录首位，最高下标为记录末尾
    int low = 0, high = length, mid;

    //若查找未结束
    while (low <= high) {
        //折半，即查找值为范围内的中值
        mid = (low + high) / 2;

        if (word.compare(words[mid].getName()) < 0) {
            //若查找值比中值小，则最高下标调整到中位下标小一位
            high = mid - 1;
        } else if (word.compare(words[mid].getName()) > 0) {
            //若查找值比中值大，则最低下标调整到中位下标大一位
            low = mid + 1;
        } else {
            //若相等则说明mid即为查找到的位置，返回其词频
            return words[mid].getCount();
        }
    }

    //若未查找到则返回-1
    return -1;
}

6.4 排序树查找

/**
 * 二叉排序树内递归查找结点
 * @param word 要查找的单词
 * @param node 要查找的树的根结点
 * @param find 查找结果指针
 * @param father 查找的树的根结点的父结点
 * @return TRUE / FALSE
 */
static Status searchTree(const string &word, TreeNode *node, TreeNode *&find, TreeNode *father) {
    if (node == nullptr) {
        //若根节点为null，说明未找到，find指向该根结点的父结点，即与查找单词最接近的单词结点
        find = father;
        //返回FALSE表示查找失败
        return FALSE;
    } else if (word == node->getWord().getName()) {
        //若找到，find指向该单词结点
        find = node;
        //返回TRUE表示查找成功
        return TRUE;
    } else if (word.compare(node->getWord().getName()) < 0) {
        //若根结点的单词顺序在查找单词之前，则在其左子树内继续查找
        return searchTree(word, node->getLeftChild(), find, node);
    } else if (word.compare(node->getWord().getName()) > 0) {
        //若根结点的单词顺序在查找单词之前，则在其右子树内继续查找
        return searchTree(word, node->getRightChild(), find, node);
    }
}

6.5 哈希表的开放定址法

/**
 * 开放定址法的哈希查找
 * @param word
 * @return 地址/-1
 */
int searchHash(const string &word) {
    //计算单词的哈希地址
    int address = Hash(word);

    //循环判断地址内是否为该单词，若是则结束循环
    while (words[address].getName() != word) {
        //若不是则说明地址冲突，将地址+1再迭代
        address = (address + 1) % length;

        //若地址内无单词，说明该单词不存在与哈希表中，返回-1
        if (words[address].getName().empty() || address == Hash(word)) {
            return -1;
        }
    }

    //若找到则返回其地址值
    return address;
}

6.6 哈希表的链地址法

/**
 * 链地址法
 * 向表中输入一个单词
 * @param word 单词名
 * @return OK
 */
Status inputWord(const string &word) {
    //计算该单词的地址值
    int address = Hash(word);
    //定义查找指针指向该地址下的首个单词
    LinkNode *searchPtr;
    searchPtr = head[address].getNext();

    //若查找指针扫描完该地址下的所有单词，说明未在该地址下找到该单词，结束循环
    while (searchPtr != nullptr) {
        //若查找指针找到单词，则让该单词词频+1
        if (searchPtr->getWord().getName() == word) {
            searchPtr->addWordCount();
            return OK;
        }

        //查找指针指向同地址的下一个单词
        searchPtr = searchPtr->getNext();
    }

    //未找到该单词则新增一个单词，以头插法插入该地址下，单词个数+1
    auto *tempWord = new LinkNode(word);
    tempWord->setNext(head[address].getNext());
    head[address].setNext(tempWord);
    count++;

    return OK;
}