- •1. Функциональные структуры данных.
- •2.Рекурсивные структуры данных.
- •3.Теоретико-множественные структуры данных.
- •4.Абстрактные типы данных.
- •5.Атд «Список»: основные понятия, типы.
- •6.Линейные списки. Описать алгоритм и написать пример функции создания списка.
- •7.Линейные списки. Описать алгоритм и написать пример функции включения нового элемента в список.
- •8.Линейные списки. Описать алгоритм и написать пример функции исключения элемента из списка.
- •9.Линейные списки. Описать алгоритм и написать пример функции поиска элемента в списке.
- •10.Понятие «очередь».
- •11.Понятие «стек».
- •12.Понятие «дек».
- •13.Обратная польская запись: алгоритм ее составления.
- •15.Двусвязные списки и их свойства.
- •16.Иерархические списки и их свойства.
- •17.Ассоциативные списки и их свойства.
- •18. Атд «Дерево»: основные понятия.
- •19.Двоичные деревья и их свойства.
- •20.Деревья двоичного поиска. Описать алгоритм и написать пример функции добавления узла в дерево.
- •21.Деревья двоичного поиска. Описать алгоритм и написать пример функции обхода узлов дерева.
- •22.Деревья двоичного поиска. Описать алгоритм и написать пример функции поиска узла по его метке.
- •23.Деревья двоичного поиска. Описать алгоритм и написать пример функции удаления узла дерева.
7.Линейные списки. Описать алгоритм и написать пример функции включения нового элемента в список.
В общем виде разделяется на следующие шаги:
Выделить память под новый элемент
Записать данные в элемент
Определить место вставки и вставить
Если список пуст, новый элемент становиться головным элементом списка.
Если нужно вставить в начало списка, записать указатель на головной элемент в новый элемент, и новый элемент становиться головным.
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.Линейные списки. Описать алгоритм и написать пример функции исключения элемента из списка.
При удалении существуют два варианта:
Удаление первого элемента (головы), тогда новый головной элемент.
Удаление любого другого элемента, тогда нужно запомнить элемент расположенный за удаляемым и изменить его указатель на следующий.
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* search_item(HITEM* h, VAL, search_val)
{
HITEM *q=h->first;
if ((q==NULL )ιι (q->val>search_val))
return NULL;
do { if(q->val==search_val)
return q;
q=q->next;
} while ((q!=NULL )&& (q->val>search_val));
return NULL;
}
10.Понятие «очередь».
Очередь – список, в котором новый элемент добавляется в конец списка, а удаляется только первый элемент.
«1-й ушел, 1-й пришел»
FIFO
(First Input
First Output)
Операции:
Выбор с одновременным удалением
Добавление нового элемента в конец очереди
Разновидность очереди – очередь с приоритетом (приоритет, определяющий элемент, который удалять).
11.Понятие «стек».
Стек (или магазин) представляет собой список, упорядоченный по времени поступления элементов таким образом, что извне доступен только последний из записанных в список элементов, который называется вершиной стека. Другими словами, стек функционирует по принципу «последним пришел - первым ушел».
Операции:
выборка с одновременным удалением вершины стека;
добавление нового элемента в вершину стека.
Объявление элемента стека.
typedef struct node
{
char el;
struct node *next;
} Stack;
Глобальная переменная – указатель на вершину стека.
Stack* Head=NULL;
Добавление в стек.
void Push(char element)
{
Stack *p;
p = (Stack*)malloc(sizeof(Stack));
if(p!=NULL)
{
p->el=element;
p->next=Head;
Head=p;
printf(“Push elem %c \n”,element);
}
else
{
puts(“Error! Not free memory!”);
}
}
Удаление из стека.
char Pop()
{
char a=Head->el;
Stack* p=Head;
Head=Head->next;
free(p);
printf(“Pop elem %c \n”,a);
return a;
}