Тренировочные задания: Связные списки
Десять задач на односвязные и двусвязные списки, стек, очередь, дек и кольцевой список. Решайте по одной: сначала попробуйте сами, потом открывайте спойлер с решением. Во всех задачах ввод и вывод — через стандартные потоки, как в обычных тренировочных заданиях.
Задача 1. Сумма элементов
Считайте N и N целых чисел, постройте односвязный список и выведите сумму всех значений.
Пример ввода:
5
1 2 3 4 5
Пример вывода:
15
Решение
#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
int value;
struct Node *next;
} Node;
Node *push_back(Node *head, int value)
{
Node *node = malloc(sizeof(*node));
if (node == NULL)
{
return NULL;
}
node->value = value;
node->next = NULL;
if (head == NULL)
{
return node;
}
Node *p = head;
while (p->next != NULL)
{
p = p->next;
}
p->next = node;
return head;
}
void free_list(Node *head)
{
while (head != NULL)
{
Node *next = head->next;
free(head);
head = next;
}
}
int main(void)
{
int n;
if (scanf("%d", &n) != 1 || n < 0 || n > 1000)
{
fprintf(stderr, "Ошибка ввода\n");
return 1;
}
Node *head = NULL;
for (int i = 0; i < n; i++)
{
int value;
if (scanf("%d", &value) != 1)
{
free_list(head);
return 1;
}
head = push_back(head, value);
if (head == NULL)
{
return 1;
}
}
long long sum = 0;
for (Node *p = head; p != NULL; p = p->next)
{
sum += p->value;
}
printf("%lld\n", sum);
free_list(head);
return 0;
}
Задача 2. Разворот списка
Считайте N и N целых чисел, постройте односвязный список и выведите его в обратном порядке, не создавая второй список.
Пример ввода:
5
1 2 3 4 5
Пример вывода:
5 4 3 2 1
Решение
#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
int value;
struct Node *next;
} Node;
Node *push_back(Node *head, int value)
{
Node *node = malloc(sizeof(*node));
if (node == NULL)
{
return NULL;
}
node->value = value;
node->next = NULL;
if (head == NULL)
{
return node;
}
Node *p = head;
while (p->next != NULL)
{
p = p->next;
}
p->next = node;
return head;
}
Node *reverse(Node *head)
{
Node *prev = NULL;
while (head != NULL)
{
Node *next = head->next;
head->next = prev;
prev = head;
head = next;
}
return prev;
}
void free_list(Node *head)
{
while (head != NULL)
{
Node *next = head->next;
free(head);
head = next;
}
}
int main(void)
{
int n;
if (scanf("%d", &n) != 1 || n < 0 || n > 1000)
{
fprintf(stderr, "Ошибка ввода\n");
return 1;
}
Node *head = NULL;
for (int i = 0; i < n; i++)
{
int value;
if (scanf("%d", &value) != 1)
{
free_list(head);
return 1;
}
head = push_back(head, value);
}
head = reverse(head);
int first = 1;
for (Node *p = head; p != NULL; p = p->next)
{
if (!first)
{
printf(" ");
}
printf("%d", p->value);
first = 0;
}
printf("\n");
free_list(head);
return 0;
}
Задача 3. Удалить минимумы
Считайте N и N целых чисел. Найдите минимальное значение и удалите из списка все узлы с этим значением. Если список опустел, выведите empty.
Пример ввода:
5
3 1 4 1 5
Пример вывода:
3 4 5
Решение
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
typedef struct Node
{
int value;
struct Node *next;
} Node;
Node *push_back(Node *head, int value)
{
Node *node = malloc(sizeof(*node));
if (node == NULL) return NULL;
node->value = value;
node->next = NULL;
if (head == NULL) return node;
Node *p = head;
while (p->next != NULL) p = p->next;
p->next = node;
return head;
}
Node *remove_value(Node *head, int value)
{
Node *prev = NULL;
Node *cur = head;
while (cur != NULL)
{
if (cur->value == value)
{
Node *next = cur->next;
if (prev == NULL) head = next;
else prev->next = next;
free(cur);
cur = next;
}
else
{
prev = cur;
cur = cur->next;
}
}
return head;
}
void free_list(Node *head)
{
while (head != NULL)
{
Node *next = head->next;
free(head);
head = next;
}
}
int main(void)
{
int n;
if (scanf("%d", &n) != 1 || n < 0 || n > 1000)
{
fprintf(stderr, "Ошибка ввода\n");
return 1;
}
Node *head = NULL;
int min = INT_MAX;
for (int i = 0; i < n; i++)
{
int value;
if (scanf("%d", &value) != 1)
{
free_list(head);
return 1;
}
if (value < min) min = value;
head = push_back(head, value);
if (head == NULL) { free_list(head); return 1; }
}
if (n > 0) head = remove_value(head, min);
if (head == NULL) printf("empty\n");
else
{
int first = 1;
for (Node *p = head; p != NULL; p = p->next)
{
if (!first)
{
printf(" ");
}
printf("%d", p->value);
first = 0;
}
printf("\n");
}
free_list(head);
return 0;
}
Задача 4. Стабильное разделение по порогу
Считайте N, N целых чисел и порог T. Переставьте узлы так, чтобы сначала шли значения >= T, затем < T, сохранив порядок внутри каждой группы.
Пример ввода:
6
1 5 2 6 3 4
4
Пример вывода:
5 6 4 1 2 3
Решение
#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
int value;
struct Node *next;
} Node;
Node *push_back(Node *head, int value)
{
Node *node = malloc(sizeof(*node));
if (node == NULL) return NULL;
node->value = value;
node->next = NULL;
if (head == NULL) return node;
Node *p = head;
while (p->next != NULL) p = p->next;
p->next = node;
return head;
}
Node *partition(Node *head, int threshold)
{
Node *high = NULL, *high_tail = NULL;
Node *low = NULL, *low_tail = NULL;
while (head != NULL)
{
Node *next = head->next;
head->next = NULL;
if (head->value >= threshold)
{
if (high_tail == NULL) high = high_tail = head;
else { high_tail->next = head; high_tail = head; }
}
else
{
if (low_tail == NULL) low = low_tail = head;
else { low_tail->next = head; low_tail = head; }
}
head = next;
}
if (high == NULL) return low;
high_tail->next = low;
return high;
}
void free_list(Node *head)
{
while (head != NULL)
{
Node *next = head->next;
free(head);
head = next;
}
}
int main(void)
{
int n, threshold;
if (scanf("%d", &n) != 1 || n < 0 || n > 1000)
{
fprintf(stderr, "Ошибка ввода\n");
return 1;
}
Node *head = NULL;
for (int i = 0; i < n; i++)
{
int value;
if (scanf("%d", &value) != 1) { free_list(head); return 1; }
head = push_back(head, value);
if (head == NULL) { free_list(head); return 1; }
}
if (scanf("%d", &threshold) != 1) { free_list(head); return 1; }
head = partition(head, threshold);
int first = 1;
for (Node *p = head; p != NULL; p = p->next)
{
if (!first)
{
printf(" ");
}
printf("%d", p->value);
first = 0;
}
printf("\n");
free_list(head);
return 0;
}
Задача 5. Слияние двух отсортированных списков
Считайте два отсортированных по возрастанию списка и слейте их в один отсортированный список. Новые узлы не создавайте — переставляйте ссылки.
Пример ввода:
3
1 3 5
4
2 4 6 8
Пример вывода:
1 2 3 4 5 6 8
Решение
#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
int value;
struct Node *next;
} Node;
Node *push_back(Node *head, int value)
{
Node *node = malloc(sizeof(*node));
if (node == NULL) return NULL;
node->value = value;
node->next = NULL;
if (head == NULL) return node;
Node *p = head;
while (p->next != NULL) p = p->next;
p->next = node;
return head;
}
Node *merge(Node *a, Node *b)
{
Node dummy;
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;
}
void free_list(Node *head)
{
while (head != NULL)
{
Node *next = head->next;
free(head);
head = next;
}
}
int main(void)
{
int n, m;
if (scanf("%d", &n) != 1 || n < 0 || n > 1000) return 1;
Node *a = NULL;
for (int i = 0; i < n; i++)
{
int v; if (scanf("%d", &v) != 1) { free_list(a); return 1; }
a = push_back(a, v); if (a == NULL) { free_list(a); return 1; }
}
if (scanf("%d", &m) != 1 || m < 0 || m > 1000) { free_list(a); return 1; }
Node *b = NULL;
for (int i = 0; i < m; i++)
{
int v; if (scanf("%d", &v) != 1) { free_list(a); free_list(b); return 1; }
b = push_back(b, v); if (b == NULL) { free_list(a); free_list(b); return 1; }
}
Node *result = merge(a, b);
int first = 1;
for (Node *p = result; p != NULL; p = p->next)
{
if (!first)
{
printf(" ");
}
printf("%d", p->value);
first = 0;
}
printf("\n");
free_list(result);
return 0;
}
Задача 6. Разворот двусвязного списка
Считайте N и N целых чисел, постройте двусвязный список и разверните его, обменяв prev и next у каждого узла. Выведите список в новом порядке.
Пример ввода:
4
1 2 3 4
Пример вывода:
4 3 2 1
Решение
#include <stdio.h>
#include <stdlib.h>
typedef struct DNode
{
int value;
struct DNode *prev;
struct DNode *next;
} DNode;
typedef struct
{
DNode *head;
DNode *tail;
} DList;
void init(DList *list)
{
list->head = NULL;
list->tail = NULL;
}
int push_back(DList *list, int value)
{
DNode *node = malloc(sizeof(*node));
if (node == NULL) return 0;
node->value = value;
node->prev = list->tail;
node->next = NULL;
if (list->tail == NULL) list->head = node;
else list->tail->next = node;
list->tail = node;
return 1;
}
void reverse(DList *list)
{
DNode *p = list->head;
while (p != NULL)
{
DNode *next = p->next;
p->next = p->prev;
p->prev = next;
p = next;
}
DNode *tmp = list->head;
list->head = list->tail;
list->tail = tmp;
}
void free_list(DList *list)
{
DNode *p = list->head;
while (p != NULL)
{
DNode *next = p->next;
free(p);
p = next;
}
list->head = NULL;
list->tail = NULL;
}
int main(void)
{
int n;
if (scanf("%d", &n) != 1 || n < 0 || n > 1000) return 1;
DList list;
init(&list);
for (int i = 0; i < n; i++)
{
int v;
if (scanf("%d", &v) != 1) { free_list(&list); return 1; }
if (!push_back(&list, v)) { free_list(&list); return 1; }
}
reverse(&list);
int first = 1;
for (DNode *p = list.head; p != NULL; p = p->next)
{
if (!first)
{
printf(" ");
}
printf("%d", p->value);
first = 0;
}
printf("\n");
free_list(&list);
return 0;
}
Задача 7. Проверка скобок стеком
Считайте строку из символов ()[]{} без пробелов. Проверьте, правильно ли расставлены скобки, и выведите YES или NO. Используйте стек на связном списке.
Пример ввода:
([]){}
Пример вывода:
YES
Решение
#include <stdio.h>
#include <stdlib.h>
typedef struct StackNode
{
char value;
struct StackNode *next;
} StackNode;
int push(StackNode **top, char value)
{
StackNode *node = malloc(sizeof(*node));
if (node == NULL) return 0;
node->value = value;
node->next = *top;
*top = node;
return 1;
}
int pop(StackNode **top, char *out)
{
if (*top == NULL) return 0;
StackNode *node = *top;
*out = node->value;
*top = node->next;
free(node);
return 1;
}
void free_stack(StackNode *top)
{
while (top != NULL)
{
StackNode *next = top->next;
free(top);
top = next;
}
}
int main(void)
{
char s[1001];
if (scanf("%1000s", s) != 1) return 1;
StackNode *top = NULL;
int ok = 1;
for (int i = 0; s[i] != '\0' && ok; i++)
{
char c = s[i];
if (c == '(' || c == '[' || c == '{')
{
if (!push(&top, c)) { ok = 0; }
}
else if (c == ')' || c == ']' || c == '}')
{
char open;
if (!pop(&top, &open)) { ok = 0; break; }
if ((c == ')' && open != '(') || (c == ']' && open != '[') || (c == '}' && open != '{'))
{
ok = 0;
}
}
}
if (top != NULL) ok = 0;
free_stack(top);
printf("%s\n", ok ? "YES" : "NO");
return 0;
}
Задача 8. Очередь по командам
Считайте число команд Q. Команда 1 x добавляет x в очередь, команда 2 забирает элемент из начала. Для каждой команды 2 выведите значение или empty, если очередь пуста.
Пример ввода:
6
1 10
1 20
2
1 30
2
2
Пример вывода:
10
20
30
Решение
#include <stdio.h>
#include <stdlib.h>
typedef struct QNode
{
int value;
struct QNode *next;
} QNode;
typedef struct
{
QNode *head;
QNode *tail;
} Queue;
void init(Queue *q)
{
q->head = NULL;
q->tail = NULL;
}
int enqueue(Queue *q, int value)
{
QNode *node = malloc(sizeof(*node));
if (node == NULL) return 0;
node->value = value;
node->next = NULL;
if (q->tail == NULL) q->head = node;
else q->tail->next = node;
q->tail = node;
return 1;
}
int dequeue(Queue *q, int *out)
{
if (q->head == NULL) return 0;
QNode *node = q->head;
*out = node->value;
q->head = node->next;
if (q->head == NULL) q->tail = NULL;
free(node);
return 1;
}
void free_queue(Queue *q)
{
while (q->head != NULL)
{
QNode *next = q->head->next;
free(q->head);
q->head = next;
}
q->tail = NULL;
}
int main(void)
{
int q;
if (scanf("%d", &q) != 1 || q < 0 || q > 1000) return 1;
Queue queue;
init(&queue);
for (int i = 0; i < q; i++)
{
int op;
if (scanf("%d", &op) != 1) { free_queue(&queue); return 1; }
if (op == 1)
{
int value;
if (scanf("%d", &value) != 1 || !enqueue(&queue, value)) { free_queue(&queue); return 1; }
}
else if (op == 2)
{
int value;
if (dequeue(&queue, &value)) printf("%d\n", value);
else printf("empty\n");
}
}
free_queue(&queue);
return 0;
}
Задача 9. Палиндром через дек
Считайте N и N целых чисел. Положите их в дек и проверьте, является ли последовательность палиндромом: сравнивайте элементы с обоих концов. Выведите YES или NO.
Пример ввода:
5
1 2 3 2 1
Пример вывода:
YES
Решение
#include <stdio.h>
#include <stdlib.h>
typedef struct DNode
{
int value;
struct DNode *prev;
struct DNode *next;
} DNode;
typedef struct
{
DNode *head;
DNode *tail;
int size;
} Deque;
void init(Deque *d)
{
d->head = NULL;
d->tail = NULL;
d->size = 0;
}
int push_back(Deque *d, int value)
{
DNode *node = malloc(sizeof(*node));
if (node == NULL) return 0;
node->value = value;
node->prev = d->tail;
node->next = NULL;
if (d->tail == NULL) d->head = node;
else d->tail->next = node;
d->tail = node;
d->size++;
return 1;
}
int pop_front(Deque *d, int *out)
{
if (d->head == NULL) return 0;
DNode *node = d->head;
*out = node->value;
d->head = node->next;
if (d->head == NULL) d->tail = NULL;
else d->head->prev = NULL;
free(node);
d->size--;
return 1;
}
int pop_back(Deque *d, int *out)
{
if (d->tail == NULL) return 0;
DNode *node = d->tail;
*out = node->value;
d->tail = node->prev;
if (d->tail == NULL) d->head = NULL;
else d->tail->next = NULL;
free(node);
d->size--;
return 1;
}
int main(void)
{
int n;
if (scanf("%d", &n) != 1 || n < 0 || n > 1000) return 1;
Deque d;
init(&d);
for (int i = 0; i < n; i++)
{
int v;
if (scanf("%d", &v) != 1 || !push_back(&d, v)) return 1;
}
int ok = 1;
while (d.size > 1)
{
int left, right;
if (!pop_front(&d, &left) || !pop_back(&d, &right)) { ok = 0; break; }
if (left != right) ok = 0;
}
printf("%s\n", ok ? "YES" : "NO");
while (d.size > 0)
{
int value;
pop_front(&d, &value);
}
return 0;
}
Задача 10. Задача Иосифа
Считайте N и K. Поставьте числа 1..N в кольцевой список и удаляйте каждый K-й узел, продолжая счёт со следующего. Выведите номер последнего оставшегося узла.
Пример ввода:
5 2
Пример вывода:
3
Решение
#include <stdio.h>
#include <stdlib.h>
typedef struct CNode
{
int value;
struct CNode *next;
} CNode;
CNode *build_ring(int n)
{
if (n <= 0) return NULL;
CNode *head = NULL;
CNode *tail = NULL;
for (int i = 1; i <= n; i++)
{
CNode *node = malloc(sizeof(*node));
if (node == NULL)
{
if (head != NULL)
{
CNode *p = head->next;
while (p != head) { CNode *next = p->next; free(p); p = next; }
free(head);
}
return NULL;
}
node->value = i;
node->next = NULL;
if (head == NULL) { head = tail = node; }
else { tail->next = node; tail = node; }
}
tail->next = head;
return head;
}
int josephus(int n, int k)
{
CNode *head = build_ring(n);
if (head == NULL || k <= 0) return -1;
CNode *prev = head;
while (prev->next != head) prev = prev->next;
CNode *cur = head;
while (cur->next != cur)
{
for (int i = 1; i < k; i++)
{
prev = cur;
cur = cur->next;
}
prev->next = cur->next;
CNode *next = cur->next;
free(cur);
cur = next;
}
int result = cur->value;
free(cur);
return result;
}
int main(void)
{
int n, k;
if (scanf("%d %d", &n, &k) != 2 || n < 1 || n > 1000 || k < 1) return 1;
printf("%d\n", josephus(n, k));
return 0;
}
Что потренировать отдельно
- пустой список и список из одного узла;
- удаление головы, хвоста и единственного узла;
- вставку в начало, в конец и после заданного узла;
- разворот списка и кольца;
- слияние списков без создания новых узлов;
- освобождение памяти во всех ветках, включая ошибки ввода.
Связь с ЛР 3
Эти задачи — тренировка тех же приёмов, что нужны в ЛР 3: malloc/free, обход по next,
аккуратное обновление head/tail/prev, проверка пустого списка и разбиение на функции.
Формат ЛР 3 отличается: там данные читаются из input.txt, результат пишется в output.txt,
а структура задана вариантом.