Лекция 2

2.1 Прямоугольные структуры. Таблицы

Таблица – неограниченный набор однотипных записей, содержащих ключ.

Пусть Key и Inf - известные типы, тогда таблица B есть конечный (но не ограниченный заранее) набор записей B={зап}, где зап = record кл:Key , инф:Inf end.

На данных типа Key, как правило, определен порядок.

Частным случаем таблицы можно считать массив (с определенной натяжкой!), если в качестве Key взять множество индексов.

Таблицы можно характеризовать как неупорядоченные и упорядоченные.

Упорядоченные таблицы могут быть упорядочены по ключу и по частоте обращения. Основные операции над таблицами и их функциональные спецификации приведены в таблице.

Имя операции	Функциональные спецификации	Описание
Создать	B	Создается пустая таблица
Добавить	BKeyInfB	Добавляется запись
Найти	BKeyInf	Ищется запись
Удалить	BKeyB	Удаляется запись
Пусто?	BBoolean	Пуста ли таблица?

Решение этих задач зависит от типа таблицы:

1. неупорядоченная

2. упорядоченная по ключу

3. упорядоченная по частоте обращения.

Физическое представление с использованием параллельных массивов (ограничение размера) или с использованием динамической памяти.

2.2 Реализация с использованием параллельных массивов (статическое представление таблицы)

type

PElem=1..N;

MInf = array [PElem] of Inf;

MKey = array [PElem] of Key;

var

k:integer - количество записей в таблице.

MI:MInf; MK:MKey;

2.3 Реализация операций для неупорядоченной таблицы с использованием статической памяти

Заголовок	Действие
Создать (var k:integer)	k:=0
Таблица пуста? (k:integer): Boolean	Таблица пуста?:= k=0
Добавить в начало (var k:integer, x:Key,ii:Inf)	if k<N then begin for i:=k downto 1 do begin MI[k+1]:=MI[k]; MK[k+1]:=MK[k] end; k:=k+1; MI[1]:=ii; MK[1]:=x end else печать «оп. выполнить не могу»
Добавить в конец (var k:integer,x:Key,ii:Inf)	if k<N then begin k:=k+1; MI[k]:=ii; MK[k]:=x end else печать «оп. выполнить не могу»
Найти по ключу последовательный поиск(k:integer,x:Key): PElem	k1:=1; while (k1<=k)and(MK[k1]<>x) do k1:=k1+1; Найти по ключу=k1
Найти по ключу бинарный поиск(k:integer,x:Key): PElem	Сами!!!
Удалить запись таблицы, заданную ключем, если она есть (var k:integer,x:Key)	k1:=Найти по ключу(k,x); if k1<=k then begin for i:=k1+1 to k do begin MI[i-1]:=MI[i];MK[i-1]:=MK[i] end; k:=k-1 end

2.4 Динамическая память. Куча

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

В отличие от таких статических переменных в программах, написанных на языке ПАСКАЛЬ, могут быть созданы динамические переменные. Основное свойство динамических переменных заключается в том, что их создание (и распределение памяти под них) осуществляется пользовательской программой на этапе ее выполнения. Размещаются динамические переменные за пределами статической области памяти – в динамической области памяти (в heap-области, в куче).

Пусть Т – некоторый тип данных, t:T, тогда ^T – новый тип данных. Переменная q:^T называется типизированным указателем. Типизированный указатель предназначен для хранения адреса участка динамической памяти, куда может быть записано значение базового типа Т.

Инициализация указателя с помощью процедуры NEW(q). По запросу процедуры NEW диспетчер динамической памяти находит в динамической области памяти (в куче) свободный участок памяти, размером данного типа T, и адрес начала этого участка записывает в q. С этого момента указатель q является инициализированным, а выделенный участок имеет имя q^. Диспетчер динамической памяти считает участок q^ занятым. Для его освобождения можно использовать процедуру DISPOSE(q). Переменная q становится неопределенной (неинициализированной), а конструкция q^ – бессмысленной.

Использование указателя. Если указатель q инициализирован с помощью NEW, то q^ – имя динамической переменной типа Т. Динамическую переменную q^ можно инициализировать значением типа Т, например q^:=t.

"Заземление" – константа NIL, совместимая со всеми указателями (в частности, с типизированными указателями любых базовых типов). Можно q:=NIL, тогда q – определено (инициализировано), однако q^ – бессмысленно. Инициализированный константой NIL указатель может сравниваться с другими инициализированными указателями на равенство и неравенство.