1

1.

ТАШКЕНТСКИЙ УНИВЕРСИТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ
ИМЕНИ МУХАММАДА АЛ-ХОРАЗМИЙ
DTSA16MBK
СТРУКТУРЫ ДАННЫХ
И АЛГОРИТМЫ
ТЕМА
01
ТИПЫ И АЛГОРИТМЫ ДАННЫХ.
АБСТРАКТНЫЕ СТРУКТУРЫ ДАННЫХ
1

2. Типы и алгоритмы данных. Абстрактные структуры данных

1
Данные и структуры данных
2
Разработка и анализ алгоритмов
3
Этапы представления данных
4
Классификация структуры данных
5
Операции над структурами данных
СТ РУ К Т У Р Ы Д А Н Н Ы Х И А Л ГО Р И Т М Ы
2

3. 1. Данные и структуры данных

Информация (от лат. informatio - сведения, разъяснения, представление,
изложение) это сведения (сообщения) о ком-либо или о чем либо, то есть
обо всем что нас окружает.
Данные это информация выраженная в какой либо форме
(электрический сигнал, звуковая волна, символы, знаки и т.д.)
Данные = Информация + Форма
Структура данных (англ. data structure) – программная единица,
позволяющая хранить и обрабатывать множество однотипных и/или
логически связанных данных в вычислительной технике. Для добавления,
поиска, изменения и удаления данных структура данных предоставляет
некоторый набор функций, составляющих её интерфейс.
Структура данных — это способ организации данных, а алгоритм —
это метод решения проблем.
СТ РУ К Т У Р Ы Д А Н Н Ы Х И А Л ГО Р И Т М Ы
3

4. Графическое и математическое представление структуры данных

Под СТРУКТУРОЙ ДАННЫХ в общем
случае понимают множество элементов данных и
множество связей между ними.
При этом под элементами данных может
подразумеваться как простое данное так и
структура данных. Под отношениями между
данными понимают функциональные связи
между ними и указатели на то, где находятся эти
данные.
S = { D, R }
где
S - структура данных,
D – данные, R - отношения.
R = (Порядок, Операции)
Данные
Отношения
Другие
элементы
D1
D2
D2
D3
Последовательность
D3
Множество
D1
D2
D1
D3
Дерево
СТ РУ К Т У Р Ы Д А Н Н Ы Х И А Л ГО Р И Т М Ы
D1
D2
D3
Граф
4

5. Типы данных и его абстракция

В языках программирования понятие "структуры данных" тесно связано с понятием
"типы данных". Любые данные, т.е. константы, переменные, значения функций или
выражения, характеризуются своими типами. Информация по каждому типу однозначно
определяет:
1) структуру хранения данных указанного типа,
т.е. выделение памяти и
представление данных в ней, с одной стороны, и интерпретацию двоичного
представления, с другой;
2) множество допустимых значений, которые может иметь тот или иной объект
описываемого типа;
3) множество допустимых операций, которые применимы к объекту описываемого
типа.
Абстрактный тип данных (АТД) — это математическая модель плюс различные
операторы, определенные в рамках этой модели.
Для представления АТД используются структуры данных, которые представляют
собой набор переменных, возможно, различных типов данных, объединенных
определенным образом.
СТ РУ К Т У Р Ы Д А Н Н Ы Х И А Л ГО Р И Т М Ы
5

6. 2. Разработка и анализ алгоритмов

«Алгоритмы» и «структуры данных» являются одними из основополагающих
понятий, рассматриваемых в Computer Science.
Слово «Алгоритм» происходит от algorithmi - латинского написания имени
аль-Хорезми, под которым в средневековой Европе знали величайшего
математика из Хорезма (город в современном Узбекистане) Мухаммеда бен
Мусу, жившего в 783-850 гг. В своей книге "Об индийском счете" он
сформулировал правила записи натуральных чисел с помощью арабских цифр и
правила действий над ними столбиком. В дальнейшем алгоритмом стали
называть точное предписание, определяющее последовательность действий,
обеспечивающую получение требуемого результата из исходных данных.
Добавим к его утверждению, что для написания и реализации программы
необходим алгоритмический язык и получим формулу:
Программа = Алгоритм + Данные
СТ РУ К Т У Р Ы Д А Н Н Ы Х И А Л ГО Р И Т М Ы
6

7. Аспекты теории алгоритмов

Теоретический аспект
Практический аспект
Теоретический аспект: при исследовании
некоторой задачи результаты теории алгоритмов
позволяют ответить на вопрос – является ли эта
задача в принципе алгоритмически разрешимой.
В случае алгоритмической разрешимости задачи
– следующий важный теоретический вопрос –
это вопрос о принадлежности этой задачи к
классу NP–полных задач, при утвердительном
ответе на который, можно говорить о
существенных
временных
затратах
для
получения точного решения для больших
размерностей исходных данных.
Практический аспект: методы и методики
теории алгоритмов (в основном разделов
асимптотического и практического анализа)
позволяют осуществить:
• рациональный выбор из известного множества
алгоритмов решения данной задачи с учетом
особенностей их применения (например, при
ограничениях на размерность исходных
данных или объема дополнительной памяти);
• получение
временных
оценок
решения
сложных задач;
• получение
достоверных
оценок
невозможности решения некоторой задачи за
определенное
время,
что
важно
для
криптографических методов;
• разработку
и
совершенствование
эффективных алгоритмов решения задач в
области обработки информации на основе
практического анализа.
СТ РУ К Т У Р Ы Д А Н Н Ы Х И А Л ГО Р И Т М Ы
7

8. Немного о способах представления алгоритмов

При задании алгоритма необходимо позаботиться о том, чтобы
алгоритм
воспринимался
всеми
возможными
исполнителями
однозначно и точно, чтобы его можно было выполнить при любых
допустимых исходных условий, и чтобы необходимый результат был
получен за приемлемое время.
Среди множества известных способов представления алгоритмов,
можно выделить:
• словесно-формульное представление - описание алгоритма в
словесной форме с использованием математических или других
формул;
• графическое представление - подача алгоритма в виде блоксхем, таблиц, формул, схем, рисунков и тому подобное;
• программное
представление
запись
алгоритма
на
специализированном языке программирования (псевдокоде) или на
конкретном языке программирования.
СТ РУ К Т У Р Ы Д А Н Н Ы Х И А Л ГО Р И Т М Ы
8

9. 3. Этапы представления данных

Занося информацию в компьютер, представляем ее в каком-то виде,
который на наш взгляд упорядочивает данные и придает им смысл. Машина
отводит поле для поступающей информации и задает ей какой-то адрес. Таким
образом получается, что мы обрабатываем данные на логическом уровне, как
бы абстрактно, а машина делает это на физическом уровне.
Содержательный этап
УРОВНИ
ПРЕДСТАВЛЕНИЯ
ДАННЫХ
Логический этап
Физический этап
СТ РУ К Т У Р Ы Д А Н Н Ы Х И А Л ГО Р И Т М Ы
9

10. Уровни представления данных пример

На содержательном уровне структур данных исследуются
конкретные объекты обработки, их свойства и отношения
между объектами. На этом уровне важны не только
значения, но и определения смысла данных.
На логическом или абстрактном уровне структура данных
считается машинно-независимым логическим понятием, и
определение массивов данных как объектов исследования,
и реализован алгоритм
Физический уровень. На этом уровне рассматриваются
память компьютера и представление в ней значений (ячейки,
разряды ячеек, их адреса и взаимное расположение
значений.), т.е. отображение данных в памяти компьютера
СТ РУ К Т У Р Ы Д А Н Н Ы Х И А Л ГО Р И Т М Ы
Проблема А + Б
Ввод 2 числа. Вывод суммы
Пример: 2, 3
Результат: 5
#include <iostream.h>
void main()
{
int A=2,B=3;
cin >> A >> B;
cout << A+B;
}
2
3
5
10

11. 4. Классификация структур данных

1. С точки зрения архитектуры можно выделить:
линейные структуры – одномерные массивы, линейные списки, линейные очереди,
стеки;
нелинейные структуры – списки с пропуском, иерархическое дерево, графы;
прямоугольные структуры – двумерные и многомерные массивы;
кольцевые структуры – кольцевые списки, кольцевые очереди, некоторые
реализации графов;
ветвящиеся структуры – деревья различных видов, некоторые реализации графов;
сетевые структуры – графы.
2. По изменчивости структуры во времени или в процессе выполнения
программы:
- статические структуры - структуры, неменяющиеся до конца выполнения программы
(записи, массивы, строки, вектора)
- полустатические структуры (стеки, деки, очереди)
- динамические структуры - происходит полное изменение при выполнении программы
СТ РУ К Т У Р Ы Д А Н Н Ы Х И А Л ГО Р И Т М Ы
11

12. 4. Классификация структуры данных

3. По упорядоченности структуры:
- линейные (вектора, массивы, стеки, деки, записи)
- нелинейные (многосвязные списки, древовидные структуры, графы)
4. По уровню сложности структуры:
простые – обычные переменные или константы языков программирования
стандартных типов, а также динамические переменные этих же типов;
наборы однотипных данных – массивы, одно- и многомерные;
составные – записи и объекты классов и подобные структуры;
динамические структуры с внутренними связями – списки, деревья, графы.
СТ РУ К Т У Р Ы Д А Н Н Ы Х И А Л ГО Р И Т М Ы
12

13. 5. Операции над структурами данных

Над всеми структурами данных могут выполняться четыре основные операции:
создание, уничтожение, выбор (доступ), обновление.
• Операция создания заключается в выделении памяти для структуры данных.
Память может выделяться в процессе выполнения программы при первом появлении
имени переменной в исходной программе или на этапе компиляции. ( i n t A ; )
• Операция уничтожения структур данных противоположна по своему действию
операции создания.
(return 0;)
• Операция выбора используется программистами для доступа к данным внутри
самой структуры. Форма операции доступа зависит от типа структуры данных, к
которой осуществляется обращение.
(cout << A; )
• Операция обновления позволяет изменить значения данных в структуре данных.
(A = 5;)
Помимо этих общих операций для каждой структуры данных могут быть
определены операции специфические, работающие только с данными указанного
типа (данной структуры).
СТ РУ К Т У Р Ы Д А Н Н Ы Х И А Л ГО Р И Т М Ы
13

14.

ТАШКЕНТСКИЙ УНИВЕРСИТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ
ИМЕНИ МУХАММАДА АЛ-ХОРАЗМИЙ
СПАСИСО ЗА ВНИМАНИЕ!