时间戳

首页 > 解决方案 > 在 C 中的链表中的特定位置插入节点（仅限）

c - 在 C 中的链表中的特定位置插入节点（仅限）

问题描述

谁能帮助我哪里出错了！！！，我是编程的初学者，我是 DSA 的新手，我找不到我的错误，这里是代码，请通过它：

这是我的问题的大纲，希望清楚！:)


sample input : 3 16 13 7 1 2
3 is the number of elements to input into a linked list
so 16 13 7 are elements of the linked list initially
1 is the element I'm interested to insert
2 is the position where I want to insert the element 1
so the expected output will be:
sample output: 16 13 1 7

我面临的问题：


The output I'm getting is: 13 1 7
So the problem is not every element in the list is getting returned, please help !!!

这是我尝试过的代码，鼓励任何建议，:)

   struct SinglyLinkedListNode 
  {
        int data;
        SinglyLinkedListNode* next;
  };

    SinglyLinkedListNode* insertNodeAtPosition(SinglyLinkedListNode* head, int data, int position) 
{
    int i = 0;
    SinglyLinkedListNode *pcurr, *pnew;

    pnew = (SinglyLinkedListNode*)malloc(sizeof(SinglyLinkedListNode));
    if(position == 0)
    {
        pnew->data = data;
        pnew->next = head->next;
        head = pnew;
        return head;
    }
    if(head == NULL)
    {
        pnew ->data = data;
        return pnew;
    }
    else
    {
        do 
        {
            pcurr = head;
            pcurr = pcurr->next;
            head = head->next;
            i++;
        }
        while (i != position-1);
        pnew->next = pcurr->next;
        pnew->data = data;
        pcurr->next = pnew;
        return head;
    }
}

如果有人建议一个好的可视化平台来逐行查看我们的代码，特别是对于 c ，我会很高兴，就像在 python 中一样。

标签： cdata-structuressingly-linked-list

解决方案

有一些问题，代码实际上要简单得多。

你做malloc 了两次而不是一次，所以每次调用都会泄漏内存。

不要投malloc:。请参阅：我是否强制转换 malloc 的结果？

SinglyLinkedListNode有点长。当在很多地方使用时，这不能很好地扩展。Node更短的东西怎么样SlNode

这是一个重构版本：

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

typedef struct node Node;
struct node {
    int data;
    Node *next;
};

Node *
insertNodeAtPosition(Node *head, int data, int position)
{
    int i = 0;
    Node *prev;
    Node *pcurr;
    Node *pnew;

    pnew = malloc(sizeof(Node));
    pnew->data = data;

    // find the correct place to insert
    prev = NULL;
    for (pcurr = head;  pcurr != NULL;  pcurr = pcurr->next, i += 1) {
        if (i >= position)
            break;
        prev = pcurr;
    }

    // link up the element that will follow the new node
    pnew->next = pcurr;

    // insert into middle or end of list
    if (prev != NULL)
        prev->next = pnew;

    // insert into empty list or _before_ the first node
    else
        head = pnew;

    return head;
}

void
printlist(Node *head)
{
    Node *pcurr;

    printf("List:");

    for (pcurr = head;  pcurr != NULL;  pcurr = pcurr->next)
        printf(" %d",pcurr->data);

    printf("\n");
}

int
main(void)
{
    FILE *fi;
    Node *head = NULL;
    int count;
    int newval;
    int pos;

    fi = fopen("input.txt","r");
    if (fi == NULL) {
        perror("input.txt");
        exit(1);
    }

    fscanf(fi," %d",&count);

    for (int i = 0;  i < count;  ++i) {
        fscanf(fi," %d",&newval);
        printf("new: %d\n",newval);
        head = insertNodeAtPosition(head,newval,count + 10);
    }
    printlist(head);

    while (1) {
        if (fscanf(fi," %d %d",&newval,&pos) != 2)
            break;
        printf("insert: %d at %d\n",newval,pos);
        head = insertNodeAtPosition(head,newval,pos);
    }
    printlist(head);

    fclose(fi);

    return 0;
}

这是测试文件input.txt：：

3
16 13 7
1 2
9 0
8 0

这是程序输出：

new: 16
new: 13
new: 7
List: 16 13 7
insert: 1 at 2
insert: 9 at 0
insert: 8 at 0
List: 8 9 16 13 1 7

更新：

你能告诉我为什么我们必须使用指针*prev吗？为什么只有pcurr和pnew不够？作为初学者，它将帮助我学习这个新概念。

当然。如果我们在列表的头部插入是因为列表是空的，或者我们想在头部插入（即我们想要一个新的头部，即使我们在列表中有其他节点），我们调整head.

但是，如果我们在列表的中间插入或追加到列表的末尾，我们需要知道前一个节点是什么。

考虑一下我们正在尝试追加到列表的末尾。我们需要知道列表的现有/之前的尾部[最后一个元素]。如果我们有：

head | node1 | node2 | node3

然后，node3是列表的尾部。node3->next将NULL。要追加，我们创建新节点 ( pnew) 并且我们必须设置node3->next = pnew，所以我们得到：

head | node1 | node2 | node3 | pnew
                       prev

在这里，prev最终将具有 的值node3，因此设置prev->next = pnew就像设置一样node3->next = pnew。请注意，当附加到末尾时，pcurr将为NULL.

我们称之为它prev是因为它（前一个节点）也可以是我们希望在之后插入的任何节点，即使它位于列表的中间（例如）。这看起来像（在插入之前）：prevnode2

head | node1 | node2 | node3
               prev    pcurr

插入后，我们想要：

head | node1 | node2 | pnew | node3
               prev           pcurr

在这种情况下，pcurr将是node3（即prev->next）。

因此，prev指向我们要插入的位置之前pnew的节点，并pcurr指向我们要插入的位置之后pnew的节点。

换句话说，在插入之后，prev是刚好左边的pnew节点（即它之前的节点）。pcurr是右侧的pnew节点（即跟随它的节点）。如果pcurr为null，则没有后续节点，但无论是否为null ，设置pnew->next = pcurr在所有情况下都有效。headprev

如果prev最终是NULL，这意味着列表要么是空的，要么我们希望插入pnew到列表的头部/前面。在这种情况下，我们不能尝试取消引用 [a null] prev，所以我们只需设置head为pnew. 然后，我们返回一个更新 head的指针。

有几种可能的列表状态和插入操作：

  1. 列表为空（调整头部）
  2. 我们要在[非空]列表的头部之前插入新节点（调整头部）
  3. 我们想在列表中间的某处插入新节点
  4. 我们想将新节点附加到列表的末尾（如果tail为空，则调整tail或head）

我认为使用铅笔和纸绘制每个单独的案例对您很有帮助。然后，手动验证代码是否处理了这些情况，即使列表具有先前的元素或为空。

关于上述代码需要注意的重要一点是，它使用了适用于几种不同情况的变量，使用相同的代码路径，最大限度地减少了以统一方式if/else处理各种边缘情况的子句数量。

我所做的简化类型在编码时一次又一次地发生。彻底了解做了什么以及为什么将在未来为您提供不可估量的帮助。

一个人编写的任何一个函数，就其本身而言，可能看起来并不多。但是，将这一点放大到数百或数千个函数中，它所带来的回报将远远超出最初的额外工作。

一句格言：尽可能简单——而且不会更简单

代码越简单（即越干净），它就越有可能是正确的、完整的，也就越容易检查正确性。与流行的看法相反，我还发现更简单的代码也往往更快。

推荐阅读