Структуры данных. 2

Содержание 
 

 

 

Задание 

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

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

ЗАДАНИЕ –  склад

 

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

     Программа, предназначена для ведения списка товаров на складе (вставки, удаления, редактирования, сортировки, поиска).

     О каждом наименовании товара, программа имеет следующую информацию :

• Артикул
• Наименование
• Количество
• Единица измерения
• Место хранения

 

     Существует  возможность сортировки списка товаров по артикулу или наименованию, а так же поиска по артикулу..

     Программа написана на языке C++ в среде визуального программирования Builder C++ фирмы Borland.

 

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

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

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

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

 

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

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

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

     Вместе  с тем связное представление  не лишено и недостатков, основные из которых:

• на поля связок расходуется дополнительная память;
• доступ к элементам связной структуры может быть менее эффективным по времени.

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

     1. Очередь FIFO (первым зашел, первым вышел)

     2. Очередь LIFO (первым зашел, последним вышел)

     3. Стек

     4. Линейный список

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

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

     

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

 

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

 

 

     Таблица имен 
 

     Рассмотрим  поля структуры с информацией о товаре (файл tovar.hpp). 
 

//Структура  с информацией  о товаре

struct  tovar{

public:

String Art;    // артикул

String Name;   // наименование

int Kol;       // количество на  складе

String Ed;     //единица измерения

String Pls;    // место хранения 

}; 

     Далее приведем имена структуры узла списка и класса  - списка товаров. (файл tovarlst.hpp) 
 
 

//Структура  - узел списка 

struct unit 

{

tovar a;

unit *nt;//ссылка на  след. элемент

}; 

//список пациентов 

class tovarlst{

private:

unit *f;  //начало

unit *e;  //конец

int size; //размер 

public:

tovarlst(); //конструктор

~tovarlst(); //деструктор

void Add(tovar);     //вставка в конец

void Delete(int);         //удаление элемента по номеру

void SortByArt();        //сортировка по артикулу

void SortByName();      //сортировка по наименованию

int Count();              //возвращает размер

tovar &operator[](int);   //индексирование

int Search(String art);   //поиск по артикулу

}; 
 

     В программе используются объекты классов визуальных компонентов Builder C++. Основные из них :

• *Form1  - основная форма
• *F2 – форма для добавления товара
• *F3 – форма редактирования информации о товаре
• *F4 – форма поиска отвара

     В класс TForm1 – основной формы входит объект tovar P – список товаров и функция Out() – вывода отсортированного списка на экран в компонент TListView. 
 
 
 
 
 
 

 

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

     Рассмотрим  объекты, созданные специально для  курсовой работы. Объекты VCL рассматривать не будем.

     В программе используются структуры и класс:

• struct tovar – структура с информацией о товаре
• struct unit – узел списка товаров
• class tovsrlst – список товаров

     Подробно  они рассмтренны выше в пункте “таблица имен” 

     

 

      Разработка интерфейса программы  

     Основная  форма программы  в режиме редактирования:

       

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

1. TlistVieqw *LV – для отображеиня списка товаров
2. Tbuttons – кнопки для инициации различных действий (добавления, удаления и т.д.).

 

     Для добавления нового товара используем форму редактирования, (F2) вызываемую в безмодальном режиме: 

       

     Форма содержит в себе компоненты TEdit * для ввода информации и TComboBox * для выбора единицы измерения. А так же кнопки TButton * (Ok и Отмена) . Аналогично выглядит форма редактирования (F3).

     

       Еще добавим форму поиска по артикулу :

       

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

 

     

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

     Программ  не прихотлива к ресурсам. Для запуска и работы программы достаточно Windows 98 (вполне возможно, что запустится и под Windows 95). Запускается информационная система файлом sklad.exe. При запуске происходит автоматическая загрузка данных из файла tovar.lst.

     Пример  файла tovar.lst

В150-3

Ведро

15

Шт.

17

И67

Линейка

90

Шт.

12

К-745

Клей ПВА

19

Л.

78

М127

Молоток

10

Шт.

15

     Как видно, на каждый товар приходится по 5 строк в файле tovar.lst 

     Интерфейс состоит из 4-х форм (основная форма, форма вставки, редактирования, поиска).

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

       

     Интерфейс программы представлен таблицей товаров с информацией о них  и кнопками для работы со списком

     Нажав кнопку «Добавить », пользователь попадает в форму занесения информации о новом товаре

      . 
 

     Кнопка  «Удалить» - предназначена для удаления информации о конкретном отваре. После ее нажатия пользователю будет предложено подтвердить удаление. 

       

     С помощью кнопки «Поиск», можно найти  товар по его артикулу. 

       

     Кнопка  «Редактировать» (или двойной клик мыши на пациенте) вызывает форму редактирования информации.

     

       По кнопке «Выход» осуществляется  выход из программы. При выходе автоматически сохраняются сделанные изменения в файле tovar.lst.

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

     Сортировка  по артикулу:

     

     Сортировка  по наименованию

     

 

     Заключение 

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

     В процессе  выполнения работы , на языке  C++ был написан класс, реализующий связанный линейный список структур с информацией о пациентах. На базе этого класса, в среде программирования Builder C++, была разработана информационная система для склада, реализующая следующие возможности работы со списком товаров:

1. Просматривать список товаров
2. Добавлять, удалять товаров
3. Просматривать, редактировать информацию о товарах
4. Искать отвары в списке по артикулу
5. Сортировать список товаров по артикулу или наименованию.

 
 
 
 

 

     Литература 
 

1. Архангельский А.Я.  Программирование в C++ Builder 6. – М:”Бином”,2002
2. Павловская Т.А. C/C++. Программирование на языке высокого уровня: Учебник для вузов. - СПб:”Питер”,2003
3. Шилдт Г. Самоучитель С++. – СПб:”BHV – Санкт-Петербург”,1998
4. Страуструп Б. Язык программирования С++.1-Киев.:”Диасофт”,1993.
5. Страуструп Б. Язык программирования С++.2-Киев.:”Диасофт”,1993.

 

 

     Приложение 1 

Файл tovar.hpp 

#ifndef __tovar

#define __tovar 

#include<classes.hpp> 
 

//Структура с  информацией о товаре

struct  tovar{

public:

String Art;    // артикул

String Name;   // наименование

int Kol;       // количество на складе

String Ed;     //единица измерения

String Pls;    // место хранения 

}; 

#endif 
 

Файл tovarlst.hpp 
 

#ifndef __tovarlst

#define __tovarlst

#include"pntnt.hpp"

#include<classes.hpp> 
 

struct unit 

{

tovar a;

unit *nt;//ссылка на  след. элемент

}; 

//список пациентов 

class tovarlst{

private:

unit *f;  //начало

unit *e;  //конец

int size; //размер 

public:

tovarlst(); //конструктор

~tovarlst(); //деструктор

void Add(tovar);     //вставка в конец

void Delete(int);         //удаление элемента по номеру

void SortByArt();        //сортировка по артикулу

void SortByName();      //сортировка по наименованию

int Count();              //возвращает размер

tovar &operator[](int);   //индексирование

int Search(String art);   //поиск по артикулу

}; 

#endif 
 
 

Файл tovarlst.cpp 
 

#include<stddef.h>

#include"pntlst.hpp" 

        //конструктор 

tovarlst::tovarlst()

{

        size=0;

        f=NULL;

        e=NULL;

} 
 

        //деструктор 

tovarlst::~tovarlst()

{

        while(size>0) Delete(0); 

} 

        //вставка элемента в конец 

void tovarlst::Add(tovar a)

{

        unit *p,*t;

        int i; 

        //увеличение размера

        size++;

        //создание узла

        p=new unit;

        p->a=a;

        p->nt=0;

       //вставка

        if (f==0)

        {f=p;

        e=p;return;} //если список пуст

        e->nt=p;

        e=p; 

} 
 

//удаление элемента  по номеру 

void   tovarlst::Delete(int n)

{

        unit *p,*t;

        int i; 

        //если индекс выходит за допустимые границы, то выход

        if (n<0 || n>=size) return; 

        t=f; 

        //если удаляется  первый элемент

        if(n==0)

        {

        t=f;

        f=f->nt;

        delete t;

        size--;

        return;

        } 
 

        //переход на узел, после которого  осуществляется удаление

        for(i=0;i<n-1;i++) t=t->nt; 

        //собственно удаление

        p=t->nt;

        t->nt=p->nt;

        if(n==size-1) e=t;

        //освобождение памяти

        delete p;

        //изменение размера

        size--; 

} 
 
 
 
 

//доступ по номеру 

tovar &tovarlst::operator[](int n)

{

       int i;

        unit *t; 

        t=f;

       for(i=0;i<n;i++) t=t->nt; 

        return((t->a)); 

} 
 

        //размер 

int tovarlst::Count()

{

        return(size);

} 
 

        //поиск 

int tovarlst::Search(String art)

{

        int i;

        tovar a; 

        for(i=0;i<size;i++)

         {

         a=(*this)[i];

         if (a.Art==art) break;

         } 

        if (i==size) i=-1;

        return(i);

} 
 

        //Сортировка по артикулу 

void tovarlst::SortByArt()

{

        unit *p,*t;

        int i,j;

        tovar z; 

        p=f; 

        for(i=0;i<size;i++,p=p->nt)

         for(j=0,t=f;j<size;j++,t=t->nt)

          if ((p->a).Art<(t->a).Art)

           {

           z=p->a;

           p->a=t->a;

           t->a=z;

           }

} 
 

        //Сортировка пузырьком по наименованию 

void tovarlst::SortByName()

{

        unit *p,*t;

        int i,j;

        tovar z; 

        p=f; 

        for(i=0;i<size;i++,p=p->nt)

         for(j=0,t=f;j<size;j++,t=t->nt)

          if ((p->a).Name<(t->a).Name)

           {

           z=p->a;

           p->a=t->a;

           t->a=z;

          }

} 
 

        //вывод в список строк (для  создания интерфейса) 

/*void pntlst::PatientsToStrings(TStringList *s)

{

        int i;

        patnt a; 

        for(i=0;i<size;i++)

         {

         a=(*this)[i];

         s->Add(a.F+"    "+a.I+"    "+a.O+"      "+a.A+"       "+a.D);

         } 

} */ 
 
 
 
 

Заголовочный файл основной формы

//--------------------------------------------------------------------------- 

#ifndef sklad1H

#define sklad1H

//---------------------------------------------------------------------------

#include <Classes.hpp>

#include <Controls.hpp>

#include <StdCtrls.hpp>

#include <Forms.hpp>

#include"pntlst.hpp"

#include <ComCtrls.hpp>

//---------------------------------------------------------------------------

class TForm1 : public TForm

{

__published: // IDE-managed Components

        TButton *Del;

        TButton *Add;

        TButton *Ext;

        TButton *Button1;

        TButton *Button2;

        TListView *LV;

        TButton *Button3;

        TButton *Button4;

        void __fastcall AddClick(TObject *Sender);

        void __fastcall DelClick(TObject *Sender);

        void __fastcall ExtClick(TObject *Sender);

        void __fastcall LBDblClick(TObject *Sender);

        void __fastcall Button1Click(TObject *Sender);