Указатель на указатель в связанном списке
Может ли кто-нибудь объяснить мне, почему этот код дает мне пустой список:
typedef struct str_node{
int data;
struct str_node *next;
}node;
void begin(node *head);
void display_list(node *head);
int main(){
node *head;
int i;
head = NULL;
for(i=0;i<5;i++) {
begin(head);
}
display_list(head);
return 0;
}
void begin(node *head){
node *new;
int value;
new = (node*) malloc(sizeof(node));
printf("Insert the element to add at the beginning of the list: ");
scanf("%d",&value);
new->data = value;
new->next = head;
head = new;
}
Но если я изменю функцию begin () указателем на указатель, она даст мне правильный список?
void begin(node **head){
node *new;
int value;
new = (node*) malloc(sizeof(node));
printf("Insert the element to add at the beginning of the list: ");
scanf("%d",&value);
new->data = value;
new->next = *head;
*head = new;
}
Можете ли вы также объяснить мне, почему, когда я передаю в основном заголовок узла функции begin, я должен передавать его как «& head»? и не более как "голова"
Ответы
В первой программе в этом фрагменте кода
head = NULL;
for(i=0;i<5;i++) {
begin(head);
}
указатель headпередается в функцию beginпо значению. То есть создается копия значения указателя, headобъявленного в main, и присваивается параметру с таким же именем функции begin
void begin(node *head);
Таким образом, внутри функции это параметр, headкоторый изначально содержит копию headизмененного исходного указателя . Исходный указатель, headзначение которого было присвоено параметру, не изменяется.
Чтобы изменить исходный заголовок указателя, объявленный в main, вы должны передать его функции по ссылке косвенно через указатель на указатель head, как это делается во второй программе.
Таким образом, функция должна быть объявлена как
void begin(node **head);
И вы должны передать заголовок указателя косвенно через указатель на него
begin( &head );
В этом случае при разыменовании переданного указателя функция получит прямой доступ к исходному заголовку указателя, объявленному в main, и сможет изменить его (а не копию его значения, как это имеет место в первом определении функции)
new->next = *head;
*head = new;
Чтобы было понятнее, рассмотрим эту простую демонстрационную программу.
#include <stdio.h>
typedef int T;
void f( T t )
{
t = 10;
}
int main(void)
{
T t = 0;
printf( "Before calling f t is equal to %d\n", t );
f( t );
printf( "After calling f t is equal to %d\n", t );
return 0;
}
Его выход
Before calling f t is equal to 0
After calling f t is equal to 0
Поскольку функция f работает с копией значения переданного аргумента, значение переменной, tобъявленной в main, не изменилось.
Поэтому вам нужно передать исходную переменную tпо ссылке через указатель, например
#include <stdio.h>
typedef int T;
void f( T *t )
{
*t = 10;
}
int main(void)
{
T t = 0;
printf( "Before calling f t is equal to %d\n", t );
f( &t );
printf( "After calling f t is equal to %d\n", t );
return 0;
}
Теперь вывод программы
Before calling f t is equal to 0
After calling f t is equal to 10
В этих демонстрационных программах имя Tиспользуется как псевдоним для типа, intи в основном объект tимеет этот тип.
Теперь предположим, что имя T является псевдонимом для типа int *.
typedef int * T;
В этом случае объявление в основном как например
T t = NULL;
означает, что переменная tимеет тип указателя int *. То есть это эквивалентно
int * t = NULL;
Итак, чтобы передать его функции, которая должна изменить исходную переменную t, нам нужно передать ее по ссылке, например
f( &t );
это означает, что соответствующая функция должна иметь тип параметра, объявленный как
void f( T *t );
но as Tявляется псевдонимом, int *следовательно, это означает, что функция имеет параметр типа int **.
void f( int * *t );
Потому что headэто (фактически) локальная переменная, поэтому ее изменение не имеет никакого эффекта вне функции, тогда как изменение *headменяет то, headна что указывает, и, следовательно, влияет .
Если вы хотите, чтобы функция могла изменять значение в intпеременной (скажем, x), вы должны передать ей указатель x, который будет иметь тип, int*и вы получите указатель x, используя &x. То же самое независимо от типа x.
Небольшая путаница может возникнуть из-за объявления
node *head;
вместо
node* head;
Вы заявляете head. headэто переменная, и это указатель. Это не узел. Также обратите внимание, что узел не является связанным списком: связанный список - это набор узлов и, возможно, чего-то еще, чтобы иметь полезную реализацию. Подробнее об этом позже, в конце.
Дело в том, что вы в main()заявлении head, всего лишь a node*. Сама нода еще даже не существует. Вы заявили begin()как
void begin(node *head);
и я думаю, вы увидите это более ясно, как
void begin(node* parameter);
parameterесть node*.
Внутри begin()вы получаете копию указателя, и изменение указателя не изменит исходный указатель в main(). В вашем случае это main()всегда будет указывать на NULL.
Важно то, что указатель подобен любой переменной: указатель имеет адрес. И контент. Когда вы переходите по значению, как и вы, указатель begin()начинается с NULLЗНАЧЕНИЯ, из которого произошло main(). Но связь между ними заканчивается вызовом: начальное значение.
Когда вы передаете указатель на begin(), используя оператор «адрес» и записываете, &headчто-то меняется: вы измените его с помощью оператора, '*'что означает, что вы измените адрес, на который он указывает, так что он изменится на main(). Так headкак node*указатель на него будет объявленnode**
Но рассмотрите возможность изменения объявления begin()связанного списка, используя:
node* begin(node* node);
Логика заключается в том, что вставка узла может изменить заголовок списка, поэтому вы вернете новый адрес, как в
node* _insert_begin(int value, node* pNode)
{
node* new = (node*)malloc(sizeof(node));
new->data = value;
new->next = pNode;
return new;
}
это обычный способ написать это. Другой - использовать node**.
Как я здесь описываю, любая операция, которая может изменить заголовок списка, должна
- верните новую голову
- получать и обновлять указатель на указатель головы
Еще раз посмотрите этот код, который вставляется в начало списка:
node* _insert_begin(int value, node* pNode)
{ // insert 'value' at the start of the list
node* new = (node*)malloc(sizeof(node));
(*new).data = value;
new->next = pNode;
return new;
}
возвращаясь, newвы получите headобновления. И вы можете написать вmain()
node* another = NULL;
display_list(another);
// inserts 5 to 0 at the beginning
for (int i = 5; i >= 0; i -= 1)
another = _insert_begin(i, another);
printf("inserted 5..0 at the beginning\n");
display_list(another);
Обратите внимание на строку, another = _insert_begin(i, another);и вы увидите, как main()обновляется указатель .
Это результат
empty list
inserted 5..0 at the beginning
0 1 2 3 4
5
list has 6 elements
Используя эту реализацию display_list(), которая печатает 5 значений в строке:
int display_list(node* p)
{
if (p == NULL)
{
printf("empty list\n");
return 0;
};
int count = 0;
// not empty
do
{
printf("%8d ", p->data);
count++;
if (count % 5 == 0) printf("\n");
p = p->next;
} while (p != NULL);
if (count % 5 != 0) printf("\n");
printf("list has %d elements\n", count);
return count;
};
Другой пример: вставка в конце
обратите внимание, что вставка в конце также может изменить заголовок в случае, если список пуст, поэтому нам все равно нужно вернуть адрес заголовка
node* _insert_end(int value, node* pNode)
{ // insert value at the end of the list
node* new = (node*)malloc(sizeof(node));
new->data = value;
new->next = NULL;
if (pNode == NULL) return new;
node* p = pNode;
while (p->next != NULL) p = p->next;
p->next = new;
return pNode;
}
Другое использование: вставка в порядке возрастания
Конечно, вставка в порядке возрастания также может изменить заголовок, как в
node* _insert_ordered(int value, node* pNode)
{ // insert value at ascending order in the list
node* new = (node*)malloc(sizeof(node));
new->data = value;
new->next = NULL;
if (pNode == NULL) return new;
node* p = pNode;
node* prev = NULL; // previous node: list if forward only
while (p->next != NULL)
{
if (new->data < p->data)
{
// insert before first greater than value
if (prev == NULL)
{
// new head
new->next = p;
return new;
}; // if()
prev->next = new;
new->next = p;
return pNode; // no change in head
};
prev = p; p = p->next; // updates pointers
}; // while()
// we are at the end: new will be the last?
if (new->data < p->data)
{
if (prev == NULL)
pNode = new;
else
prev->next = new;
new->next = p;
}
else
{
p->next = new;
};
return pNode;
} // _insert_ordered()
Удаление списка
Удаление списка также должно возвращать, node*чтобы сделать недействительным указатель заголовка. Это обычное дело. Когда вы привыкните к механике этого, это гарантирует, что недействительный указатель не останется.
Обратите внимание, что эта логика кооперативная: вы должны назначать указатель головы обратно при каждом вызове, который может изменить голову.
node* delete_list(node* H)
{
if (H == NULL) return NULL;
if (H->next == NULL)
{ // single node
free(H);
return NULL;
};
// more than one node
do
{ node* p = H->next;
free(H);
H = p;
} while (H != NULL);
return NULL;
};
Работающая программа
Вывод программы-примера
empty list
inserted 5..0 at the beginning
0 1 2 3 4
5
list has 6 elements
inserted 6 to 10 at the end
0 1 2 3 4
5 6 7 8 9
10
list has 11 elements
inserted 0 to 10, ordered
0 0 1 1 2
2 3 3 4 4
5 5 6 6 7
7 8 8 9 9
10 10
list has 22 elements
inserted -1 to -10, ordered
-10 -9 -8 -7 -6
-5 -4 -3 -2 -1
0 0 1 1 2
2 3 3 4 4
5 5 6 6 7
7 8 8 9 9
10 10
list has 32 elements
inserted 11 to 20, ordered
-10 -9 -8 -7 -6
-5 -4 -3 -2 -1
0 0 1 1 2
2 3 3 4 4
5 5 6 6 7
7 8 8 9 9
10 10 11 12 13
14 15 16 17 18
19 20
list has 42 elements
about to delete list
empty list
Пример программы C
#include <stdio.h>
#include <stdlib.h>
typedef struct str_node
{
int data;
struct str_node* next;
} node;
void begin(node* pNode);
node* delete_list(node*);
int display_list(node*);
node* _insert_begin(int, node*);
node* _insert_end(int, node*);
node* _insert_ordered(int, node*);
int main()
{
node* another = NULL;
display_list(another);
// insert 5 to 0 at the beginning
for (int i = 5; i >= 0; i -= 1)
another = _insert_begin(i, another);
printf("inserted 5..0 at the beginning\n");
display_list(another);
// insert 6 to 10 at the end
for (int i = 6; i <= 10; i += 1)
another = _insert_end(i, another);
printf("inserted 6 to 10 at the end\n");
display_list(another);
// insert 0 to 10 ordered
for (int i = 0; i <=10; i += 1)
another = _insert_ordered(i, another);
printf("inserted 0 to 10, ordered\n");
display_list(another);
// insert -1 to -10 ordered
for (int i = -1; i >= -10; i -= 1)
another = _insert_ordered(i, another);
printf("inserted -1 to -10, ordered\n");
display_list(another);
// insert 11 to 20 ordered
for (int i = 11; i <= 20; i += 1)
another = _insert_ordered(i, another);
printf("inserted 11 to 20, ordered\n");
display_list(another);
printf("about to delete list\n");
another = delete_list(another);
display_list(another);
return 0;
}
node* delete_list(node* H)
{
if (H == NULL) return NULL;
if (H->next == NULL)
{ // single node
free(H);
return NULL;
};
// more than one node
do
{ node* p = H->next;
free(H);
H = p;
} while (H != NULL);
return NULL;
};
node* _insert_begin(int value, node* pNode)
{ // insert 'value' at the start of the list
node* new = (node*)malloc(sizeof(node));
(*new).data = value;
new->next = pNode;
return new;
}
node* _insert_end(int value, node* pNode)
{ // insert value at the end of the list
node* new = (node*)malloc(sizeof(node));
new->data = value;
new->next = NULL;
if (pNode == NULL) return new;
node* p = pNode;
while (p->next != NULL) p = p->next;
p->next = new;
return pNode;
}
node* _insert_ordered(int value, node* pNode)
{ // insert value at ascending order in the list
node* new = (node*)malloc(sizeof(node));
new->data = value;
new->next = NULL;
if (pNode == NULL) return new;
node* p = pNode;
node* prev = NULL; // previous node: list if forward only
while (p->next != NULL)
{
if (new->data < p->data)
{
// insert before first greater than value
if (prev == NULL)
{
// new head
new->next = p;
return new;
}; // if()
prev->next = new;
new->next = p;
return pNode; // no change in head
};
prev = p; p = p->next; // updates pointers
}; // while()
// we are at the end: new will be the last?
if (new->data < p->data)
{
if (prev == NULL)
pNode = new;
else
prev->next = new;
new->next = p;
}
else
{
p->next = new;
};
return pNode;
} // _insert_ordered()
int display_list(node* p)
{
if (p == NULL)
{
printf("empty list\n");
return 0;
};
int count = 0;
// not empty
do
{
printf("%8d ", p->data);
count++;
if (count % 5 == 0) printf("\n");
p = p->next;
} while (p != NULL);
if (count % 5 != 0) printf("\n");
printf("list has %d elements\n", count);
return count;
};
Возможно более полезная структура связанного списка
Рассмотрим следующее
struct no
{
void* item;
struct no* next;
struct no* prev;
}; // no
typedef struct no Node;
typedef struct
{ // example, more flexible
char* name;
unsigned size;
unsigned capacity;
Node* head;
Node* tail;
} Linked_list;
Таким образом, связанный список определяется как контейнер узлов.
- У него даже есть необязательный
name. sizeвсегда доступен и актуален- ограничение размера может быть реализовано как
capacity - вставка в конце и в начале не требует, чтобы вы следовали за всеми другими узлами, поскольку список инкапсулирует указатели как на голову, так и на хвост
- у узла есть указатели на следующие И предыдущие узлы, поэтому некоторые данные, такие как списки воспроизведения или подобные коллекции, могут быть легко повторены.
- программа может иметь любое количество списков, поскольку каждый из них инкапсулирует все эти метаданные.
- список может содержать что угодно, поскольку данные являются указателем на void,
void* - такие функции, как empty () или size (), могут быть легко реализованы
- все функции используют указатель на список
Linked_list ll_one;
Linked_list many_ll[20];
Linked_list* pLL = &ll_one;
относительно:
void begin(node *head){
При изменении headизменяется только «голова» стека вызовов, необходимо только изменить место, на которое указывает «голова» в функции вызывающего. Для этого вызывающий должен передать адрес head. Тот факт, что "голова" сама по себе является указателем, не помогает ясности в том, что нужно делать,