Язык C. Урок про функции и параметры

Для начала решите и сдайте в проверяющую систему две задачи.
Вход в проверяющую систему

L: Удалить элемент

Дан массив из чисел и индекс элемента в списке k. Удалите из списка элемент с индексом k, сдвинув влево все элементы, стоящие правее элемента с индексом k (считаем, что элементы массива нумеруются с 0).

Программа получает на вход натуральное N (не превышающее 10) - количество элементов массива, затем сами элементы (типа int), затем число k.

Программа должна осуществлять сдвиг непосредственно в массиве, а не делать это при выводе элементов. Также нельзя использовать дополнительный массив.

Ввод	Вывод
7 7 6 5 4 3 2 1 2	7 6 4 3 2 1

M: Вставить элемент

Дано натуральное число N (не превышающее 10), затем массив из N целых чисел (типа int), число k и значение C. Необходимо вставить в список на позицию с индексом k элемент, равный C, сдвинув все элементы, имевшие индекс не менее k, вправо (считаем, что элементы массива нумеруются с 0).

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

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

Ввод	Вывод
7 7 6 5 4 3 2 1 2 0	7 6 0 5 4 3 2 1

Реализовываем динамический двухсвязный список

Давайте вместе реализуем двухсвязный список. Возьмите шаблон программы:

#include <iostream>
#include <cstdlib>
using namespace std;

struct mylist {
    int a;
    mylist *next;
    mylist *prev;
};

mylist *first = nullptr;
mylist *last = nullptr;


mylist *new_elem() {
    return (mylist *) malloc(sizeof(mylist));
}

void del_elem(mylist *elem) {
    free(elem);
}


int main()
{
    first = new_elem();
    last = first;
    first->a = 0;
    first->next = nullptr;
    first->prev = nullptr;

    return 0;
}

Что есть в этой программе: здесь заведен тип данных mylist, который является элементом списка. В нем есть поле a, в котором хранится числовое значение элемента, и два указателя next и prev, указывающие на следующий и предыдущий элементы списка. У крайних элементов списка (prev у первого и next у последнего) соответствующие указатели равны nullptr - то есть не указывают никуда.

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

В начале в списке есть один элемент со значением 0.

Допишите код main, чтобы программа последовательно решала следующие задачи (задачи не сдаются в проверяющую систему):

Задача 1

Напишите функцию

void print_mylist()

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

Если вы добавите в исходную функцию main вызов функции print_mylist();, должен будет напечататься 0.

Задача 2

Вам вводится число N и затем N чисел типа int. Добавьте последовательно все введенные числа в список, после чего напечатайте его.

Рекомендация: напишите функцию void add_to_end(int x), которая добавляет в конец списка элемент со значением x. Для этого она последовательно:

вызывает функцию new_elem() и запоминает ее результат (например, в локальной переменной cur) - эта функция выделяет память под новый элемент и возвращает указатель на эту память.
В поле cur->a записывает значение x.
Смотрит на значение last->next. last указывает на последний элемент списка, а его поле next - на следующий за ним элемент, то есть сейчас вникуда. Надо сделать так, чтобы оно указывало на вновь созданный элемент (то есть присвоить ему cur).
Полю cur->prev нужно присвоить указатель на элемент, который являлся последним до добавления (то есть значение last).
Полю cur->next надо присвоить признак, что это сейчас последний элемент, то есть значение nullptr
Наконец нужно поменять переменную last, чтобы она указывала на вновь созданный элемент.

После того, как вы написали такую функцию, в функции main осталось лишь считать данные и вызвать функцию add_to_end для каждого считанного числа, а затем вызвать print_mylist(); для печати результата.

Задача 3

Напишите функцию mylist * find_first(int x), которая находит в нашем списке первый элемент со значением x и возвращает ссылку на него. Если элемента с таким значением нет, возвращает nullptr.

Задача 4

Напишите функцию void remove_elem(mylist * elem), которая удаляет из списка элемент, указатель на который передан в качестве параметра. Для того, чтобы освободить соответствующую память, нужно вызвать функцию del_elem(elem). Не забудьте, что вам также надо правильно изменить указатели next у предыдущего и prev у следующего элемента. Для начала считайте, что удаляемый элемент не является ни первым, ни последним в списке.

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

Задача 5

Дополните задачу 4 так, чтобы она корректно удаляла также первый и последний элемент списка (при условии, что в списке после удаления остается хотя бы один элемент).