使用递归在 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 中实现单链表:我做错了什么? 的相关文章

  • 删除文件的最后 10 个字符

    我想删除文件的最后 10 个字符 说一个字符串 hello i am a c learner 是文件内的数据 我只是希望该文件是 hello i am a 文件的最后 10 个字符 即字符串 c learner 应在文件内消除 解决方案 将
  • 如何将 std::string& 转换为 C# 引用字符串

    我正在尝试将 C 函数转换为std string参考C 我的 API 如下所示 void GetStringDemo std string str 理想情况下 我希望在 C 中看到类似的东西 void GetStringDemoWrap r
  • 如何在 Cassandra 中存储无符号整数?

    我通过 Datastax 驱动程序在 Cassandra 中存储一些数据 并且需要存储无符号 16 位和 32 位整数 对于无符号 16 位整数 我可以轻松地将它们存储为有符号 32 位整数 并根据需要进行转换 然而 对于无符号 64 位整
  • 如何连接重叠的圆圈?

    我想在视觉上连接两个重叠的圆圈 以便 becomes 我已经有部分圆的方法 但现在我需要知道每个圆的重叠角度有多大 但我不知道该怎么做 有人有主意吗 Phi ArcTan Sqrt 4 R 2 d 2 d HTH Edit 对于两个不同的半
  • 无限循环与无限递归。两者都是未定义的吗?

    无副作用的无限循环是未定义的行为 看here https coliru stacked crooked com view id 24e0a58778f67cd4举个例子参考参数 https en cppreference com w cpp
  • 需要帮助优化算法 - 两百万以下所有素数的总和

    我正在尝试做一个欧拉计划 http projecteuler net问题 我正在寻找 2 000 000 以下所有素数的总和 这就是我所拥有的 int main int argc char argv unsigned long int su
  • 方程“a + bx = c + dy”的积分解

    在等式中a bx c dy 所有变量都是整数 a b c and d是已知的 我如何找到整体解决方案x and y 如果我的想法是正确的 将会有无限多个解 由最小公倍数分隔b and d 但我只需要一个解决方案 我可以计算其余的 这是一个例
  • 两个静态变量同名(两个不同的文件),并在任何其他文件中 extern 其中一个

    在一个文件中将变量声明为 static 并在另一个文件中进行 extern 声明 我认为这会在链接时出现错误 因为 extern 变量不会在任何对象中看到 因为在其他文件中声明的变量带有限定符 static 但不知何故 链接器 瑞萨 没有显
  • 为什么这个字符串用AesCryptoServiceProvider第二次解密时不相等?

    我在 C VS2012 NET 4 5 中的文本加密和解密方面遇到问题 具体来说 当我加密并随后解密字符串时 输出与输入不同 然而 奇怪的是 如果我复制加密的输出并将其硬编码为字符串文字 解密就会起作用 以下代码示例说明了该问题 我究竟做错
  • C# xml序列化必填字段

    我需要将一些字段标记为需要写入 XML 文件 但没有成功 我有一个包含约 30 个属性的配置类 这就是为什么我不能像这样封装所有属性 public string SomeProp get return someProp set if som
  • 如何在当前 Visual Studio 主机内的 Visual Studio 扩展中调试使用 Roslyn 编译的代码?

    我有一个 Visual Studio 扩展 它使用 Roslyn 获取当前打开的解决方案中的项目 编译它并从中运行方法 程序员可以修改该项目 我已从当前 VisualStudioWorkspace 成功编译了 Visual Studio 扩
  • 为什么 isnormal() 说一个值是正常的,而实际上不是?

    include
  • 相当于Linux中的导入库

    在 Windows C 中 当您想要链接 DLL 时 您必须提供导入库 但是在 GNU 构建系统中 当您想要链接 so 文件 相当于 dll 时 您就不需要链接 为什么是这样 是否有等效的 Windows 导入库 注意 我不会谈论在 Win
  • C++ 中的参考文献

    我偶尔会在 StackOverflow 上看到代码 询问一些涉及函数的重载歧义 例如 void foo int param 我的问题是 为什么会出现这种情况 或者更确切地说 你什么时候会有 对参考的参考 这与普通的旧参考有何不同 我从未在现
  • C# 使用“?” if else 语句设置值这叫什么

    嘿 我刚刚看到以下声明 return name null name NA 我只是想知道这在 NET 中叫什么 是吗 代表即然后执行此操作 这是一个俗称的 条件运算符 三元运算符 http en wikipedia org wiki Tern
  • 指针和内存范围

    我已经用 C 语言编程有一段时间了 但对 C 语言还是很陌生 有时我对 C 处理内存的方式感到困惑 考虑以下有效的 C 代码片段 const char string void where is this pointer variable l
  • 类型或命名空间“MyNamespace”不存在等

    我有通常的类型或命名空间名称不存在错误 除了我引用了程序集 using 语句没有显示为不正确 并且我引用的类是公共的 事实上 我在不同的解决方案中引用并使用相同的程序集来执行相同的操作 并且效果很好 顺便说一句 这是VS2010 有人有什么
  • 从 mvc 控制器使用 Web api 控制器操作

    我有两个控制器 一个mvc控制器和一个api控制器 它们都在同一个项目中 HomeController Controller DataController ApiController 如果我想从 HomeController 中使用 Dat
  • 如何确定 CultureInfo 实例是否支持拉丁字符

    是否可以确定是否CultureInfo http msdn microsoft com en us library system globalization cultureinfo aspx我正在使用的实例是否基于拉丁字符集 我相信你可以使
  • 使用 WGL 创建现代 OpenGL 上下文?

    我正在尝试使用 Windows 函数创建 OpenGL 上下文 现代版本 基本上代码就是 创建窗口类 注册班级 创建一个窗口 choose PIXELFORMATDESCRIPTOR并设置它 创建旧版 OpenGL 上下文 使上下文成为当前

随机推荐