Добавление элемента в заголовок связанного списка, если элемент отсутствует в списке - PullRequest
Новая
       48

Добавление элемента в заголовок связанного списка, если элемент отсутствует в списке

0 голосов
/ 04 декабря 2018

У меня следующая структура данных: 

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

и так далее, и так далее.

Я предполагал, что где-то в моем коде я связываю последнийэлемент к первому, поэтому я нарисовал следующие диаграммы, чтобы выяснить, где это происходит.

enter image description here

enter image description here

Затем я предположил, что проблема заключается в строке *w = new;.Как мне снова установить *w для начала списка, не создавая циклический список?

1 Ответ

0 голосов
/ 04 декабря 2018

Я немного упростил ваш код ... возможно, вы поймете идею: 

#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(....) или вы можете использовать (в нашем случае) указатель на этот указатель. Вы должны получить ссылку на этот указатель.

...