LINUX.ORG.RU
решено Форум — Development  

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'ов через указатели. Или указатели, созданные на стеке и все манипуляции через них над линкованным списком умирают при выходе из функции?

★

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

list_head = p;

Параметр – локальная переменная, её изменение не влияет на значение list в main().

xaizek ★★★★★
()
Ответ на: комментарий от 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

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

а как это работает в alloc_list(&list); ?

conalex ★★★
()
Ответ на: комментарий от 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)
Ответ на: комментарий от cherry_boy

Очень хороший комментарий. Спасибо тебе!

ubik ★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
Development