Обработка динамических структур данных
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ
УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«МОСКОВСКИЙ АВИАЦИОННЫЙ ИНСТИТУТ
(национальный исследовательский университет)» (МАИ)
Курсовая работа
на тему:
«Обработка динамических структур данных»
по
дисциплине: Программирование на ЯВУ
Студента
гр. ДА 2-49
Буйная
М.А/
Байконур
2014 г.
Аннотация
Данная курсовая работа посвящена разработке и
обработке массивов структур. Программы курсовой работы дают возможность
обработать данные одномерных списков. В курсовой работе имеется описание
алгоритмов и листингов программ.
Алгоритм решения задач выполнен в программе Microsoft
Visual в среде языка
Си++.
1. Постановка задачи
Разработать алгоритм и составить программу
обработки списка данных «Гостиница», выполнив следующие этапы:
. Представление (построение, создание)
списка данных в виде линейного однонаправленного списка с элементами сложного
типа
. Выполнить удаление из исходного списка
сведений о гостиницах, в которых нет свободных номеров
. Выполнить перемещение в начало
исходного списка сведений о пятизвёздочных гостиницах
. Выполнить сортировку исходного списка
данных по полю «общее количество мест» методом вставки
. Создать пользовательский интерфейс, с
помощью которого будет проходить работа с программой, используя средства
текстового и графического режимов работы. Интерфейс должен содержать:
все основные пункты работы (создание, удаление,
перемещение, сортировка, выход, просмотр результатов работы на каждом этапе);
В процессе обработки указанного списка
необходимо сформировать текстовый файл отчета, содержащий как исходный список
данных, так и списки данных, полученные в результате их обработки на каждом
этапе.
Требования к программе:
Программа должна обеспечивать ввод исходных
данных с клавиатуры(не менее 20 записей);
Программа должна содержать пояснения основных
идентификаторов и блоков;
Реализацию алгоритма необходимо выполнить на
языке программирования С/С++.
2. Метод решения
Для записи данных о туризме необходимо
воспользоваться структурами. Структура позволяет объединить в одном объекте
разнотипные данные с целью их совместной обработки.
Ключевым словом для объявления структуры
является слово «struct».
Пример 1:
a { int x;
y;
char
mas[15]; }
Это так называемый структурный шаблон. Общий вид
описания шаблона:
тег(имя структуры) { тип1 имя поля1;
тип2 имя поля2;
тип3 имя поля3;
………………..
тип n
имя
поля n; };
Структурные переменные удобно изображать в виде
дерева или графа.
Пример 2:
z
x
y mas
mas0 mas1 ……. Mas14
Рис. 1 - граф структурных переменных примера 1
Изобразим в виде дерева поля записи о
гостиницах:
Гостиница
Название Класс Всего мест Свободно Стоимость номера
Рисунок 2 - граф полей записи о гостиницах
.1 Формирование данных
Запишем структурный шаблон, который будет
содержать названия гостиниц, класс гостиницы, общее количество мест, количество
свободных номеров, минимальная стоимость номера в сутки:
struct data_{char nazvanie[255];//название
гостиницыclass_;//класс гостиницы //1-5kolichestvo_o;//количество мест
общееkolichestvo_s;//количество мест свободноеcena;//стоимость номера в сутки
};
Следовательно, будет формироваться массив
разнотипных данных
data_
0
nazvanie class_ kolichstvo_o kolichestvo_s cena_
n
Рисунок 3 - Массив разнотипных данных полей
записи структуры «Гостиница»
.2 Линейный поиск
Линейный поиск эффективен в массивах, с
небольшим количеством элементов, причём элементы в таких массивах никак не
отсортированы и не упорядочены. Алгоритм линейного поиска в массивах
последовательно проверяет все элементы массива и сравнивает их с ключевым
значением. Чтобы убедиться, в отсутствии искомого значения необходимо проверить
все элементы массива. У линейного поиска есть один недостаток: если образец не
присутствует в массиве, то без принятия предохранительных мер поиск может выйти
за границы массива.
Линейный поиск необходим в удалении из исходного
списка о гостиницах, в которых нет свободных номеров. Следовательно, решение
делится на 3 пункта:
) Ввести количество гостиниц;
) Поиск гостиниц, в которых нет свободных
номеров;
) Удалить данные.
sspisok::udalenie()
{spisok
*p;//n=0;((BegQ!=NULL)&&(EndQ!=NULL))
{=BegQ;(p!=NULL//поиск номеров
{n++;(p->data.kolichestvo_s==0) //если нет
свободных номеров
{sspisok::delete_data(n); //удаление
гостиницы-;//возврат индекса к предыдущему элементу
}=p->next;
};
}
}((BegQ==NULL)&&(EndQ==NULL))//если
список пустой
{cout<<"Список не был создан или
пустой"<<endl;
}((BegQ->data.kolichestvo_o==NULL)&&(EndQ->data.kolichestvo_o==NULL))//проверка
на пустоту списка
{cout<<"Список
пустой"<<endl;//вывод соотв. сообщения
};
}
Поиск в программе реализован согласно алгоритму
линейного поиска.
.3 Сортировка методом вставки
Рассмотрим сортировку методом вставки. Принцип
метода заключается в следующем:
Массив разделяется на 2 части: отсортированную и
не отсортированную. Элементы из не отсортированной части поочередно выбираются
и вставляются в отсортированную часть так, чтобы не нарушить в ней
упорядоченность элементов. В начале работы алгоритма в качестве отсортированной
части массива принимают только первый элемент, а в качестве не отсортированной
- все остальные элементы.
Таким образом, алгоритм будет состоять из (n-1)
- го прохода ( n -
размерность массива), каждый из которых будет включать 4 действия:
взятие очередного i-го
отсортированного элемента и сохранение его в дополнительной переменной;
поиск позиции i
в отсортированной части массива, в которой присутствие взятого элемента не
нарушит упорядоченности элементов;
сдвиг элементов массива от i-го
до (j-1)-го вправо,
чтобы освободить найденную позицию вставки;
вставка взятого элемента в найденную i-ую
позицию
Примером сортировки вставками можно взять пункт
из разработанной программы сортировка по общему количеству мест в гостинице.
sspisok::sort_mas(long n)//сортировка массива по
общему количеству мест
{data_ tmp;(int i = 1; i < n; i++) {(int j =
0; j < n-i; j++) {(c[j].kolichestvo_o > c[j+1].kolichestvo_o) {= c[j];[j]
= c[j+1];[j+1] = tmp;
}
}
}
};
Сортировка в программе реализована согласно
методу вставки.
алгоритм сортировка данные линейный
3 .Алгоритмизация задачи
Схема алгоритмов и пояснение используемых
идентификаторов приведены в Приложении Б и руководстве программиста. Текст
программы представлен в приложении А.
Решение задачи включает следующие этапы:
) Формирование массива данных;
) Вывод данных на экран;
) Удаление данных;
) Перемещение данных;
) Сортировка данных;
) Запись данных в файл;
) Загрузка данных из файла;
.1 Алгоритм формирования данных
При создании списка данных о гостиницах
необходимо:
Шаг 1. Ввод размерности массива;
Шаг 2. Цикл: для i=0;i<n;i++
выполнять ввод:
Название Data.nazvanie;
Класс Data.class_;
Общее количество мест - Data.kolichestvo_o;
Количество свободных мест - Data.kolichestvo_s;
Цена - Data.cena;
Шаг 3. Конец цикла;
.2 Алгоритм вывода данных на экран
Шаг 1. Вывод на экран шапки таблицы с данными
Шаг 2. Цикл: для i=0;i<n;i++
выполнять вывод:
Название Data.nazvanie;
Класс Data.class_;
Общее количество мест - Data.kolichestvo_o;
Количество свободных мест - Data.kolichestvo_s;
Цена - Data.cena;
Шаг 3. Конец цикла;
.3 Алгоритм удаления данных
Шаг 1. Ввод данных о гостиницах
Шаг 2. Цикл: while(p!=NULL) // пока не найдется
гостиница без свободных номеров
При отсутствии свободных номеров в гостинице
data.kolichestvo_s==0
удалить данные об этой гостинице
sspisok::delete_data(n)
продолжить поиск по циклу (n--).
Шаг 4. Конец цикла;
.4 Алгоритм перемещения данных
Шаг 1. Ввод данных о гостиницах;
Шаг 2. Цикл while(Q!=NULL)//пока не начало
списка
выполнять поиск пятизвездочной гостиницы Q->next->data.class_==5
присвоить указателю Q2 значение указателя Q->next
найденной гостинице присвоить указатель начала
списка BegQ=Q2.
Шаг 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. Конец цикла;
.6 Алгоритм записи данных в файл
Шаг 1. Открытие файла
Шаг 2. Цикл while
пока не конец файла выполнять запись данных в файл
Название Data.nazvanie;
Класс Data.class_;
Общее количество мест - Data.kolichestvo_o;
Количество свободных мест - Data.kolichestvo_s;
Цена - Data.cena;
Шаг 3. Конец цикла
Шаг 4. Закрытие файла
.7 Алгоритм загрузки данных из файла
Шаг 1. Открытие файла;
Шаг 2. Цикл: пока
не закончатся данные в файле выполнять
Вывод на экран данных
Название x.nazvanie;
Класс x.class_;
Общее количество мест x.kolichestvo_o;
Количество свободных мест x.kolichestvo_s;
Цена x.cena.
Шаг 3. Конец цикла;
Шаг 4. Закрытие файла;
. Инструкция по пользованию программой
.1 Руководство пользователя
Назначение программы «Гостиница» предназначена для
обработки массивов структур, содержащего сведения о гостиницах.
Для запуска программы необходимо:
) Запустить программу Microsoft
Visual C++.
) Выполнить следующие команды: File\
Open project…\
C:\Users\Маша\Documents\Visual Studio
2008\Projects\Курсовая Отель.sln
3) Запустить программу выполнением опции
главного меню Run/Run.
Для удобства с программой разработан
пользовательский интерфейс, представленный далее.
<<"Menu"<<endl;<<"1.Sformirovat
spisok"<<endl;<<"2.Dobavit
zapis'"<<endl;<<"3.Udalit' zapis'"<<endl;<<"4.Otobrazit
spisok"<<endl;<<"5.Skoirovat v
Fail"<<endl;<<"6.Skopirovat v
Massiv"<<endl;<<"7.Otobrazit
Massiv"<<endl;<<"8.Sortirovat Massiv"<<endl;<<"9.Skopirovat
iz Faila"<<endl;<<"10.Nayti zapis' v
spiske"<<endl;<<"11.Udalenie otelei bez svobodnih
nomerov"<<endl;<<"12.Peremeshenie 5-ti zvezdochnih
gostinic"<<endl;<<"0.Vyhod"<<endl;<<endl<<endl;<<"Vyberite:_";
После запуска программы необходимо выбрать
соответствующий пункт меню, путем ввода его номера с клавиатуры.
Выходные параметры программы: результатом работы
программы являются списки гостиниц, представленные в табличной форме.
.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. Запуск программы;
Шаг 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
|
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
|
Полученный результат
Вывод: полученный результат совпал с ожидаемым.
) Сохранение в файл
Шаг 1. Выберем пункт копировать в файл (5);
Шаг 2. Проверка наличия данных в файле ftext_in.txt.
Вывод: данные сохранены в файле
) Удаление гостиниц без свободных номеров
Шаг 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
|
Полученный результат
Вывод: полученный результат совпал с ожидаемым.
) Перемещение
Шаг 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
|
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
|
Полученный результат
Вывод: полученный результат совпал с ожидаемым
) Сортировка
Шаг 1. Выбрать в меню пункт сортировка
массива(8);
Шаг 2. Проверить результаты сортировки;
Ожидаемый результат:
Название
|
Класс
|
Общее
количество мест
|
Количество
свободных мест
|
Минимальная
Цена
|
Gomer
|
1
|
15
|
2
|
100
|
Gagas
|
1
|
20
|
1
|
80
|
Lelik
|
2
|
30
|
10
|
120
|
Oleg
|
1
|
30
|
25
|
100
|
Fox
|
2
|
45
|
11
|
500
|
Toll
|
1
|
50
|
21
|
200
|
Kira
|
1
|
50
|
10
|
150
|
Max
|
3
|
100
|
22
|
400
|
GHOST
|
5
|
120
|
32
|
5000
|
Milana
|
4
|
120
|
32
|
2000
|
Kiska
|
4
|
120
|
32
|
2000
|
Kinder
|
3
|
130
|
22
|
200
|
Apple
|
2
|
200
|
35
|
220
|
Dobi
|
3
|
250
|
65
|
400
|
Toto
|
4
|
250
|
13
|
1300
|
Gosha
|
2
|
250
|
21
|
1200
|
Lumos
|
4
|
250
|
34
|
4600
|
Alex
|
4
|
300
|
23
|
5500
|
Ermak
|
3
|
320
|
23
|
150
|
jIjI
|
3
|
320
|
23
|
4500
|
Pappa
|
3
|
330
|
125
|
2000
|
Polli
|
5
|
450
|
65
|
3500
|
Sandra
|
3
|
450
|
35
|
4000
|
Hippo
|
4
|
450
|
125
|
2000
|
Evas
|
4
|
500
|
12
|
1200
|
GoGs
|
5
|
550
|
36
|
5000
|
Reg
|
5
|
600
|
254
|
5500
|
Finnish
|
4
|
600
|
32
|
6000
|
Rex
|
4
|
600
|
36
|
6000
|
UFO
|
5
|
750
|
32
|
6000
|
Frank
|
5
|
777
|
120
|
5000
|
Полученный результат:
Вывод: полученный результат совпал с ожидаемым.
) Загрузка данных из файла
Шаг 1. Выбрать в меню пункт копирование из файла
(9);
Шаг 2. Проверить результаты загрузки
Ожидаемый результат:
Полученный результат:
Вывод: полученный результат совпал с ожидаемым.
Заключение
В данной курсовой работе были разработаны и
обработаны массивы структур. Программа курсовой работы даёт возможность
обработать данные одномерных списков. Все полученные результаты совпали с
ожидаемыми, а именно: при выводе списка на экран были показаны все те данные,
что вводились при создании; удалены данные, в соответствии с пустыми турами;
страны были упорядочены по возрастанию количества билетов. Следовательно,
программа работает правильно.
Список используемой литературы
1. Дональд
К. «Искусство программирования. 3 том. Сортировка и поиск».
2. Хэзфилд
Р., Кирби Л. «Искусство программирования на C++. Фундаментальные алгоритмы,
структуры данных и примеры приложений».
. Либерти
Д. «Освой самостоятельно С++»
. Лафоре
Р. «Объектно- ориентированное программирование в С++».
. Подбельский
В. «Язык Cu ++: Учебное пособие».
. Жарков
В. «Visual C++».
Приложение А
// Курсовая_Отель.cpp : main project file.
#include <malloc.h>//для динамических
массивов
#include <iostream>//для cin cout
#include <conio.h>//для getch()
#include <fstream>//для файлов
#include <stdio.h>//стандартный ввод вывод
#include <string.h>//библиотека работы со строками
namespace std;
struct data_{char nazvanie[255];//название
гостиницыclass_;//класс гостиницы 1-5kolichestvo_o;//количество мест
общееkolichestvo_s;//количество мест свободноеcena;//стоимость номера в сутки
};
struct spisok{data_ data; //структура однонаправленного
списка* next;
};
*BegQ,*EndQ,*Q;//BegQ-начало списка,EndQ-конец
списка//Q-основной список_ Data;//Data-для ввода данных_ *c;//динамическая
переменная для массива_ *d;//дополнительный массив для
сортировкиnn;//количество элементов в массивеsspisok
{public:form(void);//процедура формирования спискаadd_data(data_);//добавления
элемента в конец списка списокshow_sp(void);//просмотр списка
данныхdelete_data(long);//удаление элемента списка
sp_copy_mas();//процедура копирования списка
данных в массивsort_mas(long);//процедура сортировки
массиваshow_mas(long);//вывод массиваfind_data(char*);//поиск в
массиве,т.к.линейныйsp_copy_file(void);//процедура копирования из списка в
файлfile_copy_sp();//процедура заполнения списка из файлаperemesh();//перемещение
5-ти звёздочных гостиниц в начало спискаudalenie();//удаление гостиниц без
свободных номеров
};
sspisok::form(void)//процедура формирования
однонаправленного списка,Q-сам список
//так как спискок кольцевой начало списка
обозначим меткой,значением -1
{Q=new spisok;//создание самого списка=new
spisok;//создание указателя на начало=new spisok;//создание указателя на
конец>next=EndQ;//начало ссылается на конец>next=NULL;//списорк ссылается
в конец,а конец в никуда=BegQ;//список лежит в начале>next=EndQ;//след. эл.
ссылается в конец>data.kolichestvo_o=NULL;//обнуление полей
данных>data.kolichestvo_o=NULL;//обнуление полей данных<<"Sozdan
spisok"<<endl;
}
sspisok::add_data(data_ Data)//добавление данных
{spisok *p;//для добавления элемента
//для первого элемента((BegQ->data.kolichestvo_o==NULL)&&(EndQ->data.kolichestvo_o==NULL))//если
список пустой в полях данных
{Q->data=Data;//заполняем поле
данных>next=NULL;//указатель следующего элемента пустота
Приложение А(продолжение)
BegQ=Q;//начало списка ссылается на
список=BegQ;//список переносим в начало списка=BegQ;//конец приравниваем
началу=Q;//конец списка>next=EndQ;//начало ссылается на
конец>next=NULL;//списорк ссылается в конец,а конец в никуда
}
//для всех
остальных((BegQ==NULL)&&(EndQ==NULL))
{cout<<"spisok ne
sozdan"<<endl;
}
{p=new spisok;//создаем переменную
динамическую>data=Data;//в поле данных заносим
данные>next=NULL;>next=p;//следующий после конца это добавленный
элемент=p;//смещаем конец на добавленный элемент
};
}
sspisok::delete_data(long n)//удаление n-ного
элемента списка
{spisok
*p;//i;//счетчик((BegQ!=NULL)&&(EndQ!=NULL)&&(n!=1))
{p=BegQ;//передача адреса(i=0;i<n-2;i++)
{p=p->next;//смещение указателя
}>next=p->next->next;//удаление
элемента<<"bil udalen "<<n<<"-ii element
"<<endl;
};
//на случай удаления первого
элемента((BegQ!=NULL)&&(EndQ!=NULL)&&(n==1))
{BegQ=BegQ->next;<<"bil udalen
"<<n<<"-ii element "<<endl;
};
((BegQ==NULL)&&(EndQ==NULL))//если
список пустой
Приложение А(продолжение)
{cout<<"Spisok pustoi ili
ne sozdan"<<endl;
}((BegQ->data.kolichestvo_o==NULL)&&(EndQ->data.kolichestvo_o==NULL))//проверка
на пустоту списка
{cout<<"Spisok
pustoi"<<endl;//вывод соотв. сообщения
};
}
sspisok::show_sp(void)//просмотр
списка
{ Q=BegQ;//смещение
указателя(Q->data.kolichestvo_o!=NULL)
{cout<<" Nazvanie Klass
Kol-vo obshee Kol-vo svobodnoe
Cena"<<endl<<endl;(Q!=NULL)//пока не начало списка
{.width(8);<<Q->data.nazvanie;.width(10);<<Q->data.class_;.width(10);<<Q->data.kolichestvo_o;.width(18);<<Q->data.kolichestvo_s;.width(20);<<Q->data.cena<<endl;
=Q->next;//переход на следующую
позицию
}
}((BegQ==NULL)&&(EndQ==NULL))//если
спискок пустой
{cout<<"Spisok ne
sozdan"<<endl;//вывод соотв. сообщения
}((BegQ->data.kolichestvo_o==NULL)&&(EndQ->data.kolichestvo_o==NULL))//проверка
на пустоту списка
{cout<<"Spisok
pustoi"<<endl;//вывод соотв. сообщения
};
}
sspisok::sp_copy_mas()//копирование
списка в массив
{long i,n;//n-для определения
количества элементов в списке,i-для цикла
//если в списке что то
есть=BegQ;//смещение указателя=0;//обнуление количества(Q!=NULL)//пока не
начало списка
{n++;=Q->next;//переход на
следующую позицию
}=(data_*)malloc(n*sizeof(data_));//создания
динамического массива=n;//передача количества элементов списка в глобальную
переменную для сортировки=BegQ;
//копирование списка в
массив(i=0;i<n;i++)
{c[i]=Q->data;=Q->next;
}
//если элементы не
обнаружены((BegQ->data.kolichestvo_o==NULL)&&(EndQ->data.kolichestvo_o==NULL))//проверка
на наличие списка
{cout<<"Spisok ne
sozdan"<<endl;
}((BegQ->data.kolichestvo_o==NULL)&&(EndQ->data.kolichestvo_o==NULL))//проверка
на пустоту списка
{cout<<"Spisok
pustoi"<<endl;
};
};
sspisok::sort_mas(long
n)//сортировка массива
// сортировка
{data_ tmp;(int i = 1; i < n;
i++) {(int j = 0; j < n-i; j++) {(c[j].kolichestvo_o >
c[j+1].kolichestvo_o) {= c[j];[j] = c[j+1];[j+1] = tmp;
}
}
}
};
sspisok::show_mas(long n)//вывод
массива
{long i;//счетчик
//вывод массива по
циклу<<" Nazvanie Klass Kol-vo obshee Kol-vo svobodnoe
Cena"<<endl<<endl;
(i=0;i<n;i++)
{
cout.width(8);<<c[i].nazvanie;.width(10);<<c[i].class_;.width(10);<<c[i].kolichestvo_o;.width(18);<<c[i].kolichestvo_s;.width(20);<<c[i].cena<<endl;
}<<endl;//переход на новую
строчку
}
sspisok::find_data(char Data[255])
{long t;//t-количество найденных
элементов=BegQ;//указатель списка в начало=0;//обнулнение
счетчика(Q!=NULL)//пока не конец списка
{if(stricmp(Q->data.nazvanie,Data)==0)//если
элемент найден то увеличение счетчика
{cout<<"nazavanie -
"<<Q->data.nazvanie<<" class -
"<<Q->data.class_<<endl;//печать элемента в
файл++;//увеличение счетчика
}=Q->next;//переход на следующий
элемент
}(t>0)//если элемент списка равен
искомому
{cout<<"Zapis' naidena
"<<t<<" raz(a)"<<endl;
{cout<<"Zapis' ne
naidena"<<endl;
}
}sspisok::sp_copy_file(void)//копирование
списка в файл
{ofstream
file("C:\\ftext_from.txt");//создание файла=BegQ;//смещение
указателя(Q!=NULL)//пока не конец списка
{file<<"Nazvanie -
"<<Q->data.nazvanie<<" Klass -
"<<Q->data.class_<<" kol-vo_o -
"<<Q->data.kolichestvo_o<<" kol-vo_s -
"<<Q->data.kolichestvo_s<<" Cena -
"<<Q->data.cena<<endl;//печать элемента в
файл=Q->next;//переход на следующую позицию
}
}
sspisok::file_copy_sp()//копирование
данных из файла в список
{data_ x;//переменная для считывания
из файлаfile("C:\\ftext_in.txt");//открытие файла(file!=NULL)
{cout<<"File Soderzhit
sleduiushie elementi:"<<endl;<<" Nazvanie Klass Kol-vo
obshee Kol-vo svobodnoe Cena"<<endl<<endl;
(!file.eof())//пока не конец файла
{
>>x.nazvanie;.width(8);cout<<x.nazvanie;>>x.class_;.width(10);cout<<x.class_;>>x.kolichestvo_o;.width(10);cout<<x.kolichestvo_o;>>x.kolichestvo_s;.width(18);cout<<x.kolichestvo_s;>>x.cena;.width(20);cout<<x.cena<<endl;;::add_data(x);//вызов
метода класса и добавление элемента в список
}
}
{cout<<"File
C:\\ftext_in.txt ne naiden"<<endl;
}
}
sspisok::peremesh()
{int n=0;*Q2;//буфер=new
spisok;=BegQ;//смещение указателя(Q->next!=NULL)//пока не начало списка
{
n++;(Q->next->data.class_==5)
{ cout<<"
n="<<n<<endl;=Q->next;>next=Q->next->next;->next=BegQ;=Q2;
}
=Q->next;//переход на следующую
позицию
}
}
sspisok::udalenie()
{spisok *p;n=0;((BegQ!=NULL)&&(EndQ!=NULL))
{=BegQ;(p!=NULL)
{n++;
(p->data.kolichestvo_s==0)
{sspisok::delete_data(n);-;//возврат
индекса к предыдущему элементу
}=p->next;
};
}((BegQ==NULL)&&(EndQ==NULL))//если
список пустой
{cout<<"Spisok pustoi ili
ne sozdan"<<endl;
}
Приложение А(продолжение)
if((BegQ->data.kolichestvo_o==NULL)&&(EndQ->data.kolichestvo_o==NULL))//проверка
на пустоту списка
{cout<<"Spisok
pustoi"<<endl;//вывод соотв. сообщения
};
}main(array<System::String ^>
^args)
{sspisok x;//объект классаvibor;//для
менюi,n;//i-для циклов,n-для количесваj;//для прочих целей=NULL;//обнуление
указателя=NULL;//обнуление указателя=NULL;//обнуление указателя
//////////////////////////меню///////////////////////////
(vibor!=0)
{system("cls");<<"Menu"<<endl;<<"1.Sformirovat
spisok"<<endl;<<"2.Dobavit
zapis'"<<endl;<<"3.Udalit'
zapis'"<<endl;<<"4.Otobrazit
spisok"<<endl;<<"5.Skoirovat v Fail"<<endl;<<"6.Skopirovat
v Massiv"<<endl;<<"7.Otobrazit
Massiv"<<endl;<<"8.Sortirovat
Massiv"<<endl;<<"9.Skopirovat iz Faila"<<endl;<<"10.Nayti
zapis' v spiske"<<endl;<<"11.Udalenie otelei bez
svobodnih nomerov"<<endl;<<"12.Peremeshenie 5-ti
zvezdochnih gostinic"<<endl;<<"0.Vyhod"<<endl;<<endl<<endl;<<"Vyberite:_";>>vibor;("cls");(vibor==1)//формирование
списка
{x.form();//формирование списка
}
(vibor==2)//ввод данных
{if((BegQ!=NULL)&&(EndQ!=NULL))
{cout<<"Skolko Zapisey
vvesti"<<endl;<<"n=";>>n;//ввод количества
(i=0;i<n;i++)
{<<"Nazvanie
-";>>Data.nazvanie;//ввод
данных<<"Klass-";>>Data.class_;<<"Obshee
kolichestvo-";>>Data.kolichestvo_o;//ввод
данных<<"Kolichestvo
svobodnih-";>>Data.kolichestvo_s;//ввод
данных<<"Cena-";>>Data.cena;.add_data(Data);//добавление
элемента в список
}
}((BegQ==NULL)&&(EndQ==NULL))
{cout<<"Spisok ne
sozdan"<<endl;
}
}(vibor==3)//удаление элемента
{if((BegQ!=NULL)&&(EndQ!=NULL))
{cout<<"Vvedite nomer
zapisi kotoruyu nuzhno
udalit"<<endl;<<"n=";>>j;//ввод номера
удаляемого элемента.delete_data(j);//удаление элемента
}((BegQ==NULL)&&(EndQ==NULL))
{cout<<"Spisok ne
sozdan"<<endl;
}
}
(vibor==4)//вывод элементов на экран
{x.show_sp();//вывод списка на экран
}
Приложение А(продолжение)
(vibor==5)//копировать в файл
{if((BegQ!=NULL)&&(EndQ!=NULL))
{cout<<"Dannie skopirovani v fail, po
adresu C:\\ftext_from.txt"<<endl;.sp_copy_file();//копирование
данных в список
}((BegQ==NULL)&&(EndQ==NULL))
{cout<<"Spisok ne
sozdan"<<endl;
}
}
(vibor==6)//копировать в массив
{if((BegQ!=NULL)&&(EndQ!=NULL))
{x.sp_copy_mas();//копирание данных в
массив<<"V spiske "<<nn<<" -
elementov"<<endl;//вывод сообщения о количестве элементов<<"Spisok
skopirovan v massiv"<<endl;
}((BegQ==NULL)&&(EndQ==NULL))
{cout<<"Spisok ne
sozdan"<<endl;
}
}
(vibor==7)//вывод массива
{if((BegQ!=NULL)&&(EndQ!=NULL))
{cout<<"Vivod
massiva"<<endl;.show_mas(nn);//вывод массива на экран
}((BegQ==NULL)&&(EndQ==NULL))
{cout<<"Spisok ne
sozdan"<<endl;
}
}
(vibor==8)//сортировать массив
{if((BegQ!=NULL)&&(EndQ!=NULL))
{x.sort_mas(nn);//сортировка
массива<<"Massiv
otsortirovan"<<endl;.show_mas(nn);//вывод массива на экран
}((BegQ==NULL)&&(EndQ==NULL))
{cout<<"Spisok ne
sozdan"<<endl;
}}
Приложение А(продолжение)
if(vibor==9)//сформировать файл из списка или
добавить элементы в список из файла
{if((BegQ!=NULL)&&(EndQ!=NULL))
{x.file_copy_sp();
}((BegQ==NULL)&&(EndQ==NULL))
{cout<<"Spisok ne
sozdan"<<endl;
}
}
(vibor==10)//найти элемент в массиве
{if((BegQ!=NULL)&&(EndQ!=NULL))
{cout<<"Vvedite nazvanie gostinici
kotoruiu nuzhno
naiti:_"<<endl;<<"Gostinica-";>>Data.nazvanie;//ввод
данных.find_data(Data.nazvanie);//поиск элемента
}((BegQ==NULL)&&(EndQ==NULL))
{cout<<"Spisok ne
sozdan"<<endl;
}
}
(vibor==11)
{if((BegQ!=NULL)&&(EndQ!=NULL))
{ x.udalenie();<<"Gostinici bez
svobodnyh nomerov udaleny"<<endl;.show_sp();
}
}(vibor==12)
{if((BegQ!=NULL)&&(EndQ!=NULL))
{ x.peremesh(); x.peremesh();<<"5-ti
zvezdochnie gostinici v nachalo spiska"<<endl;.show_sp();
}
}();
}
}
Приложение Б
Рисунок Б.1 - Блок-схема основной части
программы
Рисунок Б.2- блок-схема функции «form
()»
Рисунок Б.3- блок-схема функции «add_data
()»
Рисунок Б.4- блок-схема функции « delete_data
()»
Рисунок Б.5- блок-схема функции « show_sp
()»
Рисунок Б.6- блок-схема функции «sp_copy_file()»
Рисунок Б.7-
блок-схема
функции
«sp_copy_mass()»
Рисунок Б.8- блок-схема функции «show_mass()»
Рисунок Б.9- блок-схема функции «sort_mass()»
Рисунок Б.10-
блок-схема
«file_copy_sp()»
Рисунок Б.11- блок-схема функции «find_data()»
Рисунок Б.12- блок-схема функции «udalenie
()»
Рисунок Б.13- блок-схема функции «peremesh
()»