Структуры данных и алгоритмы

Структура данных — это способ хранения и организации данных в компьютере.

Структура данных — это совокупность элементов данных, которые имеют определённые логические связи, используют определённую структуру хранения в компьютере и инкапсулируют соответствующие операции. Она включает три аспекта: логические связи, связи хранения и операции.

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

Зачем изучать структуры данных и алгоритмы?

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

Изучение структур данных и алгоритмов позволяет:

• Повышение эффективности кодаХорошие структуры данных и алгоритмы позволяют программам работать быстрее и потреблять меньше памяти
• Решение сложных задач: Многие практические задачи требуют конкретных структур данных и алгоритмов для эффективного решения.
• Основы для собеседованийЗнания, которые почти всегда проверяются на технических собеседованиях
• Основы программированияЭто краеугольный камень всех передовых методик программирования

Что нужно знать перед чтением этого руководства?

Прежде чем начать читать этот учебник, вы должны обладать базовыми знаниями программирования, например, понимать концепции программирования на Python или Java.

Если вы ещё не знакомы с этими концепциями, мы рекомендуем сначала прочитать нашУчебник по PythonилиУчебник по Java。

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

Объяснение структур данных и алгоритмов

Структуры данныхЭто похоже на то, как мы организуем предметы. Представьте свою книжную полку:

• Если книги сложены случайным образом, найти книгу будет трудно (неэффективная структура данных).
• Если их расположить по категориям, автору или в алфавитном порядке, поиск книги происходит быстро (эффективная структура данных).

АлгоритмыЭто шаги и методы решения задач, подобно рецепту для приготовления блюда:

• Одни и те же ингредиенты (данные) при разных способах приготовления (алгоритмах) дадут разные результаты
• Некоторые методы быстрые и эффективные, тогда как другие требуют много времени и труда.

Основные термины

Распространённые структуры данных

• Стек:Стек — это особый линейный список; вставка и удаление узлов данных могут выполняться только на одном фиксированном конце списка.
• Очередь:Очередь похожа на стек и также является специальным линейным списком. В отличие от стека, очередь допускает вставку только на одном конце списка, а удаление — на другом конце.
• Массив:Массив — это агрегатный тип данных; это набор нескольких переменных одного типа, организованных вместе по порядку.
• Связный список:Связный список — это структура данных, в которой элементы данных хранятся в соответствии с цепной структурой хранения, характеризующейся физической не непрерывностью.
• Дерево:Дерево — типичная нелинейная структура; это конечное множество K, которое включает 2 узла.
• Граф:Граф — это ещё одна нелинейная структура данных. В структуре графа узлы данных обычно называются вершинами, а рёбра — упорядоченными парами вершин.
• Куча:Куча — это специальная древовидная структура данных; обычно рассматриваемая куча — это двоичная куча.
• Хеш-таблица:Хеш-таблица происходит от хеш-функции. Её идея состоит в том, что если в структуре есть запись, ключ которой равен T, то запись можно найти в месте хранения F(T), поэтому нужную запись можно получить напрямую без операций сравнения.

Основные алгоритмы

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

• Поиск:Поиск заключается в нахождении узлов в структуре данных, удовлетворяющих определённым условиям. Обычно, задавая значение некоторого поля, находят узлы с этим значением поля.
• Вставка:Добавление новых узлов в структуру данных.
• Удаление:Удаление указанного узла из структуры данных.
• Обновление:Изменение значения одного или нескольких полей указанного узла.
• Сортировка:Переупорядочивание узлов в заданном порядке, например по возрастанию или убыванию.

Ссылки

Hello Algo:https://github.com/krahets/hello-algo

Реализация алгоритмов на Python:https://github.com/TheAlgorithms/Python。

Play-with-Algorithms: https://github.com/liuyubobobo/Play-with-Algorithms。