1

我正在做一个项目（用 C 语言实现），我们需要维护一个功能或关键字列表。用户输入一个字符串。我们需要在存储的字符串数组中对该字符串进行不区分大小写的搜索。该列表目前包含 100 个字符串，并且可能会添加新字符串（一年左右 5 个字符串）。

我想知道存储这个数组并提高搜索效率的最佳方式。

当前实现的解决方案如下：（我没有编译这段代码。这只是一个代码片段。）

    char **applist={ asdf , adgh, eftg , egty, ...} 
    char *user_input; // this string contains user entered string
    int id;
    switch(user_input[0])
    {
     case 'a':
     case 'A':
     switch(user_input[1]
     {
     case 's':
     case 'S':
     id=0
     break;

     case 'd':
     case 'D':
     id=1
     break;
     }
     break;
     case'e':
     case'E':
     switch(user_input[1])
     {
     case 'f':
     case 'F':
     id=2
     break;

     case 'g':
     case 'G':
     id=3
     break;
     }
     break;
     }
    if(stricmp(user_input,applist[id]))
    return id;
    else 
    return -1;

在实际代码中 applist 没有排序。随着新字符串被添加到 applist，我需要一种有效的方法来存储这个数组。

如果我存储按字母顺序排序的字符串，那么每次添加新字符串时，我都必须手动找到新字符串的正确位置。（不是在运行时编译代码之前将新字符串添加到 applist 中）

建议一种有效的方法来做到这一点。

编辑：我目前的方法导致代码更长，但效率更高。但是这段代码不容易维护。我需要的是一种数据结构，它可以以与此相同的效率进行搜索，但代码更小。您建议的数据结构不应有额外的开销。唯一的要求是高效搜索。以及一种在编译时轻松向数据结构添加元素的方法。在运行时排序不是我的要求，因为在编译时添加了新字符串（这是为了避免限制用户将任何新字符串添加到列表中）。

4

3 回答 3

3

一个好的数据结构可能是 TRIE：

http://en.wikipedia.org/wiki/Trie

看起来这就是您已经开始在代码中实现的内容。

于 2012-04-19T08:21:01.997 回答
2

听起来这不是代码的性能关键位，在这种情况下，我建议使用 strcasestr 进行字符串比较。像这样存储关键字

char *applist[] = {"abc", "def", "geh"}

然后遍历它们并像这样将用户输入与 strcasestr 进行比较

if (strlen(applist[id]) == strlen(user_input) && 
            strcasestr(applist[id], user_input) != NULL)
    return id;

这种方法比使用复杂的数据结构更简洁和可维护。如果您确实关心性能，请首先实现此方法，进行一些时序测试，然后您可以决定是否需要更快的算法。

于 2012-04-19T08:35:06.483 回答
0

在搜索字符串时，您可以使用的最佳数据结构是 BST - 二进制搜索树 - http://en.wikipedia.org/wiki/Binary_search_tree。最坏情况的搜索时间将仅O(log n)与O(n)使用arraysor时进行比较lists。

这是一个带有数字的示例代码（您可能必须用字符串更改它并使用strcmp）：

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>

typedef struct node {
        int data;
        struct node *left;
        struct node *right;
} NODE;


NODE * newnode (int data) 
{
    NODE * n = NULL;
    if (n = (NODE *) malloc (sizeof (NODE))) {
        n->data = data;
        n->right = n->left = NULL;
    } else {
        printf("Error: unable to allocate memory \n");
    }

    return n;
}


NODE * insert (NODE * head, int data)
{
    NODE * n;

    if (head == NULL)
        return newnode(data);

    if (head->data == data) {
        printf("Info: attempting to add duplicate element : %d\n", data);
        return head;
    }

    if (head->data < data)
        head->right = insert(head->right, data);
    else
        head->left = insert(head->left, data);

    return head;
}    

void inorder(NODE * node)
{
        if (node == NULL) 
                return;

        inorder(node->left);
        printf("%d ", node->data);
        inorder(node->right);
        return;
}

int lookup(NODE * head, int data)
{
    if (head == NULL)
        return 0;

    if (head->data == data)
        return 1;

    if (head->data < data)
        return lookup(head->right, data);
    else
        return lookup(head->left, data);
}

void search(NODE * head, int data)
{
    if (lookup(head, data)) {
        printf("found : %d \n", data);
    } else {
        printf("not found : %d \n", data);
    }

    return;
}

int main()
{
    int sum = 35;
    NODE * root = NULL;

    root = insert(root, 20); 
    root = insert(root, 10); 
    root = insert(root, 22); 
    root = insert(root, 23); 
    root = insert(root, 24); 
    root = insert(root, 25); 
    root = insert(root, 10); 
    root = insert(root, 20); 
    root = insert(root, 30); 
    root = insert(root, 40); 
    root = insert(root, 50); 
    root = insert(root, 60); 
    inorder(root);  printf("\n");

    search(root, 10);
    search(root, 11);
    search(root, 13);
    search(root, 14);

    return 0;
}

OTOH，hast 表将为您提供恒定的搜索时间 O(1) - http://en.wikipedia.org/wiki/Hash_table

于 2012-04-19T08:24:21.450 回答