C語言中的搜索算法詳細解讀
一、分析
有大量的信息(關(guān)鍵字:描述),需要在大量的信息當(dāng)中搜索想要的信息:
(1)如果用全部檢索(遍歷)方法搜索關(guān)鍵字,無疑會浪費時間和資源;
(2)如果用樹構(gòu)建一個搜索樹,層層搜索關(guān)鍵字(的一個字母),搜索到后就是需要的描述,就會節(jié)約很多時間。
二、算法思想
創(chuàng)建一個結(jié)構(gòu)體,有關(guān)于關(guān)鍵字指針的數(shù)組,還有信息對應(yīng)的描述。
typedef struct search_tree_node { //定義搜索樹節(jié)點 struct search_tree_node* ch[CHAR_SIZE]; //分類 char desc[DESC_SIZE]; //描述 }STNode;
1、文字介紹
指針數(shù)組大小為 CHAR_SIZE = 26(默認(rèn)全部是小寫),每一個節(jié)點只存儲關(guān)鍵字的一個字母,層層遞進,當(dāng)關(guān)鍵字存儲完后,最后一個節(jié)點里的描述信息就是從根節(jié)點到當(dāng)前節(jié)點構(gòu)成關(guān)鍵字對應(yīng)的描述。(所以默認(rèn)關(guān)鍵字不能重復(fù))
2、圖例
從每一層讀取一個字母,找到最后一個字母下面就是描述。(bear)
三、算法實現(xiàn)
1、代碼
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <string.h> #include <malloc.h> #define CHAR_SIZE 26 //字母大?。?6小寫) #define KEY_SIZE 256 //關(guān)鍵字大小 #define DESC_SIZE 256 //描述區(qū)大小 #define BUFF_SIZE 512 //緩沖區(qū)大小 #define FILE_NAME "test.txt" //文件路徑 typedef struct search_tree_node { //定義搜索樹節(jié)點 struct search_tree_node* ch[CHAR_SIZE]; //分類 char desc[DESC_SIZE]; //描述 }STNode; int get_word(FILE* fp, char* key, char* desc); //分離文本信息 STNode* new_node(); //新建節(jié)點 int insert_st_tree(STNode** st_tree, char* key, char* desc); //插入信息 char* find(STNode* st_tree, char* key); //查找分類 int main() { char key[KEY_SIZE]; char desc[DESC_SIZE]; STNode* st_tree = NULL; char* data; FILE* fp = fopen(FILE_NAME, "r"); if (fp == NULL) { fprintf(stderr, "fopen error!\n"); return -1; } while (1) { int res = get_word(fp, key, desc); if (res != -1) { printf("%s\n", key); printf("%s\n", desc); } else { break; } insert_st_tree(&st_tree, key, desc); } data = find(st_tree, (char*)"ant"); if (data != NULL) { printf("\nFind description: %s", data); } else { printf("\nCan not find!\n"); } fclose(fp); return 0; } /***************************************************************************** * @data : 2020/4/19 * @brief : 讀取文件,分離關(guān)鍵字和描述信息 * @input : * fp : 文件指針 * key : 關(guān)鍵字(返回) * desc: 描述信息(返回) * @output: * -1 : 失敗 * 0 : 成功 *****************************************************************************/ int get_word(FILE* fp, char* key, char* desc) { int i, j; char buff[BUFF_SIZE]; char* res = fgets(buff, BUFF_SIZE, fp); //逐行讀?。ò〒Q行符) if (res == NULL) { return -1; } for (i = 0; i < KEY_SIZE - 1 && buff[i] != ':'; i++) { //預(yù)留結(jié)束符,分割標(biāo)志 key[i] = buff[i]; } key[i] = '\0'; i++; for (j = 0; j < DESC_SIZE - 1 && buff[i] != '\0'; j++, i++) { //預(yù)留結(jié)束符,結(jié)束標(biāo)志 desc[j] = buff[i]; } desc[j] = '\0'; return 0; } /***************************************************************************** * @data : 2020/4/19 * @brief : 創(chuàng)建新搜索樹結(jié)點 * @input : * none : none * @output: * node : 初始化的新結(jié)點 *****************************************************************************/ STNode* new_node() { STNode* node; node = (STNode*)malloc(sizeof(STNode)); //分配一個空間 if (node == NULL) { return NULL; } for (int i = 0; i < CHAR_SIZE; i++) { //初始化 node->ch[i] = NULL; } node->desc[0] = '\0'; return node; } /***************************************************************************** * @data : 2020/4/19 * @brief : 創(chuàng)建搜索樹 * @input : * st_tree : 二級指針創(chuàng)建搜索樹 * key : 關(guān)鍵字 * desc : 描述信息 * @output: * -1 : 失敗 * 0 : 成功 *****************************************************************************/ int insert_st_tree(STNode** st_tree, char* key, char* desc) { if (*st_tree == NULL) { *st_tree = new_node(); if (*st_tree == NULL) { return -1; } } if (*key == '\0') { strcpy((*st_tree)->desc, desc); return 0; } //遞歸創(chuàng)建,因為以小寫英文字母為例(26),ASCII碼減去'a',得到指針相對地址(或數(shù)組下標(biāo)) return insert_st_tree((*st_tree)->ch + *key - 'a', key + 1, desc); } /***************************************************************************** * @data : 2020/4/19 * @brief : 使用搜索樹查詢關(guān)鍵字描述(有返回,無) * @input : * st_tree : 搜索樹 * key : 關(guān)鍵字 * @output: * desc : 描述信息 * NULL : 空 *****************************************************************************/ char* find(STNode* st_tree, char* key) { if (st_tree == NULL) { //為空,返回 NULL return NULL; } if (*key == '\0') { //完全匹配,返回描述信息 if (st_tree->desc[0] == '\0') { return NULL; } return st_tree->desc; } return find(st_tree->ch[*key - 'a'], key + 1); //遞歸查找 }
2、測試數(shù)據(jù)
ant:a small insect that lives in group
bee:an animal that can pick flowers and make honey
bear:the bear's body is thick and fat, and its hair is long and dense
beetle:an animal that feeds on pollen and a few nectar
dog:an animal which is loyal to human
dove:a flighty bird that feeds mainly on cereals
donkey:an animal with short legs and long ears
snake:a long and thin animal that lives in grass or other dark places
四、結(jié)果圖
以找 dog 為例:
五、總結(jié)
要是能夠?qū)崿F(xiàn)加載下一層,是不是就相當(dāng)于簡化的搜索提示。
到此這篇關(guān)于C語言中的搜索算法詳細解讀的文章就介紹到這了,更多相關(guān)C語言搜索算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
C語言實現(xiàn)酒店客房管理系統(tǒng)課程設(shè)計
這篇文章主要為大家詳細介紹了C語言實現(xiàn)酒店客房管理系統(tǒng)課程設(shè)計,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下2022-03-03C++進程的創(chuàng)建和進程ID標(biāo)識詳細介紹
傳統(tǒng)的C++(C++98)中并沒有引入線程這個概念。linux和unix操作系統(tǒng)的設(shè)計采用的是多進程,進程間的通信十分方便,同時進程之間互相有著獨立的空間,不會污染其他進程的數(shù)據(jù),天然的隔離性給程序的穩(wěn)定性帶來了很大的保障2022-08-08