Проблемы со связанным списком в C

Подсказка, которую мне дали, запрашивает программу на c, которая реализует связанный список и дает пользователям возможность выполнять различные функции в связанном списке. Необходимые функции:

  • isempty(): проверяет, пуст ли список, и возвращает значения, указывающие, пуст он или нет.
  • add(): добавить элемент в конец списка
  • insert(): вставить элемент по определенному индексу в списке
  • find(): найти индекс, в котором хранится определенное значение. . Если функция не вернет значение, указывающее, что
  • get(): получить значение, хранящееся по определенному индексу
  • remove(): удалить первое появление определенного значения в списке. Если функция не вернет значение, указывающее, что
  • replace(): заменить значение, хранящееся по определенному индексу
  • delete(): удалить элемент по определенному индексу. . Если функция не вернет значение, указывающее, что
  • list(): вывести элементы списка в формате [a, b, c]

Когда я вызываю функцию add_tail, она позволяет мне ввести значение, которое я хочу добавить, но примерно через минуту я получаю сообщение в терминале о том, что программа была убита. Что может быть причиной этого? У меня также возникают проблемы с циклом while в основной функции, которая используется для печати меню и ввода данных пользователем. Меню будет печататься нормально, когда я впервые запускаю программу, но после завершения действия меню печатается один раз, но пропускает ввод пользователя, а затем печатается снова, но принимает ввод пользователя во второй раз.

заголовочный файл:

#ifndef LAB8_H_
#define LAB8_H_

#define FIND 'F'
#define EMPTY 'E'
#define ADD 'A'
#define INSERT 'I'
#define DELETE 'D'
#define REMOVE 'R'
#define REPLACE 'S'
#define GET 'G'
#define LIST 'L'
#define QUIT 'Q'
#define FAIL -100

struct node_t {
        struct node_t * next;
        int value;
};

struct node_t * create_node(int value);
struct node_t * add_tail(struct node_t * head, int value);
struct node_t * insert_node(struct node_t * head, int index, int value);
int is_empty(struct node_t * head);
int find_val(struct node_t * head, int value);
int get_value(struct node_t * head, int index);
struct node_t * replace_val(struct node_t * head, int index, int value);
struct node_t * remove_val(struct node_t * head, int value);
struct node_t * delete_node(struct node_t * head, int index);
void print_list(struct node_t * head);

#endif

.c-файл:

#include <stdio.h>
#include <stdlib.h>
#include "func.h"

struct node_t * create_node(int value)
{
        struct node_t * new_node = malloc(sizeof(struct node_t));
        new_node -> next = NULL;
        new_node -> value = value;

        return new_node;
}


struct node_t * add_tail(struct node_t * head, int value)
{
        struct node_t * tmp;

        if (head == NULL){
                printf("Cannot add tail to an empty list. Try again\n");
                return NULL;
        } else{
                while(head != NULL){
                        if (head -> next == NULL){
                                tmp = create_node(value);
                                head -> next = tmp;
                        } else{
                                head = head -> next;
                        }
                }
        }

        return head;
}


struct node_t * insert_node(struct node_t * head, int index, int value)
{
        struct node_t * tmp;
        struct node_t * new;

        if (index < 0){
                printf("Index cannot be a negative number. Please try again\n");
                return head;
        }

        if (index == 0){
                tmp = head;
                head = create_node(value);
                head -> next = tmp;
        } else {
                tmp = head;

                while(tmp != NULL){
                        if (index == 1){
                                struct node_t * prev = tmp;
                                tmp = tmp -> next;
                                new = create_node(value);
                                new -> next = tmp;
                                prev -> next = new;
                                head = prev;
                        } else if ((tmp -> next == NULL) && (index != 0)){
                                printf("The index is not found in the bounds of the list. Try again\n");
                                return head;
                        } else{
                                tmp = tmp -> next;
                                index--;
                        }
                }
        }

        return head;
}

int is_empty(struct node_t * head)
{
        if (head == NULL){
                return 0;
        } else{
                return 1;
        }
}

int find_val(struct node_t * head, int value)
{
        int index = 0;

        if (head == NULL){
                printf("Cannot find value in empty list! Try again\n");
                index = -100;
        } else{
                while(head != NULL){
                        if ((head -> next == NULL) && (head -> value != value)){
                                printf("The value does not exist in the list\n");
                                index = -100;
                        } else if (head -> value == value){
                                return index;
                        } else{
                                head = head -> next;
                                index++;
                        }
                }
        }

        return index;
}

int get_value(struct node_t * head, int index)
{
        int value;

        if (index < 0){
                printf("Index cannot be a negative number. Try again\n");
                value = -100;
        } else if (head == NULL){
                printf("Cannot find index in empty list. Try again\n");
                value = -100;
        } else{
                while(head != NULL){
                        if (index == 0){
                                value = head -> value;

                        } else if ((head -> next == NULL) && (index != 0)){
                                printf("Index does not exist in the bounds of the list. Try again\n");
                                value= -100;
                        } else{
                                head = head -> next;
                                index--;
                        }
                }
        }

        return value;
}

struct node_t * replace_val(struct node_t * head, int index, int value)
{
        struct node_t * tmp;

        if (index < 0){
                printf("Index cannot be a negative number. Try again\n");
                return NULL;
        } else if (head == NULL){
                printf("Cannot replace elements in an empty list. Try again\n");
                return NULL;
        } else{
                while(head != NULL){
                        if (index == 0){
                                tmp = head;
                                tmp -> value = value;
                                free(head);
                                head = tmp;
                        } else if ((head -> next == NULL) && (index != 0)){
                                printf("Index does not exist is the bounds of the list. Try again\n");
                                return NULL;
                        } else{
                                head = head -> next;
                                index--;
                        }
                }
        }

        return head;
}

struct node_t * remove_val(struct node_t * head, int value)
{
        struct node_t * tmp;

        if (head == NULL){
                printf("Value cannot be found in an empty list. Try again\n");
                return NULL;
        } else{
                while(head != NULL){
                        if ((head -> next == NULL) && (head -> value != value)){
                                printf("The value does not exist in the list. Try again\n");
                                return NULL;
                        } else if (head -> next -> value == value){
                                tmp = head -> next;
                                head -> next = tmp -> next;
                                free(tmp);
                        } else{
                                head = head -> next;
                        }
                }
        }

        return head;
}

struct node_t * delete_node(struct node_t * head, int index)
{
        struct node_t * tmp;

        if (index < 0){
                printf("Index cannot be a negative number. Try again\n");
                return NULL;
        } else if (head == NULL){
                printf("Cannot delete elements from an empty list. Try again\n");
                return NULL;
        } else{
                while(head != NULL){
                        if ((head -> next == NULL) && (index != 0)){
                                printf("The index is not found in the bounds of the list. Try again\n");
                                return NULL;
                        } else if (index == 1){
                                tmp = head;
                                head = head -> next;
                                tmp -> next = head -> next;
                                head -> next = NULL;
                                free(head);
                                head = tmp;
                        } else{
                                head = head -> next;
                                index--;
                        }
                }
        }

        return head;
}

void print_list(struct node_t * head)
{
        if (head == NULL){
                printf("The list is empty. Nothing to print\n");
        } else{
                while(head != NULL){
                        if (head -> next != NULL){
                                printf("%d, ", head -> value);
                        } else{
                                printf("%d", head -> value);
                        }

                        head = head -> next;
                }
        }
}

основной файл:

#include <stdio.h>
#include <stdlib.h>
#include "func.h"

int main(void)
{
        struct node_t * head = NULL;
        int index, value;
        char choice;
        int cont = 0;

        while(cont == 0){
                printf("Welcome to the Linked List operator. Here are the functions that can be performed:\n");
                printf("A) Add element to the end of the list\n");
                printf("I) Insert and element at a specific index\n");
                printf("E) Check if the list is empty\n");
                printf("F) Find a value in the list and return the index\n");
                printf("G) Get the value at a specific index\n");
                printf("S) Replace the value at a specific index\n");
                printf("R) Remove the first occurance of a specific value\n");
                printf("D) Delete the element at a specific index\n");
                printf("L) List all the elements currently stored\n");
                printf("Q) Quit the program\n");
                printf("Please enter which action you would like to perform: ");
                scanf("%c", &choice);

                switch(choice){
                        case ADD:
                                printf("Please enter the value you would like to add: ");
                                scanf("%d", &value);

                                head = add_tail(head, value);

                                break;
                        case INSERT:
                                printf("Please enter the index at which you want to insert a new element: ");
                                scanf("%d", &index);
                                printf("Please enter the value you would like to insert: ");
                                scanf("%d", &value);

                                head = insert_node(head, index, value);

                                break;
                        case EMPTY:
                                if (is_empty(head) == 0){
                                        printf("The list is empty!\n");
                                } else if (is_empty(head) == 1){
                                        printf("The list is not empty!\n");
                                } else{
                                        printf("Something went wrong\n");
                                }

                                break;
                        case FIND:
                                printf("Please enter the value that you would like to find in the list: ");
                                scanf("%d", &value);

                                index = find_val(head, value);

                                if (index == FAIL){
                                        printf("Error. Try again\n");
                                } else{
                                        printf("The index that the value %d exists at is %d\n", value, index);
                                }

                                break;
                        case GET:
                                printf("Please enter the index for which you would like to know the value: ");
                                scanf("%d", &index);

                                if (value == FAIL){
                                        printf("Error. Try again\n");
                                } else{
                                        printf("The value of the element at index %d is %d\n", index, value);
                                }

                                break;
                        case REPLACE:
                                printf("Please enter the index of the element that you would like to replace: ");
                                scanf("%d", &index);
                                printf("Please enter the new value: ");
                                scanf("%d", &value);

                                if (replace_val(head, index, value) == NULL){
                                        printf("Error. Could not replace node\n");
                                } else{
                                        printf("Success. Here is the new list:\n");
                                        print_list(head);
                                }

                                break;
                        case REMOVE:
                                printf("Please enter the value that you would like to remove the first occurance of: ");
                                scanf("%d", &value);

                                if (remove_val(head, value) == NULL){
                                        printf("Error. Could not remove node\n");
                                } else{
                                        printf("Success! Here is the new list:\n");
                                        print_list(head);
                                }

                                break;
                        case DELETE:
                                printf("Please enter the index of the element you would like to delete: ");
                                scanf("%d", &index);

                                if (delete_node(head, index) == NULL){
                                        printf("Error. Could not delete selected element\n");
                                } else{
                                        printf("Success! Here is the new list:\n");
                                        print_list(head);
                                }

                                break;
                        case LIST:
                                printf("[");
                                print_list(head);
                                printf("]\n");

                                break;
                        case QUIT:
                                printf("You have chosen to quit the program. Goodbye!\n");
                                cont = 1;

                                break;
                        default:
                                printf("You entered an invalid choice. Please try again. Goodbye!\n");
                }
        }

        return 0;
}

Пожалуйста, предоставьте минимальную программу с функцией, которая, по вашему мнению, не работает.

— Vlad from Moscow 05.04.2023 20:43

Вы можете спросить себя: когда while(head != NULL){ внутри add_tail остановится? Или вы также можете пройти через это с помощью отладчика, это должно помочь. И return head тоже может быть не очень хорошей идеей.

— teapot418 05.04.2023 20:52

Поместите оператор printf выше tmp = create_node(value); в add_tail, и вы увидите, что у вас есть бесконечный цикл.

— Fiddling Bits 05.04.2023 21:00

Примечание: стилистически замените все (например) x -> y на x->y. Оператор стрелки (-->) имеет жесткую привязку. Ни один опытный программист не будет ставить вокруг него пробелы.

— Craig Estey 06.04.2023 02:22
c while-loop linked-list singly-linked-list function-definition
05.04.2023 20:34
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
2
4
68
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Ответ принят как подходящий

Это оператор if внутри функции add_tail

    if (head == NULL){
            printf("Cannot add tail to an empty list. Try again\n");
            return NULL;

не имеет смысла. Его следует удалить.

В цикле while в функции изменяется указатель head.

while(head != NULL){
        if (head -> next == NULL){
                tmp = create_node(value);
                head -> next = tmp;
        } else{
                head = head -> next;
        }
}

И после добавления узла цикл не прерывается. Он снова добавит новый узел. То есть цикл бесконечен.

Но даже если вы вставите оператор break

while(head != NULL){
        if (head -> next == NULL){
                tmp = create_node(value);
                head -> next = tmp;
                break;
        } else{
                head = head -> next;
        }
}

возвращаемый указатель из функции не будет указателем, указывающим на головной узел списка.

Функция может быть определена следующим образом

struct node_t * add_tail( struct node_t *head, int value )
{
    struct node_t *new_node = create_node( value );

    if ( head == NULL )
    {
        head = new_node;
    }
    else
    {
        struct node_t *current = head;
        
        while ( current->next != NULL ) current = current->next;

        current->next = new_node;
    }

    return head;
}

Я уверен, что в вашей программе есть и другие проблемы с вашим кодом. Вы можете задать новый вопрос после обновления функции add_tail, на которую вы ссылаетесь в этом своем вопросе.

@teapot418 По правде говоря, у меня нет никакого желания изучать весь его код. :) Он должен предоставить минимальную программу, демонстрирующую проблему. Пусть он задаст новый вопрос относительно другой проблемы. Ему это будет полезно.

— Vlad from Moscow 05.04.2023 21:00
05.04.2023 20:53

Примечание. У OP было несколько вопросов, связанных с этим:

  1. Реализация одного связанного списка на C с использованием рекурсии: что я делаю не так?
  2. Проблемы со связанным списком в C Этот вопрос!
  3. Ошибка сегментации при изменении связанного списка

(3) это вопрос, на который я хотел бы ответить, но он был закрыт до того, как я смог это сделать. Итак, я отвечаю на него здесь. Код аналогичен (и я взял код примера из (3)).

К сожалению, было много проблем...

  1. add_tail было if (head == NULL), что было плохо (и могло привести к ошибке).
  2. Как правило, нет необходимости в особых случаях пустых списков или списков с одним элементом (что имело место в ряде функций).
  3. В insert_node не было ясно, должна ли вставка происходить до или после заданного индекса вставки (в приведенном ниже коде было выбрано «до»).
  4. Логика цикла в большинстве функций была слишком сложной [и подверженной ошибкам].
  5. В функциях, которые могут дать сбой (т. е. функциях, которые не находят индекс или значение), возврат NULL вместо head является ошибкой. Он пропускает весь список.
  6. scanf для choice был нарушен (например, это должно было быть scanf(" %s",&choice); [обратите внимание на дополнительный пробел].
  7. Слишком много реплицированного кода в main для получения пользовательского ввода (см. использование функций get* в коде ниже).
  8. Из-за подсказок для ввода от stdin сложно воспроизвести данную ошибку (например, сохранить входные данные в файле, который используется (например) ./myprogram < inp.txt).

Вот рефакторинг кода. Это аннотировано с ошибками и исправлениями. Я перекодировал все функции и протестировал некоторые, но не все.

Некоторые функции, которые терпят неудачу по индексу или значению, не найденному, пустому списку и т. д., по-прежнему нуждаются в некоторой очистке.

Я добавил функции getstr и getval, чтобы улучшить тестирование воспроизведения.

#include <stdio.h>
#include <stdlib.h>
#if 1
#include <ctype.h>
#include <termios.h>
#include <string.h>
#endif

#define ADD 'A'
#define INSERT 'I'
#define DELETE 'D'
#define REMOVE 'R'
#define REPLACE 'S'
#if 1
#define PRINT 'P'
#endif

struct node_t {
    struct node_t *next;
    int value;
};

struct node_t *create_node(int value);
struct node_t *add_tail(struct node_t *head, int value);
struct node_t *insert_node(struct node_t *head, int index, int value);
#if 0
struct node_t *replace_val(struct node_t *head, int index, int value);
#else
struct node_t *replace_index(struct node_t *head, int index, int value);
#endif
struct node_t *remove_val(struct node_t *head, int value);
struct node_t *delete_node(struct node_t *head, int index);
void print_list(struct node_t *head);
#if 1
char *getstr(const char *prompt);
int getnum(const char *prompt);
#endif

#ifndef DOABORT
#define DOABORT     1
#endif

int
main(void)
{
    struct node_t *head = NULL;
    int index, value;
    char *choice;
    int cont = 0;

    while (cont == 0) {
        printf("\nWelcome to the Linked List operator.\nHere are the functions that can be performed:\n");
        printf("A) Add element to the end of the list\n");
        printf("I) Insert and element at a specific index\n");
        printf("S) Replace the value at a specific index\n");
        printf("R) Remove the first occurance of a specific value\n");
        printf("D) Delete the element at a specific index\n");
        printf("P) Print the list\n");

        choice = getstr("Please enter which action you would like to perform: ");
        if (choice == NULL)
            break;

        choice[0] = toupper((unsigned char) choice[0]);

        switch (choice[0]) {
        case ADD:
            value = getnum("Please enter the value you would like to add: ");
            head = add_tail(head, value);
            break;

        case INSERT:
            index = getnum("Please enter the index at which you want to insert a new element: ");
            value = getnum("Please enter the value you would like to insert: ");

            head = insert_node(head, index, value);
            break;

        case REPLACE:
            index = getnum("Please enter the index of the element that you would like to replace: ");
            value = getnum("Please enter the new value: ");

            if (replace_index(head, index, value) == NULL) {
                printf("Error. Could not replace node\n");
            }
            else {
                printf("Success. Here is the new list:\n");
                print_list(head);
            }
            break;

        case REMOVE:
            value = getnum("Please enter the value that you would like to remove the first occurance of: ");

            if (remove_val(head, value) == NULL) {
                printf("Error. Could not remove node\n");
            }
            else {
                printf("Success! Here is the new list:\n");
                print_list(head);
            }
            break;

        case DELETE:
            index = getnum("Please enter the index of the element you would like to delete: ");

            if (delete_node(head, index) == NULL) {
                printf("Error. Could not delete selected element\n");
            }
            else {
                printf("Success! Here is the new list:\n");
                print_list(head);
            }
            break;

        case PRINT:
            print_list(head);
            break;

        default:
            printf("You entered an invalid choice. Please try again. Goodbye!\n");
            break;
        }
    }

    return 0;
}

//create a new node
struct node_t *
create_node(int value)
{
    struct node_t *new_node = malloc(sizeof(struct node_t));

    new_node->next = NULL;
    new_node->value = value;

    return new_node;
}

//insert an element at the end of the list
struct node_t *
add_tail(struct node_t *head, int value)
{
    struct node_t *tmp;

#if 0
// NOTE/BUG: this is a defect and returning NULL is _not_ the solution
// NOTE/BUG: no need to special case this
    if (head == NULL) {
        printf("Cannot add tail to an empty list. Try again\n");
        head = NULL;
    }
// NOTE/BUG: changing head to head->next breaks the list
    else {
        while (head != NULL) {
            if (head->next == NULL) {
                tmp = create_node(value);
                head->next = tmp;
            }
            else {
                head = head->next;
            }
        }
    }
#else
    // create the new node
    tmp = create_node(value);

    // find the tail of the list
    struct node_t *tail = NULL;
    for (struct node_t *cur = head;  cur != NULL;  cur = cur->next)
        tail = cur;

    // add to tail of non-empty list
    if (tail != NULL)
        tail->next = tmp;
    // add to empty list
    else
        head = tmp;
#endif

    return head;
}

//insert a new element at index i
struct node_t *
insert_node(struct node_t *head, int index, int value)
{
    struct node_t *tmp;

    if (index < 0) {
        printf("Index cannot be a negative number. Please try again\n");
        return head;
    }

// NOTE/BUG: it's unclear whether inserting _at_ a given index is inserting
// _before_ this index or _after_ -- we have to choose so we'll choose "before"
// [below]

#if 0
// NOTE/BUG: no need to special case
    if (index == 0) {
        tmp = head;
        head = create_node(value);
        head->next = tmp;
    }
    else {
        tmp = head;

        while (tmp != NULL) {
// NOTE/BUG: no need to special case this
            if (index == 1) {
                struct node_t *prev = tmp;

                tmp = tmp->next;
                new = create_node(value);
                new->next = tmp;
                prev->next = new;
                head = prev;
            }
            else if ((tmp->next == NULL) && (index != 0)) {
                printf("The index is not found in the bounds of the list. Try again\n");
                return head;
            }
            else {
                tmp = tmp->next;
                index--;
            }
        }
    }
#else
// NOTE/FIX: we insert _before_ index (so we can insert before the head with 0)
    // create new node
    tmp = create_node(value);

    // find the Nth index and insert before it
    struct node_t *cur = head;
    struct node_t *prev = NULL;
    int curidx = 0;
    for (;  cur != NULL;  cur = cur->next, ++curidx) {
        if (curidx == index) {
            if (prev != NULL)
                prev->next = tmp;
            else
                head = tmp;
            tmp->next = cur;
            break;
        }

        prev = cur;
    }

    do {
        // we did the insert in above loop
        if (cur != NULL)
            break;

        // no index found
        // we can add to tail (or abort)
        if (prev != NULL)
            prev->next = tmp;
        else
            head = tmp;
    } while (0);
#endif

    return head;
}

//replace the value of the element at index i
struct node_t *
replace_index(struct node_t *head, int index, int value)
{

    if (index < 0) {
        printf("Index cannot be a negative number. Try again\n");
        exit(1);
    }
    else if (head == NULL) {
        printf("Cannot replace elements in an empty list. Try again\n");
        exit(1);
    }

#if 0
// NOTE/BUG: changing head to head->next breaks the list
// NOTE/BUG: no need to free head -- this leaks memory and is undefined behavior
// NOTE/BUG: doing tmp = head before this does _not_ fix this
    else {
        while (head != NULL) {
            if (index == 0) {
                tmp = head;
                tmp->value = value;
                free(head);
                head = tmp;
            }
            else if ((head->next == NULL) && (index != 0)) {
                printf("Index does not exist is the bounds of the list. Try again\n");
                exit(1);
            }
            else {
                head = head->next;
                index--;
            }
        }
    }
#else
    struct node_t *cur = head;
    int curidx = 0;
    for (;  cur != NULL;  cur = cur->next, ++curidx) {
        if (curidx == index) {
            cur->value = value;
            break;
        }
    }

    // we could _not_ find the correct index -- abort or just ignore?
    // NOTE: with a boolean return, we could just return true if the index
    // was found
#if DOABORT
    if (cur == NULL) {
        printf("replace_index: index=%d not found\n",index);
        exit(1);
    }
#endif
#endif

    return head;
}

//remove the first occurance of a value x in the list
struct node_t *
remove_val(struct node_t *head, int value)
{

#if 0
// NOTE/BUG: removing by value in an empty list _is_ valid
    if (head == NULL) {
        printf("Value cannot be found in an empty list. Try again\n");
        return NULL;
    }
// NOTE/BUG: changing head to head->next breaks the list
    else {
        while (head != NULL) {
            if ((head->next == NULL) && (head->value != value)) {
                printf("The value does not exist in the list. Try again\n");
                return NULL;
            }
            else if (head->next->value == value) {
                tmp = head->next;
                head->next = tmp->next;
                free(tmp);
            }
            else {
                head = head->next;
            }
        }
    }
#else
    struct node_t *next;
    struct node_t *prev = NULL;
    struct node_t *cur = head;
    for (;  cur != NULL;  cur = next) {
        next = cur->next;

        if (cur->value == value) {
            if (prev != NULL)
                prev->next = next;
            else
                head = next;
            free(cur);
            break;
        }

        prev = cur;
    }

    // same issue as above -- do we abort of just ignore
#if DOABORT
    if (cur == NULL) {
        printf("remove_val: value=%d not found\n",value);
        exit(1);
    }
#endif
#endif

    return head;
}

//delete the node at index i
struct node_t *
delete_node(struct node_t *head, int index)
{

    if (index < 0) {
        printf("Index cannot be a negative number. Try again\n");
        return NULL;
    }

#if 0
// NOTE/BUG: no need to special case an empty list
    else if (head == NULL) {
        printf("Cannot delete elements from an empty list. Try again\n");
        return NULL;
    }
    else {
        while (head != NULL) {
            if ((head->next == NULL) && (index != 0)) {
                printf("The index is not found in the bounds of the list. Try again\n");
                return NULL;
            }
            else if (index == 1) {
                tmp = head;
                head = head->next;
                tmp->next = head->next;
                head->next = NULL;
                free(head);
                head = tmp;
            }
            else {
                head = head->next;
                index--;
            }
        }
    }
#else
    struct node_t *cur = head;
    struct node_t *next;
    struct node_t *prev = NULL;
    int curidx = 0;
    for (;  cur != NULL;  cur = next, ++curidx) {
        next = cur->next;

        if (curidx == index) {
            if (prev != NULL)
                prev->next = next;
            else
                head = next;
            break;
        }

        prev = cur;
    }

#if DOABORT
    if (cur == NULL) {
        printf("delete_node: index=%d not found\n",index);
        exit(1);
    }
#endif
#endif

    return head;
}

//print elements of the list
void
print_list(struct node_t *head)
{
    if (head == NULL) {
        printf("The list is empty. Nothing to print\n");
    }
#if 0
    else {
        while (head != NULL) {
            if (head->next == NULL) {
                printf("%d", head->value);
            }
            else {
                printf("%d, ", head->value);
                head = head->next;
            }
        }
    }
#else
    for (struct node_t *cur = head;  cur != NULL;  cur = cur->next) {
        if (cur != head)
            printf(", ");
        printf("%d",cur->value);
    }
    printf("\n");
#endif
}

#if 1
char *
getstr(const char *prompt)
{
    static char buf[100];
    char *bp;

    // echo input if _not_ a TTY
    static int echoflg = -1;
    if (echoflg < 0) {
        struct termios tio;
        echoflg = (tcgetattr(fileno(stdin),&tio) < 0);
    }

    while (1) {
        printf("%s",prompt);
        fflush(stdout);

        bp = fgets(buf,sizeof(buf),stdin);

        if (bp == NULL) {
            if (echoflg)
                printf("EOF\n");
            break;
        }

        if (echoflg)
            fputs(buf,stdout);

        buf[strcspn(buf,"\n")] = 0;

        // stop if _not_ blank line
        if (buf[0] != 0)
            break;
    }

    return bp;
}

int
getnum(const char *prompt)
{
    char *buf = getstr(prompt);
    int val = -1;

    if (buf != NULL)
        val = strtol(buf,&buf,10);

    return val;
}
#endif

В приведенном выше коде я использовал условные обозначения cpp для обозначения старого и нового кода:

#if 0
// old code
#else
// new code
#endif

#if 1
// new code
#endif

Примечание: это можно исправить, запустив файл через unifdef -k

Вот пример входного файла, который я использовал:

a
1

a
2

a
3

a
4

a
5

a
6

a
7

p

r
5

d
5

s
4
9

Вот пример вывода для этого входного файла:


Welcome to the Linked List operator.
Here are the functions that can be performed:
A) Add element to the end of the list
I) Insert and element at a specific index
S) Replace the value at a specific index
R) Remove the first occurance of a specific value
D) Delete the element at a specific index
P) Print the list
Please enter which action you would like to perform: a
Please enter the value you would like to add: 1

Welcome to the Linked List operator.
Here are the functions that can be performed:
A) Add element to the end of the list
I) Insert and element at a specific index
S) Replace the value at a specific index
R) Remove the first occurance of a specific value
D) Delete the element at a specific index
P) Print the list
Please enter which action you would like to perform:
Please enter which action you would like to perform: a
Please enter the value you would like to add: 2

Welcome to the Linked List operator.
Here are the functions that can be performed:
A) Add element to the end of the list
I) Insert and element at a specific index
S) Replace the value at a specific index
R) Remove the first occurance of a specific value
D) Delete the element at a specific index
P) Print the list
Please enter which action you would like to perform:
Please enter which action you would like to perform: a
Please enter the value you would like to add: 3

Welcome to the Linked List operator.
Here are the functions that can be performed:
A) Add element to the end of the list
I) Insert and element at a specific index
S) Replace the value at a specific index
R) Remove the first occurance of a specific value
D) Delete the element at a specific index
P) Print the list
Please enter which action you would like to perform:
Please enter which action you would like to perform: a
Please enter the value you would like to add: 4

Welcome to the Linked List operator.
Here are the functions that can be performed:
A) Add element to the end of the list
I) Insert and element at a specific index
S) Replace the value at a specific index
R) Remove the first occurance of a specific value
D) Delete the element at a specific index
P) Print the list
Please enter which action you would like to perform:
Please enter which action you would like to perform: a
Please enter the value you would like to add: 5

Welcome to the Linked List operator.
Here are the functions that can be performed:
A) Add element to the end of the list
I) Insert and element at a specific index
S) Replace the value at a specific index
R) Remove the first occurance of a specific value
D) Delete the element at a specific index
P) Print the list
Please enter which action you would like to perform:
Please enter which action you would like to perform: a
Please enter the value you would like to add: 6

Welcome to the Linked List operator.
Here are the functions that can be performed:
A) Add element to the end of the list
I) Insert and element at a specific index
S) Replace the value at a specific index
R) Remove the first occurance of a specific value
D) Delete the element at a specific index
P) Print the list
Please enter which action you would like to perform:
Please enter which action you would like to perform: a
Please enter the value you would like to add: 7

Welcome to the Linked List operator.
Here are the functions that can be performed:
A) Add element to the end of the list
I) Insert and element at a specific index
S) Replace the value at a specific index
R) Remove the first occurance of a specific value
D) Delete the element at a specific index
P) Print the list
Please enter which action you would like to perform:
Please enter which action you would like to perform: p
1, 2, 3, 4, 5, 6, 7

Welcome to the Linked List operator.
Here are the functions that can be performed:
A) Add element to the end of the list
I) Insert and element at a specific index
S) Replace the value at a specific index
R) Remove the first occurance of a specific value
D) Delete the element at a specific index
P) Print the list
Please enter which action you would like to perform:
Please enter which action you would like to perform: r
Please enter the value that you would like to remove the first occurance of: 5
Success! Here is the new list:
1, 2, 3, 4, 6, 7

Welcome to the Linked List operator.
Here are the functions that can be performed:
A) Add element to the end of the list
I) Insert and element at a specific index
S) Replace the value at a specific index
R) Remove the first occurance of a specific value
D) Delete the element at a specific index
P) Print the list
Please enter which action you would like to perform:
Please enter which action you would like to perform: d
Please enter the index of the element you would like to delete: 5
Success! Here is the new list:
1, 2, 3, 4, 6

Welcome to the Linked List operator.
Here are the functions that can be performed:
A) Add element to the end of the list
I) Insert and element at a specific index
S) Replace the value at a specific index
R) Remove the first occurance of a specific value
D) Delete the element at a specific index
P) Print the list
Please enter which action you would like to perform:
Please enter which action you would like to perform: s
Please enter the index of the element that you would like to replace: 4
Please enter the new value: 9
Success. Here is the new list:
1, 2, 3, 4, 9

Welcome to the Linked List operator.
Here are the functions that can be performed:
A) Add element to the end of the list
I) Insert and element at a specific index
S) Replace the value at a specific index
R) Remove the first occurance of a specific value
D) Delete the element at a specific index
P) Print the list
Please enter which action you would like to perform: EOF

ОБНОВЛЯТЬ:

Одна из вышеперечисленных проблем заключается в том, что функции, которые ищут узлы, могут дать сбой. То есть совпадений не найдено. Как сообщить об этом вызывающему абоненту?

Для связанных списков существует три основных способа возврата обновленного head вызывающему объекту:

// current way ...
node_t *
add_tail(node_t *head,int value)
{

    // do stuff and update head ...

    return head;
}

// double pointer to head ...
void
add_tail(node_t **head,int value)
{

    // do stuff and update *head ...
}

// use of list struct ...
void
add_tail(list_t *list,int value)
{

    // do stuff and update list->head ...
}

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

Поскольку функциям больше не нужно возвращать обновленное значение head через return head;, мы можем переопределить возвращаемое значение как логическое значение «успех» (т. е. 0 = неудача, 1 = успех).

Еще одно преимущество заключается в том, что вызывающему объекту функции связанного списка не нужно знать, будет ли функция обновляться head или нет. Он просто передает указатель списка, и данная функция может делать все, что пожелает.

Вот версия, перекодированная для использования «настоящего» списка (она также была пропущена через unifdef -k):

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

#define ADD 'A'
#define INSERT 'I'
#define DELETE 'D'
#define REMOVE 'R'
#define REPLACE 'S'
#define PRINT 'P'

typedef struct node node_t;
struct node {
    node_t *next;
    int value;
};

typedef struct {
    node_t *head;
    int count;
} list_t;

node_t *create_node(int value);
void add_tail(list_t *list, int value);
int insert_node(list_t *list, int index, int value);
int replace_index(list_t *list, int index, int value);
int remove_val(list_t *list, int value);
int delete_node(list_t *list, int index);
void print_list(list_t *list);
char *getstr(const char *prompt);
int getnum(const char *prompt);

#ifndef DOABORT
#define DOABORT     1
#endif

int
main(void)
{
    list_t *list = calloc(1,sizeof(*list));
    int index, value;
    char *choice;
    int cont = 0;

    while (cont == 0) {
        printf("\nWelcome to the Linked List operator.\nHere are the functions that can be performed:\n");
        printf("A) Add element to the end of the list\n");
        printf("I) Insert and element at a specific index\n");
        printf("S) Replace the value at a specific index\n");
        printf("R) Remove the first occurance of a specific value\n");
        printf("D) Delete the element at a specific index\n");
        printf("P) Print the list\n");

        choice = getstr("Please enter which action you would like to perform: ");
        if (choice == NULL)
            break;

        choice[0] = toupper((unsigned char) choice[0]);

        switch (choice[0]) {
        case ADD:
            value = getnum("Please enter the value you would like to add: ");
            add_tail(list, value);
            break;

        case INSERT:
            index = getnum("Please enter the index at which you want to insert a new element: ");
            value = getnum("Please enter the value you would like to insert: ");

            insert_node(list, index, value);
            break;

        case REPLACE:
            index = getnum("Please enter the index of the element that you would like to replace: ");
            value = getnum("Please enter the new value: ");

            if (replace_index(list, index, value) == 0) {
                printf("Error. Could not replace node\n");
            }
            else {
                printf("Success. Here is the new list:\n");
                print_list(list);
            }
            break;

        case REMOVE:
            value = getnum("Please enter the value that you would like to remove the first occurance of: ");

            if (remove_val(list, value) == 0) {
                printf("Error. Could not remove node\n");
            }
            else {
                printf("Success! Here is the new list:\n");
                print_list(list);
            }
            break;

        case DELETE:
            index = getnum("Please enter the index of the element you would like to delete: ");

            if (delete_node(list, index) == 0) {
                printf("Error. Could not delete selected element\n");
            }
            else {
                printf("Success! Here is the new list:\n");
                print_list(list);
            }
            break;

        case PRINT:
            print_list(list);
            break;

        default:
            printf("You entered an invalid choice. Please try again. Goodbye!\n");
            break;
        }
    }

    return 0;
}

//create a new node
node_t *
create_node(int value)
{
    node_t *new_node = malloc(sizeof(node_t));

    new_node->next = NULL;
    new_node->value = value;

    return new_node;
}

//insert an element at the end of the list
void
add_tail(list_t *list, int value)
{
    node_t *tmp;

    // create the new node
    tmp = create_node(value);

    // find the tail of the list
    node_t *tail = NULL;
    for (node_t *cur = list->head;  cur != NULL;  cur = cur->next)
        tail = cur;

    // add to tail of non-empty list
    if (tail != NULL)
        tail->next = tmp;
    // add to empty list
    else
        list->head = tmp;
}

//insert a new element at index i
int
insert_node(list_t *list, int index, int value)
{
    node_t *tmp;

    if (index < 0) {
        printf("Index cannot be a negative number. Please try again\n");
        return 0;
    }

    // create new node
    tmp = create_node(value);

    // find the Nth index and insert before it
    node_t *cur = list->head;
    node_t *prev = NULL;
    int curidx = 0;
    for (;  cur != NULL;  cur = cur->next, ++curidx) {
        if (curidx == index) {
            if (prev != NULL)
                prev->next = tmp;
            else
                list->head = tmp;
            tmp->next = cur;
            break;
        }

        prev = cur;
    }

    do {
        // we did the insert in above loop
        if (cur != NULL)
            break;

        // no index found
        // we can add to tail (or abort)
        if (prev != NULL)
            prev->next = tmp;
        else
            list->head = tmp;
    } while (0);

    return 1;
}

//replace the value of the element at index i
int
replace_index(list_t *list, int index, int value)
{

    if (index < 0) {
        printf("Index cannot be a negative number. Try again\n");
        return 0;
    }
    else if (list->head == NULL) {
        printf("Cannot replace elements in an empty list. Try again\n");
        return 0;
    }

    node_t *cur = list->head;
    int curidx = 0;
    for (;  cur != NULL;  cur = cur->next, ++curidx) {
        if (curidx == index) {
            cur->value = value;
            break;
        }
    }

    if (cur == NULL) {
        printf("replace_index: index=%d not found\n",index);
        return 0;
    }

    return 1;
}

//remove the first occurance of a value x in the list
int
remove_val(list_t *list, int value)
{

    node_t *next;
    node_t *prev = NULL;
    node_t *cur = list->head;
    for (;  cur != NULL;  cur = next) {
        next = cur->next;

        if (cur->value == value) {
            if (prev != NULL)
                prev->next = next;
            else
                list->head = next;
            free(cur);
            break;
        }

        prev = cur;
    }

    // same issue as above -- do we abort of just ignore
    if (cur == NULL) {
        printf("remove_val: value=%d not found\n",value);
        return 0;
    }

    return 1;
}

//delete the node at index i
int
delete_node(list_t *list, int index)
{

    if (index < 0) {
        printf("Index cannot be a negative number. Try again\n");
        return 0;
    }

    node_t *cur = list->head;
    node_t *next;
    node_t *prev = NULL;
    int curidx = 0;
    for (;  cur != NULL;  cur = next, ++curidx) {
        next = cur->next;

        if (curidx == index) {
            if (prev != NULL)
                prev->next = next;
            else
                list->head = next;
            break;
        }

        prev = cur;
    }

    if (cur == NULL) {
        printf("delete_node: index=%d not found\n",index);
        return 0;
    }

    return 1;
}

//print elements of the list
void
print_list(list_t *list)
{
    node_t *cur = list->head;

    if (cur == NULL)
        printf("The list is empty. Nothing to print");

    for (;  cur != NULL;  cur = cur->next) {
        if (cur != list->head)
            printf(", ");
        printf("%d",cur->value);
    }

    printf("\n");
}

char *
getstr(const char *prompt)
{
    static char buf[100];
    char *bp;

    // echo input if _not_ a TTY
    static int echoflg = -1;
    if (echoflg < 0) {
        struct termios tio;
        echoflg = (tcgetattr(fileno(stdin),&tio) < 0);
    }

    while (1) {
        printf("%s",prompt);
        fflush(stdout);

        bp = fgets(buf,sizeof(buf),stdin);

        if (bp == NULL) {
            if (echoflg)
                printf("EOF\n");
            break;
        }

        if (echoflg)
            fputs(buf,stdout);

        buf[strcspn(buf,"\n")] = 0;

        // stop if _not_ blank line
        if (buf[0] != 0)
            break;
    }

    return bp;
}

int
getnum(const char *prompt)
{
    char *buf = getstr(prompt);
    int val = -1;

    if (buf != NULL)
        val = strtol(buf,&buf,10);

    return val;
}
07.04.2023 01:48

Другие вопросы по теме

Переключите и во время комбинации с помощью scanf, как избежать множественного ввода
Упрощение кода для размещения кораблей в игре Морской бой на Python и проведение модульного тестирования
Почему этот массив не сохраняет отсканированные числа?
Как вернуть логическое значение в Java
Проверка положительности элементов, введенных пользователем в массив
Бесконечный цикл в питоне
Python, выход из цикла While с пользовательским вводом с использованием многопоточности (cntrl+c не работает)
Как рассчитать время этой петли
Как постоянно обновлять переменную в колбе
Параллельная обработка для установки начального числа в R

Похожие вопросы

Почему мой реверсивный аудиокод для CS50 не работает?
Как проверить значение макроса со скобками и приведением типов во время компиляции?
Переключите и во время комбинации с помощью scanf, как избежать множественного ввода
Правильное построение AST в C
Запись и чтение файла в двоичном формате
Самый быстрый способ реализовать _mm256_mullo_epi4 с использованием AVX2
Как я могу улучшить использование типа данных с фиксированной точкой?
Которые определяют диапазон целочисленных типов в языке c
Как я могу скопировать строку в указатель массива символов?
Почему этот массив не сохраняет отсканированные числа?