---
tags: прога, зачёт по проге
---

# Задачи с зачёта (2020-12-10, четверг)
**АХТУНГ:** копипаст кода отсюда тождественно равно получению пермабана. Семинарист мой код спалит моментально — быстрее, чем свет до него дойдёт, от листочка отразившись. Никто так не упарывается с красотой и декомпозицией.
Весь код даётся только в образовательных целях, чтобы понять, куда рыть. Алгоритмы вы будете писать на нелинованных листочках A4 ручкой, простыню убьётесь копировать.

**ДИСКЛЕЙМЕР:** Ответы могут быть несущественно, заметно, разительно или полностью и в корне неверными. Если ошибки есть, то виноваты все, кроме меня. Но можете написать, и я исправлю.

## Задача 1. Область видимости и время жизни
> Классифицируйте виды переменных по области видимости и по времени жизни. Приведите примеры.

### Времена жизни переменных
Время жизни переменной — это промежуток времени, когда для переменной выделена память. Время жизни тесно связано с видом хранения объекта.

- **Автоматическое**: начинается с момента входа в блок, в котором определена переменная, и завершается после выхода из него.

  int main() {
      int x = 42; // автоматическое хранение
      return 0;
  }

- **Статическое**: начинается до начала исполнения программы и длится до её завершения.

  // вне функций
  static int x = 42;
  
  // Если static внутри блока, то срок жизни - от первого
  // захода в блок до завершения работы программы
  int main() {
      static int y = 24;
      return 0;
  }
  // Например, скрок жизни a - ноль
  void func() {
      if (false) {
          static int a = 5;
      }
  }

- **Потоковое**: на протяжении работы потока.

  // Это можно пропустить, если скажете - ожидайте
  //  доп.вопросов про потоки
  thread_local int my_id = 0;

### Область видимости переменных
- **Блок**: внутри блока, в том числе во вложенных блоках, с момента объявления.

  int main() {
      int x = 0; // виден в блоке
      return 0;
  }

- **Файл**: внутри единицы трансляции с момента объявления.

  static int x = 42;
  
  int main() {
      printf("%d\n", x);
      return 0;
  }

  // Например, если в code.c написать
  #include "code.h"
  static int c = 1;
  // то в main.c нельзя будет ею пользоваться
  int main() {
      extern int c;
      c++;
  }
  // Но если написать в code.c просто
  #include "code.h"
  int c = 1;
  // То в main.c код выше будет исполняться

### Референсы
- https://en.cppreference.com/w/c/language/scope
- https://en.cppreference.com/w/c/language/storage_duration

## Задача 2. Типизация
> Что такое типизация? Какие проверки типизации делает компилятор? Приведите примеры ошибок типизации.

Типизация — классификация значений по типам. Тип — множество значений и операции над ними. В C тип объекта определяет, как интерпретировать значение в памяти.

Компилятор узнаёт, можно ли выполнить операцию над объектом в коде, проверяя тип объекта. Например, нельзя присвоить в переменную типа стракта число:

struct test {
    int value;
};

int main() {
    struct test my_struct = 42;
    return 0;
}

Другой пример: попытка использовать `->` для чего-то, кроме указателя:

struct test my_struct;
my_struct->value = 42;

## Задача 3. Дополнительный код
> Даны два signed char, в один присвоили -72, в другой -113. Запишите их в двоичной системе счисления и в шестнадцатеричной. Приведите вычисления.

- `-72` = `0b10111000` = `0xb8`
1. Переведём `72` в двоичную систему счисления: `0b01001000`.
2. Инвертируем все биты: `0b10110111`.
3. Прибавим единичку: `0b10111000`.
- `-113` = `0b10001111` = `0x8f`
1. Переведём `113` в двоичную систему счисления: `0b01110001`.
2. Инвертируем все биты: `0b10001110`.
3. Прибавим единичку: `0b10001111`.

## Задача 4. Запись сложных типов
> Запишите следующие типы (без использования `typedef`):
> - указатель на константный указатель на целое число
> - ???
> - указатель на массив указателей на целое число
> - указатель на любую функцию
> - указатель на функцию, принимающую указатель на функцию, которая возвращает указатель на функцию
> > Не совсем так
> >
> > > Возможно. [name=slowlime]

int *const *one;
int *(*three)[];
int (*four)();
void (*five)(void (*(*)())());

### Референсы
- https://hackmd.io/@slowlime/B1esMNpiv#1-%D0%A7%D1%82%D0%B5%D0%BD%D0%B8%D0%B5-%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D0%B3%D0%BE-%D1%82%D0%B8%D0%BF%D0%B0-%D0%B2-%D0%A1%D0%B8
- https://en.cppreference.com/w/c/language/declarations

## Задача 5. Чтение сложных типов
> Опишите словами следующий тип:
> ```c
> int (*(*f(void))[])(void);
> ```

`f` — это функция с 0 параметров, возвращающая указатель на массив указателей на функции с 0 параметров и возвращающие `int`.

## Задача 6. Бинарный поиск
> Напишите двоичный поиск. Код должен уметь работать с любыми типами данных.
> Приведите пример вызова для int, double, строк и произвольных структур.

void const *bsearch(void const *array, void const *key,
                    size_t size, size_t len,
                    int (*comparator)(void const *, void const *)) {
    assert(array != NULL);
    assert(key != NULL);
    assert(size > 0);
    assert(comparator != NULL);
    
    char const *bytes = array;
    size_t left = 0;
    size_t right = len;
    
    while (left < right) {
        size_t middle = left + (right - left) / 2;
        void const *element = (void const *) bytes[middle * size];
        int cmp = comparator(element, key);
        
        if (cmp < 0) {
            left = middle + 1;
        } else if (cmp > 0) {
            right = middle;
        } else {
            return element;
        }
    }

    return NULL;
}

int int_cmp(void const *left_ptr, void const *right_ptr) {
    assert(left_ptr != NULL);
    assert(right_ptr != NULL);

    int left = *(int const *) left_ptr;
    int right = *(int const *) right_ptr;
    
    if (left < right) {
        return -1;
    } else if (left > right) {
        return 1;
    }
    
    return 0;
}

int string_cmp(void const *left_ptr, void const *right_ptr) {
    assert(left_ptr != NULL);
    assert(right_ptr != NULL);
    
    char const *left = *(char const **) left_ptr;
    char const *right = *(char const **) right_ptr;
    
    return strcmp(left, right) == 0;
}

int double_cmp(void const *left_ptr, void const *right_ptr) {
    assert(left_ptr != NULL);
    assert(right_ptr != NULL);

    double left = *(double const *) left_ptr;
    double right = *(double const *) right_ptr;
    
    if (left < right) {
        return -1;
    } else if (left > right) {
        return 1;
    }
    
    return 0;
}

struct test {
    int value;
};

int struct_cmp(void const *left_ptr, void const *right_ptr) {
    assert(left_ptr != NULL);
    assert(right_ptr != NULL);

    struct test const *left = (struct test const *) left_ptr;
    struct test const *right = (struct test const *) right_ptr;
    
    if (left->value < right->value) {
        return -1;
    } else if (left->value > right->value) {
        return 1;
    }
    
    return 0;
}

int main() {
    int int_array[] = {1, 2, 3, 4, 5};
    printf("int_array: %d\n", *(int const *) bsearch(
        int_array, &int_array[2],
        sizeof(int_array[0]), sizeof(int_array) / sizeof(int_array[0]),
        int_cmp
    ));
    
    double double_array[] = {1., 2., 3., 4., 5.};
    printf("double_array: %lf\n", *(double const *) bsearch(
        double_array, &double_array[2],
        sizeof(double_array[0]), sizeof(double_array) / sizeof(double_array[0]),
        double_cmp
    ));
    
    char const *string_array[] = {"hello", "goodbye", "world", "space"};
    printf("string_array: %s\n", *(char const **) bsearch(
        string_array, &"world",
        sizeof(string_array[0]), sizeof(string_array) / sizeof(string_array[0]),
        string_cmp
    ));
    
    struct test struct_array[] = {{1}, {2}, {3}, {4}, {5}};
    printf("struct_array: {%d}\n", ((struct test *) bsearch(
        struct_array, &struct_array[2],
        sizeof(struct_array[0]), sizeof(struct_array) / sizeof(struct_array[0]),
        struct_cmp
    ))->value);
    
    return 0;
}

## Задача 7. Очередь
> Реализуйте очередь на списке.

typedef struct list {
    int value;
    struct list *next;
} list_t;

list_t *list_new() {
    return NULL;
}

bool list_insert_after(list_t **self, int value) {
    assert(self != NULL);
    
    list_t *node = malloc(sizeof(list_t));
    
    if (node == NULL) {
        return false;
    }
    
    node->value = value;
    
    if (*self != NULL) {
        node->next = (*self)->next;
        (*self)->next = node;
    } else {
        node->next = NULL;
    }
    
    *self = node;
    
    return true;
}

bool list_decapitate(list_t **self) {
    assert(self != NULL);
    
    if (*self == NULL) {
        return false;
    }
    
    list_t *head = *self;
    list_t *next = head->next;
    free(head);
    *self = next;
    
    return true;
}

typedef struct {
    list_t *start;
    list_t *end;
    size_t len;
} queue_t;

queue_t queue_new() {
    queue_t result = {
        .start = list_new(),
    };

    result.end = result.start;
    
    return result;
}

bool queue_is_empty(queue_t const *self) {
    assert(self != NULL);

    return self->len == 0;
}

bool queue_enqueue(queue_t *self, int value) {
    assert(self != NULL);
    
    if (!list_insert_after(&self->end, value)) {
        return false;
    }
    
    if (queue_is_empty(self)) {
        self->start = self->end;
    }
    
    ++self->len;
    
    return true;
}

bool queue_dequeue(queue_t *self, int *result) {
    assert(self != NULL);

    if (queue_is_empty(self)) {
        return false;
    }
    
    int value = *list_get_value(self->start);

    if (!list_decapitate(&self->start)) {
        return false;
    }

    if (result != NULL) {
        *result = value;
    }
    
    if (self->len == 1) {
        self->end = self->start;
    }
    
    --self->len;
    
    return true;
}

Этот код я писал вручную и на листочке. Надеюсь, понятно, чем я 2 часа занимался.

### Референсы
- https://hackmd.io/@slowlime/B1esMNpiv#2-BFS

## Задача 8. Successor в дереве
> Напишите функцию, которая возвращает следующий за данным элемент дерева при инфиксном обходе. Считайте, что узлы хранят указатель на родителя.

typedef struct node {
    struct node *parent;
    struct node *left;
    struct node *right;
} node_t;

bool is_left_child(node_t const *node) {
    return node->parent != NULL && node->parent->left == node;
}

node_t *successor(node_t *node) {
    if (node == NULL) {
        return NULL;
    }
    
    if (node->right != NULL) {
        node_t *leftmost_node = node;
        
        while (leftmost_node->left != NULL) {
            leftmost_node = leftmost_node->left;
        }
        
        return leftmost_node;
    }
    
    node_t *result_child = node;
    
    while (result_child->parent != NULL) {
        if (is_left_child(result_child->parent)) {
            return result_child->parent;
        }
        
        result_child = result_child->parent;
    }
    
    return NULL;
}

## Задача 9. Анаграммы
> Напишите функцию, которая проверяет, являются ли две строки анаграммами друг друга.

Две строки — анаграммы, если они состоят из тех же символов в том же количестве.

bool is_anagram(char const *left, char const *right) {
    assert(left != NULL);
    assert(right != NULL);
    
    size_t count_left[256] = {0};
    size_t count_right[256] = {0};
    memset(count_left, 0, sizeof(count_left));
    memset(count_right, 0, sizeof(count_right));
    
    char const *lptr = left;
    char const *rptr = right;
    
    while (true) {
        if (*lptr == '\0' && *rptr == '\0') {
            break;
        }
        
        if (*lptr == '\0' || *rptr == '\0') {
            return false;
        }
        
        ++count_left[*(lptr++)];
        ++count_right[*(rptr++)];
    }
    
    for (size_t i = 0; i < 256; ++i) {
        if (count_left[i] != count_right[i]) {
            return false;
        }
    }
    
    return true;
}

## Задача 10. Связывание
> В `code.c` объявляются две функции: `f`, `g` — и две глобальные переменные: `a`, `b`. `f` и `a` должны быть видны из других единиц трансляции; `g`, `b` нужно скрыть, чтобы их не было видно из других единиц трансляции. Приведите код `code.c` и `code.h`.

Код `code.c`:

void f();
static void g();

int a;
static int b;

Код `code.h`:

#pragma once

void f();
extern int a;

### Референсы
- https://en.cppreference.com/w/c/language/storage_duration#Linkage

## Задача 11. Поиск ошибок в коде
> Отметьте ошибки в коде и прокомментируйте их.
>
> ```c
> #define MAX(a, b) a < b ? a : b;
>
> void main() {
> char *str = malloc(1);
> int i; char c; int ws_counter;
>
> while (c = getchar() != EOF) {
> str[++i] = c;
> str = realloc(str, i);
> }
>
> printf(str);
>
> for (i = 0; i < strlen(str); ++i); {
> ws_counter += str[i] == ' ';
> }
>
> int limit;
> print("Enter whitespace limit:\n");
> scanf("%d", limit);
>
> /* do The Check */
> if (MAX(limit, ws_counter) == ws_counter) {
> printf("Too much!\n");
> } else if (MAX(limit, ws_counter) == limit) {
> printf("Not enough!\n");
> } else if (limit == ws_counter) {
> printf("OK!\n");
> }
> };
> ```

Строки с ошибкой отмечены числами в кружочке.

#define MAX(a, b) a < b ? a : b; // ①

void main() { // ②
    char *str = malloc(1);
    int i; char c; int ws_counter; // ③

    while (c = getchar() != EOF) { // ④
        str[++i] = c; // ⑤
        str = realloc(str, i); // ⑥
    }

    // ⑦
    printf(str); // ⑧

    for (i = 0; i < strlen(str); ++i); { // ⑨
        ws_counter += str[i] == ' ';
    }

    int limit; // ⑩
    print("Enter whitespace limit:\n"); // ⑪
    scanf("%d", limit); // ⑫

    /* do The Check */
    if (MAX(limit, ws_counter) == ws_counter) { // ⑬
        printf("Too much!\n");
    } else if (MAX(limit, ws_counter) == limit) {
        printf("Not enough!\n");
    } else if (limit == ws_counter) {
       printf("OK!\n");
    }
}; // ⑭

1. Во-первых, если используем параметризуемые макросы, вход надо оборачивать в скобки.
Во-вторых, `;` в конце не нужна и всё портит.
В-третьих, не `<`, а `>`.
В-четвёртых, от макроса вообще избавиться можно было. Но если оставить, то такой:

   #define MAX(a, b) ((a) > (b) ? (a) : (b))

2. `int main()` всё же. `int main()` и `int main(int argc, char *argv[])` стандарт разрешает, а остальное — implementation-defined, то есть бяка.

3. Инициализация переменных забыта. В переменных мусор! Оптимизатор вообще считать будет это неинициализированной памятью и может подсунуть туда что угодно. При этом оптимизировать все использования этой переменной он не будет, а мог бы!

4. Не тот приоритет у `=`, чтоб без скобок брать. Надо:

   while ((c = getchar()) != EOF) {

А ещё `c` типа `char`, а должен быть `int`, потому что `EOF` в `char` не влезает.

5. Если уж и использовать инкремент, то постфиксный: `i++`.

6. `realloc(str, i + 1)`. Плюс нет обработки ошибок.

7. Строка не терминирована NUL-байтом. Надо:

   str[i] = '\0';

8. Пихать в строку формата `printf` недоверенный инпут — верный способ стать инвалидом и внести в программу уязвимость. Надо:

   printf("%s", str);

9. У нас уже есть длина, кровью и потом посчитанная, — `i`. Зачем перезатирать переменную? Зачем `strlen` использовать? А вы в курсе, что я мог в инпут спокойно и `\0` кинуть, например? У вас в памяти 2 гига для строки выделено, а юзать будете только первые 10 байт. Потрясающе же. 👏

К слову, `;` там лишний.

10. Раз уж барин не соизволил проверять `scanf`, можно было хотя бы сюда `= 0` вписать.

11. `printf`

12. Нет обработки ошибок. Что будет, если:

- я не дам вообще ничего?
- я дам не число?
- я дам число и мусор?
- я дам слишком большое число?

А ещё `&limit`.

13. А если `ws_counter == limit`? Третью ветку первой надо ставить было. А лучше вообще сравнения.

14. `;` не нужна.