Уровень языка ассемблера Часть X

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

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

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

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

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

Графическое представление объектов данных АТД Информационные поля – для данных Ссылочное / адресное поле Указатель Пустой указатель / пустая ссылка e1e1 …enen * * nil

Графическое представление связей между объектами данных АТД e1e1 *e2e2 *e3e3 nil e4e4 *e5e5 * "Звёздочки" подразумевают адрес начала размещения в памяти следующего объекта данных. Стрелки визуально отображают, на какой именно объект данных имеется ссылка. Пустая ссылка – nil – подразумевает недопустимое значение адреса (ссылку на "особую" ячейку памяти.

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

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

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

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

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

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

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

Графическое представление ЛОС *e1e1 *…enen nil Произвольный n-элементный список с указателем list. nil Указатель на пустой список. list empty

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

Список vs. массив Создадим массив array и заполним его неотрицательными целыми числами размерности byte. array

Список vs. массив Удалим все элементы "2". Вопрос: как показать, что на их месте ничего нет, ведь диапазон 0…255?! array?153?1109

Список vs. массив Как (куда) добавить элементы, если их больше 2?! array

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

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

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

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

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

Вставка звена в начало списка *e1e1 *1*1 …enen nil *x*x x* 3. Сохраним указатель на список. list p

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

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

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

Пример программной реализации ЛОС.MODELsmall.STACK100h nilequ0;Определяем константу nil. liststruct;Задаём шаблон структуры звена списка: elemdw0; - информационное поле elem; linkdw0; - ссылка link (по умолчанию = nil). listends listsizeequtype list;Получаем длину звена. heapsizeequ ;n – число доступных звеньев кучи – области ;свободной памяти / heap-области. heapsegment;Создаём сегмент для кучи. hpntdw2;Указатель на 1 свободную ячечку (0=nil!). lslistheapsize dup();Собственно список свободной памяти (ССП). heapends.DATA pntdw0;Укащатель на будущий список. freedw ;Число свободных звеньев ССП (в куче)..CODE main: сегментов… movds,ax movax,heap moves,ax

Замечания по программной реализации Удобно сразу (в самом начале программы) задать все адреса в ССП: _ _000A… Можно (но с осторожностью) не резервировать сразу целый сегмент в программе, сэкономив место в памяти: heapsegment hpntdw2 lslist heapends

Задания В терминах графической нотации продемонстрируйте группе одну из операций (выполняется индивидуально): Вставка элемента в конец списка Поиск элемента в списке Вставка звена после данного элемента Вставка звена перед данным элементом Приписывание списка к списку Удаление первого звена Удаление последнего звена Удаление всех нулевых элементов из целочисленного списка Замена элементов целочисленного списка на противоположные (2 -2) Сортировка элементов целочисленного списка по возрастанию Разделение целочисленного списка на 2: из положительных элементов и из неположительных элементов Удаление списка по 1 звену, начиная с последнего.

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

Презентация составлена Кибиткиной Э.В. для поддержки курса «Архитектура ВС» для студентов III курса ф-та математикиКибиткиной Э.В. РГПУ им. А.И. Герцена, 2007 г.