Рубрики

Как написать функции C, которые изменяют указатель головы связанного списка?

Рассмотрим простое представление (без какого-либо фиктивного узла) связанного списка. Функции, которые работают с такими связанными списками, можно разделить на две категории:

1) Функции, которые не изменяют указатель заголовка. Примеры таких функций включают печать связанного списка, обновление элементов данных узлов, например добавление заданного значения ко всем узлам, или некоторую другую операцию, которая осуществляет доступ / обновление данных узлов
Как правило, легко определить прототип функций этой категории. Мы всегда можем передать указатель головы в качестве аргумента и пересмотреть / обновить список. Например, следующая функция, которая добавляет x к элементам данных всех узлов.

void addXtoList(struct Node *node, int x)

{

    while(node != NULL)

    {

        node->data = node->data + x;

        node = node->next;

    }

}    

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

«Учитывая связанный список, напишите функцию deleteFirst (), которая удаляет первый узел данного связанного списка. Например, если список 1-> 2-> 3-> 4, его следует изменить на 2-> 3-> 4 ”

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

2.1) Сделать указатель головы глобальным: мы можем сделать указатель головы глобальным, чтобы он мог быть доступен и обновлен в нашей функции. Ниже приведен код C, который использует глобальный указатель головы.

// глобальный указатель головы

struct Node *head = NULL;

  
// функция для удаления первого узла: используется подход 2.1
// Смотрите http://ideone.com/ClfQB для полной программы и вывода

void deleteFirst()

{

    if(head != NULL)

    {

       // сохраняем старое значение указателя головы

       struct Node *temp = head;

         

       // Изменить указатель головы, чтобы он указывал на следующий узел

       head = head->next; 

  

       // удаляем память, выделенную для предыдущего головного узла

       free(temp);

    }

}

Смотрите это для полного запуска программы, которая использует вышеуказанную функцию.

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

Посмотрите это, чтобы узнать все причины, по которым мы должны избегать глобальных переменных в наших проектах.

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

// функция для удаления первого узла: используется подход 2.2
// Смотрите http://ideone.com/P5oLe для полной программы и вывода

struct Node *deleteFirst(struct Node *head)

{

    if(head != NULL)

    {

       // сохраняем старое значение указателя головы

       struct Node *temp = head;

  

       // Изменить указатель головы, чтобы он указывал на следующий узел

       head = head->next;

  

       // удаляем память, выделенную для предыдущего головного узла

       free(temp);

    }

  

    return head;

}

Смотрите это для полной программы и вывода.
Этот подход намного лучше, чем предыдущий 1. С этим связана только одна проблема: если пользователь пропустит присвоение возвращаемого значения заголовку, то все станет грязно. Компиляторы C / C ++ позволяют вызывать функцию без присваивания возвращаемого значения.

head = deleteFirst(head);  // правильное использование deleteFirst ()

deleteFirst(head);  // неправильное использование deleteFirst (), разрешенное компилятором

2.3) Использование двойного указателя: этот подход следует простому правилу Си: если вы хотите изменить локальную переменную одной функции внутри другой функции, передайте указатель на эту переменную . Таким образом, мы можем передать указатель на указатель заголовка, чтобы изменить указатель заголовка в нашей функции deleteFirst ().

// функция для удаления первого узла: используется подход 2.3
// Смотрите http://ideone.com/9GwTb для полной программы и вывода

void deleteFirst(struct Node **head_ref)

{

    if(*head_ref != NULL)

    {

       // сохраняем старое значение указателя на указатель головы

       struct Node *temp = *head_ref;

  

       // Изменить указатель головы, чтобы он указывал на следующий узел

       *head_ref = (*head_ref)->next;

  

       // удаляем память, выделенную для предыдущего головного узла

       free(temp);

    }

}

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

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Как написать функции C, которые изменяют указатель головы связанного списка?

0.00 (0%) 0 votes