Почему мы используем узел * вместо того, чтобы просто говорить узел при инициализации root для связанного списка? - PullRequest
Новая
       28

Почему мы используем узел * вместо того, чтобы просто говорить узел при инициализации root для связанного списка?

0 голосов
/ 01 февраля 2020

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

#include <stdio.h>
#include <stdlib.h>

struct node {
int data;
node* next;
}

Приведенный выше код имеет смысл, так как имеет указатель для указания на другую структуру (я полагаю, он имеет рекурсивное существование, верно меня, если я ошибаюсь).

Но я борюсь с продолжающимся кодом: 

int main (){
node* root;
}

Почему мы должны поставить звездочку при инициализации root? Сама структура root уже имеет указатель, указывающий на следующий узел.

Ответы [ 2 ]

2 голосов
/ 01 февраля 2020

Для начала это объявление структуры (если даже не учитывать забытую точку с запятой после закрывающей скобки) 

struct node {
int data;
node* next;
}

является неправильным.

struct node и node являются два разных спецификатора типа. Структура должна быть объявлена ​​как 

struct node {
    int data;
    struct node* next;
};

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

Голова или начало список указывается одним указателем, который обозначает начало списка и изначально устанавливается в NULL, потому что изначально список пуст. 

int main( void ){
   node* root = NULL;
}

Так, если каждый узел содержит ссылку (указатель) на следующий узел, тогда нам нужно иметь начальную ссылку (указатель) на потенциально первый узел списка, который будет добавлен или вставлен перед списком.

Если эта начальная ссылка (указатель) не равна NULL, тогда он означает, что список имеет по крайней мере один фактический узел, и ссылка указывает на первый узел списка.

Обычно этот узел включен в структуру, которая обозначает список. Например, 

struct SinglyLinkedList
{
    struct node *head;
};

и в основном объект структуры объявляется как 

int main( void )
{
    SinglyLinkedList list = { NULL );
    //…
}

Пользователь списка не должен иметь дело непосредственно с объектами узла типа структуры.

Например, функция, которая выдвигает новый узел, может выглядеть как 

int push_front( struct SinglyLinkedList *list, int data )
{
    struct node *new_node = malloc( sizeof( struct node ) );
    int success = new_node != NULL;

    if ( success )
    {
        new_node->data = data;
        new_node->next = list->head;
        list->head = new_node;
    }

    return success;
}

Что-то вроде 

#include <stdio.h>
#include <stdlib.h>

struct node 
{
    int data;
    struct node* next;
};

struct SinglyLinkedList
{
    struct node *head;
};

int push_front( struct SinglyLinkedList *list, int data )
{
    struct node *new_node = malloc( sizeof( struct node ) );
    int success = new_node != NULL;

    if ( success )
    {
        new_node->data = data;
        new_node->next = list->head;
        list->head = new_node;
    }

    return success;
}

int main(void) 
{
    struct SinglyLinkedList list = { NULL };

    const int N = 10;

    for ( int i = 0; i < N; i++ )
    {
        push_front( &list, i );
    }

        //…

    return 0;
}
2 голосов
/ 01 февраля 2020

это похоже на связанный список. Теоретически, вы можете просто сделать 

node root;

, но тогда возникает вопрос: как бы вы представили пустую связанную структуру, в которой ничего нет? обычно мы можем использовать nullptr (NULL в C) для представления пустой структуры. Если вы создаете первый узел без указателя, он не может быть нулевым. Следовательно, ваша структура данных должна содержать хотя бы один узел (если это не то, что вам нужно).

...