.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
  • lecture.bystrickaya.ru/ad-aleksandrov-al-verner-vi-rizhik-geometriya-10-geometriya-11.html
  • reading.bystrickaya.ru/konkurs-detskogo-tvorchestva-saratovskij-kraj-lyubi-ego-i-vospevaj-provodilsya-po-pyati-nominaciyam-stranica-2.html
  • writing.bystrickaya.ru/dnevnik-k-i-chukovskogo-stranica-5.html
  • uchit.bystrickaya.ru/uchebnaya-programma-disciplini-obrabotka-rechevih-dannih-v-informacionno-telekommunikacionnih-sistemah-specialnost.html
  • report.bystrickaya.ru/kalendarno-tematicheskij-plan-lekcij-dlya-studentov-4-kursa-lechebnogo-fakulteta-na-vesennij-semestr-20102011-uchebnogo-goda.html
  • uchebnik.bystrickaya.ru/vnutrifrakcionnaya-rabota-tv-radio-13-mayak-15-12-2004-novosti-10-00-00-bistrov-ruslan-13.html
  • writing.bystrickaya.ru/bblyagrafchnae-abslugovanne-pa-krayaznastvu.html
  • student.bystrickaya.ru/2008-g-nauchno-prakticheskaya-konferenciya-novgorod-i-novgorodskaya-zemlya-g-novgorod-velikij-titov-sm-doklad-nevskaya-bitva-1240-g-opit-kompleksnoj-rekonstrukcii-22-24-01.html
  • spur.bystrickaya.ru/literaturnij-geroj-mitrofanushka.html
  • uchitel.bystrickaya.ru/razrabotchiki-osnovnaya-obrazovatelnaya-programma-visshego-professionalnogo-obrazovaniya-napravlenie-podgotovki-030100-filosofiya.html
  • kolledzh.bystrickaya.ru/babylon-nis-uchebnik-latinskogo-yazika-lingua-latina-sost-k-a-tananushko-minsk-harvest-2007-448-s.html
  • otsenki.bystrickaya.ru/sostoyanie-zdorovya-shkolnikov-meri-po-ohrane-i-ukrepleniyu-zdorovya-novogorenskaya-sosh.html
  • kolledzh.bystrickaya.ru/568-gijlemhanov-r-00-fn-m-mdniyatne-gomumi-msllre-obshie-voprosi-nauki-i-kulturi.html
  • pisat.bystrickaya.ru/tema-406-zakonomernosti-samoorganizacii-uchebno-metodicheskij-kompleks-po-discipline-koncepcii-sovremennogo-estestvoznaniya.html
  • portfolio.bystrickaya.ru/ou-dstemelk-ral-asen-glzhazira-amanzholizi-astana-2013-zh-ali-sz.html
  • student.bystrickaya.ru/-skoro-poyavitsya-ploshad-65-letiya-pobedi-v-velikoj-otechestvennoj-vojne.html
  • holiday.bystrickaya.ru/nestor-stranica-25.html
  • uchit.bystrickaya.ru/tehnicheskoe-zadanie-razdel-obshie-trebovaniya-predmet-aukciona-nachalnaya-maksimalnaya-cena-kontrakta-stranica-25.html
  • uchitel.bystrickaya.ru/razum-kompyuter-ekzamen-pervoe-nauchnoe-obosnovanie-bessmertiya-dushi-2008-smert-eto-tolko-ekzamen-pervoe-nauchnoe.html
  • institute.bystrickaya.ru/garrat-gibbens-na-stranicah-etogo-sajta-vi-obnaruzhite-mnozhestvo-izvestnejshih-imen-hochu-srazu-predupredit-chto.html
  • essay.bystrickaya.ru/doklad-glavi-administracii-municipalnogo-obrazovaniya-cherdaklinskij-rajon.html
  • universitet.bystrickaya.ru/tematika-kursovih-rabot-dlya-studentov-4-kursa-specialnosti-060700-nacionalnaya-ekonomika-ne.html
  • teacher.bystrickaya.ru/f-engels-dialektika-prirodi-stranica-13.html
  • predmet.bystrickaya.ru/skazal-bog-sotvorim-cheloveka-po-obrazu-nashemu-i-po-podobiyu-nashemu-bernd-fon-vittenburg-shah-planete-zemlya.html
  • holiday.bystrickaya.ru/metodicheskoe-posobie-prednaznacheno-dlya-uchitelej-kotorie-planiruyut-provodit-zanyatiya-po-kursu-osnovi-programmirovaniya-na-prime-re-visual-basic-net-net-chitaetsya-kak-dot-net-stranica-5.html
  • credit.bystrickaya.ru/osobennosti-problemnogo-podhoda-filosofskoe-antikovedenie-i-klassicheskaya-tradiciya-tom-i-vipusk-2.html
  • uchenik.bystrickaya.ru/magisterskaya-programma-profilya-istoricheskoe-obrazovanie-napravleniya-050100-68-pedagogicheskoe-obrazovanie.html
  • crib.bystrickaya.ru/kafedra-iksu-tpu-2010-god-voprosi-po-discipline-tehnologicheskie-processi-i-proizvodstva.html
  • diploma.bystrickaya.ru/zakladka-plodovo-yagodnogo-sada-v-omskom-rajone-na-100-ga-chast-5.html
  • teacher.bystrickaya.ru/glava-15-kombat-i-dityatki-poluraspad-aleksandr-zorich.html
  • books.bystrickaya.ru/diplomirovannogo-specialista-stranica-5.html
  • nauka.bystrickaya.ru/upominaniya-vmutko-22-05-2012-glavnie-novosti-sporta-5.html
  • reading.bystrickaya.ru/melnikova-i-a-byulleten-novih-postuplenij-za-2009-god.html
  • paragraf.bystrickaya.ru/zadachi-i-funkcii-otdela-po-mobilizacionnoj-rabote-go-i-chs-i.html
  • institute.bystrickaya.ru/glava-3-stanovlenie-i-razvitie-politicheskoj-sociologii-v-rossii-v-n-ivanov-zam-direktora-instituta-socialno-politicheskih.html
  • © bystrickaya.ru
    Мобильный рефератник - для мобильных людей.