К основному контенту

Структуры данных

Методология программирования должна включать в себя все аспекты структурирования данных. Программы суть конкретные формулировки абстрактных алгоритмов, основанные на конкретных представлениях и структурах данных. 

Данные предшествуют алгоритмам: нужно иметь некоторые объекты до того, как можно будет что-то с ними делать.

Фундаментальные структуры данных меняют только своё значение, но никогда не меняют ни своё строение, ни множество своих допустимых значений. "Сложные" структуры, напротив, характеризуются изменением во время выполнения программы как своих значений, так и строения.

  • Выбор абстрактного представления реальности
  • Выбор представления данных
  • Фундаментальные структуры данных
    • Стандартные примитивные типы
    • Массивы
    • Записи
    • Множества
    • Файлы или последовательности (у последовательности может меняться длина; но такое изменение структуры тривиально)
  • Динамические структуры данных (т.е. такие, строение которых меняется во время выполнения программы)
    • Рекурсивные типы данных
    • Указатели
    • Списки
      • Линейные списки
    • Деревья
      • Бинарные деревья
      • Сбалансированные деревья
      • Оптимальные деревья поиска
      • Б-деревья (B-trees)
      • Приоритетные деревья поиска (такие деревья допускают экономное представление и позволяют выполнять быстрый поиск по множествам точек на плоскости)
  • Хэш-таблицы (часто используют вместо деревьев поиска)
  • Структуры данных для представления графов
    • Матрица смежности
    • Список смежности
  • Стеки
  • Очереди

Комментарии

Отправить комментарий

Популярные сообщения из этого блога

Сравнение и арифметические операции

Операции сравнения Все операторы сравнения считаются эквивалентными, и их учитывают в алгоритмах поиска и сортировки. Важным элементом таких алгоритмов является сравнение двух величин для определения (при поиске) того, совпадает ли данная величина с искомой, а при сортировке - вышла ли она за пределы данного интервала. Операторы сравнения проверяют, равна или не равна одна величина другой, меньше они ли больше, меньше или равна, больше или равна. Арифметические операции Аддитивные операции (сложения) Включают в себя сложение, вычитание, увеличение и уменьшение счетчика. Мультипликативные операции (умножения) Включают в себя умножение, деление и взятие остатка по модулю. Умножения работают дольше, чем сложения. На практике некоторые алгоритмы считаются предпочтительнее других, если в них меньше умножений, даже если число сложений при этом пропорционально возрастает. Целочисленное умножение или деление на степень двойки образуют специальный случай. Эта операция ...
Отправить комментарий
Далее...

Наихудший случай

Анализ наихудшего случая говорит о максимальном времени работы алгоритма. Анализ наихудшего случая даёт верхние оценки для времени работы частей программы в зависимости от выбранных алгоритмов. При анализе наихудшего случая необходимо найти входные данные, на которых алгоритм будет выполнять больше всего работы.
Отправить комментарий
Далее...

Метод турниров

Метод турниров можно использовать для решения задач, в которых информация, полученная в результате первого прохода по данным, может облегчить последующие проходы. Поиск наибольшего значения Если воспользоваться им для поиска наибольшего значения, то потребуется построение бинарного дерева, все элементы которого являются листьями. На каждом уровне два элемента объединены в пару, причем наибольший из двух элементов копируется в родительский узел. Процесс повторяется до достижения корневого узла. Полное дерево турнира для фиксированного набора данных: Алгоритм поиска второго по величине элемента списка из N значений, требующий около N сравнений В результате каждого сравнения мы получаем "победителя" и "проигравшего". Проигравших мы забываем, и вверх по дереву двигаются только победители. Всякий элемент, за исключением наибольшего, "проигрывает" в точности в одном сравнении. Поэтому для построения дерева турнира требуется N-1 сравнение. Вт...
Отправить комментарий
Далее...