Изменение реакции на ошибку

Коломенский институт (филиал)

федерального государственного бюджетного образовательного учреждения высшего образования

«Московский политехнический университет»

Лабораторный практикум по дисциплине

«Структуры данных и алгоритмы их обработки»

Основная образовательная программа высшего образования

27.03.04 «Управление в технических системах»

Академический  бакалавриат

Направление подготовки:

 «Управление в технических системах»

Нормативный срок освоения программы - 4 года

Ежегодно актуализируется и утверждается в составе ООП

на заседании Ученого совета института

Коломна

Содержание

Введение ....................................................................................................................... 5

Лабораторная работа №1

Фундаментальные структуры данных ...................................................................... 6

Лабораторная работа №2

Алгоритмы поиска в фиксированной группе данных ........................................... 10

Лабораторная работа №3

Алгоритмы базовых и улучшенных сортировок.

Порядковые статистики ............................................................................................ 13

Лабораторная работа №4

Полустатические структуры данных  ..................................................................... 18

Лабораторная работа №5

Динамические структуры данных - односвязные и двусвязные списковые структуры.................................................................................................................... 22

Лабораторная работа №6

Деревья, как динамические структуры данных ..................................................... 26

Лабораторная работа №7

Алгоритмы метода перебора с возвратами - (МПВ), "жадные" алгоритмы................................................................................................................... 29

Лабораторная работа №8

Хеширование. Алгоритмы организации и обработки хеш-таблиц ...................... 32

Лабораторная работа №9

Сетевые модели. Алгоритмы на графах .................................................................. 35

Введение

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

«Алгоритмы + структуры данных = программы» (Н.Вирт) - тезис, на котором базируется искусство программирования.

В процессе выполнения лабораторных работ студенты осваивают и анализируют основные алгоритмы обработки различных структур данных. Освоение достигается путем программирования учебных задач на языке Object Pascal в визуальной среде программирования Delphi.

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

Вторая задача: (4 часа) – посвящена алгоритмам поиска в массивах, а также в строках различной организации.

В третьей работе: (8 часов) – студентам предлагается освоение на практике: 1) базовых алгоритмов сортировки массива;

2) улучшенных методов сортировки, построенных на основе простейших, реализованных студентом при выполнении п.1).

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

Шестая работа: (8 часов) – направлена на освоение алгоритмов построения, обработки и вывода (печати) деревьев различной структуры: бинарные, сбалансированные АВЛ-деревья, сильноветвящиеся Б-деревья.

Седьмая работа: (4 часа) – предназначена для изучения и реализации общих методов обработки данных: алгоритмы перебора с возвратом, динамического программирования и, так называемые, «жадные» алгоритмы для различных задач.

В восьмой работе: (4 часа) – студенты должны написать и отладить программу для быстрого поиска с помощью организации и использования
хеш-таблиц.

В девятой работе: (4 часа) – студентами осваиваются, реализуются и анализируются различные алгоритмы на графах.

Предлагаемые варианты задач для реализации достаточно небольшие, чтобы их можно было реализовать полностью в процессе выполнения лабораторных работ.

Лабораторная работа № 1

(8 часов)

Фундаментальные структуры данных

Цель работы: изучение вопросов представления базовых структур (массивов, записей, множеств) в ЭВМ; освоение средств языка Object Pascal (в интегрированной среде Delphi) для реализации алгоритмов обработки фундаментальных структур; так же изучение вопросов организации файлов в ЦВМ, применение средств Object Pascal для обработки файлов.

Домашнее задание:

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

2. Изучить отображение фундаментальных структур на ОП ЦВМ и средства Delphi, позволяющие программно организовать и применять в приложениях такие структуры.

3. Освоить принципы организации файловой системы в Delphi и средства Object Pascal для работы с файлами разных типов.

Теоретические сведения:

Объявление массива

Массив, как и любая переменная программы, перед использованием должен быть объявлен в разделе объявления переменных.

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

Имя: array [нижний_индекс. .верхний_индекс] of тип элемента;

имя – имя массива;

array – зарезервированное слово языка Delphi, обозначающее, что объявляемое имя является именем массива;

нижний_индекс и верхний_индекс – целые константы, определяющие диапазон изменения индекса элементов массива и, неявно, количество элементов (размер) массива;

тип – тип элементов массива.

Пример:

temper:array[1..31] of real;

коef:array[0. .2] of integer;

name:array[1..30] of string[25];

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

Имя: array[НижняяГраница1..ВерхняяГраница1, НижняяГраница2..ВерхняяГраница2] of Тип

Имя – имя массива;

array – слово языка Delphi, указывающее, что объявляемый элемент данных является массивом;

НижняяГраница1, ВерхняяГраница1, НижпяяГраница2, ВерхняяГраница2 – целые константы, определяющие диапазон изменения индексов и, следовательно, число элементов массива;

Тип – тип элементов массива.

Пример:

itog: array [1..12, 1..6] of integer

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

Пример:

const

NT = 18;

team: array[1..NT] of string[SN];

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

team [ 1] := 'Зенит';

d := koef[l]*koef[l]-4*koef[2]*koef[1];

ShowMessage(name[n+1]);

temper[i] := StrToFloat(Edit1.text);

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

Имя:array [нижний_индекс..верхний_индекс] of тип = (список);

список – разделенные запятыми значения элементов массива.

Пример:

a: array[10] of integer = (0,0,0,0,0,0,0,0,0,0);

Team: array[1..5] of String[10]=('Зенит','Динамо','Спартак','Ротор','СКА');

Операции с массивами

Ввод (вывод) массива

Под выводом массива понимается вывод на экран монитора (в диалоговое окно) значений элементов массива.

Если в программе необходимо вывести значения всех элементов массива, то для этого удобно использовать инструкцию for.

Пример:

const

NT = 5;

var

team: array[1..NT] of string[10] =('Зенит','Динамо','Ротор','Спартак','СКА'

procedure TForml.ButtonlClick(Sender: TObject);

var

st:string;

i:integer;

begin

for i:=l to NT do

st := st + IntToStr(i)+ ' '+ team[i] + #13;

end;

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

Любая обработка элементов массива также - в цикле, поэлементно!

Работа с файлами.

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

Типы файлов.В языке Pascal имеется возможность работы с тремя типами файлов: текстовыми; типизированными; бестиповые.

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

Описание файлов

В разделе var переменные, используемые для работы с файлами (файловые переменные), описываются следующим образом:

var  f1,f2: text;        {текстовые файлы}

g: file of <тип_элементов_файла>; {типизированные файлы}

t: file ; {бестиповые файлы}

Файловая переменная не может быть задана константой.

Текстовые файлы.

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

Назначение файла

Процедура assign(f,'<имя_файла>'); служит для установления связи между файловой переменной fи именем того файла, за действия с которым эта переменная будет отвечать. На разных этапах работы программы одной и той же файловой переменной можно присваивать разные значения. Например, если в начале программы мы напишем

assign(f,'input.txt');

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

assign(f,'output.txt');

после которой переменной f будет уже соответствовать другой файл.

Строка '<имя_файла>' может содержать полный путь к файлу. Если путь не указан, файл считается расположенным в той же директории, что и исполняемый модуль программы. Именно этот вариант обычно считается наиболее удобным.

Открытие файла

В зависимости от того, какие действия ваша программа собирается производить с открываемым файлом, возможно троякое его открытие:

Закрытие файла

После того, как ваша программа закончит работу с файлом, очень желательно закрыть его:close(f);В противном случае информация, содержащаяся в этом файле, может быть потеряна.

Считывание файла

Чтение данных из файла, открытого для считывания, производится с помощью команд read() и readln(). В скобках сначала указывается имя файловой переменной, а затем - список ввода. Например:

Если вспомнить, что в памяти компьютера любой файл записывается линейной последовательностью символов и никакой разбивки на строки там реально нет, то действия процедуры readln() можно пояснить так: читать все указанные переменные, а затем игнорировать все символы вплоть до ближайшего символа "конец строки" или "конец файла". Указатель при этом перемещается на позицию непосредственно за первым найденным символом "конец строки". Если же символ конца строки встретится где-нибудь между переменными, указанными в списке ввода, то обе процедуры его просто проигнорируют. Считывать из текстового файла можно только переменные простых типов: целых, вещественных, символьных, а также строковых. Численные переменные, считываемые из файла, должны разделяться хотя бы одним пробельным символом. Типы вводимых данных и типы тех переменных, куда эти данные считываются, обязаны быть совместимыми. Здесь действуют все те же правила, что и при считывании с клавиатуры.

Считываемые переменные могут иметь различные типы. Например, если в файле fзаписана строка

1 2.5 с

то командойread(f,a,b,c,c); можно прочитать одновременно значения для трех переменных, причем все разных типов: a: byte;b: real;c: char;

Замечание: Обратите внимание, что символьную переменную c пришлось считывать дважды, так как после числа "2.5" сначала идет символ пробела и только затем буква "c".

Из файла невозможно считать переменную составного типа (например, если а - массив, то нельзя написать read(f,a), можно ввести его только поэлементно, в цикле. Но, для типизированного файла цикл не требуется, если компонента объявлена таким же типом , что и вводимый массив.Особенно внимательно нужно считывать строки (string[length]и string): эти переменные "забирают" из файла столько символов, сколько позволяет им длина (либо вплоть до ближайшего конца строки). Если строковая переменная неопределенной длины (тип данных string) является последней в текущей строке файла, то никаких проблем с ее считыванием не возникнет. Но в случае, когда необходимо считывать переменную типа string из начала или из середины строки файла, это придется делать с помощью цикла - посимвольно. Аналогичным образом - посимвольно, от пробела до пробела - считываются из текстового файла слова.

Запись в файл

Сохранять переменные в файл, открытый для записи командами rewrite(f) или append(f), можно при помощи команд write() и writeln(). Так же, как в случае считывания, первой указывается файловая переменная, а за ней - список вывода:

Выводить в текстовый файл можно переменные любых базовых типов (вместо значений логического типа выведется их строковый аналог TRUE или FALSE) или строки.

Структурированные типы данных можно записывать только поэлементно.

Пробельные символы

К пробельным символам (присутствующим в файле, но невидимым на экране) относятся:

· символ горизонтальной табуляции (#9);

· символ перевода строки (#10) (смещение курсора на следующую строку, в той же позиции);

· символ вертикальной табуляции (#11);

· символ возврата каретки (#13) (смещение курсора на начальную позицию текущей строки; в кодировке UNIX один этот символ служит признаком конца строки);

· символ конца файла (#26);

· символ пробела (#32).

Замечание: Пара символов #13 и #10 является признаком конца строки текстового файла (в кодировках DOS и Windows).

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

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

Поиск специальных пробельных символов (нас интересуют в основном #10, #13 и #26) можно осуществлять при помощи стандартных функций:

eof(f) – возвращает значение TRUE, если уже достигнут конец файла f (указатель находится сразу за последним элементом файла), и FALSE в противном случае;

seekeof(f) – возвращает значение TRUE, если «почти» достигнут конец файла f (между указателем и концом файла нет никаких символов, кроме пробельных), и FALSE в противном случае;

eoln(f) – возвращает значение TRUE, если достигнут конец строки в файле f (указатель находится сразу за последним элементом строки), и FALSE в противном случае;

seekeoln(f) – возвращает значение TRUE, если «почти» достигнут конец строки в файле f (между указателем и концом строки нет никаких символов, кроме пробельных), и FALSE в противном случае.

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

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

· одна строка, заканчивающаяся символом конца файла;

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

· одна строка, заканчивающаяся символом конца строки, а затем – символом конца файла (на самом деле получается, что в файле содержится не одна, а две строки, но вторая – пустая);

· одна строка, заканчивающаяся несколькими концевыми пробелами, затем символом конца строки, а затем – символом конца файла.

Поскольку функции seekeof() и seekeoln() при каждой проверке пытаются проигнорировать все пробельные символы, то и результаты их работы отличаются от результатов работы функций eof() и eoln(). Эти различия нужно учитывать.

Изменение реакции на ошибку

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

Директива компилятора⁵⁾ {$I-} отключает режим проверки, соответственно директива {$I+} - включает.

Если при отключенной проверке правильности ввода-вывода ({$I-}) происходит ошибка, то все последующие операции ввода-вывода игнорируются вплоть до первого обращения к функции IOResult. Ее вызов "очищает" внутренний показатель ("флаг") ошибки, после чего можно продолжать ввод или вывод.

Если функция IOResult возвращает нуль, значит, операция ввода-вывода была завершена успешно. В противном случае функция вернет номер произошедшей ошибки.

Порядок выполнения работы

1. Открыть проект Delphi Structures.

2. На главной форме (Main Form) установить компонент, управляющий всем проектом – главное меню, и назвать первый пункт «Лабораторная раб. №1» . Расширить меню с помощью вертикальной составляющей: первый вертикальный пункт назвать «Задача 1», второй – «Задача 2».

3. Добавить к проекту модуль с формой Fundstruct, которая должна появляться на экране при выборе пункта меню «Задача 1». Убедитесь в том, что ваша управляющая структура в проекте работает. 

4. Установить на форму модуля Fundstruct компоненты, обеспечивающие ввод исходных данных, управляющую командную кнопку, и компоненты для вывода результатов на экране – для реализации программного приложения в соответствии с вариантом задания таблицы 1.1.

5. В обработчике события onClick командной кнопки на языке Object Pascal написать фрагмент программы для ввода исходных данных, обработки по алгоритму варианта задания и вывода результатов в объекты на форму модуля Fundstruct. Отладить программу и продемонстрировать результаты преподавателю.

6. Добавить к проекту модуль с формой Filestruct, которая должна появляться на экране при выборе пункта меню «Задача 2».

7. Установить на форму модуля Filestruct компоненты, обеспечивающие ввод данных в соответствии с вариантом задания таблицы 1.2, две управляющих кнопки «Ввод» и «Выборка», компоненты для вывода результатов в соответствии с вариантом.

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

9. В обработчике события onClick кнопки «Выборка» запрограммировать чтение имеющегося текстового файла, выборку требуемых данных в соответствии с вашим вариантом и вывод выборки в другой текстовый файл. Отладить обработчик, убедиться в правильности полученной выборки и продемонстрировать результат преподавателю.

10. Составить отчет и защитить работу преподавателю.

Таблица 1.1

№ вар.	Текст задания
1.	Создать верхнюю треугольную матрицу порядка n: в первой строке n элементов, во второй (n-1) элемент, начиная со второго, ...., в n-ой строке -1 элемент на n-ном месте. Заполнить ее единицами и просуммировать для проверки все элементы и отдельно элементы главной диагонали.
2.	Написать программу вычисления значения многочлена по схеме Горнера: а0+а1х+а2х2+...аnxn=а0+х(а1+ х(а2+...+х(аn-1+xan)...) причем с ее помощью чтобы можно было вычислить многочлен любой степени, с любыми коэффициентами и при любом значении х.
3.	Дана непустая последовательность ненулевых целых чисел, за которой следует 0. Определить сколько раз в этой последовательности меняется знак. (Например, в последовательности1, -34, 8, 12, -5 знак меняется 3 раза).
4.	Дана последовательность из n целых чисел. Выявить отрезки возрастания в этой последовательности и вывести каждый из них на экран с новой строки.
5.	Дан массив Х, в котором N целых чисел (N ). Не используя дополнительного массива, элементы массива расположить в обратном порядке.
6.	Дана последовательность из N различных целых чисел (N ). Найти сумму чисел, расположенных между max-ным и min-ным элементами этой последовательности, включая сами эти элементы.
7.	Даны две последовательности по N целых чисел в каждой (N ). Найти наибольшее среди тех членов первой последовательности, которые не входят во вторую последовательность.
8.	Дана последовательность из n целых чисел (n ). Определить количество инверсий в этой последовательности (т.е. таких пар элементов, в которых большее число находится слева от меньшего: xi>xj при i>j).
9.	Дано n вещественных чисел (n ). Определить порядковый номер того из них, который наиболее близок к среднему арифметическому всех этих чисел, считая, что такой элемент единственный.
10.	Даны две последовательности по n целых чисел в каждой (n≤30). Найти наименьшее среди тех членов первой последовательности, которые входят во вторую последовательность (считая, что хотя бы одно такое число есть).

Таблица 1.2

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

1. Концепция типа данных.

2. Объявление массива: статического и динамического.

3. Отображение массива на ОП. Адрес компоненты.

4. Выравнивание; упаковка массива.

5. Тип запись – определение, представление в ОП.

6. Представление множеств в ОП.

7. Последовательный файл.

8. Операции с файлами.

9. Буферизованные последовательности.

Лабораторная работа № 2