Структура In C для связанного списка - PullRequest
Новая
       17

Структура In C для связанного списка

1 голос
/ 10 января 2011

Извините, что задал такой глупый вопрос, но я действительно запутался. 

struct Amit
{
  int a;
  struct Amit *link;
}
*start;

Здесь и *link, и *start используются для указания на узел связанного списка, но в чем разницамежду этими двумя, и почему мы не можем поместить *start в тело структуры?

Ответы [ 4 ]

5 голосов
/ 10 января 2011

link является членом типа структуры. Каждая структура типа struct Amit имеет одну.

start - это переменная типа указатель на struct Amit. В любой момент времени может быть не более одной переменной с именем start visible.

Вы можете поместить start внутри структуры, но она станет членом структуры (например, link), и вам все равно придется объявлять переменные типа структуры или указатели на них.

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

struct Amit *item = start;
while (item != NULL && item->a != value_wanted)
    item = item->link;

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

Глядя на комментарии и объясняя немного больше ...

Один из способов создать список: 

struct Amit root = { 0, NULL };
struct Amit *start = &root;

Переменная root является структурой, инициализированной root.a == 0 и root.link == NULL (или, что эквивалентно, root.link == 0). Переменная-указатель start указывает на (сохраняет адрес) root. Учитывая новый узел: 

struct Amit next = { 1, NULL };

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

next.link = start;
start = &next;

Более вероятным способом создания списка является динамическое распределение узлов, включая корневой узел. Согласованность имеет решающее значение, потому что вы должны освободить динамически распределенные узлы, а некоторые узлы динамически распределяются, а другие не беспорядочно. (Я предполагаю, что функция void *emalloc(size_t nbytes); является функцией покрытия для malloc(), которая никогда не возвращает нулевой указатель - поэтому она выполняет проверку ошибок для меня.) 

// Create the empty list
start = emalloc(sizeof(*start));
start->a = 0;
start->link = NULL;

// Create a node
struct Amit *node = emalloc(sizeof(*node));
node->a = 42;
node->link = NULL:

// Add the node to the font of the list
node->link = start;
start = node;

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

struct Amit *add_node(struct Amit *start, int value)
{
    struct Amit *node = emalloc(sizeof(*node));
    node->a = value;
    node->link = start;
    return start;
}

start = add_node(start, 42);
start = add_node(start, 30);
start = add_node(start, 18);

for (node = start; node->link != 0; node = node->link)
    printf("Node: %d (%p)\n", node->a, node->link);
* * И т.д. тысяча сорок-девять
2 голосов
/ 10 января 2011

Это в основном определяет три вещи:

  • a struct (кстати, не пишите с заглавной буквы как Struct)
  • переменная-член в структуре с именем link
  • переменная вне структуры с именем start

Вы можете уменьшить путаницу, отделив определение структуры от объявления переменной start, например так:: 

struct Amit
{
  int a;
  struct Amit *link;
};

struct Amit *start;
0 голосов
/ 21 октября 2016

Старт указывает на верхнюю часть списка и доступен для вашей программы по всему миру. Принимая во внимание, что ссылка просто отслеживает следующий элемент и доступна при обращении к определенному «узлу». Посмотрите на эту диаграмму, это может помочь вам понять визуально!

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

+------+     +------+     +------+
| data |     | data |     | data |
+------+     +------+     +------+
| link |---->| link |---->| link |----> NULL
+------+     +------+     +------+
   ^
   |
 START (Keep track of the whole list.)

Надеюсь, это поможет прояснить.

0 голосов
/ 10 января 2011

Если вы переименуете «link» в «next», это поможет вам лучше понять это.Связанный список похож на цепочку - ваш «старт» (или, как обычно называют, «заголовок» списка) является первым кольцом цепочки, а следующее кольцо цепочки связывается с ним через указатель «следующий» (в вашем случае указатель вашей "ссылки").Вы знаете, что получили последний элемент в своей цепочке, когда нет других колец (ссылка NULL).

...