Вывод элементов дцс в обратном порядке:
Функция вывода элементов ДЦС в обратном порядке принимает в качестве аргумента указатель на корень списка. Функция перемещает указатель на последний узел списка и осуществляет последовательный обход всех узлов с выводом их значений в обратном порядке. Однако процедура перемещения указателя на последний узел в данном случае намного проще по сравнению с ДЛС, поскольку указатель "предыдущий" корня списка как раз и содержит адрес последнего узла.
void listprintr(list *lst) {
struct list *p;
p = lst;
do {
p = p->prev; // переход к предыдущему узлу
printf("%d ",p->field); // вывод значения элемента p
} while(p != lst); // условие окончания обхода }
Взаимообмен узлов дцс:
В качестве аргументов функция взаимообмена узлов ДЦС принимает два указателя на обмениваемые узлы, а также указатель на корень списка. Функция возвращает адрес корневого узла списка.
Взаимообмен узлов списка осуществляется путем переустановки указателей. Для этого необходимо определить предшествующий и последующий узлы для каждого заменяемого. При этом возможны две ситуации:
заменяемые узлы являются соседями;
заменяемые узлы не являются соседями, то есть между ними имеется хотя бы один узел.
При замене соседних узлов переустановка указателей выглядит следующим образом:
Рисунок 5 - Взаимообмен узлов ДЦС
Функция взаимообмена узлов ДЦС выглядит следующим образом:
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->ptr; // узел следующий за lst1
next2 = lst2->ptr; // узел следующий за 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); }
2.3 Стандартные функции для двусвязного списка
Рассмотрим несколько стандартных функций для двусвязного списка. Функция push добавляет новый элемент в i-ую позицию списка. Функция выполняет следующие действия:
создаёт новый элемент;
копируем значение информационного поля;
если данный элемент является единственным:
оба указателя (next и pred) ссылаются на этот элемент,
указатель first указывает на единственный элемент в списке.
иначе сдвигаем указатель на i-ый элемент и добавляем новый элемент перед i-ым.
Добавим новое значение в двусвязный список (push 4), новый элемент будем добавлять после первого. После операции push список содержит один элемент (Рисунок 6).
Рисунок 6 - После операции push
Добавим ещё несколько значений (push 6 и push 7), каждый новый элемент будем добавлять после первого. Список содержит три элемента (Рисунок 7) в следующей последовательности.
Рисунок 7- Добавление новых значений
Функция pop выталкивает i-ый элемент из списка. Функция выполняет следующие действия:
1)если список пуст, выходим из функции;
2) если в список содержит единственный элемент:
копируем значение информационного поля
удаляем элемент из списка
присваиваем заголовку пусто
3)иначе сдвигаем указатель на i-ый элемент:
если заголовок указывает на i-ый элемент (first==t), тогда перемещаем заголовок на следующий элемент (First=t->next)
копируем значение информационного поля
удаляем i-ый элемент из списка
4) возвращаем значение информационного поля.
Выполнив функцию pop над линейным списком (выталкиваем 3-ий элемент), получим следующее состояние связного списка (Рисунок 8).
Рисунок 8 - Выталкивание элемента.
Функция view пробегает по всем элементам и выводит в консоль значение информационного поля. Просмотр элементов осуществляется слева направо, но легко можно переписать функцию и изменить просмотр элементов справа налево (заменить a=a->next на a=a->pred). Функция clean удаляет все элементы в списке и присваивает заголовку пусто (first=null). После данной операции список возвращается в исходное состояние.