Белорусский национальный технический университет

Международный институт дистанционного образования

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

КУРСОВОЙ ПРОЕКТ

по курсу « Структуры и организация данных в ЭВМ »

На тему

« Информационная система расчетов по договорам »

Исполнитель ст. гр.417313 Я

Руководитель Романов А.В.

Минск 2005г.

Введение

Без использования данных и структур, образованных элементами данных, не обходится ни одна программа для электронных вычислительных машин. Любые конструкции программы – нотации, операторы и т. д. – обязательно включают в себя идентификаторы некоторых данных и их совокупностей. Логическая схема структуры данных, представляющей собой совокупность взаимосвязанных данных, определяет не только внутреннее представление в памяти компьютера информационной модели некоторой предметной области (или ее составной части), но и, что самое главное, построение алгоритма, применяемого для обработки этой структуры. Так, например, алгоритм включения нового элемента в таблицу, организованную в памяти как вектор записей, не может быть использован для включения в иерархически организованный список. Как указывает Н. Вирт, определяющую роль в программировании играют не алгоритмы, а именно структуры данных, логическое и физическое построение которых являются главными факторами, влияющими на реализацию программируемой процедуры обработки.

Значимость той роли, которую играют структуры данных в процессе конструирования и кодирования программ для ЭВМ, послужила причиной появления в специальной «компьютерной» литературе множества работ, посвященных структурному подходу к организации данных. Было разработано значительное количество программных компонентов (многие из них получили название «стандартных»), применение которых существенно облегчило работу по обработке тех взаимосвязанных совокупностей данных, которые выбирают программисты для использования в своих программах. В учебных программах высших учебных заведений появилась специальная дисциплина «Структуры и организация данных в ЭВМ», в рамках которой изучаются не только логические схемы различных структур данных и способы их физической организации, но и построение алгоритмов обработки таких структур (формирования, просмотр и т. д.). Важность такой дисциплины для специалистов по программному обеспечению трудно переоценить.

Тема данного курсового проекта – «Информационная система расчётов по договорам». При этом по заданию к курсовому проекту необходимо использовать структуру данных типа вектор и пирамидальную сортировку данных.

Базовым была взята ИСР Delphi, так как он позволяет с большой гибкостью оперировать различными данными, а также предоставляет практически неограниченные возможности по созданию пользовательских интерфейсов.

Ниже я приведу некоторые обоснования использования среды Delphi для разработки данного программного продукта.

Delphi - это комбинация нескольких важнейших технологий:

• Высокопроизводительный компилятор в машинный код.

• Объектно-ориентированная модель компонент.

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

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

2. Состав DELPHI-проекта

1. Состав проекта

Данный проект состоит из одной формы Form1. На форме расположены следующие компоненты (см. рис1):

- компонент MainMenu1 – осуществляет общее управление программой, в частности сохранение файлов с данными, обновление данных из файлов, выход из программы.

- компонент BtnDel – кнопка в нижней части формы для удаления записей данных.

- компонент txtSearch – поле ввода искомых данных.

- компонент btnSearch – кнопка для начала поиска введенных данных в поле txtSearch.

- компонент CheckBox1 – соответственно для разрешения редактирования данных.

- компонент PageControl1 – содержит вкладки TabSheet 1÷4 на которых отражены данные (соответственно “ХД”, “ВТК”, “БАНК” и “Незавершенные договора”).

Компоненты TabSheet 1÷4 содержат в себе элементы таблицы (соответственно “XDgrid”, “WTKgrid”, “BANKgrid” и “NDgrid”). Кроме того, TabSheet 4 содержит ещё компонент GroupBox1 c кнопками btnSort1 и btnSort2 для сортировки списка незавершенных договоров по возрастанию и по убыванию количества членов ВТК.

Рис.1 – Главная форма программы.

1.2 Основные модули и процедуры, входящие в состав программного комплекса

Список модулей:

Программа содержит модуль Unit1 – модуль интерфейсной формы проекта.

Список основных процедур, входящих в состав программного комплекса:

- procedure LoadFromFiles – процедура загрузки данных из файлов в одномерные массивы.

- procedure InitGrids – процедура инициализации таблиц и заполнения их в соответствии с массивами.

- procedure FillArrays – процедура заполнения массивов в соответствии с данными в таблицах.

- procedure SaveInFiles – процедура сохранения данных из массивов в файлы.

- procedure FillNDgrid – заполнение таблицы незавершенных договоров.

- procedure Sort – пирамидальная сортировка таблицы незавершенных договоров NDgrid по возрастанию.

- procedure Sort2– пирамидальная сортировка таблицы незавершенных договоров NDgrid по убыванию.

- procedure SweepRows(r1,r2:word) - замена местами строк в таблице незавершенных договоров NDgrid при сортировке.

- procedure SaveRow(var sr:SRow;r:word) – сохранение замененной строки.

2. Статические данные и структуры

В программе для хранения данных объявлено 5 одномерных строковых массива типа String[N] , где N≤255.

XDar: array [1..70] of String[30];

WTKar: array [1..150] of String[30];

BANKar: array [1..50] of String[30];

SRow=array [0..5] of String[30];

s: array [0..5] of String[30];

Имя массива	Тип	Размер в байтах
XDar	String[N]	(30+1)*70=2170
WTKar	String[N]	(30+1)*150=4650
BANKar	String[N]	(30+1)*50=1550
SRow	String[N]	(30+1)*6=186
S	String[N]	(30+1)*6=186

Кроме того, в программе для временных нужд объявляются переменные:

nCol, i, j, y, x, n, n1, n2, c типа integer (каждая по 4 байта);

l, r типа word (каждая по 2 байта);

st, code, s импа string[30] (каждая по 30+1=31 байт).

2. Логические структуры данных

Главным элементом и базовой структурой данного проекта являются обычные одномерные строковые массивы XDar, WTKar и BANKar размерностью 70, 150 и 50 соответственно.

Объявление массива выглядит следующим образом:

XDar: array [1..70] of String[30];

WTKar: array [1..150] of String[30];

BANKar: array [1..50] of String[30];

Массив (array) – это структура данных. Общим признаком всех массивов всех типов является возможность прямого доступа к их элементам со стороны программы. Эта возможность обеспечивается нумерацией элементов с помощью индекса, который обычно имеет целый тип.

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

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

	0	1	2	…	30
1
2
3
…
70

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

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

	0	1	2	…	30
1
2
3
…
150

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

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

	0	1	2	…	30
1
2
3
…
50

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

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

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

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

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

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

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

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), которую рас-смотрим на следующем примере.