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.

    


 

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

53738. Распознавание частей речи. Местоимение 58.5 KB
  Задачи: закрепление знаний об основных частях речи и развитие умения определять часть речи слов по вопросу; формирование общего понятия о местоимении как части речи; совершенствование навыка разбора предложения по членам; развитие умения правильно употреблять разные части речи в предложении. К какому новому большому разделу вы перешли на прошлом уроке...
53739. Распознавание рода у имен существительных множественного числа 58 KB
  Цель урока: Научить учащихся определять род у имен существительных стоящих во множественном числе. Задачи: совершенствование навыка изменения имен существительных по числам; закрепление знаний о роде имен существительных и развитие умения определять род имени существительного с помощью опорных слов местоимений; формирование и закрепление умения...
53740. Часть речи – прилагательное 34 KB
  Цель: Ознакомить с новой частью речи именем прилагательным его ролью в речи. Ознакомить с существенными признаками имени прилагательного как части речи. Что вы для этого сделали изменили окончания О чем это говорит Это говорит о том что эти слова зависят от имени прилагательного Знаете ли вы к какой части речи относятся слова 2 столбика Значит какую цель мы ставим перед собой на этом уроке узнать о новой части речи.
53741. Правописание гласных против шипящих 41.5 KB
  Что же нам нужно сделать Щука в озере жила Червячка с крючка сняла Наварила щука щей Пригласила всех ершей Говорили всем ерши: Щи у Щуки хороши Давайте запишем наше упражнение в тетрадь. Запись в тетрадь. Нам нужно вставить пропущенные буквы и записать его в тетрадь. Разбор с учителем стихотворения запись его в тетрадь.
53742. Подготовка к сочинению-рассуждению 36 KB
  Цели урока: познакомить с работами писателей посвящённых русскому языку; развивать речевые умения и навыки; прививать любовь к родному краю к малой и большой Родине. В гостях у нас учителя русского языка и литературы. Мы будем говорить о русском языке.
53743. Обобщающий урок по теме “Природа”. Урок - КВН 51 KB
  Природа Да все что нас окружает это природа. Природа прекрасна в любое время года. Весной мы можем наблюдать как вся природа просыпается от зимней спячки.
53744. Роль имени прилагательного в русском языке 88.5 KB
  Цель: Обучающая учить детей правильно использовать имена прилагательные в речи находить прилагательные и по существенным признакам определять предмет; Развивающая развивать критическое мышление умение ставить проблемные вопросы выдвигать гипотезы анализировать и сравнивать обобщать полученные данные и делать выводы; развивать устную и письменную речь учащихся; Воспитывающая создать условия для формирования познавательного интереса к русскому языку воспитания культуры общения в группе со сверстниками; воспитывать...
53745. Столетняя война 72 KB
  Учитель приветствует учеников и организует повторение ими материала прошлого урока. Учитель проводит фронтальный опрос класса по теме прошлого урока. которая подтвердила права и вольности церкви городов рыцарей баронов свободного населения Что такое совет двадцати пяти совет баронов который следил за исполнением Великой хартии вольностей; в случае нарушения условий этой хартии бароны могли начать военные действия против короля всяческими способами добиваться исправления нарушений Затем учитель заслушивает письменные ответы...
53746. Ателье мод 47 KB
  Как вы думаете какие Правильно основной материал для изготовления одежды это ткань. Что такое ткань Ткань изделие изготовленное путём плотного соединения накрест переплетённых нитей расположенных двумя рядами – продольными основа и поперечными уток. Первая ткань которую мы с вами рассмотрим это хлопок. Преимущества хлопковой ткани: Мягкость Хорошая поглощающая способность в тёплое время Лёгкость в окраске Давайте с вами заполним табличку хлопковая ткань она натуральная или синтетическая Пощупайте хлопковую ткань она...