Тренировочные задания: Списки
Десять задач на создание, обход, поиск, удаление и разворот односвязного списка. Ввод — с
клавиатуры, память — динамическая. В решениях показаны функции; вызовы добавьте в main
самостоятельно, если не указано иное.
Задача 1. Список из N чисел
Считайте N, затем N чисел, добавьте каждое в начало списка и выведите список.
Пример ввода:
4
1 2 3 4
Пример вывода:
4 3 2 1
Решение
#include <stdio.h>
#include <stdlib.h>
struct Node
{
int value;
struct Node *next;
};
int main(void)
{
int n;
if (scanf("%d", &n) != 1 || n < 0)
{
return 1;
}
struct Node *head = NULL;
for (int i = 0; i < n; i++)
{
int x;
if (scanf("%d", &x) != 1)
{
/* ... освободить список ... */
return 1;
}
struct Node *node = malloc(sizeof(*node));
if (node == NULL)
{
/* ... освободить список ... */
return 1;
}
node->value = x;
node->next = head;
head = node;
}
for (struct Node *p = head; p != NULL; p = p->next)
{
printf("%d ", p->value);
}
printf("\n");
while (head != NULL)
{
struct Node *next = head->next;
free(head);
head = next;
}
return 0;
}
Задача 2. Добавление в конец
Считайте N чисел и добавьте их в конец списка, сохранив порядок ввода.
Пример ввода:
3
10 20 30
Пример вывода:
10 20 30
Решение
Держим указатель на хвост tail, тогда добавление не требует обхода:
struct Node *head = NULL;
struct Node *tail = NULL;
for (int i = 0; i < n; i++)
{
int x;
scanf("%d", &x);
struct Node *node = malloc(sizeof(*node));
if (node == NULL)
{
/* ... освободить список ... */
return 1;
}
node->value = x;
node->next = NULL;
if (tail == NULL)
{
head = tail = node; /* первый узел */
}
else
{
tail->next = node; /* прицепляем к хвосту */
tail = node;
}
}
Задача 3. Сумма и максимум
Найдите сумму и максимальный элемент списка.
Пример ввода:
5
-3 7 0 12 5
Пример вывода:
sum = 21, max = 12
Решение
int list_sum(struct Node *head)
{
int sum = 0;
for (struct Node *p = head; p != NULL; p = p->next)
{
sum += p->value;
}
return sum;
}
int list_max(struct Node *head)
{
int max = head->value; /* список не пуст */
for (struct Node *p = head->next; p != NULL; p = p->next)
{
if (p->value > max)
{
max = p->value;
}
}
return max;
}
Перед вызовом проверьте, что список не пуст.
Задача 4. Поиск значения
Найдите узел с заданным значением. Верните указатель на узел или NULL.
Пример ввода:
5
1 2 3 4 5
3
Пример вывода:
Найдено: 3
Решение
struct Node *find(struct Node *head, int value)
{
for (struct Node *p = head; p != NULL; p = p->next)
{
if (p->value == value)
{
return p;
}
}
return NULL;
}
Задача 5. Удаление первого вхождения
Удалите первый узел с заданным значением. Верните новую голову списка.
Пример ввода:
5
1 2 3 2 4
2
Пример вывода:
1 3 2 4
Решение
struct Node *remove_first(struct Node *head, int value)
{
struct Node *prev = NULL;
struct Node *cur = head;
while (cur != NULL && cur->value != value)
{
prev = cur;
cur = cur->next;
}
if (cur == NULL)
{
return head; /* не нашли */
}
if (prev == NULL)
{
head = cur->next;
}
else
{
prev->next = cur->next;
}
free(cur);
return head;
}
Задача 6. Удаление всех вхождений
Удалите все узлы с заданным значением.
Пример ввода:
6
1 2 2 3 2 4
2
Пример вывода:
1 3 4
Решение
struct Node *remove_all(struct Node *head, int value)
{
struct Node *cur = head;
struct Node *prev = NULL;
while (cur != NULL)
{
if (cur->value == value)
{
struct Node *next = cur->next;
if (prev == NULL)
{
head = next;
}
else
{
prev->next = next;
}
free(cur);
cur = next; /* prev не двигаем */
}
else
{
prev = cur;
cur = cur->next;
}
}
return head;
}
Задача 7. Разворот списка
Разверните список, изменив ссылки. Новый список создавать нельзя.
Пример ввода:
4
1 2 3 4
Пример вывода:
4 3 2 1
Решение
struct Node *reverse(struct Node *head)
{
struct Node *prev = NULL;
struct Node *cur = head;
while (cur != NULL)
{
struct Node *next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
return prev;
}
Задача 8. Длина списка
Верните количество узлов в списке.
Пример ввода:
5
1 2 3 4 5
Пример вывода:
5
Решение
int list_length(struct Node *head)
{
int count = 0;
for (struct Node *p = head; p != NULL; p = p->next)
{
count++;
}
return count;
}
Задача 9. Слияние двух отсортированных списков
Даны два списка, отсортированных по возрастанию. Слейте их в один отсортированный список.
Пример ввода:
4
1 3 5 7
3
2 4 6
Пример вывода:
1 2 3 4 5 6 7
Решение
struct Node *merge_sorted(struct Node *a, struct Node *b)
{
struct Node dummy; /* фиктивный узел для удобства */
struct Node *tail = &dummy;
dummy.next = NULL;
while (a != NULL && b != NULL)
{
if (a->value <= b->value)
{
tail->next = a;
a = a->next;
}
else
{
tail->next = b;
b = b->next;
}
tail = tail->next;
}
tail->next = (a != NULL) ? a : b;
return dummy.next;
}
Фиктивный узел dummy живёт на стеке и не освобождается; он нужен только для сборки
списка.
Задача 10. Разделение на чётные и нечётные
Разделите список на два: чётные и нечётные значения, сохранив исходный порядок.
Пример ввода:
6
1 2 3 4 5 6
Пример вывода:
Чётные: 2 4 6
Нечётные: 1 3 5
Решение
void split_even_odd(struct Node *head, struct Node **even, struct Node **odd)
{
*even = NULL;
*odd = NULL;
struct Node *even_tail = NULL;
struct Node *odd_tail = NULL;
for (struct Node *p = head; p != NULL; p = p->next)
{
struct Node *node = malloc(sizeof(*node));
if (node == NULL)
{
/* ... освободить even и odd ... */
return;
}
node->value = p->value;
node->next = NULL;
if (p->value % 2 == 0)
{
if (even_tail == NULL)
{
*even = even_tail = node;
}
else
{
even_tail->next = node;
even_tail = node;
}
}
else
{
if (odd_tail == NULL)
{
*odd = odd_tail = node;
}
else
{
odd_tail->next = node;
odd_tail = node;
}
}
}
}
Исходный список после разделения нужно освободить отдельно.