c - 如果该元素不在列表中，则在链表的头部添加一个元素

Question

我有以下数据结构:

typedef struct Word {
    char *word;
    int occur;
    struct Word *next_word;
} * WordList;

我正在尝试实现一个将字符串(单词)添加到 WordList 的函数。如果它已经存在于列表中，则增加它的出现次数，否则，将它添加到头部。此函数还返回列表中所述单词的出现次数。

下面是我的实现:

#include <stdlib.h>
#include <string.h>

int addAtHead(WordList *w, char *word) {
    WordList head = *w;

    while (*w && strcmp((*w)->word, word) != 0)
        w = &(*w)->next_word;

    if (!*w) {
        WordList new = malloc(sizeof(struct Word));

        size_t length = strlen(word) + 1;
        new->word = malloc(length);
        memcpy(new->word, word, length);

        new->occur = 0;

        new->next_word = head;
        *w = new;
    }

    return ++(*w)->occur;
}

我有这些下一个函数来测试前一个函数:

#include <stdio.h>

void printWordList(WordList w) {
    for ( ; w; w = w->next_word)
        printf("Word: %s\nOccurrences: %d\n\n",
            w->word, w->occur);
}

int main(void) {
    WordList w = NULL;

    addAtHead(&w, "world");
    addAtHead(&w, "hello");
    printWordList(w);

    return 0;
}

当我编译并运行可执行文件时，我得到了这个结果:

> Word: world Occurrences: 1
> 
> Word: hello Occurrences: 1
> 
> Word: world Occurrences: 1
> 
> Word: hello Occurrences: 1
> 
> Word: world Occurrences: 1
> 
> Word: hello Occurrences: 1

继续，继续......

我假设在我的代码中某处我将最后一个元素链接到第一个元素，所以我画了下面的图表来找出发生这种情况的位置。

然后我假设问题出在 *w = new; 行。如何在不创建循环列表的情况下再次将 *w 设置为列表的开头？

Answer 1

我稍微简化了你的代码......也许你会明白这个想法:

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

typedef struct Word {
  char *word;
  int occur;
  struct Word *next_word;
}WordList;

int addAtHead(WordList **w_ptr, char *word) {
  WordList *head, *w;
  w = *w_ptr;
  head = w;

  while (w != NULL && strcmp(w->word, word) != 0)
     w = w->next_word;

  if (w == NULL) {
     WordList *newstruct;
     newstruct = malloc(sizeof *newstruct);
     if(newstruct == NULL) /* out of memory etc. */
       return -1;
     size_t length = strlen(word) + 1;
     newstruct->word = malloc(length);
     if(newstruct->word == NULL){
       free(newstruct);
       return -2;
     }
     memcpy(newstruct->word, word, length);

     newstruct->occur = 0;
     newstruct->next_word = head;
     w = newstruct;
     printf("address: %p, head: %p\n", w, head);
     *w_ptr = newstruct;
  }
  return ++(w->occur);
}

void printWordList(WordList *w) {
  for ( ; w; w = w->next_word)
     printf("Word: %s\nOccurrences: %d\n\n",
        w->word, w->occur);
}

int main(void) {
  int rv = 0;    
  WordList *w = NULL;

  rv = addAtHead(&w, "world");
  printf("addAtHead = %d\n",rv);
  rv = addAtHead(&w, "hello");
  printf("addAtHead = %d\n",rv);
  if(w == NULL){
    printf("w == NULL\n");
  } else { 
    printf("pointer address: %p\n",w);  
  }
  printWordList(w);
  return 0;
}

如果你想改变函数中的指针并想取回这个改变后的指针:要么你返回一个指针(函数的构建方式类似于 Wordlist * addAtHead(....) 或者您可以使用(在我们的例子中)指向该指针的指针。您必须获得对该指针的引用。