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

# Задачи с зачёта (2020-12-15, вторник)
**ДИСКЛЕЙМЕР:** Как прИнятО в СоВрЕМеННоМ МИрЕ, IN NO EVENT AND UNDER NOT LEGAL THEORY, WHETHER IN TORT (INCLUDING NEGLIGENCE), CONTRACT, OR OTHERWISE, UNLESS REQUIRED BY APPLICABLE LAW (SUCH AS DELIBERATE AND GROSSLY NEGLIGENT ACTS) OR AGREED TO IN WRITING, SHALL ANY CONTRIBUTOR TO THIS DOCUMENT BE LIABLE TO YOU FOR DAMANGES, INCLUDING ANY DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES OF ANY CHARACTER ARISING AS A RESULT OF THE USE OR INABILITY TO USE THE WORK (INCLUDING BUT NOT LIMITED TO DAMAGES FOR LOSS OF GOODWILL, WORK STOPPAGE, COMPUTER FAILURE OR MALFUNCTION, PERMANENT BAN BY THE INSTRUCTOR, OR ANY AND ALL OTHER COMMERCIAL AND ACADEMICAL DAMAGES OR LOSSES), OR FOR DISINFORMATION, MISTAKES, ERRORS, COMMITED DELIBERATELY AND OTHERWISE, EVEN IF SUCH CONTRIBUTOR HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES. (© http://www.apache.org/licenses/).

**АХТУНГ:** как и прежде, прочитывать этот документ можно, но копипастить отсюда на листок есть грех смертный и искупимый только баном. Мой код взрывоопасен, поэтому спалится он быстрее, чем вы орудием письма дотронетесь до пергамента.

## 1. Утечки памяти
> Что такое утечка памяти? Приведите несколько разных примеров кода.

Утечка памяти — отсутствие освобождения области динамически распределённой памяти после её использования. Например, отсутствие вызова `free`, соответствующему `calloc` / `malloc` / `realloc`.

Примеры:

- ```c
int main() {
for (size_t i = 0; i < 10; ++i) {
malloc(100500);
}

return 0;
}

- ```c
  int **array = calloc(100, sizeof(int *));
  for (size_t i = 0; i < 100; ++i) {
    array[i] = calloc(100, sizeof(int));
  }
  
  do_something(array, 100, 100);
  // отсутствуют вызовы free для содержимого array
  free(array);

## 2. Типизация
> Что такое типизация? Приведите примеры проверок, которые выполняет компилятор, и ошибок типизации в программах на Си

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

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

struct test {
    int value;
};

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

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

struct test my_struct;
my_struct->value = 42;

## 3. Дополнительный код
> Как будут представлены числа `-69`, `-117` в переменной типа `signed char` в дополнительном коде? Приведите вычисления. Напишите ответ в двоичной и шестнадцатеричной записи.

- `-69` = `0b10111011` = `0xbb`:
1. Переведём `69` в двоичную систему счисления: `0b01000101`.
2. Инвертируем все биты: `0b10111010`.
3. Прибавим единичку: `0b10111011`.
- `-117` = `0b10001011` = `0x8b`:
1. Переведём `117` в двоичную систему счисления: `0b01110101`.
2. Инвертируем все биты: `0b10001010`.
3. Прибавим единичку: `0b10001011`.

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

int *const *first;
int (*const second)[];
int (*third)();
int (*(*fourth)[])();
int (*(*(*fifth)())())();

## 5. Чтение сложных типов
> Что это за тип?
>
> ```c
> int (**f(void))(int (*)[1]);
> ```

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

## 6. Поиск
> Напишите функцию для поиска заданного элемента (нужно вернуть индекс элемента, если он найден, `-1` иначе) в массиве элементов произвольного типа. Приведите пример вызова вышей функции для массива целых, строк, каких-либо структур.

int search(void const *array, void const *key,
           size_t size, size_t len,
           bool (*eq)(void const *, void const *)) {
    assert(array != NULL);
    assert(key != NULL);
    assert(size > 0);
    assert(eq != NULL);

    char const *bytes = array;

    for (size_t i = 0; i < len; ++i) {
        if (eq(bytes + i * size, key)) {
            return i;
        }
    }
    
    return -1;
}

bool int_eq(void const *left, void const *right) {
    assert(left != NULL);
    assert(right != NULL);

    return *((int const *) left) == *((int const *) right);
}

bool string_eq(void const *left, void const *right) {
    assert(left != NULL);
    assert(right != NULL);
    
    char const *const *cast_left = left;
    char const *const *cast_right = right;

    return strcmp(*cast_left, *cast_right) == 0;
}

struct test {
    int value;
};

bool test_eq(void const *left, void const *right) {
    assert(left != NULL);
    assert(right != NULL);

    struct test const *cast_left = left;
    struct test const *cast_right = right;

    return cast_left->value == cast_right->value;
}

int main() {
    int int_array[] = {1, 2, 3, 4, 5};
    printf("%d\n", search(
        int_array, &int_array[2],
        sizeof(*int_array), sizeof(int_array) / sizeof(*int_array),
        int_eq
    ));
    
    char const *string_array[] = {"hello", "world", "yeah"};
    char *key = "world";
    printf("%d\n", search(
        string_array, &key,
        sizeof(*string_array), sizeof(string_array) / sizeof(*string_array),
        string_eq
    ));
    
    struct test test_array[] = {{1}, {3}, {5}};
    printf("%d\n", search(
        test_array, &test_array[2],
        sizeof(*test_array), sizeof(test_array) / sizeof(*test_array),
        test_eq
    ));
    
    return 0;
}

## 7. Инверсия битов
> Напишите функцию, инвертирующих биты числа (младший бит становится старшим и т. д.)
> ```c
> void invertBits(int *x) {
> ```

void invert_bits(int *x) {
    assert(x != NULL);
    size_t bits = sizeof(int) * 8;
    
    int result = 0;

    for (size_t i = 0; i < bits; ++i) {
        result <<= 1;
        result |= (*x >> i) & 0x1;
    }
    
    *x = result;
}

## 8. BFS
> Напишите функцию, которая распечатывает произвольное двоичное дерево «по слоям».

typedef struct node {
    struct node *left;
    struct node *right;
    int value;
} node_t;

typedef struct {
    node_t *node;
    size_t level;
} queue_item_t;

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

list_t *list_new() {
    return NULL;
}

queue_item_t *list_get_value(list_t *self) {
    assert(self != NULL);
    
    return self->value;
}

bool list_insert_after(list_t **self, queue_item_t *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, queue_item_t *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, queue_item_t *result) {
    assert(self != NULL);

    if (queue_is_empty(self)) {
        return false;
    }
    
    queue_item_t 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;
}

void print_tree(node_t *root) {
    if (root == NULL) {
        return;
    }

    queue_item_t root_item = {
        .node = root,
        .level = 0,
    };

    queue_t queue = queue_new();
    bool ok = queue_push(&queue, root_item);
    assert(ok);
    
    size_t level = 0;

    while (!queue_is_empty(&queue)) {
        queue_item_t node_data = NULL;
        bool ok = queue_pop(&queue, &node_data);
        assert(ok);
        
        while (level < node_data->level) {
            printf("\n");
            level++;
        }

        printf("%d ", node_data->node->value);
        
        if (node->left != NULL) {
            queue_item_t child_data = {
                .node = node->left,
                .level = level + 1,
            };
            ok = queue_push(&queue, child_data);
            assert(ok);
        }

        if (node->right != NULL) {
            queue_item_t child_data = {
                .node = node->right,
                .level = level + 1,
            };
            ok = queue_push(&queue, child_data);
            assert(ok);
        }
    }
    
    printf("\n");
}

## 9. Общие элементы
> Напишите функцию, строящую новый список из чисел, которые входят в оба упорядоченных списка — аргументы функции. Пример: для список `1 → 2 → 3 → 4` и `2 → 4 → 7 → 10` получится список `2 → 4`:
>
> ```c
> struct list *intersection(struct list *l1, struct list *l2) {
> ```

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

struct list *intersection(struct list *l1, struct list *l2) {
    struct list *head = NULL;
    struct list **end = &head;

    struct list *left = l1;
    struct list *right = l2;

    while (true) {
        if (left == NULL || right == NULL) {
            break;
        }
        
        if (left->value < right->value) {
            left = left->next;
        } else if (left->value > right->value) {
            right = right->next;
        } else {
            *end = malloc(sizeof(struct list));
            (*end)->value = left->value;
            (*end)->next = NULL;
            end = &(*end)->next;
        }
    }
    
    return head;
}

## 10. Объявления и определения
> Чем отличается объявление (declaration) от определения (definition) в Си? Приведите пример объявления (но не определения) функции и переменной.

Declaration — объявление нового идентификатора с указанием его типа.

Definition — это вид объявления, который полностью определяет идентификатор, например:

- указывается тело функции;
- указывается содержимое структур или объединений;
- объявляется не-`extern` переменная.

int hello(void);

extern const int *start_address;

## 11. Поиск ошибок
> Отметьте и поясните проблемы, ошибки, недочёты в данном коде.
>
> ```c
> bool check(char * s) {
> if(*s != '%')
> {
> return 1;
> } else {
> return 0;
> }};
>
> void main(int arg, char * argv) {
> char * str = (char*)malloc(123);
> FILE * f = fopen(argv[0], "rw");
> int limit = itoa(argv[1]);
> int count = 0;
> /*Read lines and count ones beginning with %. Check only first 'limit' lines.*/
> for(int i = 0; i <= limit; ++i); {
> fscanf(f, "%s", &str);
> printf("Entered string: %s", s);
> if(!check(str) )
> {
> printf("WRong input! Input don't start with '%'!");
> return;
> }
> count++;
> }
> prinf("Result: %i lines in file %s begin with '%' symbol\n", count);
> }
> ```

bool check(char * s) { // ①
  // ②
  if(*s != '%')
  { // ③
   return 1; // ④
  } else {
   return 0; // ④
  }}; // ⑤

void main(int arg, char * argv) { // ⑥ ⑦
  char * str = (char*)malloc(123); // ⑧
  FILE * f = fopen(argv[0], "rw"); // ⑨ ⑩ ⑪ ⑫
  int limit = itoa(argv[1]); // ⑩ ⑪ ⑬
  int count = 0;
  /*Read lines and count ones beginning with %. Check only first 'limit' lines.*/
  for(int i = 0; i <= limit; ++i); { // ⑭ ⑮
    fscanf(f, "%s", &str); // ⑯ ⑰ ⑱
    printf("Entered string: %s", s); // ⑰ ⑲
    if(!check(str) ) // ⑳
    {
        printf("WRong input! Input don't start with '%'!"); // ⑳ ㉑
        return;
    }
    count++;
  }
  prinf("Result: %i lines in file %s begin with '%' symbol\n", count); // ㉒ ㉓ ㉔
}

1. Функция не изменяет строку, поэтому `char const *s`.
2. Отсутствует проверка на `NULL`.
3. Эпатажный стиль кода.
Всё условие бесполезно, можно было написать простое
`return *s != '%';`
4. Так как возвращаемый тип — `bool`, лучше использовать `true` и `false`.
5. Лишняя `;` после тела функции.
6. `void main(...)` — нестандартная форма. Стандарт допускает только `int main(void)`, или `int main(int, char **)`, или `int main(int, char *[])`.
7. `char **argv` или `char *argv[]`.
`int argc`.
8. Аллоцированная память не освобождается в программе.
9. `"rw"` невалиден, тут нужен `"r"`.
10. Нет проверки числа аргументов командной строки.
11. В массиве `argv` аргументы начинаются с `[1]`, а нулевой элемент — название программы.
12. `fopen` может вернуть `NULL`, если файл не открылся. Проверка отсутствует.
13. Надо юзать `strtol`: `itoa` решает вообще обратную задачу.
14. `i < limit` в условии
15. Лишняя `;`.
16. Возможен выход за границу массива. Использовать `fgets` или передавать размер буфера в формат.
17. `str`
18. Здесь условие наоборот должно быть, то есть без `!`.
19. `fscanf(f, "%s", ...)` прочтёт **слово**, а не всю строку.
20. Недостаёт `\n`.
21. Это не фатальная ошибка, а штатная ситуация. Нужно не материться, а скипать строку.
22. `printf`
23. `%'` распознаётся как спецификатор преобразования. В стандарте этого нет — undefined behavior.
Чтобы было хорошо, нужно писать `%%`.
24. Для трёх спецификаторов требуются 2 (3 по коду, 2 по смыслу) аргумента, а передаётся только один.