Содержание
- 2. Структуры данных Структуры данных Составитель курса лекций: Спиричева Наталия Рахматулловна, ст. преподаватель каф. Информационных технологий
- 3. Структуры данных Структуры данных Динамические структуры данных
- 4. Структуры данных Структуры данных и алгоритмы Основные темы лекции: Связное представление данных в памяти Стек Очередь
- 5. Структуры данных Структуры данных Целью лекции является приобретение студентами следующих компетенций: знать особенности динамических структур данных
- 6. Структуры данных ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ. СВЯЗНЫЕ СПИСКИ Тема 1: Связное представление данных в памяти
- 7. Структуры данных Связное представление данных в памяти Динамические структуры, по определению, характеризуются отсутствием физической смежности элементов
- 8. Структуры данных Связное представление данных в памяти Поскольку элементы динамической структуры располагаются по непредсказуемым адресам памяти,
- 9. Структуры данных Связное представление данных в памяти Элемент динамической структуры состоит из двух полей: информационного поля
- 10. Структуры данных Связное представление данных в памяти В простейшем случае элемент имеет вид: В данном случае
- 11. Структуры данных Связное представление данных в памяти Достоинства связного представления данных - в возможности обеспечения значительной
- 12. Структуры данных Связное представление данных в памяти Вместе с тем связное представление не лишено и недостатков,
- 13. Структуры данных Списком называется линейно – упорядоченная последовательность элементов данных Е.(1), Е(2), ..., Е(п), n >
- 14. Структуры данных Операции, которые имеем право выполнять с линейными списками
- 15. Структуры данных Стек – линейный список, в котором все включения и исключения (и обычно всякий доступ)
- 16. Структуры данных ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ. СВЯЗНЫЕ СПИСКИ Тема 2: Стеки
- 17. Структуры данных Стеки Стек - такой последовательный список с переменной длиной, включение и исключение элементов из
- 18. Структуры данных Стеки
- 19. Структуры данных Стеки Основные операции над стеком: включение нового элемента исключение элемента из стека Вспомогательные операции:
- 20. Структуры данных Стеки Состояния стека: а) пустой; б-г) после последовательного включения в него элементов 'A', 'B',
- 21. Структуры данных Машинное представление стека и реализация операций При представлении стека в статической памяти для него
- 22. Структуры данных Стеки Операция исключения элемента состоит в модификации указателя стека и выборке значения, на которое
- 23. Структуры данных Стеки Операция очистки стека сводится к записи в указатель стека начального значения - адреса
- 24. Структуры данных Стеки Определение размера стека сводится к вычислению разности указателей: указателя стека и адреса начала
- 25. Структуры данных Стеки Стеки в вычислительных системах Стек является чрезвычайно удобной структурой данных для многих задач
- 26. Структуры данных Стеки В 1920 г. польский математик Ян Лукашевич предложил способ записи арифметических формул, не
- 27. Структуры данных Стеки В польской записи скобки не нужны. Например, выражение (2+3)*(15-7) записывается в прямой польской
- 28. Структуры данных Стеки Обратная польская запись формулы позволяет вычислять выражение любой сложности, используя стек как запоминающее
- 29. Структуры данных Стеки Для вычисления выражения надо сначала преобразовать его в обратную польскую запись (при некотором
- 30. Структуры данных ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ. СВЯЗНЫЕ СПИСКИ Тема 3: Очереди FIFO
- 31. Структуры данных Очереди FIFO Логическая структура очереди Очередью FIFO (First In - First Out - "первым
- 32. Структуры данных Очереди FIFO Из динамических элементов формируется цепочка. Динамический элемент хранит адрес следующего динамического элемента.
- 33. Структуры данных Очереди FIFO Основные операции над очередью - те же, что и над стеком: включение
- 34. Структуры данных Очереди FIFO Машинное представление очереди FIFO и реализация операций При представлении очереди вектором в
- 35. Структуры данных Очереди FIFO Возможны, конечно, и другие варианты организации очередей: например, всякий раз, когда указатель
- 36. Структуры данных Очереди FIFO Очереди с приоритетами В реальных задачах иногда возникает необходимость в формировании очередей,
- 37. Структуры данных Очереди FIFO Очереди с приоритетами могут быть реализованы на линейных списковых структурах - в
- 38. Структуры данных Очереди FIFO Очереди в вычислительных системах Идеальным примером кольцевой очереди в вычислительной системы является
- 39. Структуры данных Очереди FIFO Очередь является одним из ключевых понятий в многозадачных операционных системах (Windows NT,
- 40. Структуры данных Очереди FIFO Также в современных операционных системах одним из средств взаимодействия между параллельно выполняемыми
- 41. Структуры данных Очереди FIFO Логическая структура очереди FIFO (First In - First Out - "первым пришел
- 42. Структуры данных Очереди FIFO Очереди с приоритетами Порядок выборки элементов из очередей определяется приоритетами элементов. Приоритет
- 43. Структуры данных ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ. СВЯЗНЫЕ СПИСКИ Тема 4: Деки
- 44. Структуры данных Деки Логическая структура дека Дек особый вид очереди в виде последовательного списка, в котором
- 45. Структуры данных Деки Состояния дека в процессе изменения
- 46. Структуры данных ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ. СВЯЗНЫЕ СПИСКИ Тема 5: Связные линейные списки
- 47. Структуры данных Связные линейные списки Машинное представление связных линейных списков Поле INF - информационное поле, данные,
- 48. Структуры данных Связные линейные списки Обработка односвязного списка не всегда удобна, так как отсутствует возможность продвижения
- 49. Структуры данных Связные линейные списки Разновидностью рассмотренных видов линейных списков является кольцевой список. При этом в
- 50. Структуры данных Связные линейные списки Реализация операций над связными линейными списками Перебор элементов списка. Осуществляется последовательный
- 51. Структуры данных Связные линейные списки В двухсвязном списке возможен перебор как в прямом направлении, так и
- 52. Структуры данных Связные линейные списки В кольцевом списке окончание перебора должно происходить не по признаку последнего
- 53. Структуры данных Связные линейные списки Вставка элемента в список. void InsertSll( link& prev, data inf )
- 54. Структуры данных Связные линейные списки Вставка элемента в середину 2-связного списка
- 55. Структуры данных Связные линейные списки Вставка элемента в начало 1-связного списка
- 56. Структуры данных Связные линейные списки void DeleteSll( link& head, link del ) { if( head ==
- 57. Структуры данных Связные линейные списки Удаление элемента из 2-связного списка
- 58. Структуры данных Связные линейные списки Перестановка элементов списка void ExchangeSll( link& prev ) { if( prev
- 59. Структуры данных Связные линейные списки Перестановка соседних элементов 2-связного списка
- 60. Структуры данных Связные линейные списки Копирование части списка При копировании старый список сохраняется в памяти и
- 61. Структуры данных Связные линейные списки Алгоритм копирования части списка: link CopyList( link head, int num )
- 62. Структуры данных Связные линейные списки Слияние двух списков Операция слияния заключается в формировании из двух списков
- 63. Структуры данных ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ. СВЯЗНЫЕ СПИСКИ Тема 6: Мультисписки
- 64. Структуры данных Мультисписки Пример мультисписка
- 65. Структуры данных Мультисписки Для того чтобы при выборке каждого подмножества не выполнять полный просмотр с отсеиванием
- 66. Структуры данных Мультисписки Специфика мультисписка проявляется только в операции исключения элемента из списка. Исключение элемента из
- 67. Структуры данных ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ. СВЯЗНЫЕ СПИСКИ Тема 7: Нелинейные разветвленные списки
- 68. Структуры данных Нелинейные разветвленные списки Основные понятия Нелинейным разветвленным списком является список, элементами которого могут быть
- 69. Структуры данных Нелинейные разветвленные списки Схематичное представление разветвленного списка
- 70. Структуры данных Нелинейные разветвленные списки Разветвленные списки описываются тремя характеристиками: порядком глубиной длиной.
- 71. Структуры данных Нелинейные разветвленные списки Порядок. Над элементами списка задано транзитивное отношение, определяемое последовательностью, в которой
- 72. Структуры данных Нелинейные разветвленные списки Глубина. Это максимальный уровень, приписываемый элементам внутри списка или внутри любого
- 73. Структуры данных Нелинейные разветвленные списки Выражение: (a+b)*(c-(d/e))+f будет вычисляться в следующем порядке: a+b d/e c-(d/e) (a+b)*(c-d/e)
- 74. Структуры данных Нелинейные разветвленные списки Представление списковых структур в памяти Элементы списка могут быть двух видов:
- 75. Структуры данных Нелинейные разветвленные списки Поле type содержат признак атом/узел, оно может быть 1-битовым. Такой формат
- 76. Структуры данных Нелинейные разветвленные списки Операции обработки списков Базовыми операциями при обработке списков являются операции (функции):
- 77. Структуры данных Нелинейные разветвленные списки Операция car в качестве аргумента получает список (указатель на начало списка).
- 78. Структуры данных Нелинейные разветвленные списки Операция cdr в качестве аргумента также получает список. Ее возвращаемым значением
- 79. Структуры данных Нелинейные разветвленные списки Операция cons имеет два аргумента: указатель на элемент списка и указатель
- 80. Структуры данных Нелинейные разветвленные списки Операция atom выполняет проверку типа элемента списка. Она должна возвращать логическое
- 81. Структуры данных ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ. СВЯЗНЫЕ СПИСКИ Тема 8: Управление динамически выделяемой памятью
- 82. Структуры данных Управление динамически выделяемой памятью Динамические структуры по определению характеризуются непостоянством и непредсказуемостью размера. Поэтому
- 83. Структуры данных Управление динамически выделяемой памятью В общем случае при распределении памяти должны быть решены следующие
- 84. Структуры данных Управление динамически выделяемой памятью Память выделяется блоками. Блоки могут быть фиксированной или переменной длины.
- 85. Структуры данных Управление динамически выделяемой памятью Одной из проблем, которые должны приниматься во внимание при управлении
- 86. Структуры данных 1.Каковы особенности динамических структур данных? 2. Перечислите основные динамические структуры? 3. Какие основные операции
- 88. Скачать презентацию