Как сделать двусвязный список из структуры
Есть задание сделать из этого двусвязный список,хотел бы разобраться что вообще хотят. Как я понял,то нужна только структура,указатели на следующий и предыдущий элемент сделал,а вот дальше как правильно,в методичке у меня указывается,что нужно создавать отдельную структуру Node(ячейки),в инете почти везде через классы делают,как по всем правилам сделать грамотно двусвязный список,если не готовый код с комментариями,то хотя бы на словах,как поэтапно делать его,как принято и т.д.
Двусвязный список (list) в STL на С++
На этом занятии мы рассмотрим уже готовую реализацию двусвязного списка из стандартной библиотеки шаблонов (STL). Чтобы воспользоваться этой коллекцией данных, вначале нужно подключить модуль list:
#include
А, затем, в функции main() определить объект класса list, например, так:
int main() { using namespace std; listint> lst; return 0; }
Все, у нас в программе имеется объект lst, который представляет собой двусвязный список. Обратите внимание, в угловых скобках прописан тип int – тот тип данных, который предполагается хранить в элементах двусвязного списка. Вместо типа int можно прописать любой другой, включая собственные определения классов и структур. То есть, мы здесь имеем универсальную реализацию списка, который может работать с любыми типами данных. Но для простоты пусть будет тип int.
Далее, если прописать lst и поставить точку, то интегрированная среда покажет набор методов, поддерживаемых данным классом. На этом занятии мы рассмотрим наиболее значимые из них. Начнем со способа инициализации списка.
При создании двусвязного списка командой:
listint> lst;
создается пустой список (без элементов). Мы в этом можем легко убедиться, если вызовем метод size(), который возвращает общее число элементов:
cout lst.size() endl;
Если же нам нужно прописать в список некоторый набор начальных значений, то это можно сделать так:
listint> lst = {1, 5, 3, 2};
или так (без разницы):
listint> lst {1, 5, 3, 2};
В обоих случаях мы получим список из четырех элементов со значениями 1, 5, 3, 2. Давайте выведем их в консоль:
for (auto it = lst.cbegin(); it != lst.cend(); it++) cout *it " "; cout endl;
Смотрите, чтобы перебрать элементы связного списка используется механизм итераторов, который в С++ нужно прописывать явно. Вначале с помощь метода cbegin() получаем константный итератор, установленный в самое начало списка. Затем, делаем цикл до тех пор, пока адрес итератора не равен конечному адресу. А оператор it++ позволяет сместить итератор на следующий элемент списка. В самом цикле с помощью операции разыменования указателя *it получаем значение текущего элемента списка и выводим его в консоль. Фактически, с помощью итератора мы последовательно переходим от одного элемента к другому, используя ссылки next и prev, которые есть у каждого объекта двусвязного списка.
- cbegin() и cend() – для работы с константным итератором;
- begin() и end() – для работы с обычным итератором.
cout lst.front() endl; cout lst.back() endl;
Видим значения 1 и 2. Эти методы бывают весьма полезны, например, при реализации очередей, о которых мы будем говорить на следующем занятии. Следующий часто используемый метод empty(), который возвращает булево значение true – если список пуст, и false в противном случае. Например, методы front() и back() будут приводить к ошибке, если их вызвать для пустого списка. Поэтому правильнее было бы обращаться к ним с проверкой:
if (!lst.empty()) { cout lst.front() endl; cout lst.back() endl; }
Добавление элементов в список
Следующий набор методов, используемый для добавления элементов в двусвязный список. Методы push_back() и push_front() используются для добавления элементов в конец и начало списка. Например:
listint> lst; lst.push_back(1); lst.push_front(4); lst.push_front(-4); lst.push_back(-1);
Увидим значения: -4, 4, 1, -1. Если нам требуется вставить какое-либо значение в произвольную позицию, то для этого используется метод insert(). Этот метод использует итератор для указания позиции вставки. Например, если определить итератор с помощью команды:
auto pos_it = lst.cbegin();
то получим указатель на первую позицию, куда и будет вставлен элемент:
lst.insert(pos_it, 100);
Если нужно вставить во вторую позицию, то это можно сделать так:
auto pos_it = lst.cbegin(); pos_it++; lst.insert(pos_it, 100);
или в более краткой записи:
auto pos_it = lst.cbegin(); lst.insert(++pos_it, 100);
Обратите внимание, что оператор ++ должен быть записан перед итератором pos_it. Если его прописать после, то сначала будет выполнен метод insert() и только потом изменится итератор на единицу. Если нужно вставить элемент в произвольную k-ю позицию, то сначала итератор устанавливается в эту позицию, например, с помощью цикла:
auto pos_it = lst.cbegin(); int n = 3; for (int k = 0; k n; ++pos_it, ++k) ; lst.insert(pos_it, 100);
а, затем, выполняется команда insert(). Поэтому операция вставки, в общем случае, имеет сложность O(n), где n – общее число элементов в списке. Также с помощью insert() можно относительно просто вставить сразу несколько одинаковых значений, например, так:
lst.insert(pos_it, 5, 3);
Выполняется вставка пяти троек, начиная с позиции pos_it.
Удаление элементов из списка
Последняя группа методов связана с удалением элементов из списка. Если нам нужно очистить список (удалить все элементы), то это делается с помощью метода clear():
lst.clear();
Для удаления первого или последнего элемента – методы pop_front() и pop_back():
lst.pop_front(); lst.pop_back();
Наконец, удаление произвольного элемента выполняется методом erase(). Здесь также, как и в методе insert(), необходимо определить итератор на удаляемый элемент, например, так:
auto pos_it = lst.cbegin(); lst.erase(++pos_it);
В результате будет удален второй элемент. Либо можно задать границы удаляемых элементов через итераторы:
auto start_it = lst.cbegin(); auto end_it = lst.cend(); lst.erase(++start_it, --end_it);
Заключение
Вот основные операции при работе с двусвязными списками объекта list языка С++. Конечно, мы рассмотрели не все доступные операции, но с ними можно подробно ознакомиться, например, на ресурсе: https://en.cppreference.com/w/cpp/container/list А на данный момент вы должны себе представлять, как работают следующие методы двухсвязного списка класса list:
| Метод | Описание | Сложность |
| size() | Возвращает число элементов в списке | O(1) |
| begin(), cbegin() | Возвращает итератор на первый элемент списка | O(1) |
| end(), cend() | Возвращает итератор на последний элемент списка | O(1) |
| front() | Получение значения первого элемента | O(1) |
| back() | Получение значения последнего элемента | O(1) |
| push_back() | Вставка нового элемента в конец списка | O(1) |
| push_front() | Вставка нового элемента в начало списка | O(1) |
| insert() | Вставка нового элемента в произвольную позицию | O(n) |
| clear() | Очистка двусвязного списка | — |
| pop_front() | Удаление первого элемента из списка | O(1) |
| pop_back() | Удаление последнего элемента из списка | O(1) |
| erase() | Удаление произвольного элемента списка | O(n) |
Двусвязный список
М ы рассмотрели односвязный список и пришли к неутешительным выводам — список разумно использовать в качестве стека, потому что операции вставки в начало списка и удаления из начала списка имеют сложность порядка 1, с дополнительными манёврами можно добиться сложности вставки в конец порядка 1 и определения длины за O(1), но удаление с конца, вставка и поиск элемента остаются O(n).
Каким образом можно упростить удаление последнего элемента? Очевидно, что если бы мы хранили указатель на предыдущий элемент, то было бы возможно удалять последний.
Двусвязный список — это структура данных, которая состоит из узлов, которые хранят полезные данные, указатели на предыдущий узел и следующий узел.
Двусвязный список
Для реализации списка нам понадобится структура узел
typedef struct _Node < void *value; struct _Node *next; struct _Node *prev; >Node;
Указатель prev хранит адрес предыдущего узла, если его нет (значит, это первый узел) то переменная равна NULL. Аналогично, указатель next хранит адрес следующего узла. Структура «Двусвязный Список» будет хранить свой размер (чтобы не пересчитывать количество элементов каждый раз), а также указатель head, ссылающийся на первый элемент, и указатель tail, ссылающийся на последний элемент
typedef struct _DblLinkedList < size_t size; Node *head; Node *tail; >DblLinkedList;
Пустая структура типа DblLinkedList
В случае, когда в списке нет элементов, оба они равны нулю. Если в списке один элемент, то оба указателя ссылаются на один и тот же элемент (соответственное, они равны). Об этом постоянно следует помнить: каждый раз, удаляя или вставляя элемент, придётся проверять, чтобы указатели head и tail правильно хранили адреса.
Структура типа DblLinkedList с одним элементом
Первая функция, как обычно, создаёт экземпляр структуры DblLinkedList
DblLinkedList* createDblLinkedList() < DblLinkedList *tmp = (DblLinkedList*) malloc(sizeof(DblLinkedList)); tmp->size = 0; tmp->head = tmp->tail = NULL; return tmp; >
В ней нет ничего интересного. Заодно опишем функцию, которая удаляет список
void deleteDblLinkedList(DblLinkedList **list) < Node *tmp = (*list)->head; Node *next = NULL; while (tmp) < next = tmp->next; free(tmp); tmp = next; > free(*list); (*list) = NULL; >
Теперь, определим набор стандартных функций – pushFront и popFront для работы с головой, pushBack И popBack для работы с последним элементом, getNth, insert и deleteNth для вставки и удаления в произвольное место.
Вставка нового элемента в начало списка
Вставка спереди очень похожа на вставку в односвязный список. Сначала создаётся новый элемент
Node *tmp = (Node*) malloc(sizeof(Node)); if (tmp == NULL)
Создали новый элемент и задали ему значения
потом задаём ему значения
tmp->value = data; tmp->next = list->head; tmp->prev = NULL;
Создали новый элемент и задали ему значения
Так как он стал первым, то указатель next ссылается на старую голову списка, а предыдущего элемента нет. Теперь, если в списке уже был головной элемент, то его указатель prev должен ссылаться на вновь созданный элемент
if (list->head) < list->head->prev = tmp; >
Теперь проверим указатель tail. Если он пустой, то после добавления нового элемента он должен ссылаться на него
if (list->tail == NULL) < list->tail = tmp; >
Теперь перекинем указатель head на вновь созданный элемент и увеличим значение счётчика size
Перекинули указазатель head списка на вновь созданный элемент
list->head = tmp; list->size++;
void pushFront(DblLinkedList *list, void *data) < Node *tmp = (Node*) malloc(sizeof(Node)); if (tmp == NULL) < exit(1); >tmp->value = data; tmp->next = list->head; tmp->prev = NULL; if (list->head) < list->head->prev = tmp; > list->head = tmp; if (list->tail == NULL) < list->tail = tmp; > list->size++; >
Удаление из начала списка также похоже на оное для односвязного списка. Прибавляются только перекидывания дополнительных указателей и проверка, чтобы указатель на последний элемент, в случае, если элементов больше не осталось, стал равным нулю.
Сначала создадим указатель на первый элемент списка. Он понадобится, чтобы после изменения всех указателей prev и next мы смогли удалить узел.
Создали указатель на первый элемент
Node *prev; void *tmp; if (list->head == NULL) < exit(2); >prev = list->head;
После этого перекинем указатель head на следующий за ним элемент
list->head = list->head->next;
Перекидываем указатель head на следующий элемент
Далее проверяем, что удаляемы элемент не является одновременно последним (когда в списке всего один элемент), после чего освобождаем память.
Создали указатель на первый элемент
void* popFront(DblLinkedList *list) < Node *prev; void *tmp; if (list->head == NULL) < exit(2); >prev = list->head; list->head = list->head->next; if (list->head) < list->head->prev = NULL; > if (prev == list->tail) < list->tail = NULL; > tmp = prev->value; free(prev); list->size--; return tmp; >
Вставка в конец и удаление с конца очень похожи — просто мы переворачиваем список. Соответственное, все prev меняются на next, а head на tail
void pushBack(DblLinkedList *list, void *value) < Node *tmp = (Node*) malloc(sizeof(Node)); if (tmp == NULL) < exit(3); >tmp->value = value; tmp->next = NULL; tmp->prev = list->tail; if (list->tail) < list->tail->next = tmp; > list->tail = tmp; if (list->head == NULL) < list->head = tmp; > list->size++; > void* popBack(DblLinkedList *list) < Node *next; void *tmp; if (list->tail == NULL) < exit(4); >next = list->tail; list->tail = list->tail->prev; if (list->tail) < list->tail->next = NULL; > if (next == list->head) < list->head = NULL; > tmp = next->value; free(next); list->size--; return tmp; >
Получение n-го элемента очень простое и не отличается от оного для односвязного списка.
Node* getNth(DblLinkedList *list, size_t index) < Node *tmp = list->head; size_t i = 0; while (tmp && i < index) < tmp = tmp->next; i++; > return tmp; >
Можно улучшить эту функцию: если список длинный, то в зависимости от индекса можно проходить либо с начала в конец, либо с конца в начало. Это позволяет всегда использовать не более N/2 шагов.
Node* getNthq(DblLinkedList *list, size_t index) < Node *tmp = NULL; size_t i; if (index < list->size/2) < i = 0; tmp = list->head; while (tmp && i < index) < tmp = tmp->next; i++; > > else < i = list->size - 1; tmp = list->tail; while (tmp && i > index) < tmp = tmp->prev; i--; > > return tmp; >
Теперь можно написать функцию удаления и вставки узла. Сначала находим нужный элемент, затем создаём либо новый узел (если вставка), либо указатель на удаляемый элемент. Затем изменяем все указатели.
void insert(DblLinkedList *list, size_t index, void *value) < Node *elm = NULL; Node *ins = NULL; elm = getNth(list, index); if (elm == NULL) < exit(5); >ins = (Node*) malloc(sizeof(Node)); ins->value = value; ins->prev = elm; ins->next = elm->next; if (elm->next) < elm->next->prev = ins; > elm->next = ins; if (!elm->prev) < list->head = elm; > if (!elm->next) < list->tail = elm; > list->size++; > void* deleteNth(DblLinkedList *list, size_t index) < Node *elm = NULL; void *tmp = NULL; elm = getNth(list, index); if (elm == NULL) < exit(5); >if (elm->prev) < elm->prev->next = elm->next; > if (elm->next) < elm->next->prev = elm->prev; > tmp = elm->value; if (!elm->prev) < list->head = elm->next; > if (!elm->next) < list->tail = elm->prev; > free(elm); list->size--; return tmp; >
Не забываем, конечно, смотреть за значениями head И tail, чтобы они указывали на существующие в данный момент элементы.
Добавим пару вспомогательных функций, которые помогут в работе. Первая — это печать списка. Так как тип значения — void*, то необходимо передавать функцию печати одного элемента.
void printDblLinkedList(DblLinkedList *list, void (*fun)(void*)) < Node *tmp = list->head; while (tmp) < fun(tmp->value); tmp = tmp->next; > printf("\n"); >
В примерах будем использовать переменные типа int
void printInt(void *value)
Вторая функция – создание списка из массива
DblLinkedList* fromArray(void *arr, size_t n, size_t size) < DblLinkedList *tmp = NULL; size_t i = 0; if (arr == NULL) < exit(7); >tmp = createDblLinkedList(); while (i < n) < pushBack(tmp, ((char*)arr + i*size)); i++; >return tmp; >
Теперь можно пользоваться двусвязным списком
void main() < DblLinkedList *list = createDblLinkedList(); int a, b, c, d, e, f, g, h; a = 10; b = 20; c = 30; d = 40; e = 50; f = 60; g = 70; h = 80; pushFront(list, &aamp;a); pushFront(list, &b); pushFront(list, &c); pushBack(list, &d); pushBack(list, &e); pushBack(list, &f); printDblLinkedList(list, printInt); printf("length %d\n", list->size); printf("nth 2 %d\n", *((int*)(getNthq(list, 2))->value)); printf("nth 5 %d\n", *((int*)(getNthq(list, 5))->value)); printf("popFront %d\n", *((int*)popFront(list))); printf("popFront %d\n", *((int*)popFront(list))); printf("head %d\n", *((int*)(list->head->value))); printf("tail %d\n", *((int*)(list->tail->value))); printf("popBack %d\n", *((int*)popBack(list))); printf("popBack %d\n", *((int*)popBack(list))); printf("length %d\n", list->size); printDblLinkedList(list, printInt); insert(list, 1, &g); printDblLinkedList(list, printInt); deleteNth(list, 0); printDblLinkedList(list, printInt); deleteDblLinkedList(&list); getch(); >
Сортировка вставками
Р анее мы рассмотрели алгоритм сортировки однонаправленного связного списка методом слияния. Двусвязный список можно сортировать точно также, поэтому сейчас рассмотрим другой алгоритм — сортировку вставками. Суть алгоритма очень простая – создаём новый двунаправленный связный список. Вставляем в него первый элемент неотсортированного списка. Для вставки второго элемента проходим по отсортированному списку и ищем место, куда вставить. Если место не найдено, то вставляем в конец. Очевидно, что если тип данных не известен, то необходимо будет передавать функцию сравнения, с помощью которой можно изменить порядок сортировки.
Для реализации нам понадобится ещё одна функция — вставка до указанного элемента. Эта функция будет получать указатель на список, указатель на узел, перед которым нужно вставить элемент и новые данные.
void insertBeforeElement(DblLinkedList *list, Node* elm, void *value) < Node *ins = NULL; if (elm == NULL) < exit(6); >if (!elm->prev) < pushFront(list, value); return; >ins = (Node*) malloc(sizeof(Node)); ins->value = value; ins->prev = elm->prev; elm->prev->next = ins; ins->next = elm; elm->prev = ins; list->size++; >
Теперь непосредственно сортировка
void insertionSort(DblLinkedList **list, int (*cmp)(void*, void*)) < DblLinkedList *out = createDblLinkedList(); Node *sorted = NULL; Node *unsorted = NULL; pushFront(out, popFront(*list)); unsorted = (*list)->head; while (unsorted) < sorted = out->head; while (sorted && !cmp(unsorted->value, sorted->value)) < sorted = sorted->next; > if (sorted) < insertBeforeElement(out, sorted, unsorted->value); > else < pushBack(out, unsorted->value); > unsorted = unsorted->next; > free(*list); *list = out; >
Видно, что в конце в переданном списке не остаётся элементов, так как мы их выталкиваем, так что старый список мы подменяем на вновь созданный.
Сложность алгоритма – O(n 2 ), мы имеем одни проход по неотсортированному списку сложностью порядка n, для каждого элемента проходим по отсортированному.
Так как при каждом создании нового узла мы удаляем узел из первого списка, то дополнительной памяти не требуется.
Тепер сравним сложности различных операций для односвязного и двусвязного списка. Однонаправленный связный список
| pushFront | popFront | pushBack | popBack | insert | delete | get | size |
|---|---|---|---|---|---|---|---|
| O(1) | O(1) | O(1) | O(n) | O(n) | O(n) | O(n) | O(1) |
| pushFront | popFront | pushBack | popBack | insert | delete | get | size |
|---|---|---|---|---|---|---|---|
| O(1) | O(1) | O(1) | O(1) | O(n) | O(n) | O(n) | O(1) |
ru-Cyrl 18- tutorial Sypachev S.S. 1989-04-14 sypachev_s_s@mail.ru Stepan Sypachev students
Всё ещё не понятно? – пиши вопросы на ящик
Делаем двусвязный список на С++
На этом занятии я решил привести вариант полной реализации двусвязного списка на С++, чтобы у вас было полное понимание, как работает эта структура данных. А на следующем занятии рассмотрим уже готовую реализацию двусвязного списка на С++ стандартной библиотеки шаблонов STL.
Итак, каждый объект (элемент) двусвязного списка будет определять классом с именем Node, а работу со всем списком целиком – с помощью класса LinkedList. Начнем с класса Node. Каждый объект должен содержать данные data и ссылки на предыдущий и следующий элементы prev и next:
class Node { public: double data; Node* prev, * next; public: Node(double data) { this->data = data; this->prev = this->next = NULL; } };
В этом классе определен один конструктор, в который передаются хранимые данные в виде вещественного числа, и сохраняются в переменной data объекта класса Node. А указатели prev и next по умолчанию принимают значение NULL.
В следующем классе LinkedList реализуем все основные операции для работы с элементами двусвязного списка. Вначале определим этот класс с двумя указателями head и tail:
class LinkedList { public: Node* head, * tail; public: LinkedList() { this->head = this->tail = NULL; } };
Здесь также присутствует конструктор класса, в котором указатели head и tail принимают начальное значение NULL, что означает, что список пуст.
Далее, по порядку, определим методы для базовых операций со списком. И первыми пропишем методы push_front() и push_back() для добавления элементов в начало и конец двусвязного списка:
Node* push_front(double data) { Node* ptr = new Node(data); ptr->next = head; if (head != NULL) head->prev = ptr; if (tail == NULL) tail = ptr; head = ptr; return ptr; } Node* push_back(double data) { Node* ptr = new Node(data); ptr->prev = tail; if (tail != NULL) tail->next = ptr; if (head == NULL) head = ptr; tail = ptr; return ptr; }
Логика работы обоих методов одинакова. Сначала создается новый объект класса Node в памяти устройства. Затем, настраиваются связи либо с первым объектом списка (при добавлении в начало), либо с последним (при добавлении в конец). И меняются значения указателей head и ptr. В конце мы возвращаем указатель на новый добавленный элемент.
По аналогии реализуются операции удаления элементов в начале и конце двусвязного списка:
void pop_front() { if (head == NULL) return; Node* ptr = head->next; if (ptr != NULL) ptr->prev = NULL; else tail = NULL; delete head; head = ptr; } void pop_back() { if (tail == NULL) return; Node* ptr = tail->prev; if (ptr != NULL) ptr->next = NULL; else head = NULL; delete tail; tail = ptr; }
Далее, мы реализуем метод getAt() и оператор [] для доступа к произвольному элементу двусвязного списка:
Node* getAt(int index) { Node* ptr = head; int n = 0; while (n != index) { if (ptr == NULL) return ptr; ptr = ptr->next; n++; } return ptr; } Node* operator [] (int index) { return getAt(index); }
Воспользуемся методом getAt() в реализации метода insert() для вставки нового элемента в позицию с индексом index (индексы отсчитываются от нуля):
Node* insert(int index, double data) { Node* right = getAt(index); if (right == NULL) return push_back(data); Node* left = right->prev; if (left == NULL) return push_front(data); Node* ptr = new Node(data); ptr->prev = left; ptr->next = right; left->next = ptr; right->prev = ptr; return ptr; }
Наконец, последний метод erase(), который удаляет произвольный элемент с индексом index из связного списка:
void erase(int index) { Node* ptr = getAt(index); if (ptr == NULL) return; if (ptr->prev == NULL) { pop_front(); return; } if (ptr->next == NULL) { pop_back(); return; } Node* left = ptr->prev; Node* right = ptr->next; left->next = right; right->prev = left; delete ptr; }
В целом, у нас получилась реализация двусвязного списка с базовым набором операций. Осталось только выполнить очистку памяти (удаление всех объектов) при удалении объекта класса LinkedList. Делается это, обычно, в деструкторе класса:
~LinkedList() { while (head != NULL) pop_front(); }
Давайте теперь посмотрим, как все это работает. В функции main() создадим объект класса LinkedList и добавим несколько элементов:
int main() { LinkedList lst; lst.push_back(1.0); lst.push_back(2.0); lst.push_back(3.0); lst.push_back(4.0); return 0; }
Переберем элементы и выведем значения на экран:
for (Node* ptr = lst.head; ptr != NULL; ptr = ptr->next) std::cout ptr->data " "; std::cout std::endl;
Или же, можно пройтись в обратном направлении:
for (Node* ptr = lst.tail; ptr != NULL; ptr = ptr->prev) std::cout ptr->data " "; std::cout std::endl;
Верный результат говорит о том, что структура двусвязного списка сформирована верно.
Проверим работу оператора взятия по индексу:
std::cout lst[1]->data std::endl; std::cout lst[0]->data std::endl; std::cout lst[3]->data std::endl;
Обратите внимание, что индекс должен быть корректным, иначе оператор вернет значение указателя NULL и операция ->data приведет к ошибке.
И я еще проверю операции вставки и удаления произвольного элемента:
lst.insert(2, -5.0); lst.insert(20, -10.0); lst.erase(3); lst.erase(30);
Как видим, все работает корректно.
Вот пример того, как можно с нуля реализовать двусвязный список на С++. Конечно, это лишь учебный пример, в реальных проектах лучше использовать двусвязный список из стандартной библиотеки STL. Об этом мы поговорим на следующем занятии.
Видео по теме
#1. О большое (Big O) — верхняя оценка сложности алгоритмов
#2. О большое (Big O). Случаи логарифмической и факториальной сложности
#3. Статический массив. Структура, его преимущества и недостатки
#4. Примеры реализации статических массивов на C++
#5. Динамический массив. Принцип работы
#6. Реализация динамического массива на Python
#7. Реализация динамического массива на С++ с помощью std::vector
#8. Односвязный список. Структура и основные операции
#9. Делаем односвязный список на С++
#10. Двусвязный список. Структура и основные операции
#11. Делаем двусвязный список на С++
#12. Двусвязный список (list) в STL на С++
#13. Очереди типов FIFO и LIFO
#14. Очередь collections.deque на Python
#15. Очередь deque библиотеки STL языка C++
#16. Стек. Структура и принцип работы
#17. Реализация стека на Python и C++
#18. Бинарные деревья. Начало
#19. Бинарное дерево. Способы обхода и удаления вершин
#20. Реализация бинарного дерева на Python
#21. Множества (set). Операции над множествами
#22. Множества set и multiset в C++
#23. Контейнер map библиотеки STL в C++
#24. Префиксное (нагруженное, Trie) дерево. Ассоциативные массивы
#25. Хэш-таблицы. Что это такое и как работают
#26. Хэш-функции. Универсальное хэширование
#27. Метод открытой адресации. Двойное хэширование
#28. Использование хэш-таблиц в Python и С++
© 2024 Частичное или полное копирование информации с данного сайта для распространения на других ресурсах, в том числе и бумажных, строго запрещено. Все тексты и изображения являются собственностью сайта