LINUX.ORG.RU

C pointers & linked list

 , ,


0

1

Всем привет.

Дали задачку на реверс списка:

int main(void)
{
     struct Node *list;
     alloc_list(&list);
     print_list(list);          /* 0 1 2 3 4 */
     revert_list(list);
     print_list(list);          /* 4 3 2 1 0 */

     return 0;
}
Собственно нужно реализовать revert_list. Немного порисовав стрелочки с кружочками на листике пришёл к такому решению:
void revert_list(struct Node *list_head)
{
     struct Node *p = NULL;     /* previous */
     struct Node *c = NULL;     /* current */
     struct Node *n = NULL;     /* next */

     c = list_head;

     while(c != NULL) {
          n = c->next;
          c->next = p;
          p = c;
          c = n;
     }

     list_head = p;
     print_list(list_head);
}

К моему удивлению, если print_list вызывается из main(), то печатается 0, а внутри reverse_list всё хорошо:

gcc -Wall -Wextra -Wpedantic -g3 rlist.c -o rlist && ./rlist 
0 1 2 3 4 
4 3 2 1 0 
0
Почему так происходит? Ведь я же меняю «направление» next'ов через указатели. Или указатели, созданные на стеке и все манипуляции через них над линкованным списком умирают при выходе из функции?


Ответ на: комментарий от xaizek

Поясни, пожалуйста, я не совсем понял. Запаустил в gdb, адрес list'a в main'e:

(gdb) p	list
$3 = (struct Node *) 0x555555559260
Тот же адрес попадает в revert_list():
Breakpoint 1, revert_list (list_head=0x555555559260) at rlist.c:34

ubik ()
Ответ на: комментарий от mittorn

сделай либо struct Node *revert_list(struct Node *p)

Судя по сигнатуре функции от меня ожидают как раз второй вариант

void revert_list(struct Node **p)

Но я не понимаю как мне поможет двойной поинтер. Как это работает?

ubik ()
Ответ на: комментарий от ubik

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

cherry_boy ()

Если первый кусок кода менять нельзя, то только так:

struct Node* revert_list_real(struct Node* list_head);
#define revert_list(lst) \
    do { lst = revert_list_real(lst); } while(0)

Но так делать в жизни не стоит.

Или можно менять элементы, а не указатели, но это требует O(n) памяти если список однонаправленный.

rymis ★★ ()
Последнее исправление: rymis (всего исправлений: 1)