- •1. Функциональные структуры данных.
- •2.Рекурсивные структуры данных.
- •3.Теоретико-множественные структуры данных.
- •4.Абстрактные типы данных.
- •5.Атд «Список»: основные понятия, типы.
- •6.Линейные списки. Описать алгоритм и написать пример функции создания списка.
- •7.Линейные списки. Описать алгоритм и написать пример функции включения нового элемента в список.
- •8.Линейные списки. Описать алгоритм и написать пример функции исключения элемента из списка.
- •9.Линейные списки. Описать алгоритм и написать пример функции поиска элемента в списке.
- •10.Понятие «очередь».
- •11.Понятие «стек».
- •12.Понятие «дек».
- •13.Обратная польская запись: алгоритм ее составления.
- •15.Двусвязные списки и их свойства.
- •16.Иерархические списки и их свойства.
- •17.Ассоциативные списки и их свойства.
- •18. Атд «Дерево»: основные понятия.
- •19.Двоичные деревья и их свойства.
- •20.Деревья двоичного поиска. Описать алгоритм и написать пример функции добавления узла в дерево.
- •21.Деревья двоичного поиска. Описать алгоритм и написать пример функции обхода узлов дерева.
- •22.Деревья двоичного поиска. Описать алгоритм и написать пример функции поиска узла по его метке.
- •23.Деревья двоичного поиска. Описать алгоритм и написать пример функции удаления узла дерева.
1. Функциональные структуры данных.
Структуры данных – сложные данные, построенные из более простых или элементарных данных, объединенных с помощью определенных языковых конструкций.
Функциональные структуры данных – массив.
2.Рекурсивные структуры данных.
Структуры данных – сложные данные, построенные из более простых или элементарных данных, объединенных с помощью определенных языковых конструкций.
Рекурсивные структуры данных – списковые стандартные деревья, деревья, сетевые и фреймовые деревья.
3.Теоретико-множественные структуры данных.
Структуры данных – сложные данные, построенные из более простых или элементарных данных, объединенных с помощью определенных языковых конструкций.
Теоретико-множественные структуры данных основаны на математическом множестве.
4.Абстрактные типы данных.
Абстрактные типы данных – типы данных рассматр. независимо от способов его представления или реализации средствами языка программирования. Представляют собой математическую модель взаимосвязи некоторых объектов предметной области с определенными операциями.
5.Атд «Список»: основные понятия, типы.
Список – набор однотипных элементов связанных друг с другом по средствам ссылок.
Списки:
односвязные (одна ссылка)
двусвязные (две ссылки)
Они могут быть линейными (1-й и последующие элементы не связаны) и кольцевыми (могут ссылаться друг на друга).
Существуют иерархические списки (список списков).
Совокупность списков создаются на базе одного общего набора записей – информационная сеть.
Список:
информационная часть (обязательно)
ссылочная часть (обязательно)
справочная часть (не обязательно)
В начале располагается головной элемент, в котором находятся сведенья о списке в целом и ссылка на первый элемент списка.
Основные операции:
поиск элемента
включение нового элемента
исключение элемента.
6.Линейные списки. Описать алгоритм и написать пример функции создания списка.
Например, структура может быть реализована в виде
typedef struct node
{
int data;
struct node *next;
} ITEM;
*typedef – деректива определения типа (используется для задание более коротких имен типов), т.е. struct node теперь тоже, что и ITEM.
Пустой список – только 1 головной элемент. Чтобы его создать нужно создать головной элемент и пустую ссылку.
HITEM *Emplist ()
{
HITEM *head=NULL;
head=( HITEM *) malloc ()
sizeof (HITEM)
If (head!=NULL)
{
head->NULL=0;
head->first=NULL
}
return head:
}