1.Функциональные структуры данных – массив, запись

2. Рекурсивные структуры данных Граф-это математическая модель связи между объектом произвольной природы, представляющая собой набор точек на плоскости (величины графа) которые могут соединяться направленными и ненаправленными линиями(дуги или ребра графа).

Если ребра графа являются направленными, т.е. для каждой вершины можно указать какие ребра в нее входят и какие выходят, то граф называется ориентированным, если нет, то неориентированным. Граф называется связным, если любые его две вершины соединены путем.

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

3.Теоретико-множественные структуры данных.(ТМСД)

Основаны на математическом понятии множества. В математике под множеством понимается любое объединение в одно целое определенных и различных между собой объектов находящихся в определенных отношениях между собой или элементами других множеств

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

5. АТД «Список»: основные понятия, типы. Список-это ориентированный или неориентированный граф, в ту вершину в кот. входит 1 или 2 ребра. Список представлен набором однотипных элементов, связанные между собой при помощи ссылок .По количеству ссылок делятся на односвязные и двусвязные. Могут быть линейными(первая и последняя не связаны) и кольцевыми(первая и последняя связаны).Списки, которые позволяют избежать избыточного дублирования данных, называются ассоциативными.

6. Линейные списки. Описать алгоритм и написать пример функции создания списка.

typedef struct node

{

int data;

struct node *next;

} ITEM;

7. Линейные списки. Описать алгоритм и написать пример функции включения нового элемента в список. зависит от способа организации списка (отсортированный или нет), и правил добавления элементов (только в конец, только в начало, в определенное сортировкой место). В общем виде разделяется на следующие шаги: 1.Выделить память под новый элемент 2.Записать данные в элемент 3.Определить место вставки и вставить 4. Если список пуст, новый элемент становиться головным элементом списка

Если нужно вставить в начало списка, записать указатель на головной элемент в новый элемент, и новый элемент становиться головным

Если нужно вставить не в начало, тогда нужно найти элемент, после которого произвести вставку Prev и сделать 2 шага 1)записать в новый элемент указатель на следующий за Prev, 2) в элементе Prev изменить указатель на следующий элемент (записать адрес New_item)

Item* add_item(hitem *h, val, new_val)

{

ITEM *q=h->first, *new_item;

if ((new_item=(ITEM *)malloc(sizeof(ITEM)))=NULL);

return NULL;

new_item->val=new_val;

if(h->first=NULL)

{ h->first=new_item;

new_item->next=NULL;

}

else

{ while ((q->next->val<new_val) ιι (q->next=NULL));

if (q->val==new_val)

return NULL;

else

q=q->next;

new_item->next=q->next

q->next=new_item;

}

h->NULL++;

return new_item;

}

8. Линейные списки. Описать алгоритм и написать пример функции исключения элемента из списка существуют два варианта: Удаление первого элемента (головы), тогда новый --- головной элемент Удаление любого другого элемента, тогда нужно запомнить элемент расположенный за удаляемым и изменить его указатель на следующий.

Также необходимо освободить память, занимаемую удаляемым элементом, с помощью функции free, т.к. память выделялась в динамической области памяти с помощью функции malloc

int delete_item (HITEM *h,VAL, del_val)

{

ITEM *q, *p;

q=p=h->first

while (q->val != del_val)

}

p=q;

if ((q==NULL)ιι(q->val >del_val))

return 0;

q=q->next

}

p->next=q->next;

free(q);

h->NULL- -;

return 1;

}

9. Линейные списки. Описать алгоритм и написать пример функции поиска элемента в списке.

ITEM* find_node(ITEM* head, int find_data)

{

ITEM *cur;

cur=head;

while(cur!=NULL && cur->data<=find_data)

{

if(cur->data==find_data) {

printf("Элемент %d найден\n",find_data);

return cur;

}

cur=cur->next;

}

printf("Элемент %d НЕ найден \n",find_data);

return NULL;

}

10. Очередь — структура данных с дисциплиной доступа к элементам «первый пришёл — первый вышел»Добавление элемента возможно лишь в конец очереди, выборка — только из начала очереди, при этом выбранный элемент из очереди удаляется.

11.Стек - структура данных, в которой доступ к элементам организован по принципу LIFO (last in — first out, «последним пришёл — первым вышел»)

12. Дек - особый вид очереди. Дек (от англ. deq - double ended queue,т.е очередь с двумя концами) - это такой последовательный список, в котором как включение, так и исключение элементов может осуществляться с любого из двух концов списка. Частный случай дека - дек с ограниченным входом и дек с ограниченным выходом. Логическая и физическая структуры дека аналогичны логической и физической структуре кольцевой FIFO-очереди. Однако, применительно к деку целесообразно говорить не о начале и конце, а о левом и правом конце.Операции над деком:включение элемента справа;включение элемента слева;исключение элемента права;исключение элемента слева;определение размера;очистка.

13.Обратная польская запись: алгоритм ее составления.Если посмотреть внимательно, можно заметить, что операнды в постфиксной форме не меняют своего относительного расположения, а вот порядок следования операций и функций меняется как по отношению к операндам, так и по отношению друг к другу. Правила перевода следующие 1.Ввести в стек левую скобку '(' 2.Добавить в конец строки с инфиксным выражением правую скобку ')' 3.Пока стек не пуст, считываем символы из строки содержащей инфиксное выражение слева направо и выполняем следующие действия. a.Если текущий символ в инфиксной строке – левая скобка, помещаем ее в стек. b.Если текущий символ в инфиксной строке – правая скобка, извлекаем знаки операций из стека и вставляем их в результирующую строку, до тех пор пока на вершине стека не появиться левая скобка. Извлечь левую скобку и отбросить ее. c.Если текущий символ в инфиксной строке – знак операции, извлекаем знаки операций из стека (если они там есть), пока соответсвующее им операции имеют равный или более высокий приоритет по сравнению с текущей операцией, и вставляем извлеченные знаки операций в результирующую строку. Вставим текущий символ в стек. d.Если текущий символ в инфиксной строке – цифра, копируем его в результирующую строку.