Обработка динамических структур данных. 2

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ

УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«МОСКОВСКИЙ АВИАЦИОННЫЙ ИНСТИТУТ

(национальный  исследовательский университет)» (МАИ)

 

 

 

 

Курсовая работа

на тему: «Обработка динамических структур данных»

по дисциплине: Программирование на ЯВУ

 

 

Студента гр. ДА 2-49

Буйная М.А/

 

 

 

 

 

 

 

 

 

Байконур 2014 г.

 

Аннотация

 

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

Алгоритм решения задач выполнен в программе Microsoft Visual в среде языка Си++.

 

 

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

 

Разработать алгоритм и составить программу обработки списка данных «Гостиница», выполнив следующие этапы:

1. Представление (построение, создание) списка данных в виде линейного однонаправленного списка с элементами сложного типа
2. Выполнить удаление из исходного списка сведений о гостиницах, в которых нет свободных номеров
3. Выполнить перемещение в начало исходного списка сведений о пятизвёздочных гостиницах
4. Выполнить сортировку исходного списка данных по полю «общее количество мест» методом вставки
5. Создать пользовательский интерфейс, с помощью которого будет проходить работа с программой, используя средства текстового и графического режимов работы. Интерфейс должен содержать:

- все основные пункты  работы (создание, удаление, перемещение, сортировка, выход, просмотр результатов  работы на каждом этапе);

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

Требования к программе:

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

- Программа должна содержать  пояснения основных идентификаторов  и блоков;

- Реализацию алгоритма  необходимо выполнить на языке  программирования С/С++.

 

 

2. Метод решения

 

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

Ключевым словом для объявления структуры является слово «struct».

Пример 1:

 

struct a { int x;

float y;

char mas[15]; }

 

Это так называемый структурный шаблон. Общий вид описания шаблона:

 

struct тег(имя структуры) { тип1 имя поля1;

тип2 имя поля2;

тип3 имя поля3;

………………..

тип n имя поля n; };

 

Структурные переменные удобно изображать в виде дерева или графа.

Пример 2:

 

                                        z

                        x   y  mas

 

                                                 mas0     mas1 ……. Mas14

Рис. 1 – граф структурных переменных примера 1

Изобразим в виде дерева поля записи о гостиницах:

 

                                         Гостиница

 

        Название            Класс    Всего мест           Свободно  Стоимость номера

Рисунок 2 – граф полей записи о гостиницах

 

2.1 Формирование данных

 

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

 

typedef struct data_{char nazvanie[255];//название гостиницы

int class_;//класс гостиницы //1-5

int kolichestvo_o;//количество мест  общее

int kolichestvo_s;//количество мест  свободное

int cena;//стоимость номера  в сутки

};

 

Следовательно, будет формироваться массив разнотипных данных

 

                                                         data_

 

 

0                              nazvanie      class_       kolichstvo_o kolichestvo_s cena

data_

n

Рисунок 3 – Массив разнотипных данных полей записи структуры «Гостиница»

2.2 Линейный поиск

 

Линейный поиск эффективен в массивах, с небольшим количеством элементов, причём элементы в таких массивах никак не отсортированы и не упорядочены. Алгоритм линейного поиска в массивах последовательно проверяет все элементы массива и сравнивает их с ключевым значением. Чтобы убедиться, в отсутствии искомого значения необходимо проверить все элементы массива. У линейного поиска есть один недостаток: если образец не присутствует в массиве, то без принятия предохранительных мер поиск может выйти за границы массива.

Линейный поиск необходим в удалении из исходного списка о гостиницах, в которых нет свободных номеров. Следовательно, решение делится на 3 пункта:

1. Ввести количество гостиниц;
2. Поиск гостиниц, в которых нет свободных номеров;
3. Удалить данные.

 

void sspisok::udalenie()

{spisok *p;//

int n=0;

if((BegQ!=NULL)&&(EndQ!=NULL))

{

p=BegQ;

while(p!=NULL//поиск номеров

{n++;

if(p->data.kolichestvo_s==0) //если нет свободных номеров

{sspisok::delete_data(n); //удаление гостиницы

n--;//возврат индекса к  предыдущему элементу

}

p=p->next;

};

}

}

if((BegQ==NULL)&&(EndQ==NULL))//если  список пустой

{cout<<"Список не был  создан или пустой"<<endl;

}

else

if((BegQ->data.kolichestvo_o==NULL)&&(EndQ->data.kolichestvo_o==NULL))//проверка  на пустоту списка

{cout<<"Список пустой"<<endl;//вывод соотв. сообщения

};

}

 

Поиск в программе реализован согласно алгоритму линейного поиска.

 

2.3 Сортировка методом  вставки

 

Рассмотрим сортировку методом вставки. Принцип метода заключается в следующем:

Массив разделяется на 2 части: отсортированную и не отсортированную. Элементы из не отсортированной части поочередно выбираются и вставляются в отсортированную часть так, чтобы не нарушить в ней упорядоченность элементов. В начале работы алгоритма в качестве отсортированной части массива принимают только первый элемент, а в качестве не отсортированной – все остальные элементы.

Таким образом, алгоритм будет состоять из (n-1) - го прохода ( n – размерность массива), каждый из которых будет включать 4 действия:

- взятие очередного i-го отсортированного элемента и сохранение его в дополнительной переменной;

- поиск позиции i в отсортированной части массива, в которой присутствие взятого элемента не нарушит упорядоченности элементов;

- сдвиг элементов массива  от i-го до (j-1)-го вправо, чтобы освободить найденную позицию вставки;

- вставка взятого элемента  в найденную i-ую позицию

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

 

void sspisok::sort_mas(long n)//сортировка массива по общему количеству мест

{data_ tmp;

for (int i = 1; i < n; i++) {

for (int j = 0; j < n-i; j++) {

if (c[j].kolichestvo_o > c[j+1].kolichestvo_o) {

tmp = c[j];

c[j] = c[j+1];

c[j+1] = tmp;

}

}

}

};

 

Сортировка в программе реализована согласно методу вставки.

алгоритм сортировка данные линейный

 

3 .Алгоритмизация задачи

 

Схема алгоритмов и пояснение используемых идентификаторов приведены в Приложении Б и руководстве программиста. Текст программы представлен в приложении А.

Решение задачи включает следующие этапы:

1. Формирование массива данных;
2. Вывод данных на экран;
3. Удаление данных;
4. Перемещение данных;
5. Сортировка данных;
6. Запись данных в файл;
7. Загрузка данных из файла;

 

3.1 Алгоритм формирования  данных

 

При создании списка данных о гостиницах необходимо:

Шаг 1. Ввод размерности массива;

Шаг 2. Цикл: для i=0;i<n;i++ выполнять ввод:

Название Data.nazvanie;

Класс Data.class_;

Общее количество мест - Data.kolichestvo_o;

Количество свободных мест - Data.kolichestvo_s;

Цена - Data.cena;

Шаг 3. Конец цикла;

 

3.2 Алгоритм вывода данных  на экран

 

Шаг 1. Вывод на экран шапки таблицы с данными

Шаг 2. Цикл: для i=0;i<n;i++ выполнять вывод:

Название Data.nazvanie;

Класс Data.class_;

Общее количество мест - Data.kolichestvo_o;

Количество свободных мест - Data.kolichestvo_s;

Цена - Data.cena;

Шаг 3. Конец цикла;

 

3.3 Алгоритм удаления данных

 

Шаг 1. Ввод данных о гостиницах

Шаг 2. Цикл: while(p!=NULL) // пока не найдется гостиница без свободных номеров

При отсутствии свободных номеров в гостинице data.kolichestvo_s==0

удалить данные об этой гостинице sspisok::delete_data(n)

продолжить поиск по циклу (n--).

Шаг 4. Конец цикла;

 

3.4 Алгоритм перемещения  данных

 

Шаг 1. Ввод данных о гостиницах;

Шаг 2. Цикл while(Q!=NULL)//пока не начало списка

выполнять поиск пятизвездочной гостиницы Q->next->data.class_==5

присвоить указателю Q2 значение указателя Q->next

найденной гостинице присвоить указатель начала списка BegQ=Q2.

Шаг 3. Конец цикла;

 

3.5 Алгоритм сортировки  данных

 

Шаг 1. Ввод новой переменной tmp и массива данных c[j]

Шаг 2. Циклы: для i=0;i<n-1;i++ , для j = 0; j < n-i; j++ выполнять

Сравнение полей записи общего количества мест в гостинице

Присваивание tmp значения c[j]

Копирование c[j] в массив c[j+1];

Шаг 3. Конец цикла;

 

3.6 Алгоритм записи данных  в файл

 

Шаг 1. Открытие файла

Шаг 2. Цикл while пока не конец файла выполнять запись данных в файл

Название Data.nazvanie;

Класс Data.class_;

Общее количество мест - Data.kolichestvo_o;

Количество свободных мест - Data.kolichestvo_s;

Цена - Data.cena;

Шаг 3. Конец цикла

Шаг 4. Закрытие файла

 

3.7 Алгоритм загрузки данных  из файла

 

Шаг 1. Открытие файла;

Шаг 2. Цикл: пока не закончатся данные в файле выполнять

Вывод на экран данных

Название x.nazvanie;

Класс x.class_;

Общее количество мест x.kolichestvo_o;

Количество свободных мест x.kolichestvo_s;

Цена x.cena.

Шаг 3. Конец цикла;

Шаг 4. Закрытие файла;

4. Инструкция по пользованию  программой

 

4.1 Руководство пользователя

 

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

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

1. Запустить программу Microsoft Visual C++.
2. Выполнить следующие команды: File\ Open project…\ C:\Users\Маша\Documents\Visual Studio 2008\Projects\Курсовая Отель.sln
3. Запустить программу выполнением опции главного меню Run/Run.

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

 

cout<<"Menu"<<endl;

cout<<"1.Sformirovat spisok"<<endl;

cout<<"2.Dobavit zapis'"<<endl;

cout<<"3.Udalit' zapis'"<<endl;

cout<<"4.Otobrazit spisok"<<endl;

cout<<"5.Skoirovat v Fail"<<endl;

cout<<"6.Skopirovat v Massiv"<<endl;

cout<<"7.Otobrazit Massiv"<<endl;

cout<<"8.Sortirovat Massiv"<<endl;

cout<<"9.Skopirovat iz Faila"<<endl;

cout<<"10.Nayti zapis' v spiske"<<endl;

cout<<"11.Udalenie otelei bez svobodnih nomerov"<<endl;

cout<<"12.Peremeshenie 5-ti zvezdochnih gostinic"<<endl;

cout<<"0.Vyhod"<<endl;

cout<<endl<<endl;

cout<<"Vyberite:_";

 

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

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

 

4.2 Руководство программиста

 

Данная программа написана с использованием языка Си++. Минимальное количество обрабатываемых данных ограничено (не менее 20). Данные вводятся клавиатуры . Данная программа состоит из основного блока и 12 подпрограмм.

 

Таблица 4.2.1 – Идентификаторы функции add_data

Переменная	Тип	Назначение
i	long	Указывает номер записи в массиве
n	long	Указывает на количество записей в массиве

 

Таблица 4.2.2 – Идентификаторы функции delete_data

Переменная	Тип	Назначение
i	long	Указывает номер удаляемой записи в массиве
n	long	Указывает на количество записей в массиве
j	int	Указывает номер удаляемого элемента

 

Таблица 4.2.3 – Идентификаторы функции sp_copy_mas

Переменная	Тип	Назначение
i	long	Указывает на количество записей в массиве
n	long	Указывает номер записи в массиве

 

 

Таблица 4.2.4 – Идентификаторы функции sort_mas

Переменная	Тип	Назначение
i	int	Указывает на количество записей в массиве
n	long	Указывает на номер записи в массиве
j	int	Указывает на номер записи в массиве
tmp	int	Переменная для копирования записи количества номеров
c[j]	char	Переменная для копирования строк

 

Таблица 4.2.5 – Идентификаторы функции show_mas

Переменная	Тип	Назначение
i	long	Указывает на количество записей в массиве

 

Таблица 4.2.6 – Идентификаторы функции fail

Переменная	Тип	Назначение
i	int	Указывает номер записи в массиве
n	int	Указывает на количество записей в массиве

 

Таблица 4.2.7 – Идентификаторы функции find_data

Переменная	Тип	Назначение
t	long	Указывает количество найденных записей

 

Таблица 4.2.8 – Идентификаторы функции peremesh

Переменная	Тип	Назначение
n	int	Указывает номер записи в массиве

 

Таблица 4.2.9 – Идентификаторы функции udalenie

Переменная	Тип	Назначение
n	int	Указывает номер записи в массиве

 

 

5. Анализ результатов

 

1. Создание списка данных

Шаг 1. Запуск программы;

Шаг 2. Выбор пункта формирование списка (1);

Шаг 3. Ввод количества гостиниц (n=32)

Шаг 4. Ввод данных

2. Вывод списка данных

 

Ожидаемый результат

Название	Класс	Общее количество мест	Количество свободных мест	Минимальная Цена
Milana	4	120	32	2000
Kinder	3	130	22	200
GoGs	5	550	36	5000
Finnish	4	600	32	6000
Dobi	3	250	65	400
Max	3	100	22	400
Apple	2	200	35	220
Evas	4	500	12	1200
Fox	2	45	11	500
Lelik	2	30	10	120
Toto	4	250	13	1300
Gomer	1	15	2	100
Frank	5	777	120	5000
Sandra	3	450	35	4000
Rex	4	600	36	6000
Toll	1	50	21	200
Oleg	1	30	25	100
Kira	1	50	10	150
Ermak	3	320	23	150
UFO	5	750	32	6000
Polli	5	450	65	3500
GHOST	5	120	32	5000
jIjI	3	320	23	4500
Kiska	4	120	32	2000
Gosha	2	250	21	1200
Alex	4	300	23	5500
Lumos	4	250	34	4600
Pappa	3	330	125	2000
Reg	5	600	254	5500
Kollags	2	120	0	100
Gagas	1	20	1	80
Hippo	4	450	125	2000

 

Полученный результат

 

 

Вывод: полученный результат совпал с ожидаемым.

3. Сохранение в файл

Шаг 1. Выберем пункт копировать в файл (5);

Шаг 2. Проверка наличия данных в файле ftext_in.txt.

 

 

 

Вывод: данные сохранены в файле

4. Удаление гостиниц без свободных номеров

Шаг 1. Выберем в меню пункт удаление (11);

 

Ожидаемый результат:

Название	Класс	Общее количество мест	Количество свободных мест	Минимальная Цена
Milana	4	120	32	2000
Kinder	3	130	22	200
GoGs	5	550	36	5000
Finnish	4	600	32	6000
Dobi	3	250	65	400
Max	3	100	22	400
Apple	2	200	35	220
Evas	4	500	12	1200
Fox	2	45	11	500
Lelik	2	30	10	120
Toto	4	250	13	1300
Gomer	1	15	2	100
Frank	5	777	120	5000
Sandra	3	450	35	4000
Rex	4	600	36	6000
Toll	1	50	21	200
Oleg	1	30	25	100
Kira	1	50	10	150
Ermak	3	320	23	150
UFO	5	750	32	6000
Polli	5	450	65	3500
GHOST	5	120	32	5000
jIjI	3	320	23	4500
Kiska	4	120	32	2000
Gosha	2	250	21	1200
Alex	4	300	23	5500
Lumos	4	250	34	4600
Pappa	3	330	125	2000
Reg	5	600	254	5500
Gagas	1	20	1	80
Hippo	4	450	125	2000

 

Полученный результат

 

 

Вывод: полученный результат совпал с ожидаемым.

5. Перемещение

Шаг 1. Выбрать в меню пункт перемещение (12)

Шаг 2. Перенести пятизвёздочные гостиницы в начало списка:

 

Следовательно, ожидаемый результат:

Название	Класс	Общее количество мест	Количество свободных мест	Минимальная Цена
Polli	5	450	65	3500
Frank	5	777	120	5000
GHOST	5	120	32	5000
Reg	5	600	254	5500
UFO	5	750	32	6000
GoGs	5	550	36	5000
Milana	4	120	32	2000
Kinder	3	130	22	200
Finnish	4	600	32	6000
Dobi	3	250	65	400
Max	3	100	22	400
Apple	2	200	35	220
Evas	4	500	12	1200
Fox	2	45	11	500
Lelik	2	30	10	120
Toto	4	250	13	1300
Gomer	1	15	2	100
Sandra	3	450	35	4000
Rex	4	600	36	6000
Toll	1	50	21	200
Oleg	1	30	25	100
Kira	1	50	10	150
Ermak	3	320	23	150
jIjI	3	320	23	4500
Kiska	4	120	32	2000
Gosha	2	250	21	1200
Alex	4	300	23	5500
Lumos	4	250	34	4600
Pappa	3	330	125	2000
Gagas	1	20	1	80
Hippo	4	450	125	2000