Блог

Главная - Вопросы по программированию - как вставить узел в круговой связанный список на C

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

#c #linked-list #circular-list

#c #связанный список #круговой список

Вопрос:

Может ли кто-нибудь объяснить «while часть» кода?- в заголовке main() объявляется указатель на узел структуры, инициализированный значением NULL. и узел вставляется путем вызова функции = push(amp;head, 12)

 void push(struct Node **head_ref, int data)
{ 
    struct Node *ptr1 = (struct Node *)malloc(sizeof(struct Node)); 
    struct Node *temp = *head_ref; 
    ptr1->data = data; 
    ptr1->next = *head_ref; 
    if (*head_ref != NULL) 
    { 
        while (temp->next != *head_ref)
            temp = temp->next; 
        temp->next = ptr1; 
    }
    else
        ptr1->next = ptr1; /*For the first node */

    *head_ref = ptr1;
}

Комментарии:

1. В приведенном ниже ответе я пытаюсь ответить на ваш вопрос, но если этого недостаточно, пожалуйста, отметьте меня (@ryyker) в комментарии с любыми вопросами :))

2. Отсутствие указателя на последний узел в циклическом списке (предоставляемый ->prev указателем в двусвязном списке) требует, чтобы после добавления нового 1-го узла вам пришлось пройти весь список, чтобы найти последний узел и обновить ->next указатель, чтобы он указывал на новый 1-й узел. (урок: всегда сохраняйте tail указатель или делайте список doubly-linked списком, чтобы сохранить O (1) вставок)

Ответ №1:

Может ли кто-нибудь объяснить «while часть» кода?

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

Последнее выражение в процедуре:

 *head_ref = ptr1;

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

Общий подход для следующих начальных условий:

  1. Связанный список пуст:
    a) поскольку new_node является единственным узлом в CLL, создайте цикл self.
    new_node-> next = new_node;
    б) измените указатель заголовка, чтобы он указывал на новый узел. * head_ref = new_node;
  2. Новый узел должен быть вставлен непосредственно перед головным узлом:
    (a) Найдите последний узел с помощью цикла. в то время как(текущий-> следующий != *head_ref) текущий = текущий-> следующий; (б) Измените следующий из последних узлов. текущий-> следующий = new_node; (c) Измените следующий из нового узла, чтобы указать на заголовок. new_node-> next = *head_ref; (d) измените указатель заголовка, чтобы он указывал на новый узел. * head_ref = new_node;
  3. Новый узел должен быть вставлен где-то после заголовка: (а) Найдите узел, после которого должен быть вставлен новый узел. в то время как ( current-> next!= *head_ref amp;amp; current->next->данные данных) { current = текущий-> следующий; } (b) Сделайте следующий из new_node следующим из расположенного указателя new_node-> next = текущий-> следующий; (c) Измените следующий из расположенного указателя current->next = new_node;

Подробности и реализация для этого показаны в этом примере кода