Алгоритмы и структуры данных

Добрый день! Требует выполнить работу по алгоритмам и структурам данных.

Задание в закрепе. Вариант №4

Программа работы со связным списком

 

1. Создать тип данных, описывающий звено двусвязного списка.

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

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

4. Заполнить список данными, используя, например, цикл for и добавляя данные в начало списка (за ведущим звеном). Число данных выбрать в количестве 7 – 8 элементов.

5. Просмотреть содержимое списка.

6. Удалить звено, следующее за ведущим.

7. Просмотреть содержимое списка.

8. Удалить звено из середины списка, используя операцию поиска данных в списке.

9. Просмотреть содержимое списка.

Работа со списком как со стеком

 

10. Добавить 1 звено в начало списка (в позицию за ведущим звеном).

11. Просмотреть содержимое списка.

12. Считать данные из вершины стека (т.е. из начала списка – из звена, следующего за ведущим).

13. Просмотреть содержимое списка.

14. Повторить пункты 10, 11 несколько раз с разными данными.

15. Повторить пункты 12, 13 несколько раз.

16. Считать все звенья из начала списка. После каждой операции считывания выполнять просмотр списка.

 

 

Работа со списком как с очередью

 

17. Добавить 1 звено в конец очереди (т.е. в конец списка – в позицию перед ведущим звеном).

18. Просмотреть содержимое списка.

19. Повторить пункты 17, 18 несколько раз с разными данными.

20. Считать данные из начала очереди (из звена следующего за ведущим звеном).

21. Просмотреть содержимое списка.

22. Повторить пункты 20, 21 несколько раз.

23. Считать все звенья из начала списка. После каждой операции считывания выполнять просмотр списка.

 

 

Работа со списком как с двухвходовой очередью (деком)

 

24. Добавить 1 звено в конец очереди (т.е. в конец списка – в позицию перед ведущим звеном).

25. Просмотреть содержимое списка.

26. Повторить пункты 24, 25 несколько раз.

27. Удалить звено из начала очереди (из звена следующего за ведущим звеном).

28. Просмотреть содержимое списка.

29. Добавить 1 звено в начало очереди (в позицию за ведущим звеном).

30. Просмотреть содержимое списка.

31. Повторить пункты 29, 30 несколько раз.

32. Удалить звено из конца очереди.

33. Просмотреть содержимое списка.

34. Удалить все звенья из списка.

Работа с двоичным деревом поиска

 

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

в нисходящем и последовательном порядках.

36. Удалить ведущее звено двусвязного кольцевого списка, если оно создавалось (см. пояснения к выполнению задания), и обнулить отводимый для этого звена указатель.

37. Создать двоичное дерево поиска путѐм ввода данных (не менее 7 элементов).

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

38. Выполнить просмотр дерева в последовательном порядке.

39. Выполнить просмотр дерева в нисходящем порядке.

40. Выполнить поиск данных в дереве.

41. Определить высоту дерева.

42. Удалить все узлы дерева.

43. Создать двоичное дерево поиска путѐм ввода упорядоченных данных (не менее 7 элементов, в таком же количестве, как и в пункте 37).

44. Выполнить просмотр дерева в последовательном порядке.

45. Выполнить просмотр дерева в нисходящем порядке. Сравнить с результатами выполнения пунктов 38 и 39.

46. Определить высоту дерева. Сравнить с результатами выполнения пункта 41.