Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
СТРУКТУРЫ ДАННЫХ Лектор Спиричева Наталия Рахматулловна Ст. преподаватель каф
Содержание
- 1. СТРУКТУРЫ ДАННЫХ Лектор Спиричева Наталия Рахматулловна Ст. преподаватель каф
- 2. Структуры данных Структуры данныхСоставитель курса лекций:Спиричева Наталия Рахматулловна, ст. преподаватель каф. Информационных технологий
- 3. Структуры данных Структуры данныхДинамические структуры данных
- 4. Структуры данных Структуры данных и алгоритмыОсновные темы лекции:Связное представление данных в памятиСтекОчередьДекМногосвязные списки
- 5. Структуры данных Структуры данных Целью лекции является приобретение студентами
- 6. Структуры данных ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ. СВЯЗНЫЕ СПИСКИ Тема 1: Связное представление данных в памяти
- 7. Структуры данных Связное представление данных в памяти Динамические
- 8. Структуры данных Связное представление данных в памяти Поскольку
- 9. Структуры данных Связное представление данных в памяти Элемент
- 10. Структуры данных Связное представление данных в памяти
- 11. Структуры данных Связное представление данных в памяти Достоинства
- 12. Структуры данных Связное представление данных в памяти Вместе
- 13. Структуры данных Списком называется
- 14. Структуры данных Операции, которые имеем право выполнять с линейными списками
- 15. Структуры данных Стек – линейный список, в котором
- 16. Структуры данных ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ. СВЯЗНЫЕ СПИСКИ Тема 2: Стеки
- 17. Структуры данных Стеки Стек - такой последовательный список с
- 18. Структуры данных Стеки
- 19. Структуры данных СтекиОсновные операции над стеком:включение нового элементаисключение
- 20. Структуры данных СтекиСостояния стека:а) пустой;б-г) после последовательного включения
- 21. Структуры данных Машинное представление стека и реализация операций При
- 22. Структуры данных Стеки Операция исключения элемента состоит в модификации
- 23. Структуры данных Стеки Операция очистки стека сводится к записи
- 24. Структуры данных Стеки Определение размера стека сводится к вычислению разности указателей: указателя стека и адреса начала области.
- 25. Структуры данных СтекиСтеки в вычислительных системах Стек является чрезвычайно
- 26. Структуры данных Стеки В 1920 г. польский математик Ян
- 27. Структуры данных Стеки В польской записи скобки не нужны.
- 28. Структуры данных Стеки Обратная польская запись формулы позволяет вычислять
- 29. Структуры данных Стеки Для вычисления выражения надо сначала преобразовать
- 30. Структуры данных ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ. СВЯЗНЫЕ СПИСКИ Тема 3: Очереди FIFO
- 31. Структуры данных Очереди FIFOЛогическая структура очереди Очередью FIFO (First
- 32. Структуры данных Очереди FIFO Из динамических элементов
- 33. Структуры данных Очереди FIFOОсновные операции над очередью - те же, что и над стеком: включениеисключениеопределение размераочистка,неразрушающее чтение.
- 34. Структуры данных Очереди FIFOМашинное представление очереди FIFO и
- 35. Структуры данных Очереди FIFO Возможны, конечно, и другие варианты
- 36. Структуры данных Очереди FIFOОчереди с приоритетами В реальных задачах
- 37. Структуры данных Очереди FIFO Очереди с приоритетами могут быть
- 38. Структуры данных Очереди FIFOОчереди в вычислительных системах Идеальным примером
- 39. Структуры данных Очереди FIFO Очередь является одним из ключевых
- 40. Структуры данных Очереди FIFO Также в современных операционных системах
- 41. Структуры данных Очереди FIFOЛогическая структура очереди FIFO (First In
- 42. Структуры данных Очереди FIFOОчереди с приоритетами Порядок выборки элементов
- 43. Структуры данных ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ. СВЯЗНЫЕ СПИСКИ Тема 4: Деки
- 44. Структуры данных ДекиЛогическая структура дека Дек особый вид очереди
- 45. Структуры данных ДекиСостояния дека в процессе изменения
- 46. Структуры данных ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ. СВЯЗНЫЕ СПИСКИ Тема 5: Связные линейные списки
- 47. Структуры данных Связные линейные списки Машинное представление связных
- 48. Структуры данных Связные линейные списки Обработка односвязного списка
- 49. Структуры данных Связные линейные списки Разновидностью рассмотренных видов
- 50. Структуры данных Связные линейные списки Реализация операций над
- 51. Структуры данных Связные линейные списки В двухсвязном списке
- 52. Структуры данных Связные линейные списки В кольцевом списке
- 53. Структуры данных Связные линейные списки Вставка элемента в
- 54. Структуры данных Связные линейные списки Вставка элемента в середину 2-связного списка
- 55. Структуры данных Связные линейные списки Вставка элемента в начало 1-связного списка
- 56. Структуры данных Связные линейные списки void DeleteSll( link&
- 57. Структуры данных Связные линейные списки Удаление элемента из 2-связного списка
- 58. Структуры данных Связные линейные списки Перестановка элементов списка
- 59. Структуры данных Связные линейные списки Перестановка соседних элементов 2-связного списка
- 60. Структуры данных Связные линейные списки Копирование части списка При
- 61. Структуры данных Связные линейные списки Алгоритм копирования
- 62. Структуры данных Связные линейные списки Слияние двух списков Операция
- 63. Структуры данных ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ. СВЯЗНЫЕ СПИСКИ Тема 6: Мультисписки
- 64. Структуры данных Мультисписки Пример мультисписка
- 65. Структуры данных Мультисписки Для того чтобы при выборке
- 66. Структуры данных Мультисписки Специфика мультисписка проявляется только в
- 67. Структуры данных ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ. СВЯЗНЫЕ СПИСКИ Тема 7: Нелинейные разветвленные списки
- 68. Структуры данных Нелинейные разветвленные списки Основные понятия Нелинейным разветвленным
- 69. Структуры данных Нелинейные разветвленные списки Схематичное представление разветвленного списка
- 70. Структуры данных Нелинейные разветвленные списки Разветвленные списки описываются тремя характеристиками:порядкомглубинойдлиной.
- 71. Структуры данных Нелинейные разветвленные списки Порядок. Над элементами
- 72. Структуры данных Нелинейные разветвленные списки Глубина. Это максимальный
- 73. Структуры данных Нелинейные разветвленные списки Выражение: (a+b)*(c-(d/e))+f
- 74. Структуры данных Нелинейные разветвленные списки Представление списковых структур
- 75. Структуры данных Нелинейные разветвленные списки Поле type содержат
- 76. Структуры данных Нелинейные разветвленные списки Операции обработки списковБазовыми
- 77. Структуры данных Нелинейные разветвленные списки Операция car в
- 78. Структуры данных Нелинейные разветвленные списки Операция cdr в
- 79. Структуры данных Нелинейные разветвленные списки Операция cons имеет
- 80. Структуры данных Нелинейные разветвленные списки Операция atom выполняет
- 81. Структуры данных ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ. СВЯЗНЫЕ СПИСКИ Тема 8: Управление динамически выделяемой памятью
- 82. Структуры данных Управление динамически выделяемой памятью Динамические структуры
- 83. Структуры данных Управление динамически выделяемой памятью В общем
- 84. Структуры данных Управление динамически выделяемой памятью Память выделяется
- 85. Структуры данных Управление динамически выделяемой памятью Одной из
- 86. Структуры данных 1.Каковы особенности динамических структур данных?2. Перечислите
- 87. Спасибо за внимание!Структуры данных
- 88. Скачать презентанцию
Структуры данных Структуры данныхСоставитель курса лекций:Спиричева Наталия Рахматулловна, ст. преподаватель каф. Информационных технологий
Слайды и текст этой презентации
Слайд 2Структуры данных
Структуры данных
Составитель курса лекций:
Спиричева Наталия Рахматулловна,
ст. преподаватель каф.
Информационных технологий
Слайд 4Структуры данных
Структуры данных и алгоритмы
Основные темы лекции:
Связное представление данных в
памяти
Стек
Очередь
Дек
Многосвязные списки
Слайд 5Структуры данных
Структуры данных
Целью лекции является приобретение студентами следующих компетенций:
знать особенности
динамических структур данных
иметь представление о физической и логической структуре
уметь применять
динамические структуры при программировании
Слайд 6Структуры данных
ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ.
СВЯЗНЫЕ СПИСКИ
Тема 1:
Связное представление данных
в памяти
Слайд 7Структуры данных
Связное представление данных в памяти
Динамические структуры, по определению,
характеризуются отсутствием физической смежности элементов структуры в памяти, непостоянством и
непредсказуемостью размера (числа элементов) структуры в процессе ее обработки.
Слайд 8Структуры данных
Связное представление данных в памяти
Поскольку элементы динамической структуры
располагаются по непредсказуемым адресам памяти, адрес элемента такой структуры не
может быть вычислен из адреса начального или предыдущего элемента. Для установления связи между элементами динамической структуры используются указатели, через которые устанавливаются явные связи между элементами. Такое представление данных в памяти называется связным.
Слайд 9Структуры данных
Связное представление данных в памяти
Элемент динамической структуры состоит
из двух полей:
информационного поля или поля данных, в котором
содержатся те данные, ради которых и создается структура; в общем случае информационное поле само является интегрированной структурой - вектором, массивом, записью и т.п.;поля связок, в котором содержатся один или несколько указателей, связывающих данный элемент с другими элементами структуры.
Слайд 10Структуры данных
Связное представление данных в памяти
В простейшем случае
элемент имеет вид:
В данном случае информационная часть состоит из одного
поля, которое используется для хранения одного целого числа, указатель - из указателя на один элемент.
Слайд 11Структуры данных
Связное представление данных в памяти
Достоинства связного представления данных
- в возможности обеспечения значительной изменчивости структур
размер структуры ограничивается только
доступным объемом машинной памяти;при изменении логической последовательности элементов структуры требуется не перемещение данных в памяти, а только коррекция указателей.
Слайд 12Структуры данных
Связное представление данных в памяти
Вместе с тем связное
представление не лишено и недостатков, основные из которых:
работа с указателями
требует, как правило, более высокой квалификации от программиста;на поля связок расходуется дополнительная память;
доступ к элементам связной структуры может быть менее эффективным по времени.
Слайд 13Структуры данных
Списком называется линейно
– упорядоченная последовательность элементов данных Е.(1), Е(2), ..., Е(п), n
> О, причем каждый элемент характеризуется одним и тем же набором попей.
Слайд 15Структуры данных
Стек – линейный список, в котором все включения и
исключения (и обычно всякий доступ) делаются в одном конце списка.
Очередь
– линейный список, в котором все включения производятся на одном конце списка, а все исключения (и обычно всякий доступ) делаются на другом его конце.Дек (очередь с двумя концами) – линейный список, в котором все включения и исключения (и обычно всякий доступ) делаются на обоих концах списка.
Слайд 17Структуры данных
Стеки
Стек - такой последовательный список с переменной длиной, включение
и исключение элементов из которого выполняются только с одной стороны
списка, называемого вершиной стека.LIFO (Last In - First Out - "последним пришел - первым исключился").
Слайд 19Структуры данных
Стеки
Основные операции над стеком:
включение нового элемента
исключение элемента из стека
Вспомогательные операции:
определение текущего числа элементов в стеке;
очистка стека;
неразрушающее чтение элемента
из вершины стека, которое может быть реализовано как комбинация основных операций:x:=pop(stack); push(stack,x).
Слайд 20Структуры данных
Стеки
Состояния стека:
а) пустой;
б-г) после последовательного включения в него элементов
'A', 'B', 'C';
д, е) после последовательного удаления из стека элементов
'C' и 'B';ж) после включения в стек элемента 'D'.
Слайд 21Структуры данных
Машинное представление стека и реализация операций
При представлении стека в
статической памяти для него выделяется память, как для вектора. В
дескрипторе этого вектора кроме обычных для вектора параметров должен находиться также указатель стека - адрес вершины стека.Указатель стека может указывать либо на первый свободный элемент стека, либо на последний записанный в стек элемент.
При занесении элемента в стек элемент записывается на место, определяемое указателем стека, затем указатель модифицируется таким образом, чтобы он указывал на следующий свободный. Модификация указателя состоит в прибавлении к нему или в вычитании из него единицы.
Слайд 22Структуры данных
Стеки
Операция исключения элемента состоит в модификации указателя стека и
выборке значения, на которое указывает указатель стека. После выборки слот,
в котором размещался выбранный элемент, считается свободным.
Слайд 23Структуры данных
Стеки
Операция очистки стека сводится к записи в указатель стека
начального значения - адреса начала выделенной области памяти.
Слайд 24Структуры данных
Стеки
Определение размера стека сводится к вычислению разности указателей: указателя
стека и адреса начала области.
Слайд 25Структуры данных
Стеки
Стеки в вычислительных системах
Стек является чрезвычайно удобной структурой данных
для многих задач вычислительной техники. Наиболее типичной из таких задач
является обеспечение вложенных вызовов функций.
Слайд 26Структуры данных
Стеки
В 1920 г. польский математик Ян Лукашевич предложил способ
записи арифметических формул, не использующий скобок. В привычной нам записи
знак операции записывается между аргументами, например, сумма чисел 2 и 3 записывается как 2 + 3. Ян Лукашевич предложил две другие формы записи: префиксная форма, в которой знак операции записывается перед аргументами, и постфиксная форма, в которой знак операции записывается после аргументов. В префиксной форме сумма чисел 2 и 3 записывается как + 2 3, в постфиксной — как 2 3 +. В честь Яна Лукашевича эти формы записи называют прямой и обратной польской записью.
Слайд 27Структуры данных
Стеки
В польской записи скобки не нужны. Например, выражение
(2+3)*(15-7)
записывается
в прямой польской записи как
* + 2 3 -
15 7,в обратной польской записи — как
2 3 + 15 7 - *.
Если прямая польская запись не получила большого распространения, то обратная оказалась чрезвычайно полезной. Неформально преимущество обратной записи перед прямой польской записью или обычной записью можно объяснить тем, что гораздо удобнее выполнять некоторое действие, когда объекты, над которыми оно должно быть совершено, уже даны.
Слайд 28Структуры данных
Стеки
Обратная польская запись формулы позволяет вычислять выражение любой сложности,
используя стек как запоминающее устройство для хранения промежуточных результатов. Такой
стековый калькулятор был впервые выпущен фирмой Hewlett Packard. Обычные модели калькуляторов не позволяют вычислять сложные формулы без использования бумаги и ручки для записи промежуточных результатов. В некоторых моделях есть скобки с одним или двумя уровнями вложенности, но более сложные выражения вычислять невозможно. Также в обычных калькуляторах трудно понять, как результат и аргументы перемещаются в процессе ввода и вычисления между регистрами калькулятора. Калькулятор обычно имеет регистры X, Y и регистр памяти, промежуточные результаты каким-то образом перемещаются по регистрам, каким именно — запомнить невозможно.
Слайд 29Структуры данных
Стеки
Для вычисления выражения надо сначала преобразовать его в обратную
польскую запись (при некотором навыке это легко сделать в уме).
В приведенном выше примере выражение (2+3)*(15-7) преобразуется к2 3 + 15 7 - *
Затем обратная польская запись просматривается последовательно слева направо. Если мы видим число, то просто вводим его в калькулятор, т.е. добавляем его в стек. Если мы видим знак операции, то нажимаем соответствующую клавишу калькулятора, выполняя таким образом операцию с числами на вершине стека.
Слайд 31Структуры данных
Очереди FIFO
Логическая структура очереди
Очередью FIFO (First In - First
Out - "первым пришел - первым исключается") называется такой последовательный
список переменной длины, в котором включение элементов выполняется только с одной стороны списка (эту сторону часто называют концом или хвостом очереди), а исключение - с другой стороны (называемой началом или головой очереди).Очереди в магазинах являются типичным бытовым примером очереди FIFO.
Слайд 32Структуры данных
Очереди FIFO
Из динамических элементов формируется цепочка. Динамический
элемент хранит адрес следующего динамического элемента.
Очередь работает по тому же
принципу, что и очередь в магазине: "первым пришел, первым ушел". Элементы добавляются в конец очереди, а берутся из начала. Для работы необходимо знать начало и конец очереди.Указатель у последнего элемента в очереди хранит нулевое значение
Слайд 33Структуры данных
Очереди FIFO
Основные операции над очередью - те же, что
и над стеком:
включение
исключение
определение размера
очистка,
неразрушающее чтение.
Слайд 34Структуры данных
Очереди FIFO
Машинное представление очереди FIFO и реализация операций
При представлении
очереди вектором в статической памяти в дополнение к обычным для
дескриптора вектора параметрам в нем должны находиться два указателя: на начало очереди (на первый элемент в очереди) и на ее конец (первый свободный элемент в очереди).При включении элемента в очередь элемент записывается по адресу, определяемому указателем на конец, после чего этот указатель увеличивается на единицу.
При исключении элемента из очереди выбирается элемент, адресуемый указателем на начало, после чего этот указатель уменьшается на единицу.
Слайд 35Структуры данных
Очереди FIFO
Возможны, конечно, и другие варианты организации очередей: например,
всякий раз, когда указатель конца достигнет верхней границы памяти, сдвигать
все непустые элементы очереди к началу области памяти, но как этот, так и другие варианты, требуют перемещения в памяти элементов очереди и менее эффективны, чем кольцевая очередь.
Слайд 36Структуры данных
Очереди FIFO
Очереди с приоритетами
В реальных задачах иногда возникает необходимость
в формировании очередей, отличных от FIFO или LIFO. Порядок выборки
элементов из таких очередей определяется приоритетами элементов. Приоритет в общем случае может быть представлен числовым значением, которое вычисляется либо на основании значений каких-либо полей элемента, либо на основании внешних факторов. Так, и FIFO, и LIFO-очереди могут трактоваться как приоритетные очереди, в которых приоритет элемента зависит от времени его включения в очередь. При выборке элемента всякий раз выбирается элемент с наибольшим приоритетом.
Слайд 37Структуры данных
Очереди FIFO
Очереди с приоритетами могут быть реализованы на линейных
списковых структурах - в смежном или связном представлении. Возможны очереди
с приоритетным включением - в которых последовательность элементов очереди все время поддерживается упорядоченной, т.е. каждый новый элемент включается на то место в последовательности, которое определяется его приоритетом, а при исключении всегда выбирается элемент из начала. Возможны и очереди с приоритетным исключением - новый элемент включается всегда в конец очереди, а при исключении в очереди ищется (этот поиск может быть только линейным) элемент с максимальным приоритетом и после выборки удаляется из последовательности. И в том, и в другом варианте требуется поиск, а если очередь размещается в статической памяти - еще и перемещение элементов.
Слайд 38Структуры данных
Очереди FIFO
Очереди в вычислительных системах
Идеальным примером кольцевой очереди в
вычислительной системы является буфер клавиатуры в Базовой системе ввода-вывода ПЭВМ
IBM PC. Буфер клавиатуры занимает последовательность байтов памяти по адресам от 40:1E до 40:2D включительно. По адресам 40:1A и 40:1C располагаются указатели на начало и конец очереди соответственно. При нажатии на любую клавишу генерируется прерывание 9. Обработчик этого прерывания читает код нажатой клавиши и помещает его в буфер клавиатуры - в конец очереди. Коды нажатых клавиш могут накапливаться в буфере клавиатуры, прежде чем они будут прочитаны программой. Программа при вводе данных с клавиатуры обращается к прерыванию 16H. Обработчик этого прерывания выбирает код клавиши из буфера - из начала очереди - и передает в программу.
Слайд 39Структуры данных
Очереди FIFO
Очередь является одним из ключевых понятий в многозадачных
операционных системах (Windows NT, Unix, OS/2, ЕС и др.). Ресурсы
вычислительной системы (процессор, оперативная память, внешние устройства и т.п.) используются всеми задачами, которые одновременно выполняются в среде такой операционной системы. Поскольку многие виды ресурсов реально не допускают одновременного их использования разными задачами, такие ресурсы предоставляются задачам поочередно. Таким образом, задачи, претендующие на использование того или иного ресурса, выстраиваются в очередь к этому ресурсу. Эти очереди обычно приоритетные, однако, довольно часто применяются и FIFO-очереди, так как это единственная логическая организация очереди, которая гарантированно не допускает постоянного вытеснения задачи более приоритетными. LIFO-очереди обычно используются операционными системами для учета свободных ресурсов.
Слайд 40Структуры данных
Очереди FIFO
Также в современных операционных системах одним из средств
взаимодействия между параллельно выполняемыми задачами являются очереди сообщений, называемые также
почтовыми ящиками. Каждая задача имеет свою очередь - почтовый ящик, и все сообщения, отправляемые ей от других задач, попадают в эту очередь. Задача-владелец очереди выбирает из нее сообщения, причем может управлять порядком выборки - FIFO, LIFO или по приоритету.
Слайд 41Структуры данных
Очереди FIFO
Логическая структура очереди
FIFO (First In - First Out
- "первым пришел - первым исключается")
последовательный список переменной длины,
в котором включение элементов выполняется только с одной стороны списка,а исключение - с другой стороны. Основные операции над очередью:
включение
исключение
определение размера
очистка
неразрушающее чтение
Слайд 42Структуры данных
Очереди FIFO
Очереди с приоритетами
Порядок выборки элементов из очередей определяется
приоритетами элементов. Приоритет в общем случае может быть представлен числовым
значением, которое вычисляется либо на основании значений каких-либо полей элемента, либо на основании внешних факторов.FIFO, и LIFO-очереди могут трактоваться как приоритетные очереди, в которых приоритет элемента зависит от времени его включения в очередь. При выборке элемента всякий раз выбирается элемент с наибольшим приоритетом.
Слайд 44Структуры данных
Деки
Логическая структура дека
Дек особый вид очереди в виде последовательного
списка, в котором как включение, так и исключение элементов может
осуществляться с любого из двух концов списка.Над деком определены следующие операции:
включение элемента справа;
включение элемента слева;
исключение элемента справа;
исключение элемента слева;
определение размера;
очистка.
Слайд 46Структуры данных
ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ.
СВЯЗНЫЕ СПИСКИ
Тема 5:
Связные линейные списки
Слайд 47Структуры данных
Связные линейные списки
Машинное представление связных линейных списков
Поле INF
- информационное поле, данные, NEXT - указатель на следующий элемент
списка.Каждый список должен иметь особый элемент, называемый указателем начала списка или головой списка, который обычно по формату отличен от остальных элементов. В поле указателя последнего элемента списка находится специальный признак NULL, свидетельствующий о конце списка
Слайд 48Структуры данных
Связные линейные списки
Обработка односвязного списка не всегда удобна,
так как отсутствует возможность продвижения в противоположную сторону. Такую возможность
обеспечивает двухсвязный список, каждый элемент которого содержит два указателя: на следующий и предыдущий элементы списка.поле NEXT- указатель на следующий элемент, поле PREV- указатель на предыдущий элемент. В крайних элементах соответствующие указатели должны содержать NULL.
Слайд 49Структуры данных
Связные линейные списки
Разновидностью рассмотренных видов линейных списков является
кольцевой список. При этом в односвязном списке указатель последнего элемента
должен указывать на первый элемент; в двухсвязном списке в первом и последнем элементах соответствующие указатели переопределяются.
Слайд 50Структуры данных
Связные линейные списки
Реализация операций над связными линейными списками
Перебор
элементов списка. Осуществляется последовательный доступ к элементам списка - ко
всем до конца списка или до нахождения искомого элемента.void LookSll( link head )
{ link curr = head;
while( curr )
{ curr = curr->next;
}
}
Слайд 51Структуры данных
Связные линейные списки
В двухсвязном списке возможен перебор как
в прямом направлении, так и в обратном. В последнем случае
параметром процедуры должен быть tail - указатель на конец списка, и переход к следующему элементу должен осуществляться по указателю назад:curr = curr->prev;
Слайд 52Структуры данных
Связные линейные списки
В кольцевом списке окончание перебора должно
происходить не по признаку последнего элемента - такой признак отсутствует,
а по достижению элемента, с которого начался перебор.
Слайд 53Структуры данных
Связные линейные списки
Вставка элемента в список.
void InsertSll(
link& prev, data inf )
{ if( prev )
{ link curr = new
SllNode;curr->inf = inf;
curr->next = prev->next;
prev->next = curr;
}
}
Вставка элемента в середину 1-связного списка
Слайд 56Структуры данных
Связные линейные списки
void DeleteSll( link& head, link del
)
{ if( head == NULL ) return;
if( del == head )
{ head
= del->next;}
else
{ link prev = head;
while( prev->next && prev->next != del ) prev = prev->next;
if( prev->next == del )
{prev->next = del->next;
}
}
if( del ) delete del;
}
Удаление элемента из односвязного списка
Удаление элемента из списка
Слайд 58Структуры данных
Связные линейные списки
Перестановка элементов списка
void ExchangeSll( link&
prev )
{ if( prev && prev->next && prev->next->next )
{ link p1
= prev->next; link p2 = p1->next;
p1->next = p2->next;
P2->next = p1;
prev->next = p2;
}
}
Слайд 60Структуры данных
Связные линейные списки
Копирование части списка
При копировании старый список
сохраняется в памяти и создается новый список. В информационных полях
элементов нового списка содержатся те же данные, что и в элементах старого списка, но поля связок в новом списке совершенно другие, поскольку элементы нового списка расположены по другим адресам в памяти.
Слайд 61Структуры данных
Связные линейные списки
Алгоритм копирования
части списка:
link CopyList( link head, int num )
{ if( head ==
NULL ) return NULL; link first = NULL, last = NULL;
while( head && num>0 )
{ link curr = new SllNode;
curr->next = NULL;
curr->inf = head->inf;
if( first == NULL )
{ first = curr;
last = first; }
else
{ last->next = curr;
last = curr; }
head = head->next;
num--; }
last->next = NULL;
return first;}
Слайд 62Структуры данных
Связные линейные списки
Слияние двух списков
Операция слияния заключается в
формировании из двух списков одного - она аналогична операции сцепления
строк. В случае односвязного списка: последний элемент первого списка содержит пустой указатель на следующий элемент, этот указатель служит признаком конца списка. Вместо этого пустого указателя в последний элемент первого списка заносится указатель на начало второго списка. Таким образом, второй список становится продолжением первого.void Unit( link& Head1, link Head2 )
{ if( Head2 )
{ if(Head1 == NULL ) Head1 = Head2;
else
{ link curr = Head1;
while( curr->next ) curr = curr->next;
curr->next = Head2; }
Head2 = NULL; } }
Слайд 65Структуры данных
Мультисписки
Для того чтобы при выборке каждого подмножества не
выполнять полный просмотр с отсеиванием записей, в каждую запись включаются
дополнительные поля ссылок, каждое из которых связывает в линейный список элементы соответствующего подмножества. В результате получается многосвязный список или мультисписок, каждый элемент которого может входить одновременно в несколько односвязных списков
Слайд 66Структуры данных
Мультисписки
Специфика мультисписка проявляется только в операции исключения элемента
из списка. Исключение элемента из какого-либо одного списка еще не
означает необходимости удаления элемента из памяти, так как элемент может оставаться в составе других списков.
Слайд 67Структуры данных
ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ.
СВЯЗНЫЕ СПИСКИ
Тема 7:
Нелинейные разветвленные списки
Слайд 68Структуры данных
Нелинейные разветвленные списки
Основные понятия
Нелинейным разветвленным списком является список,
элементами которого могут быть тоже списки.
Если один из указателей
каждого элемента списка задает порядок, обратный к порядку, устанавливаемому другим указателем, то такой двусвязный список будет линейнымЕсли же один из указателей задает порядок произвольного вида, не являющийся обратным по отношению к порядку, устанавливаемому другим указателем, то такой список будет нелинейным.
Слайд 69Структуры данных
Нелинейные разветвленные списки
Схематичное представление разветвленного списка
Слайд 70Структуры данных
Нелинейные разветвленные списки
Разветвленные списки описываются тремя характеристиками:
порядком
глубиной
длиной.
Слайд 71Структуры данных
Нелинейные разветвленные списки
Порядок. Над элементами списка задано транзитивное
отношение, определяемое последовательностью, в которой элементы появляются внутри списка. В
списке (x,y,z) атом x предшествует y, а y предшествует z. При этом подразумевается, что x предшествует z.Данный список не эквивалентен списку (y,z,x). При представлении списков графическими схемами порядок определяется горизонтальными стрелками. Горизонтальные стрелки истолковываются следующим образом: элемент из которого исходит стрелка, предшествует элементу, на который она указывает.
Слайд 72Структуры данных
Нелинейные разветвленные списки
Глубина. Это максимальный уровень, приписываемый элементам
внутри списка или внутри любого подсписка в списке. Уровень элемента
предписывается вложенностью подсписков внутри списка, т.е. числом пар круглых скобок, окаймляющих элементДлина - число элементов уровня 1 в списке.
Слайд 73Структуры данных
Нелинейные разветвленные списки
Выражение:
(a+b)*(c-(d/e))+f
будет вычисляться
в следующем порядке:
a+b
d/e
c-(d/e)
(a+b)*(c-d/e)(a+b)*(c-d/e)+f
Глубина этого списка равна 4,
длина - 3.
Слайд 74Структуры данных
Нелинейные разветвленные списки
Представление списковых структур в памяти
Элементы списка
могут быть двух видов: атомы, содержащие данные и узлы, и
содержащие указатели на подсписки. В атомах не используется поле down элемента списка, а в узлах - поле data. Поэтому логичным является совмещение этих двух полей в одно:
Слайд 75Структуры данных
Нелинейные разветвленные списки
Поле type содержат признак атом/узел, оно
может быть 1-битовым. Такой формат элемента удобен для списков, атомарная
информация которых занимает небольшой объем памяти. В этом случае теряется незначительный объем памяти в элементах списка, для которых не требуется поля data. В более общем случае для атомарной информации необходим относительно большой объем памяти. Наиболее распространенный в данной ситуации формат структуры узла:
Слайд 76Структуры данных
Нелинейные разветвленные списки
Операции обработки списков
Базовыми операциями при обработке
списков являются операции (функции):
car,
cdr,
cons
atom.
Слайд 77Структуры данных
Нелинейные разветвленные списки
Операция car в качестве аргумента получает
список (указатель на начало списка). Ее возвращаемым значением является первый
элемент этого списка (указатель на первый элемент). Например:если X - список (2,6,4,7), то car(X) - атом 2;
если X - список ((1,2),6), то car(X) - список (1,2);
если X - атом то car(X) не имеет смысла и в действительности не определено.
Слайд 78Структуры данных
Нелинейные разветвленные списки
Операция cdr в качестве аргумента также
получает список. Ее возвращаемым значением является остаток списка - указатель
на список после удаления из него первого элемента. Например:если X - (2,6,4), то cdr(X) - (6,4);
если X - ((1,2),6,5), то cdr(X) - (6,5);
если список X содержит один элемент, то cdr(X) равно nil.
Слайд 79Структуры данных
Нелинейные разветвленные списки
Операция cons имеет два аргумента: указатель
на элемент списка и указатель на список. Операция включает аргумент-элемент
в начало аргумента-списка и возвращает указатель на получившийся список. Например:если X - 2, а Y - (6,4,7), то cons(X,Y) - (2,6,4,7);
если X - (1,2), Y - (6,4,7), то cons(X,Y) - ((1,2),6,4,7).
Слайд 80Структуры данных
Нелинейные разветвленные списки
Операция atom выполняет проверку типа элемента
списка. Она должна возвращать логическое значение: true - если ее
аргумент является атомом, или false - если ее аргумент является подсписком.
Слайд 81Структуры данных
ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ.
СВЯЗНЫЕ СПИСКИ
Тема 8:
Управление динамически выделяемой
памятью
Слайд 82Структуры данных
Управление динамически выделяемой памятью
Динамические структуры по определению характеризуются
непостоянством и непредсказуемостью размера. Поэтому память под отдельные элементы таких
структур выделяется в момент, когда они "начинают существовать" в процессе выполнения программы, а не во время трансляции. Когда в элементе структуры больше нет необходимости, занимаемая им память освобождается.
Слайд 83Структуры данных
Управление динамически выделяемой памятью
В общем случае при распределении
памяти должны быть решены следующие вопросы:
способ учета свободной памяти;
дисциплины выделения
памяти по запросу;обеспечение утилизации освобожденной памяти.
Слайд 84Структуры данных
Управление динамически выделяемой памятью
Память выделяется блоками.
Блоки могут
быть фиксированной или переменной длины.
Фиксированный размер блока гораздо удобнее
для управления: в этом случае вся доступная для распределения память разбивается на "кадры", размер каждого из которых равен размеру блока, и любой свободный кадр годится для удовлетворения любого запроса. К сожалению, лишь ограниченный круг реальных задач может быть сведен к блокам фиксированной длины.
Слайд 85Структуры данных
Управление динамически выделяемой памятью
Одной из проблем, которые должны
приниматься во внимание при управлении памятью, является проблема фрагментации (дробления)
памяти. Она заключается в возникновении "дыр" - участков памяти, которые не могут быть использованы. Различаются дыры внутренние и внешние.Внутренняя дыра - неиспользуемая часть выделенного блока, она возникает, если размер выделенного блока больше запрошенного. Внутренние дыры характерны для выделения памяти блоками фиксированной длины.
Внешняя дыра - свободный блок, который в принципе мог бы быть выделен, но размер его слишком мал для удовлетворения запроса. Внешние дыры характерны для выделения блоками переменной длины.
Слайд 86Структуры данных
1.Каковы особенности динамических структур данных?
2. Перечислите основные динамические структуры?
3.
Какие основные операции выполняются над динамическими структурами?
Контрольные вопросы
