Динамические структуры данных на Си: Введение. Список — простой вариант

В качестве введения. Для чего эта статья?

Эта статья призвана резюмировать приобретенные знание полученные в процессе обучения программированию. Так вышло, что я попал на обучение на программиста, скажем так, «по-взрослому». Поэтому первым языком стал Си. Основы языка дались легко благодаря опыту работы с языками программирования PHP, JavaScript, C# и Python. Но позднее процесс обучения вышел на новый уровень, связанный со структурами данных. И начались мои страдания.

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

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

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

Ну а теперь к делу. Реализация простого варианта списка:

Как мы знаем, всё везде у нас состоит из всяких списков. Куда не плюнь, всюду эти списки. Даже хлеб не купишь без списка, а купив, тоже получишь список. Так как же нам реализовать список. Давайте размышлять.

В самом простом, элементарном варианте, наш список состоит из двух вещей: Первое — общая структура списка, и второе — структура элемента списка. Попробуем реализовать эту радость.

Создадим заголовочный файл: database.h:

#include <stdio.h> // стандартная библиотека Си #include <string.h> // для работы со строками #include <stdlib.h> // для работы с памятью  // структура элемента списка typedef struct list_item {     void *data; // по этому указателю мы храним какие-то данные     struct list_item *next; // это у нас ссылка на следующий указатель     struct list_item *prev; // это у нас ссылка на предыдущий указатель } list_item;  // Общая структура списка typedef struct list {     int count; // информация о размере списка     list_item *head; // это ссылка на головной элемент     list_item *tail; // это у нас ссылка на последний элемент (хвост списка) } list;

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

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

Попробуем реализовать все эти функции. В том же самом заголовочном файле «database.h» ниже под структурами обозначим прототипы функций.

list * db_create(); // создает список. возвращает список.

Перейдем теперь в файл «main.c» — это наш главный файл программы, который мы будем компилировать. Оформляем заготовок программы.

#include "database.h" // не забудем подключить наш заголовочный файл  int main(int argc, const char** argv) { // code }

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

list * db_create() {   // Создадим указатель на переменную структуры списка и выделим немного памяти для нее     list *lst = (list*)malloc(sizeof(list));          // задаем первоначальные значения     lst->count = 0; // наш список пуст     lst->head = NULL; // первого элемента у нас нет     lst->tail = NULL; // и последнего тоже          return lst; }

Возвращаемся в функцию main, вызываем наш список.

int main(int argc, const char** argv) { list *database = create(); // список мы создали }

Теперь мы немного с этим списком поработаем. А чтобы было с чем работать мы туда, для начала, попробуем добавить первые данные. Добавлять мы будем следующим образом, мы укажем некий индекс, который будет сигнализировать куда добавлять элемент в начало или конец, ну и сами данные в виде строки. Ну и также в нашу функцию мы будем передавать указатель на список, чтобы она понимала, куда ей это счастье наше добавлять.
В нашем заголовочном файле «database.h» ниже пишем новый прототип:

void db_insert(list *lst, int index, char *data);

В файле «main.c»:

void db_insert(list *lst, int index, char *data) { // создадим указатель переменной элемента списка,  // и присвоим ему значение указателя на первый элемент списка   list_item *base = lst->head;      // создадим указатель переменной на новый элемент и выделим под него память list_item *new_item = (list_item*)malloc(sizeof(list_item));      // выделим память внутри самого элемента структуры куда принимаем данные,   // и получим указатель на него,   // strlen() нужен, чтобы выделенная память была равна длинне полученной строки.   new_item->data = malloc(sizeof(char) * strlen(data));    strcpy(new_item->data, data); // копируем туда данные      // Пришла пора решить куда мы определим элемент,   // т.к. у нас еще нет элементов, lst->head вернет нам NULL.   // Следовательно нужно условие, при создании первого элемента списка.   if (base == NULL) {       // Этот элемент единственный, а значит его указатели будут NULL.       new_item->next = NULL;         new_item->previous = NULL;        // При этом, он сам будет первым и последним в списке.         lst->first = new_item;         lst->last = new_item;         lst->count++; // Увеличем кол-во на единицу         return;     }      // Если индекс, который пришел будет меньше нуля, то будем вставлять в конец   if (index < 0) {     // голова теперь будет ссылаться на новый элм. впереди себя       base->prev = new_item;          new_item->previous = NULL;          new_item->next = base; // а ссылка на след. элм. у нового будет на голову          lst->head = new_item; // назначаем новый элемент головой     } else { // тут все в обратном порядке     base = lst->tail; // перейдем в хвост списка              // пусть он теперь ссылаеться на новый элемент       base->next = new_item;       new_item->next = NULL; // Новый не будет иметь ссылки на следующий       new_prev->prev = base; // А предыдущий у него будет хвост списка              lst->tail = new_item; // Назначаем новый элемент хвостом списка     }   lst->count++; // увеличим размер на единицу }

На этом функция вставки готова, теперь вставим что-нибудь в наш список. В функции main пишем.

int main(int argc, const char** argv) { list *database = create(); // список мы создали      insert(database, 0, "One");   insert(database, 1, "Two");   insert(database, -1, "Three"); }

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

char * db_read(list *lst, int index) {   list_item *base;   int middle = lst->count / 2; // Вычисляем середину списка        if (index > middle) { // если индекс больше середины     base = lst->tail;       for (int i = lst->count; i > index; i--)         base = base->prev;     } else { // если индекс меньше середины     base = lst->head;       for (int i = 0; i < index; i++)         base = base->next;     }      // Если элемента нет     if (base == NULL) {         printf("\033[3;31mError! The list item was not found...\n\033[0m");         return NULL;     }        char *value = malloc(sizeof(char) * strlen(base->data)); // Выделяем память под строку     strcpy(value, base->data); // копируем данные      return value; // возвращаем полученное значение }

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

int db_search(list *lst, char *data) {     int i = 0; // организуем счетчик     list_item *base = lst->first; // перейдем к первому элементу   // воспользуемся функцией strcmp, чтобы сравнить перебираемые строки     while (strcmp(base->data, data) != 0) {         // пока строки не совпадут с тем что бы ищем, будем перебирать элементы       base = base->next;          i++;     }     return i; // получив совпадение просто вернем полученный индекс }

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

list_item * get_element(list *lst, int index) {   list_item *base;   int middle = lst->count / 2; // Вычисляем середину списка        if (index > middle) { // если индекс больше середины     base = lst->tail;       for (int i = lst->count; i > index; i--)         base = base->prev;     } else { // если индекс меньше середины     base = lst->head;       for (int i = 0; i < index; i++)         base = base->next;     }      // Если элемента нет     if (base == NULL) {         printf("\033[3;31mError! The list item was not found...\n\033[0m");         return NULL;     }   return base; // возвращаем элемент }

Перепишем нашу функцию read:

char * db_read(list *lst, int index) {   list_item *base = get_element(lst, index);   if (base == NULL)       return NULL;        char *value = malloc(sizeof(char) * strlen(base->data)); // Выделяем память под строку     strcpy(value, base->data); // копируем данные      return value; // возвращаем полученное значение }

То же самое с функцией delete:

void db_delete(list *lst, int index) {     list_item *base = get_element(lst, index);     list_item *prev, *next;      if (base == NULL)       return;          prev = base->previous; // получение предыдущего элемента     next = base->next; // мы получаем следующий элемент      // переопределение указателя для предыдущего элемента на следующий     if (prev != NULL)         prev->next = base->next;        // И тоже самое для предыдущего элемента     if (next != NULL)         next->previous = base->previous;       free(base); // Освобождаем память      lst->count--; // уменьшаем длинну списка на единицу }

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

int main(int argc, const char** argv) { list *database = create(); // список мы создали      insert(database, 0, "One"); // добавим несколько элементов   insert(database, 1, "Two");   insert(database, -1, "Three");      char *value = read(database, 1); // Получим One   printf("Value %s", value);      int index = search(database, "One"); // получим 1   printf("Index: %d", index);      db_delete(database, 1); // удалит элемент One      // Пришла пора посмотреть, что там в нашем списке   db_print(database); }

Нам теперь нужна функция, которая поможет нам вывести содержимое списка на экран. Делается это следующим образом:

void db_print(list *lst) {     list_item *base = lst->first; // переходим к началу списка     puts("\033[43m***Printing a list***\033[0m");           if (lst->count == 0) { // если список пустой, так и говорим         printf("The list is empty\n");         return;     }    int i = 0; // организуем счетчик     while (base != NULL) { // Пока все элементы не кончаться мы будем их перебирать         printf("ID: %d || Data: %s\n", i, (char*)base->data); // выводя на экран         base = base->next;         i++;     }   // В конце покажем какой размер у нашего списка     printf("Base size: %d\n", lst->count); }

Такой вот простой способ организации двусвязного списка. Работает как положено, но у него есть один существенный минус. Что если элементов в списке будет не 3, ни 10, ни даже 1000, а будет их 1млн? Как показало испытание, генерация списка размером в 1млн заняло порядка 20 секунд. 10млн — 15 минут. И это только генерация, а поиск и чтение по такому огромному списку тоже не сильно быстрее. Пришлось несколько подумать над решением этой проблемы, и в следующей статье я объясню как ее решил.

Следующая статья: Динамические структуры данных на Си: Список — Продвинутая версия