САМОСТОЯТЕЛЬНАЯ РАБОТА-2
Студент: 2 - курс
Группа: ДИ-13-20
Подготовил: Д . Дустмуродов Принял: Р.АБДУЛЛАЕВ
Темы:
Полустатическая структура данных
Динамическая структура данных
Списки с кольцевой связъю
Линейная структура данных
Рекурсивные алгоритмы и их функции
Полустатическая структура данных
Свойства полустатических структур данных:
они имеют переменную длину и простые способы ее изменения;
изменени длины структуры происходит в определенных пределах, не превышая какого-то максимального (предельного) значения.
С логической точки зрения полустатическая структура представляет собой последовательность данных, связанную отношениями линейного списка. Доступ к элементу может осуществляться по его порядковому номеру.
Физически полустатические структуры представляются либо в виде вектора, т. е. располагаются в непрерывной области памяти, либо в виде однонаправленного связного списка где каждый следующий элемент адресуется указателем, находящимся в текущем элементе.
К полустатическим структурам относятся стеки, очереди, деки, строки.
Динамические структуры данных
Динамические структуры не имеют постоянного размера, поэтому память под отдельные элементы таких структур выделяется в момент, когда они создаются в процессе выполнения программы, а не во время трансляции. Когда в элементе структуры больше нет необходимости занимаемая им память освобождается (элемент «разрушается»)
С помощью связного представления данных обеспечивается высокая изменчивость структуры. Достоинства динамических структур:
размер структуры ограничивается только объемом памяти компьютера;
при изменении логической последовательности элементов структуры (удалении, добавлении элемента, изменении порядка следования элементов) требуется только коррекция указателей
Кольцевые списки
Списки могут быть не только линейными, но и кольцевыми. В кольцевом списке для последнего элемента следующим является первый, а если список двунаправленный, то для первого предыдущим является последний
Как и линейный, кольцевой список определяется указателем на свой первый элемент. Из процедур обработки кольцевого списка принципиально отличается от процедур линейного только просмотр списка.
Так, при просмотре линейного списка мы переходили от одного элемента к другому, пока рабочий указатель не стал равен Nil. При просмотре кольцевого списка, очевидно, надо переходить к следующему элементу до тех пор, пока рабочий указатель не совпадет с указателем на первый элемент. Однако, если мы начнем просмотр с первого элемента, то мы сразу же выйдем из цикла просмотра. Поэтому первый элемент должен обрабатываться отдельно, а просмотр при помощи цикла следует начинать со второго элемента. Итак, предположим, что элементы нашего кольцевого списка содержат числа.
Линейная структура данных
Линейные структуры — это упорядоченные структуры, в которых адрес элемента однозначно определяется его номером.
Линейных структуры данных обладают следующими свойствами:
Каждый элемент имеет не более 1 предшественника
Два разных элемента не могут иметь одинакового последователя
К линейным структурам данным можно отнести:
Массивы
Связный список
Стек
Очередь
Дек
Хэш-таблица
Рекурсивные алгоритмы и их функции
Рекурсия ( от латинского « recurso » - бегу назад, возвращаюсь) в сомом общем виде – это есть правило определения ( или построения ) некоторого объекта с использованием его же самого.
Рекурсивный алгоритм – это алгоритм, который в качестве выполняемых операций может использовать обращение к самому себе. Рекурсивные алгоритмы представляют собой особый интерес, поскольку зачастую являются более простым и изящным способом решения задачи, чем традиционные алгоритмы.
Do'stlaringiz bilan baham: |