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

Содержание 
 

 

 

Задание 

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

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

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

 

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

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

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

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

 

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

     Программа написана на языке 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