Основы теории. Одна из стратегий для хранения списка в основной памяти машины, заключается в том, чтобы хранить содержимое списка в едином блоке ячеек памяти сОдна из стратегий для хранения списка в основной памяти машины, заключается в том, чтобы хранить содержимое списка в едином блоке ячеек памяти с последовательными адресами. Такая структура называется непрерывным списком и является типичной для системы хранения, получаемой, когда программист хранит список в виде массива. Непрерывный список прост в применении, однако имеет некоторые существенные недостатки. Предположим, что необходимо удалить одно из имен в списке. Если это имя в настоящий момент расположено близко к началу списка и требуется сохранить в списке тот же порядок, понадобится переместить все имена, находящиеся дальше по списку, вперед, чтобы заполнить пустое место в памяти, образовавшееся после удаления. Более серьезная проблема возникнет, если потребуется добавить имена, поскольку при этом может понадобиться переместить весь список в другое место, так как придется получить новый блок непрерывной памяти, достаточный для размещения расширенного списка. Проблема эффективного управления данными является важнейшей для любой реализации списка. Учитывая недостатки, присущие последовательным спискам необходимо разработать новую структуру списка, которая не основывалась бы на непрерывном порядке сохранения данных. В качестве основы такой структуры может использоваться модель звеньев в цепи.
Длина цепи может увеличиваться без ограничений при добавлении новых звеньев. Более того, новые элементы могут быть вставлены в цепь простым разрывом соединения, добавлением нового звена и восстановлением соединения.
Элементы удаляются из цепи разрывом двух соединений, удалением звена и затем повторным соединением цепи.
Применительно к связанным спискам данная модель будет представлять совокупность связанных узлов. Узел (Node) состоит из поля данных (item) и указателя (next), обозначающего следующий элемент в списке. Указатель — это соединитель, связывающий вместе отдельные узлы списка. Связанный список состоит из множества узлов, первый элемент которого (front), — это узел, на который указывает голова (head). Список связывает узлы вместе от первого до конца или хвоста (rear) списка. Хвост определяется как узел, чье поле указателя имеет значение NULL (0). Списочные приложения проходят по узлам, следуя за каждым указателем на следующий узел. В любой точке сканирования на текущее положение ссылается указатель currPtr. Для списка без узлов head будет содержать значение NULL. На рисунке 1 приведена структура односвязного списка. На нем поле INF - информационное поле, данные, NEXT - указатель на следующий элемент списка. Каждый список должен иметь особый элемент, называемый указателем начала списка или головой списка, который обычно по формату отличен от остальных элементов. В поле указателя последнего элемента списка находится специальный признак nil, свидетельствующий о конце списка.
Рисунок 1 – Структура односвязного списка Однако, обработка односвязного списка не всегда удобна, так как отсутствует возможность продвижения в противоположную сторону. Такую возможность обеспечивает двухсвязный список, каждый элемент которого содержит два указателя: на следующий и предыдущий элементы списка. Структура линейного двухсвязного списка приведена на рисунке 2, где поле NEXT - указатель на следующий элемент, поле PREV - указатель на предыдущий элемент. В крайних элементах соответствующие указатели должны содержать nil, как и показано на рисунке 3:
Рисунок 2 – Структура двусвязного списка Для удобства обработки списка добавляют еще один особый элемент - указатель конца списка. Наличие двух указателей в каждом элементе усложняет список и приводит к дополнительным затратам памяти, но в то же время обеспечивает более эффективное выполнение некоторых операций над списком. Разновидностью рассмотренных видов линейных списков является кольцевой список, который может быть организован на основе как односвязного, так и двухсвязного списков. При этом в односвязном списке указатель последнего элемента должен указывать на первый элемент; в двухсвязном списке в первом и последнем элементах соответствующие указатели переопределяются, как показано на рисунке 3:
Рисунок 3 – Структура кольцевого списка При работе с такими списками несколько упрощаются некоторые процедуры, выполняемые над списком. Однако, при просмотре такого списка следует принять некоторых мер предосторожности, чтобы не попасть в бесконечный цикл. При программировании задач по работе с динамическими структурами данных, и в частности, со связанными списками основное внимание уделяется разбиению на функции и программированию их интерфейсов. Например, логично оформить в виде функции каждую операцию со списком (формирование, поиск, добавление и удаление элемента), поскольку они представляют собой законченные действия. Алгоритмы связанных списков реализуются как независимые функции, чтобы изменения в одной функции не повлияли на поведение другой. Для этого все, что функциям необходимо получить извне, должно передаваться им через параметры. Все параметры, не изменяемые внутри функции, должны передаваться им с модификатором const. Указатели, которые могут измениться (например, при удалении из списка последнего элемента указатель на конец списка требуется скорректировать), передаются по адресу. #include < iostream.h> #include < stdlib.h>
struct Node { int data; Node *link; };
// создание узла (используется функциями Insert) Node *GetNode(int item, Node *nextPtr);
// функциивставкиузла voidInsertFront(Node* & head, int item); voidInsertEnd(Node* & head, int item); voidInsertOrder(Node* & head, int item);
// удаление узла voidDeleteFront(Node* & head); void Delete(Node* & head, int key);
// печать списка voidPrintList(Node *head);
// очистка списка voidClearList(Node* & head);
Для создания связанных списков используется структураNode. Для простоты изложения учебного материала подразумевается, что узлы списка содержат целые данные. Связанный список начинается с указателя узла, который ссылается на начало списка. Такой указатель называется головой, так как он указывает на начало списка. Первоначально значением головы является NULL для указания пустого списка. Node *head = NULL; Связанный список может быть создан различными способами. Наиболее простой способ, это когда каждый новый узел помещается в голову списка.
ПРИМЕР ... intmain() { Node *head = NULL; // объявление и инициализация // головы списка InsertFront(head, 12); // вставка 12 в голову списка InsertFront(head, 8); // вставка 8 в голову списка PrintList(head); // печатает 8 и 12 DeleteFront(head); // удаляет 8 InsertEnd(head, 15); // вставка 15 в конец списка PrintList(head); // печатает 12 и 15 ... Создание узла. Реализуется с помощью функции GetNode, которая принимает начальные данное-значение и указатель и далее динамически создает новый узел. Если выделение памяти происходи неудачно, программа завершается, иначе, функция возвращает указатель на новый узел.
// выделение узла с данным-членомitem и указателем nextPtr Node *GetNode(int item, Node *nextPtr = NULL) { Node *newNode; //выделение памяти при передаче item и NextPtr конструктору // завершение программы, если выделение памяти неудачно newNode = new Node; if (newNode == NULL) { cerr< < " Ошибка выделения памяти! " < < endl; exit(1); } newNode-> data = item; newNode-> link = nextPtr; returnnewNode; } Вставка узла в начало списка. Реализуется с помощью функции InsertFront. Операция вставки узла в начало списка требует обновления значения указателя головы, так как список должен теперь иметь новое начало. Проблема сохранения головы списка является основной для управления списками. Если голова потеряется, то потеряется и список! Перед началом вставки голова определяет начало списка. После вставки новый узел займет положение в начале списка, а предыдущее начало списка займет вторую позицию. Следовательно, полю указателей нового узла присваивается текущее значение головы, а голове присваивается адрес нового узла. Назначение выполняется с использованием GetNode для создания нового узла.
Рисунок 4 – Вставка узла в начало списка
Функция InsertFront принимает текущую голову списка, которая является указателем, определяющим список, а также принимает новое значение данных. Она вставляет значение данных в узел в начале списка. Так как голова будет изменяться этой операцией, она передается как ссылочный параметр.
// вставка элемента в начало списка voidInsertFront(Node* & head, intitem) { // создание нового узла, чтобы он указывал на // первоначальную голову списка, изменение головы списка head = GetNode(item, head); } Прохождение по связанному списку.Функция PrintList реализует прохождение по списку и печать всех данных-значений. Начальной точкой любого алгоритма прохождения является указатель головы, так как он определяет начало списка. При прохождении по списку, используется указатель currPtr для ссылки на текущее положение в списке. Первоначально currPtr устанавливается на начало списка: currPtr = head; Для печати значений каждого узла во время прохождения списка используется оператор cout: cout< < currPtr-> data; В процессе сканирования currPtrнепрерывно перемещаетсяк следующему узлу до тех пор, пока не будетдостигнут конец списка. currPtr = currPtr-> nextNode(); Прохождение по списку завершается, когда currPtr становится равным NULL. Например, функция PrintList печатает значение данных каждого узла. Голова передается в качестве параметра для определения списка.
// печать связанного списка voidPrintList(Node *head) { // currPtr пробегает по списку, начиная с головы Node *currPtr = head; // пока не конец списка, печатать значение данных // текущегоузла while(currPtr! = NULL) { cout< < currPtr-> data< < endl; // перейти к следующему узлу currPtr = currPtr-> link; } } Вставка узла в конец списка. Операция реализуется функцией InsertEnd. Помещение узла в хвост списка требует начального тестирования для определения, пуст ли список. Если да, то узел вставляетсяв начало списка с помощью функции InsertFront. При непустом списке необходимо сканировать узлы для обнаружения хвостового узла (в котором поле link содержит значение NULL). currPtr-> link == NULL;
Рисунок 5 – Вставка узла в конец списка
Затем с помощью функции GetNode создается новый узел newNode и, наконец, он вставляется после текущего объекта. newNode-> link = currPtr-> link; currPtr-> link = newNode; Так как вставка может изменять значение указателя головы, голова передается как ссылочный параметр:
// найти хвост списка и добавить item voidInsertEnd(Node* & head, int item) { Node *newNode, *currPtr = head; // если список пуст, вставить item в начало if (currPtr == NULL) InsertFront(head, item); else { // найти узел с нулевым указателем while(currPtr-> link! = NULL) currPtr = currPtr-> link; // создать узел и вставить в конец списка // (послеcurrPtr) newNode = GetNode(item); newNode-> link = currPtr-> link; currPtr-> link = newNode; } }
Рисунок 6 – Удаление узла в начале списка
Функция DeleteFront, которой передается голова списка как ссылочный параметр, отцепляет от списка первый узел и освобождает его память:
// удалить первый узел списка voidDeleteFront(Node * & head) { // сохранить адрес удаляемого узла Node *p = head; // убедиться в том, что список не пуст if (head! = NULL) { // передвинуть голову к следующему узлу head = head-> link; // удалитьоригинал delete p; } }
Удаление первого элемента, совпадающего с ключом. Общая функция удаления Delete проверяет список и удаляет первый узел, чье значение данных совпадает с ключом. В началеprevPtrустанавливается на NULL, a currPtr — на голову списка. Затем currPtrперемещаетсяпо списку в поисках совпадения с ключом и prevPtrсохраняется так, чтобы он ссылался на предыдущее значение currPtr.
Рисунок 7 – Удаление первого элемента, совпадающего с ключом
Указатели prevPtr и currPtr перемещаются по списку совместно до тех пор, пока currPtr не станет равным NULL или не будет найден ключ (currPtr-> data == key). while (currPtr! = NULL & & currPtr-> data! =key) { // перемещение prevPtr вперед к currPtr prevPtr = currPtr; // перемещение currPtr вперед на один узел currPtr = currPtr-> link; } Совпадение возникает, если происходит выход из оператора while с currPtr! =NULL. Тогда можно удалить текущий узел. Существует две возможности. Если prevPtr — это NULL, удаляется первый узел в списке. Иначе, выполняется отсоединение и удаление узла. if (prevPtr == NULL) head = head-> link; else prevPtr-> link = currPtr-> link; deletecurrPtr;
Если ключ не найден, функция Delete просто завершается. Так как удаление в начале списка приводит к изменению головы, необходимо передавать голову по ссылке.
// удаление первого элемента, совпадающего с ключом void Delete(Node* & head, int key) { Node *currPtr = head, *prevPtr = NULL; // завершить функцию, если список пустой if (currPtr == NULL) return; // прохождение до совпадения с ключей или до конца while (currPtr! = NULL & & currPtr-> data! = key) { prevPtr = currPtr; currPtr = currPtr-> link; } // если currPtr не равно NULL, ключ в currPtr if (currPtr! = NULL) { // prevPtr == NULL означает совпадение в начале списка if(prevPtr == NULL) head = head-> link; else // совпадение во втором или последующем узле // отсоединение этого узла prevPtr-> link = currPtr-> link; // удаление узла deletecurrPtr; } } Упорядоченная вставка. Упорядоченная вставка узлов в список реализуется с помощью функции InsertOrder. Во многих приложениях необходимо поддерживать упорядоченный список данных с узлами, приведенными в возрастающем или убывающем порядке. Для этого алгоритм вставки должен сначала сканировать список для определения правильного положения, в которое будет добавляться новый узел. Последующее обсуждение иллюстрирует процесс создания списка с возрастающим порядком. Для ввода значения данных x сначала сканируется список и устанавливаетсяcurrPtr на первый узел, значение данных которого больше, чем x. Новый узел со значением x должен вставляться непосредственно слева от currPtr. Во время сканирования указатель prevPtr перемещается совместно с currPtr и сохраняет запись предыдущей позиции. Следующий пример иллюстрирует этот алгоритм. Предположим, что список первоначально содержит целые 60, 65, 74 и 82.
Рисунок 8 – Первоначальный состав списка Вставка 50 в список: поскольку 60 является первым узлом в списке, большим, чем 50, мы вставляем 50 в голову списка.
Рисунок 9 – Вставка элемента в голову списка insertFront(head, 50); Вставка 70 в список: 74 — это первый узел в списке, больший, чем 70. Указатели prevPtr и currPtr обозначают узлы 65 и 74, соответственно.
Рисунок 10 – Вставка элемента в середину списка newNode = GetNode(70); newNode-> link = prevPtr-> link; prevPtr-> link = newNode; Вставка 90 в список: Сканируется весь список, но узел, больший, чем 90 не найден (currPtr ==NULL). Новое значение больше, или равно всем другим значениям в списке и, следовательно, новое значение должно быть помещено в хвост списка. Когда сканирование завершается, новый узел вставляется после prevPtr.
Рисунок 11 – Вставка элемента в конец списка
newNode = GetNode(90); newNode-> link = prevPtr-> link; prevPtr-> link = newNode;
Так как вставка в начале списка приводит к изменению головы, то голову следует передавать по ссылке. Для списка из n элементов, оценка эффективности алгоритма в наихудшем случае определяется при вставке нового элемента в конец списка. В этом случае должно быть выполнено n сравнений. В среднем ожидается, что для нахождения места вставки мы просматриваем половину списка. Конечно, в наилучшем случае выполняется одно сравнение.
// вставить item в упорядоченный список voidInsertOrder(Node * & head, int item) { // currPtrпробегаетпосписку Node *currPtr, *prevPtr, *newNode; // prevPtr == NULL указывает на совпадение в начале списка prevPtr = NULL; currPtr = head; // цикл по списку и поиск точки вставки while (currPtr! = NULL) { // точка вставки найдена, если item< текущегоdata if (item < currPtr-> data) break; prevPtr = currPtr; currPtr = currPtr-> link; } // вставка if (prevPtr == NULL) // если prevPtr == NULL, вставлять в начало InsertFront(head, item); else { // вставить новый узел после предыдущего newNode = GetNode(item); newNode-> link = prevPtr-> link; prevPtr-> link = newNode; } }
InsertOrder может использоваться для сортировки элементов, при условии, что оператор сравнения " < " определяется для этого типа данных. Удаление всех узлов. Вызов функции ClearList освобождает память, ассоциированную с каждым узлом в списке. Функция проходит по списку и для каждого узла записывает его адрес, перемещается к следующему узлу и затем удаляет исходный узел. После удаления всех узлов голове списка присваивается значение NULL, следовательно, голову следует передавать по ссылке.
// удаление всех узлов в связанном списке voidClearList(Node * & head) { Node *currPtr, *nextPtr; currPtr = head; while(currPtr! = NULL) { // записать адрес следующего узла nextPtr = currPtr-> link; // удалить текущий узел deletecurrPtr; currPtr = nextPtr; } // пометить как пустой head = NULL; }
|
