Структура данных — это специальное решение для организации данных, которое предоставляет место для размещения элементов и возможность для их сохранения и извлечения
Просто знайте, что, пока я писал эту книгу, я прожил четыре года, сменил три работы, две страны и пять разных квартир!
структуры и алгоритмов (модель данных и алгоритмы).
приложении В разъясняется, в чем разница между абстрактной структурой данных и конкретной структурой данных. Первая включает в себя API и инварианты, описывающие на высоком уровне, как клиенты будут взаимодействовать с ней, а также результаты и производительность операций. Последняя строится на принципах и API, выраженных абстрактным описанием, с добавлением конкретной реализации
Инварианты — (необязательные) внутренние свойства, которые всегда остаются истинными на протяжении всего жизненного цикла структуры данных. Например, отсортированный список будет иметь один инвариант: каждый элемент не больше своего преемника. Цель инвариантов — убедиться, что условия, необходимые для выполнения контракта с внешними клиентами, всегда выполняются. Они являются внутренним аналогом гарантий в API.
Резюме
• Алгоритмы нужно описывать с точки зрения их ввода, вывода и последовательности инструкций, которые будут обрабатывать ввод и производить ожидаемый вывод.
• Структура данных — это конкретная реализация абстрактного типа данных, состоящая из структуры для хранения данных как таковой и набора алгоритмов, которые ими управляют.
• Абстрагирование задачи означает формулирование четкой постановки задачи и только потом обсуждение ее решения.
• Эффективно упаковать рюкзак может быть непросто (особенно если вы планируете отправиться на Марс!), но с алгоритмами и правильной структурой данных нет (почти) ничего невозможного!
6 А именно, хотя бы один метод для добавления нового элемента в структуру и один метод либо для извлечения указанного элемента, либо для выполнения запроса к структуре данных.
7 В современных архитектурах/языках элемент массива может соответствовать слову, а не байту, но для простоты предположим, что массив символов хранится как массив байтов.
8 В принципе, это не обязательно должно иметь отношение к информатике. Например, вы можете описать в качестве системы стопку папок, которые необходимо изучить, или — распространенный пример на
алгоритмы — это процедуры, последовательность инструкций, направленных на преобразование данных.
структуры данных — это основа, способ организации области памяти для пред
Структура данных — это специальное решение для организации данных, которое предоставляет место для размещения элементов и возможность для их сохранения и извлечения6.
