В качестве введения. Для чего эта статья?
Эта статья призвана резюмировать приобретенные знание полученные в процессе обучения программированию. Так вышло, что я попал на обучение на программиста, скажем так, "по-взрослому". Поэтому первым языком стал Си. Основы языка дались легко благодаря опыту работы с языками программирования 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 минут. И это только генерация, а поиск и чтение по такому огромному списку тоже не сильно быстрее. Пришлось несколько подумать над решением этой проблемы, и в следующей статье я объясню как ее решил.
Следующая статья: Динамические структуры данных на Си: Список - Продвинутая версия
