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

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

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

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

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

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

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 обработки одномерныхмассивов произвольного размера и типа. Использовать шаблон для типа. Память выделяется динамически. К основным функциям (добавление и удалениеэлементов массива, поиск по ключу,вывод массива на экран по 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). Определить всеоперации (сложение, вычитание, умножение, деление) над комплексными числами,перегрузив стандартные операции. Перегрузить оператор вывода в поток
26	Описать класс для обработкилинейного связного списка из числовых значений. В данные о списке включитьколичество элементов в нем, указательна первый и последний элементы. Определить операции добавления (в начало или конец списка),поиск, удаление элемента из списка. Список использовать для храненияцелочисленных и вещественных значений. В файле хранятся числа.Сформировать Nсписков таким образом, чтобы каждый список хранил только неубывающиепоследовательности. Вывести полученные списки на экран. Слить все списки водин, представляющий собой упорядоченную последовательность. Результатсохранить в файле.	Тазуев
27	Описать класс для обработкилинейного двусвязного списка с головой структурного типа (фамилия абонента,номер телефона, адрес). В данные о списке включить количество элементов в нем, указатель на первый ипоследний элементы. Определить операциидобавления, поиск, удаление элемента из списка. В файле хранятся данные о телефонах сотрудников некоторойорганизации. Перед началом работы данные считываются из файла в список. Еслисписок неупорядочен, то выполняется сортировка. В дальнейшем новый абонентдобавляется в список таким образом, чтобы не нарушилась его упорядоченность.Результат сохранить в файле. Оформить поиск абонента по его номеру телефона.	Топоров
28	Описать хеш- функцию и составитьтаблицу хеширования записей некоторой базы данных по многозначному числовомуключу (например, по шифру товара), используя метод деления.Предусмотреть использование цепочек переполнения для разрешенияколлизий хеширования. Выполнить поиски вставку в таблицу хеширования. Проанализировать зависимость подсчетасреднего числа попыток поиска или включенияЕ(а) от коэффициента заполнения таблицы. Выполнить поиск реальной базыданных, состоящей из записей, содержащих информацию о товарах на складе (шифртовара; наименование; цена; количество).
29

Статьи к прочтению:

Защита курсовой работы

Похожие статьи: