# 1-3 вопрос: Общее представление о типах данных

## 1 вопрос: Уровни описания структур данных
Методичка (страница 203)

Тип данных - это множество значений и операций, определенных над этими значениями (IEEE Std 1320.2-1998).

### Уровни описания структур

При описании какого-либо объекта полезно разделять его абстрактные свойства и их конкретную реализацию, связанную с языком программирования, операционной системой и прочими особенностями среды. В данном курсе будут рассматриваться *функциональная спецификация*, *логическое описание* и *физическое представление* типов данных.

#### Функциональная спецификация

**Функциональная спецификация** - это описание типа данных без привязки к конкретной его реализации. Оно включает в себя множество значений этого типа, методы их интерпретации, его атрибуты и связанные с ним функции, операции, отношения и прочее. Короче говоря, функциональная спецификация - это ответ на вопросы: "Что такое объект типа?" и "Что с ним можно делать?".

#### Логическое описание

**Логическое описание** - это реализация функциональной спецификации типа на выбранном языке программирования. Здесь возможны две ситуации:

1. Тип данных встроен в выбранный язык программирования. Тогда его непосредстенная реализация программистом не требуется.
2. Тип данных в язык не встроен. В таком случае его необходимо реализовать средствами данного языка.

#### Физическое представление

Так как один и тот же тип данных может быть представлен в памяти по-разному, возникает необходимость соответствующего описания.

**Физическое представление** - это отображение объекта типа данных на память рабочей машины в соответсвтии с логическим описанием.

Привычная нам память, представляющая из себя упорядоченный и пронумерованный набор машинных слов, обуславливает два вида физического представления типов данных в памяти:

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

## 2 вопрос: Статические и динамические объекты программ

Методичка (страница 197)

Тута есть два понятия статики и динамики, одно описывает свойства объектов в общем, другое дает характеристику именно памяти, выделяемой под объект.

Свойство объекта, которое не изменяется в ходе исполнения программы, называется *статическим*, а то, которое может быть изменено - *динамическим*. Распределение этой характеристики по свойствам зависит от языка. Например, в таких языках как Basic, Lisp, Python, любая характеристика, начиная от значения, заканчивая типом объекта, может быть изменена в ходе исполнения. С другой стороны, в таких языках как C, C++, Rust, все объекты обладают статическим типом, некоторые обладают статическим значением (константы) или объемом выделенной памяти (статические массивы).

**Статическими** объектами принято называть сущности, память которых выделяется при их объявлении и после остается неизменной. **Динамическими** же объектами принято называть сущности, память которых может быть изменена в ходе исполнения программы (например, при объявлении память может и не быть выделена, затем аллоцирована,а,а,)

## 3 вопрос: Ссылочный тип данных

Методичка (страница 196)

Мне не нравится такое определение, потому что в разных языках определение "ссылки" может содержать в себе разные очень важные детали. Т.к. мой основной язык программирования - C++, под "ссылочном типом", о котором говориться в методичке, я привык понимать как раз указатели, а не ссылки, но раз В.Е. решил предоставить нам определение под таким названием, будем послушно ему следовать.

(Ребят, вы все знаете, что такое ссылка, просто напишите это грамотно)

Итак, опишем ссылки *функциональной спецификацией*.

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

Присвоение значения объекту ссылочного типа можно интерпретировать разными способами. Это может быть аллокация памяти, итерация по объекту, приведение типов и прочее (может быть, я что-то упустил. Дополните, если изволите).

# 4-5 вопрос: Файл как тип данных
## 4 вопрос. Файл. Функциональная спецификация.
### Файл.

Динамические объекты могут размещаться не только в основной, но и во внешней памяти ЭВМ. Динамические объекты, размещаемые на устройствах внешней памяти, обычно имеют структуру классического последовательного файла-картотеки или массива. Файл может быть пустым; количество составляющих его компонент может меняться в процессе выполнения программы. Важно, чтобы имя файла и его характеристики должны быть известны операционной системе до начала выполнения программы обработки этого файла.

Операции, которые вычислительная система может выполнять над файлами, определяются принципами, заложенными в конструкции тех устройств памяти, на которых эти файлы хранятся. Например, для файлов, хранящихся на МЛ и МД, определены чтение, запись и стирание; для пpинтеpа — только запись, а для CD-ROM и сканеpа — только чтение.

Слово «файл» в языке Паскаль употребляется для динамических объектов, состоящих из последовательности компонент одного типа. В любой момент непосредственно доступна только одна текущая компонента. Другие компоненты становятся доступными по мере продвижения по файлу. Длина файла (число компонент) не фиксируется.

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

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

Концепция файлов Си более общая, чем в Паскале. Наряду с традиционными файлами в Си файлами являются стандартные потоки(stdin, stdout, stderr), конвейеры, физические устройства вроде принтеров или датчиков температуры процессора. В Си есть функция быстрого подвода к нужному месту файла. Работа с файлами в Си организована на процедурном уровне. Возможно создание, переименование, удаление постоянных и временных файлов, имена которых задаются строковыми константами или переменными. В отличие от Паскаля каждый файл в Си может быть открыт и использован как в текстовом, так и в двоичном режимах.

### Функциональная спецификация.

Обозначим через $F_T$ файловый тип с компонентами типа $T$. Для задания функциональной спецификации файлового типа необходимо, во-первых, указать множество значений, множество изображений значений этого типа, правила интерпретации изображений и, во-вторых, определить базовое множество атрибутов этого типа (множество операций над значениями этого типа и их свойства, множество отношений и их свойства, выделенные функции и т. п.). Значениями типа $F_T$ являются сколь угодно длинные, но конечные последовательности компонент типа $T$ (изображаемые по правилам интерпретации типа компонент $T$). Такое бесконечное множество значений можно определить формально с помощью операции конкатенации (слияния) двух файлов, состоящих из компонент одного и того же типа: если $f_1=\{x_1,...,x_m\}$ и $f_2 = \{y_1,...,y_n\}$, то $f_1 \parallel f_2 = \{x_1, . . . , x_m, y_1, . . . , y_n\}$, где $\parallel$ — знак операции конкатенации.

Тогда **множество значений** файлового типа строго определяется следующими порождающими правилами:
1. {} есть файл типа $F_T$ (пустая последовательность, пустой файл);
2. если $f$ есть файл типа $F_T$ и $t$ есть объект типа $T$, то $f \parallel \{t\}$ есть файл типа $F_T$;
3. никакие другие значения не являются файлами типа $F_T$.

Базовое **множество атрибутов** файлового типа:
1. операция конкатенации, определенная выше; ее свойство — несимметричность;
2. операция присваивания определяется как покомпонентное копирование одного файла в другой с сохранением порядка и количества компонент.
3. отношение равенства: два файла, состоящие из компонент одного и того же типа, равны тогда и только тогда, когда они имеют одинаковую длину, а их соответствующие компоненты — равные значения; отношение равенства симметрично;
4. функции: создание, доступ (последовательный доступ к каждой компоненте, причем только для чтения значения: чтобы прочитать значение k-той компоненты файла, надо прочитать предварительно k − 1 компоненту от начала файла), модификация (дозапись компоненты того же типа в конец файла — фактически это конкатенация файла и новой компоненты типа $T$), уничтожение файла.

## 5 вопрос. Файл. Логическое описание. Физическое представление.

Почти вся глава в методичке посвящена файлам в Паскале, мотивация чего мне абсолютно непонятна. 
Но, предвкушая всякие выкрутасы на судном дне, вот, собственно, дайджест...

В Паскаль-программе может быть использован именованный и неименованный файловый тип. Именованный файловый тип должен быть описан в разделе описания типов:

type Т =. . . ;{тип компоненты файла}
<имя файлового типа> = file of Т;
Тогда объект-файл должен быть описан в разделе переменных таким образом:

var <имя объекта−файла> : <имя файлового типа >;
При использовании неименованного файлового типа описание такого же объекта выглядит следующим образом:

var <имя файловой переменной> : file of Т;
При обработке описания объекта-файла f транслятор должен выделить память в генерируемой программе под буфер файла, достаточную для размещения значения одной компоненты этого файла (тем самым порождая буферную переменную типа Т). Создание и модификацию файла можно реализовать в Паскаль-программе, используя стандартную функцию eof(f) и процедуры reset(f), rewrite(f), get(f) и put(f), где f имя файла. Встроенная операции присваивания, конкатенации, отношение равенства файлов в Паскале не реализованы. Пополнение файла новой компонентой является конкатенацией файла и переменной того же типа T, что и компоненты файла, и осуществляется с помощью стандартной процедуры put(f).

Наконец, Си...

Для описания файла в Си необходимо объявить переменную предопределённого типа FILE∗. Созданный компилятором виртуальный файловый дескриптор может быть динамически связан с конкретным файлом, потоком или устройством с помощью функций
стандартной библиотеки языка Си.

FILE* <имя объекта-файла>;
Файлового типа в Си нет. Для работы с файлами в стандартной библиотеке Си имеются определения файловых дескрипторов и функций, доступных через заголовочный файл <stdio.h>. Вместо описания файловой переменной в Си необходимо определить переменную-дескриптор файла, которая является ссылкой на файл. Далее Си позволяет сопоставить этому дескриптору существующий либо вновь создаваемый реальный файл, установить режимы доступа (чтение, запись, перезапись и др.), задать
формат и типизацию (интерпретацию) данных файла. Набор функций работы с файлами в Си гораздо более развит, чем в Паскале.

Теперь не из методички для понимания

**Файлы в Си**
Открытый файл представляется как последовательность считываемых или записываемых данных. При открытии файла с ним связывается поток ввода-вывода. Выводимая информация записывается в поток, вводимая информация считывается из потока.

Когда поток открывается для ввода-вывода, он связывается со стандартной структурой типа FILE, которая определена в stdio.h. Структура FILE содержит необходимую информацию о файле.

Открытие файла осуществляется с помощью функции **fopen()**, которая возвращает указатель на структуру типа FILE, который можно использовать для последующих операций с файлом.

FILE *fopen(name, type);

name – имя открываемого файла (включая путь),
type — указатель на строку символов, определяющих способ доступа к файлу:
"r" — открыть файл для чтения (файл должен существовать);
"w" — открыть пустой файл для записи; если файл существует, то его содержимое теряется;
"a" — открыть файл для записи в конец (для добавления); файл создается, если он не существует;
"r+" — открыть файл для чтения и записи (файл должен существовать);
"w+" — открыть пустой файл для чтения и записи; если файл существует, то его содержимое теряется;
"a+" — открыть файл для чтения и дополнения, если файл не существует, то он создаётся.

Возвращаемое значение — указатель на открытый поток. Если обнаружена ошибка, то возвращается значение NULL.

Функция **fclose()** закрывает поток или потоки, связанные с открытыми при помощи функции fopen() файлами. Закрываемый поток определяется аргументом функции fclose(). Возвращаемое значение: значение 0, если поток успешно закрыт; константа EOF, если произошла ошибка.

Чтение символа из файла:

char fgetc(поток);

Аргументом функции является указатель на поток типа FILE. Функция возвращает код считанного символа. Если достигнут конец файла или возникла ошибка, возвращается константа EOF.

Запись символа в файл:

fputc(символ,поток);
Аргументами функции являются символ и указатель на поток типа FILE. Функция возвращает код считанного символа.

Функции **fscanf()** и **fprintf()** аналогичны функциям scanf() и printf(), но работают с файлами данных, и имеют первый аргумент — указатель на файл.

fscanf(поток, "ФорматВвода", аргументы);

fprintf(поток, "ФорматВывода", аргументы);

Функции **fgets()** и **fputs()** предназначены для ввода-вывода строк, они являются аналогами функций gets() и puts() для работы с файлами.

fgets(Указатель На Строку, Количество Символов, поток);

Символы читаются из потока до тех пор, пока не будет прочитан символ новой строки ‘\n’, который включается в строку, или пока не наступит конец потока EOF или не будет прочитано максимальное количество символов. Результат помещается в указатель на строку и заканчивается нуль-символом ‘\0’. Функция возвращает адрес строки.

fputs(Указатель На Строку, поток);

Копирует строку в поток с текущей позиции. Завершающий нуль-символ не копируется.

# 6 вопрос: Вектор. Функциональная спецификация. Логическое описание и физическое представление
## Определение
Вектор является последовательностью переменной длины, и время доступа к элементам этой последовательности постоянно и не зависит от длины последовательности. Количество элементов вектора не фиксировано и всегда может быть изменено. Вектор с 0 компонент называется пустым.
## Функциональная спецификация
Пусть компоненты вектора имеют тип T. Тогда для типа $V_{T,I_n}$ ($I_n$ - множество допустимых индексов вектора) опеределены следующие операции:

## Логическое описание и физическое представление

// тип элементов стека задан через макрос Т, чтобы 
// было похоже на функциональную спецификацию
#include <stdbool.h>
#define T int

typedef struct{
    T* data;
    int size;
} vector;

void vector_create(vector* v, int sz) {
    v->size = sz;
    v->data = malloc(sizeof(T) * v->size);
}

bool vector_is_empty(vector* v) {
    return v->size == 0;
}

int vector_size(vector* v) {
    return v->size;
}

T vector_load(vector* v, int i){
    if ((i >= 0) && (i < v->size)){
        return v->data[i];
    }
}

void vector_save(vector* v, int i, T t) {
    if ((i >= 0) && (i < v->size)){
        v->data[i] = t;
    }
}
 
void vector_resize(vector* v, int sz){
    v->size = sz;
    v->data = realloc(v->data, sizeof(T) * v->size);
}

bool vector_equal(vector* l, vector* r){
    if (l->size != r->size){
        return false;
    }
    for (int i = 0; i< l->size; i++){
        if (l->data[i] != r->data[i]){
            return false;
        }
    }
    return true;
}

void vector_destroy(vector* v){
    v->size = 0;
    free(v->data);
}

# 7 вопрос: Очередь. Функциональная спецификация
## Определение
Очередь - упорядоченный, одномерный, динамически изменяемый набор компонент, в котором включение новых компонент производится на одном конце набора, а всякий доступ к компонентам и их исключение (удаление обработанной
компоненты) на другом конце.
## Функциональная спецификация
Тип $Q_Т$ (очередь объектов типа Т) характеризуется следующими операциями:
Перечисленные операции имеют следующие свойства ($\forall t \in T$ и $\forall q \in Q_T$):

# 8 вопрос: Очередь. Логическое описание и физическое представление (файл).

#include <stdbool.h>
#include <stdio.h>

#define T int

// Очередь на файле

typedef struct {
    char* file_path; // 
    int size;
} file_queue;

void file_queue_create(file_queue* fq, char* file_path) {
    fopen(file_path, "w+");
    fq->size = 0;
    fq->file_path = file_path;
}

bool file_queue_is_empty(file_queue* fq) {
    return fq->size == 0;
}

void file_queue_push(file_queue* fq, T t) {
    FILE* f = fopen(fq->file_path, "a");
    fprintf(f, "%d\n", t); // Формат ввода стоит для типа int
    fq->size++;
    fclose(f);
}

void file_queue_pop(file_queue* fq) {
    FILE* queue_file = fopen(fq->file_path, "r");
    FILE* temp_file = fopen("temp", "w");
    
    T t;
    fscanf(queue_file, "%d", &t);
    for (int i = 1; i < fq->size; i++) {
        fscanf(queue_file, "%d", &t);
        fprintf(temp_file, "%d\n", t);
    }
    
    fclose(queue_file);
    fclose(temp_file);
    
    rename("temp", fq->file_path)

    fq->size--;
}

T file_queue_top(file_queue* fq) {
    FILE* f = fopen(fq->file_path, "r");
    T t;
    fscanf(f, "%d", &t);
    fclose(f);
    return t;
}

int file_queue_size(file_queue* fq) {
    return fq->size;
}

void file_queue_destroy(file_queue* fq) {
    remove(fq->file_path);
    fq->size = 0;
    fq->file_path = NULL;
}

# 9 вопрос: Очередь. Логическое описание и физическое представление (массив)
## Логическое описание и физическое представление
При реализации очереди на массиве необходимо зафиксировать размер этого массива, ограничив тем самым максимальную длину очереди. В каждый конкретный момент времени очередь будет представлена сплошным участком массива. Введем две индексные переменные: первую - для индекса начала очереди («голова»), вторую - для индекса первого свободного элемента массива после последнего элемента очереди («хвост»: наш хвост не является частью тела).

Рассмотрим три стратегии отображения очереди на массив:
1. **Стратегия трудоголика**
При такой стратегии голова очереди фиксируется на первом элементе массива. Хвост очереди подвижен, поэтому время постановки элемента в очередь постоянно и невелико О(1). При извлечении элемента из очереди оставшиеся компоненты сдвигаются к началу массива. Цена этой операции довольно велика и пропорциональна ее длине О(N). Нигде не применяется.

2. **Ленивая стратегия**
При такой стратегии голова, и хвост очереди подвижны. Извлечение элемента из очереди занимает постоянное время. Постановка в очередь осуществляется так: если хвост указывает на свободный элемент массива, то туда записывается новая компонента очереди. В противном случае, когда хвост упирается в конец массива, делается попытка воспользоваться свободным местом в начале массива, освобожденным ушедшими из очереди элементами (примитивная сборка мусора). В случае успеха вся очередь копируется в начало массива, после чего добавляется элемент. При малой длине очереди постановка в очередь в среднем занимает постоянное время. Если же длина очереди близка к размеру массива и время выполнения этой операции приближается к O(N). Грамотные программисты ее также не используют.
3. **Стратегия с кольцевым буфером**
Обобщение ленивой стратегии. Перемещения очереди в массиве не бывает никогда. Склеивая начало массива с его концом (с помощью операции mod, отбрасывающей нас от конца массива к его началу, мы получаем возможность неограниченного поступательного движения вперед по буферу). При использовании кольцевого буфера как только одна из переменных-индексов подходит к концу массива, ее скачкообразно переустанавливают на начало массива, на освобожденное ушедшими из очереди элементами место. При такой стратегии и постановка, и извлечение из очереди занимают постоянное и очень небольшое время О(1). В отличие от предыдущих схем кольцевая буферизация является «экологически чистой» и не требует сборки мусора. И сама очередь, и свободная память образуют сплошные куски буферного массива (по модулю N), между началом и концом которых мигрируют освобождаемые и занимаемые элементы.

Итак, зафиксируем размер массива-буфера и обозначим его POOL_SIZE. Пусть в переменной $first$ хранится идекс головы очереди, в переменной $size$ - её длина. Зная это, легко указать на хвост очереди.

// тип элементов задан через макрос Т, чтобы 
// было похоже на функциональную спецификацию
#include <stdbool.h>
#define T int
const int POOL_SIZE = 100;

typedef struct{
    T* data[POOL_SIZE];
    int size;
    int first;
} queue;

void queue_create(queue* q) {
    q->first = 0;
    q->size = 0;
}

bool queue_is_empty(queue* q) {
    return q->size == 0;
}

int queue_size(queue* q) {
    return q->size;
}
 
bool queue_push(queue* q, const T t){
    if (q->size == POOL_SIZE){
        return false;
    }
    q->data[(q->first + q->size) % POOL_SIZE] = t;
    return true;
}

bool queue_pop(queue* q){
    if (q->size == 0){
        return false;
    }
    q->first++;
    q->first %= POOL_SIZE;
    q->size--;
    return true;
}

T queue_top(const queue* q){
    if (q->size){
        return q->data[q->first];
    }
}

# 10 вопрос: Очередь. Логическое описание и физическое представление (динамическиe объекты).
## Логическое описание и физическое представление
Свяжем ссылками одиночные элементы очереди в цепочку в том порядке, в котором они должны находиться в очереди. Для этого заведем комбинированный тип «элемент очереди», где наряду с полем данных предусмотрим переменную-ссылку на следующий
элемент того же типа.

struct Item{
    T data;
    struct Item* next;
}

Реализуем тип очередь на динамических структурах. Во-первых, понадобится ссылка на начало очереди. Чтобы обеспечить выполнение операции постановки в очередь за постоянное время, необходимо дополнительно завести ссылку на конец очереди. В противном случае цена вставки элемента в очередь повышается до неприемлемого O(N).Чтобы удешевить подсчет длины очереди с O(N) до O(1) применим неклассический подход, включив в представление очереди переменную size - длину очереди; актуализация ее значения возлагается на операции модификации.

Хвостом будет служить пустой служебный элемент - терминатор. Для его хранения потребуется дополнительный элемент, но это оправдано простотой реализаций всех функций для работы с очередью. Терминатор очереди не хранит никакого значения и не может быть прочитан из очереди либо разыменован для получения хранимого элемента. Поэтому важен не сам терминатор, а ссылка на него, которая завершает очередь

// тип элементов стека задан через макрос Т, чтобы 
// было похоже на функциональную спецификацию
#include <stdbool.h>
#define T int

struct Item{
    T data;
    struct Item* next;
}

const int POOL_SIZE = 100;

typedef struct{
    struct Item* first;
    struct Item* last;
    int size;
} queue;

void queue_create(queue* q) {
    q->first = q->last = malloc(sizeof(struct Item));
    q->size = 0;
}

bool queue_is_empty(queue* q) {
    return q->first == q->last;
}

int queue_size(queue* q) {
    return q->size;
}

bool queue_push(queue* q, const T t){
    if (!q->last->next = malloc(sizeof(struct Item))){
        return false;
    }
    q->last->data = t;
    q->last = q->last->next;
    q->size++;
    return true;
}

bool queue_pop(queue* q){
    if (q->first == q->last){
        return false;
    }
    struct Item* pi = q->first;
    q->first = q->first->next;
    q->size--;
    free(pi);
    return true;
}

T queue_top(const queue* q){
    if (q->first != q->last){
        return q->first->data;
    }
}

void queue_destroy(queue* q){
    while(!Empty(p)){
        struct Item* pi = q->first;
        q->first = q->first->next;
        free(pi);
    }
    free(q->first);
    q->first = q->last = 0;
    q->size = 0;
}

# 11 вопрос: Дек. Описание. Примеры задач.
## Определение
Дек - двухсторонняя очередь, динамическая структура данных, в которой элементы можно добавлять и удалять как в начало, так и в конец.

Оперции над деком:
- включение элемента справа;
- включение элемента слева;
- исключение элемента справа;
- исключение элемента слева;
- определение размера;
- очистка.

Физическая структура дека в статической памяти идентична струкутере кольцевой очереди. Динамическая реализация является очевидным объёдинением стека и очереди.

## Реализация (из методички)

typedef struct Item {
    int data; // хранимое значение
    struct Item* next; // указатель на следующий элемент
    struct Item* prev; // указатель на предыдущий элемент
} Item;

typedef struct deque {
    Item* left; // указатель на левый конец дека
    Item* right; // указательн на правый конец дека
    int size; // размер дека
} deque;

deque* CreateDeque(vector* v); // создание дека из вектора
bool IsEmptyDeque(deque* d); // проверка отсутсвия элементов в деке

bool PushLeftDeque(deque* d, int i); // добавить элемент с левого конца
bool PushRightDeque(deque* d, int i); // добавить элемент с правого конца

bool PopLeftDeque(deque* d); // взять элемент с левого конца
bool PopRightReque(deque* d); // взять элемент с правого конца

int TopLeftDeque(deque* d); // посмотреть элемент с левого конца
int TopRigthReque(deque* d); // посмотреть элемент с правого конца

bool DeleteDeque(deque* d); // очистить дек

deque* CreateDeque(vector* v) {
    deque* d = (deque*)malloc(sizeof(deque));
    d->size = 0;
    d->left = 0;
    d->right = 0;
    for (int i = 0; i < v->size; ++i) {
        PushLeftDeque(d, v->array[i]);
    }
    
    return d;
}

bool isEmptyDeque(deque* d) {
    if (d->size == 0)
        return true;
    return false;
}

bool PushLeftDeque(deque* d, int i) {
    Item* q = 0;
    
    if (d->left) {
        q = d->left;
        d->left = d->left->prev;
    }
    
    d->left = (Item*)malloc(sizeof(Item));
    d->left->data = i;
    d->left->next = q;
    
    if (d->left->next)
        d->left->next->prev = d->left;
    
    d->left->prev = 0;
    
    if (!q)
        d->right = d->left;
    
    d->size++;
    
    return true;
}

bool PushRightDeque(deque* d, int i) {
    Item* q = 0;
    
    if (d->right != 0) {
        q = d->right;
        d->right = d->right->next;
    }
    
    d->right = (Item*)malloc(sizeof(Item));
    d->right->data = i;
    d->right->next = 0;
    d->right->prev = q;
    
    if (d->right->prev)
        d->right->prev->next = d->right;
    
    if (!q)
        d->left=d->right;
    
    d->size++;
    
    return true;
}

bool PopLeftDeque(deque* d) {
    if (isEmptyDeque(d))
        return false;
    
    Item* q;
    q = d->left->next;
    free(d->left);
    d->size--;
    d->left = q;
    
    if (d->size == 0) {
        d->right = d->left;
        return true;
    }
    
    d->left->prev = 0;
    
    return true;
}

bool PopRightReque(deque* d) {
    if (isEmptyDeque(d))
        return false;
    
    Item* q;
    q = d->right->prev;
    free(d->right);
    d->size--;
    d->right = q;
    
    if (d->size == 0) {
        d->left == d->right;
        return true;
    }
    
    d->right->next = 0;
    
    return true;
}

int TopLeftDeque(deque* d) {
    if (isEmptyDeque(d))
        // ошибка, обращение к нулевому указателю
    return d->left->data;
}

int TopLeftDeque(deque* d) {
    if (isEmptyDeque(d))
        // ошибка, обращение к нулевому указателю
    return d->right->data;
}

bool DeleteDeque(deque* d) {
    if (isEmptyDeque(d))
        return false;
    
    Item* q;
    q = d->left->next;
    free(d->left);
    d->size--;
    
    if (q == 0) {
        d->left = d->right = q;
        return true;
    }
    
    d->left = q;
    d->left->prev = 0;
    
    return DeleteDeque(d);
}

## Реализация (на кольцевом массиве)

> Не моя, спасибо людям из другого конспекта. Понравилась за лаконичность

Реализован только необходимый минимум (в соответсвии словам Зайцева).

#define CAP 100

typedef struct {
    doublr buff[CAP];
    int size;
    int head;
    int tail;
} deque;

void init(deque* dq);
void destroy(deque* dq);

int size(deque* dq);
bool is_empty(deque* dq);

double first(deque* dq);
double last(deque* dq);

double pop_back(deque* dq);
double pop_front(deque* dq);

bool push_back(deque* dq, double val);
bool push_front(deque* dq, double val);

double pop_back(deque* dq) {
    double val = dq->buff[(CAP + dq->tail - 1) % CAP];
    dp->size--;
    dp->tail = (CAP + dp->tail - 1) % CAP;
    return val;
}

double pop_front(deque* dq) {
    double val = dq->buff[dq->head];
    dq->head = (dq->head + 1) % CAP;
    dq->size--;
    
    return val;
}

bool push_back(deque* dq, double val) {
    if (dq->size >= CAP) {
        return false;
    }
    dp->buff[(dp->tail) % CAP] = val;
    dp->tail = (dp->tail + 1) % CAP;
    dp->size++;
    
    return true;
}

bool push_front(deque* dq, double val) {
    if (dq->size >= CAP) {
        return false;
    }
    dp->buff[(CAP + dq->head - 1) % CAP] = val;
    dp->head = (CAP + dp->head - 1) % CAL;
}

## Примеры задач

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

На лекции были приведены следующие примеры задач:
- разъезд поездов с протекающим туалетом;
> чтобы это не значило...
- задача с злыми птицами, которые двигаются по проводам.
> суть решения: использовать 2 дека: дек идущих направо, дек идущих налево; обмен деков по ссылке, поэтому можно использовать и итераторы; полное условие будет ниже, а код решения уж нет 

# 12-15 вопрос: Стек
## Определение
Стек - абстрактный тип данных, представляющий собой список элементов, организованных по принципу last in - first out. Аналогия с реальным миром - стопка блинов - первый приготовленный блин достается последним

## Функциональная спецификация
Над стеком определены следующие функции:

Также, можно объединить функции $ИЗ\_СТЕКА$ и $ВЕРХ$ в одну - $ИЗ\_СТЕКА: S_T \to S_T \times T$, которая будет возвращать верхний элемент и удалять его из стека.

## Логическое описание
Последний добавленный элемент - верхушка стека, остальная часть стека называется его телом. Верхушка стека вместе с его телом называется стеком. Если снять верхушку, то тело стека станет новым стеком.

Таким образом, структура данных "стек" является рекурсивной структурой данных и может быть описана рекурсивно как конкатенация элемента типа $T$ и стека типа $S_T$.

## Физическое представление (массив)

// тип элементов задан через макрос Т, чтобы было похоже на функциональную спецификацию
#define T uint64_t

typedef struct stack {
    uint64_t _size;
    uint64_t _capacity; // вместимость массива
    T *_arr;
} stack;

stack* stack_empty() {
    stack* s;
    s = (stack*) calloc(1, sizeof(stack));
    s->_arr = calloc(1, sizeof(T));
    s->_size = 0;
    s->_capacity = 1;
    return s;
}

bool stack_is_empty(stack* s) {
    return s->_size == 0;
}

uint64_t stack_size(stack* s) {
    return s->_size;
}

void stack_push(stack* s, T e) {
    if (s->_size + 1 > s->_capacity) {
        s->_arr = realloc(s->_arr, 2 * s->_capacity)
    }
    s->_arr[s->_size] = e;
    s->_size++;
    s->_arr[s->_size] = 0;
}

T stack_pop(stack* s) {
    if (s->_size == 0) {
        printf("Stack size is zero! Bailing...\n");
        exit(1);
    }
    s->_size--;
    return s->_arr[s->_size];
}

void stack_free(stack* s) {
    s->_size = 0;
    s->_capacity = 0;
    free(s->_arr);
}

## Физическое представление (динамические объекты)
В структуре данных `stack` храним значение верхнего элемента и ссылку на стек без верхнего элемента.

// тип элементов задан через макрос Т, чтобы было похоже на функциональную спецификацию
#define T int

typedef struct stack {
    T value;
    struct stack *prev;
    uint64_t _size;
} stack;

stack* stack_empty() {
    stack* s;
    s = (stack*) calloc(1, sizeof(stack));
    s->prev = NULL;
    s->_size = 0;
    return s;
}

bool stack_is_empty(stack* s) {
    return s->_size == 0;
}

uint64_t stack_size(stack* s) {
    return s->_size;
}

void stack_push(stack* s, T e) {
    stack *n = stack_empty();
    n->value = s->value;
    n->prev = s->prev;
    n->_size = s->_size;

    s->prev = n;
    s->value = e;
    s->_size++;
}

T stack_pop(stack* s) {
    if (s->_size == 0) {
        printf("Stack size is zero! Bailing...\n");
        exit(1);
    }
    T tempv = s->value;
    stack *temps = s;

    s = s->prev;

    free(temps);
    return tempv;
}

void stack_free(stack* s) {
    while (s->prev != NULL) {
        stack *temp = s->prev;
        free(s);
        s = temp;
    }
}

# 16-20 вопрос: Линейные списки

## Линейный список

Линейный список - это представление в ЭВМ конечного упорядоченного динамического мультимножества элементов типа $T$.

Элементы этого множества линейно упорядочены, но порядок определяется не номерами (индексами), как в массиве, а относительным расположением элементов.

Отношений порядка на этом множестве может быть не одно, а два, и тогда мы имеем дело с двусвязными (двусторонними или симметричными) списками.

Для закольцевания списка необходимо доопределить в качестве следующего за последним первый элемент списка, а в качестве предыдущего первому элементу -- последний (голова указывает на хвост, а хвост на голову). Таким образом отношения порядка (предыдущий и/или следующий) становятся определенными для всех смежных ( с точностью до закольцевания) пар элементов списка.

Линейные списки естественно использовать всякий раз, когда встречаются упорядоченные множества переменного размера, где включение, поиск и удаление элементов должны выполняться в произвольных последовательно достигаемых местах с сохранением порядка следования остальных элементов.

Таким порядком могли бы быть, например, приоритеты, присвоенные заданиям, ожидающим обработки в операционной системе или распечатки на сетевом принтере.

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

Добавление и удаление непосредственно самого элемента производится за $O(1)$, но заданый элемент необходимо найти, поэтому итоговая сложность добавление и удаление заданого элемента осуществляется за $O(n)$ (т.к. сложность поиска составляет $O(n)$).

## Функциональная спецификация.
Ниже приведена полная функциональная спецификация двусвязного линейного списка $L_T$ объектов типа $T$:
$$
СОЗДАТЬ: \varnothing \rightarrow L_T \\
ПУСТО: L_T \rightarrow \textbf{boolean} \\
ДЛИНА: L_T \rightarrow \mathbb{N} \\
ПЕРВЫЙ: L_T \rightarrow T \\
ПОСЛЕДНИЙ: L_T \rightarrow T \\
СЛЕДУЮЩИЙ: L_T \times T \rightarrow T \\
ПРЕДЫДУЩИЙ: L_T \times T \rightarrow T \\
ВСТАВКА: L_T \times T \times T \rightarrow L_T \\
УДАЛЕНИЕ: L_T \times T \rightarrow L_T \\
УНИЧТОЖИТЬ: L_T \rightarrow \varnothing \\
$$

В левой части спецификации операции ВСТАВКА находится декартово произведение трёх множеств: всевозможных списков, в которые должна быть проведена вставка; всех элементов, *перед* которыми необходимо её произвести и различных вставляемых элементов.

## Логическое описание.
Списковые структуры хорошо реализованы в альтернативных достаточно распространённых языках Lisp (в этом я.п. это даже основная структура) и Prolog.
Рассмотрим реализацию списков в Prolog. Список $(t_1, t_2, t_3, t_4, t_5)$ можно записать двумя способами:
1. $.(t_1,\ .(t_2,\ .(t_3,\ .(t_4,\ .(t_5, [\;])))))$, $[\;]$ - пустой список, $.(element, list)$ - добавление элемента в начало исходного списка;
2. $[t_1, t_2, t_3, t_4, t_5]$
Логическое описание списков на Prolog базируется на встроенном предикате отделения головы списка $<<|>>$ и реализованных на самом Prolog предикатах (программных единицах этого языка), более или менее соответствующих функциональной спицификации.

Поскольку в Паскале и в Си встроенных списков нет, а есть только бибилиотечные (std::list в STL), их логическое описание тесно переплетено с их физическим представлением.

## Физическое представление. Итераторы.

Итераторами называются объекты, обладающие функциями перехода от данного элемента списка к соседним. Для них задано отношение равенства (итераторы равны тогда и только тогда, когда они указывают на один и тот же элемент списка). Посредством итераторов осуществляется чтение и запись элемента списка.

Терминатор - итератор, указывающий на фиктивный элемент после конца списка.

#define T int

struct Item {
    struct Item* prev;
    struct Item* next;
    T data;
};

typedef struct {
    Item* node;
} Iterator;

bool Equal(const Iterator* lhs, const Iterator* rhs) {
    return lhs->node == rhs->node;
}

bool NotEqual(const Iterator* lhs, const Iterator* rhs) {
    return !Equal(lhs, rhs);
}

Iterator* Next(Iterator* i) {
    i->node = i->node->next;
    return i;
}

Iterator* Prev(Iterator* i) {
    i->node = i->node->prev;
    return i;
}

T Fetch(const Iterator* i) { // чтение элемента списка, на который указывает итератор
    return i->node->data;
}

void Store(const Iterator* i, const T t) { // запись данных в элемент списка
    i->node->data = t;
}

## Физическое представление (массив).

const int POOL_SIZE = 100;

typedef struct {
    struct Item* head;
    int size;
    struct Item* top;
    struct Item data[POOL_SIZE + 1];
} List;

void Create(List* l) {
    int i;
    for (i = 0; i < POOL_SIZE; i++)
        l->data[i].next = &(l->data[i + 1]);
    l->data[POOL_SIZE - 1].next = 0;
    l->head = &(l->data[POOL_SIZE]);
    l->head->prev = l->head->next = l->head;
    l->top = &(l->data[0]);
    l->size = 0;
}

Iterator Insert(List* l, Iterator* i, const T t) {
    Iterator res = { l->top };
    if (!res.node)
        return Last(l);
    l->top = l->top->next;
    
    res.node->data = t;
    res.node->next = i->node;
    res.node->prev = i->node->prev;
    res.node->prev->next = res.node;
    i->node->prev = res.node;
    i->sizde++;
    return res;
}

Iterator Delete(List* l, Iterator* i) {
    Iterator res = Last(l);
    if (Equal(i, &res)) 
        return res;
    res.node = i->node->next;
    res.node->prev = i->node->prev;
    i->prev->next = res.node;
    i->size--;
     
    i->node->next = l->top;
    l->top = i->node;
    
    i->node = 0;
    return res;
}

void Destroy(List* l) {
    l->head = 0;
    l->size = 0;
    l->top = 0;
}

## Физическое представление (динамические объекты).

typedef struct {
    Item* head;
    int size;
} List;

void Create(List* l) {
    l->head = malloc(sizeof(struct Item));
    l->head->next = l->head->prev = l->head;
    l->size = 0;
}

Iterator First(const List* l) {
    Iterator res = { l->head->next };
    return res;
}

Iterator Last(const List* l) {
    Iterator res = { l->head };
    return res;
}

bool Empty(const List* l) {
    Iterator fst = Fitst(l);
    Iterator lst = Last(l);
    return Equal(&fst, &lst);
}

int Size(const List* l) {
    return l->size;
}

Iterator Insert(List* l, Iterator* i, const T t) {
    Iterator res = { malloc(sizeof(struct Item)) };
    if (!res.node)
        return Last(l);
    res.node->data = t;
    res.node->next = i->node;
    res.node->prev = i->node->prev;
    res.node->prev->next = res.node;
    i->node->prev = res.node;
    i->sizde++;
    return res;
}

Iterator Delete(List* l, Iterator* i) {
    Iterator res = Last(l);
    if (Equal(i, &res)) 
        return res;
    res.node = i->node->next;
    res.node->prev = i->node->prev;
    i->prev->next = res.node;
    i->size--;
    free(i->node);
    i->node = 0;
    return res;
}

void Destroy(List* l) {
    struct Item* i = l->head->next;
    while (i != l->head) {
        struct Item* pi = i;
        i = i->next;
        free(pi);
    }
    free(l->head);
    l->head = 0;
    l->size = 0;
}

# 21 вопрос: Списки общего вида
Списки общего вида отличаются от обычных линейных списков только одной деталью - элементом списка общего вида может быть список. Список общего вида является простым обобщением линейного списка.

> В методичке ничего нет (с) Виталий
> Всё там есть! По сути, в методичке всё, что идет с деревьев до конца 5 главы, и есть списки общего вида (с) Рома

Также можно добавить, что примерами списков общего вида являются деревья, двоичные деревья и графы (и сказать пару слов о них).

# 22-27 вопрос: Деревья, двоичные деревья
Поиск оптимальной стратегии для алгоритмов, с постоянным ветвлением и, возможным возвращением к предыдущим шагам требует такой структуры данных как дерево.

## Определение дерева *(общего вида)*
Деревом типа $T$ называют такую структуру данных, которая образована элементом типа $T$, называемым корнем дерева, и конечным *(возможно пустым)* множеством с переменным числом элементов - деревьев типа $T$, называемых поддеревьями.

Дерево из одного элемента образует простейшее дерево с одним уровня, в котором кроме корня ничего нет. Дерево с $k$ уровнями получается из корня и поддеревьев, хотя бы одно из которых содержит $k - 1$ уровень.


- элементы деревьев называются вершинами или узлами
- число поддеревьев вершины называется степенью этой вершины
- вершина без поддеревьев называется концевой вершиной или листом
- неконцевые вершины называются внутренними или вершинами разветвления
- уровень вершины определяется рекурсивно:
- уровень корня дерева равен единице
- уровень корня каждого поддерева вершины на единицу больше уровня вершины
- глубина дерева - наибольшее значения уровня вершины

Определенные таким образом деревья называются **деревьями общего вида** или *сильно ветвящимися*. Эти деревья представляют собой непустые структуры (по крайней мере есть корень) с многозвенным разветвлением каждой вершины на непересекающиеся поддеревья.

## Определение двоичного дерева
Бинарное дерево - это конечное множество узлов, которое или пусто или состоит из корня и двух непересекающихся поддеревьев, называемых левым и правым поддеревьями данного узла.

Бинарное дерево **не** является частным случаем дерева общего вида *(в бинарном дереве важно положение поддеревьев)*.

## Функциональная спецификация

## Логическое описание + физическое представление
Структура дерева будет состоять из двух указателей на левое и правое поддерево и из значения в вершине

#define T char

typedef struct Node {
    T value;
    struct Node* left;
    struct Node* right;
} Node;

Node *node_empty() {
    Node *n = calloc(1, sizeof(Node));
    n->value = 0;
    n->left = NULL;
    n->right = NULL;
    return n;
}

Node *node_build(Node *r, Node *l, T value) {
    Node *n = node_empty();
    n->left = l;
    n->right = r;
    n->value = value;
    return n;
}

bool node_is_empty(Node *n) {
    return n->value == 0 && n->right == NULL && n->left == NULL;
}

T node_value(Node *n) {
    return n->value;
}

Node *node_left(Node *n) {
    return n->left;
}

Node *node_right(Node *n) {
    return n->right;
}

void node_free(Node *n) {
    if (n->left != NULL) {
        node_free(n->left);
    }
    
    if (n->right != NULL) {
        node_free(n->right);
    }
    
    n->value = 0;
    free(n);
}

## Алгоритмы обхода деревьев
### Определение
Обход дерева - перебор всех вершин дерева единожды в некотором порядке.

Для бинарного дерева определены три способа обхода:
1. Прямой обход: *(**pre**order)*
- если дерево пусто, то конец обхода
- **берется корень**
- обход левого поддерева
- обход правого поддерева
2. Обратный обход: *(**in**order)*
- если дерево пусто, то конец обхода
- обход левого поддерева
- **берется корень**
- обход правого поддерева
3. Концевой обход: *(**post**order)*
- если дерево пусто, то конец обхода
- обход левого поддерева
- обход правого поддерева
- **берется корень**


При обходе используются рекурсивные функции, *(либо цикл со стеком, отражающим положение в дереве, **что по сути то же, что рекурсия**)*, однако есть способы представления деревьев, при которых возможен итеративный обход.

void node_inorder(Node *n) {
    if (node_is_empty(n)) return;
    node_inorder(n->left);
    {
        // обработка вершины (корня)
    }
    node_inorder(n->right);
}
// остальные расписываются подобно

## Особенности представления и обработки деревьев общего вида
Главная отличительная особенность дерева общего вида от двоичного дерева заключается в том, что мы не знаем сколько поддеревьев у той или иной вершины. Представлять поддеревья вершины дерева общего вида удобно при помощи списка указателей на вершины-дети.

То есть деревья общего вида можно представить в виде следующей структуры данных:

typedef struct Node {
    T value;
    struct Node *children;
}

Теперь функций обхода два типа - в глубину *(сначала смотрим детей)* и в ширину *(сначала смотрим братьев)*.

Также, общие деревья можно представить в виде бинарных деревьев:

Пусть $A$ - изначальное дерево, $B$ - новое бинарное дерево, тогда, чтобы представить $A$ как бинарное дерево можно использовать следующий рекурсивный алгоритм:
- корень $B$ есть корень $A$
- левое поддерево $B$ - результат этого алгоритма от первого поддерева $A$
- правое поддерево $B$ - результат этого алгоритма от очередного брата вершины $A$

*Слева - изначальное дерево, справа - его представление в виде двоичного дерева*

Для более стандартного вида, правое дерево можно повернуть на 45 градусов по часовой стрелке


## Прошивка деревьев (рассматриваем бинарные)

Откуда появилась идея прошивки деревьев? У листьев бинарного дерева оба указателя на левое и правое поддеревья пустые. А, как правило, около половины узлов являются листьями. В итоге, такое представление бинарного дерева оказывается неэкономичным с точки зрения расхода памяти.

В прошитых бинарных деревьях вместо пустых указателей используются специальные связи-нити и каждый указатель в узле дерева дополняется однобитовым признаком $ltag$ и $rtag$ соответсвтенно. Признак определяет, содержится ли в соответствующем указателе обычная ссылка на поддерево или в нем содержится связь-нить.





# 28 вопрос: Представление и обработка графов
### Определение
Графом называют подмножество декортова произведения двух множеств. Топологически граф изображается как множество вершин, соединенных линиями *(ребрами)*, между любой парой вершин - максимум одно ребро.

Вершины называются смежными, если между ними есть ребро.

В графе существует путь из $A$ в $B$ $\Leftrightarrow$ $\exists A_i,\ i=1..n,\ A_1 = A,\ A_n = B$, для $i=1..(n-1): A_i, A_{i+1}$ - смежные.

Путь называется простым, если все промежуточные вершины ($A_2,..,A_{n-1}$) попарно различны.

Циклом называется простой путь длины не менее 3 от любой вершины до нее самой.

Ориентированным графов называется граф, каждому ребру которого задано направление (ребро теперь называется дугой).

### Представление в ЭВМ
Граф можно представить в виде матрицы смежности.

**Существует ли путь?**
В графе с $k$ вершинами и матрицей смежности $M$ существует путь из вершины номер $i$ в вершину номер $j$ тогда и только тогда, когда в $M^+$ элемент $M^+_{ij} = 1$, где
$$M^+ = \bigvee^k_{i=1} M^i$$
Для получения $M^+$ необходимо вычислить булевский матрочлен за $O(n^4)$ шагов.

Граф с $k$ вершинами можно представить как $k$ списков, которые содержат в себе номера смежных вершин

### Алгоритмы на графах
**Поиск в глубину**, отличие от поиска в глубину в дереве в том, что мы помечаем пройденные вершины, а когда идем дальше проверяем, помечена ли вершина

**Поиск в ширину** - та же особенность

# 29-32 вопросы: Деревья выражений

## 29. Деревья выражений.
Дерево выражения - бинарное дерево, узлами которого являются элементы выражения.

Виды выражений:
1. арифметические;
2. логические;
3. информатические.

Разнофиксные формы записи выражений:
1. префиксная;
2. инфиксная;
3. постфиксная.

## 30. Алгоритм Рутисхаузера.

Один из наиболее ранних алгоритмов.

Предполагает полную скобочную структуру выражения - такую форму записи, при которой порядок действий задаётся расстановкой скобок.

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

Например, для выражения $(A + (B * C))$ значения уровней таковы:

Основные этапы алгоритма Рутисхаузера:
1. расставить уровни;
2. отыскать элементы строки с максимальным значением уровня;
3. выделить тройку - два операнда с максимальным значением уровня и операцию, которая заключена между ними;
4. результат выполнения выделенной операции обозначить вспомогательной переменной;
5. из исходной строки удалить выделенную тройку вместе с её скобками, а на её место поместить вспомогательную переменную, обозначающую результат, со значением уровня на единицу меньше, чем у выделенной тройки;
6. выполнять пункты 2-5 до тех пор, пока во входной строке не останется одна переменная, обозначающая общий результат выраежния.

## 31. Алгоритм Бауэра-Замельзона.

Ранний стековый метод.

Используются два стека и таблица функций перехода. Один стек (T) используется при трансляции выражения, а второй (E) - во время интерпретации выражения.

В таблице переходов задаются функции, которые должен выполнить транслятор при разборе выражения:
- f1: заслать операцию из входной строки в стек T; читать следующий символ строки;
- f2: выделить тройку - взять операцию с вершины стека T и два операнда с вершины стека E; вспомогательную переменную - результат операции занести в стек E; засласть операцию из входной строки в стек T; читать следующую лексему строки;
- f3: исключить лексему из стека T; читать следующий символ строки;
- f4: выделить тройку - взять операцию с вершины стека T и два операнда с вершины стека E; вспомогательную переменную - результат операции занести в стек E; по таблице определить функцию для данной лексемы входной строки;
- f5: выдача сообщения об ошибке;
- f6: завершение работы.

Таблица переходов для алгебраических выражений будет иметь вид (знак $ является признаком пустого стека или пустой строки):

Выражение просматривается слева направо и над каждой лексемой выполняются следующие действия:
- если очередная лексема входной строки является операндом, то она безусловно переносится в стек E;
- если это операция, то по таблице функций перехода определяется номер функции для выполнения.

Для выражения $A + (B - C) * D$ будут проделаны следующие действия:

## 32. Алгоритм Дейкстры.
Используется для превращения инфиксной записи в обратную польскую или в дерево выражений.

Для его работы используем один стек и очередь вывода

Пока не все лексемы обработаны:
- если число - в вывод
- если функция - в стек
- если разделитель аргументов функции, то:
- пока на вершине стека не открывающая скобка - перекладывать операции из стека в вывод *(если в стеке нет скобки, то в выражении ошибка - пропущен разделитель аргументов или пропущена открывающая скобка)*
- если операция $op_1$, то:
- пока на вершине стека $op_2$ и приоритет $op_1$ меньше - перекладываем $op_2$ в вывод, $op_1$ на стек
- если открывающая скобка - в стек
- если закрывающая скобка:
- пока на вершине стека не открывающая скобка - операции из стека в вывод
- вынуть открывающую скобку из стека, но не добавлять в вывод
- если на вершине стека функция - добавить ее в вывод
- если стек закончился и скобка не была встречена - ошибка
- если вывод пуст:
- пока есть операции в стеке:
- переложить операцию из стека в вывод
- если на вершине стека - скобка, то ошибка *(есть незакрытая скобка)*

Сложность алгоритма - $O(n)$

Пример:


Выражение: $3 + 4 * 2/(1-5)\wedge 2$





# 33 вопрос: Деревья поиска.
Бинарные деревья часто используются для представления множеств данных, элементы которых должны быть найдены по ключу.

### Определение
Если дерево организовано так, что для каждой вершины справедливо, что все ключи левого поддерева меньше ключа этой вершины, а все ключи правого поддерева - больше, то такое дерево называют **деревом поиска**.

При поиске нужного ключа на каждом шаге исключается одно из поддеревьев, что *значительно* уменьшает количество возможных для поиска вершин, причем чем сбалансированнее дерево, тем больше вершин будет исключено из поиска.

Число вершин, участвующих в поиске для сбаласированного дерева не может быть больше его глубины, которая оценивается в $\log_2n$, где $n$ - количество ключей *(вершин)*

Для реализации поиска на дереве поиска можно обойтись итеративной функцией поиска и не мудрить с рекурсией

Node *node_find(Node *n, T elem) {
    while (n != NULL && n->value != elem) {
        if (n->value < elem) {
            n = n->right;
        } else {
            n = n->left;
        }
    }
    return n;
}

### Добавление элемента
Иногда при поиске важно посчитать то, сколько раз встретился элемент, однако если элемента до этого не было в дереве - его надо добавить *(проводим параллель с `map`)*

typedef struct Node {
    T key;
    int count;
    struct Node* left;
    struct Node* right;
} Node

void node_add(Node *n, T key) {
    if (n == NULL) {
        n = node_empty();
        n->key = key;
        n->count = 1;
    } else if (key < n->key) {
        node_add(n->left, key);
    } else if (key > n->key) {
        node_add(n->right, key);
    } else {
        n->count++;
    }
}

### Удаление элемента
Удаляемый элемент заменяется либо на **самый правый элемент левого сыночка**, либо на **самый левый правого сыночка**, чтобы сохранить порядок.

Для реализации используем рекурсию

void node_delete(Node *n, T key) {
    if (n == NULL) {
        return;
    }
    
    if (key < n->key) {
        node_delete(n->left, key);
    } else if (key > n->key) {
        node_delete(n->right, key);
    } else {
        Node *tl = n->left;
        Node *tr = n->right;
        if (tr == NULL) {
            n = tl;
        } else if (tl == NULL) {
            n = tr;
        } else {
            while (tl->right != NULL) { // берем самый правый элемент левого сыночка
                tl = tl->right;
            }
            n->key = tl->key;
            n->count = tl->count;
            tl = NULL;
        }
    }
}

# 34-36 вопросы: Сбалансированные деревья
## 34. Сбалансированные деревья поиска.


## 35. Сбалансированные деревья поиска. Вставка.
### Анализ
Если дерево состоит из корня $t$, левого поддерева $L$ и правого поддерева $R$, то возможны следующие случаи:
1. дерево идеально сбалансированно и вставка новой вершины углубит одно из поддеревьев на единицу;
2. вставляемая вершина попадёт в более низкое поддерево и улучшит сбалансированность;
3. вставляемая вершина попадёт в более высокое поддерево и нарушит сбалансированность, возникает необоходимость балансировки дерева.

С точностью до симметрии существует всего лишь две различные возможности несбалансированности, возникшей из-за включения. Они отличаются местом возникновения перевеса: с края или в середине дерева.


Процесс балансировки заключается в вертикальном <<подтягивании>> одного или двух поддеревьев путем манипуляций ссылками на потомков в вышестоящих вершинах, релевантных для восстановления баланса. Среди этих манипуляций такие:
- подчинение корня левому поддереву и переподчинение внука, выравнивающее баланс;
- подъём на два уровня внутреннего подерева, включение которог привело к несбалансированности.

При этом относительное горизонтальное расположение переставляемых вершин остаётся без изменений.


### Алгоритм

Схема алгоритма включения в сбалансированное дерево такова:
1. поиск элемента в дерева (не забывать, что может быть неудачным!);
2. включение новой вершины и определение результирующего показателя сбаланисрованности;
3. отход по пути поиска с проверкой показателя сбалансированности для каждой проходимой вершины, балансируя в необходимых случаях соответствующие поддеревья;

Иллюстариция принципа работы алгоритма:

## 36. Сбалансированные деревья поиска. Удаление.

### Анализ

Процедура удаления следует схеме вставки. Удаление треминальной или однодетной вершины - задача в одно действие. Двудетные вершины обрабатываются так же, как и раньше: они заменяются на самую правую вершину её любого поддерева.

### Алгоритм
Схема алгоритма удаления из сбалансированного дерева такова:
1. поиск элемента в дерева (не забывать, что может быть неудачным!);
2. удаление новой вершины и определение результирующего показателя сбаланисрованности;
3. отход по пути поиска с проверкой показателя сбалансированности для каждой проходимой вершины, балансируя в необходимых случаях соответствующие поддеревья;

Иллюстариция принципа работы алгоритма:



# 37-41 вопрос: Таблицы
## 37: Задача поиска. Простые методы поиска в последовательностях и таблицах
Одно из наиболее часто встречающихся в программировании действий - поиск. Эффективность поиска часто является основным критерием качества различных структур данных.
Для рассмотрения алгоритмов поиска предположим, что множество данных, в котором выполняется поиск, фиксировано, резидентно и допускает прямой доступ к каждому элементу.

struct item a[N] // a[0..N-1]

В результате поиска значения x в массиве a устанавливается индекс i, удовлетворяющий условию

a[i].key == x

## Поиск в таблице
Отличие поиска в таблице от поиска в массиве заключается в том, что в таблицах ключ является составным и имеет регулярную структуру(является массивом)

Для поиска в таблице в языке C существует функция bsearch(). Она принимает в качестве параметров:
1) Указатель на ключ который мы ищем;
2) Указатель на элемент массива который мы ищем;
3) Количество элементов, над которыми производится поиска;
4) Размер элемента массива в байтах;
5) Функция сравнения элементов, принимающая на вход указатели на сравнимаемые элементы

На выход возвращает указатель на найденный элемент или **NULL**, если элемент не найден
## Поиск в последовательностях
Пусть строка в которой нужно найти A, а строка которую нужно найти будет B
Он работает так:
1) Идем по строке A, пока не найдём первый символ строки B
2) Далее идем по строке A и проверяем все символы строки B
3) Если не совпало, то идем в следующий элемент, после начала шага 1 и повторяем алгоритм до конца строки B.

Сложность: В худшем случае O(N*M), в средем: между O(M) и O(N)
## 38: Алгоритм Кнута-Морисса-Пратта(КМП)
Алгоритм КМП - алгоритм поиска подстроки в строке. Он основывается на том соображении, что начиная каждый раз сравнение образца с самого начала, мы теряем ценную информацию о неудачном поиске. Покажем иллюстрацию этого соображения на примере поиска слова Hooligan. Знаки которые мы сравнивали будут подчеркнуты. При каждом несовпадении двух знаков образец сдвигается по последовательности вперед на всё пройденное расстояние, так как при анализе мы выяснили, что меньший сдвиг не может привести к полному совпадению.
Зайцев написал сложно про функцию d, постараюсь объяснить проще. Таблица D у людей называется префикс-функцией строки K. Эта таблица является вектором. Определим его так D(K, i) = max{k:K[0..k-1]=K[i - k +1....i]}. Объясню на примере: пусть дана строка ababac:
1) a - не никаких совпадений - 0
2) ab - тоже самое - 0
3) aba - здесь имеем с 2 сторон одинаковую строку a, значит - 1
4) abab - одинаковая строка ab - 2
5) ababa - одно совпадение, a - 1
6) ababac - нет совпадений - 0.

Получаем вектор D = {0, 0, 1, 2, 1, 0}
Вектор D отвечает, насколько элементов мы будем двигать "индекс сканирования".
Реализация:

int seek_substring_KMP (char s[], char p[])
{
	int i, j, N, M;
	N = strlen(s);
	M = strlen(p);

    // Динамический массив длины М
	int *d = (int*)malloc(M * sizeof(int));

	// Вычисление префикс-функции
	d[0] = 0;
	for(i = 1, j = 0; i < M; i++)
	{
		while(j > 0 && p[j] != p[i])
			j = d[j-1];
		if(p[j] == p[i])
			j++;
		d[i] = j;
	}

	// Поиск
	for(i = 0, j = 0; i < N; i++)
	{
		while(j > 0 && p[j] != s[i])
			j = d[j - 1];
		if(p[j] == s[i])
            j++;
		if(j == M)
        {
		    free(d);
            return i - j + 1;
        }
	}
    free(d);
	return -1;
}

Сложность: O(N+M)

> Вопросы с 38 по 41 отсутствуют(

## 41 вопрос: Таблицы с прямым доступом (хеш-функции тоже здесь)

Таблицей с прямым доступом (или хеш-таблицей) называется структура данных, представляющая из себя множество пар ключ-значение. Существует два основных вида хеш-таблиц: с открытой адресацией и списками, но здесь речь будет идти о хеш-таблицах с открытой адресацией (по вопросу это понятно).

Для получения доступа к значению по ключу необходимо определить функцию

$$H: K \to A,$$

где $K$ - множество ключей, а $A$ - множество отведенных под таблицу адресов. Вместо адресов могут быть использованы индексы элементов массива.

Функцию $H$ называют хеш-функцией. Хорошая хеш-функция должна равномерно распределять ключи по всему диапазону индексов. Еще лучше, если эта функция является инъективной, однако такое встречается достаточно редко. Если распределение хеш-функции близко к равномерному, то все равно остается вероятность (причем достаточно большая).

На данной картинке вы можете видеть, что вероятность совпадения каких-то двух значений (раномерновероятностно распределенных на всем диапазоне от 1 до 100) превышает 80% уже при 20% заполненности.


Такие совпадения отображений называются *коллизиями* или *конфликтами*.

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

Вот еще вырезка из методички Зайцева. В следующей таблице приведены оценки различных методов доступа:


# 42-54 вопрос: Сортировки
## 42 вопрос: Задача сортировки. Классификация и свойства сортировок.
Cортировкa - процесс перестановки заданного множества объектов в некотором порядке. Цель сортировки — облегчить последующий поиск элементов в таком отсортированном множестве. Сортировка — это один из универсальных основополагающих видов обработки данных.

Выбор алгоритма всегда зависит от структуры обрабатываемых данных. В случае сортировки соответствующие методы распадаются на сортировку массивов и сортировку файлов(последовательностей). Иногда их называют **внутренними** и **внешними** сортировками, поскольку массивы хранятся в основной (внутренней) памяти машины с произвольным доступом, а файлы обычно размещаются во внешней памяти.

Для постановки задачи сортировки введем некоторые понятия и обозначения. Сортируемые элементы будем обозначать $a_1, a_2, . . . , a_n$. Сортировка есть некоторая перестановка этих элементов $a_{k_1}, a_{k_2}, . . . , a_{k_n}$, где ($k_1, k_2, . . . , k_n$ — перестановка последовательности 1, 2, . . ., n), для которой выполнено некоторое отношение порядка $f$: $f(a_{k_1}) \leq f(a_{k_2}) \leq ... \leq f(a_{k_n})$
В случае, когда элементы $a_1, a_2, . . . , a_n$ непосредственно сравнимы, отношение порядка f вычислять не требуется, а достаточно хранить сами сравниваемые компонентыcв соответствующих полях элементов $a_i$ . Так же, как и в случае поиска, сравнимые поля элементов сортировки называются **ключами**. Типы других компонент элементов, хранимых с ключами, могут быть самыми разнообразными, и поэтому элементы обычно имеют комбинированный тип.

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

**Сортировка массивов**
Основное ограничение внутренней сортировки связано с дефицитной оперативной памятью. Это означает, что перестановки элементов в процессе сортировки должны выполняться на месте, без использования вспомогательных массивов. Другим критерием экономичности алгоритма сортировки является временн́ая сложность, которую мы будем выражать в виде функции $f(C(n), M(n))$, где $n$ — число сортируемых элементов, $C$ — число сравнений ключей и $M$ — число перестановок(пересылок) элементов. Сравнения и пересылки рассматриваются отдельно, поскольку их времена могут отличаться существенно. Рассмотрение алгоритмов сортировки начнем с т. н. прямых методов.

## 43. Сортировка вставкой.

Сортируемые элементы мысленно делятся на уже готовую (отсортированную) последовательность $a_1, . . ., a_{i−1}$ и исходную (неупорядоченную) последовательность $a_i, . . ., a_n$. Вначале первая последовательность должна быть пуста, но мы включим в нее первый элемент множества, поскольку последовательность из одного элемента всегда упорядочена! Этот элемент не обязательно минимальный, и впоследствии он может быть переставлен на подобающее место.

Поиск места для вставки удобно осуществлять справа налево, движение справа налево позволяет выполнять необходимые сдвиги в процессе поиска, а не после него. Проходим по массиву слева направо и обрабатываем по очереди каждый элемент. Слева от очередного элемента наращиваем отсортированную часть массива, справа по мере процесса уменьшается неотсортированная. В отсортированной части массива ищется(справа налево от очередного элемента) точка вставки для очередного элемента. Сам элемент отправляется в буфер, в результате чего в массиве появляется свободная ячейка — это позволяет сдвинуть элементы и освободить точку вставки.

Просмотр упорядоченной подпоследовательности происходит справа налево и заканчивается, когда:
1. найден элемент $a_j$ с ключом, меньшим ключа x;
2. достигнут левый конец последовательности.

#define n 10
void StrInsSort(int a[])
{
    /* Сортировка прямой вставкой - стандартный алгоритм */
    /* Основной принцип: полагая, что первые i - 1 элементов отсортированы, берем i-й элемент и вставляем его на нужное место */
    int i, j;
    int x;
    for(i=1; i<n; i++)
    {
        x = a[i]; /* i-тый элемент исходной последовательности копируется в x*/
        j = i;/* Фиксируем стартовую позицию для поиска справа налево */
        /* Сдвигаем элементы вправо */
        while(a[j-1] > x && j > 0)
        {
            a[j] = a[j-1];
            j--;
        }
        a[j] = x; /* Вставляем на нужное место */
    }
}
void StrInsSortB(int a[])
{
    /* Сортировка прямой вставкой - алгоритм с барьером */
    /* Основной принцип: барьер упрощает сравнение и ускоряет сортировку
    */
    /* Недостаток: приходится наpащивать структуру данных на 1 элемент */
    int i, j;
    int x;
    for(i=1; i<n; i++)
    {
        x = a[i]; /* i-тый элемент исходной последовательности копируется в x*/
        a[0] = x;/* a[0] - барьер */
        j = i;
        /* Копирование со сдвигом */
        while(a[j-1] > x)
        {
            a[j] = a[j-1];
            j--;
        }
        a[j] = x; /* Вставляем на нужное место */
    }
}

**Сложность алгоритма:**

Алгоритм сортировки вставкой *устойчив*.

**Примечание:**
Поиск места для вставки может быть существенно ускорен за счет применения бинарного поиска в упорядоченной части
последовательности. Такой поиск возможен, поскольку она располагается в памяти прямого доступа. Соответствующая модификация алгоритма называется **методом двоичной вставки**.

## 44 вопрос: Сортировка выборкой.

Алгоритм основан на простой идее:
• отыскивается элемент с наименьшим ключом;
• он меняется местами с первым элементом $a_1$;
• процесс повторяется для оставшихся n − 1-ого, n − 2-х, . . . элементов до тех пор, пока не останется один, самый большой элемент.

Допустим необходимо отсортировать массив по возрастанию. В исходном массиве находим минимальный элемент, меняем его местами с первым элементом массива. Уже из всех элементов массива один элемент стоит на своём месте. Теперь будем рассматривать не отсортированную часть массива, то есть все элементы массива, кроме первого. В неотсортированной части массива опять ищем минимальный элемент. Найденный минимальный элемент меняем местами со вторым элементом массива и т. д. Таким образом, суть алгоритма сортировки выбором сводится к многократному поиску минимального(максимального) элементов в неотсортированной части массива.

#define n 10
void StrSelSort(int a[])
{
    /* Сортировка прямым выбором - стандартный алгоритм */
    int i, j, k;
    int x; /* Здесь x - для перестановки, а не для сдвига */
    for(i = 0; i < n; i++)
    {
        x = a[i]; /* Берем очередной элемент... */
        k = i; /* ... и запоминаем его индекс */
        /* Ищем минимальный среди остальных */
        for(j=i+1;j<n;j++)
        {
            /* Встретился меньший выбранного - запоминаем его индекс и продолжаем поиск */
            if (a[j] < a[k])
            {
                k = j;
            }
        }
        /* Перестановка текущего элемента с наименьшим в подпоследовательности */
        x = a[k];
        a[k] = a[i];
        a[i] = x;
    }
}

**Сложность: $O(n^2)$**

## 45 вопрос: Пузырьковые сортировки.

Алгоритм пузырьковой сортировки(прямого обмена), основывается на сравнении и перестановке пар соседних элементов до тех пор, пока таким образом не будут упорядочены все элементы. Как и при сортировке выборкой мы осуществляем проходы по массиву, постепенно сдвигая наименьший элемент оставшейся последовательности к левому краю массива.
Сразу внесем улучшение: поскольку легчайший пузырек всплывает наверх всего за один проход, то при последущих просмотрах можно исключать из рассмотрения по одному такому элементу и тем самым несколько ускорить пузырьковую сортировку.

Пузырьковая сортировка стобца:

#define n 10
void BubbleSort(int a[])
{
/* Сортировка прямым обменом - пузырьковая */
/* Основной принцип: на каждом проходе сравниваются два соседних элемента и обмениваются местами. Продолжается до тех пор, пока элементы не будут упорядочены. Недостатки: (1) на последних проходах элементы могут уже быть упорядочены. (2) Пузырек всплывает быстро (за 1 проход до верху), а тонет медленно (за 1 проход на 1 позицию) */
    int x;
    for(int i = 0; i < n; i++)
    {
        for(int j = n - 1; j >= i; j--)
        {
            if(a[j-1] > a[j]) 
            {
                x=a[j-1];
                a[j-1]=a[j];
                a[j] = x;
            }
        }
    }
}

Из нашего примера видно, что три последних прохода не влияют на порядок элементов из-за того, что все они уже отсортированы. Эти лишние проходы запланированы на случай самой плохой входной последовательности, в которой на первом месте расположен ее максимальный элемент. Однако, если на каждом проходе вести подсчет числа состоявшихся обменов(или фиксировать сам факт обменов), то можно улучшить пузырьковую сортировку:

#define n 10
void BubbleEnhSort(int a[])
{
    /* Сортировка прямым обменом - пузырьковая улучшенная */
    /* Основной принцип: если элементы уже упорядочены, сортировка прекращается */
    int x;
    bool swapped; /* swapped -- факт обмена */
    for(inti=1;i<n;i++)
    {
        swapped = false; /* Обменов не было */
        for(intj=n-1;j>=i;j--)
        {
            if(a[j-1]>a[j])/*ai↔aj */
            {
                x=a[j-1];
                a[j-1]=a[j];
                a[j] = x;
                swapped = true;
            }
        }
        if(!swapped)/* Перестановок не было, значит, набор упорядочен */
        {
        break;
        }
    }
}

Говоря о быстром всплытии легкого пузырька, мы можем констатировать медленное погружение тяжелого. Всплывает пузырек сразу, за один проход, а тонет медленно, только на один уровень за проход. Это наводит на мысль чередовать направления просмотра с целью дальнейшего ускорения сортировки. Технически чередование выписывается явно или могло бы быть реализовано чередованием прямого и обратного итераторов обхода массива, для которых по-разному определено направление просмотра «вперед». Такая модернизированная пузырьковая сортировка названа **шейкерной**.
Шейкерная сортировка столбца даст следующие результаты:

Программа шейкерной сортировки итерирует линейную композицию из прямого и об-
ратного прохода:
#define n 10
void ShakeSort(int a[])
{
    /* Сортировка прямым обменом - шейкерная */
    /* Основной принцип: на каждом проходе сравниваются два соседних элемента и обмениваются местами. Обмен идет в двух направлениях. Применяется: если известно, что элементы почти упорядочены */
    int x, L=1, R=n, k=n-1;
    do
    {
        for(int i=R-1; i>=L; i--)
        {
            if(a[i-1]>a[i])
            {
                x=a[i-1];
                a[i-1]=a[i];
                a[i] = x;
                k = i; /* Усовершенствованный вариант: запоминается последний обмен */
            }
        }
        L=k+1;
        for(inti=L;i<R;i++)
        {
            if(a[i-1]>a[i])
            {
            x=a[i-1];
            a[i-1]=a[i];
            a[i] = x;
            k = i; /* Усовершенствованный вариант: запоминается последний обмен */
            }
        }
        R=k;
    } while(L < R);
}

**Сложность:** $O(n^2)$

## 46 вопрос: Сортировка Шелла.

## 47 вопрос: Турнирная сортировка

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

Турнирная сортировка - это алгоритм сортировки, использующий двоичные турнирные деревья. Некоторые версии этого алгоритма используются на соревнованиях, для этого проводится несколько переигровок с разделением на основную сетку, сетку лузеров и победителей, но этот треш я здесь рассматривать не буду.

Для начала рассмотрим вариант турнирной сортировки для массива длиной $n = 2^m$ элементов, где $m \in \mathbb{N}$.

В данном случае все тривиально, сортировка проходит в несколько этапов:

1. $n$ элементов массива располагаются на нижнем уровне турнирной сетки, затем эта сетка заполняется, на уровень выше выходят элементы с наименьшим значениям по ходу попарного сравнения. В корне турнирной сетки располагается победитель - элемент с наименьшим значением среди элементов массива.
2. После победитель удаляется и заносится в последующую ячейку итогового массива, а его путь к вершине затирается максимально возможными значениями данного типа ($max\_value$). После этого турнирная сетка заполняется заново.

Этот этап повторяется до тех пор, пока все элементы не будут расположены (т.е. всего будет $n$ итераций).

Поясняющие картиночки:

Заполенная турнирная сетка

Турнирная сетка с затертым победителем (в "дырках" находятся $max\_value$)

Перезаполненная турнирная сетка (на месте исключенного бывшего победителя остается $max\_value$)

Итого: сложность 1-го этапа - $O(n)$, 2-го - $O(n\log_2n))$, следовательно, суммарная сложность сортировки - $O(n\log_2n)$

Тээк-с, теперь надо решить задачу для нетривиального случая. Ну, здесь можно просто дополнить массив фиктивными значениями ($max\_value$) до вида $m = 2^k, k \in \mathbb{N}$ и $n \leq m$ и запустить алгоритм для тривиального случая. В итоге элементы изначального массива будут занимать первые $n$ позиций нового и притом в отсортированном виде, так что остается только перезаписать старый массив и освободить новый.

Сложность от этого, понятное дело, не поменяется - $O(n\log_2n)$.

Код прилагается:

Одно важное замечание: в тривиальном случае двоичное дерево можно линеаризовать используя нумерацию: индекс корневого элемента - 0, для индекса $i$ левый ребенок под индексом $2i + 1$, правый - под $2i + 2$. Таким образом для $n$ элементного массива будет построена $k = 2n - 1$ элементная турнирная сетка (т.к. $1 + 2 + ... 2^m = 2^{m+1} - 1$, так что $n = 2^m \Rightarrow k = 2n - 1$).

tournament_sort.c

#include <inttypes.h>
#include <stdlib.h>

#define templ_type int64_t

#define max_value INT64_MAX

#define at(begin, i) (*(begin + i))

templ_type min(templ_type a, templ_type b) {
    return (a < b ? a : b);
}

typedef uint64_t size_t;

// begin - pointer to the first element of the memory line
// end - pointer to the next from the last element of the memory line
// <-------line-------->
// [0x1 0x2 0x3 0x3 0x4, ...]
//  ^                     ^
// begin                 end
typedef struct line {
    templ_type* begin;
    templ_type* end;
} line;

// Play tournament with given participants
void build_tournament_brackets(line tb, size_t n) {
    if (n < 2) {
        return;
    }
    templ_type* begin = tb.begin;

    // 'm' is beginning of playing tournament level, 'sz' - number of participants on the level
    size_t m = (2 * n - 1) - (n) - (n / 2), sz = n / 2;
    while (0 < m) {
        for (size_t i = m; i < m + sz; ++i) {
            at(begin, i) = min(at(begin, 2 * i + 1), at(begin, 2 * i + 2));
        }
        sz /= 2;
        m -= sz;
    }
    at(begin, 0) = min(at(begin, 1), at(begin, 2));
}

// Rebuild tournament brackets without winner element (root)
void rebuild_tournament_brackets(line tb, size_t n, size_t i) {
    templ_type* begin = tb.begin;
    templ_type t = at(begin, i);
    at(begin, i) = max_value;

    // If there is lower layer then go
    if (i < n - 1) {
        if (at(begin, 2 * i + 1) == t) {
            rebuild_tournament_brackets(tb, n, 2 * i + 1);
        } else if (at(begin, 2 * i + 2) == t) {
            rebuild_tournament_brackets(tb, n, 2 * i + 2);            
        }
        at(begin, i) = min(at(begin, 2 * i + 1), at(begin, 2 * i + 2));
    }
}

// Sorts array with length that is a degree of 2 (2^k)
void trivial_tournament_sort(line l) {
    templ_type* begin = l.begin;
    templ_type* end = l.end;
    size_t n = end - begin, k = 2 * n - 1;

    // 1. Build tournament bracket
    templ_type* tb = (templ_type*)malloc(k * sizeof(templ_type));
    for (size_t i = 0; i < n; ++i) {
        tb[i + k - n] = at(begin, i);
    }

    build_tournament_brackets((line){ .begin = tb, .end = tb + k }, n);

    // 2. Sort winners

    for (size_t i = 0; i < n; ++i) {
        // Choose winner
        at(begin, i) = tb[0];
        // Rebuild tournament brackets without chosen element
        rebuild_tournament_brackets((line){ .begin = tb, .end = tb + k }, n, 0);
    }
    free(tb);
}

// Sorts arrays in general case
void tournament_sort(line l) {
    size_t n = l.end - l.begin, k = 1;
    // k is the least nubmer that not less than n and is some degree of 2
    while (k < n) {
        k <<= 1;
    }

    templ_type* arr = (templ_type*)malloc(k * sizeof(templ_type));
    for (size_t i = 0; i < n; ++i) {
        arr[i] = at(l.begin, i);
    }
    for (size_t i = n; i < k; ++i) {
        arr[i] = max_value;
    }

    trivial_tournament_sort((line){ .begin = arr, .end = arr + k});

    for (size_t i = 0; i < n; ++i) {
        at(l.begin, i) = arr[i];
    }

    free(arr);

}

Если нужны какие-то пояснения - пните. Автор: @bulat_paper_plane.

## 48 вопрос: Пирамидальная сортировка

**Пирамидальная сортировка** (или же *heapsort* - сортировка кучей) - это алгоритм сортировки, использующий максимальную или минимальную кучу.

Для начала несколько моментов:

*Максимальной (минимальной)* **кучей** называют структуру данных, представляющую из себя двоичное дерево, в которой значение каждой вершины больше (меньше) значений его детей.

Хипизацией (от слова *heap*, а не ~~хиппи~~) будем называть приведение произвольного двоичного дерева к виду кучи.

Для того, чтобы не описывать новую структуру данных, пронумеруем вершины двоичного дерева следующим образом: корень дерева будет под индексом 0, левое дерево вершины с идексом $i$ будет под индексом $2i + 1$, правое - под индексом $2i + 2$. Тогда двоичное дерево получится представить в виде линейного массива.

**Пирамидальная сортировка** выполняется в два этапа:

1. Хипизация изначального массива (с учетом обговоренной интепретации двоичного дерева на массив);
2. Просеивание кучи с выборкой элементов в порядке их расположения в отсортированном виде.

Ниже приведен код реализации пирамидальной сортировки, а под ним - пояснение.

heapsort.c

#include <inttypes.h>
#include <stdlib.h>

#define templ_type int64_t

typedef size_t uint64_t;

#define at(i) *(begin + i)

void swap(templ_type* a, templ_type* b) {
    templ_type t = *a;
    *a = *b;
    *b = t;
}

void heapify(templ_type* begin, templ_type* end, templ_type* root) {
    // left and right child pointer
    templ_type* left = begin + (root - begin) * 2  + 1;
    templ_type* right = left + 1;

    // pointer to node with largest value
    templ_type* largest = root;

    // finding node with largest value between root, it's left and right child
    if (end - left > 0 && *left > *largest) {
        largest = left;
    }
    if (end - right > 0 && *right > *largest) {
        largest = right;
    }

    // if there're nothing to change, then skip
    // otherwise swap node with largest value and root and then
    // go forward to changed node
    if (largest != root) {
        swap(root, largest);
        heapify(begin, end, largest);
    }
}

void heap_sort(templ_type* begin, templ_type* end) {
    size_t n = end - begin;
    // convert given linear binary tree to heap 
    for (size_t i = 0; i < n/2; ++i) {
        heapify(begin, end, begin + (n/2 - 1 - i));
    }
    // Put the largest element to the end and then 
    // sift through the remaining heap
    for (size_t i = 0; i < n; ++i) {
        swap(begin, end - i - 1);
        heapify(begin, end - i - 1, begin);
    }
}

Данная реализация пирамидальной сортировки использует линейное представление двоичного дерева, итерация по элементам производится при помощи итераторов (в данном случае, указателей).

**Функция heapify** приводит поддерево, начинающееся с данной вершины (root) к виду кучи, если левое и правое поддерево уже приведены к этому виду. Она принимает лианиаризированное двоичное дерево в виде двух указателей на начало (begin) и конец (end) массива (это указатель на следующий после последнего элемента адрес памяти), а также указатель на вершину (root).

**Принцип действия**: В случае, если значение вершины меньше значений его детей, то она меняется местами с наибольшей из дочерних вершин; далее процесс рекурсивно повторяется, переходя к измененной дочерней вершине (к другой дочерней вершине нет смысла переходить, т.к. по условию ее поддерево уже приведено к виду максимальной кучи).

**Функция heap_sort** сортирует данный массив. Она принимает в аргументы указатели на начало (begin) и конец (end - указатель на адрес после последнего элемента) массива и приводит его к отсортированному виду.

**Принцип действия**:
1. Приведенная выше нумерация позволяет интерпретировать массив как двоичное дерево;
2. Хипизация данного двоичного дерева;

Для хипизации произвольного двоичного дерева достаточно применить функцию heapify ко всем вершинам, начиная от предпоследнего слоя и заканчивая корнем, как это показано на 2 строке функции heap_sort.
3. В максимальной куче корневой элемент, обладающий максимальным значением, перемещается в конец массива, элемент, стоявший до этого в конце, помещается в корень. Затем двоичное дерево "обрубается" и последний (максимальный элемент, стоящий на своем месте) элемент в нем не участвует. Измененное дерево снова хипизирется, после чего процесс повторяется до полной сортировки изначального массива.

Сложность функции heapify - $O(\log_2n)$, количество просеиваний - $n$, следовательно, сложность пирамидальной сортировки - $O(n\log_2n)$.

## 49 вопрос: Гладкая сортировка

OK, listen here, my little bros. Now I'm gonna teach you how to smooth sort.

Гладкая сортировка считается ответвлением пирамидальной сортировки, ведь она действует по схожему принципу. Однако Эдскер Вибе Дейкстра разработал этот алгоритм так, что на частично отсортированных массивах гладкая сортировка апроксимирует к сложности $O(n)$.

Гладкая сортировка в своем алгоритме использует леонардовы кучи, так что для дальнейшего объяснения давайте для начала с ними познакомимся.

Итак, **числами Леонардо** называют рекурентную числовую последовательность, заданную следующим образом:

$L_0 = 1, L_1 = 1, L_k = L_{k - 1} + L_{k - 2} + 1$ $\forall k \geq 2$.

В итоге получается следующий ряд: $1, 1, 3, 5, 9, 15, 22$ и т.д.

*Лемма.* Любое натуральное число может быть представлено в виде суммы различных чисел Леонардо.

**Леонардовой кучей порядка $k$** называется двоичное дерево, количество вершин которой равно $k$-му числу Леонардо, у которого значение каждой вершины не меньше значений ее дочерних вершин (если они есть), левое и правое поддеревья которой есть леонардовы кучи ($k-1$ и $k-2$ порядков соответственно). Единичная вершина есть леонардова куча.

Итак, наконец-то переходим к самому *алгоритму*.

Т.к. каждое натуральное число можно выразить в виде суммы леонардовых чисел, любой массив может быть разбит на $k \leq n$ леонардовых куч, где $n$ - размер массива. Сама сортировка происходит в два этапа:

1. Построение леонардовых куч;
После этого этапа массив разделится на некоторое количество Леонардовых куч, притом порядок этих леонардовых куч будет строго убывать.
2. Декомпозиция леонардовых куч.
После этого этапа все леонардовы кучи будут декомпозированны и массив будет отсортирован.

*Построение леонардовых куч* происходит следующим образом:

1. Если порядок предыдущей кучи равен $1$, то очередной элемент превращается в леонардову кучу порядка $0$, притом если значения корней трех последних куч (вкючая только созданную) меняются так, чтобы они не убывали. Если значение корня третьей с конца кучи уменьшилось, она хипизируется (определение то же, что и в прошлом вопросе).
2. Иначе если порядки двух предыдущий куч смежны (т.е. порядок предыдущего $k-1$, а того, что за ним - $k$), то очередной элемент вместе с ними образует леонардову кучу порядка $k+1$, после эта куча хипизируется.
3. Иначе очередной элемент массива становится леонардовой кучей порядка $1$, если корень предыдущей кучи больше нового значения, они меняются местами, предыдущая куча хипизируется.

*Декомпозиция* происходит подобно первому этапу в обратном порядке.

1. Корень последней кучи является максимальным элементом среди значений всех куч. Изымаем его, в итоге последняя куча распадается на две меньших
2. Если корень третьей с конца леонардовой кучи больше корня предпоследней, меняем их местами, хипизируем третью с конца.
3. Если корень второй с конца леонардовой кучи больше корня последней, меняем их местами, хипизируем вторую с конца.

Повторяем эти три действия до тех пор, пока все вершины леонардового леса не будут изъяты.

Построение и декомпозиция наглядно проиллюстрированы в следующей [презентации](https://drive.google.com/file/d/1LVM5RvM37J2uV3Ilc0muwjETnEQ5Xi_B/view?usp=sharing), гляньте.

**Сложность алгоритма** в худшем случае составляет $O(n\log_2n)$, но если массив частично отсортирован, то тогда при хипизации леонардовой кучи глубина рекурсии будет небольшой. При полностью отсортированном массиве сложность алгоритма будет апроксимироваться до $O(n)$.

*Дополнительно*:

Леонардовы кучи можно линиаризовать, для этого достаточно знать ее порядок (или количество ее вершин):

1. Корень ставится в конец последовательности;
2. Правое поддерево записывается слева от корня;
3. Левое поддерево записывается слева от правого;
3. Леонардова куча первого или нулевого порядка записывается как значение ее единственной вершины.

Попробуйте, например, восстановить леонардову кучу из следующей последовательности: $1 - 2 - 3 - 4 - 6 - 0 - 5 - 7 - 8$. Получится одна из леонардовых куч из презентации.

Из этого факта следует, что алгоритм гладкой сортировки реализуем на массивах, притом из дополнительных данных понадобятся лишь указатели на корни леонардовых куч и их порядки (или количества их вершин).

Еще один факт: std::sort - сортировка из стандартной библиотеки C++ является композицией быстрой и гладкой сортировки. Когда глубина рекурсии быстрой сортировки превышает некоторый порог, запускается алгоритм гладкой.

## 51 вопрос: Сортировка слиянием

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

Итак, сам алгоритм:

1. Возьмем два указателя: $i$ и $j$, первый указывает на первый элемент первой последовательности, второй - на первый элемент второй.
2. Помещаем их значения в буфер. Меньшее станет первый элементом итоговой последовательности и будет убрано из буфера, большее останется в нем.
3. Указатель на убранный из буфера элемент сдвигаем вперед.
* Если он вышел за пределы соответствующей ему последовательности - дополняем итоговую последовательность оставшимися значениями из буфера, а за ними - другой последовательности.
* Иначе новое значение добавляем в буфер, переходим к шагу 2.

Сложность алгоритма, естественно, $O(n + m)$, где $n$ и $m$ - длинны данных последовательностей.

Давайте взглянем на алгоритм на примере:

Пусть даны две последовательности:
1. $a = \{21, 23, 24, 40\}$
2. $b = \{10, 11, 41, 42\}$

Проделаем шаги алгоритма:

1. $i_{(a)} = 0, j_{(b)} = 0$, buff $= \{21, 10\}$
$\Rightarrow c_0 = 10$, buff $= \{21\}$
2. $i = 0, j = 1$, buff $= \{21, 11\}$
$\Rightarrow c_1 = 11$, buff $= \{21\}$
3. $i_ = 0, j = 2$, buff $= \{21, 41\}$
$\Rightarrow c_2 = 21$, buff $= \{41\}$
4. $i = 1, j = 2$, buff $= \{41, 23\}$
$\Rightarrow c_3 = 23$, buff $= \{41\}$
5. $i_ = 2, j = 2$, buff $= \{41, 24\}$
$\Rightarrow c_4 = 24$, buff $= \{41\}$
6. $i = 3, j = 2$, buff $= \{41, 40\}$
$\Rightarrow c_5 = 40$, buff $= \{41\}$
6. $i = 3$, сдвигать некуда, значит дописываем в $c$ $41, 42$.

Итого: $c = \{10, 11, 21, 23, 24, 40, 41, 42\}.$

Этот алгоритм можно несколько модифицировать и использовать для сортировки неупорядоченных последовательностей.

Пусть задана некоторая последовательность

$$44 - 55 - 12 - 42 - 94 - 18 - 06 - 67$$

Разделим ее на две части

$$44 - 55 - 12 - 42\\
94 - 18 - 06 - 67$$

Теперь сольем эти две последовательности по упорядоченным парам

$$(44 - 94) - (18 - 55) - (06 - 12) - (42 - 67)$$

Теперь вновь разделим последовательность пополам и сольем упорядоченные пары

$$(06 - 12 - 44 - 94) - (18 - 42 - 55 - 67)$$

Далее сливаем эти две упорядоченные четверки и получаем остортированную последовательность.

Данный алгоритм является алгоритмом внешней сортировки.

Однократное слияние или разделение называют *фазой*, а пару фаз разделение-слияние - *проходом* или *этапом*.

Итак, количество фаз равно $\log_2 n$, при каждом разделении происходит слияние сложностью $O(n)$, тогда общая сложность алгоритма - $O(n \log_2 n)$.

## 52 вопрос: Сортировка естественным слиянием


## 53 вопрос: Анализ методов внутренней сортировки.



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


Итак, быстрая сортировка лучше гладкой во всех случаях, кроме упорядоченных массивов. (Здесь можете сказать про крутую std::sort, которая использует быструю сортировку, а когда глубина рекурсии заходит слишком далеко - гладкую)

## 54 вопрос: Анализ методов внешней сортировки.


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

# 55-56 вопрос: Модульное и процедурное программирование

## 55 Вопрос: Процедурное программирование


## 56 вопрос: Модульное программирование


# 57-64 вопрос: Тимпа ООП

## 57 вопрос: Абстракции в языках программирования
Абстракция - отвлечение от несущественного.

Абстракция в языках программирования - это один из способов сокрытия деталей реализации набора **функциональных возможностей**. Она применяется для управления сложностью проектируемой системы, когда система представляется в виде иерархии уровней абстракции. Абстракция широко отражается в *объектно-ориентированном программировании*.

Конкретный пример - класс "секунда", который абстрагирует тип число - то есть в программе специально показано, что передается именно "секунда", хоть внутри и находится просто число. (По-моему, это как раз что-то противоположное абстракции, т.к. в данном случае число наделяется дополнительным смыслом, а не абстрагируется от него)

Пример из структур данных, что мы расписывали - стек, реализованный на массиве *(вопрос 14)*. Класс стек - набор из 3 полей - размер стека, вместимость массива и сам массив. **На самом деле** можно было отдельно реализовать массив и его вместимость в отдельный класс вектор, тогда стек был бы абстракцией высшего уровня, чем вектор.

Пример иерархии абстракции: *(из методички)*

Подобная иерархия для нашего примера:

## 58 Вопрос: Абстрактные типы данных


> Вопросы с 59 по 64 отсутствуют(