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

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

Лабораторный практикум

для специальностей

230105 - «Программное обеспечение вычислительной техники и автоматизированных систем»

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

Коломна, 2013

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ

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

Государственного образовательного учреждения

Высшего профессионального образования

«МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ОТКРЫТЫЙ УНИВЕРСИТЕТ»

________________________________________________________

Кафедра автоматики и электроники в машиностроении

«УТВЕРЖДЕНО»

Учебно-методическим

Советом КИ (ф) МГОУ

Председатель Совета

___________________

______________ 2013 г.

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

Лабораторный практикум

для специальностей

230105 - «Программное обеспечение вычислительной техники и автоматизированных систем»

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

Коломна, 2013

УДК 004.4 ББК 32.97 П 78

Структуры данных и алгоритмы их обработки: Лабораторный практикум для студентов очной и очно-заочной формы обучения для специальностей 230105 - «Программное обеспечение вычислительной техники и автоматизированных систем», 220201- «Управление и информатика в технических системах»: / Сост. Филоненко И.Н. – Коломна: КИ (ф) МГОУ, 2012. – 65 с.

Лабораторный практикум составлен в соответствии с Государственными образовательными стандартами высшего профессионального образования для специальностей 230105 - «Программное обеспечение вычислительной техники и автоматизированных систем», 220201- «Управление и информатика в технических системах».

Лабораторный практикум одобрен на заседании кафедры «Управление, информатика и вычислительная техника» Коломенского института (филиала) МГОУ имени В.С. Черномырдина, протокол № 7 от 14.03.12 и утвержден учебно-методическим советом.

УДК 004.4

ББК 32.97

Введение

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

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

В процессе выполнения лабораторных работ студенты осваивают и анализируют основные алгоритмы обработки различных структур данных. Освоение достигается путем программирования учебных задач на языке 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 для работы с файлами разных типов.

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

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

№ вар.

Текст задания

Создать верхнюю треугольную матрицу порядка n: в первой строке n элементов, во второй (n-1) элемент, начиная со второго,...., в n-ой строке -1 элемент на n-ном месте. Заполнить ее единицами и просуммировать для проверки все элементы и отдельно элементы главной диагонали.

Написать программу вычисления значения многочлена по схеме Горнера: а₀+а₁х+а₂х²+...а_nxⁿ=а₀+х(а₁+ х(а₂+...+х(а_n_-1+xa_n)...)

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

Дана непустая последовательность ненулевых целых чисел, за которой следует 0. Определить сколько раз в этой последовательности меняется знак. (Например, в последовательности1, -34, 8, 12, -5 знак меняется 3 раза).

Дана последовательность из n целых чисел. Выявить отрезки возрастания в этой последовательности и вывести каждый из них на экран с новой строки.

Дан массив Х, в котором N целых чисел (N

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

Дана последовательность из N различных целых чисел (N

). Найти сумму чисел, расположенных между max-ным и min-ным элементами этой последовательности, включая сами эти элементы.

Даны две последовательности по N целых чисел в каждой (N

). Найти наибольшее среди тех членов первой последовательности, которые не входят во вторую последовательность.

Дана последовательность из n целых чисел (n

). Определить количество инверсий в этой последовательности (т.е. таких пар элементов, в которых большее число находится слева от меньшего: x_i>x_j при i>j).

Дано n вещественных чисел (n

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

10.

Даны две последовательности по n целых чисел в каждой (n≤30). Найти наименьшее среди тех членов первой последовательности, которые входят во вторую последовательность (считая, что хотя бы одно такое число есть).

Таблица 1.2

№ вар.	Текст задания
1.	Создать файл f, содержащий сведения о веществах: название вещества, его удельный вес, проводимость (проводник, полупроводник, изолятор). С помощью другой программы выбрать из этого файла данные о проводниках и сохранить их в другом файле.
2.	Создать файл данных по описанию варианта №1. С помощью другой программы найти среди веществ в этом файле проводник с наибольшим удельным весом.
3.	Создать файл f, содержащий различные даты. Каждая дата – это число, месяц и год. С помощью другой программы найти дату с наименьшим значением года.
4.	Создать файл f, содержащий различные даты, для каждой даты указать число, месяц и год. С помощью другой программы найти все весенние даты и сохранить их в другом файле g.
5.	Создать файл f, содержащий сведения о книгах. Сведения о каждой из книг – это фамилия автора, название книги и год издания. С помощью другой программы найти все книги данного автора, изданные с 1980 года. Сохранить эту информацию в файле g.
6.	Создать файл f, содержащий сведения об экспортируемых товарах: наименование товара, страна, импортирующая товар и объем поставляемой партии в штуках. С помощью другой программы, найти страны, в которые экспортируется данный товар. Занести сведения в файл g.
7.	Создать файл данных f по описанию варианта №6. С помощью другой программы найти общий объем экспорта данного товара.
8.	Создать файл f, который содержит следующие сведения о сотрудниках учреждения: фамилия сотрудника, инициалы и № телефона. С помощью другой программы найти телефон сотрудника по его фамилии и инициалам.
9.	Создать файл f, содержащий сведения об учениках школы: имя, фамилия и название класса (типа 10А). С помощью другой программы вывести все сведения об учениках заданного класса в другой файл, определив при этом количество учащихся в этом классе.
10.	Создать файл f, содержащий сведения об учениках школы: имя, фамилия и название класса (типа 10А). С помощью другой программы выяснить имеются ли однофамильцы в школе; если да – сохранить всю информацию о них в файле g.

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

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

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

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

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

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

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

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

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

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

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