哈希表之單詞查找

1. 英文文章，寫入一個文本檔案，作為基礎測驗資料， 建立一個待查關鍵字檔案，存盤待查詢的單詞，
2. 輸入查詢的單詞，輸出該單詞的出現次數，及每個出現位置的背景關系（前一句，單詞/短語所在的句子，下一句），
3. 目前只支持查詢一個單詞，

以下為代碼：

#include <iostream>
#include <string.h>
#include<vector>
#include <map>
#include <set>
#include<sstream>
#include <fstream>
#include <windows.h>
const int HASHNUM = 29989;

typedef struct Hashtable{            //哈希表結構體
    char *word;
    int count;
    struct Hashtable * next;
}Hashnode;
Hashnode* hashtable[HASHNUM];       //HASHNUMBER大小的指標陣列(儲存指標的陣列) 作為hash表

std::vector<std::string>lines;
std::map<std::string,std::set<int>> wordline;   //需要使用到迭代器匹配行號所以使用map嵌套set

unsigned int Hashfuntion(const char *str);
void Hashinsert(char *str);
void readintohash(char *path);
void findquery(char *path);
void getlinecplusplus(char *path,char *str);


void readintohash(char *path){
    char ch[1024] = {NULL};              //存盤一行字串
    char *p;
    FILE *fp = fopen(path,"r");
    if(fp == NULL)
        exit(-1);
    while(( fgets(ch,sizeof (ch),fp) != NULL ))                           //讀取到換行符時，或者到達檔案末尾時停止
    {
        if(strcmp( " " , ch ) == 0)                                       //空行繼續
            continue;

        const char *ch1 = ", \n\t.";                                      //要分割的字符(逗號、空格、換行、制表符、句號)
        p = strtok(ch,ch1);                                               //用strtok函式從一行字串中分離出每個單詞，分隔符設定為(空格、逗號、換行、制表符)
        while(p != NULL)
        {
            Hashinsert(p);
            p = strtok(NULL, ch1);                              //每次找到一個分隔符后，一個空（NULL）就被放到分隔符處，strtok函式用這種方法來連續查找該字串，此處的NULL是一個指向后面還未分割的單詞的指標，因此，首次呼叫時，第一個元素必須指向要分解的字串，隨后呼叫要把元素設成NULL，
        }
    }
    fclose(fp);
}

void Hashinsert(char *str){
    int hashcode = Hashfuntion(str);
    Hashnode *newnode;
    for (newnode = hashtable[hashcode]; newnode != NULL ; ++newnode) {
        if(strcmp(str, newnode->word) == 0){       //查找單詞是否已經在hash表中了
            (newnode->count)++;
            return;
        }
    }
    //如果上面沒回傳，也就是說hash表中沒有這個單詞，添加新節點，加入這個單詞
    newnode = new Hashnode;
    newnode->count = 1;

    newnode->word = (char *)malloc(strlen(str) + 1);
    strcpy(newnode->word,str);

    newnode->next = hashtable[hashcode];        //將新生成的節點插入到hashcode為下標的鏈表中去
    hashtable[hashcode] = newnode;
}

unsigned int Hashfuntion(const char *str)
{
    unsigned int index = 0;
    for (; *str != '\0' ; str++) {
        index = index * 31 + *str;
    }
    return index % HASHNUM;
}

void findquery(char *path){
    char ch[50] = {NULL};
    FILE *fp = fopen(path,"r");
    std::ofstream outfile1("E:\\answer.txt");

    while(fgets(ch,sizeof (ch),fp)){                    //把待查關鍵字讀入
        int hashcode2 = Hashfuntion(ch);
        outfile1 << hashtable[hashcode2]->word << "出現了" << hashtable[hashcode2]->count << "次" << std::endl;
    }
    getlinecplusplus("E:\\database.txt",ch);
    fclose(fp);
}

void getlinecplusplus(char *path,char *str){
    std::ifstream readfile(path);                                        //用ifstream讀入txt檔案path并與readfile相連
    std::ofstream outfile("E:\\answer.txt",std::ofstream::app);         //用ofstream將答案輸出到answer.txt
    int linecount = 0;
    std::string line;
    std::string word;
    while(std::getline(readfile, line)){
        lines.push_back(line);                                        //將一行放入vector<string>中
        std::istringstream iss(line);                                 //獲取一行
        ++linecount;                                                  //行號加1
        while(iss >> word){  
            wordline[word].insert(linecount);                        //加入詞的行號
        }
    }
    std::set<int>::const_iterator itset;
    std::vector<std::string>::const_iterator itvector;              //新建兩個迭代器

    int i;
    for(itset = (wordline.find(str)->second).begin();itset != (wordline.find(str)->second).end(); itset++)
    {
        outfile << "出現在第 "<< *itset <<"行" << std::endl;
        i = 0;
        for (itvector = lines.begin(); itvector != lines.end(); itvector++) {       //前一句，單詞所在的句子，下一句
            if (*itset == ++i)          //行號與vector回圈次數匹配上了
            {
                if(itvector != lines.begin()){                                      //第一句不能列印前一句
                    outfile << *(itvector-1) << std::endl;
                }
                if(itvector != lines.end()-1){                                      //最后一句不能列印后一句
                    outfile << *(itvector+1) << std::endl;
                }
                outfile << *itvector << std::endl;                                  //單詞本身句
            }
        }
    }
    outfile.close();
}

int main(){
    SetConsoleOutputCP(65001);              //避免控制臺中文亂碼
    readintohash("E:\\database.txt");      //自行更改路徑
    findquery("E:\\query.txt");
    return 0;
}

標籤：其他

上一篇：串口多位元組資料的接收

下一篇：Chapter_2_變數和簡單資料型別