DINAMICO (Методичка С++), страница 2

2013-09-07СтудИзба

Описание файла

Файл "DINAMICO" внутри архива находится в папке "METODY". Документ из архива "Методичка С++", который расположен в категории "". Всё это находится в предмете "информатика" из 2 семестр, которые можно найти в файловом архиве МГТУ им. Н.Э.Баумана. Не смотря на прямую связь этого архива с МГТУ им. Н.Э.Баумана, его также можно найти и в других разделах. Архив можно найти в разделе "книги и методические указания", в предмете "информатика" в общих файлах.

Онлайн просмотр документа "DINAMICO"

Текст 2 страницы из документа "DINAMICO"

Однако, каким бы способом не запрашивалась память, может возникнуть ситуация, когда оставшаяся динамическая память меньше требуемой или исчерпалась и память выделить невозможно. В этом случае система по умолчанию выдает ошибку выполнения и аварийно завершает задачу.

Избежать подобной ситуации можно несколькими способами.

Первый способ заключается в предварительной проверке наличия доступной памяти до выдачи запроса на выделение памяти. Для этой цели используются две функции, которые позволяют определить наличие доступной памяти:

Maxavail: longint; возвращает размер максимального непрерывного участка памяти

Memavail: longint; возвращает размер всей свободной памяти, состоящей из суммы всех свободных фрагментов.

Второй способ заключается в возможности перехватить системную ошибку. Для этого необходимо определить свою подпрограмму обработки ошибки, в которой вместо признака ошибки HeapFunc:=0 (0 означает ошибку использования динамической памяти), необходимо задать Heapfunc:=1. Пример такой подпрограммы приведен ниже:

{$F+}

FUNCTION HeapFunc (size: word) : integer: far;

begin HeapFunc: =1; end;

{$F-}

В программе необходимо определить адрес подпрограммы обработки ошибки, который задается с помощью операции взятия адреса HepError:=@HeapFunc . Использование такой подпрограммы приведет к тому, что процедуры New и GetMem вернут указатель nil и выполнение программы не будет прервано. Управление система передаст в программу в точку возврата из процедуры, в которой возникла ошибка. Именно здесь пользователь имеет возможность сам решить, как поступить при наличии такой ошибки.

Пример 1. Программа подсчитывает сумму элементов массива большой размерности. Для размещения такого массива потребуется n*m*6 байт памяти. Нетрудно подсчитать, что одного сегмента здесь явно не хватит. Использование динамического массива по схеме указатель на элемент требует n*m*4 байта памяти, что превышает, при больших n и m (например при n=200,m=200), 64к. Решение можно найти, если подойти к массиву как к массиву строк, где каждая строка адресуется отдельным указателем, как указано на схеме.

Тогда одного сегмента достаточно для адресации 64000байт/4=16000 строк. Так как указатель может адресовать целый сегмент, то в каждой строке можно разместить 64000байт/6=10677. Однако эти цифры достижимы только при наличии доступной памяти. Поэтому в программе осуществляется проверка наличия доступной памяти путем перехвата ошибки, которую выдает система при отсутствии памяти, с помощью собственной функции обработки ошибок

program ex_large_mas;

const

nn=16000; {в сегменте длиной 64к можно разместить 64к/4 = 16000 указателей длиной 4б}

var

i,j,n,m:word;

ptrstr:array[1..nn] of pointer; {статический массив указателей на строки по m элементов в строке}

s:real;

type

realpoint=^real;

{функция возвращающая указатель на вещественное число по адресу его сегмента и смещения }

function addrR(i,j:word):realpoint;

begin

addrR:=ptr(seg(ptrstr[i]^),ofs(ptrstr[i]^)+(j-1)*sizeof(real))

end;

{ пользовательская функция обработки ошибок}

{$F+}

function heapfunc(size:word):integer;

begin heapfunc:=1; end;

{$F-}

begin randomize;

heaperror:=@heapfunc;{подключение пользовательской функции обработки ошибок}

writeln('Введите n,m');

readln(n,m);

for i:=1 to n do

begin getmem(ptrstr[i],m*sizeof(real));{запрос на память под строку вещественных чисел}

if ptrstr[i]=nil then begin {если памяти не хватает то выйти }

writeln(' Нет места в "куче"');

for j:=1 to i-1 do

freemem(ptrstr[j],m*sizeof(real)); {освободить уже выделенную память}

halt(2); end;

for j:=1 to m do addrR(i,j)^:=random; {если память есть заполнить массив случайными числами}

end;

s:=0;

for i:=1 to n do

for j:=1 to m do

s:=s+addrR(i,j)^;

writeln('Значение суммы =',s:15:10);

writeln('Среднее значение =',s/(n*m):15:10);

for i:=1 to n do

freemem(ptrstr[i],m*sizeof(real)); {освободить использованную память }

end.

  1. Динамические структуры данных.

Наиболее часто переменные ссылочного типа используются при создании динамических структур данных. Самыми распространенными из таких структур в Паскале являются списковые структуры, которые представляют собой совокупность элементов, количество которых заранее не известно. Оно определяется в процессе работы программы или программистом.

Элементом списка называется переменная типа запись, в качестве одного или нескольких полей которой определена переменная ссылочного типа - указатель на запись, в которой он описан. Остальные поля содержат информацию, подлежащую обработке и могут быть описаны как переменные любого допустимого типа, в том числе другого ссылочного.

Например:

TYPE ukzap = ^element; {ссылочный тип - указатель на запись}

element = record {новый тип - элемент, представляет собой запись о студенте}

name: string[16]; {фамилия}

b1,b2,b3: 2..5; {три отметки по экзаменам}

p: ^real; {указатель на вещественное число - размер стипендии}

next: ukzap; {переменная ссылочного типа ukzap - указатель на след. элемент}

end;

В зависимости от количества полей ссылочного типа, указывающих на записи этого же типа и описанных в элементе списочной структуры различают:

  1. Односвязные списки. (Однонаправленные списки) Каждый элемент такого списка содержит только одно поле ссылочного типа Указатель, определенный с помощью этого поля, предназначен для хранения адреса расположения в памяти следующего элемента списка. На приведенной ниже схеме представлена структура однонаправленного списка.

Элемент такого списка можно описать, как в ранее описанном примере:

TYPE ukzap = ^element;

element = record

name: string[16];

telefon:string[7];

next: ukzap;

end;

Однонаправленный список может содержать любое количество элементов, которое регламентируется целями задачи и доступной памятью. Последний элемент такого списка должен содержать признак конца списка. В качестве признака конца служит значение поля указателя последнего элемента равное nil. Адрес первого элемента однонаправленного списка запоминается в переменной ссылочного типа, которая используется для идентификации списка и работы с ним. Иногда можно хранить не только адрес первого но и последнего элемента, что облегчает работу со списком по некоторым алгоритмам.

2.Двусвязные списки. (Двунаправленные списки). Каждый элемент такого списка содержит два поля ссылочного типа Указатели, определенные с помощью этих полей, предназначены для хранения адресов расположения в памяти соответственно предыдущего и последующего элементов списка. На приведенной ниже схеме представлена структура двунаправленного списка.


Элемент такого списка можно описать, используя ранее введенное определение:

TYPE ukzap = ^element;

element = record

name: string[16];

telefon:string[7];

next: ukzap;

pred:ukzap;

end;

В этом описании элемента списка указатель pred (указ.1 на схеме ) содержит адрес предыдущего элемента, указатель next (указ.2 на схеме ) содержит адрес последующего элемента.

Двунаправленный список характеризуется тем, что

а.) у первого элемента списка указатель на предыдущий элемент должен отсутствовать, так как такового у первого элемента нет и поэтому указатель pred устанавливается равным nil.

б ) у последнего элемента списка указатель на последующий элемент должен отсутствовать, так как такового у него нет и поэтому указатель next устанавливается равным nil.

  1. N - связные списки. Каждый элемент такого списка содержит n полей ссылочного типа Указатели, определенные с помощью этих полей, предназначены для хранения адресов расположения в памяти элементов списка. Элемент такого списка можно описать следующим образом:

TYPE ukzap = ^element;

element = record

name: string[16];

telefon:string[7];

uk1: ukzap;

uk2:ukzap;

..................

ukn: ukzap;

end;

Приемы работы со списочными структурами зависят от типа организации списковой структуры, которая определяется тем, как осуществляется добавление нового элемента и удаление очередного. По этим признакам различают дисциплины обслуживания списков. По дисциплинам обслуживания различают: очереди, стеки и деки.

Очередь -динамический список (односвязный или двусвязный), добавление нового элемента в который осуществляется только в конец списка, а удаление - только из начала списка. При этом, поступивший в очередь первым, выбирается первым для обслуживания и удаляется из очереди.

Стек - динамический список (односвязный или двусвязный), и добавление нового элемента в который, и удаление очередного элемента списка осуществляется только с первого элемента списка. При этом первый элемент принято называть вершиной стека. Это позиция, в которой находится последний по времени поступления в стек элемент. Он же является тем элементом, который можно выбрать из стека. Выбранный элемент удаляется из стека, а в его вершине оказывается элемент, который был занесен в стек перед выбранным из него элементом.

Дек - динамический список (односвязный или двусвязный), и добавление нового элемента в который, и удаление очередного элемента списка осуществляется как с первого элемента списка, так и с последнего. При этом оказывается не важным, каким по счету поступил элемент в дек. Выбранным для обслуживания может оказаться как вошедший последним, так и первым.

Кроме выше перечисленных типов списков следует отметить кольцевой список. Такой список получается, если в указатель на последующий элемент последнего элемента однонаправленного списка записать адрес первого элемента. При использовании двунаправленного списка, кроме записи в последний элемент, в указатель на предыдущий элемент первого элемента списка вместо указателя nil необходимо занести адрес последнего элемента списка. При этом, для организации работы с таким списком следует хранить в отдельном указателе адрес начала списка.

Наиболее интересными манипуляциями со списками являются:


style="position: absolute; top: 1.24in; left: 4.4in" 1.Добавление нового элемента в середину списка. Для этой операции необходимо, после определения места вставки., а затем переопределить все необходимые указатели. Пусть необходимо вставить новый элемент после второго элемента списка. После включения список будет выглядеть для односвязного списка, как представлено на схеме слева. Для двузвязного списка подключение элемента выглядит как на схеме справа


style="position: absolute; top: 0.16in; left: 1.28in"


style="position: absolute; top: 1.05in; left: 1.22in"
style="position: absolute; top: 1.02in; left: 4.3in" 2.Удаление элемента из середины списка. Для этой операции необходимо, после определения места, где располагается удаляемый элемент, а затем переопределить все необходимые указатели и удалить элемент. Пусть необходимо удалить второй элемент списка. После удаления список будет выглядеть для односвязного списка, как представлено на схеме слева. Для двузвязного списка схема удаления элемента представлена справа.

Рассмотрим примеры формирования списковых структур и работы с ними на примере стека и очереди и кольцевого списка. В примерах очередь формируется с помощью однонаправленного и двунаправленного списков.

Пример 2.Программа формирует однонаправленный список в виде очереди. При этом добавление нового элемента происходит в конец списка. Программа создает список целых чисел случайным образом, выводит список на печать, а затем вычеркивает из него все числа кратные введенному с клавиатуры числу l.

Свежие статьи
Популярно сейчас
Как Вы думаете, сколько людей до Вас делали точно такое же задание? 99% студентов выполняют точно такие же задания, как и их предшественники год назад. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
5193
Авторов
на СтудИзбе
433
Средний доход
с одного платного файла
Обучение Подробнее