Поп из связанного списка

Question

Я реализовал Linked-List с помощью функции Pop в C:

Node * pop (Node * head) {
    Node * temp = head;

    printf("Temp is: %s\n", temp->val);

    if (head->next != NULL) {
        *head = *head->next;
    }

    printf("Temp is: %s\n", temp->val);
    return temp;
}

И вывод, когда я поп, будет что-то вроде:

Temp is: node1 value
Temp is: node2 value

То есть температура становится временной -> следующей, когда я назначаю *head = *head->next,

Так как я могу получить значение текущего head и вернуть его, одновременно перемещая заголовок связанного списка в head->next?

дела head = head->next НЕ удаляет ссылку на первый узел. (т.е. когда я печатаю список, первый узел все еще там).

Благодарю.

Answer 1

Вам нужно передать адрес head для вашей функции, чтобы изменить его. Тогда ваша функция должна разыменовать этот адрес. Кроме того, последний pop() также должен изменить *AddressOfHead

Node *pop(Node **AddressOfHead) {
    Node *temp = *AddressOfHead;
    if (temp) {
        *AddressOfHead = temp->next;
    }
    return temp;
}

...

// Usage example
Node *TopOfList = pop(&Head);

Answer 2

Во-первых, обратите внимание, что ваш код (и некоторые из предыдущих решений) никогда не вытеснят последний элемент из списка. Ты хочешь

if (*head != NULL) ...

Далее, передача указателя на указатель будет работать. Но на самом деле лучше сделать заголовок списка следующим образом:

typedef struct node_s {
  struct node_s *next;
  ... data declaration here
} Node;

typedef struct list_s {
  struct node_s *head;
} List;

void init_list(List *list) {
  list->head = NULL;
}

Теперь объявите список следующим образом:

List list[1];

init_list(list);

Объявление массива из одного элемента делает каждую ссылку на list указатель автоматически, что устраняет много &в вашем коде. Тогда хорошо и чисто реализовать push и pop:

void push(List *list, Node *node) {
  node->next = list->head;
  list->head = node;
}

Node *pop(List *list) {
  Node *head = list->head;
  if (head) {
    list->head = head->next;
    head->next = NULL;
  }
  return head;
}

Почему это лучше? Скажем, вы решили позже сохранить количество элементов в списке. С отдельным узлом заголовка это очень просто:

typedef struct list_s {
  struct node_s *head;
  int length;
} List;

void init_list(List *list) {
  list->head = NULL;
  length = 0;
}

void push(List *list, Node *node) {
  node->next = list->head;
  list->head = node;
  ++list->length;
}

Node *pop(List *list) {
  Node *head = list->head;
  if (head) {
    list->head = head->next;
    head->next = NULL;
    --list->length;
  }
  return head;
}

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

Answer 3

Другие говорили, как это исправить, позвольте мне ответить, почему temp изменилось..

Node * pop (Node * head) {

Вы проходите head как указатель на Node,

Таким образом, когда вы делаете

*head = *head->next;

Я думаю, что это анализируется как

 *head = *(head->next);

И, таким образом, копирует объект, который находится рядом в объект в head, который, конечно, тот же объект в temp,

Answer 4

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

Чтобы значение указателя узла было изменено в вызывающей функции, вам нужно передать стек в качестве указателя на указатель:

Node* pop (Node** head) {

    Node* temp = *head;    

    if (temp) {
       *head = temp->next;    // to update stack in calling function
       temp->next = NULL;     // to detach temp from the rest of the list
    }

    return temp;
}

Вам не нужно проверять if ((*head)->next) или в этом случае if (temp->next) перед обновлением значения *headпотому что, если вы находитесь на последнем узле стека, а следующий узел NULLВы хотите, чтобы список был NULL тем не мение.

Ответ Karthik T имеет правильное объяснение того, почему значение temp менялся в вашем исходном коде.

Answer 5

void pop(struct node** tol) {
  struct node* t = *tol;
  while (t->link->link != NULL){
    t = t->link;    
  }
  t->link = NULL;
}