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

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

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

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

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

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

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

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

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

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

· неупорядоченная

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

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

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

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

type

PElem=1..N;

MInf = array [PElem] of Inf;

MKey = array [PElem] of Key;

var

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

MI:MInf; MK:MKey;

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

Заголовок	Действие
Создать (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