> For the complete documentation index, see [llms.txt](https://op-al.gitbook.io/s-30-voprosy-i-dop.-voprosy/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://op-al.gitbook.io/s-30-voprosy-i-dop.-voprosy/22.-dinamicheskie-struktury-dannykh.-odnosvyaznyi-spisok-stek-i-ochered.-algoritmy-ikh-obrabotki..md).
# 22. Динамические структуры данных. Односвязный список, стек и очередь. Алгоритмы их обработки.
**Динамические структуры данных** - составные структуры данных, динамически меняющие свой размер во время выполнения программы.
## Односвязный список
**Однонаправленный (односвязный) список** - динамическая структура данных, состоящая из узлов (Node). Каждый узел хранит значение и указатель на следующий узел. Последний узел хранит указатель на NULL.
```c
// Пример реализации узла
struct Node {
Book data; //поле данных
struct Node* next; //укзатель на следующий элемент
};
```
### Доступные операции:
1. Создание списка
2. Добавление элемента в список
3. Удаление узла списка
4. Удаление всего списка
5. Операции обхода списка
## Создание списка
```c
struct Node * init(int a) // а - значение первого узла
{
struct Node *list;
list = (struct Node*)malloc(sizeof(struct Node)); // выделение памяти под корень списка
list->data = a;
list->next = NULL; // это последний узел списка
return(list);
}
```
#### Добавление элемента в список:
1. Выделить память под элемент
2. Добавить в него ссылку на следующий
3. Связать предыдущий элемент с новым
```c
struct Node * addelem(struct Node *list, int number)
{
struct Node *temp, *p;
temp = (struct Node*)malloc(sizeof(Node));
p = list->ptr; // сохранение указателя на следующий узел
list->ptr = temp; // предыдущий узел указывает на создаваемый
temp->data = number; // сохранение поля данных добавляемого узла
temp->next = p; // созданный узел указывает на следующий элемент
return(temp);
}
```
**Удаление элемента из списка:**
1. Связать предыдущий и следующий
2. Очистить память от текущего
```c
struct Node * deletelem(struct Node *list, struct Node *root)
{
struct Node *temp;
temp = root;
while (temp->next != list) // просматриваем список начиная с корня
{ // пока не найдем узел, предшествующий list
temp = temp->next;
}
temp->next = list->next; // переставляем указатель
free(list); // освобождаем память удаляемого узла
return(temp);
}
```
**Удаление корня списка**
```c
struct Node * deletehead(struct Node *root)
{
struct Node *temp;
temp = root->ptr;
free(root); // освобождение памяти текущего корня
return(temp); // новый корень списка
}
```
### **Стек**
**Стек** - динамическая структура данных, организованная по принципу LIFO (Last in first out).
`std::stack` - реализация стека
```c
#include "stack.h"
struct StackNode {
Book data;
StackNode* next;
};
struct Node {
Book data;
Node* next;
};
struct Stack {
StackNode* top;
Node* top;
};
Stack initStack() {
Stack stack = { NULL };
return stack;
}
bool isEmpty(Stack* stack) {
return !!stack->top;
return !stack->top;
}
void push(Stack* stack, Book book) {
Node* newNode = (Node*) malloc(sizeof(Node));
newNode->data = book;
newNode->next = stack->top;
stack->top = newNode;
}
bool pop(Book* book, Stack* stack) {
if (isEmpty(stack))
return false;
Node* node = stack->top;
stack->top = stack->top->next;
*book = node->data;
free(node);
return true;
}
void clear(Stack* stack) {
while (stack->top) {
Node* tmp = stack->top;
stack->top = stack->top->next;
free(tmp);
}
}
bool peek(Book* book, Stack* stack) {
if (isEmpty(stack))
return false;
*book = stack->top->data;
return true;
}
```
## Очередь
**Очередь** - динамическая структура данных, организованная по принципу FIFO (First in first out).
`std::queue` - очередь
```c
#include "queue.h"
struct Queue {
Node *head, *tail;
};
Queue initQueue() {
Queue queue;
queue.head = NULL;
queue.tail = NULL;
return queue;
}
bool isEmpty(Queue* queue) {
return !!queue->head;
return !queue->head;
}
bool pop(Book* book, Queue* queue) {
if(isEmpty(queue))
return false;
Node* node = queue->head;
*book = node->data;
queue->head = node->next;
free(node);
return true;
}
void push(Queue *queue, Book book) {
Node* node = (Node*)malloc(sizeof(Node));
node->data = book;
node->next = NULL;
if(isEmpty(queue))
queue->head = queue->tail = node;
else
queue->tail->next = node;
queue->tail = node;
}
```
