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

Question

struct node
{
     int         info;
     struct node *llink;
     struct node *rlink;
};

typedef node *nodep;

Что значит иметь указатель структуры внутри самой структуры?
Пожалуйста, объясните вышеупомянутую структуру подробно.

PS
Я НЕ говорю о логике деревьев.Я говорю о структуре C и поведении указателя.

EDIT 1:

struct node *llink Как для этого выделяется память?Это тип, который еще не появился?

Answer 1

Указатель - это просто ссылка на место в памяти («адрес»).В случае node указатель на экземпляр node является ссылкой на место в памяти, где хранится этот экземпляр node.

Для вашего struct, как определено,если у вас есть экземпляр node, который находится в одной ячейке памяти, он может указывать на два других экземпляра node, которые находятся в их собственных ячейках памяти (*llink, *rlink).

Используя реальное дерево в качестве метафоры, *llink и *rlink являются указателями на левую и правую «ветви» корневого узла древовидной структуры соответственно.Сами эти указатели могут разветвляться на более глубокие левые и правые «поддеревья».

Прочитайте это введение в двоичные деревья .

Answer 2

Поскольку в вебах есть некоторая противоречивая информация относительно «объявления» и «определения», я буду придерживаться определения :-) этих двух терминов, следующих за этим постом .

struct node
{

Это начало определения структуры "узел". Также вводится тип node.

     int         info;
     struct node *llink;
     struct node *rlink;

Вот некоторые поля объявлений . Тип должен быть известен, и он известен, потому что он уже введен. Фактический размер node не имеет значения.

};

Теперь определение из node завершено, и его можно использовать как тип:

typedef node *nodep;

Когда определяет переменную типа node, память выделяется:

node n = {42, NULL, NULL};
// or
nodep np = (struct node *)malloc(sizeof(struct node));

---

С C ++ : Но что, если вы хотите использовать два типа друг в друге? Затем вы вводите тип B, определяете тип A и определяете тип B:

class B;

class A
{
    class B *pointerToB;
};

class B
{
    class A *pointerToA;
};

-> Это должно показать идею, а не производственный код. Я не уверен, что вы можете использовать его в C с struct вместо class в последнем примере. Если это не на 100% правильно, пожалуйста, прокомментируйте, и я исправлю.

---

Вот отличное продолжение сообщения с начала моего ответа. Ссылка больше не действительна

Answer 3

Эта страница содержит информацию о том, что такое древовидная структура данных:

http://en.wikipedia.org/wiki/Tree_(data_structure)

Узел дерева содержит значение данных (элемент info) и указатели слева иправые поддеревья (указатели llink и rlink).Поддеревья также являются узлами, поэтому указатели являются указателями на struct node объектов.Наличие указателей позволяет вам ходить по дереву, поскольку все узлы связаны с помощью указателей.

Answer 4

Бинарное дерево может быть определено рекурсивно так:

• Каждый отдельный узел (узел без поддеревьев) сам является двоичным деревом.
• Если у узла есть левое поддерево, правое или оба, это двоичное дерево.

Определение struct node следует этому рекурсивному определению двоичного дерева.

Например:

Это изображение представляет собой двоичное дерево. Мы можем представить это двоичное дерево в C следующим образом:

Узел со значением 2 - это узел, который не имеет поддеревьев и может быть представлен в виде структуры, подобной этой:

struct node* node2 = malloc(sizeof(struct node));
node2->info = 2;
node2->llink = NULL;
node2->rlink = NULL;

Значение NULL для llink и rlink означает, что у узла нет поддеревьев. Обратите внимание, что мы можем представить узлы со значениями 5 ( внизу слева один, а не вверху справа), 11 и 4.

Узел со значением 6 имеет два поддерева (помните, что все узлы сами являются поддеревьями) и, предполагая, что узлы со значениями 5 и 11 соответственно представлены

struct node* node5 = malloc(sizeof(struct node));
node5->info = 5;
node5->llink = NULL;
node5->rlink = NULL;

struct node* node11 = malloc(sizeof(struct node));
node11->info = 11;
node11->llink = NULL;
node11->rlink = NULL;

мы можем представить наш узел следующим образом:

struct node* node6 = malloc(sizeof(struct node));
node6->info = 6;
node6->llink = node5; /* Pointer to node with value 5 */
node6->rlink = node11; /* Pointer to node with value 11 */

То же самое относится ко всем остальным узлам двоичного дерева.

Обратите внимание, что мы используем указатели для поддеревьев. Причина в том, что использование NULL позволяет дереву иметь конечное число элементов, в противном случае двоичное дерево потребует бесконечного количества памяти (структура, которая содержит себя, содержит себя, содержит себя, содержит себя). требуется бесконечное количество памяти).

(Изображение взято из статьи в Википедии для Двоичное дерево и, в частности, из http://upload.wikimedia.org/wikipedia/commons/thumb/f/f7/Binary_tree.svg/200px-Binary_tree.svg.png)