Вставить узел в указанной c позиции в связанном списке в C (только)

Question

Кто-нибудь может помочь мне, где я ошибаюсь, пожалуйста !!!, Я новичок в программировании, я новичок в DSA, я не могу найти свою ошибку, вот код, пожалуйста go через него:

Это план моего вопроса, надеюсь, он ясен! :)

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.

Answer 1

Было несколько проблем, и код на самом деле намного проще.

Вы выполняли malloc дважды вместо одного раза, поэтому вы теряли память при каждом вызове.

Не произносить malloc:. См .: Привести результат mallo c?

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, потому что он (предыдущий узел) также может быть любым узлом, который мы используем. sh для вставки после , даже если prev находится в середине списка (например, node2). Это будет выглядеть так ( до вставки):

head | node1 | node2 | node3
               prev    pcurr

После вставки мы хотим:

head | node1 | node2 | pnew | node3
               prev           pcurr

В этом случае pcurr будет node3 (т.е. prev->next).

Итак, prev указывает на узел только до туда, куда мы хотим вставить pnew и pcurr указывает на узел просто после , куда мы хотим вставить pnew.

Другими словами, после вставки prev - это узел слева от pnew (т.е. узел, который предшествует it). pcurr - это узел справа от pnew (т.е. узел, который следует за ). Если pcurr имеет значение null, существует нет следующий узел, но настройка pnew->next = pcurr работает в всех случаях, независимо от значений head или prev имеет значение NULL или нет.

Если prev оказывается NULL, это означает, что список либо пуст, либо мы sh вставляем pnew в начало / перед список. В этом случае мы не можем попытаться разыменовать [a null] prev, поэтому мы просто устанавливаем head на pnew. Затем мы возвращаем обновленный head указатель.

Есть несколько возможных состояний списка и операций вставки:

1. список пуст (настройте head)
2. мы хотим вставить новый узел перед заголовком [непустого] списка (настроить заголовок)
3. мы хотим вставить новый узел где-то в середине списка
4. мы хотим добавить новый узел в конец списка (настроить хвост или голову, если хвост равен нулю)

Я думаю, это будет поможет вам изобразить каждый из этих отдельных случаев карандашом и бумагой. Затем вручную убедитесь, что код обрабатывает каждый из этих случаев, даже если в списке есть предыдущие элементы или он пуст.

Важно отметить, что в приведенном выше коде используются переменные, которые работают для несколько разных случаев, используя один и тот же путь кода, минимизируя количество if/else предложений для обработки различных крайних случаев равномерным способом.

Тип упрощения, который я сделал, повторяется снова и опять же при кодировании. Тщательное понимание того, что было сделано, и почему неизмеримо поможет вам в будущем.

Любая одна функция, которую вы пишете сама по себе, может показаться не такой уж большой. Но увеличьте это до сотен или тысяч функций, и это принесет дивиденды, намного превышающие первоначальную дополнительную работу.

Чем проще (т.е. чище) код, тем больше вероятность, что он будет правильным, полным и тем легче будет его проверить на правильность. Вопреки распространенному мнению, я также обнаружил, что более простой код также имеет тенденцию быть быстрее.

Answer 2

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

    SinglyLinkedListNode* insertNodeAtPosition(SinglyLinkedListNode* head, int data, int position) 
{
    int i = 0;
    SinglyLinkedListNode *temp1, *pcurr, *prev;
    temp1 = (SinglyLinkedListNode *)malloc(sizeof(SinglyLinkedListNode));
    prev = (SinglyLinkedListNode*)malloc(sizeof(SinglyLinkedListNode));
    if(position == 0&&head!=NULL)
    {
        temp1->data = data;
        temp1->next = head;     //new node's next will point to head and new node will become the new head
        head = temp1;          //since the insertion is made at start, new node(temp1) will becomes the new head.
        return head;
    }
    else if(head == NULL)      //if linked list is empty
    {
        temp1->data = data;    
        temp1->next = NULL;
        head = temp1;         //just set the new node as head of linked list and return the head node
        return head; 
    }
    else
    {
        int i=0;         //for iterating to the required position
        temp->data = data;

        //store 2 nodes, one node which will store prev node and another to store current node. The temp node will go between these 
        prev = head,pcurr = head->next; 
        while(i != position-1 && pcurr != NULL){  //traverse the linked list till you reached the insertion position
            i++;
            prev = pcurr;
            pcurr = pcurr->next;
        }
        if(i != position-1){
            return head;     //can't insert at the specified position
        }
        prev->next = temp;   //point the node preceding the insertion position to new node to be inserted
        temp->next = pcurr; //point the new node to the next node to maintain the linked list
        return head;
    }  
}

Надеюсь, вышеуказанные изменения решат ваш вопрос. Я добавил комментарии везде, где это необходимо, чтобы помочь вам понять код. Прокомментируйте, если обнаружите ошибку, и я ее исправлю.