Нет никакой магии для вставки в любом месте в связанном списке, единственная реальная проблема - держать ваши указатели прямыми при обработке трех условий:
- вставка первого узла (или нового первого узла);
- вставка узла между в некоторой позиции между существующим первым и последним узлом;и
- вставка в конец списка.
В первом случае, вставка первого (или нового первого) узла просто требует выделения нового узла, и либо вставка его является первымузел в списке или, если головной узел уже существует, установка newnode->next = head; и head = newnode;
Вставка в конце не сильно отличается, вы просто переходите к последнему узлу и устанавливаете last->next = newnode;
В случае вставки узла между ними нужно немного подумать.Самый простой способ сохранить ваши указатели прямыми - это вытащить карандаш и бумагу и нарисовать диаграмму указателя вашего списка, а затем разбить список на две части, где вам нужно вставить новый узел, и выяснить необходимые шаги перед тем, как поднять клавиатуру (так будет намного проще)
Ничего особенного не нужно, просто блок-схема с указателем next (или pNext), соединяющим узлы.Простой список подойдет двум узлам (A и B), например,
A B
+------+ +------+
| node | | node |
| next |--> | next |-->NULL
+------+ +------+
Затем просто разбейте список в точке, где будет вставлен новый узел, например,
A B
+------+ | +------+
| node | / | node |
| next |--> \ | next |-->NULL
+------+ / +------+
|
new
+------+
| node |
| next |-->
+------+
Это позволяет визуализировать необходимые шаги.Найдите node A, установите new->next = B;, установите A->next = new; ( примечание: , вы должны остановиться на узле до места, в которое вы хотите вставить новый узел)be:
A new B
+------+ +------+ +------+
| node | | node | | node |
| next |--> | next |--> | next |-->NULL
+------+ +------+ +------+
Когда вы точно поймете, что вам нужно сделать для обработки вставки, теперь поднимите клавиатуру и реализуйте эту логику.
Поскольку у вас будет одна функция вставкидля обработки всех трех случаев, как прокомментировал @WhozCraig, при обработке операций со списками (или вообще указателей, где вам может потребоваться назначить новый блок памяти в функции, изменяющей адрес указателя), помогает передать адрес указатель на вашу функцию (так что ваша функция получает сам указатель - вместо копии указателя).
Независимо от того, требуется ли вам вначале выделить для обертки списка или в простом списке, где вы можете назначить новый узел в качестве первого узла в списке, передача адреса указателя разрешает изменение в пределахфункция без необходимости возврата и назначения возврата в качестве нового адреса обратно в вызывающей функции.
Добавление пары typedefs gelement_t для типов struct GraphicElement и rgraphic_t для struct RasterGraphic, обачтобы сократить ввод некоторых неловких стилей MixedCase, вы можете думать о своей функции InsertGraphicElement следующим образом.
Во-первых, ваша InsertGraphicElement функция будет либо успешной или fail , поэтому выберите значимый тип возврата, который может указывать success или fail .При работе со списками возврат указателя на вновь вставленный узел полезен и позволяет возвращать NULL даже в случае сбоя, например,
gelement_t *InsertGraphicElement (rgraphic_t **pA)
Поскольку вы передаете указатель на указатель на ваш RasterGraphic struct, вы можете добавить данные в структуру, чтобы сделать ее немного более полезной в качестве оболочки для вашего фактического списка.Добавление счетчика узлов - это удобный способ отслеживать количество узлов в односвязном списке без необходимости каждый раз повторять список, например,
typedef struct RasterGraphic {
size_t nelements;
gelement_t *GraphicElements;
} rgraphic_t;
В вашей функции вы должны проверить, чтоу вас есть выделенный указатель, а если нет, то выделите для структуры RasterGraphic, например,
int position = 0;
if (!*pA) { /* if list NULL - allocate new list */
puts ("allocating new list.");
*pA = malloc (sizeof **pA);
if (!*pA) { /* validate every allocation */
perror ("malloc-*list");
exit (EXIT_FAILURE);
}
(*pA)->nelements = 0; /* initialize values */
(*pA)->GraphicElements = NULL;
}
Затем вы можете выделить и проверить новый узел для добавления либо в качестве первого узла, либо в позиции, например
gelement_t *node = malloc (sizeof *node); /* allocate node */
if (!node) { /* validate */
perror ("malloc-node");
exit (EXIT_FAILURE);
}
Затем соберите ваше имя файла и информацию о местоположении и установите node->fileName во вновь выделенный блок, содержащий имя файла, введенное пользователем (пара вспомогательных функций делает это намного проще), например,
node->fileName = get_filename_stdin(); /* request filename */
if (!node->fileName) { /* validate */
free (node);
return NULL;
}
node->pNext = NULL; /* set next pointer NULL */
position = get_int_stdin (*pA); /* request position */
Теперь вы находитесь в той точке функции, в которой вы обрабатываете 3 случая, указанных в начале ответа.Если узла (*pA)->GraphicElements еще нет, вы добавите первый узел (поэтому вам не нужно запрашивать позицию).Если это не первый узел, а запрашиваемая позиция 0, вы вставляете как новый первый узел.(оба могут быть обработаны в одном случае)
Если запрошенная позиция больше нуля, то вы итерируете к узлу до точки вставки и вставляете, как показано на схеме выше, и вставляете узел туда.
Один из подходов будет:
gelement_t *p = (*pA)->GraphicElements;
if (!p || position == 0) { /* insert as new head */
node->pNext = p;
(*pA)->GraphicElements = node;
}
else { /* insert at position (default end) */
int n = 0;
while (n < position - 1 && p->pNext) { /* locate node before */
p = p->pNext;
n++;
}
node->pNext = p->pNext; /* set node->pNext to current pNext */
p->pNext = node; /* set current pNext to node */
}
(*pA)->nelements++; /* increment number of elements in list */
, который будет обрабатывать вставку на основе пользовательского ввода.Осталось только:
return node; /* meaningful return to indicate success/failure */
}
( примечание: , когда вам удобна логика операций со списком, это помогает разбить эту функцию на несколько функций, которые обрабатывают операции по отдельности,как create_list(), create_node() и add_node(). (где вы создаете свой список RasterGraphic, свой узел GraphicElement и, наконец, добавляете этот узел в заданную позицию в списке - это остается вам)
Сложив его целиком и добавив вспомогательные функции, можно привести короткий пример:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h> /* for PATH_MAX */
typedef struct GraphicElement {
char* fileName;
struct GraphicElement* pNext;
} gelement_t;
typedef struct RasterGraphic {
size_t nelements;
gelement_t *GraphicElements;
} rgraphic_t;
char *get_filename_stdin (void)
{
char filename[PATH_MAX] = "";
char *newname = NULL;
fputs ("enter filename : ", stdout);
if (fgets (filename, PATH_MAX, stdin)) {
size_t len = strlen (filename);
if (len && filename[len-1] == '\n') {
filename[--len] = 0;
if (!len) {
fputs ("error: filename empty.\n", stderr);
return NULL;
}
}
else if (len == PATH_MAX) {
fputs ("error: filename exceeds PATH_MAX\n", stderr);
return NULL;
}
newname = malloc (len + 1);
if (!newname) {
perror ("malloc-newname");
exit (EXIT_FAILURE);
}
memcpy (newname, filename, len + 1);
}
return newname;
}
int get_int_stdin (rgraphic_t *list)
{
char buf[PATH_MAX];
int pos = 0;
if (!list->nelements) {
puts ("inserting as head.");
return 0;
}
fputs ("index to insert: ", stdout);
if (fgets (buf, PATH_MAX, stdin))
if (sscanf (buf, "%d", &pos) != 1 || pos < 0 ||
pos > (long)list->nelements)
return list->nelements;
return pos;
}
gelement_t *InsertGraphicElement (rgraphic_t **pA)
{
int position = 0;
if (!*pA) { /* if list NULL - allocate new list */
puts ("allocating new list.");
*pA = malloc (sizeof **pA);
if (!*pA) { /* validate every allocation */
perror ("malloc-*list");
exit (EXIT_FAILURE);
}
(*pA)->nelements = 0; /* initialize values */
(*pA)->GraphicElements = NULL;
}
gelement_t *node = malloc (sizeof *node); /* allocate node */
if (!node) { /* validate */
perror ("malloc-node");
exit (EXIT_FAILURE);
}
node->fileName = get_filename_stdin(); /* request filename */
if (!node->fileName) { /* validate */
free (node);
return NULL;
}
node->pNext = NULL; /* set next pointer NULL */
position = get_int_stdin (*pA); /* request position */
gelement_t *p = (*pA)->GraphicElements;
if (!p || position == 0) { /* insert as new head */
node->pNext = p;
(*pA)->GraphicElements = node;
}
else { /* insert at position (default end) */
int n = 0;
while (n < position - 1 && p->pNext) { /* locate node before */
p = p->pNext;
n++;
}
node->pNext = p->pNext; /* set node->pNext to current pNext */
p->pNext = node; /* set current pNext to node */
}
(*pA)->nelements++; /* increment number of elements in list */
return node; /* meaningful return to indicate success/failure */
}
/* loop over list printing values */
void prn_list (rgraphic_t *list)
{
size_t n = 0;
gelement_t *node = list->GraphicElements;
printf ("\n\n%zu nodes in list\n", list->nelements);
for (; node; node = node->pNext)
printf ("%2zu: %s\n", 1 + n++, node->fileName);
}
/* loop over list freeing memory (pay attention to victim) */
void free_list (rgraphic_t *list)
{
gelement_t *node = list->GraphicElements;
while (node) {
gelement_t *victim = node;
node = node->pNext;
free (victim->fileName);
free (victim);
}
free (list);
}
int main (void) {
rgraphic_t *list = NULL;
puts ("\nNOTE: pressing [Enter] for index - inserts at end!\n"
" [Ctrl+d] at \"filename: \" prompt to end input.\n");
while (InsertGraphicElement(&list)) {} /* create list/insert nodes */
prn_list (list); /* print list */
free_list (list); /* free list */
}
Пример использования / Вывод
$ ./bin/ll_single_insert_ptp
NOTE: pressing [Enter] for index - inserts at end!
[Ctrl+d] at "filename: " prompt to end input.
allocating new list.
enter filename : one
inserting as head.
enter filename : four
index to insert: 1
enter filename : two
index to insert: 1
enter filename : three
index to insert: 2
enter filename : five
index to insert:
enter filename :
5 nodes in list
1: one
2: two
3: three
4: four
5: five
Использование памяти / проверка ошибок
В любом написанном вами коде, который динамически распределяет память, у вас есть 2 обязанностей в отношении любого выделенного блока памяти: (1) всегда сохраняетсяуказатель на начальный адрес для блока памяти, поэтому (2) он может быть освобожден , когда он больше не нужен.
Обязательно, чтобы вы использовали ошибку памятипроверка программы, чтобы убедиться, что вы не пытаетесь получить доступ кemory или пишите за пределами / за пределами выделенного блока, попытайтесь прочитать или основать условный переход на неинициализированном значении и, наконец, подтвердить, что вы освобождаете всю выделенную память.
Для Linux valgrind - нормальный выбор.Для каждой платформы есть похожие проверки памяти.Все они просты в использовании, просто запустите вашу программу через нее.
$ valgrind ./bin/ll_single_insert_ptp
==9747== Memcheck, a memory error detector
==9747== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==9747== Using Valgrind-3.12.0 and LibVEX; rerun with -h for copyright info
==9747== Command: ./bin/ll_single_insert_ptp
==9747==
NOTE: pressing [Enter] for index - inserts at end!
[Ctrl+d] at "filename: " prompt to end input.
allocating new list.
enter filename : one
inserting as head.
enter filename : four
index to insert: 1
enter filename : two
index to insert: 1
enter filename : three
index to insert: 2
enter filename : five
index to insert:
enter filename :
5 nodes in list
1: one
2: two
3: three
4: four
5: five
==9747==
==9747== HEAP SUMMARY:
==9747== in use at exit: 0 bytes in 0 blocks
==9747== total heap usage: 12 allocs, 12 frees, 136 bytes allocated
==9747==
==9747== All heap blocks were freed -- no leaks are possible
==9747==
==9747== For counts of detected and suppressed errors, rerun with: -v
==9747== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
Всегда подтверждайте, что вы освободили всю выделенную память и что ошибок памяти нет.
Посмотрите вещии дайте мне знать, если у вас есть дополнительные вопросы.