М ы рассмотрели односвязный список и пришли к неутешительным выводам — список разумно использовать в качестве стека, потому что операции вставки в начало списка и удаления из начала списка имеют сложность порядка 1, с дополнительными манёврами можно добиться сложности вставки в конец порядка 1 и определения длины за O(1), но удаление с конца, вставка и поиск элемента остаются O(n).
Каким образом можно упростить удаление последнего элемента? Очевидно, что если бы мы хранили указатель на предыдущий элемент, то было бы возможно удалять последний.
Двусвязный список — это структура данных, которая состоит из узлов, которые хранят полезные данные, указатели на предыдущий узел и следующий узел.
Двусвязный список
Для реализации списка нам понадобится структура узел
typedef struct _Node < void *value; struct _Node *next; struct _Node *prev; >Node;
Указатель prev хранит адрес предыдущего узла, если его нет (значит, это первый узел) то переменная равна NULL. Аналогично, указатель next хранит адрес следующего узла. Структура «Двусвязный Список» будет хранить свой размер (чтобы не пересчитывать количество элементов каждый раз), а также указатель head, ссылающийся на первый элемент, и указатель tail, ссылающийся на последний элемент
Дербышева Т.Н. Лекция 13-2-all. Двусвязный список, циклический с барьерным элементом. API.
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 должен ссылаться на вновь созданный элемент
Двусвязный список | Динамические структуры данных #2
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, pushFront(list, pushBack(list, pushBack(list, pushBack(list, printDblLinkedList(list, printInt); printf(«length %dn», list->size); printf(«nth 2 %dn», *((int*)(getNthq(list, 2))->value)); printf(«nth 5 %dn», *((int*)(getNthq(list, 5))->value)); printf(«popFront %dn», *((int*)popFront(list))); printf(«popFront %dn», *((int*)popFront(list))); printf(«head %dn», *((int*)(list->head->value))); printf(«tail %dn», *((int*)(list->tail->value))); printf(«popBack %dn», *((int*)popBack(list))); printf(«popBack %dn», *((int*)popBack(list))); printf(«length %dn», list->size); printDblLinkedList(list, printInt); insert(list, 1, printDblLinkedList(list, printInt); deleteNth(list, 0); printDblLinkedList(list, printInt); deleteDblLinkedList( 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, для каждого элемента проходим по отсортированному.
Так как при каждом создании нового узла мы удаляем узел из первого списка, то дополнительной памяти не требуется.
Тепер сравним сложности различных операций для односвязного и двусвязного списка. Однонаправленный связный список
| O(1) | O(1) | O(1) | O(n) | O(n) | O(n) | O(n) | O(1) |
| O(1) | O(1) | O(1) | O(1) | O(n) | O(n) | O(n) | O(1) |
Всё ещё не понятно? – пиши вопросы на ящик
Источник: learnc.info
Русские Блоги
Базовая работа и реализация двусвязного списка на языке Си
Базовая работа и реализация двусвязного списка на языке Си
задний план
Существует только один указатель на преемника узла односвязного списка, так что по односвязному списку можно пройти только назад последовательно от первого узла. Чтобы получить доступ к узлу-предшественнику узла (при операциях вставки или удаления), вы можете пройти только с самого начала. Сложность времени доступа к последующим узлам составляет 0 (1), а сложность времени доступа к узлу-предшественнику составляет O (n ).
Чтобы преодолеть вышеупомянутые недостатки односвязных списков, вводится двусвязный список.Существуют два указателя спереди и сзади в узле двусвязного списка, которые указывают на его предшествующий узел и узел-последователь соответственно.
Состав
typedef struct SqNode < int data; struct SqNode * fron; // Указываем на узел-предшественник struct SqNode * tail; // Указываем на узел заднего привода >SqNode,*SqList;
Базовая операция двусвязного списка
инициализация
SqList InitList(SqList L) < /* Параметры: первый адрес двусвязного списка Функциональная функция: инициализировать двусвязный список, сделать указатель головы и указатель хвоста равными нулю, В случае инициализации вернуть «пусто», в случае успешной инициализации вернуть первый адрес связанного списка */ L = (SqList)malloc(sizeof(SqNode)); if (!L) < return NULL; >L->fron = NULL; L->tail = NULL; return L; >
Создание (метод вставки хвоста)
SqList TailCreateList(SqList L) < /* Параметры: первый адрес связанного списка Функция: Метод интерполяции хвоста для создания двусвязного списка */ SqList s; SqList r; r = L; int Value = 0; printf («Введите связанный список, который необходимо создать, введите 999, чтобы завершить создание: n»); scanf_s(«%d», getchar(); while (Value!=999) < s = (SqList) malloc (sizeof (SqNode)); // Создаем узел каждый раз, если создание не удается, вернуть нулевое значение if (!s) return NULL; s->data = Value; s->tail = r->tail; s->fron = r; r->tail = s; r = s; scanf_s(«%d», getchar(); > return L; >
Обойти все узлы
void PrintfList(SqList L) < /* Функция Функция: пройти все узлы и распечатать их */ SqList s; s = L->tail; while (s != NULL) < printf(«%dt», s->data); s = s->tail; > >
Вставить узел в указанную позицию
SqList InsertElement(SqList L, int Locate) < int Lenngth = LengthList(L); if (Locate >Lenngth + 1 || Locate < 0) return NULL; int Value=’ ’; SqList s; int i=0; SqList r; r = L; printf («Пожалуйста, введите данные узла:»); scanf_s(«%d», s = (SqList)malloc(sizeof(SqNode)); if(s==NULL) return NULL; while (r->tail!=NULL itail; i++; > printf(«%d», r->data); s->data = Value; if (Locate < Lenngth) < s->tail = r->tail; s->fron = r; r->tail->fron = s; r->tail = s; > else < s->tail = r->tail; s->fron = r; r->tail = s; > return L; >
Получить длину двусвязного списка
int LengthList(SqList L) < /* Параметры: первый адрес связанного списка Функция: получить длину связанного списка */ SqList s; s = L;; int i = 0; while (s->tail!=NULL) < i++; s = s->tail; > return i; >
Удалить узел в указанном месте
SqList DeleteElement(SqList L, int Locate) < /* Первый параметр: первый адрес связанного списка Второй параметр: позиция удаленного элемента.
Функция функция: удалить узел в соответствии с указанной позицией и вернуть удаленный узел */ int Length = 0; Length = LengthList(L); if (Locate >Length || Locate<0) return NULL; SqList s=NULL; SqList r=NULL; int i=1; s = L->tail; while (i < Locate s != NULL) < i++; s = s->tail; > r = s; if (Locate < Length) < s->fron->tail = s->tail; s->tail->fron = s->fron; > if (Locate == Length) < s->fron->tail = s->tail; s->fron = NULL; > return r; >
Полный код
Файловая структура
Файл с двойной связью .h
#pragma once #ifndef __Двухсвязный список__H__ #define __Двухсвязный список__H__ typedef struct SqNode < int data; struct SqNode *fron; struct SqNode *tail; >SqNode,*SqList; SqList InitList (SqList L); // Инициализировать двусвязный список SqList TailCreateList (SqList L); // Создаем двусвязный список (метод вставки хвоста) void PrintfList (SqList L); // Распечатать связанный список SqList InsertElement (SqList L, int Locate); // Вставляем узел в указанную позицию int LengthList (SqList L); // Получить длину связанного списка SqList DeleteElement (SqList L, int Locate); // Удаляем указанный элемент позиции #endif // __Двухсвязный список__H__
Файл с двойной связью списка .c
#include #include «Двойной связанный список.h» SqList InitList(SqList L) < /* Параметры: первый адрес двусвязного списка Функциональная функция: инициализировать двусвязный список, сделать указатель головы и указатель хвоста равными нулю, При инициализации вернуть «пусто», если инициализация прошла успешно, вернуть первый адрес связанного списка */ L = (SqList)malloc(sizeof(SqNode)); if (!L) < return NULL; >L->fron = NULL; L->tail = NULL; return L; > // Инициализируем двусвязный список SqList TailCreateList(SqList L) < /* Параметры: первый адрес связанного списка Функция: Метод интерполяции хвоста для создания двусвязного списка */ SqList s; SqList r; r = L; int Value = 0; printf («Введите связанный список, который необходимо создать, введите 999, чтобы завершить создание: n»); scanf_s(«%d», getchar(); while (Value!=999) < s = (SqList) malloc (sizeof (SqNode)); // Создаем узел каждый раз, если создание не удается, вернуть нулевое значение if (!s) return NULL; s->data = Value; s->tail = r->tail; s->fron = r; r->tail = s; r = s; scanf_s(«%d», getchar(); > return L; > // Создаем двусвязный список (метод вставки заголовка) void PrintfList(SqList L) < /* Функция функция */ SqList s; s = L->tail; while (s != NULL) < printf(«%dt», s->data); s = s->tail; > printf(«n»); > // Распечатать связанный список SqList InsertElement(SqList L, int Locate) < int Lenngth = LengthList(L); if (Locate >Lenngth + 1 || Locate < 0) return NULL; int Value=’ ’; SqList s; int i=0; SqList r; r = L; printf («Пожалуйста, введите данные узла:»); scanf_s(«%d», s = (SqList)malloc(sizeof(SqNode)); if(s==NULL) return NULL; while (r->tail!=NULL itail; i++; > printf(«%d», r->data); s->data = Value; if (Locate < Lenngth) < s->tail = r->tail; s->fron = r; r->tail->fron = s; r->tail = s; > else < s->tail = r->tail; s->fron = r; r->tail = s; > return L; > // Вставляем узел в указанную позицию int LengthList(SqList L) < SqList s; s = L;; int i = 0; while (s->tail!=NULL) < i++; s = s->tail; > return i; > // Получаем длину связанного списка SqList DeleteElement(SqList L, int Locate) < /* Первый параметр: первый адрес связанного списка Второй параметр: позиция удаленного элемента. Функция функция: удалить узел в соответствии с указанной позицией и вернуть удаленный узел */ int Length = 0; Length = LengthList(L); if (Locate >Length || Locate<0) return NULL; SqList s=NULL; SqList r=NULL; int i=1; s = L->tail; while (i < Locate s != NULL) < i++; s = s->tail; > r = s; if (Locate < Length) < s->fron->tail = s->tail; s->tail->fron = s->fron; > if (Locate == Length) < s->fron->tail = s->tail; s->fron = NULL; > return r; > // Удаляем указанный элемент позиции
Основная функция .c файл
#include «Двойной связанный список.h» #include int main() < SqList L=NULL; < L = InitList(L); if (L == NULL) < printf («Ошибка двусторонней инициализации n»); return; >printf («Инициализация прошла успешно n»); > // Инициализация двусвязного списка < SqList s; s = TailCreateList(L); if (s == NULL) printf («Не удалось подать заявку на пространство, создание окончено n»); else < L = s; >> // Создаем связанный список (метод вставки заголовка) < printf («Пожалуйста, введите позицию, в которую вы хотите вставить узел: n»); int Locate = ‘ ’; SqList s; scanf_s(«%d», getchar(); s = InsertElement(L, Locate); if (s == NULL) printf («Длина вставленного узла превышает длину связанного списка, вставка не удалась n»); else < L = s; >PrintfList(L); > // Вставляем узел < SqList p; int Locate = ‘ ’; printf («Пожалуйста, введите место, где вы хотите удалить узел:»); scanf_s(«%d», getchar(); p=DeleteElement(L,Locate); printf («Удаленный вами узел:% d n», p->data); free(p); printf («Удалить связанный список узлов n»); PrintfList(L); > // Удаляем узел < PrintfList(L); >// Распечатать связанный список < printf («Длина связанного списка:% d n», LengthList (L)); >// Получаем длину связанного списка >
надеюсь, что это поможет нам
Источник: russianblogs.com
Двусвязный линейный список
Каждый узел двунаправленного (двусвязного) линейного списка (ДЛС) содержит два поля указателей — на следующий и на предыдущий узлы. Указатель на предыдущий узел корня списка содержит нулевое значение. Указатель на следующий узел последнего узла также содержит нулевое значение.
Узел ДЛС можно представить в виде структуры:
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 = NULL ; // указатель на следующий узел
lst->prev = NULL ; // указатель на предыдущий узел
return (lst);
>
Добавление узла в ДЛС
Функция добавления узла в список принимает два аргумента:
- Указатель на узел, после которого происходит добавление
- Данные для добавляемого узла.
Процедуру добавления узла можно отобразить следующей схемой:
Добавление узла в ДЛС включает в себя следующие этапы:
- создание узла добавляемого элемента и заполнение его поля данных;
- переустановка указателя «следующий» узла, предшествующего добавляемому, на добавляемый узел;
- переустановка указателя «предыдущий» узла, следующего за добавляемым, на добавляемый узел;
- установка указателя «следующий» добавляемого узла на следующий узел (тот, на который указывал предшествующий узел);
- установка указателя «предыдущий» добавляемого узла на узел, предшествующий добавляемому (узел, переданный в функцию).
Таким образом, функция добавления узла в ДЛС имеет вид:
1
2
3
4
5
6
7
8
9
10
11
12
13
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; // созданный узел указывает на предыдущий узел
if (p != NULL )
p->prev = temp;
return (temp);
>
Возвращаемым значением функции является адрес добавленного узла.
Удаление узла ДЛС
В качестве аргументов функции удаления узла ДЛС передается указатель на удаляемый узел. Поскольку узел списка имеет поле указателя на предыдущий узел, нет необходимости передавать указатель на корень списка.
Функция возвращает указатель на узел, следующий за удаляемым.
Удаление узла может быть представлено следующей схемой:
Удаление узла ДЛС включает в себя следующие этапы:
- установка указателя «следующий» предыдущего узла на узел, следующий за удаляемым;
- установка указателя «предыдущий» следующего узла на узел, предшествующий удаляемому;
- освобождение памяти удаляемого узла.
1
2
3
4
5
6
7
8
9
10
11
12
struct list * deletelem(list *lst)
struct list *prev, *next;
prev = lst->prev; // узел, предшествующий lst
next = lst->next; // узел, следующий за lst
if (prev != NULL )
prev->next = lst->next; // переставляем указатель
if (next != NULL )
next->prev = lst->prev; // переставляем указатель
free(lst); // освобождаем память удаляемого элемента
return (prev);
>
Удаление корня ДЛС
Функция удаления корня ДЛС в качестве аргумента получает указатель на текущий корень списка. Возвращаемым значением будет новый корень списка — тот узел, на который указывает удаляемый корень.
struct list * deletehead(list *root)
struct list *temp;
temp = root->next;
temp->prev = NULL ;
free(root); // освобождение памяти текущего корня
return (temp); // новый корень списка
>
Вывод элементов ДЛС
Функция вывода элементов ДЛС аналогична функции для ОЛС.
В качестве аргумента в функцию вывода элементов передается указатель на корень списка.
Функция осуществляет последовательный обход всех узлов с выводом их значений.
void listprint(list *lst)
struct list *p;
p = lst;
do printf( «%d » , p->field); // вывод значения элемента p
p = p->next; // переход к следующему узлу
> while (p != NULL ); // условие окончания обхода
>
Для ДЛС также можно вызвать функцию вывода элементов списка в обратном порядке.
Вывод элементов ДЛС в обратном порядке
Функция вывода элементов ДЛС в обратном порядке принимает в качестве аргумента указатель на корень списка. Функция перемещает указатель на последний узел списка и осуществляет последовательный обход всех узлов с выводом их значений в обратном порядке.
1
2
3
4
5
6
7
8
9
10
11
void listprintr(list *lst)
struct list *p;
p = lst;
while (p->next != NULL )
p = p->next; // переход к концу списка
do printf( «%d » , p->field); // вывод значения элемента p
p = p->prev; // переход к предыдущему узлу
> while (p != NULL ); // условие окончания обхода
>
Взаимообмен узлов ДЛС
В качестве аргументов функция взаимообмена узлов ДЛС принимает два указателя на обмениваемые узлы, а также указатель на корень списка. Функция возвращает адрес корневого узла списка.
Взаимообмен узлов списка осуществляется путем переустановки указателей. Для этого необходимо определить предшествующий и последующий узлы для каждого заменяемого. При этом возможны две ситуации:
- заменяемые узлы являются соседями;
- заменяемые узлы не являются соседями, то есть между ними имеется хотя бы один узел.
При замене соседних узлов переустановка указателей выглядит следующим образом: 
При замене узлов, не являющихся соседними переустановка указателей выглядит следующим образом: 
Функция взаимообмена узлов списка выглядит следующим образом:
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
44
45
46
47
48
49
50
51
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;
if (next2 != NULL )
next2->prev = lst1;
if (lst1 != head)
prev1->next = lst2;
>
else if (lst1 == next2) // обмениваются соседние узлы
lst1->next = lst2;
lst1->prev = prev2;
lst2->next = next1;
lst2->prev = lst1;
if (next1 != NULL )
next1->prev = lst2;
if (lst2 != head)
prev2->next = lst1;
>
else // обмениваются отстоящие узлы
if (lst1 != head) // указатель prev можно установить только для элемента,
prev1->next = lst2; // не являющегося корневым
lst2->next = next1;
if (lst2 != head)
prev2->next = lst1;
lst1->next = next2;
lst2->prev = prev1;
if (next2 != NULL ) // указатель next можно установить только для элемента,
next2->prev = lst1; // не являющегося последним
lst1->prev = prev2;
if (next1 != NULL )
next1->prev = lst2;
>
if (lst1 == head)
return (lst2);
if (lst2 == head)
return (lst1);
return (head);
>
Комментариев к записи: 30
Источник: prog-cpp.ru