Материал: Методические указания к выполнению лабораторной работы «Сложные типы данных» по дисциплине «Программирование». Литвиненко Ю.В

ФГБОУВПО «Воронежский государственный технический университет»

Кафедра систем автоматизированного проектирования и информационных систем

Методические указания

к выполнению лабораторной работы

«Сложные типы данных»

по дисциплине «Программирование»

для студентов по направлению 230400

«Информационные системы и технологии»

(бакалавриат) очной формы обучения

Воронеж 2011

Составитель канд. техн. наук Ю.В.Литвиненко

УДК 681.3

Методические указания к выполнению лабораторной работы «Сложные типы данных» по дисциплине «Программирование» для студентов специальности 230400 «Информационные системы и технологии» очной формы обучения / ФГБОУВПО «Воронежский государственный технический университет»; сост. Ю.В.Литвиненко. Воронеж, 2011. 22 с.

В методических указаниях приведено описание лабораторной работы «Сложные типы данных» по дисциплине «Программирование». Лабораторные работы проводятся на первом курсе. Содержащаяся информация является базовой для изучения основ программирование на языке Pascal.

Методические указания подготовлены в электронном виде в текстовом редакторе MS Word XP и содержатся в файле Программирование№3.doc.

Рис.1. Библиогр.: 4 назв.

Рецензент канд. техн. наук, доц. А.В.Питолин

Ответственный за выпуск зав. кафедрой д-р техн. наук, проф. Я.Е.Львович

Издается по решению редакционно-издательского совета Воронежского государственного технического университета

© ФГБОУВПО «Воронежский государственный технический университет», 2011

Содержание

Введение……………………………………………..…………..2

1. Сложные типы данных (массивы).……………………….....4

1.1. Одномерные массивы……………...……………...........6

1.2. Многомерные массивы. …………………...…………..13

2. Задание на лабораторную работу…………….....................18

3. Контрольные вопросы к лабораторной работе………..….20

Библиографический список………………...…..…………….22

..

ВВЕДЕНИЕ

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

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

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

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

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

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

Тип определяет:

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

-внутреннюю форму представления данных в ЭВМ;

-операции и функции, которые могут выполняться над величинами, принадлежащими к данному типу.

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

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

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

- числовой или арифметический: целые, вещественные (действительные);

- логический (или булевский);

- символьный;

- строковый.

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

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

Каждый тип данных предназначен для определенных целей и имеет свое внутреннее представление (на "атомарном'', битовом уровне каждое данное состоит из комбинации нулей и единиц).

Визуально типы данных в Паскале представлены на рис.1.

Рис.1. Типы данных Паскаля

1. Сложные типы данных (массивы)

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

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

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

Тип элементов массива называется базовым. Используя любой ранее описанный тип, такой, как, например, базовый, можно получить массив мас­сивов, массив записей, массив строк, массив множеств и т. д.

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

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

Компоненты массива называются переменными с индексами. В обычной математической символике записывают: X₁, Х₂, ..., Х_n; или a₁,..., а₅₀ и т. д. Наименьший индекс называется нижней границей, наибольший - верх­ней границей, а число элементов - размером массива. Размер массива фиксируется при описании и в процессе выполнения про­граммы не меняется. Индексы можно вычислять. Наиболее часто в качестве типа индекса используется ограниченный целый тип или перечисляемый тип.

Описание массивов включает в себя следующие указания:

- из переменных какого типа должен состоять массив;

- сколько в нем должно быть элементов;

- какие индексы должны быть использованы для доступа к его элементам.

В общем виде объявление массива выглядит так:

Var <Имя массива> : Array [Нижний индекс .. Верхний индекс] Of <Тип элементов>;

Для имени массива применяются идентификаторы, отвечающие тем же правилам, что и имена переменных и других элементов программы. Параметры массива - нижний и верхний индексы - должны являться константами и определяют пределы изменения индекса и, соответственно, количество элементов, которые содержатся в массиве. Например, если в каче­стве нижнего индекса использовано значение 5, а в качестве верхнего индекса - 7, то массив будет включать в себя три элемента, доступ к которым может быть осуществлен по индексам 5, 6 и 7. Array - слово языка Pascal, показывающее, что объявляемый элемент данных является массивом;

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

Рассмотрим примеры описания массивов с пояснениями:

Program massiv1;

Const

Start =100;

Finish = 105;

Var

S : Integer;

Al: Array [1..10] Of Integer;

{массив десяти переменных типа Integer, для доступа будут использоваться

индексы 1, 2, 3, 4, 5, 6, 7, 8, 9 и 10. Имя мас­сива-А1}

А2: Array [5.. 10] Of Real;

{массив шести переменных типа Real, для доступа будут ис­пользоваться

индексы 5, 6, 7, 8, 9 и 10. Имя массива - А2}

Names: Array [5.. 10] Of String;

{массив шести переменных типа String, для доступа будут ис­пользоваться

индексы 5, 6, 7, 8, 9 и 10. Имя массива – Names}

В: Array [Start..Finish] Of Byte;

{массив шести переменных типа Byte, диапазон индексов за­дается константами

Start и Finish - от 100 до 105. Имя мас­сива – В}

Bl: Array [Start..ll0] Of Byte;

{массив одиннадцати переменных типа Byte, диапазон ин­дексов задается

константами Start и 110 - от 100 до 110. Имя массива - В1}

IC1: Array [Start..90] Of Byte;

{некорректное описание массива: нижний индекс (задан кон­стантой Start = 100)

превышает верхний индекс (задан кон­стантой 90)}

Begin

{Тело программы}

End.

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

< Имя массива >[< Индекс элемента >]

Индекс может быть константой или выражением целого типа, например:

Fam[1]: = 'Иванов';

D: = koef [1] * koef [1] -4 * koef [2] * koef [1];

ReadLn (name[n + 1]);

WriteLn (temper [I]);

Под вводом массива понимают ввод значений элементов массива, а именно:

- как и вывод массива, ввод удобно реализовать при помощи инструк­ции For;

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

- в качестве индексов массивов могут использоваться не только константы, но и переменные, в том и числе и счетчики оператора цикла For;

- в прикладных программах ввод, как правило, осуществляется либо с клавиатуры, либо из файла;

- можно заполнить массив с помощью датчика случайных чисел.

Остановимся подробнее на вводе с клавиатуры элементов массива и n-количества элементов в массиве.

Количество элементов массива, их упорядоченность и тип задают явно до начала выполнения программы. Поэтому если границы массива точно не­известны, то их выбирают «с запасом», так чтобы его размер был не меньше значения n, которое будет введено. Например, после описания

a: Array [1.. 100] of Real;

введенное n должно принадлежать диапазону 1..100, а после описания

а: Array [Byte] of Real;

введенное n должно принадлежать типу Byte.

Рассмотрим пример заполнения элементов массива с помощью операто­ра присваивания и вывод без использования оператора цикла For.

Program massiv2;

Var

A: Array [1..3] Of Integer;

Begin

A[1]: = 8;

A[2]: = 12;

A[3]:=A[1]+A[2];

WriteLn('Первый: ', A[l]);

WriteLn('Второй: ', A[2]);

WriteLn('Третий: ', A[3]);

End.

Массив А содержит 3 элемента типа Integer. Размерность массива задана явно в описании массива. Изменение значений элементов массива происхо­дит с помощью оператора присваивания.

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

Program massiv3;

Const

n = 9;

Var

A : Array [l..n] Of Integer;

i: Integer;

BEGIN

For i: = 1 To n Do

A[i]: = i*i;

WriteLn;

For i: = 1 To n Do

Begin

WriteLn (i, '-й элемент');

WriteLn (A[i]);

end;

End.

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

Имеется большое разнообразие задач на одномерные массивы. Как и все задачи вообще, условно их можно разделить на три вида:

- задачи, решаемые в «одно соображение»;

- стандартные задачи;

- задачи, решения которых требуют знания вспомогательных алгорит­мов, специальных методов и приемов (например, улучшенные методы сортировки массивов, поиск моды и медианы массива; алгоритмы генерирования комби­наторных объектов, алгоритмы на графах и т. д.). Очевидно, что без умения решать задачи первых двух видов невозможно ре­шать нестандартные задачи.

Перечислим стандартные (типовые) задачи на одномерные массивы:

1) нахождение наибольшего (наименьшего) элемента;

2) суммирование элементов (безусловное и условное);

3) подсчет (замена) элементов, удовлетворяющих заданному условию;

4) поиск заданного элемента:

- в неупорядоченном массиве;

- в упорядоченном массиве;

5) определение заданного расположения элементов;

6) удаление элемента, включение элемента в заданную позицию;

7) переразмещение (инвертирование, циклический сдвиг) элементов;

8) случайная выборка элементов (с повторениями и без повторений);

9) слияние двух упорядоченных массивов в упорядоченный массив;

10) сортировка массива (простые методы).

Рассмотрим алгоритм задачи поиска минимального (максимального) элемента в неупорядо­ченном массиве. Делается предположение, что первый элемент массива является мини­мальным (максимальным), затем остальные элементы массива последова­тельно сравниваются с этим элементом. Если во время очередной проверки обнаруживается, что проверяемый элемент меньше (больше) принятого за минимальный (максимальный), то этот элемент принимается за минимальный (максимальный) и продолжается проверка оставшихся элементов. Если в массиве несколько наибольших (наименьших) эле­ментов, то программа находит тот, индекс которого минимальный. Чтобы найти эти величины с максимальным индексом, достаточно добавить знаки равенств в условиях операторов ветвления.

Например, в некоторых видах спортивных состязаний выступление каждого спорт­смена оценивается независимо несколькими судьями. Затем из всей совокуп­ности оценок удаляются наиболее высокая и низкая, а для оставшихся оценок вычисляется среднее арифметическое, которое и идет в зачет спортсмену. Ес­ли наиболее высокую оценку выставило несколько судей, то удаляется только одна такая оценка. Аналогично поступают с наиболее низкими оценками. Дано натуральное число n, положительные действительные числа a₁, ..., a_n (n > 3). Считая, что числа a₁, ..., a_n - это оценки, выставленные судьями од­ному из участников соревнований, определить оценку, которая пойдет в зачет этому спортсмену.