1

私は K&R 本 (#6.3) の問題に取り組んでおり、ユーザーが一連の単語を入力すると、これらの単語のリストを、各単語が表示される行と共に作成する必要があります。それは構造を含むはずなので、これらは私が今持っているものです:

struct entry {
    int line; 
    int count; 
    struct entry *next; 
};

struct word {
    char *str;  
    struct entry *lines; 
    struct word *next; 
}; 

static struct word *wordlist = NULL;    // GLOBAL WORDLIST

しかし、何かを入力して、プログラムが新しいエントリを構造 (リンクされたリストのようなもの) に追加しようとすると、問題が発生し、プログラムはエラー メッセージなしで終了します。そのためのコード:

void add_entry(char *word, int line)
{
    if (word == NULL || line <= 0 || is_blocked_word(word))
        return;

    struct word *w; 
    for (w = wordlist; w != NULL && w->next != NULL && !strcmp(w->str, word); w = w->next); 

    // If word is found in the wordlist, then update the entry
    if (w != NULL) {
        struct entry *v; 
        for (v = w->lines; v != NULL && v->next != NULL && v->line != line; v = v->next); 

        if (v == NULL) {
            struct entry *new = (struct entry*) malloc(sizeof(struct entry)); 
            new->line = line;
            new->count = 1;
            new->next = NULL; 

            if (w->lines == NULL)
                w->lines = new; 
            else
                v->next = new; 
        }
        else v->count++; 
    }

    // If word is not found in the word list, then create a new entry for it
    else {
        struct word *new = (struct word*) malloc(sizeof(struct word)); 
        new->lines = (struct entry*) malloc(sizeof(struct entry)); 
        new->next = NULL; 
        new->str = (char*) malloc(sizeof(char) * strlen(word)); 
        new->lines->line = line; 
        new->lines->count = 1; 
        new->lines->next = NULL; 
        strcpy(new->str, word); 

        // If the word list is empty, then populate head first before populating the "next" entry
        if (wordlist == NULL) 
            wordlist = new; 
        else 
            w->next = new;
    }
}

に最初の単語を追加しただけでも、プログラムは終了しwordlistます。これは、私が malloc した有効な構造へのポインターが含まれているif (wordlist == NULL) wordlist = new;場所を示す行にあります。newこれはどのように可能ですか？

私の知る限り、それは私のポインターの使用法に問題がありますが、正確にどこにあるのかわかりません。誰か助けてくれませんか？

4

1 に答える 1

1

かなり明白なものもあれば、あまり明白でないものもあります。

wストップ 1 ショートの for ループ制限

for (w = wordlist; w != NULL && w->next != NULL && !strcmp(w->str, word); w = w->next);

これは最初から始まり、最後まで続きます。

  1. ノードが不足しています
  2. ほとんど(1 回の短い) ノードが不足しています。
  3. 現在のノードの単語が一致しません

ほぼ同じ問題、異なる for ループ

for (v = w->lines; v != NULL && v->next != NULL && v->line != line; v = v->next);

上記のように、これには同様の属性があります (ただし、3 番目のオプションではありません。これは、行番号が一致しない限り正しく続行されるためです。前のループは、単語が一致しないとすぐに壊れました。

そして、それはこの関数の最初の 10 行にあります。

文字列の割り当てサイズがヌル文字ターミネータを考慮していない

これは、ゼロで終わる文字列に必要な割り当てサイズの 1 文字分不足しています。

malloc(sizeof(char) * strlen(word))

ターミネータ用のスペースが常に必要です。これを覚える最も簡単な方法は、長さゼロの C 文字列に必要な文字数を考慮することです。答え: 1 つ、ターミネーターがどこかに行く必要があるためです。その後は単純にlength+1

これを行う 1 つの可能な方法は、以下に示すように、ポインターからポインターへのアプローチを使用することです。

void add_entry(const char *word, int line)
{
    if (word == NULL || line <= 0 || is_blocked_word(word))
        return;

    struct word **pp = &wordlist;
    for (; *pp && strcmp((*pp)->str, word); pp = &(*pp)->next);
    if (*pp)
    {
        // search for matching line number
        struct entry **vv = &(*pp)->lines;
        for (; *vv && (*vv)->line != line; vv = &(*vv)->next);
        if (!*vv)
        {
            *vv = malloc(sizeof(**vv));
            if (!*vv)
            {
                perror("Failed to allocate line entry.");
                exit(EXIT_FAILURE);
            }
            (*vv)->count = 1;
            (*vv)->line = line;
            (*vv)->next = NULL;
        }
        else
        {   // found an entry. increment count.
            (*vv)->count++;
        }
    }
    else
    {   // no matching word. create a new word with a new line entry
        size_t len = strlen(word);
        *pp = malloc(sizeof(**pp));
        if (!*pp)
        {
            perror("Failed to allocate word entry.");
            exit(EXIT_FAILURE);
        }

        (*pp)->lines = malloc(sizeof(*(*pp)->lines));
        if (!(*pp)->lines)
        {
            perror("Failed to allocate line count entry.");
            exit(EXIT_FAILURE);
        }

        (*pp)->str = malloc(len + 1);
        if (!(*pp)->str)
        {
            perror("Failed to allocate word string entry.");
            exit(EXIT_FAILURE);
        }

        (*pp)->lines->count = 1;
        (*pp)->lines->line = line;
        (*pp)->lines->next = NULL;
        (*pp)->next = NULL;
        memcpy((*pp)->str, word, len+1);
    }
}

使い方

どちらの場合も、ポインターツーポインターを使用します。「ワンバック」または「前の」ポインターを保持する必要なく、リンクされたリストで末尾の挿入を実行することが必要な場合、これらは最も手のかかる構造です。他のポインターと同様に、アドレスを保持します。通常のポインターから何かへのポインターとは異なり、ポインターからポインターから何かへのポインターは、別のポインターのアドレスを保持します。それを使用して、最初にヘッドポインタのアドレスに設定して検索を開始することにより、「ループ」できます。

struct word **pp = &wordlist;
for (; *pp && strcmp((*pp)->str, word); pp = &(*pp)->next);

ここでは、ヘッド ポインターのアドレスから始めます。保持されているアドレスppのポインターが NULL の場合、または単語が実際に一致する場合、ループは終了します。それ以外の場合は、現在のノードのポインター( のアドレスではなく)のアドレスを設定します。単語が不足し、一致するものが見つからない場合、ループは中断されますが、最も便利な結果が得られます。新しい割り当てに設定する必要があります。リストが最初に空の場合、ヘッド ポインタのアドレスが含まれます。nextpp

これで、次のことができます。

if (*pp)
{
    // search for matching line number
    struct entry **vv = &(*pp)->lines;
    for (; *vv && (*vv)->line != line; vv = &(*vv)->next);

行エントリ リストでも同じ考え方を使用していることに注意してください。エントリを見つけるか、またはループを終了し*vvてNULL、新しい割り当てに設定するポインタvvのアドレスを含めます。next

デバッガーでこのコードを 1 行ずつ実行し、そのしくみを理解することを強くお勧めします。この手法を利用することには多くの償いの資質があります。その中には、ヘッド ポインターをチェックしたり、挿入ごとにリストをウォークしたり、元の順序を保持したり (順序を逆にするのではなく) したりすることなくO(n)、複雑な前方リンク リストに入力する非常に簡単な方法があります。スタックのようなソリューションが得られるため):

struct node *head = NULL;

struct node **pp = &head;
while (get-data-for-our-list)
{
    *pp = malloc(sizeof(**pp));
    // TODO: populate (*pp)->members here
    pp = &(*pp)->next;
}
*pp = NULL;
于 2013-10-17T03:03:08.983 に答える