Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

Над списками выполняются следующие операции:

• начальное формирование списка (запись первой компоненты);

• добавление компоненты в конец списка;

• определение первого элемента в линейном списке;

• чтение компоненты с заданным ключом; с заданным свойством;

• вставка компоненты в заданное место списка (обычно до компоненты с заданным ключом или после неё);

• исключение компоненты с заданным ключом из списка.

• упорядочивание узлов линейного списка в определенном порядке.

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

В организации стека используется доступ по принципу "последней пошел, первый вышел". Такой метод доступа называют методом LIFO (Last-In, First-Out).

Обычно над стеками выполняются три операции:

• начальное формирование стека (запись первой компоненты);

• добавление компоненты в стек;

• выборка компоненты (удаление).

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

Очередь представляет собой линейный список данных, доступ к которому осуществляется по принципу "первый вошел, первый вышел", иногда сокращенно его называют методом доступа FIFO (First-In, First-Out). Элемент, который был первым поставлен в очередь, будет первым получен при поиске или обработке. Элемент, поставленный в очередь вторым, при поиске будет получен также вторым и т.д. Этот способ является единственным при постановке элементов в очередь и при поиске элементов в очереди.

Применение очереди не позволяет делать прямой доступ к любому конкретному элементу.

Над динамической структурой - очередью - выполняются следующие операции:

• начальное формирование очереди (запись первой компоненты);

• добавление компоненты в конец очереди;

• определение первого элемента в очереди с последующим извлечением его из очереди.

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

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

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

В зависимости от количества связей между соседними элементами различают односвязные и двусвязные списки.

Каждый элемент в списке с двойной связью имеет указатель на следующий элемент списка и указатель на предыдущий элемент списка.

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

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

1) информационного поля или поля данных;

2) ссылки на следующий элемент списка;

3) ссылки на предыдущий элемент списка.

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

Cлучай, когда заглавное звено одно:

Пустой двунаправленный список с одним заглавным звеном:

Приведем вариант структуры двунаправленного списка с двумя заглавными звеньями:

В данном случае двунаправленный список стал симметричным.

Соответствующий пустой двунаправленный список с двумя заглавными звеньями выглядит так:

Рассмотрим три свойства двунаправленных списков:

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

2. если List есть указатель на любой элемент двунаправленного списка, то выполняются следующие свойства

List = List^.pNext^.pPrev

и

List = List^.pPrev ^.pNext

Данные свойства легко можно проиллюстрировать с помощью схемы:

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

Над двунаправленными списками выполняются следующие операции:

• начальное формирование списка (запись первой компоненты);

• добавление компоненты в конец списка;

• вставка компоненты в заданное место списка (обычно до компоненты с заданным ключом или после неё);

• определение первого или последнего элементов в двунаправленном списке;

• чтение компоненты с заданным ключом; с заданным свойством;

• исключение компоненты с заданным ключом из списка;

• упорядочивание узлов линейного списка в определенном порядке.

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

В двоичном (бинарном) дереве каждый узел может быть связан не более чем двумя другими узлами. Рекурсивно двоичное дерево определяется так: двоичное дерево бывает либо пустым (не содержит ни одного узла), либо содержит узел, называемый корнем, а также два независимых поддерева — левое поддерево и правое поддерево.

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

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

Выделим типовые операции над двоичными деревьями поиска:

• добавление элемента в дерево;

• удаление элемента из дерева;

• обход дерева (для печати элементов и т.д.);

• поиск в дереве.

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

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

1. Д. Кнут. «Искусство программирования на ЭВМ», М., Мир, 1978

2. Ахо Альфред В., Хопкрофт Джон Ульман, Джеффри, Д. Структуры данных и алгоритмы : Пер. с англ. : Уч. пос. - М. : Издательский дом "Вильяме", 2000.

Варианты заданий.

Задание №2 (варианты)

1. В качестве элемента рассматривается тип:

TElement = record

Key: Integer;

Data: TData;

end;

1. Для защиты работы студент должен представить работоспособное ПМО и файлы с исходной и выгруженной структурой.

Варианты заданий сведены в таблицу 2.1.

Таблица 2.1.

1. Разработка ПМО для простейших методов решения систем обыкновенных дифференциальных уравнений

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

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

Варианты заданий сведены в таблицу 3.1.

Таблица 3.1.

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

1. Э. Хайрер, С. Нерсетт, Г. Ваннер. Решение обыкновенных дифференциальных уравнений. М., Мир, 1990.

2. Р.В. Хемминг. Численные методы. Изд. “Наука”, М. 1968. Бахвалов, Н. С. Численные методы / Н. С. Бахвалов, Н. П. Жидков, Г. Н. Кобельков. М.: БИНОМ. Лаб. знаний, 2003. 632 с.

3. Бахвалов, Н. С. Численные методы в задачах и упражнениях / Н. С. Бахвалов, А. В. Лапин, Е. В. Чижонков. М.: Высш. шк., 2000. 192 с.

4. Вержбицкий, В. М. Численные методы. Математический анализ и обыкновенные дифференциальные уравнения. М.: Высш.шк., 2001. 383 с.

5. Волков, Е. А. Численные методы. СПб.: Лань, 2004. 248 с.

6. Мудров, А. Е. Численные методы для ПЭВМ на языках Бейсик, Фортран и Паскаль. Томск: МП "РАСКО", 1991. 272 с.

1. Разработка ПМО для методов численного вычисления определенных интегралов

Постановка задачи: Требуется разработать программно-математическое обеспечение, реализующее метод численного вычисления определенных интегралов (в соответствии с вариантом задания).

Характеристики

Список файлов учебной работы