Самостоятельная работа-2 Студент: 2 курс Группа: ди-13-20

САМОСТОЯТЕЛЬНАЯ РАБОТА-2


Студент: 2 - курс
Группа: ДИ-13-20
Подготовил: Д . Дустмуродов Принял: Р.АБДУЛЛАЕВ

Темы:

• 
  Полустатическая структура данных
  
• 
  Динамическая структура данных
  
• 
  Списки с кольцевой связъю
  
• 
  Линейная структура данных
  
• 
  Рекурсивные алгоритмы и их функции
  

Полустатическая структура данных

Свойства полустатических структур данных:

• 
  они имеют переменную длину и простые способы ее изменения;
  
• 
  изменени длины структуры происходит в определенных пределах, не превышая какого-то максимального (предельного) значения.
  

• 
  С логической точки зрения полустатическая структура представляет собой последовательность данных, связанную отношениями линейного списка. Доступ к элементу может осуществляться по его порядковому номеру.
  
• 
  Физически полустатические структуры представляются либо в виде вектора, т. е. располагаются в непрерывной области памяти, либо в виде однонаправленного связного списка где каждый следующий элемент адресуется указателем, находящимся в текущем элементе.
  
• 
  К полустатическим структурам относятся стеки, очереди, деки, строки.
  

Динамические структуры данных

• 
  Динамические структуры не имеют постоянного размера, поэтому память под отдельные элементы таких структур выделяется в момент, когда они создаются в процессе выполнения программы, а не во время трансляции. Когда в элементе структуры больше нет необходимости занимаемая им память освобождается (элемент «разрушается»)
  

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

• 
  размер структуры ограничивается только объемом памяти компьютера;
  
• 
  при изменении логической последовательности элементов структуры (удалении, добавлении элемента, изменении порядка следования элементов) требуется только коррекция указателей
  

Кольцевые списки
Списки могут быть не только линейными, но и кольцевыми. В кольцевом списке для последнего элемента следующим является первый, а если список двунаправленный, то для первого предыду­щим является последний

Как и линейный, кольцевой список определяется указателем на свой первый элемент. Из процедур обработки кольцевого списка принципиально от­личается от процедур линейного только просмотр списка.

Так, при просмотре линейного списка мы переходили от одного элемента к другому, пока рабочий указатель не стал равен Nil. При просмотре кольцевого списка, очевидно, надо переходить к следующему эле­менту до тех пор, пока рабочий указатель не совпадет с указателем на первый элемент. Однако, если мы начнем просмотр с первого элемента, то мы сразу же выйдем из цикла просмотра. Поэтому пер­вый элемент должен обрабатываться отдельно, а просмотр при по­мощи цикла следует начинать со второго элемента. Итак, предположим, что элементы нашего кольцевого списка содержат числа.
Линейная структура данных
Линейные структуры — это упорядоченные структуры, в которых адрес элемента однозначно определяется его номером.
Линейных структуры данных обладают следующими свойствами:

• 
  Каждый элемент имеет не более 1 предшественника
  
• 
  Два разных элемента не могут иметь одинакового последователя
  

К линейным структурам данным можно отнести:

• 
  Массивы
  
  • 
    Динамические массивы
    
• 
  Связный список
  
• 
  Стек
  
• 
  Очередь
  
• 
  Дек
  
• 
  Хэш-таблица
  

Рекурсивные алгоритмы и их функции

• 
  Рекурсия ( от латинского « recurso » - бегу назад, возвращаюсь) в сомом общем виде – это есть правило определения ( или построения ) некоторого объекта с использованием его же самого.
  

• 
  Рекурсивный алгоритм – это алгоритм, который в качестве выполняемых операций может использовать обращение к самому себе. Рекурсивные алгоритмы представляют собой особый интерес, поскольку зачастую являются более простым и изящным способом решения задачи, чем традиционные алгоритмы.