У вас вопросы?
У нас ответы:) SamZan.net

Лекция 2 21 Прямоугольные структуры

Работа добавлена на сайт samzan.net: 2016-06-09

Поможем написать учебную работу

Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.

Предоплата всего

от 25%

Подписываем

договор

Выберите тип работы:

Скидка 25% при заказе до 20.2.2025

Лекция 2

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

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

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

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

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

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

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

Имя операции

Функциональные спецификации

Описание

Создать

B

Создается пустая таблица

Добавить

BKeyInfB

Добавляется запись

Найти

BKeyInf

Ищется запись

Удалить

BKeyB

Удаляется запись

Пусто?

BBoolean

Пуста ли таблица?

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

  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 указатель может сравниваться с другими инициализированными указателями на равенство и неравенство.


2.5 Операции над указателями

Указатель может находиться в одном из трех состояний:

  1.  Указатель не инициализирован. Можно только инициализировать значением  другого  (инициализированного) указателя, процедурой NEW, или константой NIL;
  2.  Указатель инициализирован процедурой NEW. Можно использовать динамическую переменную q^, как переменную типа T, сам указатель сравнивать с другими указателями (только на совпадение или несовпадение), переинициализировать любым способом (см.1.);
  3.  Указатель инициализирован константой NIL. Можно указатель сравнивать с другими указателями (только на совпадение или несовпадение), переинициализировать любым способом (см.1.);

Операция взятия адреса.

program adres;

var x:real;

   p:^real;

begin

  x:=3.1415;

  p:=@x;

  writeln(integer(p),p^)

end.

2.6 Геометрическая интерпретация

Указатель q:^T;

NEW(q);

Куча;

Диспетчер Динамической Памяти;

q^:T;


2.7 Динамическая цепочка

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(‘нет записи’);

Смоделировать динамическую память с помощью массива.


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

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

Задача

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




1. ГРАНД МИР Крым г
2. Иркутский государственный университет ФГБОУ ВПО ИГУ Исторический факультет ИОО
3.  Зарождение концепции хранилища данных 2
4. а Медиа объединение обеспечивает доставку CD и DVD дисков с четырех складов расположенных в разных т
5. По дорогам сказок Что за прелесть эти сказки А
6. ПОСОБИЕ ПО СУБД MICROSOFT CCESS
7. темами архивации данных WinRR и WinZIP
8. на тему- ldquo;Індивідуальні особливості у здібностях людейrdquo; 1
9. To contribute to the beuty of town or city if you wnt to leve memory of yourself in the history of tht town or city come to construction site nd lern the trde of builder
10. тематические вычисления в тысячу раз вернее чем человек