Подготовка к зачёту (2020-12-09, среда)

--- tags: прога, зачёт по проге --- # Подготовка к зачёту (2020-12-09, среда) ## 1. Чтение сложного типа в Си Если вы мне дадите тип `void *(*f[])(void *(*)(void *(*)()[]))`, я вам без проблем скажу, что это тип массива указателей на функции, которые возвращают `void *` и принимают `void *(*)(void *(*)()[])` (указатель на функцию, которая возвращает `void *` и принимает указатель на функцию, которая принимает неопределённое число аргументов и возвращает массив указателей на `void *`) единственным аргументом. Придержите свою челюсть, это не магия, и тут всё очень просто. Сейчас расскажу как. Дано: `void *(*f[])(void *(*)(void *(*)()[]))`. Надо понять, откуда начинать развёртывать тип. Делается это так. 1. Читаем тип слева направо. Первым мы должны встретить какой-то **основной тип**. В примере это `void`. Может быть стракт, юнион, енам, инт какой-нибудь, каждый может быть вместе с `const`. 2. Дальше у нас идёт декларатор. > Формально говорить если (вдруг поможет), задаётся он так: > > - идентификатор — это декларатор > - `(декларатор)` — это декларатор > - `*декларатор` — это декларатор > - `декларатор-кроме-понтеров[размер]` — декларатор (`размер` может отсутствовать) > - `декларатор-кроме-поинтеров(тип без идентификаторов, тип без идентификаторов, ⋯)` — декларатор > > `декларатор-кроме-поинтеров` означает, что это любой декларатор, кроме вида `*декларатор`. 3. Если встретили идентификатор, останавливаемся здесь. 4. Если видим `*`, идём дальше. 5. Если видим `(`, идём внутрь. 6. Если встретили квадратную скобку, стопаемся перед ней. С места, где остановились, начинаем читать тип. В нашем примере: `void *(* | f[])(void *(*)(void *(*)()[]))` — на месте чёрточки. Будем тип описывать постепенно. Кусочки я в кавычки записывать буду. Если справа идентификатор, то "переменная с этим именем имеет тип...". Иначе — "наш тип — это..." 1. Смотрим направо от уже прочитанного. - Там может быть `[]` — "...массив..." - Уходим в шаг 1. - Там может быть `(...)` — "...функция с параметрами внутри скобок и возвращающей..." - Уходим в шаг 1. - Там может быть закрывающаяся скобка `)` — тогда переходим ко 2 шагу. - Или мы могли дойти до конца типа, тогда тоже ко 2 шагу переходим. 2. Смотрим налево от уже прочитанного. - Там может быть `*` — "...указатель на..." - Уходим в шаг 2 - Там может быть `(` — goto step 1. - Там может стоять основной тип. "...основной тип." Мы дошли до конца, выходим. Попробуем. Прочитано | Номер шага | Видим | Кусочек описания типа :---------------------------------------------------------------------------------|:----------:|:--------------------|:---------------------------------------------------------- <code>void \*(\*f[])(void \*(\*)(void \*(\*)()[]))</code> | 0 | Идентификатор `f` | Переменная с именем `f` имеет тип... <code>void \*(\*f[])(void \*(\*)(void \*(\*)()[]))</code> | 1 | `[]` | ...массива... <code>void \*(\*f[])(void \*(\*)(void \*(\*)()[]))</code> | 1 → 2 | `)` | ... <code>void \*(\*f[])(void \*(\*)(void \*(\*)()[]))</code> | 2 | `*` | ...указателей на... <code>void \*(\*f[])(void \*(\*)(void \*(\*)()[]))</code> | 2 → 1 | `(` | ... <code>void \*(\*f[])(void \*(\*)(void \*(\*)()[]))</code> | 1 | `(...)` | ...функции с параметрами внутри скобок и возвращающих... <code>void \*(\*f[])(void \*(\*)(void \*(\*)()[]))</code> | 1 → 2 | Конец типа | ... <code>void \*(\*f[])(void \*(\*)(void \*(\*)()[]))</code> | 2 | `*` | ...указатель на... <code>void \*(\*f[])(void \*(\*)(void \*(\*)()[]))</code> | 2 → конец | Основной тип `void` | ...`void`. Итак, переменная с именем `f` имеет тип массива указателей на функции с параметрами внутри скобок и возвращающих указатель на `void`. Чтобы узнать типы параметров, мы рекурсивно проходимся алгоритмом выше. Потренироваться: https://cdecl.org/ > Подсказывают, что невозможно в си создать функцию, которая возвращает массив. > > ```c > int id(int x[])[] { > return x; > } > ``` > > Этот код будет невалидным. Но тип корректен: функция, возвращающая `int[]`. ### 1.2. Запись сложного типа в Си Используя логику и алгоритм выше, мы можем записать тип любой сложности. Например, нужна функция `foo`, которая берёт указатель на функцию `(int x[]) -> void *` и возвращает его же. Как это записать? - Начинаем с имени: `foo`. - Дальше нужно сказать, что это функция, и мы добавляем: `foo(...)`. Вернёмся к содержимому позже, пока пойдём дальше. - Парсер типа поедет дальше вправо, чтобы узнать возвращаемый тип `foo`. Но чтобы подставить звёздочку, нужно его вернуть налево. Поэтому ставим в конце `)`: `foo(...))` — и парсер пойдёт налево от прочитанного до соответствующей `(`. - Ставим слева звёздочку: `*foo(...))`. У нас уже записано "foo — функция, возвращающая указатель на...". Теперь надо сказать, что указатель возвращает `foo` на функцию, а для этого парсер придётся отбросить вправо — скобочкой. `(*foo(...))`. - Парсер будет смотреть вправо от прочтённого, и туда мы закинем функцию: `(*foo(...))(...)`. - Теперь нам нужно снова записать указатель, для чего парсер должен вернуться назад. Можно снова поставить `)`, но если подумать, то вправо тип мы наращивать уже не будем, поэтому если ничего не ставить, то парсер и так влево возращаться будет. - Накидываем теперь влево оставшееся. Сначала "...возвращающую указатель на..." — `*(*foo(...))(...)`. Парсер всё ещё на 2 шаге алгоритма, что нам и нужно. Допишем основной тип: `void *(*foo(...))(...)`. - Мы получили такое: "`foo` — функция, возвращающая указатель на функцию, возвращающую указатель на `void`". Заполним пропуски на месте `...`. - Параметр у `foo` единственный. Назовём его `func`. Это указатель (`*func`) на функцию (`(*func)(...)`), берущую массив интов (`(*func)(int [])`) и возвращающую `void *` (`void *(*func)(int [])`). - Во втором пропуске параметры функции, которую плюёт `foo`, — это `int []`, поэтому так и запишем: `void *(*foo(void *(*func)(int [])))(int [])`. Вуаля. Мы получили нужный тип. Можем теперь дописать содержимое: ```c void *(*foo(void *(*func)(int [])))(int []) { return func; } ``` ## 2. BFS Код, который написали, внизу. Поговорили про такие вещи: - BFS = Breadth-first search — обход в ширину — дерево обходит послойно: сначала первый слой, потом второй и т. д. - Есть вот такая взаимосвязь: - Для DFS нужен **стэк**. - Стэк — это LIFO (last in, first out) структура данных. - Мы кладём (push) данные в один конец и достаём (pop) их оттуда же. - Получается, что забираем последний добавленный элемент. - Бытовая визуализация — стопка тарелок: добавляем новые мы поверх и сверху же берём их. - Для BFS нужна **очередь**. - Очередь — это FIFO (first in, first out) структура данных. - Мы кладём (enqueue) данные в один конец, а достаём (dequeue) с другого. - Получается, что первый элемент, который в очередь заехал, первым же оттуда и выйдет. - Бытовая визуализация — обычная линейная очередь: кто первый пришёл, тот первый попадёт. <table> <thead> <tr> <th>Очередь</th> <th>Стэк</th> </tr> </thead> <tbody> <tr> <td><a href="https://commons.wikimedia.org/wiki/File:Data_Queue.svg#/media/File:Data_Queue.svg"><img src="https://upload.wikimedia.org/wikipedia/commons/thumb/5/52/Data_Queue.svg/1200px-Data_Queue.svg.png" alt="Data Queue.svg"></a> By <a href="https://upload.wikimedia.org/wikipedia/commons/5/52/Data_Queue.svg" class="internal" title="Data Queue.svg">This Image</a> was created by <a href="https://en.wikipedia.org/wiki/User:Vegpuff" class="extiw" title="en:User:Vegpuff">User:Vegpuff</a>. - Own work, <a href="https://creativecommons.org/licenses/by-sa/3.0" title="Creative Commons Attribution-Share Alike 3.0">CC BY-SA 3.0</a>, <a href="https://commons.wikimedia.org/w/index.php?curid=7586271">Link</a></td> <td><a href="https://commons.wikimedia.org/wiki/File:Tallrik_-_Ystad-2018.jpg#/media/File:Tallrik_-_Ystad-2018.jpg"><img src="https://upload.wikimedia.org/wikipedia/commons/1/19/Tallrik_-_Ystad-2018.jpg" alt="Tallrik - Ystad-2018.jpg"></a> By Foto: Jonn Leffmann, <a href="https://creativecommons.org/licenses/by/3.0" title="Creative Commons Attribution 3.0">CC BY 3.0</a>, <a href="https://commons.wikimedia.org/w/index.php?curid=67631269">Link</a></td> </tr> </tbody> </table> - В DFS мы обычно стэк вручную не делаем потому, что используем рекурсию. - Есть понятие стэка вызовов: при вызове функции она кладётся в стэк и в любой момент времени исполняется та функция, которая в его верхушке. - Пример: `foo() -> bar() -> baz() -> eggs()`. Верхушка — `eggs()`, и она же и будет исполняться, остальные спят. - Чтобы неявно задать очередь, нужно использовать `goto` или корутину. Первое — моветон, а второго в сишечке нету. - Поэтому очередь придётся делать вручную. - Очередь можно соорудить двумя способами: - Через связные списки. - Довольно удобно по сравнению с другим способом. - Достаточно односвязного списка. - Нужно хранить указатель на начало списка, откуда удалять элементы, и на конец, куда добавлять. - Через дек — сложно, но если дек уже есть, то можно использовать. - Мы сделаем очередь на связном списке. - Алгоритм BFS: 1. Берём корень, кладём в очередь. 2. В цикле, пока очередь не пуста: 3. Берём первую ноду из очереди. 4. Помещаем детей ноды в очередь: сначала левый, потом правый. 5. Обрабатываем ноду — произвольная логика. 6. GOTO 2. ```c typedef struct tree { struct tree *left; struct tree *right; int value; } tree_t; // Нужен BFS (breadth-first search). // // DFS — стэк (юзаем рекурсию вместо явного стэка) // BFS — очередь (корутина или goto) // // Стэк вызовов: foo() -> bar() -> baz() -> eggs() // Чтобы сделать BFS, нам по-любому нужна очередь. // Очередь можно делать 2 путями: через связный список и через кольцевой буфер. // Делаем через связные списки, потому что это проще. typedef struct node_list { tree_t const *node; struct node_list *next; } node_list_t; // Вставить значение в связный список после данного. void list_insert_after(node_list_t **head, int value); // Удалить значение из списка. void list_remove(node_list_t **head); // Очередь — структура данных, в которой: // - элементы *помещаются* в один конец // - элементы *выдёргиваются* с другого конца // // queue_new(): ø // enqueue(1): 1 // enqueue(2): 1 → 2 // enqueue(3): 1 → 2 → 3 // dequeue(): 2 → 3, получаем 1 // dequeue(): 3, получаем 2 // dequeue(): ø, получаем 3 // // FIFO = First-in-first-out // (Стэк = LIFO — Last-in-first-out) typedef struct { node_list_t *start; node_list_t *end; size_t len; } queue_t; queue_t queue_new() { queue_t result = { .start = NULL, .end = NULL, .len = 0, }; return result; } void enqueue(queue_t *self, int value) { assert(self != NULL); list_insert_after(&self->end, value); ++self->len; if (self->len == 1) { // Было ø, стал список из 1 элемента self->start = self->end; } // Иначе всё ок: // 1 │ 1 → 2 // ├ end │⇒ │ └ end // └ start │ └ start } tree_t const *dequeue(queue_t *self) { assert(self != NULL); int result = self->start->value; list_remove(&self->start); --self->len; if (self->len == 0) { // Список опустел, потому что удалили элемент, на который указывали // self->start и self->end. Занулим self->end. self->end = NULL; } return result; } bool queue_is_empty(queue_t const *self) { return self->len == 0; } // Алгоритм: // 1. Берём корень, кладём в очередь. // 2. В цикле, пока очередь не пуста: // 3. Берём первую ноду из очереди. // 4. Помещаем детей ноды в очередь: сначала левый, потом правый. // 5. Обрабатываем ноду — произвольная логика. // 6. GOTO 2. void bfs(tree_t const *root) { queue_t *queue = queue_new(); // читается как "кью", спасибо французам enqueue(&queue, root); // ① while (!queue_is_empty(&queue)) { // ② tree_t const *node = dequeue(&queue); // ③ enqueue(&queue, node->left); // ④ enqueue(&queue, node->right); // ④ printf("%d\n", node->value); // ⑤ } // ⑥ } ``` ## 3. Обзор задачек ### 3.1. Поиск подстроки в строке Как делать `O(n²)`, понятно. `O(n)` — сложно, до экзамена доживёт. ### 3.2. Правильно ли расставлены скобки? **Дано:** `((()())))()()(()()()((())))` - Храним глубину — число открытых скобочек. - Идём по строке слева направо. - Видим `(` — увеличиваем глубину. - `)` — уменьшаем. - Если глубина 0 и встречаем `)`, то скобки расставлены неправильно. - Закрыли скобку, которую не открывали. - Если дошли до конца и глубина ненулевая, то скобки расставлены неправильно. - Не закрыли открытую скобку. ### 3.2.1. Правильно ли расставлены скобки разного типа? **Дано:** `(([[{{()}}]]))` **Или:** `(}` - Делать это стэком. - Каждую открывающую скобку пихаем в стэк. - Видим закрывающую — вытаскиваем из стэка и сверяем, что это тот же тип скобки. - Если не тот же, то скобки расставлены неправильно. - Закрыли не тот тип скобки. - Если стэк пуст, скобки расставлены неправильно. - Закрыли скобку, которую не открывали. - Когда дошли до конца, проверяем, что стэк пуст. - Если не пуст, то скобки расставлены неправильно. - Наоткрывали скобок, но не закрыли их. #### Стэк Структура данных, также известная как LIFO = Last in, first out. Пихаем (push) в один конец и оттуда же достаём (pop). Пример: - push(1): 1 - push(2): 1 → 2 - push(3): 1 → 2 → 3 - pop(): 1 → 2, получаем 3 - pop(): 1, получаем 2 - pop(): ø, получаем 1 Стэк делать обычным массивом динамическим. В конец массива добавляем новые элементы, оттуда же удаляем. ### 3.3. RLE Run-length encoding: `aaabbbbbbccd` ⇒ `3a6b2cd`. Вспоминаем, как делали (делали же?) вторую лабу, и делаем то же самое. Возможны вариации с форматом, но алгоритм тот же. Если надо читать из файла, то обработка ошибок — самая сложная часть: диск может накрыться, заблокироваться, быть удалённым, в файле может быть не цифра, где должна быть цифра, цифры может не быть, файл после числа внезапно может оборваться, число может не влезть в лонг-лонг... ### 3.4 Удаление заданных символов `testasdfasd34bsaeb` → `testasdfasdbsaeb` Самое сложное — понять, когда остановиться. `strlen` юзать не надо, проверять лучше на `'\0'`. ### 3.5 Сортировка (связного) списка Массивы — это 4 лаба. Связный список сортируется merge sort'ом. Массив делится рекурсивно пополам, пока не получим 2 массива по 1 элементу в каждому (или 1 массив из 1 элемента). Возвращаясь назад из рекурсии, мы сливаем по 2 упорядоченных списка за раз. ```c void merge(list_t *list1, list_t *list2); ``` Не забыть про то, что один из список может быть нулевым. Понять, какой из них такой, и вернуть другой. Если оба списка непусты, то выбираем один из них и сливаем другой в него. Правый опустеет, а левый потолстеет. Или наоборот. ### 3.6. Объединение двух упорядоченных связных списков См. `merge` сверху. Это он и есть. ### 3.7. Построение дерева по списку Есть такая вещь — двоичный поиск. Двоичное дерево поиска запечатлевает все пути алгоритма во время двоичного поиска. > Двоичное дерево поиска (BST) — это дерево, в котором **все** элементы левого поддерева меньше значению сверху, а **все** элементы правого поддерева больше этого значения. > > ``` > 3 > 1─┘ > └5 > ``` > > Это не BST, потому что пятёрка в левом поддереве тройки, хотя 5 ≮ 3. > > > Возможны вариации на тему одинаковых элементов. Обычно дупликаты не хранят, но можно всунуть в одно из поддеревьев. Алгоритм следующий: 1. Берём середину упорядоченного списка. 2. Рекурсивно обрабатываем часть слева и часть справа. Слева — в левое поддерево, справа — в правое поддерево помещаем. Не забыть вовремя остановиться. ### 3.8. Сравнение 2 деревьев Без понятия, что за задача такая. Возможно, нужно сказать, являются ли все элементы первого дерева меньшими всех элементов правого дерева. На проге в среду разберёмся. ### 3.9. Копирование дерева Есть одно дерево, надо сделать второе с теми же элементами. Делается обходом в глубину. Можно префиксный использовать, так, наверное, красивее. - Префиксный (pre-order DFS): ``` process(x) dfs(left(x)) dfs(right(x)) ``` - Инфиксный (in-order DFS): ``` dfs(left(x)) process(x) dfs(right(x)) ``` - Постфиксный (post-order DFS): ``` dfs(left(x)) dfs(right(x)) process(x) ``` Сигнатура функции-копировальщика такая: ```c tree_t *copy(tree_t const *original); ``` ### 3.10 Задачи про `void *` Просто 4 лаба. Если надо, могу рассказать подробнее. ### 3.10.1. Сортировка простая Пузырьком, insertion sort, selection sort. Вспомнить алгоритм и записать в обобщённом виде. Полезно выделить индексацию и своп в отдельные функции. ### 3.11 Вопросы по теории #### 3.11.1. Раздельная компиляция, использование заголовочных файлов. Объявления и определения функций и переменных Сурс-файлы компилируются отдельно и затем только объединяются в один бинарь. Чтобы код из одного файла можно было юзать в другом, не копируя объявления постоянно, используем хедеры. **Хедер должен начинаться с инклюд-гарда (include guard)!** Есть два варианта: 1. ```c #ifndef SORT_H // ← #include <stddef.h> void sort(void *array, size_t size, size_t len); // ... #define SORT_H // ← #endif // ← ``` 2. ```c #pragma once // ← #include <stddef.h> void sort(void *array, size_t size, size_t len); // ... ``` Оба варианта проверяют, инклюдился ли уже в этой единице трансляции хедер. Если да, то инклюд раскроется в пустой код. Если инклюдится впервые, то содержмое хедера подставится. #### 3.11.2 Ошибки компиляции, линковки, понятие типа и ошибки типизации Сборка бинаря из сырцов — процесс многоступенчатый. ``` [C source files] ---preprocessing---> [translation unit] ---compilation---> [object files] ---linking---> [executable] ``` ##### Препроцессор Обрабатывает директивы препроцессора: ```c #define ANSWER 42 #define SUM(x, x) ((x) + (x)) #pragma once #error "error message" #include "..." #include <...> #if #ifdef #undef #else #elseif ``` Дефайны подставляются, комментарии удаляются. Строки с `\` в конце объединяются. Например, вот такой код: ```c int \ main( \ ) { return 0; } ``` ...после препроцессора превратится в ```c int main( ) { return 0; } ``` > С помощью директив препроцессора можно собирать разный код в зависимости от платформы. > Например, если при сборке для винды компилятор запускать как-то так: > > ``` > gcc -DWINDOWS input.c -o input.exe > ``` > > ...то внутри кода можно использовать наличие дефайна. > > ```c > #ifdef WINDOWS > int do_something() { > // this code will only be run on Windows > return 1; > } > #else > int do_something() { > // on other platforms > return 0; > } > #endif > ``` > Директива `#include` тупо берёт содержимое файла и подставляет. > > Допустим, в `data.txt` мы написали: > > ``` > 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 > ``` > > Теперь можно сделать так: > > ```c > int const data[] = { > #include "data.txt" // ← > }; > > int main() { > printf("%d\n", data[3]); //> 4 > return 0; > } > ``` Файл после обработки препроцессором называется **единицей трансляции**. В нём нет директив препроцесса (что начинается с `#`), `\` и комментов. ##### Компиляция Компилятор делает семантический анализ: например, проверяет типы. Здесь он замечает ошибки типизации: неверный тип используется. ```c int x = printf; // ☝ ошибка типизации: // в `int` пихаем `int (*)(const char *restrict format, ...)`. ``` Возможна ещё огромная куча разных ошибок, которые компилятор может встретить и выдать. Например, синтаксическую ошибку из-за кода вроде такого: ```c int привет, вася!() = 42. ``` Все эти ошибки называются **ошибками компиляции**. После компиляции мы получаем объектный файл — по одному на каждую единицу трансляции. ```c int test(); // вот эта строка приехала к нам из #include <stdio.h> // (вместе с кучей других, конечно) int printf( const char *restrict format, ... ); ``` В объектном файле на месте адресов, про реализации которых мы ничего пока не знаем (например, `test` и `printf`), стоят затычки. ##### Линковка Линкер берёт кучу объектных файлов, склеивает их в один бинарник, заменяя затычки на реальные адреса. Есть 2 вида линковки: - **статическая:** берётся библиотека и копипастится в бинарь - **динамическая:** линкер оставляет заметку в бинарнике, чтобы при запуске его операционная система автоматом подключила библиотеку, но содержимого этой библиотеки нету Если линковщик видит затычку, а функции под неё не видит, он выдаст ошибку. Например, если мы в коде сверху `test` так и не определим, линкер на нас нажалуется. Эти ошибки называются **ошибками линковки**. И их обычно весьма сложно читать.