1.1.5 Прямоугольные структуры. Массивы - Лекций 2; Семинаров 0 (2); Лабораторных 2; До 1 апреля 10 баллов на f (кто...
.RU

1.1.5 Прямоугольные структуры. Массивы - Лекций 2; Семинаров 0 (2); Лабораторных 2; До 1 апреля 10 баллов на f (кто...


^ 1.1.5 Прямоугольные структуры. Массивы
Массив - конечное упорядоченное множество элементов (записей) одного типа. Индекс (номер по порядку) указывает относительное положение элемента (отсчет ведется от первого элемента). В языках программирования структура данных "массив" поддерживается транслятором. Пусть Т - базовый тип, т.е. тип элементов, I – индексный тип (множество допустимых индексов). Тогда можно определить новый тип данных М = array[I]of Т.

Над массивом определены следующие операции:

Задача. Записать функциональные спецификации для структуры данных «массив».

Создание массива М,

Инициализация массива МITМ,

Чтение значения элемента массива МIT.

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

3-mediacentr-ruk-rn-rudich-om-shajdulina-reshenie-3-upravlyayushego-soveta-gimnazii-univers.html
3-mehanizmi-nejtralizacii-finansovih-riskov-i-ih-effektivnost-uchebnoe-posobie-2007-orenburg-soderzhanie-tema.html
3-meri-elektrobezopasnosti-pri-proizvodstve-putevih-rabot-pravila-elektrobezopasnosti-dlya-rabotnikov-oao-rzhd.html
3-meri-pozharnoj-bezopasnosti-pri-proizvodstve-stroitelno-montazhnih-rabot.html
3-mestnie-nalogi-metodicheskoe-posobie-cheboksari-2007-pod-obshej-redakciej-ermoshkina-v-p-metodicheskoe-posobie.html
3-mesto-i-sroki-provedeniya-sorevnovaniya-polozhenie-ob-okruzhnih-sorevnovaniyah-po-pauerliftingu-na-2012-god-yavlyaetsya.html
  • ucheba.bystrickaya.ru/predislovie-k-pervomu-izdaniyu-17-stranica-5.html
  • university.bystrickaya.ru/federalnij-perechen-uchebnikov-stranica-3.html
  • uchit.bystrickaya.ru/temi-kursovih-rabot-dlya-studentov-1-kursa-gruppa-161-2005-2006-uchebnij-god-5-tem-po-mehanizmam-funkcionirovaniya.html
  • grade.bystrickaya.ru/monografiya-m-izdatelstvo-rossijskogo-universiteta-druzhbi-narodov-poligraf-servis-2002-232-s-il-stranica-13.html
  • otsenki.bystrickaya.ru/sovremennie-lampi-begushej-volni-ih-konstrukcii-fizicheskie-principi-raboti-i-parametri.html
  • institute.bystrickaya.ru/gennadij-koldasov-chlen-bogoslovskogo-otdeleniya-petrovskoj-akademii-nauk-i-iskusstv-stranica-5.html
  • letter.bystrickaya.ru/novosibirsk-2006-metodicheskie-ukazaniya-po-vipolneniyu-diplomnih-rabot-dlya-studentov-specialnosti-060400-finansi-i-kredit.html
  • student.bystrickaya.ru/-v-administracii-prodolzhaet-rabotu-elektronnij-informacionnij-kiosk-informacionnij-byulleten-mestnogo-samoupravleniya.html
  • learn.bystrickaya.ru/glava-15-filosofiya-cennostej-aksiologiya-161-gosudarstvennij-ekonomicheskij-universitet-filosofiya-kurs-lekcij-tashkent-2001.html
  • crib.bystrickaya.ru/i-o-ponomareva-metodicheskij-material-podgotovlen.html
  • school.bystrickaya.ru/komponenti-stancii-upravleniya-kfcs-montiruyutsya-v-specialnom-shkafu-ili-v-stojkah-stanciya-upravleniya-podderzhivaet-do-10-blokov-vvodavivoda-do-8-modulej-vvodavivoda-v-kazhdom-bloke.html
  • control.bystrickaya.ru/ekzamenacionnaya-komissiya-po-priemu-gosudarstvennogo-ekzamena-i-po-napravleniyam-podgotovki-magistrov.html
  • prepodavatel.bystrickaya.ru/testi-dlya-podgotovki-k-sdache-kvalifikacionnogo-ekzamena-po-specialnosti-obshaya-vrachebnaya-praktika-stranica-8.html
  • ucheba.bystrickaya.ru/programma-foruma-interra-2010-stranica-22.html
  • paragraph.bystrickaya.ru/malenkaya-zhenskaya-mest-sopernice-test-revnivi-li-vi-gramotnaya-mest-kak-vernut-lyubimogo-bojsya-mesti-moej.html
  • literature.bystrickaya.ru/chast-vtoraya-ajra-levin-chislo-zverya.html
  • ucheba.bystrickaya.ru/programma-elektivnogo-kursa-po-russkoj-literature-9-klasse.html
  • write.bystrickaya.ru/glava-v-kniga-pervaya-.html
  • gramota.bystrickaya.ru/zakon-o-lgotnih-viplatah-nuzhdaetsya-v-korrektirovke-schitaet-glava-komiteta-gosdumi-po-trudu-i-socpolitike.html
  • zadachi.bystrickaya.ru/stavropol-2011-g-programma-disciplini-praktikum-po-metodike-prepodavaniya-russkogo-yazika-i-literaturi-fakultativ.html
  • prepodavatel.bystrickaya.ru/srok-sluzhbi-sokratyat-do-odnogo-goda-ria-novosti.html
  • obrazovanie.bystrickaya.ru/prilozhenie-4-instrukciya-po-kontrolyu-za-perevalkoj-opasnih-gruzov-v-morskom-portu-vostochnij-vvedena-v-dejstvie-rasporyazheniem.html
  • gramota.bystrickaya.ru/xx-vek-kak-vremya-vozniknoveniya-totalitarnih-sektnesostoyatelnost-etogo-mneniya.html
  • exchangerate.bystrickaya.ru/arhitektura-i-gradostroitelstvo-kirgizstana-chast-3.html
  • znanie.bystrickaya.ru/annotirovannaya-programma-nazvanie-disciplini-matematicheskoe-modelirovanie-soderzhanie-disciplini.html
  • ucheba.bystrickaya.ru/proektnaya-deklaraciya-ooo-moj-dom-development.html
  • tetrad.bystrickaya.ru/upravlenie-gosudarstvennoj-sobstvennostyu-itogi-socialno-ekonomicheskogo-razvitiya-respubliki-tatarstan-osnovnie.html
  • textbook.bystrickaya.ru/harakteristika-guminovih-kislot-torfov-srednego-priobya-stranica-3.html
  • learn.bystrickaya.ru/glava-4obshie-svedeniya-metodicheskie-rekomendacii-po-opredeleniyu-sostava-rabot-primenyaemih-priborov-i-oborudovaniya.html
  • spur.bystrickaya.ru/krishenko-pesa-zoopark.html
  • lecture.bystrickaya.ru/80ottepel-shpargalka-po-otechestvennoj-istorii-predmet-i-metod-istoricheskogo-issledovaniya-otechestvennaya-istoriya.html
  • notebook.bystrickaya.ru/gosudarstvennaya-programma-razvitiya-obrazovaniya-v-respublike-kazahstan-na-2005-2010-godi.html
  • znanie.bystrickaya.ru/a-a-akaev-glavnij-nauchnij-sotrudnik.html
  • grade.bystrickaya.ru/obrazovatelnaya-programma-municipalnogo-byudzhetnogo-obsheobrazovatelnogo-uchrezhdeniya-suntarskaya-nachalnaya-obsheobrazovatelnaya-shkola-im-v-g-pavlova.html
  • books.bystrickaya.ru/biznes-plan-po-organizacii-upravlyayushej-kompanii-zakon-klarka-o-radikalnih-ideyah.html
  • © bystrickaya.ru
    Мобильный рефератник - для мобильных людей.