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.

    


 

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

26488. Основные понятия делопроизводства 51 KB
  Организация работы с документами организация документооборота хранения и использования документов в текущей деятельности учреждения предприятия. Службой документационного обеспечения управления ДОУ называется структурное подразделение на которое возложены делопроизводственные операции регистрация контроль исполнения хранение использование документов и т. Структурными подразделениями службы ДОУ в зависимости от уровня организации и объема документов являются: управление делами; управление делопроизводством; канцелярия; отдел ДОУ;...
26489. Бланки документов и их оформление 49 KB
  Бланк стандартный лист бумаги на котором заранее воспроизводится информация об организации авторе от имени которого издается документ. Для организации ее структурного подразделения должностного лица устанавливают следующие виды бланков документов: общий бланк; бланк письма; бланк конкретного вида документа кроме письма. Реквизиты общего бланка документа: герб для организаций имеющих на это право; эмблема организации при наличии герба не проставляется; наименование вышестоящей организации если она имеется; наименование...
26490. ОТВЕТЫ К ПРОМЕЖУТОЧНОЙ АТТЕСТАЦИИ 10 КЛАССА ПРОФИЛЬНОГО КУРСА «ОФИСНЫЕ ТЕХНОЛОГИИ» 34.5 KB
  При адресовании документа должностному лицу инициалы указываются перед фамилией. При адресовании документа физическому лицу указывают фамилию получателя затем почтовый адрес. При подписании документа несколькими должностными лицами их подписи располагают одна под другой в последовательности соответствующей занимаемой должности. При подписании документа несколькими лицами равных должностей их подписи располагают на одном уровне.
26491. Многокритериальные задачи принятия решения 18.13 KB
  Смысл обоих подходов состоит в том что один из критериев оценки альтернатив переводится в ограничение. В ряде случаев можно использовать отношение двух указанных критериев. Третий подход к синтезу критериев стоимости и эффективности приводит к построению паретовского множества. Парето развивая исследования эджварда ввел в экономику понятия оптимальности для случая нескольких критериев.
26492. Принятие решений в задачах с детерминированными целочисленными параметрами 24.47 KB
  Первая категория задачи с неделимостями. Вторая категория комбинаторные задачи. задачи теории расписаний упорядочение планирование согласование. Третья категория задачи сводящиеся к задачам дискретного программирования.
26493. Основные понятия теории расписаний 29.8 KB
  Задачи теории расписаний делятся на детерминированные и стохастические. К детерминированным задачам теории расписаний относятся задачи упорядочения планирования и согласования. В этом случае задачи детерминированного календарного планирования сводятся к задачам упорядочения. В некоторых классификациях к задачам теории расписания могут быть отнесены например задачи распределения в которых множество работ с заданными временными характеристиками необходимо распределить по приборам у которых заранее установлены параметры производительности.
26494. Применение метода динамического программирования в задачах принятия решений 26.55 KB
  Концептуально динамическое программирование применяется для анализа систем которые характеризуются следующими признаками: процесс функционирования системы включает последовательные этапы текущие этапы i конечный этап m. предполагается что для системы выполняется принцип отсутствия последействия. Суть этого принципа заключается в том что состояние Si зависит только от состояния системы на предыдущем этапе то есть на Si1 а так же зависит от управляющего воздействия Ui. И не зависит от предыдущих состояний системы и предыдущих...
26495. Основные типы вероятностных задач и критериев оценки решения 30.14 KB
  Например допустим рассматривается детерминированная система на вход которой через равные промежутки времени Т1 поступают работы.ожидания времени простоя на стоимость 1ой единицы времени их работы зарплата отнесенная к суммарному фонду рабочего времени. 2 Математический аппарат используемый при разработке модели ПР Для конструирования вероятностных моделей ПР примем аппарат случайных процессов: Процесс называется случайным если для каждого момента времени его состояние представляет собой случайную величину. Если переходы между...
26496. Применение теории массового обслуживания в задачах принятия решений 22.61 KB
  Характеристика дисциплин обслуживания заявок. Основные задачи теории массового обслуживания состоят в следующем: вопервых в определении законов распределения количества заявок в очереди на обслуживание вовторых оптимизация пропускной способности обслуживающих приборов втретьих определение рациональных дисциплин выбора заявок из очереди. Таким образом СМО это концептуальная модель основными элементами которой являются источники заявок содержание заявки обслуживающие приборы очередь заявок дисциплина обслуживания заявок.