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

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

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

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

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

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

 

 

 

 

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

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

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

 

 

Студента гр. ДА 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;