69123

Масиви в динамічній пам’яті

Лекция

Информатика, кибернетика и программирование

Як уже зазначалось у розділі 10.2, зображення послідовностей однотипних у формі лінійних списків має і переваги, і недоліки. Основним недоліком є значна трудомісткістъ операції доступу до елемента лінійного списку за його номером. Цей недолік непритаманний масивам.

Украинкский

2014-09-30

37.5 KB

0 чел.

Лекція 32. Тема: Масиви в динамічній пам’яті

1. Масиви в динамічній пам’яті

Як уже зазначалось у розділі 10.2, зображення послідовностей однотипних у формі лінійних списків має і переваги, і недоліки. Основним недоліком є значна трудомісткістъ операції доступу до елемента лінійного списку за його номером. Цей недолік непритаманний масивам. Проте масиви, про які йшлося в розділі 7, мали іншу суттеву ваду — вони були статичними, тобто їх розмір визвачався під час розробки програми. У даному розділі розглядаютъся динамічні масиви, розмір яких визначається під час виконання програми і доступ до елементів яких здійснюється так само швидко, як і до елементів статичних масивів.

Динамічний масив ідентифікується покажчиком на його перший елемент. Базовий тип цього покажчика в мові Раsсаl оголошується у доволі спедифічний, порівняно з іншими мовами програмування, спосіб. А саме, він оголошується як тип одноелементного статичного масиву, базовий тип якого збігається із базовим типом динамичного масиву. Наприклад:

type arr=array[0..0] of integer;

var dynarr:^arr;

Тут dynarr - покажчик на динамічний масив даних типу integer, агг — тип того покажчика. Зауважимо, що, хоча згідно з синтаксисом покажчик dynarr посилається на одноелементний масив, процедурою GetMem (.див. розділ 10.1.4) можна виділити для цього покажчика довільний обсяг пам'яті, який не перевищує обсягу одного сегмента, тобто 64 Кбайта, або 65 536 байт. Тому за допомогою покажчика dynar можна посилатися на елементи масиву доволі великого обсягу. Наприклад:

GetMem(dynarr,1000*sizeof(integer));

i:=3;

dynarr^[i]:=1;

У цьому фрагменті коду було виділено пам'ять для динамічного масиву, що містить 1000 елементів типу integer, присвоєно значення 1 йоготретьому елементу. Тип змінної і має збігатися з типом індексів масиву, який було згадано в оголошенні типу агг. Тобто типом змінної і має бути один із цілочислових типів.

А як оперувати масивами, що їх розмір перевищує 64 Кбайт? Для цього можна створити масив покажчиків. Наприклад, масивом, який складається з 100 000 елементів типу integer можна оперувати, виділяючи пам 'ять під 10 000 елементів типу integer для кожного з 10 покажчиків:

type arr=array[0..0] of integer;

var p:array[0..9] of ^arr; i:integer;

for i:=0 to 9 do

   GetMem(p[i],10000*sizeof(integer));

i:=150;

p[2]^[i]:=1;

Вираз р[2]^[i] посилається на елемент 100 000-елементного масиву з індексом 20 150 = 10 000 *2+і. Взагалі, якщо кожна з частин великого масиву містить number елементів, то вираз р[j]^[k] посилається на елемент з індексом j*number+k. 1з цього випливає, що доступ до m-го елемента великого масиву можна здійснити за допомогою виразу р[m div number]^[m mod number].

Наостанок зауважимо: аби за допомогою одного й того самого покажчика можна було посилатися на динамічні масиви різних базових типів, цей покажчик слід оголошувати нетипізованим, а при згадуванні його імені використовувати операцію перетворення типів: <ім'я типу>(<ім'я покажчика>), Така техніка застосовується у прикладі 10.11.

Приклад 10.11

Потрібно отримати масив з 48 000 елементів типу longint. Оскільки зберігання елемента даних типу longint потребує чотирьох байтів пам'яті, зберігання всього масиву вимагатиме 4 * 48 000 = 192 000 байт пам'яті. Оскільки  3 • 65 536 = 196 608, то масив може бути розташований у трьох сегментах пам'яті, тобто складатися із трьох частин, кожна з яких міститьть 16 000 елементів.

У програмі ex10_8 елементам великого масиву присвоюються їх порядкові номери. На екран будуть виведені значення тих елементів, номери якіх кратні 4000. Результати роботи програми ex10_8 наведено на рис. 10.24.

program ex10_8;   {великі масиви в динамічній пам’яті}

const block=3;    {кількість блоків по 16000 елементів}

type arr=array[0..0] of longint;  {тип масиву}

      ptr=^arr;             {тип покажчика на масив}

var p:array[0..block] of pointer;   {масив покажчиків}

     number,     {кількість елементів у блоці}

     total:longint;   {загальна кількість елементів}

     j:longint;   {параметр циклу}

     i:integer    {допоміжна змінна}

begin

    number:=16000;

    total:=number*block;  {total=48000}

    writeln(‘free memory:’,memavail,’;max area:’,maxavail);

    for i:=0 to block-1 do   {виділити динамічну пам’ять}

     getmem(p[i],number*sizeof(longint));

    for j:=0 to total-1 do     {записати у пам’ять значення}

      ptr(p[j div number])^[j mod number]:=j;

    i:=0;   {і – номер стовпчика чисел}

    j:=0;   

    while j<total do    {вивести масив}

    begin

       write (ptr(p[j div number])^[j mod number]:8);

       i:=i+1;

       if i=4 then begin writeln; i:=0 end;

       j:=j+4000;

     end;

     writeln;

     writeln(‘free memory:’,memavail,’; max area’,maxavail);

     readln;

end.

    


 

А также другие работы, которые могут Вас заинтересовать

20635. Эволюционно-синергетическая парадигма. Открытость, нелинейность, диссипативность 64.5 KB
  4 Фазовое пространство и аттракторы системы Контрольные вопросыЛитература 1. В основе синергетики лежит среди прочих важное утверждение о том что материальные системы могут быть закрытыми и закрытыми равновесными и неравновесными устойчивыми и неустойчивыми линейными и нелинейными статическими и динамическими. Принципиальная же возможность процессов самоорганизации обусловлена тем что в целом все живые и неживые природные и общественные системы являются открытыми неравновесными нелинейными.Пригожин разрабатывая современную...
20636. Эволюционно-синергетическая парадигма 102 KB
  внутренняя структура или самоорганизация поддерживается за счет поглощения отрицательной энтропии или негэнтропии из окружающей среды. уводит ее от состояния равновесия максимума энтропии. В неравновесных системах помимо знания балансовых уравнений встает задача формализации и учета отношения порядка и беспорядка соответственно энтропии и негэнтропии. Рынок выступает здесь в качестве индикатора быстро обнаруживая неходовые товары производство которых нерентабельно и ведет к росту энтропии.
20637. Естествознание в мировой культуре 71 KB
  Проблема двух культурНаука и мистицизмВопрос о ценности науки 2. Люди наивные далекие от науки часто полагают что главное в учение Дарвина это происхождение человека от обезьяны. Таким образом вторжение естественной науки биологии в духовную жизнь общества заставило говорить о кризисе науки и ее разрушительном действии на человека. В итоге развитие естествознания привело к кризису науки этическое значение которой ранее усматривали в том что она постигает величественную гармонию Природы образец совершенства как цели человеческого...
20638. Концепции современного естествознания 63.5 KB
  языком науки все о природе стали называться Naturwissenchaft. Эта сеть связывает многочисленные ответвления физических химических и биологических наук включая науки синтетические возникшие на стыке основных направлений биохимия биофизика и др. Но она позволяет пояснить одну из проблем науки проблему редукционизма. Редукционизм в науке это стремление описать более сложные явления языком науки описывающей менее сложные явления или класс явлений например сведение биологии к механике и т.
20639. История развития естествознания 70.5 KB
  В естествознании это объекты или фрагменты материального мира которые человек исследует. определенного видения мира в соответствии с которым осуществляется научная деятельность. Среди естественнонаучных революций можно выделить следующие типы: 1 глобальные охватывающие все естествознание и вызывающие появление не только принципиально новых представлений о мире нового видения мира но и нового логического строя науки нового способа или стиля мышления; 2 локальные в отдельных фундаментальных науках т. Становление новой...
20640. Методология научных исследований 137 KB
  Методы эмпирического и теоретического познания3. Методы научного познания включают так называемые всеобщие методы т. общечеловеческие приемы мышления общенаучные методы и методы конкретных наук. Методы могут быть классифицированы и по соотношению эмпирического знания т.
20641. Механическая картина мира (МКМ) 71 KB
  Механическая картина мира МКМ 1. Понятие научной картины мира2. Понятие научной картины мира Само понятие научная картина мира появилось в естествознании и философии в конце 19 в. Так существуют общенаучные картины мира и картины мира с точки зрения отдельных наук например физическая биологическая или с точки зрения какихлибо господствующих методов стилей мышления вероятностностатистическая эволюционистская системная информационнокибернетическая синергетическая и т.
20642. Термодинамическая картина мира 61.5 KB
  Закон сохранения и превращения энергии в механике3. он начал исследовать принцип эквивалентности теплоты и работы и введя понятие внутренней энергии пришел к пониманию взаимопревращения энергии. До этого в физике существовало понятие механической энергии и представление об ее сохранении и превращении. Закон сохранения и превращения энергии в механике Формирование понятия механической энергии было связано с формированием понятия механической работы А = Fx и энергии как способности совершать работу.
20643. Термодинамическая картина мира (II). Второе начало термодинамики 73 KB
  Теплопроводность приводит к все большему выравниванию температур до тех пор пока распределение температуры во всех точках пространства рассматриваемой изолированной системы не станет одинаковым. Энтропия таким образом характеризует состояние системы. Действительно так же как каждому уровню высоты над поверхностью Земли отвечает своя потенциальная энергия так и каждому состоянию термодинамической системы отвечает своя энтропия. Как работа в поле тяжести потенциальном поле не зависит от вида пути а зависит только от изменения...