Эта статья призвана резюмировать приобретенные знание полученные в процессе обучения программированию. Так вышло, что я попал на обучение на программиста, скажем так, «по-взрослому». Поэтому первым языком стал Си. Основы языка дались легко благодаря опыту работы с языками программирования PHP, JavaScript, C# и Python.
Но позднее процесс обучения вышел на новый уровень, связанный со структурами данных. И начались мои страдания.
Оказалось, что моего опыта «кодинга» всякой мелочи недостаточно, опытные пользователи бы сказали, что в интернете существует множество статей по реализации тех же списков, но они мне не подходили. В конечном итоге до всего пришлось доходить самостоятельно, лишь используя имеющиеся статьи. Теперь в этой серии статей я попытаюсь зафиксировать свой опыт. Я всего лишь еще учусь, поэтому в решениях возможны некорректность в реализации, поэтому советам по улучшениям буду рад. А быть может мои статьи помогут еще кому-нибудь.
В чем особенность этих статей? Как говорят еще в научном сообществе — актуальность, новизна. Каждое решение будет ориентированно и оптимизировано на работу с большим объемом данных. И по крайней мере я попытаюсь так сделать. Все задачи будут решены с использованием языка Си.
09 2 Списки: пример реализации (Голубев В.И., 2019)
Статей будет несколько, каждая будет посвящена одному конкретному решению и его реализации. В каждой статье оставлю ссылки на другие, по другим решениям.
Условия реализации следующие. Все программы будут реализовываться для работы в ОС Ubuntu. Возможен их запуск в Unix-подобных системах. Другие специфические особенности будут мной указаны непосредственно в самой статье по конкретному решению.
Ну а теперь к делу. Реализация простого варианта списка:
Как мы знаем, всё везде у нас состоит из всяких списков. Куда не плюнь, всюду эти списки. Даже хлеб не купишь без списка, а купив, тоже получишь список. Так как же нам реализовать список. Давайте размышлять.
В самом простом, элементарном варианте, наш список состоит из двух вещей: Первое — общая структура списка, и второе — структура элемента списка. Попробуем реализовать эту радость.
Создадим заголовочный файл: database.h:
#include // стандартная библиотека Си #include // для работы со строками #include // для работы с памятью // структура элемента списка 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;
Как можно заметить, мы пытаемся реализовать двусвязный список, кроме того у нас присутствует дополнительная структура, которая хранит информацию о списке, его размер, где начало, а где его конец. Такая структура в дальнейшем облегчит нам жизнь в работе с этим списком.
Реализация односвязного списка c++ Часть 1 | Урок #133
Теперь с этим списком нам нужно произвести кое-какие операции. Для начала его нужно создать, как сущность, сам список, а затем добавить в него некоторые элементы, какие-то в начало, а какие-то в конец. С этими элементами мы затем будем работать, попытаемся найти по ключу, по значению, удалим какой-нибудь на выбор. Естественно мы захотим вывести весь список на экран и посмотреть, а что там вообще есть.
Попробуем реализовать все эти функции. В том же самом заголовочном файле «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(« 33[3;31mError! The list item was not found. n 33[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(« 33[3;31mError! The list item was not found. n 33[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(« 33[43m***Printing a list*** 33[0m»); if (lst->count == 0) < // если список пустой, так и говорим printf(«The list is emptyn»); return; >int i = 0; // организуем счетчик while (base != NULL) < // Пока все элементы не кончаться мы будем их перебирать printf(«ID: %d || Data: %sn», i, (char*)base->data); // выводя на экран base = base->next; i++; > // В конце покажем какой размер у нашего списка printf(«Base size: %dn», lst->count); >
Такой вот простой способ организации двусвязного списка.
Работает как положено, но у него есть один существенный минус. Что если элементов в списке будет не 3, ни 10, ни даже 1000, а будет их 1млн? Как показало испытание, генерация списка размером в 1млн заняло порядка 20 секунд. 10млн — 15 минут. И это только генерация, а поиск и чтение по такому огромному списку тоже не сильно быстрее.
Пришлось несколько подумать над решением этой проблемы, и в следующей статье я объясню как ее решил.
Следующая статья: Динамические структуры данных на Си: Список — Продвинутая версия
- Си
- структуры данных
- динамические структуры данных
Источник: habr.com
Односвязный список
О дносвязный список – структура данных, в которой каждый элемент (узел) хранит информацию, а также ссылку на следующий элемент. Последний элемент списка ссылается на NULL.
Для нас односвязный список полезен тем, что
- 1) Он очень просто устроен и все алгоритмы интуитивно понятны
- 2) Односвязный список – хорошее упражнение для работы с указателями
- 3) Его очень просто визаулизировать, это позволяет «в картинках» объяснить алгоритм
- 4) Несмотря на свою простоту, односвязные списки часто используются в программировании, так что это не пустое упражнение.
- 5) Эта структуру данных можно определить рекурсивно, и она часто используется в рекурсивных алгоритмах.
Для простоты рассмотрим односвязный список, который хранит целочисленное значение.
Односвязный список
Односвязный список состоит из узлов. Каждый узел содержит значение и указатель на следующий узел, поэтому представим его в качестве структуры
typedef struct Node < int value; struct Node *next; >Node;
Чтобы не писать каждый раз struct мы определили новый тип.
Теперь наша задача написать функцию, которая бы собирала список из значений, которые мы ей передаём. Стандартное имя функции – push, она должна получать в качестве аргумента значение, которое вставит в список. Новое значение будет вставляться в начало списка. Каждый новый элемент списка мы должны создавать на куче. Следовательно, нам будет удобно иметь один указатель на первый элемент списка.
Node *head = NULL;
Вначале списка нет и указатель ссылается на NULL.
Для добавления нового узла необходимо
- 1) Выделить под него память.
- 2) Задать ему значение
- 3) Сделать так, чтобы он ссылался на предыдущий элемент (или на NULL, если его не было)
- 4) Перекинуть указатель head на новый узел.
1) Создаём новый узел
Создали новый узел, на который ссылается локальная переменная tmp
2) Присваиваем ему значение
Присвоили ему значение
3) Присваиваем указателю tmp адрес предыдущего узла
Перекинули указатель tmp на предыдущий узел
4) Присваиваем указателю head адрес нового узла
Перекинули указатель head на вновь созданный узел tmp
5) После выхода из функции переменная tmp будет уничтожена. Получим список, в который будет вставлен новый элемент.
Новый узел добавлен
void push(Node **head, int data) < Node *tmp = (Node*) malloc(sizeof(Node)); tmp->value = data; tmp->next = (*head); (*head) = tmp; >
Так как указатель head изменяется, то необходимо передавать указатель на указатель.
Теперь напишем функцию pop: она удаляет элемент, на который указывает head и возвращает его значение.
Если мы перекинем указатель head на следующий элемент, то мы потеряем адрес первого и не сможем его удалить и тем более вернуть его значения. Для этого необходимо сначала создать локальную переменную, которая будет хранить адрес первого элемента
Локальная переменная хранит адрес первого узла
Уже после этого можно удалить первый элемент и вернуть его значение
Перекинули указатель head на следующий элемент и удалили узел
int pop(Node **head) < Node* prev = NULL; int val; if (head == NULL) < exit(-1); >prev = (*head); val = prev->value; (*head) = (*head)->next; free(prev); return val; >
Не забываем, что необходимо проверить на NULL голову.
Таким образом, мы реализовали две операции push и pop, которые позволяют теперь использовать односвязный список как стек. Теперь добавим ещё две операции — pushBack (её ещё принято называть shift или enqueue), которая добавляет новый элемент в конец списка, и функцию popBack (unshift, или dequeue), которая удаляет последний элемент списка и возвращает его значение.
Для дальнейшего разговора необходимо реализовать функции getLast, которая возвращает указатель на последний элемент списка, и nth, которая возвращает указатель на n-й элемент списка.
Так как мы знаем адрес только первого элемента, то единственным способом добраться до n-го будет последовательный перебор всех элементов списка. Для того, чтобы получить следующий элемент, нужно перейти к нему через указатель next текущего узла
Node* getNth(Node* head, int n) < int counter = 0; while (counter < n head) < head = head->next; counter++; > return head; >
Переходя на следующий элемент не забываем проверять, существует ли он. Вполне возможно, что был указан номер, который больше размера списка. Функция вернёт в таком случае NULL. Сложность операции O(n), и это одна из проблем односвязного списка.
Для нахождение последнего элемента будем передирать друг за другом элементы до тех пор, пока указатель next одного из элементов не станет равным NULL
Node* getLast(Node *head) < if (head == NULL) < return NULL; >while (head->next) < head = head->next; > return head; >
Теперь добавим ещё две операции — pushBack (её ещё принято называть shift или enqueue), которая добавляет новый элемент в конец списка, и функцию popBack (unshift, или dequeue), которая удаляет последний элемент списка и возвращает его значение.
Для вставки нового элемента в конец сначала получаем указатель на последний элемент, затем создаём новый элемент, присваиваем ему значение и перекидываем указатель next старого элемента на новый
void pushBack(Node *head, int value) < Node *last = getLast(head); Node *tmp = (Node*) malloc(sizeof(Node)); tmp->value = value; tmp->next = NULL; last->next = tmp; >
Односвязный список хранит адрес только следующего элемента. Если мы хотим удалить последний элемент, то необходимо изменить указатель next предпоследнего элемента. Для этого нам понадобится функция getLastButOne, возвращающая указатель на предпоследний элемент.
Node* getLastButOne(Node* head) < if (head == NULL) < exit(-2); >if (head->next == NULL) < return NULL; >while (head->next->next) < head = head->next; > return head; >
Функция должна работать и тогда, когда список состоит всего из одного элемента. Вот теперь есть возможность удалить последний элемент.
void popBack(Node **head) < Node *lastbn = NULL; //Получили NULL if (!head) < exit(-1); >//Список пуст if (!(*head)) < exit(-1); >lastbn = getLastButOne(*head); //Если в списке один элемент if (lastbn == NULL) < free(*head); *head = NULL; >else < free(lastbn->next); lastbn->next = NULL; > >
Удаление последнего элемента и вставка в конец имеют сложность O(n).
Можно написать алгоритм проще. Будем использовать два указателя. Один – текущий узел, второй – предыдущий. Тогда можно обойтись без вызова функции getLastButOne:
int popBack(Node **head) < Node *pFwd = NULL; //текущий узел Node *pBwd = NULL; //предыдущий узел //Получили NULL if (!head) < exit(-1); >//Список пуст if (!(*head)) < exit(-1); >pFwd = *head; while (pFwd->next) < pBwd = pFwd; pFwd = pFwd->next; > if (pBwd == NULL) < free(*head); *head = NULL; >else < free(pFwd->next); pBwd->next = NULL; > >
Теперь напишем функцию insert, которая вставляет на n-е место новое значение. Для вставки, сначала нужно будет пройти до нужного узла, потом создать новый элемент и поменять указатели. Если мы вставляем в конец, то указатель next нового узла будет указывать на NULL, иначе на следующий элемент
void insert(Node *head, unsigned n, int val) < unsigned i = 0; Node *tmp = NULL; //Находим нужный элемент. Если вышли за пределы списка, то выходим из цикла, //ошибка выбрасываться не будет, произойдёт вставка в конец while (i < n head->next) < head = head->next; i++; > tmp = (Node*) malloc(sizeof(Node)); tmp->value = val; //Если это не последний элемент, то next перекидываем на следующий узел if (head->next) < tmp->next = head->next; //иначе на NULL > else < tmp->next = NULL; > head->next = tmp; >
Покажем на рисунке последовательность действий
Создали новый узел и присвоили ему значение
После этого делаем так, чтобы новый элемент ссылался на следующий после n-го
Теперь значение next нового узла хранит адрес того же узла, что и элемент, на который ссылается head
Перекидываем указатель next n-го элемента на вновь созданный узел
Теперь узел, адрес которого хранит head, указывает на новый узел tmp
Функция удаления элемента списка похожа на вставку. Сначала получаем указатель на элемент, стоящий до удаляемого, потом перекидываем ссылку на следующий элемент за удаляемым, потом удаляем элемент.
int deleteNth(Node **head, int n) < if (n == 0) < return pop(head); >else < Node *prev = getNth(*head, n-1); Node *elm = prev->next; int val = elm->value; prev->next = elm->next; free(elm); return val; > >
Рассмотрим то же самое в картинках. Сначала находим адреса удаляемого элемента и того, который стоит перед ним
Для удаления узла, на который ссылается elm необходим предыдущий узел, адрес которого хранит prev
После чего прокидываем указатель next дальше, а сам элемент удаляем.
Прекидываем указатель на следующий за удалённым узел и освобождаем память
Кроме создания списка необходимо его удаление. Так как самая быстрая функция у нас этот pop, то для удаления будем последовательно выталкивать элементы из списка.
void deleteList(Node **head) < while ((*head)->next) < pop(head); *head = (*head)->next; > free(*head); >
Вызов pop можно заменить на тело функции и убрать ненужные проверки и возврат значения
void deleteList(Node **head) < Node* prev = NULL; while ((*head)->next) < prev = (*head); (*head) = (*head)->next; free(prev); > free(*head); >
Осталось написать несколько вспомогательных функций, которые упростят и ускорят работу. Первая — создать список из массива. Так как операция push имеет минимальную сложность, то вставлять будем именно с её помощью. Так как вставка произойдёт задом наперёд, то массив будем обходить с конца к началу:
void fromArray(Node **head, int *arr, size_t size) < size_t i = size — 1; if (arr == NULL || size == 0) < return; >do < push(head, arr[i]); >while(i—!=0); >
И обратная функция, которая возвратит массив элементов, хранящихся в списке. Так как мы будем создавать массив динамически, то сначала определим его размер, а только потом запихнём туда значения.
int* toArray(const Node *head) < int leng = length(head); int *values = (int*) malloc(leng*sizeof(int)); while (head) < values[—leng] = head->value; head = head->next; > return values; >
И ещё одна функция, которая будет печатать содержимое списка
void printLinkedList(const Node *head) < while (head) < printf(«%d «, head->value); head = head->next; > printf(«n»); >
Теперь можно провести проверку и посмотреть, как работает односвязный список
void main() < Node* head = NULL; int arr[] = ; //Создаём список из массива fromArray( printLinkedList(head); //Вставляем узел со значением 333 после 4-го элемента (станет пятым) insert(head, 4, 333); printLinkedList(head); pushBack(head, 11); pushBack(head, 12); pushBack(head, 13); pushBack(head, 14); printLinkedList(head); printf(«%dn», pop( printf(«%dn», popBack( printLinkedList(head); //Удаляем пятый элемент (индексация с нуля) deleteNth( printLinkedList(head); deleteList( getch(); >
Сортировка односвязного списка
Сортировать список будем слиянием. Этот метод очень похож на сортировку слиянием для массива. Для его реализации нам понадобятся две функции: одна буде делить список пополам, а другая будет объединять два упорядоченных односвязных списка, не создавая при этом новых узлов. Наша реализация не будет оптимальной, однако, некоторые решения, которые мы применим, могут быть использованы и в других алгоритмах.
Вспомогательная функция – слияние двух отсортированных списков. Функция не должна создавать новых узлов, так что будем использовать только имеющиеся. Для начала проверим, если хоть один из списков пуст, то вернём другой.
Node tmp; *c = NULL; if (a == NULL) < *c = b; return; >if (b == NULL)
После этого нужно, чтобы наша локальная переменная стала хранить адрес большего из узлов двух списков, от него и будем танцевать дальше
if (a->value < b->value) < *c = a; a = a->next; > else < *c = b; b = b->next; >
Теперь сохраним указатель c, так как в дальнейшем он будет использоваться для прохода по списку
tmp.next = *c;
После этого проходим по спискам, сравниваем значения и перекидываем их
while (a b) < if (a->value < b->value) < (*c)->next = a; a = a->next; > else < (*c)->next = b; b = b->next; > (*c) = (*c)->next; >
В конце, может остаться один список, который пройден не до конца. Добавим его узлы
if (a) < while (a) < (*c)->next = a; (*c) = (*c)->next; a = a->next; > > if (b) < while (b) < (*c)->next = b; (*c) = (*c)->next; b = b->next; > >
Теперь указатель c хранит адрес последнего узла, а нам нужна ссылка на голову. Она как раз хранится во второй переменной tmp
*c = tmp.next;
void merge(Node *a, Node *b, Node **c) < Node tmp; *c = NULL; if (a == NULL) < *c = b; return; >if (b == NULL) < *c = a; return; >if (a->value < b->value) < *c = a; a = a->next; > else < *c = b; b = b->next; > tmp.next = *c; while (a b) < if (a->value < b->value) < (*c)->next = a; a = a->next; > else < (*c)->next = b; b = b->next; > (*c) = (*c)->next; > if (a) < while (a) < (*c)->next = a; (*c) = (*c)->next; a = a->next; > > if (b) < while (b) < (*c)->next = b; (*c) = (*c)->next; b = b->next; > > *c = tmp.next; >
Ещё одна важная функция – нахождение середины списка.
Для этих целей будем использовать два указателя. Один из них — fast – за одну итерацию будет два раза изменять значение и продвигаться по списку вперёд. Второй – slow, всего один раз. Таким образом, если список чётный, то slow окажется ровно посредине списка, а если список нечётный, то второй подсписок будет на один элемент длиннее.
void split(Node *src, Node **low, Node **high) < Node *fast = NULL; Node *slow = NULL; if (src == NULL || src->next == NULL) < (*low) = src; (*high) = NULL; return; >slow = src; fast = src->next; while (fast != NULL) < fast = fast->next; if (fast != NULL) < fast = fast->next; slow = slow->next; > > (*low) = src; (*high) = slow->next; slow->next = NULL; >
Очевидно, что можно было один раз узнать длину списка, а потом передавать размер в каждую функцию. Это было бы проще и быстрее. Но мы не ищем лёгких путей)))
Теперь у нас есть функция, которая позволяет разделить список на две части и функция слияния отсортированных списков. С их помощью реализуем функцию сортировки слиянием.
Сортировка слиянием для односвязного списка
Функция рекурсивно вызывает сама себя, передавая части списка. Если в функцию пришёл список длинной менее двух элементов, то рекурсия прекращается. Идёт обратная сборка списка. Сначала из двух списков, каждый из которых хранит один элемент, создаётся отсортированный список, далее из таких списков собирается новый отсортированный список, пока все элементы не будут включены.
void mergeSort(Node **head) < Node *low = NULL; Node *high = NULL; if ((*head == NULL) || ((*head)->next == NULL)) < return; >split(*head, high); mergeSort( mergeSort( merge(low, high, head); >
Если Вы желаете изучать этот материал с преподавателем, советую обратиться к репетитору по информатике
Всё ещё не понятно? – пиши вопросы на ящик
Источник: learnc.info
Реализация односвязного линейного списка в СИ
Односвязный список – это динамическая структура данных, элементы которой содержат ссылку на следующий элемент. Последний элемент имеет в качестве ссылки NULL. Для доступа к списку используется указатель на первый элемент.
Достоинства списков
- Работа со списком занимает гораздо меньше времени, чем с массивом
- Списки можно нарисовать на бумаге, тем самым наглядно понять механизм работы
- Списки можно определить рекурсивно
Односвязный список состоит из узлов. Каждый узел содержит в себе указатель на следующий узел (элемент списка) и хранимое значение. Узлы представляются в качестве структуры:
typedef struct Node < int value; struct Node *next; >Spisok;
Комментарии к коду
- Используем typedef для создания нового типа, чтобы в дальнейшем не писать слово struct.
- int value — хранимое значение, может быть любого типа.
- struct Node *next — указатель на следующий узел списка.
- Spisok — название структуры.
Инициализируем список
Spisok *create(int data) < // Выделение памяти под корень списка Spisok *tmp = (Spisok*)malloc(sizeof(Spisok)); // Присваивание значения узлу tmp ->value = data; // Присваивание указателю на следующий элемент значения NULL tmp -> next = NULL; return(tmp); >