Удалить строку из связанного списка строк

Question

Я работаю над текстовым процессором, в котором запрашивается возможность удаления слова из списка слов.

По сути, пользователь вводит слова (то есть строки символов), которые затемхранится в связанном списке (здесь dico, благодаря структурному словарю, который представляет все слова, введенные пользователем).

Я, к сожалению, застрял: кажется, что код, который я написал, удаляет только второй символ, тогда как я хотел бы, чтобы он мог удалить слово, запрошенное пользователем (здесь: str).

Например, если ранее пользователь ввел: "hello world", и теперь он хотел бы удалить мир "world", теперь dico должен быть "hello".

typedef struct dll {
    char data;
    int count;      //not needed here
    struct dll* next;
} dll;  //linked list of each character : dll represents one word

typedef struct dictionary {
    dll * data;
    struct dictionary* next;
    struct dictionary* prev;
} dictionary;  //linked list of all the words

dll* entry(){
    char data = getc(stdin);
    if (data != '\n'){
        dll* curr = create_dico(data);
        curr->next=entry();
        return curr;
    }
    return NULL;
}


void suppression(dictionary** dico) {
    printf("Please enter what you wish to remove out of the list: \n");
    dictionary *str = malloc(sizeof(dictionary));
    str->data = entry();
    str->next = NULL;

    dictionary* temp = *dico;

    if (str->data == NULL){
        *dico = temp->next;
        free(temp);
        return;
    }
    while (temp != NULL && temp->data->data == str->data->data) {
        temp = temp->next;
    }
    dictionary *next = temp->next->next;
    free(temp->next);
    temp->next = next;
}

Answer 1

Ваша функция удаления не отражает используемые вами структуры данных: связанные списки связанных списков!

Самое первое, что вам нужно сделать, это определить, где находится слово . Для этого вам нужно сравнить два связанных списка:

// notice: pointer to dll, not dictionary!
dll* str = entry();

dictionary* temp = *dico;
while(temp)
{
    dll* s = str; // you yet need original str for deletion!
    dll* word = temp->data;
    while(word && s && word->data == s->data)
    {
        word = word->next;
        s = s->next;
    }
    // OK, now we need to know if we reached the ends of BOTH word and s
    // -> in that case, both are equal!
    if(!word && !s)
        break;
}

Итак, мы перебрали список слов. Если мы нашли строку внутри, мы преждевременно остановились, в противном случае мы достигли нулевого элемента в самом конце. Итак:

if(temp)
{
    // we didn't reach end of the words' list -> we found an equal element

    // at first, we'd remove the current word from the linked simply by
    // re-linking predecessor and successor nodes
    // the nice thing about is that you created a doubly linked list
    // so we have both of them available from current node, so:

    if(temp->prev)
        temp->prev->next = temp->next;
    else
        // special case: we are deleting the head node!
        *dico = temp->next;

    if(temp->next)
        temp->next->prev = temp->prev;
    // no else needed, as we haven't a dedicated tail node

    // now we need to delete the word's characters!
    dll* word = temp->data;
    while(word)
    {
        dll* next = word->next;
        free(word);
        word = next;
    }

    // now we yet need to delete the word node itself!
    free(temp);
}

Пока все отлично, список скорректирован. Однако мы создали временную ссылочную строку, которую тоже нужно освободить снова:

while(str)
    // well, just the same as when deleting the word...

Поскольку вы делаете одно и то же дважды, вы можете создать общую функцию для ...

Имейте в виду, что приведенный выше код не проверен, нет никаких гарантий, что он не содержит ошибок. Но этого должно быть достаточно, чтобы показать, где вы должны следить ... Также имейте в виду, что этот ответ основан на довольно многих предположениях , в основном списки, которые были созданы правильно до того, как выне предоставил минимальный воспроизводимый пример .