Ирина Эланс

Автор который поможет с любыми образовательными и учебными заданиями

Динамические массивы

Федеральное агентство связи

Сибирский Государственный Университет Телекоммуникаций и Информатики

Межрегиональный центр переподготовки специалистов

Курсовая работа

По дисциплине: Информатика и программирование

Выполнил: Снигирёв А.А.

Группа: ББЗ-31

Вариант: №2

Проверил: Бунцев И.А.

Новосибирск, 2013 г

Оглавление

Введение.

Любая программа, написанная на любом языке программирования, работает с данными. Каждый язык программирования имеет свой набор инструментов для их обработки. В исходном виде вся необходимая для работы программы информация представляет собой поток нулей и единиц (биты), сгруппированных в байты, размещаемых в оперативной памяти. Для работы с этими данными язык программирования предоставляет различные типы данных, определяющие множество значений, набор операций, которые можно применять к таким значениям, и, возможно, способ реализации хранения значений и выполнения операций. Любые данные, которыми оперируют программы, относятся к определённым типам.

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

В рамках данной курсовой работы мы в общих чертах рассмотрим существующие типы данных, типы данных, реализованные в языке программирования Free Pascal, и более подробно изучим динамические массивы.

Стоит отметить, что информационные технологии в целом (программирование в частности) динамическая отрасль, поэтому некоторая информация может оказаться уже не актуальной. Каждый день изобретаются новые языки программирования, концепции разработки и архитектурные решения. С другой стороны типизация данных это одно из фундаментальных понятий и не думаю, что в этой области произойдут кардинальные изменения.

Типы данных.

Как правило, типы в языках программирования не всегда строго соответствуют подобным типам в математике. Например, тип «целое число» большинства языков программирования не соответствует принятому в математике типу «целое число», так как в математике указанный тип не имеет ограничений ни сверху, ни снизу, а в языках программирования эти ограничения есть. Как правило, в языках и системах имеется множество целых типов, отличающихся допустимым диапазоном значений (определяемым объёмом занимаемой памяти).

Типы данных бывают следующие:

Простые.

Перечисляемый тип. Может хранить только те значения, которые прямо указаны в его описании.
Числовые. Хранятся числа. Могут применяться обычные арифметические операции.
Целочисленные: со знаком, то есть могут принимать как положительные, так и отрицательные значения; и без знака, то есть могут принимать только неотрицательные значения.
Вещественные: с запятой (то есть хранятся знак и цифры целой и дробной частей) и с плавающей запятой (то есть число приводится к виду m*be, где m — мантисса, b — основание показательной функции, e — показатель степени (порядок) (в англоязычной литературе экспонента), причём в нормальной форме 0<=m<b, а в нормализованной форме 1<=m<b, e — целое число и хранятся знак и числа m и e).
Числа произвольной точности, обращение с которыми происходит посредством длинной арифметики.
Символьный тип. Хранит один символ. Могут использоваться различные кодировки.
Логический тип. Имеет два значения: истина и ложь, при троичной логике может иметь и третье значение — «не определено» (или «неизвестно»). Могут применяться логические операции. Используется в операторах ветвления и циклах. В некоторых языках является подтипом числового типа, при этом ложь=0, истина=1.
Множество. В основном совпадает с обычным математическим понятием множества. Допустимы стандартные операции с множествами и проверка на принадлежность элемента множеству. В некоторых языках рассматривается как составной тип.

Составные (сложные).

Массив. Является индексированным набором элементов одного типа. Наиболее популярны: одномерный массив — вектор (в случае чисел) или строковый тип (в случае символов), двумерный массив — матрица.
Строковый тип. Хранит строку символов. Аналогом сложения в строковой алгебре является конкатенация (прибавление одной строки в конец другой строки). В языках, близких к бинарному представлению данных, чаще рассматривается как массив символов, в языках более высокой абстракции зачастую выделяется в качестве простого.
Запись (структура). Набор различных элементов (полей записи), хранимый как единое целое. Возможен доступ к отдельным полям записи. Например, struct в C или record в Pascal.
Файловый тип. Хранит только однотипные значения, доступ к которым осуществляется только последовательно (файл с произвольным доступом, включённый в некоторые системы программирования, фактически является неявным массивом).
Класс.

Другие типы данных. Если описанные выше типы данных представляли какие-либо объекты реального мира, то рассматриваемые здесь типы данных представляют объекты компьютерного мира, то есть являются исключительно компьютерными терминами.

Указатель. Хранит адрес в памяти компьютера, указывающий на какую-либо информацию, как правило — указатель на переменную.
Ссылка.

Типы данных Free Pascal.

Язык программирования Free Pascal предоставляет нам следующие типы данных:

Простые типы:

Символьный тип:

Char (1 байт)

Целые числа:

Shortint = -127…127 (1 байт)
Integer = -2147483648…2147483647 (4 байта)
Longint = -2147483648…2147483647 (4 байта)
Smallint = -32768…32767 (2 байта)
Int64 = -2⁶³…2⁶³ (8 байтов)
Byte = 0…255 (1 байт)
Word = 0…65535 (2 байта)
LongWord = 0…4294967295 (4 байта)
Cardinal = 0 .. 4294967295 (4 байта)

Действительные числа:

Real = 2.9E-39…1.7e38 (8 байтов)
Single = 1.5E-45…3.4E38 (4 байта)
Double = 5.0E-324…1.7E308 (8 байтов)
Extended = 3.4Е-4932…3.4E+4932 (10 байтов)
Comp = -2⁶³…2⁶³ (8 байтов)
Currency = -922337203685477.5808…922337203685477.5807 (8 байтов)

Логические:

Boolean (1 байт)
ByteBool (1 байт)
WordBool (2 байта)
LongBool (4 байта)

Перечислимый тип
Интервальный тип

Составные типы:

Массив
Строка
Запись
Множество
Файл

Массивы.

Из всего этого многообразия типов нас интересуют на данный момент массивы. Их и рассмотрим в следующем разделе.

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

Количество используемых индексов массива может быть различным. Массивы с одним индексом называют одномерными, с двумя — двумерными и т. д. Одномерный массив нестрого соответствует вектору в математике, двумерный — матрице. Чаще всего применяются массивы с одним или двумя индексами, реже — с тремя, ещё большее количество индексов встречается крайне редко.

Поддержка индексных массивов (свой синтаксис объявления, функции для работы с элементами и т. д.) есть в большинстве высокоуровневых языков программирования. Максимально допустимая размерность массива, типы и диапазоны значений индексов, ограничения на типы элементов определяются языком программирования и/или конкретным транслятором.

В языках программирования, допускающих объявления программистом собственных типов, как правило, существует возможность создания типа «массив». В определении такого типа может указываться размер, тип элемента, диапазон значений и типы индексов. В дальнейшем возможно определение переменных созданного типа. Все такие переменные-массивы имеют одну структуру. Некоторые языки поддерживают для переменных-массивов операции присваивания (когда одной операцией всем элементам массива присваиваются значения соответствующих элементов другого массива).

Пример статического массива на языке Паскаль:

{Одномерный массив целых чисел.
Нумерация элементов от 1 до 15}

a: array [1..15] of Integer;

{Двумерный массив символов. Нумерация по столбцам по типу Byte (от 0 до 255) по строкам от 1 до 5}

multiArray : array [Byte, 1..5] of Char;

{Одномерный массив из строк.
Нумерация по типу word (от 0 до 65536)}

rangeArray : array [Word] of String;

Пример статического массива на С/С++:

int Array[10];

// Одномерный массив целых чисел размера 10
// Нумерация элементов от 0 до 9

double Array[12][15];

// Двумерный массив вещественных
чисел двойной точности
// размера 12 на 15.
// Нумерация по столбцам от 0 до 11,
по строкам от 0 до 14

Существуют специфичные типы массивов:

Динамические массивы

Динамическим называется массив, размер которого может меняться во время исполнения программы. Язык программирования, поддерживающий динамические массивы, должен предоставлять возможность для изменения размера массива. Динамические массивы делают работу с данными более гибкой, так как не требуют предварительного определения хранимых объёмов данных, а позволяют регулировать размер массива в соответствии с реальными потребностями. Обычные (не динамические) массивы называют ещё статическими.

Пример динамического массива на Delphi:

byteArray : Array of Byte;
// Одномерный массив

multiArray : Array of Array of string;
// Многомерный массив

Пример динамического массива на С++:

float *array1;
// Одномерный массив

int **array2;
// Многомерный массив

array1 = new float[10];
// выделение 10 блоков размером типа float

array2 = new int*[16];
// выделение 16 блоков размером
типа указателя на int

for(int i = 0; i < 16; i++)

{
array2[i] = new int[8];
}

Гетерогенные массивы

Гетерогенным называется массив, в разные элементы которого могут быть непосредственно записаны значения, относящиеся к различным типам данных. Массив, хранящий указатели на значения различных типов, не является гетерогенным, так как собственно хранящиеся в массиве данные относятся к единственному типу — типу «указатель». Гетерогенные массивы удобны как универсальная структура для хранения наборов данных произвольных типов. Отсутствие их поддержки в языке программирования приводит к необходимости реализации более сложных схем хранения данных. С другой стороны, реализация гетерогенности требует усложнения механизма поддержки массивов в трансляторе языка.

Динамический массив в Free Pascal.

Одним из вариантов динамического массива в Free Pascal является так называемый открытый массив. Это массив, при описании которого указывается тип составляющих его элементов, но не определяются границы изменения индексов:

имя_открытого_массива: array of array of … тип;

Например:

var
massiv_1: array of real;
massiv_2: array of array of char;
massiv_3: array of array of array of byte;

Распределение памяти и указание границ индексов по каждому измерению открытых массивов осуществляется в ходе выполнения программы с помощью функции SetLength:

SetLength(имя_массива, список_границ_индексов);

Для освобождения выделенной памяти нужно выполнить оператор:

имя_массива:=NIL;

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

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

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

Free Pascal имеет гибкое средство управления памятью – указатели.

Указатель – переменная, которая в качестве своего значения содержит адрес байта памяти. Указатель занимает 4 байта. Как правило, указатель связывается с некоторым типом данных. В таком случае он называется типизированным. Для его объявления используется знак ^, который помещается перед соответствующим типом, например:

type massiv=array [1..2500] of real;

var a:^integer; b,c:^real; d:^massiv;

В языке Free Pascal можно объявлять указатель, не связывая его с конкретным типом данных. Для этого служит стандартный тип pointer, например:

var p,c,h: pointer;

Указатели такого рода будем называть нетипизированными. Поскольку нетипизированные указатели не связаны с конкретным типом, с их помощью удобно динамически размещать данные, структура и тип которых меняются в ходе работы программы.

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

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

Начало кучи хранится в стандартной переменной heaporg, конец – в переменной heapend. Текущая граница незанятой динамической памяти хранится в указателе heapprt.

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

Например:

var
i,j:^integer;
r:^real;
begin
new(i);
new(R);
new(j);

В результате выполнения первого оператора указатель i принимает значение, которое перед этим имел указатель кучи heapprt. Сам heapprt увеличивает свое значение на 4, так как длина внутреннего представления типа integer, связанного с указателем i, составляет 4 байта. Оператор new(r) вызывает еще одно смещение указателя heapprt, но уже на 8 байтов, потому что такова длина внутреннего представления типа real. Аналогичная процедура применяется и для переменной любого другого типа. После того как указатель стал определять конкретный физический байт памяти, по этому адресу можно разместить любое значение соответствующего типа, для чего сразу за указателем без каких-либо пробелов ставится значок ^, например:

i^:=4+3;
j^:=17;
r^:=2 * pi;

Таким образом, значение, на которое указывает указатель, то есть собственно данные, размещенные в куче, обозначаются значком ^. Значок ^ ставится сразу за указателем. Если после указателя значок ^ отсутствует, то имеется в виду адрес, по которому размещаются данные. Динамически размещенные данные (но не их адрес!) можно использовать для констант и переменных соответствующего типа в любом месте, где это допустимо, например:

r^:=sqr(r^)+sin(r^+i^)-2.3

Невозможен оператор

r:=sqr(r^)+i^;

так как указателю r нельзя присвоить значение вещественного типа. Точно так же недопустим оператор

r^:=sqr(r);

поскольку значением указателя r является адрес, и его (в отличие от того значения, которое размещено по данному адресу) нельзя возводить в квадрат. Ошибочным будет и присваивание r^:=i, так как вещественным данным, на которые указывает r^, нельзя давать значение указателя (адрес). Динамическую память можно не только забирать из кучи, но и возвращать обратно. Для этого используется процедура dispose(p), где р – указатель, который не изменяет значение указателя, а лишь возвращает в кучу память, ранее связанную с указателем.

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

Другая возможность состоит в освобождении целого фрагмента кучи. С этой целью перед началом выделения динамической памяти текущее значение указателя heapptr запоминается в переменной указателе с помощью процедуры mark. Теперь можно в любой момент освободить фрагмент кучи, начиная с того адреса, который запомнила процедура mark, и до конца динамической памяти. Для этого используется процедура release. Процедура mark запоминает текущее указание кучи heapptr (обращение mark(ptr), где ptr – указатель любого типа, в котором будет возвращено текущее значение heapptr). Процедура release(ptr), где ptr – указатель любого типа, освобождает участок кучи от адреса, хранящегося в указателе до конца кучи.

Для работы с указателями любого типа используются процедуры getmem, freemem. Процедура getmem(p,size), где р – указатель, size – размер в байтах выделяемого фрагмента динамической памяти (size типа word), резервирует за указателем фрагмент динамической памяти требуемого размера.

Процедура freemem(p,size), где р – указатель, size – размер в байтах освобождаемого фрагмента динамической памяти (size типа word), возвращает в кучу фрагмент динамической памяти, который был зарезервирован за указателем. При применении процедуры к уже освобожденному участку памяти возникает ошибка.

После рассмотрения основных принципов и процедур работы с указателями возникает вопрос: а зачем это нужно? В основном для того, чтобы работать с так называемыми динамическими массивами. Последние представляют собой массивы переменной длины, память под которые может выделяться (и изменяться) в процессе выполнения программы, как при каждом новом запуске программы, так и в разных её частях. Обращение к
i-му элементу динамического массива х имеет вид x^[i].

Рассмотрим процесс функционирования динамических массивов на примере решения следующей задачи: найти максимальный и минимальный элементы массива X(N).

Рассмотрим процесс решения задачи с использованием указателей. Распределение памяти проводим с помощью процедур new–dispose:

program din_mas1;
type massiw= array[1..150]of real;
var
x:^massiw;
i,n:integer;
max,min:real;
begin
{Выделяем память под динамический массив из 150 вещественных чисел.}
new(x);
writeln('Введите размер массива');
readln(n);
for i:=1 to N do
begin
write('x(',i,')=');
readln(x^[i]);
end;
max:=x^[1];min:=x^[1];
for i:=2 to N do
begin
if x^[i] > max then max:=x^[i];
if x^[i] < min then min:=x^[i];
end;
writeln('максимум=',max:1:4, ' минимум=',min:1:4);
{ Освобождаем память. }
dispose(x);
end.

Распределение памяти проводим с помощью процедур getmem–freemem:

program din_mas2;
type
massiw=array[1..150]of real;
var
x:^massiw;
i,n:integer;max,min:real;
begin
writeln(‘Введите размер массива’);
readln(n);
{ Выделяем память под n элементов массива. }
getmem(x,n*sizeof(real));
for i:=1 to N do
begin
write('x(',i,')=');
readln(x^[i]);
end;
max:=x^[1];min:=x^[1];
for i:=2 to N do
begin
if x^[i] > max then max:=x^[i];
if x^[i] < min then min:=x^[i];
end;
writeln(' максимум=',max:1:4,' минимум=',min:1:4);
{ Освобождаем память. }
freemem(x,n*sizeof(real));
end.

При работе с динамическими массивами необходимо соблюдать следующий порядок работы:

Описать указатели.
Выделить память под массив (функции new или getmem).
Обработать динамический массив.
Освободить память (функции dispose или freemem).

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

Заключение

Современное программирование сложно представить без динамических массивов. Они присутствуют практически во всех языках программирования. Использование динамических массивов позволяет с максимальной эффективностью использовать вычислительные мощности компьютеров (или серверов). «На лету» загружать в оперативную память необходимые данные, обрабатывать их и освобождать место под новую порцию.

Free Pascal позволяет работать с оперативной памятью посредством указателей. Используя это, можно динамически размещать данные в ОЗУ. И хотя в данной версии языка программирования нет нативной поддержки динамических массивов мы можем динамически выделять место в памяти под новые данные или очищать от неиспользуемых.

Прямая работа с оперативной памятью добавляет некоторые требования к программисту. Необходимо чётко представлять процессы, происходящие там. Неправильное или невнимательное использование оперативной памяти может привести к различным ошибкам. Например к чрезмерному росту используемого объёма памяти (утечка), если не очищать место от неиспользуемых данных. Другой вариант – возможно искажение данных, если области памяти переменных или массивов пересекутся.

Всё же это не столь большая плата за все преимущества использования динамически размещаемых в памяти данных, массивов в том числе.

Список литературы

Вирт, Никлаус. Алгоритмы и структуры данных. СПб.: Невский диалект. 2001.
Вирт, Никлаус. Паскаль. Руководство для пользователя и описание языка. М.: Финансы и статистика, 1982.
Алексеев Е.Р. Самоучитель по программированию на Free Pascal и Lazarus / Алексеев Е.Р., Чеснокова О.В., Кучер Т.В. Донецк: Унитех, 2009.
Документация Free Pascal: http://www.freepascal.org/docs.var

Динамические массивы 📙 Курсовая → 🆔 72570