C語言中的搜索算法詳細(xì)解讀
一、分析
有大量的信息(關(guān)鍵字:描述),需要在大量的信息當(dāng)中搜索想要的信息:
(1)如果用全部檢索(遍歷)方法搜索關(guān)鍵字,無疑會(huì)浪費(fèi)時(shí)間和資源;
(2)如果用樹構(gòu)建一個(gè)搜索樹,層層搜索關(guān)鍵字(的一個(gè)字母),搜索到后就是需要的描述,就會(huì)節(jié)約很多時(shí)間。
二、算法思想
創(chuàng)建一個(gè)結(jié)構(gòu)體,有關(guān)于關(guān)鍵字指針的數(shù)組,還有信息對(duì)應(yīng)的描述。
typedef struct search_tree_node { //定義搜索樹節(jié)點(diǎn) struct search_tree_node* ch[CHAR_SIZE]; //分類 char desc[DESC_SIZE]; //描述 }STNode;
1、文字介紹
指針數(shù)組大小為 CHAR_SIZE = 26(默認(rèn)全部是小寫),每一個(gè)節(jié)點(diǎn)只存儲(chǔ)關(guān)鍵字的一個(gè)字母,層層遞進(jìn),當(dāng)關(guān)鍵字存儲(chǔ)完后,最后一個(gè)節(jié)點(diǎn)里的描述信息就是從根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)構(gòu)成關(guān)鍵字對(duì)應(yīng)的描述。(所以默認(rèn)關(guān)鍵字不能重復(fù))
2、圖例
從每一層讀取一個(gè)字母,找到最后一個(gè)字母下面就是描述。(bear)
三、算法實(shí)現(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é)點(diǎn) 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é)點(diǎn) 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é)點(diǎn) * @input : * none : none * @output: * node : 初始化的新結(jié)點(diǎn) *****************************************************************************/ STNode* new_node() { STNode* node; node = (STNode*)malloc(sizeof(STNode)); //分配一個(gè)空間 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 : 二級(jí)指針創(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)建,因?yàn)橐孕懹⑽淖帜笧槔?6),ASCII碼減去'a',得到指針相對(duì)地址(或數(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、測(cè)試數(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)于簡(jiǎn)化的搜索提示。
到此這篇關(guān)于C語言中的搜索算法詳細(xì)解讀的文章就介紹到這了,更多相關(guān)C語言搜索算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
C語言實(shí)現(xiàn)酒店客房管理系統(tǒng)課程設(shè)計(jì)
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)酒店客房管理系統(tǒng)課程設(shè)計(jì),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2022-03-03C++進(jìn)程的創(chuàng)建和進(jìn)程ID標(biāo)識(shí)詳細(xì)介紹
傳統(tǒng)的C++(C++98)中并沒有引入線程這個(gè)概念。linux和unix操作系統(tǒng)的設(shè)計(jì)采用的是多進(jìn)程,進(jìn)程間的通信十分方便,同時(shí)進(jìn)程之間互相有著獨(dú)立的空間,不會(huì)污染其他進(jìn)程的數(shù)據(jù),天然的隔離性給程序的穩(wěn)定性帶來了很大的保障2022-08-08解析如何利用switch語句進(jìn)行字符統(tǒng)計(jì)
本篇文章是對(duì)如何利用switch語句進(jìn)行字符統(tǒng)計(jì)的方法進(jìn)行了詳細(xì)的分析介紹,需要的朋友參考下2013-06-06C++類與對(duì)象深入之運(yùn)算符重載與const及初始化列表詳解
運(yùn)算符是程序中最最常見的操作,例如對(duì)于內(nèi)置類型的賦值我們直接使用=賦值即可,因?yàn)檫@些編譯器已經(jīng)幫我們做好了,但是對(duì)象的賦值呢?能直接賦值嗎2022-06-06