Анализ предметной области. к курсовой работе по дисциплине:

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовой работе по дисциплине:

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

на тему: работа с многочленами представленная в виде линейных списков__

Разработал: Васильева Р. П.__________ _____

Специальность: Информатика и вычислительная техника ____________

Шифр работы: ____________________ Группа: ВБИ21 ______

Руководитель работы: ______________ ___ Румянцев А.Н __________

(подпись) (Ф.И.О).

Работа защищена ___________________ _____________________________

(дата) (оценка)

Ростов-на-Дону

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

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«ДОНСКОЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

Факультет ИиВТ______

Кафедра ПОВТиАС_______

Утверждаю

Зав.каф. Нейдорф Р.А ________

_____________________

«___» _____________ 2012 г.

ЗАДАНИЕ

на курсовую работу по дисциплине

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

Тема: работа с многочленами представленная в виде линейных списков______

Исходные данные: Написать программу, считающую значение выражения при

Руководитель работы: ______________ __ Румянцев А.Н___

(подпись) (Ф.И.О).

Задание принято к выполнению:

«». _______________ _Анишкевич А.А,__

(дата) (подпись) (Ф.И.О. студента)

Ростов-на-Дону

Содержание

Введение 4

Анализ предметной области 5

Алгоритмическое конструирование 9

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

Заключение 37 Список литературы 38

Приложение 39

Введение

Паскаль (англ. Pascal) — язык программирования общего назначения. Один из наиболее известных языков программирования.

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

Язык Паскаль был создан Никлаусом Виртом в 1968—1969 годах после его участия в работе комитета разработки стандарта языка Алгол-68. Он был опубликован в 1970 году Виртом как небольшой и эффективный язык, чтобы способствовать хорошему стилю программирования, использовать структурное программирование и структурированные данные.

Анализ предметной области

ЛИНЕЙНЫЙ СПИСОК – обобщение структур стеков и очередей.

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

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

Функциональная спецификация двоичного дерева:

Пусть Т – базовый тип элементов. Обозначим ЛС_т – линейный список из элементов типа Т.

Операции:

Ø Создание_списка: ® ЛС_т

Ø Список_пуст: ЛС_т ® ЛОГ

Ø Следующий: Т*ЛС_т ® Т

Ø Добавление: Т*Т*ЛС_т ® ЛС_т

Ø Удаление: Т*ЛС_т ® ЛС_т

Ø Первый: ЛС_т ® Т

Логическое описание:

тип ЛС_т = (ПУСТО/Непустой_ ЛС_т)

тип Непустой_ЛС_т = (начало: Т; продолжение_ЛС_т)

Логическое описание должно содержать описание декомпозиции операции функциональной спецификации.

1) прогр. добавление: ЛС_т (арг. t, t^’: T, ll: ЛС_Т)

|добавление если ll есть ПУСТО то непустой_ЛС_Т (t, ll)

иначе непустой_ЛС_Т (начало (ll), добавление (t, t^’, продолжение (ll))

2) прогр. удаление: ЛС_Т (арг. t: T; ll: ЛС_Т)

|удаление если ll есть ПУСТО то ОШИБКА

иначе

если t=начало (ll) то продолжение (ll)

иначе непустой_ЛС_Т (начало (ll), удаление (t, продолжение (ll))

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

Узел и ссылку можно описать так:

Type
Link = ^Node;
Node = record
Data: integer;
Next: Link;
End;

Для описания списка мы будем использовать дополнительно два вспомогательных узла head и z. Узел head будет указывать на первый элемент списка, а z - последний элемент списка. Head иногда называют "голова" списка, а z - "хвост".

Тогда список можно будет представить в следующем виде.

Такое представление данных позволяет производить некоторые операции гораздо более эффективными методами, чем над массивами. Например, если мы хотим передвинуть элемент 1 из конца в начало, то для произведения такой операции в массиве нам потребовалось бы передвинуть все его элементы чтобы освободить место. В связанном же списке мы только меняем ссылки. Оба варианта рисунка эквивалентны; они только по разному нарисованы. Мы просто переустанавливаем ссылку узла, содержащего 1, на узел содержащий 2, а ссылку пустого узла head на узел содержащий 1. Даже если бы список был очень большой, то нам все равно потребовалось бы только три перестановки ссылок для подобного обмена.

Что более важно, теперь мы можем говорить о "вставке" элемента в связанный список (что увеличивает его длину на один элемент) - операции которая столь неестественна и неудобна на массивах. На рисунке показано как вставить в список новый узел. Нужно вначале добавить этот узел, затем создать ссылку на узел q, а затем изменить ссылку узла p на новый узел. Для этого требуется изменить лишь две ссылки в независимости от длины списка.

Аналогично, мы можем вести речь об "удалении" элемента из списка (что уменьшает его размер на один элемент). Нужно просто переставить ссылку на узел, который следует за узлом q и после этого узел содержащий q должен быть уничтожен.

С другой стороны, есть и операции для которых связанный список не очень хорошо подходит. Наиболее очевидная из них - это "найти k-й элемент" (найти элемент по его индексу): в массиве это делалось простым обращением типа a[k], но в связанном списке мы должны пройти по k ссылкам.

Другой неестественной операцией над связанными списками является операция "найти элемент перед заданным". Если все, что у на есть - это ссылка на элемент q в нашем примере, то единственный способ найти элемент p, который указывает на q - это пройти по всем ссылкам начиная с узла head. На самом деле - эта операция необходима для удаления заданного элемента из списка: как же иначе мы можем переустановить ссылку предыдущего узла? Во многих задачах, мы можем обойти эту проблему посредством изменения формулировки этой фундаментальной операции на "удалить узел следующий после данного". Аналогичная проблема может быть обойдена и для вставки посредством изменения определения операции на "вставить элемент после заданного узла".

Поиск по сайту: