Как указатели работают с двусвязными списками в C?

если я создам следующую структуру:

typedef struct node {
    int a;
    char b[100][15];
    struct node *prev;
    struct node *next;
} Scope;

Должен ли я использовать указатель для инициализации моего head_node? В настоящее время это моя функция инициализации:

Scope initScope() {
    Scope head;
    head.a = 1;
    head.prev = NULL;
    head.next = NULL;
    return head;
}

В какой-то функции я бы сказал

Scope head = initScope();

Пока мне это кажется нормальным, но я не уверен, как создать новый узел. Я предполагаю, что мне понадобится указатель типа Scope. Мне пришлось бы выделить его размером Scope, а затем инициализировать его значения. Должен ли я делать то же самое при создании головы? Основной вопрос, на который я пытаюсь ответить, заключается в том, какова цель указателя здесь? Что, если бы в определении моей структуры я написал

*Scope

вместо

Scope

? Если мне нужно использовать указатели для создания узлов, то почему бы не сделать структуру указателем? Насколько я понимаю, указатели просто позволяют мне манипулировать памятью, так что же остается, когда я создаю узел и иду дальше?


c struct pointers doubly-linked-list
person Pareod    schedule 07.04.2016    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Пока мне это кажется нормальным, но я не уверен, как создать новый узел.

Элементы prev и next объекта Scope должны указывать на другие объекты Scope, чтобы создать связанный список.

Эти объекты могут находиться в статически выделенном массиве объектов или в динамически выделенных объектах.

  1. Создание связанного списка из статически выделенного массива

    Scope scopes[10];
scopes[0].prev = NULL;
scopes[9].next = NULL;
for (int i = 0; i < 9; ++i )
{
    scopes[i].next = &(scopes[i+1]);
    scopes[i+1].pref = &(scopes[i]);
}

  2. Создание связанного списка из динамически размещаемых объектов

    Scope* node = malloc(sizeof(*node));
node->next = node->prev = NULL;
for ( int i = 0; i < 9; ++i )
{
   Scope* temp = malloc(sizeof(*temp));
   temp->prev = NULL;
   temp->next = node;
   node->prev = temp;
   node = temp;
}

    Вы также можете динамически размещать все объекты с помощью одного вызова.

    Scope* scopes = malloc(10*sizeof(*scopes));

    а затем обработайте его аналогично статически выделенному массиву.

    Вам нужно будет использовать правильные вызовы free в зависимости от того, какой метод вы используете для размещения объектов.

person R Sahu    schedule 07.04.2016
comment
Итак, я бы использовал указатель для создания узлов? Первый узел будет иметь нулевые указатели, а каждый последующий узел будет связан со следующим указателем? Так что на самом деле я просто использую struct для выделения блока памяти определенного размера? - person Pareod; 07.04.2016
comment
Указатели указывают на объекты. Я не уверен, что вы имеете в виду под Значит, я буду использовать указатель для создания узлов? Если есть только один узел, его члены next и prev будут NULL. В противном случае они не будут. Да, вы используете struct для выделения блока памяти определенного размера. - person R Sahu; 07.04.2016
comment
Я имею в виду, что вместо того, чтобы говорить int = 5, я буду говорить int *ptr = malloc(sizeof(int)); &ptr = 5;, поэтому, по сути, я выделяю память размером int. Теперь, применяя эту идею к связанным спискам, я должен сделать это таким образом, иначе у меня будет уникальное имя переменной для каждого узла, верно? Или у меня будет массив узлов, каждый из которых имеет уникальный индекс? Кажется, я начинаю понимать, почему мне нужно использовать указатель для узлов после головы. - person Pareod; 07.04.2016
comment
@Pareod, ты идешь в правильном направлении. Единственное, что неправильно, это то, что нужно использовать *ptr = 5;, а не &ptr = 5;. - person R Sahu; 07.04.2016
comment
Но ptr указывает на блок памяти размером int, поэтому не будет ли &ptr = 5; помещать число 5 в этот блок памяти? Я подумал, что выражение ptr = 5 изменит блок памяти, на который смотрит указатель. Например, currentNode = currentNode->prev; не устанавливает текущую память равной предыдущей, она меняет место, где ищет currentNode. - person Pareod; 07.04.2016
comment
@Pareod, я сказал *ptr = 5;, а не ptr = 5;. Пожалуйста, потратьте немного времени на чтение об указателях и указателях на разыменование в C/C++. Переполнение SO не подходит для таких тем. - person R Sahu; 07.04.2016