Понимание функций типа со связанным списком - PullRequest
Новая
       8

Понимание функций типа со связанным списком

0 голосов
/ 02 декабря 2018

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

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

ElementoDiLista* deleteDuplicates(ElementoDiLista* head)
{
    if (head == NULL)
    {
        return NULL;
    }
    if (head->next == NULL)
    {
        return head;
    }
    if (head->info == head->next->info)
    {
        ElementoDiLista *tmp;
        tmp = head->next;
        head->next = head->next->next;
        free(tmp);
        return deleteDuplicates(head);
    }
    else
    {
        head->next = deleteDuplicates(head->next);
        return head;
    }
}

С определением моей структуры и составить список следующим образом: 

struct el {int info; struct el *next;};
typedef struct el ElementoDiLista;
typedef ElementoDiLista *ListaDiElementi;

А затем в основном я вызываю функцию следующим образом: 

Lista1 = deleteDuplicates(Lista1);

Где Lista1 объявлен следующим образом: ElementoDiLista Lista1 = NULL

Мой вопрос был, я был использован для объявления функций, которые void или зависят от отдельных типов (int, float ecc ...) Я хотел бычтобы уточнить две вещи:

  1. Почему функция объявлена ​​как ElementoDiLista* deleteDuplicates(ElementoDiLista* head), потому что для меня это более интуитивно понятно ListaDiElementi deleteDuplicates (ListaDiElementi *head), но, к сожалению, не работает.

  2. Мне не очень понятно, почему функция возвращает значения head или NULL, но по этой причине я думаю, почему в основном Lista1 принимает значение функции, потому что функция изменяет сам списокя не так лихт?

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

Спасибо, все равно!

1 Ответ

0 голосов
/ 02 декабря 2018

Почему функция объявлена ​​как ElementoDiLista* deleteDuplicates(ElementoDiLista* head), потому что для меня это более интуитивно понятно ListaDiElementi deleteDuplicates (ListaDiElementi *head)

Начиная с аргумента, первоначально она объявляется как, 

ElementoDiLista* head

, поэтому требуется указатель на элемент head.Это было бы эквивалентно (с изменением имени переменной): 

ListaDiElementi list

Таким образом, мы передаем в качестве аргумента «список», который является указателем на заголовок.Этот указатель не изменен.Чтобы действительно изменить его, нам нужно использовать, как вы предлагаете, 

ElementoDiLista** head

или, что эквивалентно и, возможно, более читабельно, 

ListaDiElementi* list

Поэтому возникает вопрос, "делаем ли мынужно изменить указатель на заголовок "? Или, другими словами, нужно ли изменить исходный указатель списка?Ответ нет .

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

Мне не очень понятно, почему функция возвращает значения head или NULL, но по этой причине я думаю, почему в основном Lista1 принимает значение функции, потому что функция изменяет списоксам, я прав?

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

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

Во-вторых, посмотрите на код, 

if (head == NULL)
{
    return NULL;

Возвращено head, поскольку оно равно нулю.

if (head->next == NULL)
{
    return head;

Вернул голову снова.

if (head->info == head->next->info)
{
    ElementoDiLista *tmp;
    tmp = head->next;
    head->next = head->next->next;
    free(tmp);
    return deleteDuplicates(head);
}

Возвращает deleteDuplicates(head), а head - исходный аргумент, который не изменился.Так что, если все остальные дела вернутся в голову, то так и будет.

else
{
    head->next = deleteDuplicates(head->next);
    return head;
}

Это также возвращает head (примечание head не изменилось).Поэтому его возвращаемое значение всегда является исходным аргументом head.Так что это бессмысленно.

Кроме того, обратите внимание, что в первых двух случаях вы ничего не делаете, вы просто возвращаете значение, которое бесполезно.

if (head == NULL)
{
    return NULL;
}
if (head->next == NULL)
{
    return head;
}

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

...