使用递归在 C 中实现单链表：我做错了什么？

我试图编写的程序的提示是这样的：

创建一个链表和一组操作它的函数。所有循环 必须使用递归来完成。以下功能是 该列表将使用的函数：

• isempty()：如果列表为空则返回true，否则返回true。
• find(v)：查找某个值并返回其索引。如果不成功，则返回一个指示失败的值。这将需要 递归。
• add(v)：将值为 v 的项目添加到列表的尾部
• insert(i, e)：在索引 i 处插入元素 e。这将需要递归。
• delete(n)：删除索引n处的元素。如果不成功，则返回一个指示失败的值。这将需要递归。
• remove(v)：删除某个值的第一个实例。如果不成功，则返回一个指示失败的值。这将需要 递归。
• Replace(i, v)：用值 v 替换索引 i 处的值。这将需要递归。
• get(i)：获取索引 i 处的值。这将需要递归
• liststring()：返回列表的字符串，显示每个元素的值，格式如下：[value, value, ... , value]。 这将需要递归。

我以前写过一个与此类似的程序，但我从未使用递归来导航链接列表。我尝试调整为链接列表编写的原始代码，但每次运行程序时都会出现内存泄漏和分段错误。我发现在尝试运行特定函数时会发生错误，因此我附加了插入节点函数、主函数和用于存储节点的结构。任何关于如何清理代码、更好地诊断我的问题或您注意到的错误的提示将不胜感激。

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

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

/**
 * @brief creates new node
 * 
 * @param value value to be stored in new node
 * @return pointer for new node
 */
struct node_t *create_node(int value) {
    struct node_t *node = (struct node_t *) malloc(sizeof(struct node_t));

    node->next = NULL;
    node->value = value;
    return node;
}

/**
 * @brief inserts node into linked list at index given by user
 * 
 * @param head pointer for node at front of linked list
 * @param index index/position of list to insert new node
 * @param value value to be stored in new node
 */
void insert_node(struct node_t *head, int index, int value) {
    struct node_t *tmp;

    if (index == 0) {
        tmp = head;
        head = create_node(value);
        head->next = tmp;
    } else if (head->next == NULL) {
        if (index == 0) {
            tmp = create_node(value);
            head->next = tmp;
            tmp->next = head->next->next;
        } else {
            printf("Index out of bounds.\n");
        }
    } else {
        if (index == 0) {
            tmp = create_node(value);
            head->next = tmp;
            tmp->next = head->next->next;
        } else {
            insert_node(head->next, index - 1, value);
        }
    }
}

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

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

    printf("Please enter the value you want to insert: ");
    scanf("%d", &value);

    insert_node(head, index, value);

    return 0;
}

当您将一个节点插入到列表的索引 0 处时，该节点将成为列表的新头节点。然而，这个函数签名...

void insert_node(struct node_t *head, int index, int value) {

...没有提供将新头节点传送回调用者的方法。因此，main()的头指针始终保持为空。解决此类问题有 2.5 种常用方法：

1. 返回新的头节点：

   struct node_t *insert_node(struct node_t *head, int index, int value)
   

   当然，这需要调用者对返回值做正确的事情。

2. 使用 in / out 参数将列表头传递给函数并使其能够直接设置新头：

   void insert_node(struct node_t **head, int index, int value) {
       // ... Work with *head ...
   
       // where appropriate:
       *head = new_head;
   }
   

2. (5.) 创建一个表示整个列表的结构，而不是使用裸头指针。使头指针成为该结构的成员，并将指针传递给列表结构：

   struct list {
       struct node_t *head;
       // and maybe other members, too, such as a tail pointer
   };
   
   void insert_node(struct list *list, int index, int value) {
       // ... Work with list->head ...
   
       // where appropriate:
       list->head = new_head;
   }
   

   这实际上只是 (2) 的改进，因为两者的要点是它们增加了额外的间接级别。

但这只是间接导致记忆错误的原因。直接原因是你的insert_node()函数假设index传递给它的值对于列表有效。当它在列表中向指定索引前进时，它不关心节点是否next指针为空，因此如果索引太大，它将尝试取消引用其中的空指针。或者，如果索引为负数，则它会在每次递归调用时递减索引，并且仅在达到索引 0 时停止。

您应该验证索引是否为非负数，并且在进行过程中应该注意列表的末尾。当索引无效时，您应该以某种方式指示错误，尽管我将详细信息留给您。