👜22. Динамические структуры данных. Односвязный список, стек и очередь. Алгоритмы их обработки.

Динамические структуры данных - составные структуры данных, динамически меняющие свой размер во время выполнения программы.

Односвязный список

Однонаправленный (односвязный) список - динамическая структура данных, состоящая из узлов (Node). Каждый узел хранит значение и указатель на следующий узел. Последний узел хранит указатель на NULL.

// Пример реализации узла
struct Node {
    Book data;  //поле данных
    struct Node* next; //укзатель на следующий элемент
};

Доступные операции:

1. Создание списка

2. Добавление элемента в список

3. Удаление узла списка

4. Удаление всего списка

5. Операции обхода списка

Создание списка

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. Связать предыдущий элемент с новым

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. Очистить память от текущего

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);
}

Удаление корня списка

struct Node * deletehead(struct Node *root)
{
  struct Node *temp;
  temp = root->ptr;
  free(root); // освобождение памяти текущего корня
  return(temp); // новый корень списка
}

Стек

Стек - динамическая структура данных, организованная по принципу LIFO (Last in first out).

std::stack - реализация стека

#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 - очередь

#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;
}