1

私は、機能またはキーワードのリストを維持する必要があるプロジェクト (C で実装) に取り組んでいます。ユーザーが文字列を入力します。格納された文字列の配列で、この文字列の大文字と小文字を区別しない検索を行う必要があります。リストは現在 100 文字列で構成されており、新しい文字列が追加される可能性があります (1 年に 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

これに適したデータ構造の 1 つは、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 (Binary Search Tree) - http://en.wikipedia.org/wiki/Binary_search_treeです。最悪の場合の検索時間は、またはを使用した場合とのみO(log n)比較されます。 O(n)arrayslists

数字を含むサンプル コードを次に示します (文字列に変更して を使用する必要がある場合があります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、ハッシュテーブルは一定の検索時間をもたらします O(1) - http://en.wikipedia.org/wiki/Hash_table

于 2012-04-19T08:24:21.450 に答える