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

2024-04-03

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

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

  • 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;
    }
    
  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 时停止。

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

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

使用递归在 C 中实现单链表:我做错了什么? 的相关文章

  • 双线性序列给出奇数结果

    我试图让我的表现技能 不存在 达到标准 但在将公式写入代码时遇到了问题 这是我试图将其引用为 转换 为代码的公式 考虑一个序列 u 其中 u 定义如下 号码u 0 1是第一个u 对于每个x in u then y 2 x 1 and z 3
  • C语言中的递归是如何工作的?

    我试图了解 C 中递归的工作原理 任何人都可以给我解释控制流吗 include
  • 如何动态加载包含非托管代码的原始程序集?(绕过“无法验证的代码失败策略检查”异常)

    我将举一个使用的例子系统 Data SQLite DLL http sqlite phxsoftware com 这是一个包含非托管代码的混合程序集 如果我执行这个 var assembly Assembly LoadFrom System
  • 如何使用 ILoggerFactory 记录 Polly 的重试

    或者 如何从静态方法记录 From https github com App vNext Polly https github com App vNext Polly你有这样的例子 其中记录器神奇地可用 Policy Timeout 30
  • 如何在线程创建和退出时调用函数?

    include
  • Linux 使用 boost asio 拒绝套接字绑定权限

    我在绑定套接字时遇到问题 并且以用户身份运行程序时权限被拒绝 这行代码会产生错误 acceptor new boost asio ip tcp acceptor io boost asio ip tcp endpoint boost asi
  • 每次调用新方法时触发事件

    我正在做一个logger for a c 应用程序需要记录每个方法被调用的时间以及每个方法执行时间 我可以通过调用自己的方法来做到这一点EventLogger LogMethodCall方法在每个方法的开头 但我想知道是否有办法使CLR每次
  • 如何启动异步任务对象

    我想开始收集Task同时处理对象并等待所有对象完成 下面的代码显示了我想要的行为 public class Program class TaskTest private Task createPauseTask int ms works w
  • 无缝滚动瓷砖地图

    我正在开发一个自上而下的角色扮演游戏 并且想要实现无缝滚动地图 也就是说 当玩家探索世界时 地图之间没有加载屏幕 也没有通往下一个区域的 门 我有两种方法可以打破世界 在顶层 我有 区域 它只是 9 个 地图 的集合 这些区域仅由目录表示
  • StreamReader,C#,peek

    我有一个 StreamReader 它偶尔会检查它是否有更多内容可以从简单的文本文件中读取 它使用 peek 属性 问题是 当我使用 peek 时 位置发生了变化 尽管不应该发生 FileStream m fsReader new File
  • 在 C++ 中使用表达式模板进行符号微分

    如何在 C 中使用表达式模板实现符号微分 一般来说 您需要一种表示符号的方法 即编码的表达式模板 例如3 x x 42 以及一个可以计算导数的元函数 希望您对 C 中的元编程足够熟悉 知道这意味着什么和需要什么 但可以给您一个想法 This
  • 读取STM32 MCU SPI数据寄存器的值

    有很多类似的问题 但似乎没有一个问题完全相同 我正在将 STML4 MCU 连接到 6 轴传感器 LSM6DS3 我已经成功地在 I2C 中实现了所有内容 但想要 SPI 的额外速度 和 DMA 如果我能让这些第一步工作起来的话 因此 第一
  • WinForms - 表单大小错误

    我们有以下代码 private void MainForm Shown object sender EventArgs e RepositionForm private void RepositionForm Rectangle rect
  • 命名空间“Microsoft”中不存在类型或命名空间名称“Practices”

    我正在使用 Microsoft Visual Studio 2005 for c 我的代码中有以下命名空间 using Microsoft Practices EnterpriseLibrary using Microsoft Practi
  • 使用 INotifyPropertyChanged

    有人可以解释一下为什么在 wpf 中使用绑定时需要使用 INotifyPropertyChanged 的 实现吗 我可以在不实现此接口的情况下绑定属性吗 例如我有代码 public class StudentData INotifyProp
  • 将一个整数从 C 客户端发送到 Java 服务器

    我使用此代码将一个整数从我的 Java 客户端发送到我的 Java 服务器 int n rand nextInt 50 1 DataOutputStream dos new DataOutputStream socket getOutput
  • 按值返回的函数的返回语句中的初始化

    我的问题源于深入研究std move in return语句 例如以下示例 struct A A std cout lt lt Constructed lt lt this lt lt std endl A A noexcept std c
  • 该组件没有由 uri 标识的资源

    我想创建一个通用数据网格以在我的所有视图 用户控件上使用 这是我的结构 Class Library called Core Class called ViewBase public class ViewBase UserControl pu
  • C# Julian 日期解析器

    我在电子表格中有一个单元格 它是 Excel 中的日期对象 但当它来自 C1 的 xls 类时 它会变成双精度型 类似于 2009 年 1 月 7 日的 39820 0 我读到这是儒略日期格式 有人可以告诉我如何在 C 中将其解析回 Dat
  • 参数数量在编译时确定的 Lambda 函数

    我想声明一个带有 N 个参数的 lambda 函数 其中 N 是模板参数 就像是 template

随机推荐