Доступ к данным в связанном списке
В C ++, если у меня есть двоичное дерево поиска (BST) следующей формы
Struct node{
node leftChild;
node rightChild;
int data;}
Законно ли получить доступ к данным LeftChild следующим образом:
foo (node head)
{
std::cout << head.leftChild.data;
}
Кроме того, иногда я вижу, что узлы связанного списка используют узел * для детей, а иногда они просто используют узел. Когда / почему вы бы использовали либо. Извините за строковый вопрос, просто любопытно.
Решение
Нет, потому что у вас не может быть такой структуры. Это было бы бесконечно большим node имеет двоих детей nodeы, у каждого из которых есть два ребенка nodeи т. д. навсегда). Именно поэтому люди будут использовать указатели при создании узла, у которого есть дочерние элементы одного типа.
Например, как не сделать это:
/* This is a problem because of the recursive nature of the structure. leftChild also
contains a leftChild itself, which also contains a leftChild, etc. forever. */
struct node
{
node leftChild; // how big is leftChild? infinitely large!
node rightChild; // how big is rightChild? infinitely large!
int data;
}
И право способ сделать это:
/* This is not a problem because the size of a pointer is always 4 bytes (assuming 32-
bit system). You can allocate room for the child nodes without recursively requiring an
infinite amount of memory. */
struct node
{
node* leftChild; // how big is leftChild? 4 bytes (assuming 32-bit system)
node* rightChild; // how big is rightChild? 4 bytes (assuming 32-bit system)
int data;
}
Как только вы сделаете это правильно, совершенно законно сказать:
void foo(node head)
{
std::cout << head.leftChild->data; // assuming leftChild points to a valid object!
}
Другие решения
Других решений пока нет …