СТРУКТУРЫ ДАННЫХ Лектор Спиричева Наталия Рахматулловна Ст. преподаватель каф

Информационных технологий

данных

ДМК-Пресс, 2010 — 272 с.
Котов В.М. Алгоритмы и структуры

данных. –Минск:БГУ,2011.-267с
Гагарина Л.Г. Алгоритмы и структуры данных. Москва: ИНФРА-М, 2009 – 304 с.
4. Т. Х. Кормен, Ч.И. Лейзерсон, Р.Л. Ривест, К. Штайн. Алгоритмы: построение и анализ. – Вильямс, 2006
Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. – Вильямс, 2000
Кнут Д. Искусство программирования для ЭВМ. (1978)

структур данных
Операции над структурами данных
Структурность данных и технология программирования

Вирт)
Алгоритм
+
Структуры данных
=
Программа

алгоритмы служат теми материалами, из которых строятся программы. Более того,

сам компьютер состоит из структур данных и алгоритмов.

Встроенные структуры данных представлены теми регистрами и словами памяти, где хранятся двоичные величины. Заложенные в конструкцию аппаратуры алгоритмы - это воплощенные в электронных логических цепях жесткие правила, по которым занесенные в память данные интерпретируются как команды, подлежащие исполнению.

операций при решении той или иной специфической задачи.

Концепция структур данных

и алгоритмов их обработки

очень интересно. Это слово еще не вошло в Webster’s New

World Dictionary даже 1957 года издания. Там можно найти только старую форму “Algorism”, что означает правило выполнения арифметических действий с использованием арабских цифр. К средним векам сложились две враждующие партии среди приверженцев различных традиций счета. Абакисты считали на абаках – счетах, алгоритмики же использовали начатки математической символики. Происхождение слова algorism долгое время оставалось неясным.

учебника по математике – Abu Ja’far Mohammed ibn Musa al-Khowarizmi

(около 825 г.), означающего буквально “Отец Джафара, Магомет, сын Моисея, уроженец Ховаризма”. В настоящее время Ховаризм – город Хива. Вышеназванный уроженец Ховаризма написал знаменитую книгу “Kitab al jabr w’al-muqabala” (“Правила восстановления и преобразования”); заглавие этой книги дало начало другому слову – “алгебра”, хотя сама книга в действительности была не совсем алгебраической.

“Oxford English Dictionary”, слово было “ошибочно видоизменено” в результате “укоренившейся

путаницы” со словом arithmetic. Изменение algorism на algoritm нетрудно понять, если учесть, что истинное происхождение слова давно было забыто.

алгоритм чаще всего подразумевали изложенный Евклидом процесс нахождения наибольшего общего

делителя двух чисел (алгоритм Евклида).

Алгоритм Евклида
Даны два целых положительных числа m и n. Требуется найти их наибольший общий делитель, т.е. наибольшее положительное целое число, которое нацело делит как m, так и n.
Шаг 1. [Нахождение остатка.] Разделим m на n. Пусть остаток равен r. (Имеем 0<=rШаг 2. [Это нуль?] Если r=0, алгоритм кончается; n – искомое число.
Шаг 3. [Замена] Положите m<-n, n<-r и возвращайтесь к шагу 1.

шаг алгоритма должен быть точно определен. Действия, которые необходимо произвести,

должны быть строго и недвусмысленно определены в каждом возможном случае.
Ввод. Алгоритм имеет некоторое (может быть, равное нулю) число входных данных, то есть величин, заданных ему до начала работы. Эти данные берутся из некоего конкретного множества объектов.

есть величин, имеющих вполне определенные отношения ко входным данным.
Эффективность. От

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

сколько раз выполняется каждый шаг алгоритма.

приспособляемость алгоритма к вычислительным

машинам,

простота

изящество

можно свести к схеме организации информации в памяти компьютера. Алгоритм

же является соответствующим процедурным элементом в структуре программы - он служит рецептом расчета.

в памяти машины и называется еще структурой хранения, внутренней структурой

или структурой памяти.

Рассмотрение структуры данных без учета ее представления в машинной памяти называется абстрактной или ЛОГИЧЕСКОЙ структурой.

(структурированные, композитные, сложные).

Простыми называются такие структуры данных, которые не

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

Интегрированными называются такие структуры данных, составными частями которых являются другие структуры данных - простые или в свою очередь интегрированные.

между элементами данных следует различать НЕСВЯЗНЫЕ структуры (векторы, массивы, строки,

стеки, очереди) и СВЯЗНЫЕ структуры (связные списки).

Весьма важный признак структуры данных - ее изменчивость - изменение числа элементов и (или) связей между элементами структуры. В определении изменчивости структуры не отражен факт изменения значений элементов данных, поскольку в этом случае все структуры данных имели бы свойство изменчивости. По признаку изменчивости различают структуры СТАТИЧЕСКИЕ, ПОЛУСТАТИЧЕСКИЕ, ДИНАМИЧЕСКИЕ.

По этому признаку структуры можно делить на ЛИНЕЙНЫЕ И НЕЛИНЕЙНЫЕ

структуры.

В зависимости от характера взаимного расположения элементов в памяти линейные структуры можно разделить на структуры с ПОСЛЕДОВАТЕЛЬНЫМ распределением элементов в памяти (векторы, строки, массивы, стеки, очереди) и структуры с ПРОИЗВОЛЬНЫМ СВЯЗНЫМ распределением элементов в памяти (односвязные, двусвязные списки). Пример нелинейных структур - многосвязные списки, деревья, графы.

с понятием "типы данных". Информация по каждому типу однозначно определяет

:
структуру хранения данных указанного типа, т.е. выделение памяти и представление данных в ней, с одной стороны, и интерпретацию двоичного представления, с другой;
множество допустимых значений, которые может иметь тот или иной объект описываемого типа;
множество допустимых операций, которые применимы к объекту описываемого типа.

ранее определенных типов данных. Значения, принадлежащие к такому типу, обычно

представляют собой совокупности значений компонент, принадлежащих к определенным ранее типам компонент, такие составные значения называются структурированными. Если имеется только один тип компонент, т.е. все компоненты принадлежат одному типу, то он называется базовым.

Число различных значений, принадлежащих типу Т, называется кардинальным числом Т. Кардинальное число определяет размер памяти, нужной для размещения переменной x типа T. Этот факт обозначается так: x:T.

связные
списки

Графы

Деревья
Последовательные

Прямого доступа

Комбинированного доступа

Организованные разделами

данными, включая их хранение, добавление и удаление, модификацию, поиск и

т.д. Структура данных поддерживает определенный порядок доступа к ним. Структуру данных можно рассматривать как своего рода склад или библиотеку.

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

и в объектно-ориентированных.

При этом следует придерживаться объектно-ориентированного стиля программирования:

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

структуры, ранее уже реализованной, или на основе массива и набора

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

значений, набор операций, которые можно применять к таким значениям и, возможно, способ

реализации хранения значений и выполнения операций. Любые данные, которыми оперируют программы, относятся к определённым типам.

выделить во всём рассматриваемом множестве (предметной области).

Математически тип может быть определён двумя

способами:

Множеством всех значений, принадлежащим типу.
Предикатной функцией, определяющей принадлежность объекта к данному типу

Ассемблере х86 различаются типы «целое число» и «вещественное число». Это

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

Концепция типа данных появилась в языках программирования высокого уровня как естественное отражение того факта, что обрабатываемые программой данные могут иметь различные множества допустимых значений, храниться в памяти компьютера различным образом, занимать различные объёмы памяти и обрабатываться с помощью различных команд процессора.

соответствуют подобным типам в математике. Например, тип «целое число» большинства

языков программирования не соответствует принятому в математике типу «целое число», так как в математике указанный тип не имеет ограничений ни сверху, ни снизу, а в языках программирования эти ограничения есть.

(включая полиморфные). Это следует из того, что все языки основаны

на машине Тьюринга или на лямбда-исчислении. И в том, и в другом случае необходимо оперировать как минимум одним типом данных — хранящимся на ленте (машина Тьюринга) или передаваемым и возвращаемым из функции (лямбда-исчисление).

Это следует из того, что все языки основаны на машине Тьюринга или

на лямбда-исчислении. И в том, и в другом случае необходимо оперировать как минимум одним типом данных — хранящимся на ленте (машина Тьюринга) или передаваемым и возвращаемым из функции (лямбда-исчисление).

Языки без типов

кроме того, развитые языки программирования предоставляют программисту возможность описывать собственные

типы данных, комбинируя или расширяя существующие.

Базовые типы

соглашениям о типах, поддерживаемых большинством систем программирования, сложилась ситуация, когда

программисты могут быстро менять свои рабочие инструменты, а программы не требуют больших переделок при переносе исходных текстов в другую среду.
Документация. Использование того или другого типа данных объясняет намерения программиста

Преимущества от использования типов данных

составные типы, предопределенные и определяемые типы и т.д. Существенно то,

что несмотря на многолетнее использование типов данных в отечественном программировании, так и не сложилась устойчивая и общепринятая русскоязычная терминология.

или языке баз данных.

«Уточняемый тип данных" - возможность определения

типа на основе встроенного типа данных, значения которого упорядочены.

Перечисляемые типы данных - явно определяемые целые типы с конечным числом именованных значений.

что в языке предопределены средства спецификации таких типов и некоторый

набор операций, дающих возможность доступа к компонентам составных значений

Указательные типы дают возможность работы с типизированными множествами абстрактных адресов переменных, содержащих значения некоторого типа.

Типы, определяемыми пользователями

данных?

Контрольные вопросы