Для начала, работа над списком связанных ссылок (круговым) в качестве введения в связанные списки требует немного больше размышлений и понимания, чем простой список Head-> Tail, где указатель last->next просто * 1002.*.Возьмем, к примеру, некруглый список :
Singly Linked-List (non-circular)
Node1 Node2 Node3
+------------+ +------------+ +------------+
| Payload | | Payload | | Payload |
+------------+ +------------+ +------------+
| Next |------->| Next |------->| Next |--->NULL
+------------+ +------------+ +------------+
Выше, просто цепочка (соединение узлов через указатель next - это все, что нужнопри установке указателя last->next на NULL. Это делает добавление в список тривиальным, так как вы можете просто добавить новый узел в качестве нового 1-го узла, каждый раз меняя адрес списка, например,
list *newnode = malloc (sizeof *newnode); /* validate, set data values, ... */
newnode->next = list;
list = newnode;
или вы можете просто выполнить итерацию while (node->next != NULL), а затем добавить новый узел в конце, например,
node->next = newnode;
newnode->next = NULL;
Некруглый список обладает преимуществом простоты, но имеет тот недостаток, что позволяет выполнять итерациюот начала до конца списка. Вы не можете выполнять итерацию от любого узла обратно к узлу непосредственно перед ним из любой точки списка (это может иметь большое значение для эффективности с большими списками)
Чтобы решить эту проблему, список циклический имеет указатель last->next, указывающий на начало списка. С этим одним дополнением вы можете перебирать iter = current; по всему списку while (iter->next != current)Вы можете выполнять итерацию от любой точки в списке до любой другой точки в списке, не начиная сначала.Это вносит лишь немного дополнительной сложности.Подумайте об этом:
Singly Linked-List (circular)
Node1 Node2 Node3
+------------+ +------------+ +------------+
| Payload | | Payload | | Payload |
+------------+ +------------+ +------------+
+--->| Next |------->| Next |------->| Next |--->+
| +------------+ +------------+ +------------+ |
| |
+<--------------------<---------------------<----------------------+
Теперь, когда вы добавляете узлы в список, у вас есть пара особых случаев, чтобы гарантировать, что вы справитесь.Например, при добавлении первого узла, поскольку список является круглым, первый узел имеет самоссылку (или самоссылку, из-за отсутствия лучших слов), например,
Singly Linked-List (circular) - 1st Node is Self-Referencial
Node1
+------------+
| Payload |
+------------+
+--->| Next |--->+
| +------------+ |
| |
+<---------------------+
Это не добавляет большой сложности, но требует, чтобы вы немного глубже подумали о том, как вы добавляете узлы в список, и убедитесь, что указатель last->next всегда указывает назад на начало списка.Это также требует большей осторожности при переборе по списку, потому что вы перебираете, пока указатель current->next не станет равным начальной точке (обычно это адрес списка, но может быть любым узлом).
Начало спискаобучение с круговым списком - это хорошо, но вы должны держать указатели прямо в голове.Лучший способ сделать это - просто вытащить карандаш и нарисовать узлы, над которыми вы работаете (так же, как поля, которые я использовал в качестве диаграммы), и когда вам нужно добавить узел, убедитесь, что вы снова подключили весь указательправильно, когда вы вставляете новый узел в список.То же самое работает для удаления узла из списка.Используйте свой ластик, чтобы избавиться от него, а затем закодируйте перемонтирование указателей, чтобы снова соединить ваш список.
Ваш код усложняет задачу, не используя описательные имена переменных (по крайней мере, смешивание детей и игроков и ребенка и т. д. ... не сработало в моем уме) Каждый узел в вашем struct будет содержать одинplayer, не кратно children.Удержание форм имен переменных единственного числа и множественного числа имеет большое значение для сохранения логики.Немного переименования, например,
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXNM 32 /* avoid generic defines like SIZE (maxname?) */
typedef struct _node {
char player[MAXNM];
struct _node *next;
} node;
( примечание: простое создание node a node также помогает, и нет необходимости создавать глобальный указатель на firstnode. Вместо этого просто создайте удобный typedef для использования в вашем коде.)
Затем в main() вы также будете использовать буфер с именем player для хранения ввода, прочитанного пользователем, например
int main (void) {
char player[MAXNM] = "";
int nplayers = 0;
node *list = NULL;
Просто примечание, вам не нужно многократные операторы printf для вывода нескольких строк текста или для предотвращения смещения текста со стороны вашей страницы.В C строки в кавычках объединяются.Кроме того, в то время как ваш компилятор, вероятно, внесет изменение в качестве автоматической оптимизации, если у вас нет спецификаторов преобразования в вашей строке, вы также можете использовать puts или fputs и избегать вызова переменная функция , если это не требуется.Например,
fputs ( " Welcome To The Count Out Game!\n"
"------------------------------------\n\n"
"How Many Children Will Be Playing? : ", stdout );
(зачем использовать fputs здесь вместо puts? - это хорошая вещь, чтобы понять ...)
Далее, вы должны проверить Все пользовательский ввод и обрабатывать любые ошибки, которые возникают.В противном случае вы будете отклоняться в Undefined Behavior , обрабатывающий мусор и неопределенные значения, пока с вашей программой не произойдут очень плохие вещи.В то время как вам лучше обслуживать, используя fgets, а затем вызывая sscanf для анализа значения (или strtol и т. Д.), scanf может быть правильно использовано, если вы как минимум проверите возврат.Таким образом, вы можете проверить, что, по крайней мере, ожидаемое количество конверсий имело место, и у вас есть действительный ввод в вашей переменной:
if (scanf ("%d", &nplayers) != 1 || nplayers < 1) {
fputs ("error: invalid integer input.\n", stderr);
return 1;
}
Но ловушки при использовании scanf в том, что он оставит завершающий '\n' (генерируется пользователем, нажимающим Введите ) во входном буфере, и вы должны обработать это, прежде чем принимать ввод с помощью fgets или другого нечислового или другого спецификатора преобразования, кроме "%s" (который сам добавляетцелый другой список проблем, созданный тем фактом, что он перестает читать на первом пробеле - поэтому, если после пробела появляются дополнительные / случайные символы, у вас возникают проблемы)
Таким образом, вы можете удалить любые дополнительныесимволы, которые остаются в вашем входном буфере (stdin здесь).Вы можете сделать это просто в цикле и getchar() (или fgetc() при чтении из другого потока открытых файлов), например,
/* remove any additional characters from stdin */
for (int c = getchar(); c != '\n' && c != EOF; c = getchar()) {}
, что приводит нас к вашему циклу ввода для имен игроков, где вы будетепозвоните insertnode (или createList), чтобы начать добавлять узлы в ваш список (и показать завершение main())
/* prompt for player and insert node in list */
while (nplayers-- &&
fputs ("name: ", stdout) != EOF &&
fgets (player, MAXNM, stdin)) {
player[strcspn (player, "\n")] = 0; /* trim '\n' from end */
if (!insertnode (&list, player))
break;
}
displaylist (list); /* output all players in list */
freelist (list); /* free list memory */
return 0;
}
Обратите внимание выше, где вызывается insertnode (&list, player).Вы передаете адрес списка в функцию вставки.Вы делаете это так, если адрес списка (то есть первый узел) изменяется, новый адрес списка будет доступен обратно в вызывающей функции.Если вам не удалось передать адрес указателя списка, вам нужно будет вернуть адрес списка из функции и назначать его каждый раз обратно в вызывающей функции.
Вам также необходимообъявить вашу функцию с значимым типом возврата , который может указывать успех / неудача операции вставки.Удобно просто возвращать указатель на узел, который был вставлен в случае успеха, или NULL в случае ошибки - это нормально.
В вашей функции вставки, кроме проверки player, это не NULL, вам нужноопределить, существует ли список, и, если нет, добавить новый узел в качестве 1-го узла (установив указатель next так, чтобы он указывал на себя), - или-- вам нужно выполнить итерацию до конца списка и вставить новыйузел там.Каждый раз, когда указатель next указывает на адрес списка.Простая реализация будет выглядеть так:
node *insertnode (node **list, char *player)
{
/* validate player not NULL, handle error */
if (!player)
return NULL;
/* allocate/validate new node */
node *newnode = malloc (sizeof *newnode);
if (!newnode) {
perror ("malloc-newnode");
return NULL;
}
/* copy player to node, initialize next NULL */
strcpy (newnode->player, player);
newnode->next = NULL;
/* check whether list exists, or is this 1st node? */
if (!*list) {
newnode->next = newnode; /* circular list is self-referencial */
*list = newnode;
}
else { /* list exist, find last node in circular list */
node *iter = *list; /* create pointer to iterate to end */
for (; iter->next != *list; iter = iter->next) {} /* iterate */
iter->next = newnode; /* insert as last node */
newnode->next = *list; /* circular, set next to *list */
}
return newnode; /* return node as convenience & success/failure */
}
Для любых других функций, которые вы хотите написать для своего списка, достаточно просто вытянуть карандаш и решить, как перебирать список, чтобы получить необходимые данные.из списка.Например, вы можете предоставить список печати или функцию displaylist(), а также функцию для освобождения памяти, связанной со списком.
Обратите внимание на тонкости обработки итерации (в случае удаления функции freelist, начинающей удаление 2-го узла, чтобы указатель last->next ссылался на действительный адрес, указывающий конец вашегоитерация), например,
void displaylist (node *list)
{
node *iter = list;
/* iterate from first to last node, setting iter NULL after last */
for (; iter; iter = (iter->next != list ? iter->next : NULL))
puts (iter->player);
}
void freelist (node *list)
{
node *victim = list->next, /* free 2nd node 1st, leaving valid 1st */
*next = NULL;
while (victim != list) { /* while victim isn't list address */
next = victim->next; /* save next address before free */
free (victim); /* free victim */
victim = next; /* assign next to victim */
}
free (victim); /* free 1st node */
}
В целом, вы получите что-то вроде следующего:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXNM 32 /* avoid generic defines like SIZE (maxname?) */
typedef struct _node {
char player[MAXNM];
struct _node *next;
} node;
node *insertnode (node **list, char *player);
void displaylist (node *list);
void freelist (node *list);
int main (void) {
char player[MAXNM] = "";
int nplayers = 0;
node *list = NULL;
fputs ( " Welcome To The Count Out Game!\n"
"------------------------------------\n\n"
"How Many Children Will Be Playing? : ", stdout );
if (scanf ("%d", &nplayers) != 1 || nplayers < 1) {
fputs ("error: invalid integer input.\n", stderr);
return 1;
}
/* remove any additional characters from stdin */
for (int c = getchar(); c != '\n' && c != EOF; c = getchar()) {}
/* prompt for player and insert node in list */
while (nplayers-- &&
fputs ("name: ", stdout) != EOF &&
fgets (player, MAXNM, stdin)) {
player[strcspn (player, "\n")] = 0; /* trim '\n' from end */
if (!insertnode (&list, player))
break;
}
displaylist (list); /* output all players in list */
freelist (list); /* free list memory */
return 0;
}
node *insertnode (node **list, char *player)
{
/* validate player not NULL, handle error */
if (!player)
return NULL;
/* allocate/validate new node */
node *newnode = malloc (sizeof *newnode);
if (!newnode) {
perror ("malloc-newnode");
return NULL;
}
/* copy player to node, initialize next NULL */
strcpy (newnode->player, player);
newnode->next = NULL;
/* check whether list exists, or is this 1st node? */
if (!*list) {
newnode->next = newnode; /* circular list is self-referencial */
*list = newnode;
}
else { /* list exist, find last node in circular list */
node *iter = *list; /* create pointer to iterate to end */
for (; iter->next != *list; iter = iter->next) {} /* iterate */
iter->next = newnode; /* insert as last node */
newnode->next = *list; /* circular, set next to *list */
}
return newnode; /* return node as convenience & success/failure */
}
void displaylist (node *list)
{
node *iter = list;
/* iterate from first to last node, setting iter NULL after last */
for (; iter; iter = (iter->next != list ? iter->next : NULL))
puts (iter->player);
}
void freelist (node *list)
{
node *victim = list->next, /* free 2nd node 1st, leaving valid 1st */
*next = NULL;
while (victim != list) { /* while victim isn't list address */
next = victim->next; /* save next address before free */
free (victim); /* free victim */
victim = next; /* assign next to victim */
}
free (victim); /* free 1st node */
}
Пример использования / Вывод
Краткий пример его использования:
$ ./bin/ll-cir_players
Welcome To The Count Out Game!
------------------------------------
How Many Children Will Be Playing? : 5
name: Tom
name: Dick
name: Harry
name: Gus
name: Sarah
Tom
Dick
Harry
Gus
Sarah
Использование памяти / проверка ошибок
В любом написанном вами коде, который динамически выделяет память, у вас есть 2 обязанности в отношении любого выделенного блока памяти: (1) всегда сохраняют указатель на начальный адрес для блока памяти, поэтому (2) он может быть освобожден , когдаон больше не нужен.
Крайне важно, чтобы вы использовали программу проверки ошибок памяти, чтобы гарантировать, что вы не пытаетесь получить доступ к памяти или писать за пределами / за пределами выделенного блока, пытаться прочитать или основать условный переход на неинициализированном значении и, наконец,, чтобы подтвердить, что вы освобождаете всю выделенную память.
Для Linux valgrind - нормальный выбор.Для каждой платформы есть похожие проверки памяти.Все они просты в использовании, просто запустите вашу программу через него.
$ valgrind ./bin/ll-cir_players
==29803== Memcheck, a memory error detector
==29803== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==29803== Using Valgrind-3.12.0 and LibVEX; rerun with -h for copyright info
==29803== Command: ./bin/ll-cir_players
==29803==
Welcome To The Count Out Game!
------------------------------------
How Many Children Will Be Playing? : 5
name: Tom
name: Dick
name: Harry
name: Gus
name: Sarah
Tom
Dick
Harry
Gus
Sarah
==29803==
==29803== HEAP SUMMARY:
==29803== in use at exit: 0 bytes in 0 blocks
==29803== total heap usage: 5 allocs, 5 frees, 200 bytes allocated
==29803==
==29803== All heap blocks were freed -- no leaks are possible
==29803==
==29803== For counts of detected and suppressed errors, rerun with: -v
==29803== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
Всегда подтверждайте, что вы освободили всю выделенную память и что ошибок памяти нет.
Теперь этозакончилась намного дольше, чем ожидалось, но было ясно, что вы совершенно потеряли понимание и приблизились к односвязному круговому связанному списку .Надеемся, что это даст вам базовое понимание и позволит вам двигаться вперед отсюда.