Задание к курсовому проекту №7

Линейные списки

Задание

Составить и отладить программу на языке Си для обработки линейного списка заданной организации с отображением на динамические структуры. Навигацию по списку следует реализовать с применением итераторов. Тип элементов списка — целый. Предусмотреть выполнение одного нестандартного и четырех стандартных действий:

  • печать списка;
  • вставка нового элемента в список;
  • удаление элемента списка;
  • подсчет длины списка.

Входные данные

На стандартный ввод программе подаются команды пяти типов:

p — печать списка; i 2 4 — вставка перед вторым элементом элемента со значением 4. d 5 — удаление первого встретившегося элемента со значением 5. l — печать длины списка. t [params] — выполнение заданного вариантом действия. Параметры, если они есть, перечислены через пробел.

Выходные данные

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

Вывести все элементы списка через пробел. Вывести сообщение «OK» в случае успеха и «Error» в случае неудачи (при попытке вставить на несуществующую позицию в некольцевом списке). Вывести сообщение «OK» при успешном удалении или «Not found», если элемента с таким значением в списке нет. Вывести длину списка. Вывести сообщение «OK» в случае успешного выполнения операции или «Error» в случае неудачи.

Варианты заданий

Вид списка

  • Кольцевой однонаправленный.
  • Линейный однонаправленный.
  • Кольцевой двунаправленный.
  • Линейный двунаправленный с барьерным элементом.

Нестандартное действие

  1. Удалить из середины списка k элементов.
  2. Очистить список, если в нем есть элемент заданного значения.
  3. Обменять местами (k+1)-й и (k-1)-й элементы списка.
  4. Обменять местами второй и предпоследний элементы списка.
  5. Удалить каждый k-й элемент списка.
  6. Удалить элементы списка со значениями, находящимися в заданном диапазоне.
  7. Дополнить список копиями заданного значения до указанно длины k. Если в списке уже имеется не менее k элементов, то не менять его.
  8. Исключить из списка последние k элементов. Если в списке менее k элементов, то не менять его.
  9. Добавить k экземпляров последнего элемента в начало списка.
  10. Переставить элементы списка в обратном порядке.
  11. Проверить упорядоченность элементов списка.
  12. Выполнить циклический сдвиг элементов списка на один вперед.
  13. Выполнить попарный обмен значениями элементов списка.
  14. Переставить первую и вторую половины списка.

Примечания

При описании структур или алгоритмов желательно использовать графическую иллюстрацию и/или нотацию одного из языков со встроенными списковыми структурами (Лисп, Пролог). Следует разделить программу на 3 части: заголовочный файл с описанием интерфейса списка, файл с реализаций списка и основной файл, в котором производится обработка команд пользователя и вызов соответствующих функций.

Удаление и добавление элементов должно быть сделано с использованием итераторов. То есть сначала производится поиск элемента в списке, а затем удаление или добавление. При работе с памятью нужно отcлеживать возможные ошибки при выделении памяти (например, она может закончиться). В отчете указать сложностные оценки всех реализованных операций.

Пример реализации стека

Toggle line numbers
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

typedef struct elem elem;

struct elem {
  int val;
  elem *next;
};

typedef struct {
  elem *top;
} stack;

int top(stack *s)
{
  return s->top->val;
}
void pop(stack *s)
{
  elem *tmp = s->top;
  s->top = s->top->next;
  free(tmp);
}

void push(stack *s, int val)
{
  elem *e = malloc(sizeof(elem));
  e->val = val;
  e->next = s->top;
  s->top = e;
}

bool empty(stack *s)
{
  return s->top == 0;
}
void stack_init(stack *s)
{
  s->top = 0;
}

int main()
{
  stack s;
  stack_init(&s);
  for (int i = 0; i != 10; ++i)
    push(&s, i);
  while (!empty(&s)) {
    printf("%i ", top(&s));
    pop(&s);
  }
  printf("\n");
}