.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
  • predmet.bystrickaya.ru/sabati-tairibi-oip-jrenud-negzg-masattari-sa-sani-merzm-oituda-oldanilatin.html
  • university.bystrickaya.ru/glava-osma-obuchitelni-institucii-uchebnikt-vklyuchva-temi-otnasyashi-se-do-predmeta-metodologiyata-i-sistemata-na-uchebnata.html
  • education.bystrickaya.ru/12-zdravoohranenie-otchet-o-socialno-ekonomicheskom-razvitii-mo-viborgskij-rajon-leningradskoj-oblasti.html
  • tetrad.bystrickaya.ru/vi-semestr-metodika-obucheniya-matematike-v-5-6-klassah-algebre-i-geometrii-v-7-klasse-44.html
  • holiday.bystrickaya.ru/nevrologiya-nejrohirurgiya-psihiatriya-psihoterapiya-bibliograficheskij-ukazatel-novih-postuplenij-v-rnmb-yanvar-fevral-2006-g.html
  • reading.bystrickaya.ru/meri-bezopasnosti-pri-tehnicheskom-obsluzhivanii-i-remonte.html
  • studies.bystrickaya.ru/deyatelnoe-raskayanie-v-sovershennom-prestuplenii.html
  • vospitanie.bystrickaya.ru/zapros-kotirovok-cen-ot-15-marta-2012g-dokumentaciya-o-zaprose-kotirovok-cen.html
  • assessments.bystrickaya.ru/deputat-ot-matrosskoj-tishini-ria-novosti.html
  • spur.bystrickaya.ru/medvedev-poruchil-tshatelno-rassledovat-prichini-krusheniya-teplohoda-na-volge-informacionnoe-agentstvo-regnum-10072011.html
  • exchangerate.bystrickaya.ru/glava-8-shagayu-po-arbatu-na-svidanie-tatyana-nikolaevna-egorova.html
  • essay.bystrickaya.ru/chast-2-yurij-nikitin.html
  • composition.bystrickaya.ru/ohorona-prac-zhnok-nepovnoltnh-nvaldv.html
  • universitet.bystrickaya.ru/svadba-v-slovenii-oficialnie-svadebnie-ceremonii-za-granicej.html
  • literatura.bystrickaya.ru/sleng-kak-yavlenie-v-sovremennoj-lingvistike.html
  • bukva.bystrickaya.ru/mineralnie-vodi-ukraini-ih-lechebnoe-znachenie.html
  • literatura.bystrickaya.ru/spisok-nominantov-na-soiskanie-respublikanskoj-premii-im-m-dzhalilya.html
  • uchebnik.bystrickaya.ru/uchebniki-dlya-vseh-urovnej-obucheniya-instrukcii-po-tehnicheskim-ustrojstvam-opisaniya-yazikov-programmirovaniya-specifikacii-nauchno-populyarnie-knigi-starie-raboti-i-drugie.html
  • education.bystrickaya.ru/13-teoriya-i-ee-struktura-druzhinin-v-n-eksperimentalnaya-psihologiya-uchebnoe-posobie.html
  • doklad.bystrickaya.ru/vladet--navikom-raboti-s-uchashimisya-klassov-korrekcii-obrazovatelnie-tehnologii.html
  • composition.bystrickaya.ru/perfekcionizm-v-strukture-lichnosti.html
  • tests.bystrickaya.ru/kontrolnaya-rabota-po-istorii-gosudarstva-i-prava-rossii-variant-2.html
  • bukva.bystrickaya.ru/razdelitelnij-sillogizm-chast-3.html
  • education.bystrickaya.ru/4-instituti-i-mehanizmi-ekonomicheskoj-diplomatii-i-ekonomicheskaya-diplomatiya-i-ee-sushnost-3.html
  • universitet.bystrickaya.ru/tom-ii-materiali-po-obosnovaniyu-proekta-generalnogo-plana-shuberskogoselskogo-poseleniya-novousmanskogo-municipalnogo-rajona.html
  • literatura.bystrickaya.ru/sotrudniki-mchs-obespechat-bezopasnost-na-izbiratelnih-uchastkah-kamchatki-informacionnoe-agentstvo-regnum-01122011.html
  • ucheba.bystrickaya.ru/programma-informatizacii-shkoli-na-2006-2009-gg-adres-shkoli-stranica-6.html
  • spur.bystrickaya.ru/metodi-opredeleniya-antagonisticheskoj-aktivnosti-molochnokislih-bakterij.html
  • tetrad.bystrickaya.ru/visshij-arbitrazhnij-sud-rossijskoj-federacii-opredelenie-ot-10-dekabrya-2010-g-n-vas-890510-o-peredache-dela-v-prezidium-visshego-arbitrazhnogo-suda-rossijskoj-federacii.html
  • zadachi.bystrickaya.ru/obrasheniya-grazhdan-v-federalnie-organi-ispolnitelnoj-vlasti-chast-6.html
  • thescience.bystrickaya.ru/kaznit-nelzya-pomilovat-ili-staraya-skazka-na-novij-lad.html
  • assessments.bystrickaya.ru/doklad-pasport-subekta-rossijskoj-federacii-kak-instrument-regionalnogo-monitoringa.html
  • assessments.bystrickaya.ru/bilyaletdinov-i-belov-budut-rabotat-v-sbornoj-s-polnoj-otdachej-fhr-rossijskij-sport-v-inostrannih-smi-po-materialam.html
  • literature.bystrickaya.ru/ekonomicheskaya-effektivnost-proizvodstva-moloka.html
  • control.bystrickaya.ru/celevoj-programmi-kultura-rossii-2006-2011-godi-na-2009-god-stranica-6.html
  • © bystrickaya.ru
    Мобильный рефератник - для мобильных людей.