списки стеки деки очереди в двух словах. Лекция 1. Программа компилятор
 Скачать 99.41 Kb.
|
|
Слайд 2 Динамические структуры данных – это структуры данных, память под которые выделяется и освобождается по мере необходимости. Динамические структуры данных в процессе существования в памяти могут изменять число составляющих их элементов, но и характер связей между элементами. При этом не учитывается изменение содержимого самих элементов данных. Такая особенность динамических структур, как непостоянство их размера и характера отношений между элементами, приводит к тому, что на этапе создания машинного кода программа-компилятор не может выделить для всей структуры в целом участок памяти фиксированного размера, а также не может сопоставить с отдельными компонентами структуры конкретные адреса. Для решения проблемы адресации динамических структур данных используется метод, называемый динамическим распределением памяти, то есть память под отдельные элементы выделяется в момент, когда они "начинают существовать" в процессе выполнения программы, а не во время компиляции. Компилятор в этом случае выделяет фиксированный объем памяти для хранения адреса динамически размещаемого элемента, а не самого элемента. Динамическая структура данных характеризуется тем что: она не имеет имени; ей выделяется память в процессе выполнения программы; количество элементов структуры может не фиксироваться; размерность структуры может меняться в процессе выполнения программы; в процессе выполнения программы может меняться характер взаимосвязи между элементами структуры. Слайд 3 Классификация динамических структур данных однонаправленные (односвязные) списки; двунаправленные (двусвязные) списки; циклические списки; стек; дек; очередь; бинарные деревья. Слайд 4 Однонаправленные (односвязные) списки Однонаправленный (односвязный) список – это структура данных, представляющая собой последовательность элементов, в каждом из которых хранится значение и указатель на следующий элемент списка. В последнем элементе указатель на следующий элемент равен NULL.  Слайд 5 Основными операциями, осуществляемыми с однонаправленными списками, являются: создание списка; печать (просмотр) списка; вставка элемента в список; удаление элемента из списка; поиск элемента в списке проверка пустоты списка; удаление списка. Слайд 6 Двунаправленные (двусвязные) списки Двунаправленный (двусвязный) список – это структура данных, состоящая из последовательности элементов, каждый из которых содержит информационную часть и два указателя на соседние элементы. При этом два соседних элемента должны содержать взаимные ссылки друг на друга.  Слайд 7 Основные операции, осуществляемые с двунаправленными списками: создание списка; печать (просмотр) списка; вставка элемента в список; удаление элемента из списка; поиск элемента в списке; проверка пустоты списка; удаление списка. Аналогично однонаправленному списку Слайд 8 |