Как сделать двусвязный список c

Как сделать двусвязный список из структуры

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

Двусвязный список

М ы рассмотрели односвязный список и пришли к неутешительным выводам — список разумно использовать в качестве стека, потому что операции вставки в начало списка и удаления из начала списка имеют сложность порядка 1, с дополнительными манёврами можно добиться сложности вставки в конец порядка 1 и определения длины за O(1), но удаление с конца, вставка и поиск элемента остаются O(n).

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

Двусвязный список — это структура данных, которая состоит из узлов, которые хранят полезные данные, указатели на предыдущий узел и следующий узел.

Двусвязный список

Для реализации списка нам понадобится структура узел

typedef struct _Node < void *value; struct _Node *next; struct _Node *prev; >Node;

Указатель prev хранит адрес предыдущего узла, если его нет (значит, это первый узел) то переменная равна NULL. Аналогично, указатель next хранит адрес следующего узла. Структура «Двусвязный Список» будет хранить свой размер (чтобы не пересчитывать количество элементов каждый раз), а также указатель head, ссылающийся на первый элемент, и указатель tail, ссылающийся на последний элемент

typedef struct _DblLinkedList < size_t size; Node *head; Node *tail; >DblLinkedList;

Пустая структура типа DblLinkedList

В случае, когда в списке нет элементов, оба они равны нулю. Если в списке один элемент, то оба указателя ссылаются на один и тот же элемент (соответственное, они равны). Об этом постоянно следует помнить: каждый раз, удаляя или вставляя элемент, придётся проверять, чтобы указатели head и tail правильно хранили адреса.

Структура типа DblLinkedList с одним элементом

Первая функция, как обычно, создаёт экземпляр структуры DblLinkedList

DblLinkedList* createDblLinkedList() < DblLinkedList *tmp = (DblLinkedList*) malloc(sizeof(DblLinkedList)); tmp->size = 0; tmp->head = tmp->tail = NULL; return tmp; >

В ней нет ничего интересного. Заодно опишем функцию, которая удаляет список

void deleteDblLinkedList(DblLinkedList **list) < Node *tmp = (*list)->head; Node *next = NULL; while (tmp) < next = tmp->next; free(tmp); tmp = next; > free(*list); (*list) = NULL; >

Теперь, определим набор стандартных функций – pushFront и popFront для работы с головой, pushBack И popBack для работы с последним элементом, getNth, insert и deleteNth для вставки и удаления в произвольное место.

Вставка нового элемента в начало списка

Вставка спереди очень похожа на вставку в односвязный список. Сначала создаётся новый элемент

Node *tmp = (Node*) malloc(sizeof(Node)); if (tmp == NULL)
Создали новый элемент и задали ему значения

потом задаём ему значения

tmp->value = data; tmp->next = list->head; tmp->prev = NULL;

Создали новый элемент и задали ему значения

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

if (list->head) < list->head->prev = tmp; >

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

if (list->tail == NULL) < list->tail = tmp; >

Теперь перекинем указатель head на вновь созданный элемент и увеличим значение счётчика size

Перекинули указазатель head списка на вновь созданный элемент

list->head = tmp; list->size++;

void pushFront(DblLinkedList *list, void *data) < Node *tmp = (Node*) malloc(sizeof(Node)); if (tmp == NULL) < exit(1); >tmp->value = data; tmp->next = list->head; tmp->prev = NULL; if (list->head) < list->head->prev = tmp; > list->head = tmp; if (list->tail == NULL) < list->tail = tmp; > list->size++; >

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

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

Создали указатель на первый элемент

Node *prev; void *tmp; if (list->head == NULL) < exit(2); >prev = list->head;

После этого перекинем указатель head на следующий за ним элемент

list->head = list->head->next;

Перекидываем указатель head на следующий элемент

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

Создали указатель на первый элемент

void* popFront(DblLinkedList *list) < Node *prev; void *tmp; if (list->head == NULL) < exit(2); >prev = list->head; list->head = list->head->next; if (list->head) < list->head->prev = NULL; > if (prev == list->tail) < list->tail = NULL; > tmp = prev->value; free(prev); list->size--; return tmp; >

Вставка в конец и удаление с конца очень похожи — просто мы переворачиваем список. Соответственное, все prev меняются на next, а head на tail

void pushBack(DblLinkedList *list, void *value) < Node *tmp = (Node*) malloc(sizeof(Node)); if (tmp == NULL) < exit(3); >tmp->value = value; tmp->next = NULL; tmp->prev = list->tail; if (list->tail) < list->tail->next = tmp; > list->tail = tmp; if (list->head == NULL) < list->head = tmp; > list->size++; > void* popBack(DblLinkedList *list) < Node *next; void *tmp; if (list->tail == NULL) < exit(4); >next = list->tail; list->tail = list->tail->prev; if (list->tail) < list->tail->next = NULL; > if (next == list->head) < list->head = NULL; > tmp = next->value; free(next); list->size--; return tmp; >

Получение n-го элемента очень простое и не отличается от оного для односвязного списка.

Node* getNth(DblLinkedList *list, size_t index) < Node *tmp = list->head; size_t i = 0; while (tmp && i < index) < tmp = tmp->next; i++; > return tmp; >

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

Node* getNthq(DblLinkedList *list, size_t index) < Node *tmp = NULL; size_t i; if (index < list->size/2) < i = 0; tmp = list->head; while (tmp && i < index) < tmp = tmp->next; i++; > > else < i = list->size - 1; tmp = list->tail; while (tmp && i > index) < tmp = tmp->prev; i--; > > return tmp; >

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

void insert(DblLinkedList *list, size_t index, void *value) < Node *elm = NULL; Node *ins = NULL; elm = getNth(list, index); if (elm == NULL) < exit(5); >ins = (Node*) malloc(sizeof(Node)); ins->value = value; ins->prev = elm; ins->next = elm->next; if (elm->next) < elm->next->prev = ins; > elm->next = ins; if (!elm->prev) < list->head = elm; > if (!elm->next) < list->tail = elm; > list->size++; > void* deleteNth(DblLinkedList *list, size_t index) < Node *elm = NULL; void *tmp = NULL; elm = getNth(list, index); if (elm == NULL) < exit(5); >if (elm->prev) < elm->prev->next = elm->next; > if (elm->next) < elm->next->prev = elm->prev; > tmp = elm->value; if (!elm->prev) < list->head = elm->next; > if (!elm->next) < list->tail = elm->prev; > free(elm); list->size--; return tmp; >

Не забываем, конечно, смотреть за значениями head И tail, чтобы они указывали на существующие в данный момент элементы.

Добавим пару вспомогательных функций, которые помогут в работе. Первая — это печать списка. Так как тип значения — void*, то необходимо передавать функцию печати одного элемента.

void printDblLinkedList(DblLinkedList *list, void (*fun)(void*)) < Node *tmp = list->head; while (tmp) < fun(tmp->value); tmp = tmp->next; > printf("\n"); >

В примерах будем использовать переменные типа int

void printInt(void *value)

Вторая функция – создание списка из массива

DblLinkedList* fromArray(void *arr, size_t n, size_t size) < DblLinkedList *tmp = NULL; size_t i = 0; if (arr == NULL) < exit(7); >tmp = createDblLinkedList(); while (i < n) < pushBack(tmp, ((char*)arr + i*size)); i++; >return tmp; >

Теперь можно пользоваться двусвязным списком

void main() < DblLinkedList *list = createDblLinkedList(); int a, b, c, d, e, f, g, h; a = 10; b = 20; c = 30; d = 40; e = 50; f = 60; g = 70; h = 80; pushFront(list, &aamp;a); pushFront(list, &b); pushFront(list, &c); pushBack(list, &d); pushBack(list, &e); pushBack(list, &f); printDblLinkedList(list, printInt); printf("length %d\n", list->size); printf("nth 2 %d\n", *((int*)(getNthq(list, 2))->value)); printf("nth 5 %d\n", *((int*)(getNthq(list, 5))->value)); printf("popFront %d\n", *((int*)popFront(list))); printf("popFront %d\n", *((int*)popFront(list))); printf("head %d\n", *((int*)(list->head->value))); printf("tail %d\n", *((int*)(list->tail->value))); printf("popBack %d\n", *((int*)popBack(list))); printf("popBack %d\n", *((int*)popBack(list))); printf("length %d\n", list->size); printDblLinkedList(list, printInt); insert(list, 1, &g); printDblLinkedList(list, printInt); deleteNth(list, 0); printDblLinkedList(list, printInt); deleteDblLinkedList(&list); getch(); >

Сортировка вставками

Р анее мы рассмотрели алгоритм сортировки однонаправленного связного списка методом слияния. Двусвязный список можно сортировать точно также, поэтому сейчас рассмотрим другой алгоритм — сортировку вставками. Суть алгоритма очень простая – создаём новый двунаправленный связный список. Вставляем в него первый элемент неотсортированного списка. Для вставки второго элемента проходим по отсортированному списку и ищем место, куда вставить. Если место не найдено, то вставляем в конец. Очевидно, что если тип данных не известен, то необходимо будет передавать функцию сравнения, с помощью которой можно изменить порядок сортировки.

Для реализации нам понадобится ещё одна функция — вставка до указанного элемента. Эта функция будет получать указатель на список, указатель на узел, перед которым нужно вставить элемент и новые данные.

void insertBeforeElement(DblLinkedList *list, Node* elm, void *value) < Node *ins = NULL; if (elm == NULL) < exit(6); >if (!elm->prev) < pushFront(list, value); return; >ins = (Node*) malloc(sizeof(Node)); ins->value = value; ins->prev = elm->prev; elm->prev->next = ins; ins->next = elm; elm->prev = ins; list->size++; >

Теперь непосредственно сортировка

void insertionSort(DblLinkedList **list, int (*cmp)(void*, void*)) < DblLinkedList *out = createDblLinkedList(); Node *sorted = NULL; Node *unsorted = NULL; pushFront(out, popFront(*list)); unsorted = (*list)->head; while (unsorted) < sorted = out->head; while (sorted && !cmp(unsorted->value, sorted->value)) < sorted = sorted->next; > if (sorted) < insertBeforeElement(out, sorted, unsorted->value); > else < pushBack(out, unsorted->value); > unsorted = unsorted->next; > free(*list); *list = out; >

Видно, что в конце в переданном списке не остаётся элементов, так как мы их выталкиваем, так что старый список мы подменяем на вновь созданный.

Сложность алгоритма – O(n 2 ), мы имеем одни проход по неотсортированному списку сложностью порядка n, для каждого элемента проходим по отсортированному.

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

Тепер сравним сложности различных операций для односвязного и двусвязного списка. Однонаправленный связный список

Сложность операций для односвязного списка.

pushFront	popFront	pushBack	popBack	insert	delete	get	size
O(1)	O(1)	O(1)	O(n)	O(n)	O(n)	O(n)	O(1)

Сложность операций для двусвязного списка.

pushFront	popFront	pushBack	popBack	insert	delete	get	size
O(1)	O(1)	O(1)	O(1)	O(n)	O(n)	O(n)	O(1)

ru-Cyrl 18- tutorial Sypachev S.S. 1989-04-14 sypachev_s_s@mail.ru Stepan Sypachev students

Всё ещё не понятно? – пиши вопросы на ящик

Двусвязный список

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

//узел (звено) списка struct node { //Информационный элемент звена списка int value; // Указатель на предыдущее звено списка node *prev; // Указатель на следующее звено списка node *next; };

Формирование двусвязного списка

Отведем место для указателей в статической памяти и зарезервируем место для динамического объекта.
Присвоим значение переменной ptail, и поместим в информационное поле значение элемента.
Присвоим указателю на предыдущий элемент значение NULL (т. к. элемент первый — предыдущего нет).
Поместим в поле звена адрес еще одного — нового динамического объекта.

В новый добавленный объект записываем значение, в указатель на следующее звено записываем NULL, т. к. объект добавляется в конец.

В указатель на предыдущий элемент записываем адрес предыдущего объекта.
Переменная ptail должна содержать адрес последнего добавленного элемента, т. к. он добавлен в конец.
Двусвязный список из двух элементов готов.
Вставка элемента в двусвязный список.
Выделить память под новый узел.
Записать в новый узел значение.
В указатель на предыдущий узел записать адрес узла, который должен располагаться перед новым узлом.
Записать в указатель на следующий узел адрес узла, который должен быть расположен после нового узла.
В предыдущем узле заменяем значение указателя на следующий узел на адрес нового узла.
В следующем узле заменяем значение указателя на предыдущий узел на адрес нового узла.

На рисунке изображен двусвязный циклический список:

Удаление элемента из двусвязного списка

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

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

Удалить узел, предназначенный для удаления.

Такое построение позволяет производить движение по списку, как в прямом, так и в обратном направлении.

Реализация двусвязного списка

#include using namespace std; struct Elem { int data; // данные Elem * next, * prev; }; class List { // Голова, хвост Elem * Head, * Tail; // Количество элементов int Count; public: // Конструктор List(); // Конструктор копирования List(const List&); // Деструктор ~List(); // Получить количество int GetCount(); // Получить элемент списка Elem* GetElem(int); // Удалить весь список void DelAll(); // Удаление элемента, если параметр не указывается, // то функция его запрашивает void Del(int pos = 0); // Вставка элемента, если параметр не указывается, // то функция его запрашивает void Insert(int pos = 0); // Добавление в конец списка void AddTail(int n); // Добавление в начало списка void AddHead(int n); // Печать списка void Print(); // Печать определенного элемента void Print(int pos); List& operator = (const List&); // сложение двух списков (дописывание) List operator + (const List&); // сравнение по элементам bool operator == (const List&); bool operator != (const List&); bool operator  (const List&); bool operator >= (const List&); bool operator  (const List&); bool operator > (const List&); // переворачивание списка List operator - (); }; List::List() { // Изначально список пуст Head = Tail = NULL; Count = 0; } List::List(const List & L) { Head = Tail = NULL; Count = 0; // Голова списка, из которого копируем Elem * temp = L.Head; // Пока не конец списка while(temp != 0) { // Передираем данные AddTail(temp->data); temp = temp->next; } } List::~List() { // Удаляем все элементы DelAll(); } void List::AddHead(int n) { // новый элемент Elem * temp = new Elem; // Предыдущего нет temp->prev = 0; // Заполняем данные temp->data = n; // Следующий - бывшая голова temp->next = Head; // Если элементы есть? if(Head != 0) Head->prev = temp; // Если элемент первый, то он одновременно и голова и хвост if(Count == 0) Head = Tail = temp; else // иначе новый элемент - головной Head = temp; Count++; } void List::AddTail(int n) { // Создаем новый элемент Elem * temp = new Elem; // Следующего нет temp->next = 0; // Заполняем данные temp->data = n; // Предыдущий - бывший хвост temp->prev = Tail; // Если элементы есть? if(Tail != 0) Tail->next = temp; // Если элемент первый, то он одновременно и голова и хвост if(Count == 0) Head = Tail = temp; else // иначе новый элемент - хвостовой Tail = temp; Count++; } void List::Insert(int pos) { // если параметр отсутствует или равен 0, то запрашиваем его if(pos == 0) { cout  <"Input position: "; cin >> pos; } // Позиция от 1 до Count? if(pos  1 || pos > Count + 1) { // Неверная позиция cout  <"Incorrect position . \n"; return; } // Если вставка в конец списка if(pos == Count + 1) { // Вставляемые данные int data; cout  <"Input new number: "; cin >> data; // Добавление в конец списка AddTail(data); return; } else if(pos == 1) { // Вставляемые данные int data; cout  <"Input new number: "; cin >> data; // Добавление в начало списка AddHead(data); return; } // Счетчик int i = 1; // Отсчитываем от головы n - 1 элементов Elem * Ins = Head; while(i  pos) { // Доходим до элемента, // перед которым вставляемся Ins = Ins->next; i++; } // Доходим до элемента, // который предшествует Elem * PrevIns = Ins->prev; // Создаем новый элемент Elem * temp = new Elem; // Вводим данные cout  <"Input new number: "; cin >> temp->data; // настройка связей if(PrevIns != 0 && Count != 1) PrevIns->next = temp; temp->next = Ins; temp->prev = PrevIns; Ins->prev = temp; Count++; } void List::Del(int pos) { // если параметр отсутствует или равен 0, то запрашиваем его if(pos == 0) { cout  <"Input position: "; cin >> pos; } // Позиция от 1 до Count? if(pos  1 || pos > Count) { // Неверная позиция cout  <"Incorrect position . \n"; return; } // Счетчик int i = 1; Elem * Del = Head; while(i  pos) { // Доходим до элемента, // который удаляется Del = Del->next; i++; } // Доходим до элемента, // который предшествует удаляемому Elem * PrevDel = Del->prev; // Доходим до элемента, который следует за удаляемым Elem * AfterDel = Del->next; // Если удаляем не голову if(PrevDel != 0 && Count != 1) PrevDel->next = AfterDel; // Если удаляем не хвост if(AfterDel != 0 && Count != 1) AfterDel->prev = PrevDel; // Удаляются крайние? if(pos == 1) Head = AfterDel; if(pos == Count) Tail = PrevDel; // Удаление элемента delete Del; Count--; } void List::Print(int pos)  // Позиция от 1 до Count? if(pos  1  Elem * temp; // Определяем с какой стороны // быстрее двигаться if(pos  Count / 2) { // Отсчет с головы temp = Head; int i = 1; while(i  pos) { // Двигаемся до нужного элемента temp = temp->next; i++; } } else { // Отсчет с хвоста temp = Tail; int i = 1; while(i  Count - pos) { // Двигаемся до нужного элемента temp = temp->prev; i++; } } // Вывод элемента cout   <" element: "; cout  ->data  ; } void List::Print() { // Если в списке присутствуют элементы, то пробегаем по нему // и печатаем элементы, начиная с головного if(Count != 0) { Elem * temp = Head; cout  <"( "; while(temp->next != 0) { cout  ->data  <", "; temp = temp->next; } cout  ->data  <" )\n"; } } void List::DelAll() { // Пока остаются элементы, удаляем по одному с головы while(Count != 0) Del(1); } int List::GetCount() { return Count; } Elem * List::GetElem(int pos)  int i = 1; // Ищем нужный нам элемент while(i  pos && temp != 0) { temp = temp->next; i++; } if(temp == 0) return 0; else return temp; } List & List::operator = (const List & L) { // Проверка присваивания элемента "самому себе" if(this == &L) return *this; // удаление старого списка this->~List(); // DelAll(); Elem * temp = L.Head; // Копируем элементы while(temp != 0) { AddTail(temp->data); temp = temp->next; } return *this; } // сложение двух списков List List::operator + (const List& L) { // Заносим во временный список элементы первого списка List Result(*this); // List Result = *this; Elem * temp = L.Head; // Добавляем во временный список элементы второго списка while(temp != 0) { Result.AddTail(temp->data); temp = temp->next; } return Result; } bool List::operator == (const List& L) { // Сравнение по количеству if(Count != L.Count) return false; Elem *t1, *t2; t1 = Head; t2 = L.Head; // Сравнение по содержанию while(t1 != 0) { // Сверяем данные, которые // находятся на одинаковых позициях if(t1->data != t2->data) return false; t1 = t1->next; t2 = t2->next; } return true; } bool List::operator != (const List& L) { // Используем предыдущую функцию сравнения return !(*this == L); } bool List::operator >= (const List& L) { // Сравнение по количеству if(Count > L.Count) return true; // Сравнение по содержанию if(*this == L) return true; return false; } bool List::operator  (const List& L) { // Сравнение по количеству if(Count  L.Count) return true; // Сравнение по содержанию if(*this == L) return true; return false; } bool List::operator > (const List& L) { if(Count > L.Count) return true; return false; } bool List::operator  (const List& L) { if(Count  L.Count) return true; return false; } // переворот List List::operator - () { List Result; Elem * temp = Head; // Копируем элементы списка, начиная с головного, // в свой путем добавления элементов в голову, // таким образом временный список Result будет содержать // элементы в обратном порядке while(temp != 0) { Result.AddHead(temp->data); temp = temp->next; } return Result; } // Тестовый пример void main() { List L; const int n = 10; int a[n] = {0,1,2,3,4,5,6,7,8,9}; // Добавляем элементы, стоящие на четных индексах, в голову, // на нечетных - в хвост for(int i = 0; i  n; i++) if(i % 2 == 0) L.AddHead(a[i]); else L.AddTail(a[i]); // Распечатка списка cout  <"List L:\n"; L.Print(); cout  ; // Вставка элемента в список L.Insert(); // Распечатка списка cout  <"List L:\n"; L.Print(); // Распечатка 2-го и 8-го элементов списка L.Print(2); L.Print(8); List T; // Копируем список T = L; // Распечатка копии cout  <"List T:\n"; T.Print(); // Складываем два списка (первый в перевернутом состоянии) cout  <"List Sum:\n"; List Sum = -L + T; // Распечатка списка Sum.Print(); }

Курсы для изучения C++

Язык С и его производные один из самых востребованных и высокооплачиваемых языков программирования.

C++ Developer. Professional Разработчик С++ (Углубленный уровень) Пройти тестирование на знание языка С++.

Двусвязный циклический список

Каждый узел двунаправленного (двусвязного) циклического списка (ДЦС) содержит два поля указателей — на следующий и на предыдущий узлы. Указатель на предыдущий узел корня списка содержит адрес последнего узла. Указатель на следующий узел последнего узла содержит адрес корня списка.

Узел ДЦС можно представить в виде структуры, аналогичной ДЛС:

struct list
int field; // поле данных
struct list *next; // указатель на следующий элемент
struct list *prev; // указатель на предыдущий элемент
>;

Основные действия, производимые над узлами ДЦС:

• Инициализация списка
• Добавление узла в список
• Удаление узла из списка
• Вывод элементов списка
• Вывод элементов списка в обратном порядке
• Взаимообмен двух узлов списка

Инициализация ДЦС

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

1
2
3
4
5
6
7
8
9
10

struct list * init( int a) // а- значение первого узла
struct list *lst;
// выделение памяти под корень списка
lst = ( struct list*)malloc( sizeof ( struct list));
lst->field = a;
lst->next = lst; // указатель на следующий узел
lst->prev = lst; // указатель на предыдущий узел
return (lst);
>

Добавление узла в ДЦС

Функция добавления узла в ДЦС аналогична функции для ДЛС и принимает два аргумента:

• Указатель на узел, после которого происходит добавление
• Данные для добавляемого узла.

Процедуру добавления узла можно отобразить следующей схемой:

Добавление узла в ДЦС включает в себя следующие этапы:

• создание узла добавляемого элемента и заполнение его поля данных;
• переустановка указателя «следующий» узла, предшествующего добавляемому, на добавляемый узел;
• переустановка указателя «предыдущий» узла, следующего за добавляемым, на добавляемый узел;
• установка указателя «следующий» добавляемого узла на следующий узел (тот, на который указывал предшествующий узел);
• установка указателя «предыдущий» добавляемого узла на узел, предшествующий добавляемому (узел, переданный в функцию).

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

Таким образом, функция добавления узла в ДЦС имеет вид:

1
2
3
4
5
6
7
8
9
10
11
12

struct list * addelem(list *lst, int number)
struct list *temp, *p;
temp = ( struct list*)malloc( sizeof (list));
p = lst->next; // сохранение указателя на следующий узел
lst->next = temp; // предыдущий узел указывает на создаваемый
temp->field = number; // сохранение поля данных добавляемого узла
temp->next = p; // созданный узел указывает на следующий узел
temp->prev = lst; // созданный узел указывает на предыдущий узел
p->prev = temp;
return (temp);
>

Возвращаемым значением функции является адрес добавленного узла.

Удаление узла ДЦС

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

Функция возвращает указатель на узел, следующий за удаляемым.

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

Удаление узла ДЦС включает в себя следующие этапы:

• установка указателя «следующий» предыдущего узла на узел, следующий за удаляемым;
• установка указателя «предыдущий» следующего узла на узел, предшествующий удаляемому;
• освобождение памяти удаляемого узла.

1
2
3
4
5
6
7
8
9
10

struct list * deletelem(list *lst)
struct list *prev, *next;
prev = lst->prev; // узел, предшествующий lst
next = lst->next; // узел, следующий за lst
prev->next = lst->next; // переставляем указатель
next->prev = lst->prev; // переставляем указатель
free(lst); // освобождаем память удаляемого элемента
return (prev);
>

Вывод элементов ДЦС

Функция вывода элементов ДЦС аналогична функции для ОЦС.
В качестве аргумента в функцию вывода элементов передается указатель на корень списка.
Функция осуществляет последовательный обход всех узлов с выводом их значений.

void listprint(list *lst)
struct list *p;
p = lst;
do printf( «%d » , p->field); // вывод значения элемента p
p = p->next; // переход к следующему узлу
> while (p != lst); // условие окончания обхода
>

Для ДЦС также можно вызвать функцию вывода элементов списка в обратном порядке.

Вывод элементов ДЦС в обратном порядке

Функция вывода элементов ДЦС в обратном порядке принимает в качестве аргумента указатель на корень списка. Функция перемещает указатель на последний узел списка и осуществляет последовательный обход всех узлов с выводом их значений в обратном порядке. Однако процедура перемещения указателя на последний узел в данном случае намного проще по сравнению с ДЛС, поскольку указатель «предыдущий» корня списка как раз и содержит адрес последнего узла.

void listprintr(list *lst)
struct list *p;
p = lst;
do p = p->prev; // переход к предыдущему узлу
printf( «%d » , p->field); // вывод значения элемента p
> while (p != lst); // условие окончания обхода
>

Взаимообмен узлов ДЦС

В качестве аргументов функция взаимообмена узлов ДЦС принимает два указателя на обмениваемые узлы, а также указатель на корень списка. Функция возвращает адрес корневого узла списка.

Взаимообмен узлов списка осуществляется путем переустановки указателей. Для этого необходимо определить предшествующий и последующий узлы для каждого заменяемого. При этом возможны две ситуации:

• заменяемые узлы являются соседями;
• заменяемые узлы не являются соседями, то есть между ними имеется хотя бы один узел.

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

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

Функция взаимообмена узлов ДЦС выглядит следующим образом:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

struct list * swap( struct list *lst1, struct list *lst2, struct list *head)
// Возвращает новый корень списка
struct list *prev1, *prev2, *next1, *next2;
prev1 = lst1->prev; // узел предшествующий lst1
prev2 = lst2->prev; // узел предшествующий lst2
next1 = lst1->next; // узел следующий за lst1
next2 = lst2->next; // узел следующий за lst2
if (lst2 == next1) // обмениваются соседние узлы
lst2->next = lst1;
lst2->prev = prev1;
lst1->next = next2;
lst1->prev = lst2;
next2->prev = lst1;
prev1->next = lst2;
>
else if (lst1 == next2) // обмениваются соседние узлы
lst1->next = lst2;
lst1->prev = prev2;
lst2->next = next1;
lst2->prev = lst1;
next1->prev = lst2;
prev2->next = lst1;
>
else // обмениваются отстоящие узлы
prev1->next = lst2;
lst2->next = next1;
prev2->next = lst1;
lst1->next = next2;
lst2->prev = prev1;
next2->prev = lst1;
lst1->prev = prev2;
next1->prev = lst2;
>
if (lst1 == head)
return (lst2);
if (lst2 == head)
return (lst1);
return (head);
>