Блог

В реализации связанного списка вставка нового узла в связанный список обычно записывается следующим образом:

void push(struct node** head_ref, int new_data)

 /* 1. allocate node */
struct node* new_node = (struct node*) malloc(sizeof(struct node));

/* 2. put in the data  */
new_node->data  = new_data;

/* 3. Make next of new node as head */
new_node->next = (*head_ref);

/* 4. move the head to point to the new node */
(*head_ref)    = new_node;
  

(Я взял этот код из http://quiz.geeksforgeeks.org/linked-list-set-2-inserting-a-node /)

и структура узла:

struct узел {

данные int;

структурировать узел * следующий;

};

Чего я не понимаю, так это 3. и 4. части вставки. Итак, вы указываете следующий указатель new_node на заголовок, а затем заголовок указывает на new_node? Так это означает, что следующий указатель указывает на new_node?

Это кажется глупым вопросом, но у меня возникли проблемы с его пониманием, поэтому я надеюсь, что кто-нибудь сможет мне это объяснить. Спасибо.

Ну, в основном, в связанном списке все узлы связаны друг с другом. Это зависит от того, где вы вставляете новый узел либо в конце, либо в начале. Каждый раз, когда мы вставляем новый узел, мы проверяем указатель head.

    if(head == NULL)  //it means that the node is empty
   {
      head = newNode;  //so we will assign the new node to the head
   }
    else
   {
      node* temp = head;       //creating a temp pointer that will go 
                               // to the end of the linked list

      while(temp -> next != NULL) { temp = temp->next; }
      temp = newNode;          //This will add the new node to the end
      newNode->next = NULL;enter code here 
    }
  

Если я правильно понял, это ваш сценарий?

http://www.kkhsou.in/main/EVidya2/computer_science/comscience/313.gif

Ваш список — это просто связанный список со следующим указателем до последнего элемента списка, который имеет null в качестве указателя

Шаг 3 заставляет ваш новый узел указывать на 2-й элемент, который был в начале списка до этой операции

Шаг 4 заставляет заголовок списка указывать на новый узел

Надеюсь, это поможет

/* 1. выделить узел / структурировать узел new_node = (структурный узел *) malloc(sizeof (структурный узел));

/* 2. введите данные */ new_node->data = new_data;

/* 3. Сделайте следующий из нового узла в качестве заголовка */ new_node-> next = (*head_ref);

/* 4. переместите заголовок, чтобы указать на новый узел */ (*head_ref) = new_node;

На этапах 1 и 2 создается новый узел и ему присваиваются данные.

Когда ваш список пуст, ваш *head_ref будет равен нулю. или же, если в нем есть какие-либо элементы, это указывало бы на это, Давайте возьмем пример

 Now 
*head_ref is null
when input is 1
newnode.data=1
newnode.next=null
*headref=newnode 
now your *headref points to the latest node that is added ,this happens with step4

When you insert 2
newnode.data=2
newnode.next=*headref(to the node which is 1)
newnode=*headref
now your list is
1->2(*headref)
now if you add 3 here
it becomes
1->2->3(*headref)
  

Надеюсь, вы понимаете

Вместо того, чтобы объяснять это вам, я собираюсь предложить технику, которая поможет вам выработать ответ для себя.

1. Возьмите лист бумаги, карандаш и ластик.

2. Нарисуйте прямоугольник на бумаге для представления каждой переменной в вашем алгоритме

3. Нарисуйте начальный связанный список:

   • Нарисуйте прямоугольник для представления каждого существующего node в исходном связанном списке.
   • Разделите каждый блок на вложенные блоки, представляющие поля.
   • В каждом поле напишите либо значение, либо точку, представляющую конец указателя «от».
   • Для каждого указателя проведите линию до объекта (например, node ), на который указано, и поставьте стрелку в конце «to». Нулевой указатель — это просто точка.

4. Теперь выполните алгоритм.

   • Каждый раз, когда вы выделяете новый узел node , рисуйте новое поле.
   • Каждый раз, когда вы присваиваете что-либо переменной или полю, вычеркивайте текущее значение и записывайте / рисуйте новое значение или новую точку / стрелку.

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

Этот же метод можно использовать для визуализации любого алгоритма списка / дерева / графика… умножьте по модулю вашу способность переносить все это на лист бумаги и способность бумаги выживать при повторных стираниях.

^{(Этот подход с карандашом и бумагой очень «олдскульный». Например, это то, чему нас учили делать, когда я учился программировать в 1970-х годах. Немного более современным подходом было бы использовать белую доску …)}

Прежде всего, указатель head указывает на первый узел в списке. В (1) создается новый узел. В (2) данные сохраняются на новый узел. В (3) Новый узел указывает туда, куда указывает заголовок (означает первый узел) В (4) теперь заголовок сделан так, чтобы указывать на новый узел, поэтому новый узел теперь является первым узлом. вот и все.