Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Таблица – неограниченный набор однотипных записей, содержащих ключ.
Пусть Key и Inf - известные типы, тогда таблица B есть конечный (но не ограниченный заранее) набор записей B={зап}, где зап = record кл:Key , инф:Inf end.
На данных типа Key, как правило, определен порядок.
Частным случаем таблицы можно считать массив (с определенной натяжкой!), если в качестве Key взять множество индексов.
Таблицы можно характеризовать как неупорядоченные и упорядоченные.
Упорядоченные таблицы могут быть упорядочены по ключу и по частоте обращения. Основные операции над таблицами и их функциональные спецификации приведены в таблице.
|
Имя операции |
Функциональные спецификации |
Описание |
|
Создать |
B |
Создается пустая таблица |
|
Добавить |
BKeyInfB |
Добавляется запись |
|
Найти |
BKeyInf |
Ищется запись |
|
Удалить |
BKeyB |
Удаляется запись |
|
Пусто? |
BBoolean |
Пуста ли таблица? |
Решение этих задач зависит от типа таблицы:
Физическое представление с использованием параллельных массивов (ограничение размера) или с использованием динамической памяти.
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 |
Статической переменной (статически размещенной) называется описанная явным образом в программе переменная, обращение к которой осуществляется по имени. Место в оперативной памяти для размещения статических переменных определяется при компиляции программы и не меняется в процессе выполнения программы. Область размещения статических переменных относится к статической области памяти для данной программы.
В отличие от таких статических переменных в программах, написанных на языке ПАСКАЛЬ, могут быть созданы динамические переменные. Основное свойство динамических переменных заключается в том, что их создание (и распределение памяти под них) осуществляется пользовательской программой на этапе ее выполнения. Размещаются динамические переменные за пределами статической области памяти – в динамической области памяти (в 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 указатель может сравниваться с другими инициализированными указателями на равенство и неравенство.
Указатель может находиться в одном из трех состояний:
Операция взятия адреса.
program adres;
var x:real;
p:^real;
begin
x:=3.1415;
p:=@x;
writeln(integer(p),p^)
end.
Указатель q:^T;
NEW(q);
Куча;
Диспетчер Динамической Памяти;
q^:T;
Pelem=^Elem;
Elem=Record inf:Inform, next:PElem end
Считаем, что Inf=real;
Таблица задается инициализированным указателем p.
Задача: Распечатать третью запись цепочки, если она есть (печать p^.след^.след^.инф)
Задача: Распечатать k-ую запись цепочки.
q:=p;
i:=1;
while (q<>nil) and (i<k) do
begin
i:=i+1;
q:=q^.next;
end;
if q<>nil then writeln(q^.inf) else writeln(‘нет записи’);
Смоделировать динамическую память с помощью массива.
PElem = ^Elem;
Elem=record кл:Key; инф:Inf, след:Pelem end;
|
Заголовок |
Действие |
|
Создать (var p:PElem) |
p:=NIL |
|
Таблица пуста? (p:PElem): Boolean |
Таблица пуста?:= p=NIL |
|
Добавить в начало (var p:PElem,x:Key,i:Inf) (доп. перем p1:PElem) |
NEW(p1); p1^.кл:=x; p1^.инф:=i; p1^.след:=p; p:=p1; |
|
Добавить в конец (var p:PElem,x:Key,i:Inf) (доп. перем p1,p2:PElem) (можно обойтись одной доп. перем.) |
p1:=p; p2:=p; while p1<>NIL do begin p2:=p1; p1:=p1^.след end; NEW(p1); p1^.кл:=x; p1^.инф:=i; p1^.след:=p; p2^.след:=p1; |
|
Найти по ключу(p:PElem,x:Key) : PElem (доп. перем. p1:PElem) |
p1:=p; while (p1<>NIL)and(p1^.кл<>x) do p1:=p1^.след; Найти по ключу:=p1 |
|
Удалить запись таблицы, заданную ключем, если она есть(var p:PElem,x:Key): (доп. перем. p1,p2:PElem) |
p1:=p; p2:=p; while (p1<>NIL)and(p1^.кл<>x) do begin p2:=p1; p1:=p1^.след end; if p1<>NIL then if p1:=p2 then begin p:=p1^.след; DISPOSE(p1) end else begin p2^.след:=p1^.след; DISPOSE(p1) end |
Реализовать операции для упорядоченной по ключу и упорядоченной по частоте обращения таблиц.