Автоматизация работы с базами данных

метки: Данные, Работа, Автоматизация, Курсовой, Дерево, Переменный, Процедура, Компонент

работ по хранению и обработки больших объемов информации, контролю и планированию деятельности средствами ЭВМ. То есть автоматизировать многие информационные процессы, организовать эффективную работу.

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

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

Целью данной работы является разработка программы средствами Turbo Pascal для автоматизации процесса работы с небольшими БД. Для наиболее эффективного использования ресурсов ЭВМ и обеспечения хорошей скорости обработки данных необходимо использовать динамические структуры данных.

1. Постановка задачи

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

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

Содержательная постановка задачи содержит разнообразную информацию о задаче, а именно следующие пункты:

• а) словесное (словесно-формульное) описание содержания (условия) задачи;
• б) перечень исходных величин и результатов решения задачи с указанием единиц измерения и точности вычисления;
• в) форма представления результатов (эскиз вывода результатов);

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

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

Вариант 18. «Отдел кадров»

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

Мотивация как один из методов управления эффективностью работы персонала

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

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

Реализовать следующие операции для пользователя:

1) добавление нового работника;

2) удаление работника;

3) поиск по фамилии, должности, дате рождения;

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

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

Свойства математической постановки задачи:

• а) модель объекта не тождественна реальному объекту, а передает только часть его свойств и качеств, являясь приближенным описанием реального объекта;
• б) модель объекта задачи не определяется однозначно реальным объектом (для одной и той же задачи можно принять разные модели в зависимости от требуемой точности вычисления результатов);
• в) для любой выбранной модели объекта необходимо доказать соответствие ее реальному объекту (ситуации), то есть доказать адекватность модели и реального объекта с точки зрения требуемой точности вычисления;
• г) в случае приближенной модели объекта результаты решения задачи также являются приближенными.

В общем, можно выделить следующие пункты математической постановки задачи:

• а) формулировка постановки задачи, то есть формулировка ее как задачи некоторой науки;
• б) выбор модели объекта задачи, то есть выбор совокупности математических объектов, отражающих все необходимые свойства реальных объектов, процессов, ситуаций задачи (модель может быть числовой, геометрической, графической, аналитической и так далее);

• в) установление адекватности (соответствия) выбранной модели реальному объекту с точки зрения требуемой точности вычисления результатов;
• г) выделение исходных данных и результатов задачи как параметров модели;
• д) выявление математических соотношений, связывающих исходные данные и результаты решения задачи и определяемых свойствами модели (могут быть выражены формулами, уравнениями, неравенствами, системами уравнений и так далее).
  7 стр., 3461 слов

  Математическая модель системы автоматического управления температурой ...

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

Формализация задачи (выбор метода решения) — это преобразование задачи, полученной на этапе математической постановки, к такой задаче, которая вписывается в рамки языка программирования. Этот процесс выполняется за два шага:

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

Задание на выполнение работы предусматривает написание программы хранения и обработки (конкретно, поиска, добавления, удаления) информации без каких-либо расчетов, то есть работа с простой БД. В сущности, для решения такой задачи не предусматривается построение математической модели (отдельные модели могут использоваться при описании отдельных частных алгоритмов для подзадач в рамках задачи), следовательно, отсутствует математическая постановка задачи.

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

Способы хранения, представления и обработки данных рассматриваются в соответствующих пунктах раздела «5. Описание программы».

Описание используемой динамической структуры, понятия, термины, принципы работы с ней рассматриваются в разделе «4. Сведения о методе решения».

Краткое описание средства разработки и другого используемого программного обеспечения приводится в разделе «3. Программное обеспечение».

программа паскаль база данные

2. Состав аппаратного обеспечения

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

• Процессор — Intel Core 2 Quad Q6600, 2400 MHz
• Материнская плата — ChainTech, чипсет — Intel 815 со встроенной звуковой картой CMI 8738;
• ОЗУ — 1024 МB;
• Видеокарта — nVIDIA GeForce 8600 GT 1024 MB;
• Жесткий диск — Seagate Barracuda ATA V 7200, 250 GB 7200 rpm;
• Монитор — LG Flatron ezT717B;
• Клавиатура;
• Мышь.

Так как средством разработки является универсальный язык программирования Turbo Pascal 7.0, который предусматривает написание программ под DOS, понятно, что предъявляемые требования к аппаратуре весьма незначительные. Данный язык программирования можно использовать практически на любой модели персонального компьютера (например, Intel 80286).

Таким образом, используемое аппаратное обеспечение не имеет принципиального значения, программа должна работать на любом IBM совместимом компьютере, на котором возможно запустить Turbo Pascal 7.0, под управление операционной системы MS-DOS (начиная с версии 5.0).

Решение задач с использованием системы MathCAD и Scilab

... программирования и команд операционной системы. В данной курсовой работе требуется проанализировать как влияет изменение параметров на электрическую цепь второго порядка используя системы компьютерной математики(СКМ) - MathCad и Scilab ... анализа ММ, в разработке эффективного алгоритма вычислительного эксперимента, а пятый этап - в создании работоспособной программы, реализующей этот алгоритм ...

3. Программное обеспечение

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

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

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

2) Утилиты — программы вспомогательного назначения. Например, программы тестирования и диагностики компьютера, антивирусные программы, программы архивации и т.д.

3) Сервисные программы — программы облегчающие взаимодействие пользователя с ОС.

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

1) Текстовые редакторы — предназначены для создания и оформления текстовой и другой информации.

2) Графические редакторы — предназначены для создания и обработки графической информации.

3) Электронные таблицы — предназначены для создания и обработки табличной информации, организации в них вычислений.

4) Учебные программы — используются для организации учебного процесса или изучения какого-либо материала.

5) Игровые программы — для организации досуга. Одна из движущих сил популярности и в свое время быстрого развития персональных компьютеров.

6) Деловые программы — используются для обработки деловой информации, организации делопроизводства.

7) Интегрированные системы — состоят из различных видов прикладного ПО и используются для решения целого класса задач. Ярким примером является MS Office.

8) Инструментальные средства разработки приложений — это программные комплексы, используемые программистами для создания других программ и автоматизированных систем. В свою очередь инструментальные средства разработки классифицируют и делят на типы: языки программирования высокого и низкого уровня; процедурные, объектно-ориентированные и логические языки программирования (ЯП); машинозависимые и машинонезависимые ЯП и так далее.

3.1 Операционная система

Операционная система (ОС) — основная программа, предназначенная для управления компьютером и взаимодействия с прикладными программами. ОС первая загружается в компьютер и выполняет множество функций, таких как запись и считывание информации, хранение данных, осуществление взаимодействия аппаратных устройств, обеспечение выполнения прикладных программ. Наиболее распространенные ОС — MS-DOS, Windows, Unix, OS/2 (для каждой ОС существуют различные версии, появляющиеся вследствие развития информационных и компьютерных технологий).

Конструирование программ

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

Для ОС определяется достаточно большое количество характеристик, некоторые из которых:

• поддержка многозадачности — возможность выполнения компьютером параллельно нескольких задач;
• поддержка многопользовательского режима — определяется числом работающих пользователей одной ОС и т.д.

Разработка программы велась под управлением ОС семейства Windows, каждая версия из которых имеет свои достоинства и недостатки. Например, главными достоинствами всех ОС Windows является многозадачность, удобный интерфейс пользователя (GUI, Graphics User Interface), простота в использовании для решения различного вида задач, большого количества прикладного ПО для данной платформы. Для программиста — большое количество разнообразных языков программирования, объектно-ориентированная реализация ОС. Некоторые версии (Windows NT/2000) имеют большое количество средств для организации сетевой работы, в том числе поддержка многопроцессорной обработки для выделенных серверов, повышенную надежность и безопасность.

В принципе для разработки программы достаточно ОС MS-DOS 5.0. ОС Windows совместима с MS-DOS и в ней поддерживается работа Turbo Pascal 7.0, что достаточно для написания программы и анализа ее работы.

3.2 Средство разработки

Для решения задачи используется язык программирования (ЯП) Turbo Pascal 7.0. Данный ЯП является универсальным и предназначен для решения широкого круга задач. Рассмотрение алфавита, операторов, конструкций языка и других, связанных с ним элементов занимает целые книги. Поэтому в работе приведем только основные понятия и используемые в ходе разработки программы конструкции языка.

ЯП Паскаль разработан Никлаусом Виртом в начале 70-х годов. Имеет достаточно большой набор инструментов для решения любых задач, удобную систему программирования и хорошие средства отладки программы. На основе элементов и конструкций языка создано визуальное средство разработки (проектировании) программ — Delphi, которое является одним из самых популярных средств разработки на сегодняшний день.

Общая схема структуры Паскаля приведена на рисунке 1.

Рис. 1. Структура ЯП Паскаль

В ходе решения поставленной задачи использовались многие элементы языка. Кратко рассмотрим основные и наиболее сложные используемые конструкции Turbo Pascal.

Данные. Типы данных

Все переменные в Turbo Pascal должны быть определены перед их использованием. Для этого в структуре программы используется раздел объявления переменных, начинающийся с зарезервированного слова VAR. При объявлении переменных необходимо указывать их тип. Тип может быть стандартным или пользовательским. Так для описания компонент динамической структуры и типизированного файла, указателя на компоненту динамической структуры описывался пользовательский тип в разделе описания типов (начинается с зарезервированного слова TYPE) в пользовательском модуле Trees.

Используемые в программе пользовательские типы и переменные с соответствующими типами данных и их назначениями рассматриваются в разделе «5. Описание программы». Также их назначение прокомментировано в тексте программы.

Программы системы 1С: Предприятие. Администрирование в программах ...

... программ 1С: Предприятие является возможность изменения конфигурации самим пользователем или организациями, специализирующимися на внедрении и поддержке программных продуктов фирмы "1С". ... Дополнительные возможности системы Разнообразные возможности настройки конфигурации Работа с распределенными ... при временном прекращении работы. 1С: Зарплата и Кадры 7.7 (Компонента «Расчет») Программа "1С: ...

Операторы

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

1) Простые операторы — не содержат в себе других операторов.

Оператор присваивания — выполняет присваивание переменной или функции (внутри тела функции) значения вычисленного выражения. Формат:

• <идентификатор>
• := <выражение>;

• Оператор обращения к процедуре (процедурный оператор) — представляет вызов стандартной или ранее описанной пользовательской процедуры в отдельном предложении. Формат:
• <идентификатор>[(<список фактических параметров>)];

2) Структурные (сложные, составные) операторы — операторы, которые состоят из других операторов.

Составной оператор — представляет собой совокупность последовательно выполняемых операторов, заключенных в операторные скобки:

begin

<оператор1>;

• <операторN>

• end;

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

Условный оператор IF — реализует алгоритмическую конструкцию «ветвление» и изменяет порядок выполнения операторов в зависимости от истинности или ложности некоторого условия. Существует две формы оператора:

• полная:
• if <условие>
• then <оператор1>
• else <оператор2>;

• неполная:
• if <условие>
• then <оператор>;

• Условие представляет собой вычисляемое логическое выражение.

Условный оператор CASE — с помощью этого оператора можно выбрать один вариант из любого их количества. Структура оператора:

• case <выражение>
• of

<список_значений_1> : <оператор1>;

• <список_значений_N>
• : <операторN>;

• [else <оператор>;]

end;

— Ветвь else не является обязательной, если она отсутствует, выражение не совпадает ни с одним из перечисленных значений весь оператор рассматривается как пустой. Если для нескольких значений необходимо выполнить одни и те же действия, то их можно перечислить через запятую в списке значений или указать диапазон.

Оператор цикла REPEAT — организует выполнение цикла, состоящего из любого числа операторов, с неизвестным заранее числом повторений. Цикл относится к виду циклов с постусловием, следовательно, тело цикла хоть раз выполнится. Выход из цикла осуществляется при истинности некоторого логического выражения. Формат оператора:

Repeat

<оператор1>;

• <операторN>;

• Until <условие>;

— Оператор цикла WHILE — организует выполнение одного оператора неизвестное заранее количество раз. Выход из цикла осуществляется, если некоторое логическое выражение окажется ложным. Цикл относится к циклам с предусловием, а, следовательно, тело цикла может ни разу не выполниться. Формат оператора:

Производственный менеджмент : «Планирование производственной ...

... А.Н.», предложено планирование безубыточной деятельности предприятия 3 Глава I . Планирование производственной деятельности предприятия 1.1. Планы предприятия и их виды Функционирование любого предприятия подразумевает взаимодействие и совместную работу нескольких звеньев (людей, отделов, ...

• While <условие>
• do <оператор>;

• Оператор цикла FOR — организует выполнение одного оператора заранее известное число раз.

Имеется два вида данного цикла:

• for <пер>
• := <нач_знач>
• to <кон_знач>
• do <опер>;

• for <пер>
• := <нач_знач>
• downto <кон_знач>
• do <опер>;

• Начальное и конечное значения должны быть порядкового типа и совместимы с типом переменной. Цикл действует следующим образом. Первоначально вычисляются и запоминаются начальное и конечное значения, после чего переменная сравнивается с конечным значением. Далее, пока переменная цикла меньше или равна конечному значению (для первого вида) или больше или равна (для второго вида), выполняется очередная итерация цикла, в противном случае происходит выход из цикла. Выполнение очередной итерации включает в себя выполнение оператора и увеличение (для первого вида) или уменьшения (для второго вида) значения переменной на минимальное значение для данного порядкового типа. После выхода из цикла переменная имеет неопределенное значение. Если минимальное значение для первого вида цикла будет больше максимального, тогда цикл ни разу не выполнится;
• и для второго вида — наоборот. За исключением, когда выход был осуществлен с помощью оператора GOTO или стандартной процедуры BREAK.

Оператор присоединения WITH — используется для упрощения работы с составными именами (например с записями).

Все идентификаторы внутри оператора также рассматриваются как поля записи, для этого к ним средой добавляется идентификатор после WITH. Формат:

• With <идетификатор>
• do <оператор>;

Ввод/вывод

Для организации диалога с пользователем используются стандартные средства Turbo Pascal и объекты стандартной библиотеки — модуля CRT.

Ввод осуществляется в программе с клавиатуры и из файла. Вывод на экран и в файл. В Turbo Pascal операции ввода/вывода независимо от направления выполняются стандартными процедурами write (вывод, запись) и read (ввод, чтение).

Если ввод/вывод осуществляется в файл, то в качестве первого фактического параметра должна быть файловая переменная, связанная с физическим файлом и открытым на чтение или запись. Формат данных процедур следующий:

• Write[([<файловая переменная>],<выражение>[,…])];

• Writeln[([<файловая переменная>],<выражение>[,…])];

• Read[([<файловая переменная>],<идентификатор>[,…])];

• Readln[([<файловая переменная>],<идентификатор>[,…])];

• Процедуры с окончанием ln выполняют те же действия, однако после выполнения процедуры осуществляется переход на новую строку (writeln) или ожидается ввод с новой строки (readln).

Вследствие того, что ввод для различных направлений (клавиатура и файл) выполняется одинаково удобно использовать средства Turbo Pascal для организации корректного ввода. Так директива компилятору (ключ компиляции) {$I-} отключает системную проверку правильности ввода/вывода, и тогда можно по результатам функции IOResult программно анализировать результат выполнения последней операции ввода/вывода. После анализа можно восстановить системную проверку директивой {$I+}, то есть, как бы операцию ввода/вывода ограничить данными ключами компиляции. Неоднократный пример такого приема можно посмотреть по тексту программы при вводе табельные номера. Когда на приглашение ввести значение типа word вводится вещественное число или строка, программа запрашивает повторный ввод, и не выводится сообщение о системной ошибке.

Создание базы данных строительной организации

... наличие инструментальных средств разработки прикладных программ. Производительность СУБД оценивается:временем выполнения запросов;скоростью поиска информации;временем импортирования баз данных из других форматов;скоростью выполнения операций ... как организовано хранение данных, он работает с такой базой, как с централизованной. Глава 2. База данных «Строительное предприятие» Любая организационная ...

Для работы с типизированным файлом используются стандартные процедуры и функции Turbo Pascal перечисленные ниже.

Процедуры

Процедура связывания файловой переменной с физическим файлом:

• Assign(<Имя файловой переменной>,<Имя файла>);

• Процедура открытия файла на чтение/запись, указатель текущей компоненты файла настраивается на начало файла. Если физического файла, соответствующего файловой переменной не существует, то возникает ситуация ошибки ввода-вывода. Формат:
• Reset(<Имя файловой переменной>);

• Процедура открытия нового пустого файла для записи. Если файл существует, то он очищается.

Rewrite(<Имя файловой переменной>);

• После работы с файлом он, как правило, должен быть закрыт. Это требование обязательно должно соблюдаться для файла, в который производилась запись. Для этого используется процедура:
• close(<Имя файловой переменной>);

Функции

Любой файл конечен и продолжать чтение из него информации можно лишь до определенного предела. Проверить, окончен ли файл, можно вызовом стандартной логической функции: Eof(<файловая переменная>) — она вырабатывает значение True, если файл окончен, и False — в противном случае.

IOResult — результат последней операции ввода-вывода. Возвращает 0, если последняя операция ввода/вывода завершилась успешно и другое число — в противном случае.

FilePos(<файловая переменная>) — возвращает номер текущей компоненты файла.

FileSize(<файловая переменная>) — возвращает текущий размер файла.

Для создания резервной копии файла использовались процедуры для работы с файловой системой:

• Erase(<файловая переменная>) — уничтожение внешнего файла, с которым связана файловая переменная.

Rename(<файловая переменная>,<новое имя>) — переименование внешнего файла. Файловая переменная получает новое имя, заданное параметром <новое имя>.

Для организации удобного пользовательского интерфейса в программе использовались подпрограммы модуля CRT:

• clrscr — процедура очистки экрана;
• readkey — функция чтения буфера клавиатуры, если пуст — ожидание нажатия любой клавиши, возвращаемое значение код символа;
• gotoxy(<позиция>,<строка>) — процедура устанавливает курсор в указанное место на экране;
• textcolor(<цвет>) — процедура устанавливает цвет выводимых далее на экран символов.

Работа с памятью

Использование баз данных и СУБД для обработки информации

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

При решении задачи использовалась динамическая память для работы с динамической структурой двоичное дерево поиска. Для выполнения действий с динамической памятью использовались следующие процедуры и функции:

• Процедура New(<указатель>) — выделяет место в динамической области памяти для размещения динамической переменной и ее адрес присваивает указателю.

Процедура Dispose(<указатель>) — освобождает участок памяти, выделенный для размещения динамической переменной процедурой New, и значение указателя становится неопределенным.

Процедура Mark(<указатель>) — записывает в указатель адрес начала участка свободной динамической памяти на момент ее вызова.

Процедура Release(<указатель>) — освобождает участок динамической памяти, начиная с адреса, записанного в указатель процедурой Mark, то есть, очищает ту динамическую память, которая была занята после вызова процедуры Mark.

Также использовались для работы с памятью:

• Процедура Move(<источник>,<приемник>,<размер>) — копирует указанное в третьем параметре количество байтов с адреса источника по адресу приемника. Данная процедура не выполняет никаких проверок, поэтому может приводить к ошибкам. В программе для возможности использования данной процедуры были созданы компоненты дерева и файла одинаковой структуры — компонента дерева в качестве двух последних полей записи содержит поля-указатели на правое и левое поддеревья, а остальные поля компонент идентичны.

Функция SizeOf(<величина>

• возвращает объем в байтах, занимаемый величиной, причем величина может быть либо именем переменной любого типа, либо именем типа.

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

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

Созданный модуль с описанием структуры и элементов в виде комментариев приведен в разделе «6. Текст программы».

4. Сведения о методе решения

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

Дерево как динамическую структуру определяют так: дерево с базовым типом Т — это: 1) либо пустое дерево; 2) либо некоторая вершина (узел) типа Т с конечным числом связанных с ней отдельных деревьев с базовым типом Т, называемых поддеревьями. С точки зрения любого языка программирования, дерево — это динамическая структура данных, состоящая из узлов, каждый из которых содержит, кроме данных, определенное количество ссылок (ветви) на другие деревья. На каждый узел имеется ровно одна ссылка. Начальный узел называется корнем дерева. Узел, не имеющий поддеревьев, называется листом (терминальный узел), а нетерминальные узлы называют внутренними. Исходящие узлы называются предками, входящие — потомками. Узлы, расположенные на соседних уровнях являются непосредственными потомком и предком. Число непосредственных потомков внутреннего узла называют его степенью. Высота (глубина) дерева определяется количеством уровней, на которых располагаются его узлы. Максимальная степень из всех узлов дерева есть степень дерева. Число ветвей или ребер, которые нужно пройти от корня к узлу, называется длиной пути к данному узлу. Корень имеет путь 0, его прямые потомки путь 1 и т.д. Длина внутреннего пути дерева определяется как сумма длин путей для всех его узлов. Длина внешнего пути дерева определяется как сумма длин путей для этого дерева, если бы все узлы имели степень дерева.

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

Сбалансированное дерево — дерево, в котором число вершин в левых и правых поддеревьях отличается не более чем на 1.

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

Бинарное (двоичное) дерево — это динамическая структура данных, состоящая из узлов, каждый из которых содержит, кроме данных, не более двух ссылок на различные бинарные деревья, то есть степень бинарного дерева равна 2 (деревья степени больше двух называют сильно ветвящимися деревьями — multiway tree).

Для деревьев определены следующие операции:

1) включение (добавление) узла в дерево;

2) обход дерева;

3) удаление (исключение) узла;

4) поиск по дереву.

Приведем словесные алгоритмы данных операций на примере используемой в задаче динамической структуры — двоичном дереве поиска.

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

1) Поиск по дереву с включением узла

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

3) Обход дерева

Обход дерева подразумевает посещение всех узлов дерева в определенном порядке. Существует 3 порядка:

• а) Сверху-вниз (preorder) — корень посещается ранее, чем поддеревья;
• б) Слева-направо (inorder) — с самого левого узла;
• в) Снизу-вверх (postorder) — корень посещается после поддеревьев.

В частности, понятно, что вывод в порядке обхода слева-направо выведет упорядоченную по ключу последовательность.

4) Исключение из дерева

Исключение узла из дерева процедура достаточно неоднозначная. Существуют различные приемы удаления узла. Для дерева поиска можно использовать следующий прием:

• а) если узел — лист, то исключение очевидно, для предка удаляем ссылку на данный узел;
• б) если узел имеет не более одного потомка, то для предка узла устанавливаем ссылку на потомка узла;

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

Алгоритмы, реализующие данные операции, в контексте задачи приведены в разделе «5. Описание программы».

5. Описание программы

Язык программирования Turbo Pascal является процедурным языком программирования. Поэтому при разработке программы активно использовались приемы процедурного программирования.

Процедурное программирования — способ программирование с широким использованием подпрограмм (процедур).

Основой метода является использование принципа модульности построения сложных программ, причем каждый программный модуль должен иметь ограниченный объем, выполнять одну специфическую функцию по обработке данных и использовать композиции только трех базовых элементов — линейной, ветвящейся и циклической структур, для описания которых разработаны специальные языковые конструкции. Основная цель структурного программирования — создать программу с минимальными взаимосвязями между ее модулями. Выделяют следующие достоинства процедурного программирования:

• упрощается процесс создания сложных программ;
• уменьшается вероятность появления ошибок;
• использование модулей небольших размеров позволяет упростить и ускорить процесс отладки;
• при использовании процедурного программирования значительно сокращается трудоемкость разработки технической документации.

Кроме того, для решения задачи использовалось как проектирование «сверху-вниз», так и проектирование «снизу-вверх». Оба вида проектирования подразумевают активное использование модулей, процедур и функций.

Проектирование «сверху-вниз» описывает процесс решения задачи от более сложного к более простому — декомпозиция задачи, то есть разбиение задачи на подзадачи и так далее. Это стандартный и очевидный подход, который наиболее часто используется при решении многих задач.

Проектированием «снизу-вверх» обратно выше указанному подходу — заведомо известно, что понадобится решать конкретные элементарные задачи в рамках всей задачи, для которых можно уже на начальном этапе разработать алгоритмы. Использование подходы «снизу-вверх» объясняется тем, что явно понадобятся подпрограммы реализующие операции работы с двоичным деревом поиска. То есть необходимо разработать алгоритмы для выполнения стандартных операций (в нашем случае, включение и удаление узла) и затем в ходе разработки программы, может быть, скорректировать ее содержание или выполнение.

5.1 Описание логической структуры программы

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

Рис. 2. Схема взаимодействия подпрограмм

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

Объекты, используемые в программе, могут быть:

1) глобальные (внешние): объявленные во внешней подпрограмме или программе и не переопределенные в данной;

2) локальные (внутренние): определенные в данной подпрограмме и доступные и используемые только в ней и во всех вложенных в нее блоках или подпрограммах, в которых они не переобъявлены;

— Глобальные объекты доступны в программе, в которой они объявлены, и во всех вложенных в нее подпрограммах, в которых они не переобъявлены. К глобальным объектам относят все объекты (из интерфейсной части) из подключаемой библиотеки. Так как библиотека подключается в начале программы, то можно считать, что ее объекты уже описаны как бы в начале текста программы.

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

Если рассматривать область действия подпрограмм, то можно представить следующую схему уровней вложенности подпрограмм.

Рис. 3. Вложенность подпрограмм

Таким образом, понятно, что из тела программы можно вызвать любую подпрограмму, кроме Delt и Search, так как они локальны — определены внутри других подпрограмм, и существуют только при их работе. Связь по вызовам подпрограмм представлена на рис. 2.

5.2 Описание алгоритма решения задачи

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

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

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

На рис. 4 представлена блок-схема алгоритма программы. В блоках описанные выполняемые на данном этапе действия. Естественно, что в ходе разработке программы они, скорее всего, будут выделены в подпрограммы.

Рис. 4. Укрупненная схема алгоритма программы

Первый этап — чтение из файла и формирование дерева явно реализуется не сложно: чтение по-компонентно из типизированного файла, добавление считанных данных о работнике в дерево. Процесс повторяется пока не конец файла. Вследствие простоты реализации нет смысла приводить алгоритм. Алгоритм добавления в дерево будет рассмотрен далее.

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

При выборе действия «добавление» пользователь вводит данные о добавляемом работнике, далее осуществляется добавление данного работника в дерево. Словесный алгоритм добавления работника в двоичное дерево поиска рассмотрен в разделе «4. Сведения о методе решения». Данный алгоритм подразумевает использование рекурсии. Вследствие того, что алгоритм описывают стандартную операцию для дерева поиска, и рассматривается в любой литературе по динамическим структурам данных, нет смысла приводить описание в виде блок-схемы. Реализующая алгоритм процедура подробно прокомментирована в тексте программы. По этим же причинам не рассматриваются блок-схемы алгоритмов удаления, поиска и обхода двоичного дерева поиска.

При выборе действия «удаление» пользователь вводит табельный номер удаляемого работника. Далее осуществляется поиск по дереву в случае нахождение работника, осуществляется его удаление из дерева поиска, словесный алгоритм которого рассмотрен в разделе «4. Сведения о методе решения».

При выборе действия «поиск» пользователь выбирает критерий поиска: по фамилии, должности или табельному номеру. Затем осуществляется обход дерева слева-направо (словесный алгоритм приведен в разделе «4. Сведения о методе решения») и осуществляется вывод работников, попадающих под условия критерия поиска.

При выборе действия «вывод» осуществляется обход дерева слева-направо с выводом каждого работника.

Третий этап — запись результатов работы в файл. В ходе данного этапа осуществляется обход дерева сверху-вниз с последовательной записью компоненты структуры в типизированный файл.

5.3 Описание входных и выходных данных программы

Назначение программы — введение простой базы данных. Данные при запуске программы читаются из файла Rab.dat. Также после окончания работы программы они записываются в данный файл. Для возможности отмены сохраненных в файл последних изменений ведется копия перезаписываемого файла Rab.tmp.

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

Файл Rab.dat представляет собой с точки зрения Turbo Pascal типизированный файл. Компоненты данного файла представляют собой запись, содержащую информацию о работнике. Структура компоненты типизированного файла описана в виде пользовательского типа-записи в пользовательском модуле Trees, следовательно, данный тип является глобальным, и имеет следующую структуру:

CompF = record

fio : string[40];

• num : word;
• pol : char;
• dat : string[10];

dol : string[40]

end;

Описание полей записи в порядке следования:

• fio — фамилия имя отчество работника;
• num — табельный номер (положительное целое число);
• pol — пол работника (символ «м» или «ж»);
• dat — дата рождения (предполагается запись формата — ДД.ММ.ГГГГГ);
• dol — должность;

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

Также для проведения анализа работы программы, распределения памяти и хранения данных необходимо оценить размер хранимой информации о каждом работнике, то есть знать размер отдельной компоненты типизированного файла или, что то же самое, знать размер типа записи. Такую информацию можно определить стандартной функцией SizeOf (упоминалась выше): SizeOf(CompF) = 103 Бт.

Данный размер складывается исходя из необходимых размеров для полей. Необходимо помнить, что реально для хранение строк выделяется на 1 байт больше (string[40] — 41 Бт).

Таким образом, можно утверждать, что если в файл записана информация о 100 работниках, то размер файла будет равен: 100 х 103 Бт = 10300 Бт.

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

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

• pTree = ^Tree;

Tree = record

fio : string[40];

• num : word;
• pol : char;
• dat : string[10];
• dol : string[40];

left, right : pTree

end;

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

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

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

{$M 65520,111000,655360},

где :

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

— Второй параметр указывает минимальный размер свободной динамической памяти (кучи), при котором можно выполнять программу. Исходя из значения данного параметра, можно сделать вывод, что если размер кучи будет менее 111000 Бт, то программа не будет запускаться на выполнение. Данное значение выбрано в расчете для работы с деревом из 100 узлов по 111 Бт каждый.

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

Для чтения и записи данных в файл используются стандартные процедуры ввода/вывода и работы с файлами и файловой системой, которые оговаривались в разделе «3. Программное обеспечение».

5.4 Описание подпрограмм

Используемые в программе, расположенные как в самой программе (Rab.pas), так и в пользовательском модуле (trees.pas), подпрограммы упоминались при описании логической структуры программы и хорошо прокомментированы в тексте программы. Поэтому ограничимся перечислением существующих подпрограмм с описанием их назначения и рассмотрением особенностей работы.

Пользовательский модуль trees.pas:

• Procedure print(v : pTree);
• Процедура вывода содержимого компоненты двоичного дерева поиска. Формальный параметр — указатель на компоненту.
• Procedure add(var x : CompF;
• var p : pTree);

— Рекурсивная процедура добавления компоненты в двоичное дерево поиска. Метод — поиск по дереву поиска по ключу и добавление компоненты-листа. Формальные параметры: запись с данными о работнике и указатель на корень. Ключ, по которому осуществляется поиск — поле num первого формального параметра — записи с данными о работнике. Данные параметр является формальным параметром-переменной (секция var), то есть ссылкой на фактический параметр-переменную. Данный прием объясняется следующим образом. При рекурсии возможна большая рекурсивная вложенность вызовов. Передача в качестве параметра-значения может привести к переполнению стека, так как на каждом вызове в стеке для данного будет параметра сохраняться 103 Бт. При использовании параметра-переменной в стеке сохраняется 4 Бт. Экономия очевидна и составляет на каждом вызове 99 Бт.

• Procedure del(x : word;
• var p : pTree);

• Рекурсивная процедура удаления компоненты из двоичного дерева поиска. Метод — поиска по дереву узла;
• если лист или имеет одно поддерево, то удаление с восстановлением связей;
• если два поддерева — поиск в левом поддереве крайнего правого узла с одним поддеревом, его удаление с предварительной записью его данных в удаляемый узел. Формальные параметры: табельный номер и указатель на корень. При условии нахождения работнике выводится информация о нем посредством вызова процедуры Print и выдается запрос о подтверждении удаления. Для поиска крайнего правого узла с одним поддеревом в случае удаления узла с двумя поддеревьями используется вложенная процедура procedure delt(var r : pTree).

  Это также рекурсивная процедура, имеющая в качестве формального параметра указатель на компоненту дерева.

Основная программа rab.pas:

• Procedure AddRab;
• Процедура добавления работника. В ней осуществляется ввод данных о новом работнике, затем вызывается процедура включения в дерево поиска add.
• Procedure DelRab;
• Процедура удаления работника. В процедуре осуществляется ввод табельный номер удаляемого работника, затем вызов процедуры исключения компоненты из дерева del.
• Procedure SearchRab;

— Процедура организации поиска и отбора работников по критерию. Метод — обход дерева слева-направо с анализом критерия поиска и, в случае необходимости, вывод на экран. При вызове данной процедуры запрашивается критерий поиска: по фамилии, должности, табельному номеру. Далее осуществляется обход дерева слева-направо с помощью вложенной рекурсивной процедуры Procedure Search(t : pTree).

При проверке критерия поиска используются глобальные по отношению к процедуре переменные с, tmps и tmpc. Для поиска по фамилии и группе используется поиск подстроки (ключ поиска) в строке. Таким образом, происходит вывод с фильтраций по совпадающему ключу. То есть при поиске по номеру группы будут выводиться все работники заданной группы. Или, например, при указании в качестве ключа поиска фамилии «Иванов» будут выводиться все работники, у которых в поле fio есть подстрока «Иванов» (Иванова, Иванович, Ивановна и т.д.).

• procedure PrintRab(r : pTree);

— Рекурсивная процедура обхода дерева поиска слева-направо с выводом данных о работнике посредством вызова процедуры Print. Для дерева поиска выводится в порядке, отсортированном по ключу, в нашем случае выводится отсортированный список работников по табельному номеру.

• Procedure LoadOfFile;
• Процедура загрузки данных из файла после запуска программы с добавлением считанных данных в дерево поиска посредством вызова процедуры Add.
• Procedure SaveToFile(t : pTree);

— Рекурсивная процедура записи компонент дерева в файл. Метод — обход дерева сверху-вниз с организацией записи компоненты дерева в файл. Метод обхода слева-направо не рекомендуется использовать, так как в файл запишется отсортированная по табельным номерам последовательность работников. При последующем запуске программы чтение осуществляется отсортированной последовательности, следовательно, дерево поиска будет иметь в каждом узле только правое поддерево, то есть получится обычный список. Что приведет к неэффективности использования динамической структуры.

• Procedure Menu;
• Процедура организации диалога с пользователем. Пользователь осуществляет выбор действия, в зависимости от выбранного действия осуществляется вызов соответствующей процедуры.

5.5 Перечень допустимых значений входных данных и проверочные

тестовые примеры

Так как входные данные могут формироваться только самой программой, то, если не будет вмешательство в содержимое файла Rab.dat, данные будут всегда корректно считываться из файла. Если файл будет отсутствовать в каталоге, из которого запущена программа, или просто-напросто файл не будет найден (необходимо учитывать переменные окружения ОС — команда path), то программа сама создаст пустой файл. Все вводимые значение в процессе выполнения программы анализируется на корректность ввода. Таким образом, практически исключено возникновение ошибочных ситуаций. Единственно, в программе не учтены возможные ошибки работы с динамической памятью, так как предполагается использование программы для небольшого количества работников. Данные ситуации потенциально могут возникать при выделении динамической памяти процедурой New. Тогда перед выделением можно функцией MaxAvail определить размер самого большого свободного участка динамической памяти, если он больше размера компоненты дерева (111 Бт), тогда использовать процедуру New.

При тестировании программы вводились различные данные и выполнялись различные операции пользователя. В ходе тестирования были выявлены и устранены различные ошибки. Для выявления ошибок также использовались стандартные средства отладки среды Turbo Pascal.

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