Оспаривание синтаксиса узла

Question

Ниже приведен синтаксис, часть связанного списка на языке программирования C

struct tag-name
{
   type member1;
   type member2;
   .......
   .......
   struct tag-name *next;
 };

Почему мы должны снова написать struct tag-name перед следующей переменной указателя.Почему мы не можем использовать void * next или int * next или что-то в этом роде?

Answer 1

Подумайте о типичной иллюстрации связанного списка:

node                node                node
+------+------+     +------+------+     +------+------+
| data | next | --> | data | next | --> | data | next | --> ...
+------+------+     +------+------+     +------+------+

Каждый элемент в списке - это узел определенного типа, и этот узел содержит next член, которыйявно указывает на следующий узел в списке.В C это обычно преобразуется в тип struct, такой как

struct node 
{
  T data; // for some type T
  struct node *next;
};

IOW, каждый struct node имеет член next, который указывает на другой объект типа struct node - не int,не void и т. д., поэтому мы не объявляем next как int *, или void *, или как угодно.

Однако ...

В зависимости от того, как вы реализуете свой список, вы можете использовать что-то отличное от struct node * в качестве элемента next.Обычно, когда мы реализуем список, мы динамически распределяем каждый узел, используя malloc, как нам это нужно.Однако, если вы знаете, что ваш список никогда не станет больше, чем какое-либо известное, достаточно маленькое значение, вы можете выделить array из struct node в качестве своей "кучи", и ваш член next может бытьзначение индекса массива:

struct node
{
  T data;
  int next; // holds the *index* of the next element
} heap[SOME_SIZE];

Затем вы инициализируете свою «кучу», чтобы каждый элемент явно указывал на следующий в массиве:

for ( int i = 0; i < SOME_SIZE-1; i++ )
{
  heap[i].next = i+1;
}
heap[SOME_SIZE-1].next = -1; // use -1 to indicate "null"

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

int avail = 0;  // initially points to the first element in the "heap"
int head  = -1; // initially "null"

«Выделение» узла затем просто становится вопросом поискаПервый свободный узел в «куче»:

int node = avail;         // get the index of the next available node in the "heap";
avail = heap[avail].next; // update avail to point to the next available node

«Освобождение» узла означает просто добавление этого индекса обратно в начало списка avail:

heap[node].next = avail; // set this node point to the first free element
avail = node;            // make this node the first free element;

Помните,node и avail не являются объектами узлов, они просто являются индексами в массиве объектов узлов.

Обычно мы так не делаем, потому что next концептуально проще указывать непосредственно на другой объект struct node, а не быть индексом в массиве.Мы все еще можем использовать массив фиксированного размера в качестве нашей «кучи», мы просто используем адрес каждого элемента вместо его индекса.

Answer 2

для связанного списка запись next (или как там ее имя) должна указывать на следующий узел.В вашем случае тип узла - tag-name.

, поэтому вам нужно <type> next;

в C (отличается для c ++), так как вы запрашиваете указатель на структуру с именем x, это делать struct x *.Следовательно, код, который вы видите, сбивает вас с толку.Вы можете упростить это?Да, ты можешь.С имеет typedef.Вы можете сделать

typedef struct tag-name node;

, и теперь вы можете иметь

struct tag-name
{
   type member1;
   type member2;
   .......
   .......
   node *next;
 };

Вы спрашиваете, могу ли я иметь void* next.Да, но зачем это делать?Вам придется продолжать приводить этот указатель к указателю на структуру (компилятор не знает неявно, на что он указывает), также читатель кода будет удивлен, поскольку ожидает, что следующий указатель будет указателем на узел.

Вы спрашиваете, может ли это быть int next.Нет, не может, следующий объект - это узел, а не int