Структурированные типы данных. Массивы. Одномерные массивы.

Структурированные типы данных. Массивы. Одномерные массивы.

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

Тип данных определяет:

> во-первых: формат представления данных в памяти компьютера;

> во-вторых: множество допустимых значений, которые может принимать принадлежащая к выбранному типу переменная или константа;

> в-третьих: множество допустимых операций, применимых к этому типу.

Так, например, для хранения переменных типа INTEGER компилятор выделяет два байта в ОЗУ, что обеспечивает размеще­ние в памяти целочисленных значений в диапазоне от — 32768 (=-2*15) до 32767 (=2*15—Выходящие за этот диапазон целые числа, а также вещественные числа храниться в выделенном в данном случае объеме памяти не могут. Благодаря таким ограничениям возможна ситуация переполнения (overflow).

ПАСКАЛЬ язык программирования, характерной особенностью которого является "сильно" разветвленная структура типов. В языке ПАСКАЛЬ все данные, используемые программой, должны принадлежать к какому-либо заранее известному типу данных — стандартному или пользовательскому (тип данных, предопределяемый программистом).

Объявление пользовательских типов данных происходит в разделе описаний, в подразделе нестандартных типов TYPE. Вслед за зарезервированным словом TYPE следуют разделенные знаком равенства имя нового пользовательского типа и конструкция, определяющая этот тип:

TYPE

Day = ('Понедельник','Вторник','Среда');

Month - ('Май','Июнь','Июль', 'Август');

В данном случае пользовательский тип Day определен тремя элементами (слова 'Понедельник', 'Вторник', 'Среда'), относящимися к стандартному типу STRING —строка.

Примечание:

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

Типы данных в языке программирования ПАСКАЛЬ делятся на несколько основных классов:

· • простые типы,

· • структурированные типы,

· ссылочные типы и другие.

К простым типам в языке ПАСКАЛЬ относятся:

· целочисленный типы,

· логический тип,

· символьный тип,

· вещественный типы.

Интервальный тип

При описании переменных в программе, как правило, известно, что они будут использованы для представления подмножества значений некоторого типа. Это подмножество значений в языке программирования ПАСКАЛЬ может быть определено с помощью, так называемого интервального типа данных.

Интервальный тип данных определяется посредством задания подмножества значений одного из ранее определенных (в программе) типов. В языке ПАСКАЛЬ диапазон значений переменной интервального типа задается с помощью любого простого типа данных за исключением вещественного.

При задании диапазона указывается наименьшее и наибольшее значения, которые может принимать переменная соответствующего типа (обе константы должны быть одного типа). Так, с помощью объявления:

God: 1900..2020.

Указывается, что переменная God может принимать целые значения в интервале целых чисел [1900; 2020]. Такая декларация типа указывает компилятору, что для переменной этого типа допустимы в качестве значений только числа из указанного интервала. Тем самым в программе могут быть автоматически организованы проверки корректности операций присвоения для этих переменных. При выполнении программы попытка присвоить такой переменной значение, не входящее в интервал допустимых значений, квалифицируется как ошибка и приводит к прекращению работы программы и выдаче соответствующего сообщения.

Массивы

К структурированным типам данных относятся массивы (ARRAY). Массив объединяет элементы одного типа данных. Более формально массив можно определить как одномерную (последовательную) упорядоченную совокупность элементов некоторого типа, которые адресуются с помощью некоторого индекса. Индексная переменная, служащая для указания отдельного элемента массива, должна быть простого типа (например, типа BYTE или INTEGER).

Наряду с термином "массив", часто можно встретить термины "матрица", "таблица" или "вектор". Суть всех этих терминов одна и та же.

Существует еще одно отличие с точки зрения реализации —элементы массива в памяти хранятся по соседству, в то время как одиночные элементы простого типа не гарантируют такого расположения данных в памяти.

Наряду с одномерными массивами в алгоритмическом языке ПАСКАЛЬ используются также двухмерные массивы данных, в которых координата по горизонтали соответствует номеру строки, а координата по вертикали —номеру столбца на пересечении которых находится элемент.

При этом размер массива в языке ПАСКАЛЬ ограничивается только объемом рабочей памяти компьютера.

Одномерные массивы

В математике и информатике массив называется одномерным, если для получения доступа к его элементам достаточно одной индексной переменной.

В алгоритмическом языке ПАСКАЛЬ Вы можете объявить одномерный массив следующим образом:

VAR Имя_массива: ARRAY [нач_индекс.. кон_ивдекс] OF Тип_данных;

При объявлении массива необходимо определить, каким образом (в каких пределах) производится нумерация элементов, указав начальное и конечное значение [начальный_индекс.. конечный_индекс] для индексной переменной (например 1.. 5 или 2.. 6). Тем самым указывается и число элементов в массиве —его размер. Кроме того, необходимо указать идентификатор (имя) массива и тип данных элементов массива.

В следующих примерах иллюстрируются возможности языка ПАСКАЛЬ по описанию массивов различного типа:

VAR Matrix: ARRAY[1..5] OF REAL;

VAR Index: ARRAY[2..7] OF INTEGER;

VAR Name: ARRAY[1..5] OF STRING[25];

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

В первом примере объявлена переменная-массив Matrix, состоящая изпяти элементов типа REAL, доступ к которым осуществляется помощью индекса, значение которого лежит в интервале от 1 до 5. Элемент массива Index имеет тип INTEGER. Индекс для этого массива может изменяться в интервале от 2 до 7. Массив Name отличается от массива Matrix только тем, что его элементами являются строки, которые могут иметь длину до 25 символов включительно.

Доступ к элементам массива

В отличие от переменных типа STRING, массивы не могут обрабатываться целиком. Но имеется возможность получить доступ к каждому элементу-ячейке массива. Это выполняется, как и в случае строковых переменных, путем указания значения индекса в квадратных скобках. Например с помощью оператора Index[2]:= 34;

элементу массива Index с индексом 2 присваивается значение 34. Наряду с конкретным значением (константой) в качестве индекса может использоваться переменная, например, при поэлементной обработке массива в рамках цикла с параметром FOR.

FOR i:=2 TO 7 DO Index[i]:= 0;

C помощью данного оператора цикла всем элементам массива Index присваивается значение 0.

Ввод элементов массива осуществляется покомпонентно.

FOR i:=1 TO 5 DO

BEGIN

Write('Введите ',I, ‘-е имя:’);

Read (Name[i]);

END;

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

Задачи

Сейчас мы рассмотрим четыре задачи и программы, написанные на алгоритмическом языке ПАСКАЛЬ.

Задача 1. Ввод и вычисление суммы элементов одномерного массива (вектора).

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

Структурная схема задачи 1 имеет вид

Программа задачи:

PROGRAM MATRIXJL;

CONST N = 10;

VAR i, Sum: INTEGER;

Matrix: ARRAY [1.. N] OF INTEGER;

BEGIN

Writeln('ВВЕДИТЕ ЭЛЕМЕНТЫ МАССИВА ');

FOR i:= 1 TO N DO

Read(Matrix[i]);

Writeln('Контрольный вывод элементов массива ');

FOR i:= 1 TO N DO

Write (Matrix[i]:7,');

Writeln;

Sum:= 0;

FOR i:= 1 TO N DO Sum:= Sum + Matrix[i];

Writeln('СУММА 10 ЭЛЕМЕНТОВ МАССИВА MATRIX РАВНА ', Sum);

END.

Результаты выполнения программы:

Контрольный вывод элементов массива

5 7 9 2 45 89 64 -87 45 12

СУММА 10 ЭЛЕМЕНТОВ МАССИВА MATRIX РАВНА 191

Задача 2. Последовательный поиск в массиве

Необходимо разработать программу, которая обеспечит ввод с клавиатуры 25 чисел и сохранит их в некотором одномерном массиве. Затем она должна запросить у пользователя ввод еще одного числа. После ввода данного числа программа осуществит проверку элементов массива на наличие в них числа, равного последнему, введенному нами, и, если такое есть, выдаст соответствующее сообщение на экран. Т.е. пользователь получит информацию о том, содержится ли последнее введенное число в массиве.

Структурная схема задачи 2

Программа задачи2:

PROGRAM MATRIX_2;

CONST N = 25;

VAR i, S, R: INTEGER;

Matrix: ARRAY [1.. N] OF INTEGER;

BEGIN

FOR i:= 1 TO N DO

BEGIN

Write ('ВВЕДИТЕ ',i,'-Й ЭЛЕМЕНТ МАССИВА ');

Read(Matrix[i]);

END;

Writeln('Контрольный вывод элементов МАССИВА ');

FOR i:= 1 TO N DO

Write(Matrix[i],' ');

Writeln;

Write('ВВЕДИТЕ, ПОЖАЛУЙСТА, ЧИСЛО, ПОИСК КОТОРОГО,',' В МАССИВЕ ВЫ ХОТИТЕ ОСУЩЕСТВИТЬ ');

Read(S);

Writeln('Контрольный вывод введенного числа для сравнения ');

Writeln(S);

R:= 0;

FOR i:= 1 TO N DO

BEGIN

IF Matrix[i] = S THEN

BEGIN

R:= R + 1;

WriteLn('ОБНАРУЖЕНО ',R, '-E ВХОЖДЕНИЕ ЧИСЛА', ' ',S,' В МАССИВ MATRIX В ПОЗИЦИИ ', i);

END;

END;

IF R<> 0 THEN WriteLn('ИТОГО ЧИСЛО ',S,' ВСТРЕЧАЕТСЯ В МАССИВЕ', 'MATRIX ',R,' РАЗ')

ELSE WriteLn('ЧИСЛО ',S,' HE ВСТРЕЧАЕТСЯ В МАССИВЕ',

'MATRIX НИ РАЗУ');

END.

 

Пример 3

Необходимо вычислить значение произведения (факториала) натурального ряда целых чисел от 1 до N.

Следовательно, (4) (4)   Схема алгоритма для вычисления факто-риала показана на рис. 8.

Рис.8

Пример 5

 

Дан вектор X = { }, i=1, 2,..., N. Необходимо вычислить значение Р согласно следующему выражению:

P = _k. (6)

Например, если N = 4 тогда

P =

Графическая схема алгоритма данной задачи представлена на рис. 11.

 

 

 

 

 

 

Рис.11

 

 

Первый шаг

Среди N-1 элементов вектора X (за исключением ) произведем поиск минимального элемента вектора и поменяем его местами с первым элементом, если значение < . В результате выполнения первого шага сортировки получим следующий вектор X =(-1, 4, 2, 3, 6, 0).

Второй шаг

Среди N-2 элементов вектора X (за исключением , ) произведем поиск минимального элемента вектора и поменяем его местами со вторым элементом, если значение < . В результате выполнения второго шага сортировки получим вектор X =(-1, 0, 2, 3, 6, 4).

Очевидно, после выполнения N-1 шага (в нашем примере после 5 шагов) получим окончательный упорядоченный вектор X =(-1, 0, 2, 3, 4, 6).

Алгоритм упорядочивания по возрастанию элементов вектора показан на рис. 22. Данный алгоритм пригоден для упорядочивания элементов вектора по убыванию с очевидной заменой знака " > " на знак " < " в блоке проверки условия (рис. 22).

 

 

Рис.22

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

для = P_N ()

 

 

 

Рис.24. Алгоритм вычисления полинома по схеме Горнера.

 

Структурированные типы данных. Массивы. Одномерные массивы.

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

Тип данных определяет:

> во-первых: формат представления данных в памяти компьютера;

> во-вторых: множество допустимых значений, которые может принимать принадлежащая к выбранному типу переменная или константа;

> в-третьих: множество допустимых операций, применимых к этому типу.

Так, например, для хранения переменных типа INTEGER компилятор выделяет два байта в ОЗУ, что обеспечивает размеще­ние в памяти целочисленных значений в диапазоне от — 32768 (=-2*15) до 32767 (=2*15—Выходящие за этот диапазон целые числа, а также вещественные числа храниться в выделенном в данном случае объеме памяти не могут. Благодаря таким ограничениям возможна ситуация переполнения (overflow).

ПАСКАЛЬ язык программирования, характерной особенностью которого является "сильно" разветвленная структура типов. В языке ПАСКАЛЬ все данные, используемые программой, должны принадлежать к какому-либо заранее известному типу данных — стандартному или пользовательскому (тип данных, предопределяемый программистом).

Объявление пользовательских типов данных происходит в разделе описаний, в подразделе нестандартных типов TYPE. Вслед за зарезервированным словом TYPE следуют разделенные знаком равенства имя нового пользовательского типа и конструкция, определяющая этот тип:

TYPE

Day = ('Понедельник','Вторник','Среда');

Month - ('Май','Июнь','Июль', 'Август');

В данном случае пользовательский тип Day определен тремя элементами (слова 'Понедельник', 'Вторник', 'Среда'), относящимися к стандартному типу STRING —строка.

Примечание:

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

Типы данных в языке программирования ПАСКАЛЬ делятся на несколько основных классов:

· • простые типы,

· • структурированные типы,

· ссылочные типы и другие.

К простым типам в языке ПАСКАЛЬ относятся:

· целочисленный типы,

· логический тип,

· символьный тип,

· вещественный типы.

Интервальный тип

При описании переменных в программе, как правило, известно, что они будут использованы для представления подмножества значений некоторого типа. Это подмножество значений в языке программирования ПАСКАЛЬ может быть определено с помощью, так называемого интервального типа данных.

Интервальный тип данных определяется посредством задания подмножества значений одного из ранее определенных (в программе) типов. В языке ПАСКАЛЬ диапазон значений переменной интервального типа задается с помощью любого простого типа данных за исключением вещественного.

При задании диапазона указывается наименьшее и наибольшее значения, которые может принимать переменная соответствующего типа (обе константы должны быть одного типа). Так, с помощью объявления:

God: 1900..2020.

Указывается, что переменная God может принимать целые значения в интервале целых чисел [1900; 2020]. Такая декларация типа указывает компилятору, что для переменной этого типа допустимы в качестве значений только числа из указанного интервала. Тем самым в программе могут быть автоматически организованы проверки корректности операций присвоения для этих переменных. При выполнении программы попытка присвоить такой переменной значение, не входящее в интервал допустимых значений, квалифицируется как ошибка и приводит к прекращению работы программы и выдаче соответствующего сообщения.

Массивы

К структурированным типам данных относятся массивы (ARRAY). Массив объединяет элементы одного типа данных. Более формально массив можно определить как одномерную (последовательную) упорядоченную совокупность элементов некоторого типа, которые адресуются с помощью некоторого индекса. Индексная переменная, служащая для указания отдельного элемента массива, должна быть простого типа (например, типа BYTE или INTEGER).

Наряду с термином "массив", часто можно встретить термины "матрица", "таблица" или "вектор". Суть всех этих терминов одна и та же.

Существует еще одно отличие с точки зрения реализации —элементы массива в памяти хранятся по соседству, в то время как одиночные элементы простого типа не гарантируют такого расположения данных в памяти.

Наряду с одномерными массивами в алгоритмическом языке ПАСКАЛЬ используются также двухмерные массивы данных, в которых координата по горизонтали соответствует номеру строки, а координата по вертикали —номеру столбца на пересечении которых находится элемент.

При этом размер массива в языке ПАСКАЛЬ ограничивается только объемом рабочей памяти компьютера.

Одномерные массивы

В математике и информатике массив называется одномерным, если для получения доступа к его элементам достаточно одной индексной переменной.

В алгоритмическом языке ПАСКАЛЬ Вы можете объявить одномерный массив следующим образом:

VAR Имя_массива: ARRAY [нач_индекс.. кон_ивдекс] OF Тип_данных;

При объявлении массива необходимо определить, каким образом (в каких пределах) производится нумерация элементов, указав начальное и конечное значение [начальный_индекс.. конечный_индекс] для индексной переменной (например 1.. 5 или 2.. 6). Тем самым указывается и число элементов в массиве —его размер. Кроме того, необходимо указать идентификатор (имя) массива и тип данных элементов массива.

В следующих примерах иллюстрируются возможности языка ПАСКАЛЬ по описанию массивов различного типа:

VAR Matrix: ARRAY[1..5] OF REAL;

VAR Index: ARRAY[2..7] OF INTEGER;

VAR Name: ARRAY[1..5] OF STRING[25];

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

В первом примере объявлена переменная-массив Matrix, состоящая изпяти элементов типа REAL, доступ к которым осуществляется помощью индекса, значение которого лежит в интервале от 1 до 5. Элемент массива Index имеет тип INTEGER. Индекс для этого массива может изменяться в интервале от 2 до 7. Массив Name отличается от массива Matrix только тем, что его элементами являются строки, которые могут иметь длину до 25 символов включительно.

Доступ к элементам массива

В отличие от переменных типа STRING, массивы не могут обрабатываться целиком. Но имеется возможность получить доступ к каждому элементу-ячейке массива. Это выполняется, как и в случае строковых переменных, путем указания значения индекса в квадратных скобках. Например с помощью оператора Index[2]:= 34;

элементу массива Index с индексом 2 присваивается значение 34. Наряду с конкретным значением (константой) в качестве индекса может использоваться переменная, например, при поэлементной обработке массива в рамках цикла с параметром FOR.

FOR i:=2 TO 7 DO Index[i]:= 0;

C помощью данного оператора цикла всем элементам массива Index присваивается значение 0.

Ввод элементов массива осуществляется покомпонентно.

FOR i:=1 TO 5 DO

BEGIN

Write('Введите ',I, ‘-е имя:’);

Read (Name[i]);

END;

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

Задачи

Сейчас мы рассмотрим четыре задачи и программы, написанные на алгоритмическом языке ПАСКАЛЬ.

Задача 1. Ввод и вычисление суммы элементов одномерного массива (вектора).

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

Структурная схема задачи 1 имеет вид

Программа задачи:

PROGRAM MATRIXJL;

CONST N = 10;

VAR i, Sum: INTEGER;

Matrix: ARRAY [1.. N] OF INTEGER;

BEGIN

Writeln('ВВЕДИТЕ ЭЛЕМЕНТЫ МАССИВА ');

FOR i:= 1 TO N DO

Read(Matrix[i]);

Writeln('Контрольный вывод элементов массива ');

FOR i:= 1 TO N DO

Write (Matrix[i]:7,');

Writeln;

Sum:= 0;

FOR i:= 1 TO N DO Sum:= Sum + Matrix[i];

Writeln('СУММА 10 ЭЛЕМЕНТОВ МАССИВА MATRIX РАВНА ', Sum);

END.

Результаты выполнения программы:

Контрольный вывод элементов массива

5 7 9 2 45 89 64 -87 45 12

СУММА 10 ЭЛЕМЕНТОВ МАССИВА MATRIX РАВНА 191

Задача 2. Последовательный поиск в массиве

Необходимо разработать программу, которая обеспечит ввод с клавиатуры 25 чисел и сохранит их в некотором одномерном массиве. Затем она должна запросить у пользователя ввод еще одного числа. После ввода данного числа программа осуществит проверку элементов массива на наличие в них числа, равного последнему, введенному нами, и, если такое есть, выдаст соответствующее сообщение на экран. Т.е. пользователь получит информацию о том, содержится ли последнее введенное число в массиве.

Структурная схема задачи 2

Программа задачи2:

PROGRAM MATRIX_2;

CONST N = 25;

VAR i, S, R: INTEGER;

Matrix: ARRAY [1.. N] OF INTEGER;

BEGIN

FOR i:= 1 TO N DO

BEGIN

Write ('ВВЕДИТЕ ',i,'-Й ЭЛЕМЕНТ МАССИВА ');

Read(Matrix[i]);

END;

Writeln('Контрольный вывод элементов МАССИВА ');

FOR i:= 1 TO N DO

Write(Matrix[i],' ');

Writeln;

Write('ВВЕДИТЕ, ПОЖАЛУЙСТА, ЧИСЛО, ПОИСК КОТОРОГО,',' В МАССИВЕ ВЫ ХОТИТЕ ОСУЩЕСТВИТЬ ');

Read(S);

Writeln('Контрольный вывод введенного числа для сравнения ');

Writeln(S);

R:= 0;

FOR i:= 1 TO N DO

BEGIN

IF Matrix[i] = S THEN

BEGIN

R:= R + 1;

WriteLn('ОБНАРУЖЕНО ',R, '-E ВХОЖДЕНИЕ ЧИСЛА', ' ',S,' В МАССИВ MATRIX В ПОЗИЦИИ ', i);

END;

END;

IF R<> 0 THEN WriteLn('ИТОГО ЧИСЛО ',S,' ВСТРЕЧАЕТСЯ В МАССИВЕ', 'MATRIX ',R,' РАЗ')

ELSE WriteLn('ЧИСЛО ',S,' HE ВСТРЕЧАЕТСЯ В МАССИВЕ',

'MATRIX НИ РАЗУ');

END.