Определение двунаправленного списка

 

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

Пример 1:

Рис.1. строка символов BETA представлена двусвязным списком

 

Первое звено не имеет ссылки на предыдущее, последнее звено не имеет ссылки на следующее звено (см. рис.2.).

Рис.2. строка символов BETA представлена циклическим списком

 

Такой список (см. рис.2.) называют кольцевым (циклическим). Здесь первое звено имеет ссылку на последнее, а последнее звено на первое. Поэтому начинать обработку такого списка можно как с первого звена, так и с последнего. Двусвязный список может иметь заглавное звено (см. рис.3.).

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

 

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

Возможны и другие структуры двусвязных списков.

Задание двусвязного списка:

struct list2

{ type elem;

list2 * next, * pred; }

list2 * headlist2;

Здесь type – тип информационного поля элемента списка. Переменная-указатель headlist2 задает список как единый программный объект, ее значение - указатель на первый (или заглавный) элемент списка (см. рис.3.).

Пример 2. Формирование двунаправленного кольцевого списка

void main ()

struct list2

{ char elem;

list2 * next, * pred; }

list2 *l, *r, *x;

char sym;

{ l = new list2;       // Создание пустого

l -> next = l;          // кольцевого списка

l -> pred = l;          // с заглавным звеном

r = l;

while ((sym = getchar ())!= ‘\n’)

{ x = new list2;

x -> elem = sym;      // Создание очередного звена

x -> next = r -> next;  // Поле next - указатель на следующее звено

//получило значение указателя на первое звено списка

x -> pred = r;                    //Поле pred - указатель на предыдущее звено получило

// значение указателя на текущее последнее звено списка

 r -> next = x;         // Поле next текущего последнего элемента - указатель на

//следующий элемент получило значение указателя на новый

//элемент, таким образом, новое звено добавлено в конец

//списка

r -> next -> pred = x; // Поле pred заглавного элемента - указатель

// на последнее звено списка получило значение указателя

// на добавленный в конец списка элемент, таким образом,

// сформирован кольцевой список

r = r -> next;

// Текущий указатель получил значение ссылки на

// новый последний элемент списка

}

}

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

Поиск элемента в двусвязном списке можно вести:

а)      просматривая элементы от начала к концу списка,

б)      просматривая элементы от конца списка к началу,

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

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

void exam1(list2 *p) // Просмотр циклического (возможно пустого)

                              // списка без заглавного звена

{ list2 *ph;            // в направлении от начала к концу списка

if (p = = NULL) return;

ph = p;

do {...

p = p -> next; }

while (p!= ph); //Просмотр продолжается пока текущий указатель

// p не равен указателю на начало списка - ph

}

...

void exam2(list2 *p) // Просмотр кольцевого (возможно пустого)

                             // списка с заглавным звеном

{ list2 *pr;            // в направлении от конца списка к началу

if (p –> next = = p) return;

pr = p -> pred;     // Текущий указатель pr получил значение ссылки

// на последний элемент списка

while (pr!= p)          //Просмотр продолжается пока текущий указатель pr

// не равен указателю на заглавное звено списка - p

{

...

pr = pr -> pred; }

...

x = new list2;      // Включение нового элемента (в список с

x -> pred = p -> pred; // заглавным звеном) перед элементом, на

x -> next = p;      // который ссылается p

p -> pred -> next = x;

p -> pred = x;

...

p -> pred -> next = p -> next; // Исключение из списка с заглавным

p -> next -> pred = p -> pred; // звеном элемента, на который

delete p;                              // ссылается указатель p

Контрольные вопросы

 

1.Понятие двусвязного списка. Возможные структуры двусвязного списка.

2.Задание двусвязного списка.

3.Основные операции над двусвязным списком.

Задания для практической работы

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

1. Дана последовательность символов, оканчивающаяся точкой найти всех соседей заданного символа (первый и последний символы считать соседями).

2. Дана последовательность символов, оканчивающаяся точкой подсчитать количество символов, у которых левый сосед больше правого соседа (первый и последний элемент считать соседями);

3. Дана последовательность символов, оканчивающаяся точкой удалить все символы, у которых равные соседи (первый и последний символы считать соседями);

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

5. Дана последовательность символов, оканчивающаяся точкой в конец последовательности добавить все ее символы, располагая их в обратном порядке (например, из последовательности 1, 2, 3 получить 1, 2, 3, 2,1).

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

7. Даны две разреженные квадратные матрицы A и B порядка n(разреженная матрица это матрица высокого порядка с большим количеством нулевых элементов). Получить матрицу C = A+B. Для представления разреженной матрицы использовать двусвязный циклический список. Каждое звено списка состоит из пяти полей:

- поле с номером строки ненулевого элемента,

- поле с номером столбца ненулевого элемента,

- поле со значением элемента,

- поле со ссылкой на предыдущий ненулевой элемент в этой же строке,

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

8. Дан многочлен P(x) произвольной степени с целыми коэффициентами, причем его одночлены могут быть не упорядочены по степеням x, а одночлены с одинаковой степенью могут повторяться (например, -75x + 8x⁴ - x² + 6x⁴ – 5 - x). Привести подобные члены в этом многочлене и расположить одночлены по убыванию степеней x.

9. Даны действительные числа x₁, x₂,..., x_n (n >= 2 и заранее неизвестно). Вычислить x₁ x_n + x₂ x_n-1 +... + x_n x₁.

10. Даны действительные числа x₁, x₂,..., x_n (n >= 2 и заранее неизвестно). Вычислить (x₁ + x_n) (x₂ + x_n-1)... (x_n + x₁).

11. Даны действительные числа x₁, x₂,..., x_n (n >= 2 и заранее неизвестно). Вычислить (x₁ + x₂ + 2x_n) (x₂ + x₃ + 2x_n-1)... (x_n-1 + x_n + 2x₂).

12. Даны действительные числа y₁, y₂,..., y_n (n >= 2 и заранее неизвестно). Получить последовательность y₁, y₂,..., y_n, y₁,..., y_n.

13. Даны действительные числа y₁, y₂,..., y_n (n >= 2 и заранее неизвестно). Получить последовательность y₁, y₂,..., y_n, y_n,..., y₁.

14. Даны действительные числа y₁, y₂,..., y_n (n >= 2 и заранее неизвестно). Получить последовательность y_n, y_n-1,..., y₁, y₁,..., y_n.

15. Даны действительные числа a₁, a₂,..., a_2n (n >= 2 и заранее неизвестно). Вычислить

15.1.1. a₁ a_2n + a₂ a_2n-1 +... + a_n a_n+1;

16. Даны действительные числа a₁, a₂,..., a_2n (n >= 2 и заранее неизвестно). Вычислить      min (a₁ + a_n+1, a₂ + a_n+2,..., a_n + a_2n);

17. Даны действительные числа a₁, a₂,..., a_2n (n >= 2 и заранее неизвестно). Вычислить      max (min (a₁, a_2n), min (a₃, a_2n-2),..., min (a_2n-1, a₂)).

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