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

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

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

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

 

 

 

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

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

 

 

 

 

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

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

Вариант: №2

 

 

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

 

 

 

 

 

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

 

Оглавление

 

 

Введение.

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

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

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

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

 

Типы данных.

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

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

1. Простые.
• Перечисляемый тип. Может хранить только те значения, которые прямо указаны в его описании.
• Числовые. Хранятся числа. Могут применяться обычные арифметические операции.
• Целочисленные: со знаком, то есть могут принимать как положительные, так и отрицательные значения; и без знака, то есть могут принимать только неотрицательные значения.
• Вещественные: с запятой (то есть хранятся знак и цифры целой и дробной частей) и с плавающей запятой (то есть число приводится к виду m*be, где m — мантисса, b — основание показательной функции, e — показатель степени (порядок) (в англоязычной литературе экспонента), причём в нормальной форме 0<=m<b, а в нормализованной форме 1<=m<b, e — целое число и хранятся знак и числа m и e).
• Числа произвольной точности, обращение с которыми происходит посредством длинной арифметики.
• Символьный тип. Хранит один символ. Могут использоваться различные кодировки.
• Логический тип. Имеет два значения: истина и ложь, при троичной логике может иметь и третье значение — «не определено» (или «неизвестно»). Могут применяться логические операции. Используется в операторах ветвления и циклах. В некоторых языках является подтипом числового типа, при этом ложь=0, истина=1.
• Множество. В основном совпадает с обычным математическим понятием множества. Допустимы стандартные операции с множествами и проверка на принадлежность элемента множеству. В некоторых языках рассматривается как составной тип.
2. Составные (сложные).
• Массив. Является индексированным набором элементов одного типа. Наиболее популярны: одномерный массив — вектор (в случае чисел) или строковый тип (в случае символов), двумерный массив — матрица.
• Строковый тип. Хранит строку символов. Аналогом сложения в строковой алгебре является конкатенация (прибавление одной строки в конец другой строки). В языках, близких к бинарному представлению данных, чаще рассматривается как массив символов, в языках более высокой абстракции зачастую выделяется в качестве простого.
• Запись (структура). Набор различных элементов (полей записи), хранимый как единое целое. Возможен доступ к отдельным полям записи. Например, struct в C или record в Pascal.
• Файловый тип. Хранит только однотипные значения, доступ к которым осуществляется только последовательно (файл с произвольным доступом, включённый в некоторые системы программирования, фактически является неявным массивом).
• Класс.
3. Другие типы данных. Если описанные выше типы данных представляли какие-либо объекты реального мира, то рассматриваемые здесь типы данных представляют объекты компьютерного мира, то есть являются исключительно компьютерными терминами.
• Указатель. Хранит адрес в памяти компьютера, указывающий на какую-либо информацию, как правило — указатель на переменную.
• Ссылка.

 

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

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

1. Простые типы:
1. Символьный тип:
1. Char (1 байт)
2. Целые числа:
1. Shortint = -127…127 (1 байт)
2. Integer = -2147483648…2147483647 (4 байта)
3. Longint = -2147483648…2147483647 (4 байта)
4. Smallint = -32768…32767 (2 байта)
5. Int64 = -2⁶³…2⁶³ (8 байтов)
6. Byte = 0…255 (1 байт)
7. Word = 0…65535 (2 байта)
8. LongWord = 0…4294967295 (4 байта)
9. Cardinal = 0 .. 4294967295 (4 байта)
3. Действительные числа:
1. Real = 2.9E-39…1.7e38 (8 байтов)
2. Single = 1.5E-45…3.4E38 (4 байта)
3. Double = 5.0E-324…1.7E308 (8 байтов)
4. Extended = 3.4Е-4932…3.4E+4932 (10 байтов)
5. Comp = -2⁶³…2⁶³ (8 байтов)
6. Currency = -922337203685477.5808…922337203685477.5807 (8 байтов)
4. Логические:
1. Boolean (1 байт)
2. ByteBool (1 байт)
3. WordBool (2 байта)
4. LongBool (4 байта)
5. Перечислимый тип
6. Интервальный тип
2. Составные типы:
1. Массив
2. Строка
3. Запись
4. Множество
5. Файл

Массивы.

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

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

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

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

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

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

{Одномерный  массив целых чисел.  
Нумерация элементов от 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

 

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

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

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

Пример динамического массива  на 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]; 
}

 

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

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

 

Динамический  массив в 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 имеет гибкое средство управления памятью – указатели.