Будь умным!


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

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

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

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

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

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

от 25%

Подписываем

договор

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

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

Лекция 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. ТЭА в особых условиях 114
3. Б Проект- Из
4. тема допускает и даже стимулирует угасания собственного контрольного механизма'конкуренции
5. История создания, развития и общее устройство БТР
6. Где прячется здоровье
7. тема энергосистема состоит из электрических станций электрических сетей и потребителей электроэнергии со.1
8. Тема- Заболевания твёрдых тканей зубов возникающие до прорезывания нарушения развития- крапчатые зубы
9. Пермская государственная фармацевтическая академия Минздравсоцразвития России Кафедра промышленной
10. ГУМАНИТАРНЫЙ КОЛЛЕДЖ Курс лекций по трудовому праву Общая и Особенная части
11. тема в основе которой лежали принципы распределения и солидарности поколений даже модернизированная не мог
12. Основными элементами правоотношения являются- а субъекты объекты содержание б преступление проступо
13. Компютерні мережі
14. Тема- Зайка потерялся
15. Андреевский Собор
16. Реферат- Судопроизводство in jure и in judicio
17. і Педагогічний такт це педагогічно грамотне спілкування в складних педагогічних ситуаціях уміння з
18. тема охлаждения предназначена для поддержания нормального теплового режима двигателя
19. Негосударственные пенсионные фонды в РФ Зарубежный опыт
20. Определения среднеразовых доз и размеров наркотических средств и психотропных веществ