Вставка в Связанный список с использованием двойной указатель в C

Question

void insert(list **l, int x) 
{ 
     list *p; 
     p = malloc(sizeof(list)); 
     p->item = x; 
     p->next = *l; 
     *l=p; 
} 

Почему мы использовали двойной указатель? Могли бы мы сделать то же самое, используя один указатель? Я видел этот пример в книге «Руководство по разработке алгоритмов», стр. 69 2nd Edition.

Список в основном узел, только для refernce.

Answer 1

параметров в C передаются по значению. Поэтому, чтобы внести некоторые изменения в переменную в функцию, мы должны сказать, что функция имеет адрес переменной. Это позволяет изменять значение переменной косвенно путем записи данных в соответствующую память.

В результате, для изменения int, вы должны пройти int *. В вашем случае, чтобы изменить list * (тип p->next), вы должны пройти list **.

Answer 2

использование двойного указателя оправдано здесь, потому что в функции вставки узла в заголовке списка, так что переменная л будет изменена с новым заголовком *l=p;

*l->|node1|->|node2| //initial value 
p->|nodeP| //after p = malloc(sizeof(list)); p->item = x; 
p->|nodeP|->|node1|->|node2| //p->next = *l; 
*l->|nodeP|->|node1|->|node2| //after *l=p 

в этом случае функции называется так :

list *head; 
insert(&head, 4); 

Для вашего вопроса:

Могли бы мы сделали то же самое, используя один указатель?

Да, функция будет выглядеть следующим образом:

list *insert(list *l, int x) 
{ 
     list *p; 
     p = malloc(sizeof(list)); 
     p->item = x; 
     p->next = l; 
     return p; 
} 

вы можете вызвать функцию в этом случае, как это:

list *head; 
head = insert(head, 4); 

Answer 3

Мы могли бы сделать то же самое, используя единый указатель?

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

Верните указатель, который был выделен, и убедитесь, что вызов функции изменен соответствующим образом.

list* insert(list *l, int x) 
{ 
    // list = *p 
    // What was that? That is not valid code. 

    list* p = malloc(sizeof(list)); 
    p->item = x; 
    p->next = l; 
    return p; 
} 

и использовать его как

list* l = NULL; 
l = insert(l, 10); 

Answer 4

Basically u might be calling the insert function using insert(&head,x); 
Previously head would have stored the address of your first node in the 
linked list and u give the address of the head node to l and to access the 
address of a u need to dereference it once and to change its value u need to 
dereference it twice. 

and obviously u can do it without double pointers just giving the value of 
head to l insert(head,x)....and in the function declaring insert(int *l,int 
x) 
suppose 

address of a(first node)=123 

value of head=123 

address of head =456 

l(storing address of head)=456 

In order to get the address of the first node dereference once 

*l=123 
in order to change value or to go to the next node you dereference it twice 
for visual satisfaction have a look at the diagram image i tried to figure 
out for your better understanding. 


---------- 

[Вот диаграмма, которая даст вам четкое представление о ABT как двойной указатель
работает здесь] [1] [1]: http://i.stack.imgur.com/HQOaa.jpg

Answer 5

Вы должны использовать двойной указатель в этом например, потому что вы также хотели бы изменить начальный узел вашего списка. Таким образом, в основном, когда вы вставляете новый элемент, вы также хотите сделать узел, который содержит его первым в списке.Если вы передаете только один указатель (list *l) и назначаете ему вновь созданный узел (p), изменения (а по изменениям означают тот факт, что он будет первым узлом списка) будут доступны только внутри вашего функции и не будет распространяться вне него.

Чтобы сделать его более ясным, если вы принимаете в простой указатель (list *l) вы в основном копирование адреса, сохраненную list* переменной, которая сидит за пределами функции, во вновь созданном указателе (параметр l) , Таким образом, переменная l внутри вашей функции является другим указателем (другое место в памяти по сравнению с переменной указателя вне вашей функции), содержащей тот же адрес, что и указатель вне функции. Вот почему назначение вновь созданного элемента на этот l однократный указатель только сделает вновь вставленный элемент первым только локальным (область функций).

По сравнению с альтернативным методом, когда вы берете двойной указатель (так list **l), действительно происходит то, что, передавая внешнюю переменную указателя функции, вы фактически передаете адрес внешнего указателя, не путать с адресом, который содержит указатель. (позаботьтесь, так как вам нужно будет вызвать функцию примерно так: insert(&l, 2)). Таким образом, вы по-прежнему будете иметь адрес, содержащий внешний указатель, разыменовывая его и используя его как rvalue (p->next = *l), и в то же время у вас есть адрес внешней переменной, поэтому, когда вы делаете *l = p (используется уведомление *l как lvalue здесь), вы на самом деле разыгрываете двойной указатель, и в результате вы получите адрес реальной переменной (внешний), назначив ей вновь созданный узел. Другими словами, вы фактически устанавливаете вновь созданный узел в качестве стартового узла, но на этот раз также вне функции.

Действительно надеюсь, что это не очень запутывает.