Оглавление

Задание   2

Назначение и область применения разрабатываемой программы    3

Основные возможности и характеристики программы    4

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

Структурная схема фрагмента информационной системы    6

Инструкция по работе с программой   7

Иерархия объектов   14

Таблица имен   15

Листинг самой программы    16

Листинг модуля программы    17

Заключение и выводы    30

Список литературы    31

Задание

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

·              Инициализацию;

·              Добавление новых элементов;

·              Удаление элементов;

·              Перемещение по структуре данных;

·              Поиск элементов структуры данных, отвечающих заданным критериям;

·              Вывод всех элементов структуры данных на экран.

Вариант 1. Склад

Назначение и область применения разрабатываемой программы

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

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

Основные возможности и характеристики программы

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

1) наименование продукта или группы продуктов;

2) его цена;

3) срок годности продукта.

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

Удобный Windows-интерфейс пользователя позволяет удалять продукты, также производить поиск продукта по его имени. При этом на специальной панели выводится вся информация о найденном продукте.

Вся иерархия продуктов автоматически отображается в виде дерева в текстовом поле. Поле перерисовывается после добавления или удаления продукта.

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

Необходимо в среде Borland Delhi 7 создать Windows-приложение, позволяющее выполнять следующие функции:

·              Инициализация глобальных переменных;

·              Добавление новых элементов в предметной области «склад»;

·              Удаление элементов;

·              Перемещение по структуре данных;

·              Поиск элементов структуры данных, отвечающих заданным критериям;

·              Вывод всех элементов структуры данных на экран.

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

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

Структурная схема фрагмента информационной системы

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

Инструкция по работе с программой

Вид программы после запуска:

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

После нажатия кнопки «Инициализация» внешний вид программы примет следующий вид:

Теперь программа готова к работе.

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

После нажатия на кнопку «Добавить» продукт будет добавлен.

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

Если в списке не выбрана группа продуктов, к которой мы добавляем продукт, то появляется следующее сообщение:

Если указанное вами название продукта уже имеется в списке продуктов, то появляется следующее сообщение:

Если вы не указали название продукта, то появляется следующее сообщение:

Внешний вид программы до добавления первого продукта:

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

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

Теперь добавим еще одну группу продуктов в корень

Теперь добавим еще два вида продуктов к группе продуктов «Апельсины».

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

Добавим еще несколько продуктов:

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

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

После чего нажать кнопку «Поиск». Текстовые поля ниже заполнятся найденными данными:

Для удаления какого-либо продукта или группы продуктов необходимо выбрать в списке этот продукт или группу:

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

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

Иерархия объектов

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

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

Таблица имен

В нашей программе мы используем одну глобальную переменную «nachalo», которая по сути является указателем на начало связанного списка. Эта переменная l указывает на объект созданного нами типа node. Приведем описание имен его переменных:

·              Name: название продукта;

·              Price: цена продукта;

·              Srok: срок годности продукта;

·              Belongto: указатель на объект такого же типа, к которому принадлежит данный объект. Для корня этот указатель равен nil;

·              Next: указатель на объект такого же типа, идущий в связанном списке после данного объекта. Для последнего элемента списка он равен nil;

·              Left: указатель на объект такого же типа, стоящий на уровне объекта слева от него. Если слева нет объектов, то он равен nil;

·              Right: указатель на объект такого же типа, стоящий на уровне объекта справа от него. Если справа нет объектов, то он равен nil;

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

Листинг самой программы

program Sklad;

uses

  Forms,

  Unit1 in 'Unit1.pas' {Form1};

{$R *.res}

begin

  Application.Initialize;

  Application.CreateForm(TForm1, Form1);

  Application.Run;

end.

Листинг модуля программы

unit Unit1;

interface

uses

  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

  Dialogs, StdCtrls, ExtCtrls;

type

  TForm1 = class(TForm)

    Edit1: TEdit;

    ComboBox1: TComboBox;

    Button1: TButton;

    Label1: TLabel;

    Label2: TLabel;

    Button2: TButton;

    Memo1: TMemo;

    ComboBox2: TComboBox;

    Button3: TButton;

    Edit2: TEdit;

    Edit3: TEdit;

    Label3: TLabel;

    Label4: TLabel;

    ComboBox3: TComboBox;

    Button4: TButton;

    Label5: TLabel;

    Label6: TLabel;

    Label7: TLabel;

    Edit4: TEdit;

    Label8: TLabel;

    Edit5: TEdit;

    Label9: TLabel;

    Edit6: TEdit;

    Bevel1: TBevel;

    Bevel2: TBevel;

    Bevel3: TBevel;

    procedure Button2Click(Sender: TObject);

    procedure Button1Click(Sender: TObject);

    procedure FormClose(Sender: TObject; var Action: TCloseAction);

    procedure Button3Click(Sender: TObject);

    procedure Button4Click(Sender: TObject);

  private

    { Private declarations }

  public

    { Public declarations }

  end;

type

  link=^node;

  node=record

    name:string[255];

    price:string[255];

    srok:string[255];

    belongto:link;

    next:link;

    first:link;

    left:link;

    right:link;

  end;

var

  Form1: TForm1;

  nachalo:link;

implementation

{$R *.dfm}

procedure init;

begin

  new(nachalo);

  nachalo^.name:='\';

  nachalo^.belongto:=nil;

  nachalo^.next:=nil;

  nachalo^.first:=nil;

  nachalo^.left:=nil;

  nachalo^.right:=nil;

  Form1.ComboBox1.Items.Add(nachalo^.name);

end;

function lastleft(p:link):link;{возвращает указатель на последний принадлежащий p узел}

var q:link;

check:boolean;

begin

  q:=nachalo;

  check:=false;

  if p^.first=nil then

  begin

    lastleft:=nil;

    exit;

  end;

  q:=p^.first;

  lastleft:=nil;

  repeat

    if q^.right=nil then check:=true;

    lastleft:=q;

    if q^.right<>nil then q:=q^.right;

  until check;

end;

procedure addto(p:link;s,s1,s2:string);

var q,left:link;

begin

  new(q);

  q^.name:=s;

  q^.price:=s1;

  q^.srok:=s2;

  q^.belongto:=p;

  left:=lastleft(p);

  q^.left:=left;

  q^.right:=nil;

  if left<>nil then left^.right:=q

  else p^.first:=q;

  q^.next:=p^.next;

  p^.next:=q;

  Form1.ComboBox1.Items.Add(s);

  Form1.ComboBox2.Items.Add(s);

  Form1.ComboBox3.Items.Add(s);

end;

function makespace(n:integer):string;

var m:integer;

var s:string[255];

begin

  s:='';

  for m:=1 to n do

  begin

    s:=s+' ';

  end;

  makespace:=s;

end;

procedure showtree(p:link;space:integer);

var q:link;

begin

  Form1.Memo1.Lines.Add(makespace(space)+p^.name);

  if p<>nil then q:=p^.first;

  if q<>nil then showtree(q,space+3);

  if p^.right<>nil then showtree(p^.right,space);

end;

procedure TForm1.Button2Click(Sender: TObject);

begin

  Label1.Enabled:=true;

  Label2.Enabled:=true;

  Label3.Enabled:=true;

  Label4.Enabled:=true;

  Label5.Enabled:=true;

  Label6.Enabled:=true;

  Label7.Enabled:=true;

  Label8.Enabled:=true;

  Label9.Enabled:=true;

  Edit1.Enabled:=true;

  Edit2.Enabled:=true;

  Edit3.Enabled:=true;

  Edit4.Enabled:=true;

  Edit5.Enabled:=true;

  Edit6.Enabled:=true;

  ComboBox1.Enabled:=true;

  ComboBox2.Enabled:=true;

  ComboBox3.Enabled:=true;

  Memo1.Enabled:=true;

  Button1.Enabled:=true;

  Button2.Enabled:=false;

  Button3.Enabled:=true;

  Button4.Enabled:=true;

  init;

end;

function find(s:string):link;

var q:link;

check:boolean;

begin

  q:=nachalo;

  check:=false;

  repeat

    if q^.next=nil then check:=true;

    if q^.name=s then

    begin

      find:=q;

      exit;

    end;

    q:=q^.next;

  until check;

  find:=nil;

end;

function findincombo(combo:TComboBox;s:string):integer;

var n:integer;

begin

  findincombo:=-1;

  for n:=1 to combo.Items.Count do

  begin

    if combo.Items[n-1]=s then

    begin

      findincombo:=n-1;

      exit;

    end;

  end;

end;

procedure TForm1.Button1Click(Sender: TObject);

var q:link;

begin

  if findincombo(Form1.ComboBox1,Form1.ComboBox1.text)=-1 then

  begin

    ShowMessage('Необходимо выбрать товара или группу товаров из списка, к которой необходимо добавить товар.');

    abort;

  end;

  if edit1.text='' then

  begin

    ShowMessage('Название продукта (группы продуктов) не может быть пустым.');

    abort;

  end;

  if findincombo(Form1.ComboBox1,edit1.text)<>-1 then

  begin

    ShowMessage('Название продукта (группы продуктов) должно быть уникальным.');

    abort;

  end;

  q:=find(combobox1.text);

  if q<>nil then addto(q,Edit1.text,Edit2.text,Edit3.text);

  Edit1.Clear;

  Edit2.Clear;

  Edit3.Clear;

  Memo1.Lines.Clear;

  showtree(nachalo,0);

end;

procedure TForm1.FormClose(Sender: TObject; var Action: TCloseAction);

begin

  dispose(nachalo);

end;

function prev(p:link):link;{ищет то, для чего p next}

var q:link;

check:boolean;

begin

  q:=nachalo;

  check:=false;

  prev:=nil;

  repeat

    if q^.next=nil then check:=true;

    if q^.next=p then

    begin

      prev:=q;

      exit;

    end;

    q:=q^.next;

  until check;

end;

function dependson(p:link):link;{ищет то, что чего p first}

var q:link;

check:boolean;

begin

  q:=nachalo;

  check:=false;

  dependson:=nil;

  repeat

    if q^.next=nil then check:=true;

    if q^.first=p then

    begin

      dependson:=q;

      exit;

    end;

    q:=q^.next;

  until check;

end;

procedure delete(p:link);

var q,ne,pr,le,ri,fi:link;

begin

  q:=p^.first;

  if q<>nil then delete(q);

  if p^.right<>nil then delete(p^.right);

  ne:=p^.next;

  pr:=prev(p);

  le:=p^.left;

  ri:=p^.right;

  fi:=dependson(p);

  if ne<>nil then pr^.next:=ne;

  if (ri<>nil) and (le<>nil) then

  begin

    le^.right:=ri;

    ri^.left:=le;

  end;

  if (ri=nil) and (le<>nil) then

  begin

    le^.right:=nil;

  end;

  if (le=nil) and (ri<>nil) then

  begin

    fi^.first:=ri;

  end;

  if (le=nil) and (ri=nil) then

  begin

    fi^.first:=nil;

  end;

end;

procedure generatecombobox(combo:TComboBox;l:boolean);

var q:link;

check:boolean;

begin

  combo.Items.Clear;

  combo.Text:='';

  q:=nachalo;

  check:=false;

  repeat

    if q^.next=nil then check:=true;

    combo.AddItem(q^.name,Form1);

    q:=q^.next;

  until check;

  if l<>true then combo.Items.Delete(0);

end;

procedure TForm1.Button3Click(Sender: TObject);

var q:link;

begin

  if findincombo(Form1.ComboBox2,Form1.ComboBox2.text)=-1 then

  begin

    ShowMessage('Необходимо выбрать из списка что необходимо удалить.');

    abort;

  end;

  q:=find(ComboBox2.text);

  delete(q);

  generatecombobox(combobox1,true);

  generatecombobox(combobox2,false);

  generatecombobox(combobox3,false);

  Memo1.Lines.Clear;

  showtree(nachalo,0);

end;

procedure TForm1.Button4Click(Sender: TObject);

var q:link;

begin

  if findincombo(Form1.ComboBox3,Form1.ComboBox3.text)=-1 then

  begin

    ShowMessage('Необходимо выбрать из списка название продукта (группы продуктов).');

    abort;

  end;

  q:=find(combobox3.text);

  Edit4.Text:=q^.name;

  Edit5.Text:=q^.price;

  Edit6.Text:=q^.srok;

end;

end.

Заключение и выводы

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

Таким образом, с поставленной задачей созданная программа справляется.

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

Список литературы

1)          “Информатика. Учебник для ВУЗов”. Под ред. Макаровой Н. В. Москва. Издательство “Финансы и статистика”. 1997 г.

2)          “Курс правовой информатики”. Гаврилов О. А. Москва. Издательство “ИНФРА-М”. 2000 г.

3)          “Информатика”. В. А. Острейковский. Москва. Издательство “Высшая школа”. 1999 г.

4)          “Информационные технологии. Учебное пособие”. Под ред. А. К. Волкова. Москва. Издательство “Инфра-М”. 2001 г.

5)          Информационные технологии управления: Учебное пособие. Под редакцией Ю.М. Черкасова. М. ИНФРА-М, 2000 г.

6)          Эбнер М. Delphi 5. Руководство разработчика: Пер. с нем.-К.: Издательская группа BHV, 2003.-480 с., ил.

7)          Архангельский А. Я. Программирование в Delphi 7.-М.: ЗАО «Издательство БИНОМ», 2003.-768 с., ил.

8)          Организация работы с документами: Учебник под ред. Кудряева В.А. М.: Инфра-М, 1998.

9)          Алгоритмы и структуры данных. Н. Вирт. Москва. Мир. 2001 г. 352 стр.

10)     Структуры данных и алгоритмы. А. Ахо. Д. Э. Хопкрофт. Д. Ульман.  Москва. ИД «Вильямс». 2001 г. 384 стр.