| Структуры данных |
| 1 | Структура данных — программная единица, позволяющая хранить и обрабатывать множество однотипных и/или логически связанных данных в вычислительной технике. Для добавления, поиска, изменения и удаления данных структура данных предоставляет некоторый набор функций, составляющих её интерфейс. Термин «структура данных» может иметь несколько близких, но тем не менее различных значений[1]: Абстрактный тип данных; Реализация какого-либо абстрактного типа данных; Экземпляр типа данных, например, конкретный список; В контексте функционального программирования — уникальная единица (англ. unique identity), сохраняющаяся при изменениях. |
| 2 | О ней неформально говорят как об одной структуре данных, несмотря на возможное наличие различных версий. Структуры данных формируются с помощью типов данных, ссылок и операций над ними в выбранном языке программирования. Различные виды структур данных подходят для различных приложений; некоторые из них имеют узкую специализацию для определённых задач. Например, B-деревья обычно подходят для создания баз данных, в то время как хеш-таблицы используются повсеместно для создания различного рода словарей, например, для отображения доменных имён в интернет-адреса компьютеров. |
| 3 | При разработке программного обеспечения сложность реализации и качество работы программ существенно зависит от правильного выбора структур данных. Это понимание дало начало формальным методам разработки и языкам программирования, в которых именно структуры данных, а не алгоритмы, ставятся во главу архитектуры программного средства. Большая часть таких языков обладает определённым типом модульности, позволяющим структурам данных безопасно переиспользоваться в различных приложениях. |
| 4 | Объектно-ориентированные языки, такие как Java, C# и C++, являются примерами такого подхода. Многие классические структуры данных представлены в стандартных библиотеках языков программирования или непосредственно встроены в языки программирования. Например, структура данных хэш-таблица встроена в языки программирования Lua, Perl, Python, Ruby, Tcl и др. Широко используется стандартная библиотека шаблонов (STL) языка C++. |
| 5 | Фундаментальными строительными блоками для большей части структур данных являются массивы, записи (struct в Си и record в Паскале), размеченные объединения (union в Си) и ссылки. Например, двусвязный список может быть построен с помощью записей и ссылок, где каждая запись (узел) будет хранить данные и ссылки на «левый» и «правый» узлы. 2 2-3-дерево Сбалансированное дерево, в котором: 1. каждый внутренний узел имеет либо 2, либо 3 сыновей; 2. |
| 6 | все пути от корня до любого листа имеют одинаковую длину. B B-дерево Сбалансированное -арное дерево, в котором: 1. корень есть либо лист, либо имеет не менее 2-х сыновей; 2. каждый узел, кроме корня и листьев, имеет от до сыновей; 3. все пути от корня до любого листа имеют одинаковую длину. M m-арное дерево Дерево, в котором каждый узел имеет не более сыновей. А Абстрактный тип данных (АТД) Математическая модель данных, состоящая из множества объектов и определённых на них операторов. |
| 7 | АВЛ-дерево Сбалансированное двоичное дерево, в котором у любого внутреннего узла высота левого и правого поддеревьев отличаются не более чем на единицу. Названо по именам создателей - советских математиков Г.М. Адельсон-Вельского и Е.М. Ландиса. Агрегированная структура данных Структура данных, в которой имена присваиваются линейно связанным совокупностям ячеек. Алгоритм Предназначенная для решения некоторого класса задач конечная последовательность элементарных инструкций, каждая из которых имеет чёткий смысл и может быть выполнена с конечными вычислительными затратами. |
| 8 | Алфавитный код Схема кодирования, при которой каждому символу первичного алфавита ставится в соответствие кодовое слово. Антагонистическая игра Игра двух игроков с нулевой суммой: сумма выигрышей игроков равна нулю. Б Бинарное дерево См. Двоичное дерево. В Висячая вершина См. Концевая вершина графа (орграфа). Внешняя обработка данных Обработка данных, хранящихся во внешней памяти и структурированных в виде файлов. |
| 9 | Внешняя сортировка Сортировка больших массивов данных, при которой организуется обмен данными между ОП и внешней памятью. Внутренняя сортировка Сортировка, при которой все сортируемые объекты помещаются в ОП. Вторичный алфавит Алфавит кодированных сообщений (чаще всего двоичный). Высота дерева Высота корня дерева. Высота узла Длина самого длинного пути от этого узла до какого-либо листа. Г Глубина узла Длина пути от корня до этого узла. |
| 10 | Глубинная нумерация Нумерация в порядке посещения при обходе в глубину вершин графа или орграфа. Глубинный остовный лес Лес, сформированный дугами или рёбрами, ведущими к непосещённым вершинам в процессе поиска в глубину. Граф Упорядоченная пара множеств, первое из которых дискретно (множество вершин), второе есть множество неупорядоченных пар элементов первого множества (множество рёбер). Д Данные Информация, представленная в формализованном виде на некотором носителе, пригодном для обработки с помощью некоторого алгоритма. |
| … |
Комментарии