Рефераты. Информационная система расчетов по договорам

Каждый элемент массива занимает 1 байт памяти. Соответственно массив WTKar будет занимать (30+1)*150=4650 байт.

Логическая схема структуры массива BANKar:

0

1

2

30

1

2

3

50

Каждый элемент массива занимает 1 байт памяти. Соответственно массив BANKar будет занимать (30+1)*50=1550 байт.

4. Алгоритмы обработки основных структур

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

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

Пирамидальная сортировка требует N•Log2N шагов даже в худшем случае. Такие отлиные характеристики для худшего случая - одно из самых выгодных качеств пирамидальной сортировки.

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

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

K[L], ..., K[R], такая, что

K[i] ? K[2i] & K[i] ? K[2i + 1], (1)

для всякого i = L, ..., R/2. Если имеется массив К[1], К[2], ..., К[R], который индексируется от 1, то этот массив можно представить в виде двоичного дерева. Пример такого представления при R=10 показан на рисунке 2.

Рис.2 - Массив ключей, представленный в виде двоичного дерева

Дерево, изображенное на рисунке 2, представляет собой пирамиду, поскольку для каждого i = 1, 2, ..., R/2 выполняется условие (1). Очевидно, последовательность элементов с индексами i = R/2+1, R/2+2, ...., R (листьев двоичного дерева), является пирамидой, поскольку для этих индексов в пирамиде нет сыновей.

Способ построения пирамиды «на том же месте» был предложен Р. Флойдом. В нем используется процедура просеивания (sift), которую рас-смотрим на следующем примере.

Предположим, что дана пирамида с элементами К[3], К[4], ..., К[10] нужно добавить новый элемент К[2] для того, чтобы сформировать расши-ренную пирамиду К[2], К[3], К[4], ..., К[10]. Возьмем, например, исходную пирамиду К[3], ..., К[10], покачанную на рисунке 3, и расширим эту пирамиду «влево», добавив элемент К[2] =44.

Рис.3 - Пирамида, в которую добавляется ключ К[2]=44

Добавляемый ключ К[2] просеивается в пирамиду: его значение сравнивается с ключами узлов-сыновей, т.е. со значениями 15 и 28. Если бы оба слюча-сына были больше, чем просеиваемый ключ, то последний остался бы на месте, и просеивание было бы завершено. В нашем случае оба ключа-сына меньше, чем 44, следовательно, вставляемый ключ меняется местами с наименьшим ключом в этой паре, т.е. с ключом 15. Ключ 44 записывается в элемент К[4], а ключ 15 - в элемент К[2]. Просеивание продолжается, поскольку ключи-сыновья нового элемента К[4] оказываются меньше его - происходит обмен ключей 44 и 18. В результате получаем новую пирамиду, показанную на рисунке 4.

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

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

Рис.4 - Просеивание ключа 44 в пирамиду.

Алгоритм просеивания в пирамиду допускает рекурсивную формулировку:

просеивание элемента с индексом temp,

при выполнении условий остановки - выход,

определение индекса q элемента, с которым выполняется обмен,

обмен элементов с индексами temp и q,

temp:= q,

перейти к п. 1.

Этот алгоритм в применении к нашему массиву а реализован в подпрограмме Sift, которая выполняет просеивания в пирамиду с максимальным индексом R:

Procedure Sift (temp, R: Integer);

Var q: integer;

x: TElement;

Begin

q:==2*t;

If q > R Then Exit;

If q < R Then

If a[q-l].Key > a[q].Key Then q:= q + 1;

If a[temp-1].Key <= a[q-l].Key Then Exit;

x:= a[temp-1];

a [temp-1] := a[q-l];

a[q-l]:= x;

temp:= q;

Shift (temp, R);

End;

Процедура Shift учитывает индексацию вектора а от нуля.

Теперь рассмотрим процесс создания пирамиды из массива а[0], а[1], a[Highlndex]. Элементы этого массива индексируются от 0, а пирамида от 1. Ясно, что элементы a[N/2], a[N/2+1], ..., a[Highlndex] уже образуют пирамиду, поскольку не существует двух индексов i (i= N/2+1, N/2+2, …) и j, таких, что, j=2i (или j=2i+l). Эти элементы составляют последовательность, которую можно рассматривать как листья соответствующего двоичного дерева. Теперь пирамида расширяется влево: на каждом шаге добавляется новый элемент и при помощи просеивания помещается на соответствующее место. Этот процесс иллюстрируется следующим примером.

Процесс построения пирамиды

44 55 12 42 94 18 06 67

44 55 12 42 94 18 06 67

44 55 06 42 94 18 12 67

44 42 06 55 94 18 12 67

06 42 12 55 94 18 44 67

Примечание - жирным шрифтом отмечены ключи, образующие пирамиду на текущем шаге ее построения

Следовательно, процесс построения пирамиды из N элементов «на том же месте» можно описать следующим образом:

R:= N;

For i:= N Div 2 Downto 1 Do

Sift(i, R);

Для того, чтобы получить не только частичную, но и полную упорядоченность элементов нужно проделать N сдвигающих шагов, причем после каждого шага на вершину дерева выталкивается очередной (наименьший элемент). Возникает вопрос, где хранить «всплывающие» верхние элементы? Существует такой выход: каждый раз брать последнюю компоненту пирамиды (скажем, это будет х), прятать верхний элемент на место х, а х посылать в начало пирамиды в качестве элемента а[0] и просеивать его в нужное место. В следующей таблице приводятся необходимые в этом случае шаги:

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

06 42 12 55 94 18 44 67

12 42 18 55 94 67 44 06

18 42 44 55 94 67 12 06

42 55 44 67 94 18 12 06

44 55 94 67 42 18 12 06

55 67 94 44 42 18 12 06

67 94 55 44 42 18 12 0б

94 67 55 44 42 18 12 06 - Результат

Этот процесс описывается с помощью процедуры Sift следующим образом:

For R:= Highlndex Downto 1 Do Begin

x:=a[0]; a[0]:=a[R]; a[R]:=x;

Sift(1, R);

End;

Из примера сортировки видно, что на самом деле в результате мы получаем последовательность в обратном порядке. Но это легко можно исправить, изменив направление отношения порядка в процедуре Sift (в третьем и четвертом операторах If текста процедуры Sift, приведенного выше). В результате получаем следующую процедуру PyramidSort, учитывающую специфику индексации вектора а:

Procedure PyramidSort;

Var R, i: integer;

x: TElement;

Begin

R:= N;

For i:= N Div 2 Downto 1 Do

Sift(i, R);

For R:= Highlndex Downto 1 Do Begin

x:=a[0]; a[0]:= a[R]; a[R]:= x;

Sift(l, R);

End;

Алгоритм просеивания для некоторого массива а можно представить в следующей блок-схеме:

5. Руководство пользователя

Данное програмное обеспечение имеет интуитивно понятный интерфейс и использует все богатейшие возможности пакета Borland Delphi.

Программа имеет четыре вкладки. При первоначальном запуске активируется первая - вкладка хозяйственных договоров “ХД” (см. рис.5).

Рис.5 - Вкладка ходяйственных договоров

Здесь же можно внести изменения (предварительно отметив чекбокс «редактирование»), добавить или удалить новые записи.

Перейдя на вкладку временных трудовых коллективов “ВТК” (см. рис.6), мы попадем на список атрибутов исполнителей всех хоздоговоров, являющиеся членами соответствующих ВТК.

Рис.6 - Вкладка списков атрибутов исполнителей всех хоздоговоров

Здесь также можно редактировать списки, удалять их и добавлять новые. Нужно отметить, что “Код ХД” составляется из номера договора и года заключения договора.

Третья вкладка “Банк” содержит атрибуты отделений банков сбербанка, где имеются счета исполнителя договоров (см. рис.7).

Рис.7 - Вкладка атрибутов отделений банков сбербанка.

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

И в четвертой вкладке находится упорядоченный по количеству членов ВТК (по возрастанию или по убыванию) всех незавершенных договоров с указанием части их атрибутов (согласно заданию к курсовому проектированию). Скриншот данной вкладки представлен на рис. 8.

Рис.8 - Вкладка атрибутов незавершенных договоров

Сортировка незавершенных договоров происходит или по убыванию, или по возрастанию количества членов ВТК пирамидальным методом (согласно заданию к курсовому проектированию).

Из всех вкладок доступно меню “Файл”, в которм можно сохранить файлы с записями всей информации, обновить данную информацию или выйти из программы. Также доступен поиск отдельных элементов атрибутов.

Заключение

В процессе разработки данного курсового проекта были изучены и закреплены знания по физическим размещениям структур данных и методам их обработки (сортировки). В ИСР DELPHI была разработана инормационная система расчётов по договорам. При создании программы не использовались компоненты баз данных данной ИСР.

Страницы: 1, 2, 3



2012 © Все права защищены
При использовании материалов активная ссылка на источник обязательна.