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

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 и заранее неизвестно). Вычислить

    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. Далее можно выбрать любую из задач для линейного односвязного списка.