Типы данных и распределение памяти

1. Тема: Типы данных и распределение памяти

2. Иерархия типов данных

3. Классификация типов данных

Приведём классификацию типов данных, с
которыми возможно работать средствами ЯА:
Простейшие / элементарные / базовые: типы
данных МП, поддерживаемые на уровне
системы команд МП.
Файлы: поддерживаемые на уровне ОС.
Фундаментальные: поддерживаемые на уровне
СК ЯА.
Абстрактные / динамические: полностью
моделируемые программистом.

4. Типы данных и уровни архитектуры ВС

Типы данных
Уровни архитектуры
Простейшие
Машинный
Файлы
ОС
Фундаментальные
ЯА
Абстрактные
ЯПВУ

5. Абстрактные / динамические типы данных

6. АТД

1.
2.
3.
Абстрактный тип данных (АТД):
множество объектов данных (1 или более
определение типов);
набор абстрактных операций над ними;
инкапсуляция этих объектов и операций таким
образом, чтобы пользователь нового типа данных
не мог манипулировать объектами данных этого
типа иначе, как только с помощью определённых
абстрактных операций (ему необходимо знать
лишь имя нового типа, синтаксис и семантику
доступных операций).

7. Графическое представление объектов данных АТД

Информационные
поля – для данных
Ссылочное / адресное
поле
e1
*
Указатель
Пустой указатель /
пустая ссылка
nil
…
en
*

8. Графическое представление связей между объектами данных АТД

e1
*
e2
*
e3
e4
*
e5
nil
*
nil
"Звёздочки" подразумевают адрес начала размещения в
памяти следующего объекта данных.
Стрелки визуально отображают, на какой именно объект
данных имеется ссылка.
Пустая ссылка – nil – подразумевает недопустимое значение
адреса (ссылку на "особую" ячейку памяти.

9. АТД в ЯА

Мы будем использовать прагматический метод абстрагирования,
состоящий в выражении АТД через типы данных,
реализованные в языке (ЯА – в нашем случае).
АТД в ЯП – конструкция (кластер / модуль / класс), состоящая из
следующих частей:
1.
Внешность /интерфейс / спецификация, содержащая имя
АТД, имена операций с указанием типов аргументов и
значений и т.п.
2.
Конкретное описание – описание операций и объектов, с
которыми они работают, средствами ЯП.
3.
Абстрактное описание средствами ЯП более высокого
уровня (включая декларативные).
4.
Описание корректности представления, определяющее, в
каком смысле конкретное описание верно представляет
абстрактное.

10. Операции над АТД

Полный тип данных – обеспечивающий достаточно операций
для того, чтобы все требующиеся пользователю действия с
объектами могли быть выполнены с приемлемой
эффективностью.
Классы операций
Примитивные
конструкторы
Конструкторы
Создают
объекты
данного типа
Часто не
имеют
аргументов
Используют
объекты данного
типа в качестве
аргументов
Создают
другие объекты
такого же типа
Модификаторы
Наблюдатели
/ селекторы
Деструкторы
Модифицируют
объекты
данного типа
Используют в
качестве
аргументов
объекты
данного типа,
а результат –
другого типа
Удаляют
объекты
данного типа

11. Динамические объекты

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

12. Понятие "список"

Понятие "список"

13. Список в ЯП

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

14. Линейный однонаправленный список

15. Линейный однонаправленный список в ЯП

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

16. Графическое представление ЛОС

list
*
e1
*
…
en
nil
Произвольный n-элементный список с указателем list.
empty
nil
Указатель на пустой список.

17. Прагматика списков

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

18. Список vs. массив

1.
Создадим массив array и заполним его
неотрицательными целыми числами размерности
byte.
array
2
1
5
3
2
1
10
9

19. Список vs. массив

2.
Удалим все элементы "2". Вопрос: как показать,
что на их месте ничего нет, ведь диапазон 0…255?!
array
?
1
5
3
?
1
10
9

20. Список vs. массив

3.
Как (куда) добавить элементы, если их больше 2?!
6
array
6
7
1
5
3
7
8
1
10
9

21. Свойства списков

Достоинства:
Длина не фиксирована.
Занимают столько места, сколько нужно в данный
момент.
Вставка / удаление / перестановка звеньев
осуществляется быстрее: на перемещением
объектов, а заменой ссылок.
Недостатки:
Расход памяти на ссылки.
Доступ к произвольному элементу осуществляется
лишь посредством просмотра ссылок всех
предыдущих.

22. Основные операции над списками

Примитивный конструктор: создание пустого списка.
Конструкторы:
Присоединение списка к списку.
Порождение новых списков из имеющихся.
Модификаторы:
Добавление звена.
Удаление звена.
Изменение информационного поля звена.
Сортировка в списке.
Селекторы:
Поиск элемента по заданной характеристике.
Предикаты на списках.
Подсчёт в списках.
Деструктор: удаление списка.

23. Пример демонстрации работы с ЛОС в терминах графической нотации

24. Вставка звена в начало списка

list
*
1.
e1
*1
…
en
nil
Пусть дан произвольный n-элементный список с
указателем list.

25. Вставка звена в начало списка

list
*
e1
*1
x
nil
…
en
nil
p
*x
2.
Вставим элемент x, доступный по указателю p, в
начало списка.

26. Вставка звена в начало списка

list
*
e1
*1
x
*
…
p
*x
3.
Сохраним указатель на список.
en
nil

27. Вставка звена в начало списка

list
*x
e1
*1
x
*
…
en
p
*x
4.
Установим указатель на новое первое звено.
nil

28. Вставка звена в начало списка

list
*x
5.
e1
*1
x
*
…
en
Удалим ненужный указатель p. Операция
выполнена.
nil

29. Вариант программной реализации ЛОС

30. Пример программной реализации ЛОС

.MODEL
small
.STACK
100h
nil
list struct
elem
link
list
listsize equ
heapsize equ
heap
equ
0
dw
0
dw
0
ends
type list
<n>
;Определяем константу nil.
;Задаём шаблон структуры звена списка:
; - информационное поле elem;
; - ссылка link (по умолчанию = nil).
segment
hpnt
ls list
heap
;Получаем длину звена.
;n – число доступных звеньев кучи – области
;свободной памяти / heap-области.
;Создаём сегмент для кучи.
dw
2
;Указатель на 1 свободную ячечку (0=nil!).
heapsize dup(<>) ;Собственно список свободной памяти (ССП).
ends
pnt
free
dw
dw
0
<n>
;Укащатель на будущий список.
;Число свободных звеньев ССП (в куче).
main:
mov
mov
mov
mov
ax,
ds,
ax,
es,
@data
ax
heap
ax
;Инициализация сегментов…
.DATA
.CODE

31. Замечания по программной реализации

1.
Удобно сразу (в самом начале программы) задать все
адреса в ССП:
0002 0000_0006 0000_000A
…
0000 0000
Можно (но с осторожностью) не резервировать
сразу целый сегмент в программе, сэкономив место в
памяти:
heap segment
hpnt dw 2
ls
list <>
heap ends
2.

32. Задания

В терминах графической нотации продемонстрируйте
группе одну из операций (выполняется индивидуально):
1.
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
Вставка элемента в конец списка.
Поиск элемента в списке.
Вставка звена после данного элемента.
Вставка звена перед данным элементом.
Приписывание списка к списку.
Удаление первого звена.
Удаление последнего звена.
Удаление всех нулевых элементов из целочисленного списка.
Замена элементов целочисленного списка на противоположные (2
→ -2).
Сортировка элементов целочисленного списка по возрастанию.
Разделение целочисленного списка на 2: из положительных
элементов и из неположительных элементов.
Удаление списка по 1 звену, начиная с последнего.

33. Задания

2.
3.
4.
Напишите программу, позволяющую создать
список, добавлением звеньев в его конец и
выводящую после каждой подобной операции
число звеньев ССП и весь список.
Добавьте в предыдущую программу возможность
удаления звеньев из начала списка. Примечание:
на забывайте добавлять освобождённые звенья к
ССП!
Добавьте в предыдущую программу возможность
поиска элемента. Результат: ответ на вопрос,
найден элемент или нет, и, если найден, то
сколько таких звеньев в списке.