Удаление всех элементов из стека, не подходящих под условие

Question

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

#define MAX_WORLD_LENGHT 1024

typedef struct Node {
    char *word;
    struct Node *next;
} Node;


void removing (Node **head)
{
    Node* prev = NULL;
    while (*head != NULL)
    {
        prev = (*head);
        (*head) = (*head)->next;
        free(prev->word);
        free(prev);
    }
}


int remove_short_words( Node **head, int x )
{
    Node * cur = (*head);
    Node * prev = NULL;

    while ( cur != NULL )
    {
        if ( strlen(cur->word) < x )
        {
            if ( prev == NULL )
            {
                free((*head)->word);
                free(*head);
                (*head) = (*head)->next;
                prev = cur;
                cur = (*head);
            }
            else if ( cur->next == NULL )
            {
                free(cur->word);
                free(cur);
                prev->next = cur;
                return 0;
            }
            else
            {
                prev->next = cur->next;
                free(cur->word);
                free(cur);
                cur = cur->next;
            }
        }
        else
        {
            prev = cur;
            cur = cur->next;
        }
    }
    return 0;
}

void push ( Node **head, char *word_link )
{
    Node *m;

    if ( (m = (Node*) malloc(sizeof(Node))) == NULL )
    {
        printf("Malloc function error\n");
        exit(1);
    }

    m->word = word_link;
    m->next = *head;

    *head = m;
}


void malloc_it ( char **word_link, char word[MAX_WORLD_LENGHT] )
{
    if ( (*word_link = (char*) malloc(strlen(word))) == NULL )
    {
        printf("Malloc function error\n");
        exit(1);
    }
    strcpy(*word_link, word);
}


int read_from_file ( FILE *read_here, char word[MAX_WORLD_LENGHT] )
{
    if ( fscanf(read_here, "%s", word) == EOF )
    {
        return 1;
    }
    return 0;
}


void output(Node *head)
{
    while (head != NULL)
    {
        printf("%s\n", ((head)->word));
        head = (head)->next;    
    }   
}


int main ( int argc, char *argv[] )
{
    Node *head = NULL;
    FILE *read_here;
    char word[MAX_WORLD_LENGHT];
    char *word_link;

    if ( argc != 2 )
    {
        printf("Usage: (This file name) (File name where to read)\n");
        return 1;
    }

    read_here = fopen(argv[1], "r");

    if (!read_here)
    {
        printf("Файл не найден.\n");
        return 1;
    }

    while ( read_from_file(read_here, word) != 1 )
    {
        malloc_it(&word_link, word);
        push(&head, word_link);
    }

    fclose(read_here);

    remove_short_words(&head, 3);

    output(head);

    removing(&head);
}

Программа считывает слова из файла, а затем удаляет слова длина которых меньше 3 и выводит оставшиеся слова. Без удаления слов (вызова функции remove_short_words) все работает хорошо. При вызове функции выдает Segmentation fault (core dumped).

Answer 1

Ну у вас тут небольшие проблемы с выделением памяти.

Вы выделяете недостаточно памяти под копирование строк, т.к. функция strlen() дает размер строки без завершающего 0. А копирование копирует в том числе и 0. Это - UB

void malloc_it ( char **word_link, char word[MAX_WORLD_LENGHT] )
{
    if ( (*word_link = (char*) malloc( strlen(word) )) == NULL ) // выделяете условно 10 байт
    {}
    strcpy(*word_link, word); // а копируете 11 байт
}
// должно быть
malloc( strlen(word) + 1 )

Вы пытаетесь работать с уже удаленной памятью в функции remove_short_words(). Это - UB. Кроме того, вы присваиваете prev значение удаленного узла. А должен быть NULL, т.к. вы удалили первый элемент списка.

int remove_short_words( Node **head, int x )
{
            if ( prev == NULL )
            {
                free((*head)->word);
                free(*head);  // удалили память по указателю
                (*head) = (*head)->next; // а теперь обращаетесь туда
                prev = cur;   // указывает на несуществующий элемент, а должен быть NULL
                cur = (*head);
            }
            else if ( cur->next == NULL )
            {
                free(cur->word);
                free(cur);
                prev->next = cur;
                return 0;
            }
            else
            {
                prev->next = cur->next;
                free(cur->word);
                free(cur);  // удалили память по указателю
                cur = cur->next;  // а теперь обращаетесь туда
            }
        }
        else
        {
            prev = cur;
            cur = cur->next;
        }
    }
    return 0;
}

Во втором блоке, в случае удаления последнего элемента в списке, вы обрываете список несуществующим элементом. А его надо завершить NULL, иначе при последующих операциях (печать, удаление и т.д.) вы выйдете из списка в неизведанные просторы памяти - это UB.

            if ( prev == NULL )
            {
            }
            else if ( cur->next == NULL )
            {
                free(cur->word);
                free(cur);
                prev->next = cur; // вы обрываете список несуществующим элементом
                // должно быть
                prev->next = NULL;
                return 0;
            }

Ну и немного рефакторинга функции remove_short_words().
Второй блок else if ( cur->next == NULL ) в общем-то не нужен - его можно соптимизировать. На последнем элементе списка после операции cur = cur->next; cur станет равен нулю и произойдет выход из цикла while()
В первом блоке вы пытаетесь работать с указателем на начало списка head, хотя везде используете локальный cur - зачем? Это сбивает с толку. Если переписать как в остальной программе, то вы увидите дублирование кода.

                prev = cur;
                cur = cur->next;
                (*head) = cur;

Ну и тогда функция уменьшается до

int remove_short_words( Node **head, int x )
{
    Node * cur = (*head);
    Node * prev = NULL;

    while ( cur != NULL )
    {
        if ( strlen(cur->word) >= x )
        {
            prev = cur;
            cur = cur->next;
            continue;
        }

        Node* tmp = cur;
        cur = cur->next;
        if ( prev == NULL )
            (*head) = cur;
        else
            prev->next = cur;

        free(tmp->word);
        free(tmp);
    }
    return 0;
}

БЛОГ НА HUSL

Удаление всех элементов из стека, не подходящих под условие

Ответы (1 шт):