06 Practise

Практика 6

На этой практике мы познакомимся с Абстрактными Типами Данных. Разберем Список, как один из видов АТД. Напишем две реализации Списка - Связный Список и Список на основе массива. Проведем бенчмарк скорости работы двух реализаций в разных задачах.

Теория

АТД - это математическая модель некоторого типа данных, где тип определяется некоторым поведением, то есть возможными значениями, которые он может принимать, возможными операциями над ним и поведением этих операций. Вся внутренняя структура такого типа скрыта от пользователя. В этом и заключается абстракция. Например, нам нужен тип данных, который хранит последовательности чисел. Нам не важно то, как реализовано хранения данных, нам важно чтобы мы могли добавлять в последовательность новые числа, получать доступ к ним. Когда мы пишем программу, мы не хотим концентрироваться на реализациях этих абстракций, мы хотим чтобы они работали эфективно и без ошибок. Например, использование АТД Список позволит нам не думать о выделении и очистке памяти.

Список

Рассмотрим матмодель списка - множество объектов, упорядоченное по индексу элемента в списке. Мы хотим иметь возможность применять следующий операции над списком:

  • Get(index) - взять элемент из списка по индексу
  • Insert(index, element) - вставить элемент по индексу
    • Append(element) - вставить элемент в конец списка(стека)
    • Prepend(element) - вставить элемент в начало списка(очереди)
  • Delete(index) - удалить элемент по индексу
    • Pop() - удалить элемент с конца списка(стека) и получить этот элемент
    • Dequeue() - удалить элемент с начала списка(очереди)
  • Min() - поиск минимального элемента в списке
  • Search(value) - поиск элемента в списке со значением value.

Содержимое файла-интерфейса list.h. Его менять нельзя, подключайте его в ваших реализациях #include "list.h".

// это файл list.h
#ifndef LIST_LIST_H
#define LIST_LIST_H

#include <stdlib.h>  // импортируем тип size_t, который используется для обозначения размера массивов

typedef struct List List; // не специфицированная струткруа, конкретные реализации должны быть описаны в c-файлах
List *Create(); // создание пустого списка
List *Copy(const List *); // полное копирование списка

void Append(List *, int); // вставка элемента в конец списка
void Prepend(List *, int); // вставка элемента в начало списка
void AppendAll(List *, const List *); // вставить все элементы одного списка в конец другого
void InsertAt(List *, int, size_t); // втсавка элемента по индексу

void RemoveAt(List *, size_t); // удаление элемента по индексу
void RemoveAll(List *); // удаление всех элементов из списка

int Pop(List *); // удаление элемента с конца списка, функция возвращает удаленный элемент
int Dequeue(List *); // удаление элемента с начала списка, функция возвращает удаленный элемент

size_t Length(const List *); // вычисление длины списка
int GetAt(const List *, size_t); // взятие элемента списка по индексу

#endif //LIST_LIST_H

Реализовать Список можно разными способами: линейно связный список и список на основе массива.

Линейно связный список

Список можно представить в виде связанных объектов, каждый из которых хранит полезную нагрузку и имеет указатель на следующий элемент списка. Можно представить вагоны поезда, как связный список.

Используйте следующий код для написания реализации:

#include "list.h"

// В узле списка хранится само значение value и указатель на следующий узел.
// Эту структуру пользователи списка не должны видеть, так как она относится к внутренней реализации.
typedef struct Node {
  int value; // само значение, которое хранит узел
  struct Node *next; // указатель на следующий узел
} Node;

// Пользовательская структура, которая скрывает механизм хранения данных.
struct List {
  Node *head; // указатель на голову списка
  Node *tail; // указатель на хвост списка
};

Список на основе массива

Очевидно, можно реализовать список на основе непрерывного куска памяти - обычного массива. В этом случае мы как разработчики списка скроем от пользователя машинерию по выделению памяти при добавлении новых элементов в массив или по очистке памяти. Основная сложность тут состоит в том, чтобы как можно реже вызывать операции по довыделению памяти и не поймать ошибку, когда ОС не может выдать нам непрерывный кусок памяти большого размера.

Вам придется использовать механизмы перевыделения памяти realloc.

Используйте следующий код для написания реализации:

#include "list.h"
// Пользовательская структура, которая скрывает механизм хранения данных.
struct List {
  int* array; // динамический массив, в котором будут раниться все данные
  size_t length; // размер массива array
};

Литература

Вы можете посмотреть следующие материалы, чтобы лучше понять, как решить задачу:

Задания

Используя описанные выше прототипы функций в файле list.h, необходиом сделать две разные реализации Списка: на основе массива, на основе связного списка. В результате вашей работы у вас будут следующие файлы с реализациями: array_list.c и linked_list.c. Создайте еще два файла test_array_list.c и test_linked_list.c, в которых вы тестируете работу ваших списков, то есть только в этих двух файлах будет main функция.

Чтобы скомпилировать проект запустите следующие команды:

gcc test_linked_list.c linked_list.c list.h -o linked_list.out
gcc test_array_list.c  array_list.c list.h  -o array_list.out

./linked_list.out # запуск тестов для связного списка
./array_list.out  # запуск тестов для списка на массивах
  • Прототипы функций менять нельзя!
  • Библиотечные реализации использовать нельзя

Рекомендуется использовать шаблон проекта, который открывается в CLion.

Домашнее задание.

Читать главу 7 K&R.