Ошибка сегментации при освобождении узла связанного списка

LNode * deleteNext (LNode *L) {
if (L == NULL) { return L; }

LNode *deleted = L->next;
L->next = L->next->next;
//L->next->next = NULL;

delete deleted;
return L->next;
}

Это функция для удаления следующего узла заостренного узла, простая логика. Текущий код работает отлично. Но если я раскомментирую закомментированную строку, произойдет ошибка сегментации, которая кажется мне странной. Заранее спасибо.

0

Решение

Это неправильная реализация. Что, если L->next нулевой?

Вот одна из возможных (правильных) реализаций:

LNode * deleteNext (LNode *L)
{
if (L == NULL || L->next == NULL) return NULL;

LNode *deleted = L->next; //L->next is NOT NULL
L->next = L->next->next;
//^^^^^^^^^^^^ could be NULL though

delete deleted;
return L->next; //L->next could be NULL here
}

Теперь вам решать, что вы хотите вернуть из функции. Вы могли бы вернуться L вместо L->nextили вы могли бы вернуться std::pair<LNode*, bool> содержащий L и логическое значение, указывающее, сделано ли удаление или нет.

1

Другие решения

Все зависит от того, как реализованы голова и хвост вашего списка. Я буду предполагать, что последний элемент списка имеет следующую ссылку, установленную на ноль (то есть список не является замкнутым кольцом сам по себе).

Вызов концептуально неверен. Вы не можете обрабатывать односвязный список, не сохраняя ссылку на его заголовок (первый элемент), если только вы не используете первый элемент в качестве заголовка, что уродливо и неэффективно.

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

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

LNode * removeNext (LNode *L)
{
if (L == NULL) panic ("Caller gave me a null pointer. What was he thinking?");
// should panic if the caller passes anything but a valid element pointer,
// be it NULL or 0x12345678

LNode * removed = L->next;
if (removed = NULL) return NULL; // L is the end of list: nothing to remove
L->next = removed->next; // removed does exist, so its next field is valid

// delete removed; // use this for the void deleteNext() variant
return removed;
}

Это не сможет полностью очистить список. По крайней мере, один элемент останется в нем (так сказать, псевдоголовый).

Также вам придется инициализировать список указанной псевдоголовкой. Вызов removeNext с псевдоголовкой безопасен, это будет эквивалентно использованию списка в качестве LIFO.
Однако эта реализация не позволит легко использовать ее в качестве FIFO, поскольку не будет простого способа сохранить фиксированную ссылку на хвост (последний элемент) списка.

То, как я бы это сделал, выглядит примерно так:

typedef struct _buffer {
struct _buffer * next;
unsigned long    data;
} tBuffer;

typedef struct {
tBuffer * head;
} tLIST;

/* ---------------------------------------------------------------------
Put a buffer into a list
--------------------------------------------------------------------- */
static void list_put (tLIST * mbx, tBuffer * msg)
{
msg->next = mbx->head;
mbx->head = msg;
}

/* ---------------------------------------------------------------------
get a buffer from a list
--------------------------------------------------------------------- */
static tBuffer * list_get (tLIST * mbx)
{
tBuffer * res;

/* get first message from the mailbox */
res = mbx->head;

if (res != NULL)
{
/* unlink the buffer */
mbx->head = res->next;
}

return res;
}

(Я написал это еще в середине 90-х. Подлинный винтаж ANSI C. Ах, это были дни …)

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

std :: templates предлагает вам все, о чем вы могли мечтать с точки зрения структур хранения, и они были протестированы и оптимизированы за последние 20 лет или около того. Ни один живой человек (за исключением, возможно, Дональда Кнута) не мог добиться успеха с нуля.

0

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector