Cの辞書の単語を確認してください

Question

私はさまざまなサイズの単語が多いファイル（.dic）を持っているプロジェクトがあります。そしていくつかの言葉で別のファイル（.pal）。 .palファイルの各単語については、.dicファイルからアルファベット順に並び替えられた単語の数と同じ数の単語のリストでその位置を見つけなければなりません。

例えば、.DICファイル内 ：だから

dog 
flower 

：.PALファイルに

3 letters: [car->dab->dog->tar] 
6 letters: [banana->flower] 

：

car 
banana 
dog 
flower 
tar 

だから辞書のようなものになるだろう出力は次のようになります。

dog in position 3 
flower in position 2 

私の質問は：Cでこれを実装するのに最適なデータ構造は何ですか？それではメモリと時間は最小限に抑えられますか？

私は最初のインデックス（index1）が単語の文字数に対応し、2番目のインデックス（index2）が私が探している単語の最初の文字に対応する行列を持つことを考えていましたために。その行列の各要素は、index1文字を持ち、index2という文字で始まる単語のリストです。

例：

| A | B | C | ..... 
_______________ 

1|list|list|list| 
2|list|....|....| 
3|... 
. 
. 

だから "犬" は、マトリックス内部リストであろう[3] [D]。

問題1：すべての文字数が異なるか、最初の文字が異なる単語がない場合は、行列に穴が空いています - >あまりにも多くのメモリが無駄になりますか？

問題2：私が使用する前に各リストの要素の数を要約する前に私が尋ねた位置を知ること。

例：私は、リスト内の単語を挿入したときに「犬」の位置が

number of element in list [3][A]+number of element in list [3][B]+number of element in list [3][C]+"dog" position in the list 

だろうだから、私は次の行列要素にリストの要素数を更新しなければなりません。 - >時間がかかりますか？

この方法についてどう思いますか？より良いアイデアはありますか？

Answer 1

これをCで実装するのに最適なデータ構造は何ですか。これにより、メモリと時間が最小限に抑えられますか？

least memoryとleast timeの両方を取得するのは難しいです。できるだけメモリ使用量を低く抑えたい場合は、動的メモリ割り当てが必要です。これは、timeと考えると高価です。

低メモリ使用量を取得するには、次のようなデータ構造のために行くことができます：

#define MAX_WORD_LEN 50 
char** dic[MAX_WORD_LEN]; 

あなたはこのようにそれを使用します。

index 0: -----> char*, char*, char*, ... // Words with length 1 
       |  |  | 
       |  |  ------> string (i.e. char, '\0') 
       |  | 
       |  ------> string (i.e. char, '\0') 
       | 
       ------> string (i.e. char, '\0') 

index 1: -----> char*, char*, ... // Words with length 2 
       |  | 
       |  ------> string (i.e. char, char, '\0') 
       | 
       ------> string (i.e. char, char, '\0') 

これはあなたが言葉の可変数を保存することができます各文字列に必要なメモリよりも多くのメモリを割り当てることはありません。これは行列のようなものですが、各行が異なる数の列を持つことができるという利点があります。

ただし、かなりのダイナミックメモリ処理が必要です（malloc、realloc、strdup）。

実行時間を節約するには、「char *、char *、char *、...」の配列をNよりも1大きいNで拡張し、未使用のエントリをNULLに設定する必要があります。それは多くのreallocを節約しますが、各行の割り当てられた要素の数を追跡する必要があります。メモリ使用量が熱い本当であるならば、あなたは「char型*、CHAR * ...」アレイとちょうど各単語の長さのために一つの大きなchar配列を使用を避けることができ

struct x 
{ 
    char** data; 
    int number_allocated; 
} 

#define MAX_WORD_LEN 50 
struct x dic[MAX_WORD_LEN]; 

：それはのようなもののために呼び出すことができます。 Like：

index 0: -----> 'a', '\0', 'I', '\0', ... 
index 1: -----> 'b', 'e', '\0', 't', 'o', '\0', .... 

char配列のすべての単語の長さが同じであるため、これを行うことができます。あなたのようなものだろう。この場合

：

struct x 
{ 
    char* data; 
    int bytes_allocated; 
    int number_of_words; 
} 

#define MAX_WORD_LEN 50 
struct x dic[MAX_WORD_LEN];