Функции C, чтобы найти и удалить узел из односвязанный список


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

То, что кажется безвкусным мне про мое решение ниже, хотя я не знаю лучшего способа выразить то, что код должен проверить первую запись в индивидуальном порядке (т. е. частный случай), то как он проходит через итерации, это не проверка ИТЭР, это проверка ИТЭР->вперед, вперед итератора нынешнее место, потому что в односвязанный список вы не можете идти в обратном направлении.

Итак, есть ли более рациональный способ, чтобы написать delete_item() функция?

#include <stdio.h>
#include <stdlib.h>

struct node {
    int x;
    struct node *next;
};

struct node *head;

struct node *create_item(int x);
void print_list();
void delete_item(int x);

int main(int argc, int argv) {

    struct node *n;
    int i;

    // initialise a linked list with a few items
    head = create_item(1);
    n = head;

    for (i = 2; i < 10; i++) {
        n->next = create_item(i);
        n = n->next;
    }

    // before
    print_list();

    // delete 7.
    delete_item(7);

    // after
    print_list();

    // lets delete all odd numbers for effect.
    delete_item(1);
    delete_item(3);
    delete_item(5);
    delete_item(9);

    print_list();
}

struct node *create_item(int x) {
    struct node *new;

    new = (struct node *) malloc (sizeof(struct node));
    new->x = x;
    return new;
}

void print_list() {
    struct node *iter;

    iter = head;

    while (iter != NULL) {
        printf("num: %i\n", iter->x);
        iter = iter->next;
    }
}

//We're looking for the best way to right this.
//This is _my_ standard solution to the problem.
// (that is, to test the first element explicitly
// the use current->next != NULL to be one behind
// the search).
//I wondered what other people's is or if there
//is a convention?
void delete_item(int x) {

    struct node *iter;
    iter = head;

    if (iter == NULL) {
        printf("not found\n");
        return;
    }

    if (iter->x == x) {
        printf("found in first element: %i\n", x);
            head = head->next;
        return;
    }

    while (iter->next != NULL) {
        if (iter->next->x == x) {
            printf("deleting element: %i\n", x);
            iter->next = iter->next->next;
            return;
        }

        iter = iter->next;
    }

    printf("not found\n");
}

Это полный пример, который может быть собран и протестирован. Вывод:

23:28: ~$ gcc -o ll linked_list.c
23:28: ~$ ./ll
num: 1
num: 2
num: 3
num: 4
num: 5
num: 6
num: 7
num: 8
num: 9
deleting element: 7
num: 1
num: 2
num: 3
num: 4
num: 5
num: 6
num: 8
num: 9
found in first element: 1
deleting element: 3
deleting element: 5
deleting element: 9
num: 2
num: 4
num: 6
num: 8


27529
12
задан 31 января 2011 в 11:01 Источник Поделиться
Комментарии
5 ответов

Если вы не против рекурсии (хотя с программистами вообще разум), то вы можете сделать:

node* delete_item(node* curr, int x) {
node* next;
if (curr == NULL) { // Found the tail
printf("not found\n");
return NULL;
} else if (curr->x == x) { // Found one to delete
next = curr->next;
free(curr);
return next;
} else { // Just keep going
curr->next = delete_item(curr->next, x);
return curr;
}
}

затем, в главном, вы должны сделать

head = delete_item(head, 7);

Это использует стек с удерживать кнопку "назад посмотри" в списке.

5
ответ дан 1 февраля 2011 в 04:02 Источник Поделиться

Самый аккуратный способ справиться с этим, чтобы использовать то, что меня учили как "2 указатель фокус" (спасибо Чарльз Линдси много лет назад):

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

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

Непроверенный эскиз, используя эту идею для delete_item (в C++) выглядит так:

void delete_item(node** head, int i) {
for (node** current = head; *current; current = &(*current)->next) {
if ((*current)->x == i) {
node* next = (*current)->next;
delete *current;
*current = next;
break;
}
}
}

Этот цикл будет перерыв после первой записи он находит, но если убрать "перерыв", то он будет удалять все записи, которые соответствуют.

17
ответ дан 2 февраля 2011 в 01:02 Источник Поделиться

Общие Замечания:

Почему ваш список функций обработки не принимает список в качестве параметра?
В результате ваше приложение может иметь только один список.

Комментарии на "Удалить":

Вы не подтекает элемента списка, когда вы удалите его.

Поскольку create_item() - это вызов функции malloc() я ожидаю, что delete_item() позвонить бесплатно().

Я бы разделил delete_item() на две части. Первая часть, которая занимается руководитель, как особый случай и вторая часть, которая занимается удалением элементов из списка (и бесплатно()Инг них).

void delete_item(struct node** list, int x)
{
if ((list == NULL) || ((*list) == NULL))
{
printf("not found\n");
return;
}

(*list) = delete_item_from_list(*list);
}

struct node* delete_item_from_list(struct node* head)
{
struct node* iter = head;
struct node* last = NULL;

while (iter != NULL)
{
if (iter->x == x)
{
break;
}

last = iter;
iter = iter->next;
}

if (iter == NULL)
{
printf("not found\n");
}
else if (last == NULL)
{
printf("found in first element: %i\n", x);
head = iter->next;
}
else
{
printf("deleting element: %i\n", x);
last->next = iter->next;
}

free(iter);
return head;
}

6
ответ дан 1 февраля 2011 в 12:02 Источник Поделиться

Давненько я сделал на C++, но вот мои наблюдения:

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

if (iter == NULL) {
printf("not found\n");
return;
}

ИТЭР находится в голову связанного списка, а если список еще не существует, вы отвечаете, что товар "не найдена\п". Я хотел бы изменить это, чтобы "связанный список пуст.\Н"

if (iter->x == x) {
printf("found in first element: %i\n", x);
return;
}

Это не похоже на работу в том смысле, что он фактически не удаляет элемент. Если вы хотите, чтобы этот пункт исключить-который я предполагаю, что вы делаете, дается название функции, то вы должны добавить эту строку: голова = Голова->далее; (, Вам необходимо пройти глава параметра "по ссылке", чтобы убедиться, что это изменение будет распространяться за пределами кодекса delete_item функции. Обычно, если параметр передается не указатель, это будет сделано путем передачи указателя. руководителем является узел*, однако, и я уже забыл, как передать указатель по ссылке... я думаю, что это будет либо узел* и головы или узла** глава ... жаль, но вы будете иметь, чтобы выяснить это! :) ) В качестве альтернативы, вы могли бы delete_item вернуть узел *и в конце функции, то первая запись, и это будет называться по голове=delete_item(глава х). Это, наверное, слегка неодобрительно, чтобы сделать это таким образом, но это будет легкий путь.

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

while (iter->next != NULL) {
if (iter->next->x == x) {
printf("deleting element: %i\n", x);
iter->next = iter->next->next;
return;
}

iter = iter->next;
}

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

if (!entryfound) printf("not found\n");

entryfound должны быть объявлены, чтобы быть 0, и значение 1 , если матч был найден в то время как петли. В качестве альтернативы, вы могли бы сделать entryfound++ в случае, если матч и изменить последнюю строчку:

if (entryfound) { printf("%i matches found and deleted.\n", entryfound); }
else { printf("No matches found.\n"); }

После внесения изменений, это то, что ваш код должен выглядеть:

#include <stdio.h>
#include <stdlib.h>

struct node {
int x;
struct node *next;
};

struct node *create_item(int x);
void print_list(node *head);
void delete_item(node *&head, int x);

int main(int argc, int argv) {
struct node *head, *tail;

// initialise a linked list with a few items
head = create_item(1);
tail = head;

for (int i = 2; i < 10; i++) {
tail->next = create_item(i);
tail = tail->next;
}

// before
print_list(head);

// delete 7.
delete_item(head, 7);

// after
print_list(head);

// lets delete all odd numbers for effect.
delete_item(head, 1);
delete_item(head, 3);
delete_item(head, 5);
delete_item(head, 9);

print_list(head);
}

struct node *create_item(int x) {
struct node *new;

new = (struct node *) malloc (sizeof(struct node));
new->x = x;
return new;
}

void print_list(node *iter) {
int i=0;

if (iter==NULL} { printf("Linked list is empty.")); }
else {
while (iter != NULL) {
printf("Index: %i, Value=%i\n", i, iter->x);
iter = iter->next;
}
}
}

//We're looking for the best way to right this.
//This is _my_ standard solution to the problem.
// (that is, to test the first element explicitly
// the use current->next != NULL to be one behind
// the search).
//I wondered what other people's is or if there
//is a convention?

void delete_item(node *&head, int x) {
int i=0;
node* iter=head; // Head might have to be dereferenced here... I forget!

if (iter==NULL) {
printf("Linked list is empty.\n");
return;
}

if (iter->x == x) {
printf("Deleting Item. Index: %i, Value=%i\n", i, x);
head = head->next;
entryfound++;
}

while (iter->next != NULL) {
i++;
if (iter->next->x == x) {
printf(Deleting Item. Index: %i, Value=%i\n", i, x);
iter->next = iter->next->next;
entryfound++;
}

iter = iter->next;
}

if (entryfound) { printf("%i matches found and deleted.\n", entryfound); }
else { printf("No matches found.\n"); }

}

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

Снова, это было долгое время, так как я сделал на C++, но это мое мнение. К сожалению для любой отладки, которые вы могли бы сделать в этот код.

4
ответ дан 1 февраля 2011 в 12:02 Источник Поделиться

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


  1. При удалении элемента, поиск по списку, чтобы найти предыдущий элемент, затем отцепить.
  2. Есть "удаленные" флаг для каждого элемента. При обходе списка для какой-то другой причине, проверьте папку "Удаленные" флаг на каждом узле. Если встречается "узел стертые", отвязать его от ранее посещаемых узлов.

Обратите внимание, что в мусора систему, можно добавить элементы в начало списка, или выполните #2 стиль удаление, в замок-бесплатный потокобезопасным способом. Узлов, которые удаляются может получить несвязанное в одну нить и случайно перекомпоновка в другой, но удалить флаг вызовет узел, чтобы быть снова разъединены на следующий проход. В многопоточной системе, требует явного освобождения, такая отключения и повторного подключения последовательности могут быть катастрофическими, поскольку узел может быть удален, освобожденных, и перекомпоновка; при этом замки будут необходимы, чтобы избежать проблем.

-1
ответ дан 1 февраля 2011 в 12:02 Источник Поделиться