Структуры хранения данных

1.

НИЖЕГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМ. Н.И. ЛОБАЧЕВСКОГО
ИНСТИТУТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ, МАТЕМАТИКИ И МЕХАНИКИ
Учебный курс
МЕТОДЫ ПРОГРАММИРОВАНИЯ - 2

2.

Нижегородский государственный университет им. Н.И. Лобачевского
Институт информационных технологий, математики и механики
Учебный курс:
Методы программирования - 2
Тема 2:
Структуры хранения данных
Гергель В.П., профессор ,
директор института ИТММ

3.

Содержание
Глава 1.
Структура действия и структуры данных
1.2. Структура хранения данных
1. Структуры программы
2. Структуры машинной памяти
3. Структура хранения вектора
4. Использование ОПП для представления структур данных
Вопросы для обсуждения
ИТММ ННГУ,
2002-2019
Структуры хранения данных
3 из 16

4.

1.2. Структура хранения данных
1. Структура программы…
Определение 1.7. Машинный образ абстрактной структуры
данных называется структурой хранения данных.
Структура программы:
адрес
имя
аппаратура
адресация
ячейка
команда
аппаратура
чт/зп
или операнд
коп
операция
операнды
или адрес
ИТММ ННГУ,
2002-2019
Структуры хранения данных
4 из 16

5.

1.2. Структура хранения данных
1. Структура программы
Для хранения команд используются ячейки памяти
Отношение следования команд реализуются
счетчиком команд или командами передачи управления
Аппаратура ЭВМ приспособлена для хранения
программ
ИТММ ННГУ,
2002-2019
Структуры хранения данных
5 из 16

6.

1.2. Структура хранения данных
2. Структура машинной памяти …
Структура элемента памяти
ИТММ ННГУ,
2002-2019
Структуры хранения данных
6 из 16

7.

1.2. Структура хранения данных
2. Структура машинной памяти
Отношение "иметь имя"
Структура памяти
S=({ячейки}, {адреса}, {значения}; pA, pB, p)
Отношение "иметь
значение"
Отношение следования между элементами памяти
реализовано программным путем (в отличие от структур
программ)
Программа может реализовать только те отношения,
которые могут быть охарактеризованы как отношения целых
чисел (адресов)
ИТММ ННГУ,
2002-2019
Структуры хранения данных
7 из 16

8.

1.2. Структура хранения данных
3. Структура хранения вектора …
Возможный способ хранения вектора – использование
непрерывной области памяти
Два элемента являются соседними, если адрес одного из них
отличается на единицу от адреса другого
Такое размещение не фиксируется в аппаратуре, а должно
быть реализовано программой
Значение (база) – может играть роль имени всего вектора,
смещение до элемента определяется номером элемента
ИТММ ННГУ,
2002-2019
Структуры хранения данных
8 из 16

9.

1.2. Структура хранения данных
3. Структура хранения вектора …
Определение 1.8. Структура хранения подобного типа
(т.е. последовательность однотипных элементов единиц
памяти с адресами, возрастающих на единицу),
обеспечивающая реализацию абстрактных линейных
структур данных (векторов), обычно называется
вектором памяти или одноместным (одноиндексным)
массивом.
ИТММ ННГУ,
2002-2019
Структуры хранения данных
9 из 16

10.

1.2. Структура хранения данных
3. Структура хранения вектора
Пример 1.3. Матрица A=(aij)
Адрес
(aij) = + 3*( i-1 ) + (j-1)
Каждый элемент матрицы участвует в двух отношениях (по
строке и по столбцу):
• Следующий по строке – адрес + 1
• Следующий по столбцу – адрес + 3
ИТММ ННГУ,
2002-2019
Структуры хранения данных
10 из 16

11.

1.2. Структура хранения данных
4. Использование ООП для представления
структур данных
Для реализации структур данных на ЭВМ наиболее
адекватным подходом является объектноориентированное программирование:
• класс – схема структуры данных;
• объект – экземпляр структуры;
• поля объекта могут использоваться для
хранения элементов структуры, а методы –
для реализации отношений.
ИТММ ННГУ,
2002-2019
Структуры хранения данных
11 из 16

12.

Заключение
Необходимость разработки программ для реализации
отношений
Использование непрерывных участков памяти для
хранения элементов структуры
Понятие вектора памяти
Примеры структур хранения: вектора и матрицы
Использование ООП при реализации структур данных
на ЭВМ
ИТММ ННГУ,
2002-2019
Структуры хранения данных
12 из 16

13.

Вопросы для обсуждения
Практическое использование изученного
теоретического материала
ИТММ ННГУ,
2002-2019
Структуры хранения данных
13 из 16

14.

Темы занятий для самостоятельной работы
Реализация вектора и матрицы с использованием ООП
• Реализация класса TSring для символьных строк
ИТММ ННГУ,
2002-2019
Структуры хранения данных
14 из 16

15.

Следующая тема
Примеры разработки структур хранения
ИТММ ННГУ,
2002-2019
Структуры хранения данных
15 из 16

16.

Контакты
Нижегородский государственный университет им.
Н.И. Лобачевского (www.unn.ru)
Институт информационных технологий, математики
и механики (www.itmm.unn.ru)
603950, Нижний Новгород, пр. Гагарина, 23,
р.т.: (831) 462-33-56,
Гергель Виктор Павлович
(http://www.software.unn.ru/?dir=17)
E-mail: [email protected]
ИТММ ННГУ,
2002-2019
Структуры хранения данных
16 из 16