Примеры. Тема 5. Алгоритмы работы со структурированными типами данных

Тема 5. Алгоритмы работы со структурированными типами данных

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

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

· массив;

· запись;

· строка;

· множество.

Алгоритм работы со строками были рассмотрены в предыдущей теме. В данной теме будут рассмотрены алгоритмы работы с массивами и записями.

Лабораторная работа № 12. Стандартные алгоритмы работы с одномерными массивами

Теория

Массив представляет собой совокупность про­нумерованных однотипных значений, имеющих общее имя. Эле­менты массива обозначаются переменными с индексами. Индек­сы записывают в квадратных скобках после имени массива. На­пример:

T[l],T[5],T[i],H[1981,9],H[i,j] и т.п.

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

Массив описывается в разделе описания переменных в следующей форме:

Var ИмяМассива: Array[ ТипИндекса ] Of ТипЭлемента

Чаще всего в качестве типа индекса употребляется интерваль­ный тип. Например:

Var T: Array[1..12] Of Real;

Описание массива определяет, во-первых, размещение масси­ва в памяти, во-вторых, правила его дальнейшего употребления в программе. Последовательные элементы массива располагаются в последовательных ячейках памяти (Т[1], Т[2] и т. д.), причем зна­чения индекса не должны выходить из диапазона 1... 12. В качестве индекса может употребляться любое выражение соответствующе­го типа. Например, T[i+j ], T[m div 2].

Тип индекса может быть любым скалярным порядковым ти­пом, кроме integer.

Часто структурированному типу присваивается имя в разделе типов, которое затем используется в разделе описания перемен­ных.

Type

Masl=Array [1..100] Of Integer;

Mas2=Array [-10..10] Of Char;

Var Num: Masl; Sim: Mas2;

В Turbo Pascal существуют только статические массивы, а это означает, что при описании массива надо точно указать границы его индексов. Изменение размеров массива происходит через изменение в тексте программы и повторную компиляцию. Для упрощения та­ких изменений удобно определять индексные параметры в разде­ле констант:

Const N=10;

Var Mas: Array[1..N] Of Integer;

Теперь для изменения размеров массива Mas и всех операторов программы, связанных с этими размерами, достаточно отредак­тировать только одну строку в программе — раздел констант.

Другой вариант использовать в программе массива с изменяющимся количеством элементов – это зарезервировать место для элементов массива с «запасом». А во время работы программы вводить количество используемых элементов массива.

Действия над массивом как единым целым допу­стимы лишь в двух случаях:

• присваивание значений одного массива другому;

• операции отношения «равно», «не равно».

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

Var A,B: Array[1..10] Of Real;

При выполнении операции присваивания A: =B все элемен­ты массива A станут равны соответствующим элементам масси­ва B.

Массив можно описать как типизированная константа. В этом случае можно задать начальные значения элементов массива непосредственно в программе:

Type mas=array [1..7] of integer;

Const A: mas = (3, 6, -2, 4, 0, 5, -1);

В отличие от обычных констант значение типизированных констант может изменяться во время работы программы. Таким образом описание массива через типизированные константы своеобразная инициализация массива.

Обработка массивов в программах производится покомпонент­но т.е. в цикле. Приведем блок-схему и программу ввода значений в массивы:

program Vvod;

var N,I: integer;

T: array [1..100] of real;

begin

WriteLn(‘Укажите кол-во элементов массива’);

ReadLn(N);

For I:=l To N Do

begin

WriteLn('Введите T[‘,I,’]’);

ReadLn(T[I]);

end;

Здесь каждое следующее значение будет вводиться с новой стро­ки с соответствующими комментариями. Для построчного ввода используется оператор Read.

Для ввода элементов массива можно создать процедуру. Чтобы можно было использовать массив как параметр его надо описать как новый тип.

Пример ввода массива в процедуре:

Type

Msa=Array [1..20] Of Integer;

Var T:Mas,

N: Integer;

Procedure Vvod(Nmas: Integer; Var A: Mas);

Var I: Integer;

begin

For I:=1 To Nmas Do

Read(A[I]);

end;

Следует обратить внимание, что массив определяется как параметр-переменная, т.к.в процедуре изменяется значение элементов массива.

В основной программе ввод будет иметь вид:

begin

WriteLn(‘Укажите кол-во элементов массива’);

ReadLn(N);

WriteLn(‘Введите элементы массива в строчку’);

Vvod(N,T);

Аналогично в цикле по индексной переменной организуется вывод значений массива. Блок-схема этого алгоритма ничем не отличается от блок-схемы ввода.

Пример программы вывода элементов массива.

For I:=l То N Do

WriteLn(‘T[‘,I,’]= ’, T[I]);

Эта программа выводит каждый элемент в отдельной строке.

Процедура вывода элементов массива в строчку будет иметь вид:

Procedure Vivod(Nmas:Integer, A:Mas);

Var I:Integer;

begin

For I:=1 To Nmas Do

Write(A[I]:5);

WriteLn;

end;

Обратите внимание, что при выводе массив описывается как параметр значение, а не как параметр переменная.

В дальнейшем ввод и вывод элементов массива будет выполняться в процедурах.

Примеры

Пример 1.

Вычислить произведение элементов массива.

Исходные данные: N элементов вещественного массива А, N – целый тип.

Результат: Произведение элементов массива P – целый тип.

Тестовый пример: при N=5,

элементы массива A=: 1 3 5 3 4, P=180.

Пример 2.

Найти среднее арифметическое значение элементов массива, не превышающих числа А

Исходные данные: N элементов вещественного массива В. Вещественное число А.

Результат: Среднее арифметическое значение Sr.

Промежуточные значения:

I - Индекс элементов массива

S - Сумма элементов массива, не превышающих число A.

k - Количество элементов массива, не превышающих число A.

Тестовый пример:

при N=7, А=2,

элементы массива В=1 -3 5 4 -4 6 2, Sr=-1

Пример 3.

Определить, сколько элементов целочисленного массива стоит до первого элемента, значение которого меньше своего индекса.

Исходные данные: Целочисленный массив Z из N элементов.

Результат: I-1 - Количество элементов, стоящих до первого элемента, меньшего своего индекса.

Тестовый пример: при N=7, элементы массива Z=1 6 15 4 0 6 -1, I-1=3.

Пример 4.

Найти минимальный элемент и его индекс среди элементов массива с номерами от K до L.

Исходные данные: Целочисленный массив D из N элементов

K – начало поиска.

L – конец поиска.

Результаты: IM - Номер минимального элемента в заданном наборе элементов. Для минимального элемента дополнительная переменная не нужна, потому что значение минимального элемента – это D[IM].

Тестовый пример: при N=7,элементы массива D=1 -3 5 4 -4 6 2,IM=5, D[IM]=-4.

Пример 5.

Определить номер и значение минимального элемента среди положительных элементов массива вещественных чисел

Исходные данные: Вещественный массив A из N элементов.

Результат: IM – Номер минимального элемента.

Промежуточные значения: k – определяет наличие положительного элемента в массиве. k равно нулю пока не встретится положительный элемент.

Тестовый пример: при N=10 и элементах: -3, -5, 7, -2, 5, 2, -7, 5,3, 6

IM=6, A[6]=2

Пример 6.

В целочисленном массиве найти номера двух первых равных элементов.

Исходные данные: Целочисленный массив D из N элементов.

Результат: K L – Номера первых равных элементов.

В данном примере поиск равных элементов лучше вести в процедуре, в этом случае при нахождении равных элементов можно досрочно выйти их процедуры, а значит сразу из двух циклов.

Тестовый пример: при N=7, элементы 4, 6, 3, 6, 3, 7, 1, K=2, L=4.

Пример 7.

Заменить элементы, имеющие четное значение нулем.

Исходные данные: Целочисленный массив A из N элементов.

Результат: Целочисленный массив A из N элементов.

Тестовый пример:при N=7

введенный массив: 4, 6, 7, 9, 3, 2, 1;

преобразованный массив: 0, 0, 7, 9, 3, 0, 1.

Пример 8.

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

Исходные данные: Вещественные массивы C и D из N элементов.

Результат: Вещественные массивы C и D из N элементов.

Тестовый пример: при N=5

введенные массивы:

С: 1, 2, 3, 4, 5

D: -1, -2, -3, -4, -5.

преобразованные массивы:

C: 1, -2, 3, -4, 5

D: -1, 2, -3, 4, -5.

Пример 9.

Удалить элемент с номером K.

Дано: Вещественный массив F из N элементов,

K – номер удаляемого элемента.

Результат: Вещественный массив F из N -1 элементов.

При удалении элементы массива сдвигаются влево.

Тестовый пример: при N=7 и K=4

ввод: 5, 6, 4, 8, 1, 9, 2

вывод: 5, 6, 4, 1, 9, 2; N=6.

Пример 10.

Вставить в массив после заданного элемента нуль.

Дано: Целочисленный массив X из N элементов,

P – номер элемента.

Результат: Целочисленный массив X из N+1 элементов.

При вставке элементы маччива сдвигаются вправо. Чтобы не потерять элементы, сдвиг выполняется с конца

Тестовый пример: N=5, P=3,

ввод: 7, 3, 4, 8, 1; вывод: 7, 3, 4, 0, 8, 1.

Пример 11.

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

1. Ввод массива целых чисел из 20 элементов.

2. Генерация 20.элементов массива от -100 до 100.

3. Замена в массиве отрицательных элементов нулем.

4. Вывод элементов массива.

5. Конец работы.

Исходные данные:

Массив А из 20 целых чисел.

Результат:

Полученный или преобразованный массив А.

В данном примере рассмотрена только основная программа выбора из меню. Блок-схема подпрограмм не приводится. Алгоритм содержит бесконечный цикл, чтобы после выполнения очередного пункта меню, снова происходил возврат в меню. Но в этом случае потребовалось вводить дополнительный пункт меню: Выход из меню, в данном случае из цикла. Бесконечный цикл обеспечивается записью в условии False.

Контрольные вопросы

1. Какой тип данных не допускается для индекса.

2. Могут ли в описании массива в индексах содержаться переменные.

3. Что надо сделать если заранее количество элементов неизвестно.

4. Почему в Примере 6 сравнивать элементы лучше в процедуре.

5. Почему в Примере 10 цикл выполняется от N до 1.

6. Может ли массив являться параметром цикла и что для этого надо сделать.

7. Почему при вводе массива массив описан как параметр-переменная, а при выводе как параметр-значение.