将节点插入C的链表中特定位置（仅）

问题描述 投票：-1回答：2

[谁能帮我解决我哪里出错了！！！，我是编程的初学者，我是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中一样，我会很高兴。

c data-structures singly-linked-list
2个回答
0
投票

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

您正在执行malloc 两次，而不是仅执行一次，因此您在每次调用时都在浪费内存。

请勿投射malloc:。请参阅：Do I cast the result of 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

UPDATE：

您还可以告诉我为什么我们必须使用指针*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，因为它（前一个节点）也可以是我们想插入之后

的any节点，即使prev位于列表的中间（例如[ C0]）。看起来像（before插入）：
node2
插入后，我们想要：
head | node1 | node2 | node3
               prev    pcurr

在这种情况下，head | node1 | node2 | pnew | node3
               prev           pcurr
将为pcurr（即node3）。

因此，prev->next指向我们要插入prev的节点[，pnew指向我们要插入pcurr的节点[。 >换句话说，在插入后，pnew是prev左侧的节点（即preceded的节点）。 pnew是pcurr右侧的节点（即

follows

的节点）。如果pnew为空，则下一个节点为[[no，但是在[[all情况下，pcurr或pnew->next = pcurr的值的不管为空或[没有。如果head最终为prev，则表示该列表为空，或者我们希望在列表的开头/开头插入prev。在这种情况下，我们无法尝试取消引用[null] NULL，因此我们只需将pnew设置为prev。然后，我们返回一个updated head指针。

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

列表为空（调整头）

我们要插入新节点

之前

[非空]列表的头（调整头）
    我们想将新节点插入列表中间的某处
  • 我们要在列表的末尾附加新节点（如果tail为null，则调整tail或head）
  • 我认为这对您用铅笔和纸画出每个单独的情况会有所帮助。然后，即使列表具有先前元素或为空，也要手工验证代码是否可以处理所有这些情况。
    • 关于上面的代码要注意的重要一点是，它使用适用于几种不同情况的变量，使用相同的代码路径，以最小化pnew子句的数量来处理
  • uniform]中的各种边缘情况。方式。
  • 我所做的简化类型在编码时一次又一次地发生。彻底了解已完成的操作和

    为什么

    将在将来极大地帮助您。

    • 一个人单独编写的任何一个函数看起来似乎都不多。但是，将其放大到成百上千个功能，它将带来远远超出最初的额外工作所能带来的收益。

    一个格言：

    就像它需要的一样简单，而且没有更简单

    代码越简单（即更清晰），它就越有可能是正确的，完整的，并且越容易检查正确性。与流行的看法相反，我还发现，更简单的代码也趋向于更快。

    head

    我希望以上更改能够解决您的问题。我在需要帮助的地方添加了注释，以帮助您理解代码。如果您发现任何错误，请发表评论，我会予以纠正。

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