2 zbxun zbxun 于 2017.08.30 16:39 提问

存放英文单词并统计次数,用什么数据结构比较合理

首先定义一个结构体,存放的是char word[20] 单词的名称, int count 单词出现次数

,一个程序按行读取文本文件,每次读到一个英语单词,count加一。最后输出文本中所有的单词。这里考虑用结构体数组(顺序线性表存储是一种最简单的方案),请问有没有更合理的方案

2个回答

qq_27997547
qq_27997547   2017.08.30 17:16

可以用trie树实现。

 #include <stdio.h>  
#include <stdlib.h>  
#include <memory.h>  

typedef struct Trie_node{  
    int  count;  
    struct Trie_node *next[26];  

}TrieNode, *Trie;  

TrieNode* createTrieNode(){  
    TrieNode* root = (TrieNode*)malloc(sizeof(TrieNode));  
    root->count = 0;  
    memset(root->next, 0, sizeof(root->next));  
    return root;  
}  

void trie_insert(Trie root, char* word){  
    TrieNode* node = root;  
    char *p = word;  
    while(*p){  
        if(NULL == node->next[*p-'a']){  
            node->next[*p-'a'] = createTrieNode();  
        }  
        node = node->next[*p-'a'];  
        p++;  
    }  
    node->count += 1;  
}  

int trie_search(Trie root, char* word){  
    TrieNode* node = root;  
    char *p = word;  
    while(*p && node!=NULL){  
        node = node->next[*p-'a'];  
        p++;  
    }  
    return (node != NULL && node->count > 0);  
}  

int trie_word_count(Trie root, char* word){  
    TrieNode * node = root;  
    char *p = word;  
    while(*p &&node != NULL){  
        node = node->next[*p-'a'];  
        p++;  
    }  
    return node->count;  
}  


int main(){  
    Trie t = createTrieNode();  
    char word[][10] = {"test","study","open","show","shit","work","work","test","tea","word","area","word","test","test","test"};  
    for(int i = 0;i < 15;i++ ){  
        trie_insert(t,word[i]);  
    }  
    for(int i = 0;i < 15;i++ ){  
        printf("the word %s appears %d times in the trie-tree\n",word[i],trie_word_count(t,word[i]));  
    }  
    char s[10] = "testit";  
    printf("the word %s exist? %d \n",s,trie_search(t,s));  
    return 0;  
}  
qq_27997547
qq_27997547 那就用hash吧
3 个月之前 回复
zbxun
zbxun 回复橘红色的火焰fire: 既要实现查找又要遍历 用什么数据结构
3 个月之前 回复
qq_27997547
qq_27997547 最大限度的减少无谓的字符串比较,查询效率要高于哈希表。Tire树核心是空间换时间,利用字符串的公共前缀来降低查询的时间开销,从而达到提高效率的目的。对于庞大的空间消耗,我们可以用链表来动态开辟空间,达到空间上利用率的最大化。
3 个月之前 回复
zbxun
zbxun 请问这个有什么优势 ?
3 个月之前 回复
me_blue
me_blue   2017.08.30 18:18

Tire树是也称为字典树,比较适合应用于楼主提出的场景。根据tire树的特点可以看出优势主要有:

  • 节省存储空间,相同前缀的单词重复字段只会保留一份
  • 查找快,能够实现log(N)的查找速度 但遍历一遍,还是比较浪费时间的。

如果楼主不在意空间因素,那直接hash也是可行的。

me_blue
me_blue 回复zbxun: 遍历时候用tire树复杂度也不是特别高,只是没有什么优势而已。 感觉你的场景用hashmap就足够了。
3 个月之前 回复
zbxun
zbxun 既要实现查找又要实现遍历
3 个月之前 回复
zbxun
zbxun 那遍历的时候 时间复杂度特别高啊。。是换用别的数据结构吗
3 个月之前 回复
Csdn user default icon
上传中...
上传图片
插入图片