Оформление и защита курсовой работы.

Механико- технологический факультет

Кафедра программного обеспечения

Методические указания к выполнению курсовой работы

по дисциплине: «Структуры и алгоритмы обработки данных», «Алгоритмы и структуры данных»

для студентов дневного и заочного отделений направлений бакалавриата

230100.62 «Информатика и вычислительная техника»,

231000.62 «Программная инженерия»

 

 

Составитель: ст. преп. Кузниченко М.А.

 

 

Орск 2013 г.

 

Содержание.

 

1. Этапы выполнения курсовой работы. 3

2. Оформление и защита курсовой работы. 4

3. Содержание отчета по курсовой работе. 4

4. Варианты заданий курсовой работы... 7

 

Этапы выполнения курсовой работы.

 

Курсовая работа по дисциплинам «САОД» и «АСД» является итогом изучения названного курса и имеет целью закрепление навыков, приобретенных студентами на теоретических занятиях и лабораторных работах по данному учебному курсу.

Спектр заданий касается рассмотрения базовых алгоритмов сортировки, поиска как во внешней так и во внутренней памяти компьютера, организации и обработки динамических списочных и древовидных структур, основ объектно- ориентированного программирования и др.

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

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

На следующем этапе студент разбивает большую задачу курсовой работы на отдельные более мелкие подзадачи и приступает к их реализации на алгоритмическом языке С++. Рекомендуется каждую подзадачу реализовать в отдельной функции. Для каждой такой функции должен быть создан алгоритм, показывающий логику выполнения подзадачи. Все алгоритмы, построенные согласно ГОСТу, затем будут включены в пояснительную записку.

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

Курсовая работа должна быть оформлена в виде самостоятельного приложения с применением меню, в котором предусмотрены всевозможные пункты обработки данных согласно варианту задания. Следует обратить внимание на создание дружественного интерфейса с пользователем, а также защиту от неверных действий пользователя с выводом сообщений об ошибках.

 

Оформление и защита курсовой работы.

 

По окончании отладки и тестирования программы для различных входных данных студент приступает к оформлению пояснительной записки к курсовой работы, который должен быть оформлен на компьютере с использованием текстового редактора MS Word (шрифт Times New Roman, размер 14, интервал полуторный). Отчет должен содержать Титульный лист, Техническое задание, Аннотацию, Введение, Теоретическую часть, Практическую часть, Заключение. Страницы пояснительной записки должны быть пронумерованы.

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

Цель: программная реализация динамического двусвязного списка.

Задачи:

1 Описание структур данных

2 Операции над двусвязными списками.

3 Организация работы в меню

4 Работа с файлом

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

В теоретической части описывается теоретический материал по теме курсовой работы, объем которой составляет 3-5 страниц. Здесь рассматриваются основные понятия, определения, операции над структурами данных, которые будут реализовываться в курсовой работе.

В практической части размещаются параграфы:

2.1 Спецификация и обоснование структур данных и их типов.

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

2.2 Блок- схема основной программы main()

2.3 Блок- схема функции <название функции>

2.4 ……

2.5 Описание файлов, входящих в проект или в приложение

2.6 Тестирование программы.

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

Блок- схемы функций должны быть построены с учетом требований ГОСТа. В каждой блок- схеме должен быть блок начала (самый верхний) и блок окончания (самый нижний) функции. Каждая линия схемы должна быть завершена.

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

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

Курсовая работа оценивается дифференцированно, и оценка заносится в зачетную книжку, а затем – в диплом. Курс «Структуры и алгоритмы обработки данных» является общепрофессинальной дисциплиной учебного плана, знание которого используется при изучении других дисциплин специальностей 230100 и 231000. Материалы данной дисциплины будут использоваться при изучении дисциплин «Базы данных», «Объектно- ориентированное программирование», «Компьютерное моделирование» и др.

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

Список литературы. (не менее 10 источников, включая адреса Интернет- сайтов, если таковые использовались)

Приложение. Текст программного кода.

К пояснительной записке прикладывается CD- диск с программой и текстом пояснительной записки.

Варианты заданий курсовой работы

 

№	Задание	ФИО
1.	Описать хеш- функцию и составить таблицу хеширования записей некоторой базы данных по некоторому строковому ключу (например, по названию книги), используя метод середины квадрата. Предусмотреть использование метода цепочек при наличии коллизий хеширования. Используя данные функции, выполнить поиск и вставку в таблицу хеширования. Проанализировать зависимость подсчета среднего числа попыток поиска или включения Е(а) от коэффициента заполнения таблицы. Выполнить поиск данных в реальной базе, состоящей из записей, содержащих информацию о книгах библиотеки (шифр; название; автор; количество).	Топоров
2.	Описать хеш- функцию и составить таблицу хеширования записей некоторой базы данных по многозначному числовому ключу (например, по шифру товара), используя метод свертки. Предусмотреть использование квадратичной функции при наличии коллизий хеширования. Выполнить поиск и вставку в таблицу хеширования. Проанализировать зависимость подсчета среднего числа попыток поиска или включения Е(а) от коэффициента заполнения таблицы. Выполнить поиск реальной базы данных, состоящей из записей, содержащих информацию о товарах на складе (шифр товара; наименование; цена; количество).	Зверев
3.	Описать хеш- функцию и составить таблицу хеширования записей некоторой базы данных по многозначному числовому ключу (например, по шифру товара), используя метод деления на простое число. Предусмотреть использование повторного хеширования с изменяющемся шагом при наличии коллизий хеширования. Выполнить поиск и вставку в таблицу хеширования. Выполнить заполнение таблицы автоматически. Осуществить подбор простого числа, определяющего размер таблицы. Проанализировать зависимость подсчета среднего числа попыток поиска или включения Е(а) от коэффициента заполнения таблицы. Выполнить поиск реальной базы данных, состоящей из записей, содержащих информацию о товарах на складе (табельный номер; ФИО; оклад; должность).	Хлыстова
4.	Составить таблицу перекрестных ссылок. Программа читает текст и собирает все слова этого текста в дерево поиска, запоминая номера строк, в которых встречалось данное слово. После того, как просмотр будет окончен, формируется таблица, в которой все слова расположены в алфавитном порядке и со списками их местонахождений. Каждая вершина дерева не только содержит в качестве ключа само слово, но и является началом списка номеров строк, в которых это слово встречалось в тексте. Имя текстового файла запрашивается у пользователя с клавиатуры.	Данилов
5.	Описать класс BinTree для представления двоичных деревьев поиска созданной вами структуры, предназначенной для поиска в некоторой реальной библиотеке книги по наименованию (шифр книги, автор, название, цена, количество). Конструктор должен формировать единичное дерево с нулевыми потомками. Предусмотреть выбор формирования дерева: с клавиатуры, из файла, из массива данных. Организовать работу в меню, в котором предусмотреть все операции над двоичными деревьями поиска, включая удаление узла. Реализовать взятие читателем и возврат заданной книги. При этом должно изменяться количество книг. В меню предусмотреть вывод списка книг по алфавиту названий (обход).	Файзулин
6.	Обработка сбалансированных (АВЛ) деревьев. Организовать класс обработки АВЛ- деревьев. Предусмотреть выбор формирования дерева: с клавиатуры, из файла, из массива данных. Организовать работу в меню, в котором предусмотреть все операции над АВЛ- деревьями (печать дерева, добавление элемента, удаление, поиск узла по заданному ключу), а так же балансировку дерева при необходимости. Выполнить поиск реальной базы данных, состоящей из записей, содержащих информацию об оборудовании некоторого предприятия (инвентарный номер оборудования, наименование, цена, дата ввода в эксплуатацию). Рекомендуется выполнить построение и обработку дерева в графическом виде.
7.	Описать класс Stack для обработки стека, состоящего из узлов созданной вами структуры. Создать стек – объект класса. Конструктор должен формировать пустой стек или новый стек с помощью копирования из другого стека. Описать деструктор, а так же функции- члены добавления в стек, извлечения из стека, проверки стека на пустоту и др. Выполнить раздельную компиляцию, создать header- файл для работы со стеком. Используя данный класс, выполнить преобразование арифметического выражения в обратную польскую запись. Предусмотреть ввод информации из файлового потока и с клавиатуры. После преобразования выражения выполнить вычисление его значения за один просмотр, используя стек.	Сокуренко
8.	Создать класс обработки двусвязного с головой, которая имеет указатели на первый и последний элементы списка. Определить структуру и все функции обработки. Методом включения отсортировать узлы списка в порядке возрастания числового поля (номер).Организовать обработку списка в меню, в котором предусмотреть операции добавления и удаления узлов, вывод списка на экран, проверку на упорядоченность. Разделить описание класса от его реализации. Выполнить раздельную компиляцию и работу в проекте. Если список отсортирован, то добавляемый элемент включается в список, не нарушая его упорядоченности.	Линкер
9.	Множества А и В целых чисел представлены линейными двунаправленными списками, в которых строки следуют в порядке возрастания. Голова списка имеет указатели на голову и хвост. Предусмотреть формирование множеств из файлов, в которых строки не упорядочены. Реализовать операции над множествами: xor (исключающее ИЛИ); ‘-‘ (разность); ‘+’ (объединение); ‘*’ (пересечение). Результатом должен быть список той же структуры. Добавить логические функции сравнения на эквивалентность двух множеств и принадлежности некоторого значения множеству. Пусть в нескольких (2-3) файлах хранятся прайс- листы разных фирм, торгующих идентичными товарами. Найти одинаковые товары, товары, которые есть в одной фирме, но отсутствуют в другой. Выдать общий перечень товаров. Организовать работу в меню.	Фазлеев
10.	Многофазное слияние. Произвольный файл произвольной длины (количество элементов запрашивается с клавиатуры) создается автоматически, например, случайным образом. Выполняется сортировка, после чего файл читается и выводится на экран или в файл по запросу пользователя. Для выполнения поиска, файл переписывается в массив и выполняется бинарный поиск с подсчетом числа выполненных сравнений. Найденный элемент и количество попыток поиска выводится на экран. Организовать работу в меню.
11.	Имеется некоторое множество двусвязных линейных списков, на которые указывают указатели из массива Р (Р[0], P[1], … , P[n-1]). Списки формируются в режиме диалога с пользователем из файлов данных и содержат неупорядоченные последовательности в формате: табельный номер, фамилия сотрудника. Упорядочить эти списки методом шейкерной сортировки, используя функцию. Из этих списков получить один новый упорядоченный список, образованный узлами исходных списков, используя метод прямого слияния. При этом считываются очередные значения из списков и сравниваются друг с другом. Наименьшее записывается в результирующий список и т.д. пока не закончатся все списки.	Нуркаева
12.	Реализовать блочную сортировку некоторого файла большого размера. Файлы создаются случайным образом и состоят из одного числового поля и одного строкового. Определить диапазон значений и диапазон для каждого блока. При чтении файла разбивать его на блоки, состоящие из двусвязных линейных списков с головой. Голова хранит указатель на первый и последний элементы списка. Затем методом включений отсортировать каждый список в порядке возрастания. Слить все списки в файл, получив упорядоченную последовательность. Предусмотреть работу в меню. Создать класс обработки списков.	Газизова
13.	Дать словесное описание метода пирамидальной сортировки, определить алгоритм и выполнить программную реализацию. Выполнить чтение неупорядоченного файла, состоящего их 3 полей (например, шифр изделия, его наименование и цена). Проанализировать эффективность данного метода в сравнении с другими методами сортировки в основной памяти (например, пузырьковой сортировкой, сортировкой включением, сортировкой выбором). Для этого использовать разные методы для одинаковых массивов большого размера в «лучшем», «худшем» и «средних случаях».	Минин
14.	Построение частотного словаря на основе двоичного дерева поиска, т.е. в вершине дерева должно храниться слово и количество его появлений в тексте. Создать класс обработки двоичных деревьев, предусмотрев все основные операции над деревом. Дополнить класс функциями включения элемента, поиска элемента по значению ключа, обхода дерева в симметричном порядке. Имя файла, предназначенного для сканирования запрашивать с клавиатуры. При распознавании слова учитывать, чтобы в слово не входили знаки препинаний, скобки и другие специальные символы. Вывести весь список встречающихся в тексте слов в алфавитном порядке. Определить слово, которое встречалось чаще других.	Балтыжаков
15.	Выполнить сбор статистики с помощью сканирования программ и определения частот появлений ключевых слов языка C++ в текстах программ *.cpp. Определение на принадлежность слова к словарю оформить в виде бинарного поиска заданного идентификатора в массиве (файле) стандартных слов (help- файл). Вывести результаты сбора статистики в файлы: в одном файле расположить ключевые слова в алфавитном порядке, в другом – в порядке убывания количества появления слова.	Калинин
16.	Описать класс обработки одномерных массивов, в который включить наиболее часто используемые операции над массивами: вывод массива в выходной поток (экран, файл), добавление в массив нового элемента. Взять для примера массив структур, в котором хранятся данные, подобные записям в записной книжке. Предусмотреть чтение данных из файла в массив, сортировку методом выбора и методом шейкерной сортировки по фамилии. Реализовать метод бинарного и интерполяционного поиска в массиве по фамилии. Вывести количество сравнений. Организовать работу в меню.
17.	Дать определение и теоретическое толкование дерева оптимального поиска. Реализовать его структуру, построение и использование на основе статистических данных о частоте появления ключевых слов языка программирования. Определить функцию определения общей взвешенной длины пути дерева. Использовать результаты сбора статистики из заданного файла. (см. вариант курсовой работы №14) Построить простое дерево и сравнить взвешенные длины пути этих деревьев.
18.	Описать класс обработки очереди с приоритетами на базе двусвязного списка с описанием всех присущих ей функций. При удалении элемента из очереди ищется минимальный и удаляется. Добавление элемента - в конец очереди. Сотрудники компании определяются по категориям: менеджер, супервайзер и рабочий. Создав тип enum Staff {Manager, Supervisor, Worker}; имеем естественное упорядочение, дающее уровень приоритета при заявке на выполнение работ. Каждый сотрудник может сделать заказ на выполнение задания, заполнив форму, которая включает информацию о категории служащего, ID- номер задания, время выполнения задания. Заявки на выполнение работ вводятся в очередь с приоритетом, определяемом по категории сотрудника. Файл job.dat содержит список заявок, которые загружаются в очередь приоритетов. Элементы извлекаются из очереди и выполняются. Массив Service[3] содержит общее количество времени, потраченное на обслуживание каждого из различных типов сотрудников. Вывести порядок выполнения заявок, указать суммарное время обслуживания по категориям.
19.	Описать класс Array обработки одномерных массивов произвольного размера и типа. Использовать шаблон для типа <template>. Память выделяется динамически. К основным функциям (добавление и удаление элементов массива, поиск по ключу, вывод массива на экран по n строк) добавьте функции чтения данных из файла, функции сортировки массива различными способами: методом включения , методом Шелла, быстрой сортировкой Хоара. Сделать сравнительный анализ эффективности данных методов, т.е. для каждого метода и для каждого случая определить количество сравнений и обменов. Предусмотреть 3 случая исходного массива: а) случайный массив, б) «лучший случай» (отсортированный массив), в) «худший случай» (массив отсортирован в обратном порядке). Организовать работу в меню. Выполнить раздельную компиляцию и работу в проекте.	Мысливко
20.	Описать класс Array обработки одномерных числовых массивов произвольного размера. Память выделяется динамически. К основным функциям (добавление и удаление элементов массива, поиск по ключу, вывод массива на экран по n строк) добавьте функции чтения данных из файла, сортировки массива различными способами: методом простого выбора, методом «пузырька», шейкерной сортировкой, методом простого выбора. Сделать сравнительный анализ эффективности данных методов, т.е. для каждого метода и для каждого случая определить количество сравнений и обменов. Предусмотреть 3 случая исходного массива: а) случайный массив, б) «лучший случай» (отсортированный массив), в) «худший случай» (массив отсортирован в обратном порядке). Организовать работу в меню. Выполнить раздельную компиляцию и работу в проекте.	Леонова
21.	Описать класс, реализующий тип данных «вещественная матрица». Класс должен реализовать следующие операции над матрицами: · Сложение, вычитание, умножение, деление (+, -, *, /) (* и / как на другую матрицу, так и на число) · Комбинированные операции (+=, - =, *=, /=); · Операция сравнения на равенство (= =); · Операция вычисления обратной и транспонированной матрицы; · Вычисление детерминанты и нормы; · Методы, реализующие проверку типа матрицы (квадратная, диагональная, нулевая, единичная, симметричная, верхняя треугольная, нижняя треугольная); · Операции ввода – вывода в стандартные потоки. Программа должна содержать меню, позволяющее осуществить проверку всех методов класса. Выполнить раздельную компиляцию.	Кириченко
22.	Реализовать внешнюю сортировку методом прямого слияния. Произвольный файл произвольной длины (количество элементов запрашивается с клавиатуры) создается автоматически, например, случайным образом. Выполняется сортировка, после чего файл читается и выводится на экран или в файл по запросу пользователя. Для выполнения поиска, файл переписывается в массив и выполняется бинарный поиск с подсчетом числа выполненных сравнений. Найденный элемент и количество попыток поиска выводится на экран. Организовать работу в меню.
23.	Естественное слияние. Произвольный файл произвольной длины (количество элементов запрашивается с клавиатуры) создается автоматически, например, случайным образом. Выполняется сортировка, после чего файл читается и выводится на экран или в файл по запросу пользователя. Для выполнения поиска, файл переписывается в массив и выполняется бинарный поиск с подсчетом числа выполненных сравнений. Найденный элемент и количество попыток поиска выводится на экран. Организовать работу в меню.	Сидоров
24.	Описать класс для обработки дека. Дек- структура данных на базе двусвязного списка, в который операции вставки и удаления разрешаются с обеих сторон. В последовательности EAs + Y +QUE * * + st + * + IO * n + + * Буква верхнего регистра означает операцию put в начале дека, буква нижнего регистра – put в конце дека, знак + означает операцию get в начале, * - операцию get в конце. Найти последовательность значений, возвращаемых операциями get, когда эта последовательность операций выполняется над пустым деком. Найти, каким образом в последовательности EasY необходимо вставить знаки + и *, чтобы операции get возвращали следующую последовательность символов: a) EsaY; b) YasE; c) aYsE; d) asYE; либо докажите, что такая последовательность невозможна. Предусмотреть ввод информации из файлового потока и с клавиатуры. Добавьте функцию, просматривающую состояние дека после каждой операции.
25.	Создать класс Complex обработки комплексных чисел (a + bi). Определить все операции (сложение, вычитание, умножение, деление) над комплексными числами, перегрузив стандартные операции. Перегрузить оператор вывода в поток <<и совместное умножение *=.Вычислить и вывести на экран и в файл числа cos(2pk/N) +i sin(2pk/N) k=0,1, …,N-1 В файле заданы комплексные числа в столбик. Прочесть их, вывести на экран и найти их произведение и сумму. Результат сохранить в том же файле.
26	Описать класс для обработки линейного связного списка из числовых значений. В данные о списке включить количество элементов в нем, указатель на первый и последний элементы. Определить операции добавления (в начало или конец списка), поиск, удаление элемента из списка. Список использовать для хранения целочисленных и вещественных значений. В файле хранятся числа. Сформировать N списков таким образом, чтобы каждый список хранил только неубывающие последовательности. Вывести полученные списки на экран. Слить все списки в один, представляющий собой упорядоченную последовательность. Результат сохранить в файле.	Тазуев
27	Описать класс для обработки линейного двусвязного списка с головой структурного типа (фамилия абонента, номер телефона, адрес). В данные о списке включить количество элементов в нем, указатель на первый и последний элементы. Определить операции добавления, поиск, удаление элемента из списка. В файле хранятся данные о телефонах сотрудников некоторой организации. Перед началом работы данные считываются из файла в список. Если список неупорядочен, то выполняется сортировка. В дальнейшем новый абонент добавляется в список таким образом, чтобы не нарушилась его упорядоченность. Результат сохранить в файле. Оформить поиск абонента по его номеру телефона.	Топоров
28	Описать хеш- функцию и составить таблицу хеширования записей некоторой базы данных по многозначному числовому ключу (например, по шифру товара), используя метод деления. Предусмотреть использование цепочек переполнения для разрешения коллизий хеширования. Выполнить поиск и вставку в таблицу хеширования. Проанализировать зависимость подсчета среднего числа попыток поиска или включения Е(а) от коэффициента заполнения таблицы. Выполнить поиск реальной базы данных, состоящей из записей, содержащих информацию о товарах на складе (шифр товара; наименование; цена; количество).
29