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

问题描述 投票：0回答：2

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

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

  • isempty()：如果列表为空则返回真，否则返回真。
  • 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;
}
c recursion singly-linked-list
2个回答
1
投票

当你在索引 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. 使用输入/输出参数将列表头传送给函数并使其能够直接设置新头：

    void insert_node(struct node_t **head, int index, int value) {
    // ... Work with *head ...

    // where appropriate:
    *head = new_head;
}
  1. (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 时才停止。

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

0
投票

@kei_cse_26 诚然，当我开始工作时，这对我来说变得比我原先想象的要复杂一些。 IMO，你应该有一个对索引进行递归搜索的函数（并且只有递归搜索），然后你可以调用它来帮助执行你需要的所有其他操作（插入、删除、修改等）。这可能并不总是最有效的，但我认为这至少是最直接的。这就是递归搜索所需的全部：

struct node_t* findNodeRecursive(struct node_t* head, int index)
{
    if (index == 0)
    {
        // here's the index we care about
        return head;
    }
    else if (index < 0)  // if index is unsigned you don't need to worry about this
    {
        return NULL;
    }
    else if (head != NULL)
    {
        return findNodeRecursive(head->next, index-1);
    }
    // else, head is NULL
    return NULL;
}

这是

insert_node
的可能实现。我用过 John Bollinger 的 1):

struct node_t* insert_node(struct node_t* head, int index, int value)
{
    if (index <= 0)  // treat negative index as 0
    {
        // special case, insert at the beginning
        if (head == NULL)
        {
            // nothing in the list yet
            head = create_node(value);
        }
        else
        {
            // head already exists, insert at new head
            struct node_t* newHead = create_node(value);
            newHead->next = head;
            head = newHead;            
        }
    }
    else
    {
        // find the previous index
        struct node_t* prevNode = findNodeRecursive(head, index-1);
        if (prevNode != NULL)
        {
            // prev node exists
            // create new node to insert
            struct node_t* newNode = create_node(value);
            // check for error
            // insert the new node
            newNode->next = prevNode->next;
            prevNode->next = newNode;
        }
    }

    return head;
}

如果可能，我会将索引更改为 

unsigned
或 
size_t
，因为负索引没有意义（并且会为您节省一些错误检查）。这是 insert_node 的 
端到端演示
。您可以使用相同的
findNodeRecursive
功能来帮助您擦除和修改节点。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.