Разработайте программу, демонстрирующую применение класса.
ВАРИАНТЫ
Номер варианта |
Класс варианта |
Операции перегружаемые |
1 |
Линейный многочлен N – ой степени (узел содержит коэффициент, степень) |
+ Сложить два многочлена = Присвоить |
2 |
Линейный многочлен N – ой степени (узел содержит коэффициент, степень) |
- Дифференцировать многочлен < Сравнить два многочлена |
3 |
Линейный многочлен N – ой степени (узел содержит коэффициент, степень) |
= = Равенство двух многочленов >> копирование многочлена
|
4 |
Массив одномерный динамический целых чисел |
[] индексация элемента + Слияние двух массивов |
5 |
Массив одномерный динамический вещественных чисел |
- Удаление из одного массива элементов другого = = Равенство двух массивов
|
6 |
Массив двухмерный n*n целых чисел |
* умножение матрицы на числовую константу (константа может быть и справа и слева) +сложение двух матриц
|
7 |
Множество целых чисел |
|| Объединение двух множеств = = Равенство двух множеств |
8 |
Множество символов |
&& Пересечение двух множеств > Cравнение двух множеств |
9 |
Множество целых чисел |
- Дополнение одного множества до другого < Сравнение двух множеств |
10 |
Очередь |
>>Добавить элемент в очередь [] доступ к первому элементу очереди |
11 |
Линейный список |
[] доступ к элементу в заданной позиции + Добавить элемент в конец списка |
12 |
Вектор задан координатами своих вершин |
* Перпендикулярны ли два вектора + Сумма двух векторов
|
13 |
Дата задана тремя параметрами: день, номер месяца, год |
- Разность между двумя датами + Получение новой даты, отстоящей от исходной на заданное количество дней |
14 |
Строка, завершающаяся терминальным нулем |
+ Конкатенация строк [] Вставить новый символ в указанную позицию |
15 |
Линейный список Стек |
>> Включить элемент в стек - Исключить элемент из стека = Присваивание |
Лабораторная работа №10(дерево)
Тема: Двоичное бинарное дерево
Цель: получение навыков по созданию иерархических структур
ЗАДАНИЕ
Разработать класс бинарное дерево, включив в него методы: конструктор по умолчанию и вывод бинарного дерева, используя прямой обход дерева.
Разработать производный класс для дерева определенного вариантом. В класс включить методы:
Конструктор с параметром (для сбалансированного дерева) – число узлов.
Копирующий конструктор
Деструктор
Методы для операций, определенных в варианте.
В нечетном варианте использовать бинарное дерево поиска, а в четном – сбалансированное бинарное дерево поиска (ЕСЛИ ВАРИАНТ НЕ ПРЕДУСМАТРИВАЕТ СВОЮ СТРУКТУРУ).
Варианты
1.Информационная часть узла содержит целое значение.
Определить сумму значений находящихся в листьях дерева.
Обойти дерево алгоритмом прямого обхода
Удалить максимальный элемент дерева (считать, что такой элемент один)
Вставить новый элемент
Информационная часть узла содержит символьное значение.
Определить сумму цифр, содержащихся в дереве, применив алгоритм симметричного обхода
Найти первое вхождение заданного символа и вернуть указатель на узел
Найти максимальное значение среди листьев дерева
Информационная часть узла содержит целое значение.
Определить среднее арифметическое всех узлов непустого дерева
Найти сумму максимального и минимального элементов дерева
Удалить самый левый лист дерева
Информационная часть узла содержит слово.
Определить длину пути в дереве от корня до узла с заданным значением.
Определить число листьев в дереве
Определить высоту дерева
Информационная часть узла содержит символьное значение.
Определить уровень, на котором находится узел с заданным значением.
Вставить новый узел в дерево
Удалить узел, содержащий заданное значение (первое вхождение)
Информационная часть узла целое число.
Заменить в дереве все отрицательные значения на их модули
Найти минимальное значение, хранящееся в дереве.
Обойти дерево “в ширину”.
Информационная часть узла - символ.
Выполнить алгоритм обратного обхода дерева.
Определить, количество цифр в дереве.
Удалить узлы, содержащие цифры.
Информационная часть узла содержит символ значение.
Определить, содержится ли в дереве заданный символ.
Вывести значения всех узлов поддерева с заданным значением узла.
Определить высоту поддерева с заданным значением узла.
Информационная часть узла содержит текст и количество в нем цифр
Определите количество узлов, текст которых содержит максимальное число цифр.
Удалить узел, не содержащий в тексте цифр.
Обойти дерево в обратном порядке и вывести значения его узлов.
Англо русский словарь построен как двоичное дерево поиска, упорядоченное по английскому слову. Каждый узел дерева содержит информацию: английское слово, русское слово, количество обращений.
Включить узел в дерево
Сформировать новое двоичное дерево поиска, упорядочивая узлы по числу обращений
Вывести новый и старый словарь по иерархии сверху вниз.
На междугородней телефонной станции картотека абонентов, содержащая сведения: номер телефона и сведения о владельце, организована как бинарное упорядоченное дерево.
Определите операции:
Формирование списка абонентов, упорядоченного по номеру телефона.
Поиск сведений о владельце по введенному номеру
Формирует извещение на оплату разговора по введенному номеру и времени за разговор
Автоматизированная информационная система на железнодорожном вокзале содержит сведения об отправлении поездов дальнего следования. Для каждого поезда указывается: номер поезда, станция назначения, время отправления. Данные охраняться в виде сбалансированного двоичного дерева.
Определите операции:
Поиск информации по номеру введенного поезда
Формирование списка поездов, отправляющихся с заданной станции
Определить, количество поездов, которые следуют до заданной станции.
Формулу вида
<формула>::=цифра | (<формула> знак <формула>)
<знак>::= +|*|-
можно представить в виде бинарного дерева. Формула из одной цифры – это дерево из одной вершины. Формула вида F1 # F2 представлена деревом, у которого в корне – операция #, левое дерево это формула F1 , а правое – F2.
Определите операции:
Построить дерево указанного вида
Вычислить значение дерева
Распечатать формулу дерева
Составить программу формирующую “перекрестные ссылки”, т.е. печатающую список слов, которые встречаются в анализируемом файле. А для каждого слова - список номеров строк, в которых это слово встречается. Информация по слову хранится в узле бинарного дерева поиска, упорядоченного по значению слова. Список номеров строк храниться в отдельном связанном списке, указатель на который хранит соответствующий узел дерева.
Построить дерево указанного вида
Найти слово, встретившееся в тексте в максимальном числе строк
Вычислить значение дерева
Распечатать формулу дерева
Лабораторная работа 11
Тема: Структура данных – файл. Файловые потоки С++
Цель. Получение навыков по обработке данных, хранящихся во внешней памяти.
Задание 1. Создание модуля с операциями над текстовым файлом.
Разработать функции для выполнения операций над текстовым файлом С++:
создание текстового файла, содержащего числовые значения по одному на строку;
вывод содержимого текстового файла;
добавление новой записи в конец файла:
разработать функции для дополнительных операций, указанных в варианте
Разработать приложение и выполнить тестирование всех функций.
Создать модуль и перенести в него все отлаженные функции. Исключить функции из приложения. Отладить приложение, подключив к нему модуль с функциями.
Разработать функции для реализации дополнительных операций, определенных вариантом и сохранить их в модуле с остальными функциями.
Текстовый файл
№ |
Дополнительные операции |
1 |
Удаление значения строки с заданным номером, путем создания нового файла, удаление старого и переименование нового, указав ему имя удаленного файла. |
2 |
Скопировать числа исходного файла, которые кратны 7, в новый файл |
3 |
Добавить в файл новую строку перед первой строкой. Путем создания нового файла. |
4 |
Создать новый файл из значений исходного, записав в него числа, полученные путем деления каждого числа исходного файла на минимальное число, хранящееся в исходном файле. |
5 |
Создать новый файл из значений исходного, умножив каждое число на значение последнего элемента исходного файла. |
6 |
Создать новый файл из значений исходного, умножив каждое число на сумму первого и последнего чисел исходного файла. |
7 |
Создать новый файл из значений исходного, поделив каждое числое на число, равное количеству строк в файле. |
8 |
Создать новый файл из значений исходного, поменяв местами первое число и и последнее. |
9 |
Создать новый файл из значений исходного, заменив все отрицательные числа файла, на квадрат минимального числа исходного файла. |
10 |
Создать новый файл из значений исходного, умножив каждое четное число на максимальное число в файле. |
11 |
Создать новый файл из значений исходного, разделив все нечетные по абсолютной величине числа на среднее арифметическое чисел в файле |
12 |
Создать новый файл из значений исходного, сформировав число по правилу: прибавить к каждому числу первое четное число исходного файла. |
13 |
Создать новый файл из значений исходного, поделив каждое число на наибольший общий делитель чисел файла. |
14 |
Создать новый файл из значений исходного, добавив к каждому числу наибольшее и наименьшее из чисел файла исходного файла. |
15 |
Создать новый файл из значений исходного, увеличив его на среднее арифметическое всех отрицательных чисел исходного файла. |
16* |
Создать новый файл из значений исходного, размещая в одной строке исходное число и через пробел количество цифр в числе. |
17* |
Создать новый файл из значений исходного, размещая в каждой строке три числа: исходное, количество цифр в числе, сумма цифр в числе. |
18* |
Создать новый файл из значений исходного, размещая на строке по три числа из исходного файла. |
19* |
Создать новый файл из значений исходного, размещая на строке значения: количество чисел до конца строки, сами числа через пробел. |
20* |
Создать новый файл из значений исходного, размещая на строке значения: четное число – количество чисел до конца строки, сами числа через пробел.
|
Задание 2. Создание модуля с операциями над двоичными файлами. Файл состоит из записей определенной структуры. Записи имеют ключ, уникальный в пределах файла, создается он как счетчик: количество записей + 1.
Подготовьте тестовые данные в текстовом файле с кодировкой ASCII.
Разработайте структуру записи двоичного файла согласно варианту задания.
Разработайте функции для операций:
преобразование тестовых данных в двоичный файл
отображение всех записей двоичного файла
манипулирование записями в двоичном файле: согласно операций определенных в варианте
Удаление записи производить путем замены на последнюю запись.
Сохраните функции в новом модуле.
Разработать приложение, демонстрирующее выполнение всех операций, подключив к нему модуль с функциями.
№ |
|
|
1 |
Структура записи |
Читательский абонемент: номер читательского - целое пятизначное число, ФИО, Адрес |
Доп. операция |
|
|
2 |
Структура записи |
Счет в банке: номер счета 7 разрядное число, ФИО, Адрес |
Доп. операция |
|
|
3 |
Структура записи |
Владелец телефона: номер телефона – последовательность символов, адрес, ФИО |
Доп. операция |
|
|
4 |
Структура записи |
Владельцев автомобилей. номер машины, марка, сведения о владельце, сведения об угоне (логического типа). |
Доп. операция |
|
|
5 |
Структура записи |
Пациент поликлиники: номер карточки, код хронического заболевания, Фамилия лечащего врача |
Доп. операция |
|
|
6 |
Структура записи |
Товар: название, код – шестиразрядное число, завод изготовитель, цена, страна(название0 |
Доп. операция |
|
|
7 |
Структура записи |
Специализация вуза: код специальности, название вуза, название специальности |
Доп. операция |
|
|
8 |
Структура записи |
Книга: ISBN – двенадцатизначное число, Автор, Название, год издания |
Доп. операция |
|
|
9 |
Структура записи |
Страховой полис: номер, компания, фамилия владельца |
Доп. операция |
|
|
10 |
Структура записи |
Англо – русский словарь: английское слово, русское слово |
Доп. операция |
|
|
11 |
Структура записи |
Железнодорожная справка: номер поезда, пункт отправления, пункт назначения, время отправления |
Доп. операция |
|
|
12 |
Структура записи |
Регистрация малого предприятия: номер лицензии(текстовое значение), название, учредитель, признак действия лицензии(0 действует, 1 отозвана) |
Доп. операция |
|
|
13 |
Структура записи |
Студент: номер зачетной книжки, номер группы, ФИО |
Доп. операция |
|
|
14 |
Структура записи |
Справочная межгорода: код города, название города, страна |
Доп. операция |
|
|
15 |
Структура записи |
Расписание занятий группы: номер группы, Название дисциплины, номер пары, номер недели, номер дня недели, вид занятия, номер аудитории. |
Доп. операция |
|
|
16 |
Структура записи |
Частотный словарь: слово, количество вхождений в текст |
Доп. операция |
Обновить количество вхождений некоторых слов, увеличив их количество на 1. |
|
17 |
Структура записи |
Читательский билет: Номер, инвентарный номер книги, дата выдачи, дата возврата |
Доп. операция |
|
|
18 |
Структура записи |
Вызов такси: Номер, Фамилия водителя, время выезда, отметка о присутствии в гараже |
Доп. операция |
|
|
19 |
Структура записи |
Продажи товаров: Код товара, название, цена, дата продажи. |
Доп. операция |
|
|
20 |
Структура записи |
Сотрудник: Табельный номер, Должность, оклад, количество детей |
Доп. операция |
|
|
Файловые потоки.
Классы потоков
ifstream – класс входных файловых потоков ( для чтения данных)
ostream – класс выходных файловых потоков (для создания файлов и добавления записей)
fstream – класс двунаправленных потоков (для обеих типов операций)
Файл – это экземпляр соответствующего класса.
Операции над файлами
Файл – это экземпляр соответствующего класса – поток..
Создание потока
Способ 1. Без связывания с файлом
ifstream if; // для ввода данных в файл
ostream of; // для чтения данных из файла
fstream ff; // для чтения и записи
Способ 2. Связывая его с файлом
ifstream if(“A.txt”);
ostream of(“A.txt”);
fstream ff(“A.txt”);
Открытие потока и связывание его с файлом
Так как поток это объект класса, то открытие осуществляет метод
open([имя файла,][способ открытия файла])
имя файла – строковое значение, которое задает имя физического файла или переменную типа строка.
Способ открытия файла
Способ открытия файла задается перечисляемой переменной
enum open_mode(app, binary, in, out, trunc, ate),
которая определена в базовом классе ios.
Так как классы ifstream,ofstream, fstream являются производными от класса ios, то при определении экземпляра одного из потоковых классов, обращение к значениям перечисяемой переменной должно идти с указанием класса родителя: ios::app, или ios::in, или ios:out и т.д.
Назначения констант перечисления:
App – открыть файл для записи в конец
Out - открыть файл для создания и записи в начало (указатель на первую запись)
In - открыть файл для чтения из файла с первой записи (указатель на первую запись)
Binary – открыть файл как двоичный (читаем структуры такого же размера как и записали)
Trunc – очистить файл, если он существует
Ate - переместить указатель на конец файла.
При открытии файла можно задавать несколько режимов открытия в одной строе, в этом случае режимы разделяются символом | .
open(“F.txt”,ios::out|ios::binary|ios::trunk)
Другие методы для работы с файлом
сlose() - закрытие файла;
is_open() – если файл открыт, то возвращает true
rdbuf() – возвращает указатель на буфер ввода – вывода.
Поток открывается в определенном режиме, для чтения, записи, или обеих операций.
Флаги для способов открытия файла через объект ios Примечание. Для экземпляров класса ifstream может быть опущен режим ios::in, а для ofstream режим ios::out. |
|||||
|
binary |
in |
out |
trunc |
app |
Запись(w) |
|
|
* |
|
|
Добавление в конец(a) |
|
|
* |
|
* |
Запись с отсечением(w) |
|
|
* |
* |
|
Чтение ® |
|
* |
|
|
|
Чтение и запись (r+) |
|
* |
* |
|
|
Запись, чтение, отсечение(w+) |
|
* |
* |
* |
|
Запись(wb) |
* |
|
* |
|
|
Добавление в конец(ab) |
* |
|
* |
|
* |
Запись с отсечением(wb) |
* |
|
* |
* |
|
Чтение(rb) |
* |
* |
|
|
|
Чтение и запись(r+b) |
* |
* |
* |
|
|
Запись, чтение, отсечение(w+b) |
* |
* |
* |
* |
|
Способ 1.
ifstream if;
if.open(“A.txt”); // по умолчанию для чтения
ostream of;
of.open(“A.txt”); // по умолчанию для записи
ifstream ff
ff.open(“A.txt”); по умолчанию для записи и чтения
Способ2.
ifstream if(“A.txt”, ios::in|ios::trunc); для записи
ofstream o(“A.txt”, ios::out|ios::trunc); для чтения
ifstream ff(“A.txt”, ios::in| ios::out ); для модификации
Ввод – вывод потоковый
Методы обмена с потоками
Операция извлечения из потока >>. Аналогично извлечению из стандартного потока cout.
Пример.
ofstream o(“A.txt”, ios::out|ios::trunc);
int x;
o>>x;
Операция включения в поток<<. Аналогично включению в стандартный поток cin.
ifstream if(“A.txt”, ios::in|ios::trunc);
int x=10;
if<<x;
Методы для чтения из потока класса istream
gcount() |
|
get(c) |
|
get(buf, num, lim=’\n’) |
|
getline(buf, num, lim=’\n’) |
|
ignore(buf, num, lim=’\n’) |
|
peek() |
|
putbuck (c) |
|
read(buf,num) |
|
readsome(buf,num) |
|
seekg(pos) |
|
seekg(offs, org) |
|
tellg() |
|
unget() |
|
Методы неформатированного вывода класса ostream
flush() |
|
put( c ) |
|
seekg(pos) |
|
seekg(offs, org) |
|
tellg() |
|
write(buf,num) |
|
|
|
Закрытие файла
ofstream o(“A.txt”, ios::out|ios::trunc);
int x;
if>>x;
if.close(); //закрытие
Методы для управления ошибками потоков
В базовом классе ios определено поле state, которое хранит состояние потока в виде совокупности битов. Каждая совокупность отвечает за определенное состояние. Для доступа к состоянию используются методы потока.
Прототип метода |
Описание действия |
int rdstate() |
текущее состояние потока |
int eof() |
результат 0, если не достигнут конец файла |
int fail() |
результат 0, если ошибка: при форматировании (флаг failbit=1), или от неисправности оборудования (hardfail), или серьезная ошибка в потоке(badbit=1) |
int bad() |
результат 0, если ошибка: при форматировании или от неисправности оборудования |
int good() |
результат 0, если флаги ошибок failbit, badbit, hardfail сброшены в 0 |
void cleare(int =0) |
очистить флаг состояния |
operator void*() |
результат NULL, если установлен хотя бы один бит ошибки |
operator !() |
результат not NULL, если установлен хотя бы один бит ошибки |
Форматирование данных
Способ 1. Флаги
В классе ios имеется поле long х_Flags, отдельные биты которого являются значениями флагов.
Флаги форматирования
Флаг |
Положение бита |
Описание действия флага при установке бита |
left |
0х0002 |
выравнивание по левому краю |
right |
0х0004 |
выравнивание по правому краю |
dec |
0х0010 |
десятичная система счисления |
hex |
0х0040 |
шестнадцатеричная система счисления |
uppercase |
0х0200 |
символы верхнего регистра |
showpos |
0х0400 |
выводить знак для положительных чисел |
scientific |
0х0800 |
выводить в формате с плавающей точкой |
fixed |
0х1000 |
выводить в форме с фиксированной точкой |
Методы установки значений флагов
Прототип метода |
Описание действия |
long ios::flags(long) |
присваивает флагам значение параметра Пример. Выводить в 16 системе, буквами верхнего регистра long a=27,b=11; cout.flags(ios::hex|ios::showbase|ios::uppercase); cout<<a<<’ ’<<b; Результат: 0Х1B 0ХB |
long ios::setf(long, long) |
присваивает флагам, биты которых установлены в первом параметре значение соответствующих битов второго параметра
|
long ios::setf(long) |
устанавливает флаги, биты которых установлены в параметре
|
Способ 2. Поля и методы форматирования класса ios
Поля класса ios для форматирования вывода
Поле |
Применение |
int х_width |
минимальная ширина поля ввода |
int precision |
количество цифр в дробной части |
int x_fill |
символ заполнения поля ввода |
Методы управления полями форматирования
Метод |
Результат метода |
int ios::width() |
ширина поля |
int ios::width(int) |
установка размера поля вывода Пример 1. long a=27,b=11; cout.width(7); cout.flags(ios::hex|ios::showbase|ios::uppercase); int w=cout.width();//перед выводом берем значение поля х_width cout<<a<<' '<<b;
cout<<"w="<<w; Результат: w=7 Пример 2. long a=27,b=11; cout.width(7); cout.flags(ios::hex|ios::showbase|ios::uppercase); cout<<a<<' '<<b; int w=cout.width();//после вывода берем значение поля х_width cout<<"w="<<w; Результат: w=0 так как этот флаг применяется к одному выводу и сразу сбрасывается |
int ios:: precision() |
размер точности для вывода вещественных чисел |
int ios:: precision(int) |
устанавливает размер точности при выводе вещественных чисел
|
char fill() |
символ установленный для заполнения |
char fill(char) |
устанавливает символ заполнения Пример. Заполнение пустых байтов в числе нулями cout.width(7); cout.flags(ios::hex|ios::showbase|ios::uppercase); int w=cout.width(); cout.fill('0'); cout<<a; cout<<"w="<<w; Вывод в 7 позиций значения 0Х1B, т.е. недостающие заполнятся нулями Результат. 0000Х1B |
Способ 3. Манипуляторы
Это функции, которые можно включать в цепочку операторов << и >>.
Функция |
Описание |
dec |
при вводе и выводе устанавливает флаг десятичной системы |
hex |
при вводе и выводе устанавливает флаг шестнадцатеричной системы |
endl |
при выводе включает в поток символ новой строки и выгружает буфер |
ends |
при выводе включает в поток нулевой символ |
flush |
при выводе выгружает буфер |
|
Пример. cout<<27<<’ ‘<<hex<<27<<endl; cout<<flush; |
Пример.Операции с текстовым файлом.
#include "stdafx.h"
#include "fstream"
#include "iostream"
using namespace std;
//создание текстового файла
//Структура файла: в строке одно число,
//строка завершается символом конца строки
void inpfiletxt(ofstream &fout,char *namefile)
{
fout.open(namefile,ios::out|ios::trunc);
for(int x=1;x<=10;x++)
{
fout<<x<<endl;
}
fout.close();
}
//вывод содержимого текстового файла
//чтение числа и символа конца строки
//чтобы обработать до конца файла
void outfiletxt(char *namefile)
{int x;
ifstream fin;
cout<<endl;
fin.open(namefile,ios::in);
while(!fin.eof())
{
fin>>x;
fin.get();
cout<<x;
}
fin.close();
}
//добавление записи в конец файла
void appfiletxt(ofstream &fout,char *namefile,int x)
{
fout.open(namefile,ios::out|ios::app);
fout<<x;
fout.close();
}
//прочитать запись по заданному номеру
void seekNtextfile(char *namefile,int n)
{ int x;
ifstream fin;
fin.open(namefile,ios::in);
int i;
for (i=1;(i<n && (!fin.eof()));i++)
{
fin>>x;
fin.get();
}
cout<<endl;
while(!fin.eof()&& (i==n))
{
fin>>x;
fin.get();
cout<<x;
i++;
}
fin.close();
}
int _tmain(int argc, _TCHAR* argv[])
{ ofstream fout;
inpfiletxt(fout,"A.txt");
ifstream fin;
outfiletxt("A.txt");
appfiletxt(fout,"A.txt",100);
outfiletxt("A.txt");
seekNtextfile("A.txt",4);
cin.get();
return 0;
}
Пример. Операции с двоичным файлом
#include "stdafx.h"
#include "iostream"
#include "fstream"
#include "string"
using namespace std;
//структура записи в двоичном файле
struct record
{int key;
char info[10];
};
void create(char *namefile);
void vivod(char *namefile);
void Append(char *namefile);
void ChengeRecord(int key,char *namefile);
int main(int argc, char* argv[])
{char *namefile="bin.dat";
cout<<"Create file"<<endl;
create(namefile);
cout<<"Show file"<<endl;
vivod(namefile);
cout<<endl;
cout<<"Append new file"<<endl;
Append(namefile);
vivod(namefile);
cout<<endl;
cout<<"update first record"<<endl;
ChengeRecord(0,namefile);
vivod(namefile);
cin.get();
cin.get();
return 0;
}
//добавление новой записи в конец вайла
void Append(char *namefile)
{ ofstream fout(namefile,ios::out|ios::app|ios::binary);
record r;
int l;
cout<<"key=";
cin>>r.key;
cout<<"info";
cin>>r.info;
l=strlen(r.info);
r.info[l-1]='\0';
fout.write((char *) &r, sizeof r);
}
//создание файла из трех записей
void create(char *namefile)
{
ofstream fout(namefile,ios::binary|ios::out);
record r;
int l;
for(int i=0;i<3;i++)
{ cout<<"key=";
cin>>r.key;
cout<<"info";
cin>>r.info;
l=strlen(r.info);
r.info[l-1]='\0';
fout.write((char *) &r, sizeof (r));
cin.get();
}
fout.flush();
fout.close();
}
//чтение файла пока указатель не станет 0
void vivod(char *namefile)
{ ifstream fin(namefile,ios::binary|ios::in);
record r;
while (fin.read((char *) &r, sizeof r))
{cout<<'\n';
cout<<r.key<<' ';
cout<<r.info<<' ';
}
fin.close();
}
//изменение записи с заданным номером двустороннем потоке
void ChengeRecord(int pos,char *namefile)
{ fstream fdirect(namefile,ios::binary|ios::out|ios::in);
record r;
fdirect.seekg(pos*sizeof(r),ios::beg);
fdirect.read((char *) &r, sizeof r);
fdirect.seekg(-sizeof(r),ios::cur);
strcpy(r.info,"****");
fdirect.write((char *) &r, sizeof r);
// fdirect.close();
}
}
Лабораторная работа 12
Тема: Хеширование для организации быстрого поиска данных.
Цель: Получить навыки по разработке хеш таблиц.
Задание
Разработайте шаблонный класс – хеш таблица, для поиска информации в коллекциях данных с помощью хеш функции. Хеш функцию подберите самостоятельно.
Разработайте приложение, которое использует хеш таблицу для организации прямого доступа к элементам множества (массив данных), структура элементов которого приведена в варианте. Множество реализуйте через класс - шаблон с операциями вставки, удаления, поиска, вывода и включите в него хеш таблицу. Предусмотрите возможность создания наследников хеш-таблицы.
Разработайте такие тесты, чтобы возникли коллизии.
Выведите список индексов, которые формируются при вставке элементов в таблицу.
ВАРИАНТЫ
№ |
Метод хеширования (способ реализации коллизий) |
Структура элемента множества(ключ – подчеркнутое поле) |
1 |
С открытой адресацией (увеличение на 1) |
Читательский абонемент: номер читательского - целое пятизначное число, ФИО, Адрес |
2 |
С открытой адресацией(увеличение на номер выполняемого подбора) |
Счет в банке: номер счета 7 разрядное число, ФИО, Адрес |
3 |
С открытой адресацией (двойное хеширование) |
Владелец телефона: номер телефона – последовательность символов, адрес |
4 |
Цепное хеширование |
Владельцев автомобилей. номер машины, марка, сведения о владельце. |
5 |
Цепное хеширование |
Пациент поликлиники: номер карточки, код хронического заболевания, Фамилия лечащего врача |
6 |
Цепное хеширование |
Товар: название, код – шестиразрядное число |
7 |
Цепное хеширование |
Специализация вуза: код специальности, название вуза |
8 |
Открытый адрес(двойное хеширование) |
Книга: ISBN – двенадцатизначное число, Автор, Название |
9 |
Цепное хеширование |
Страховой полис: номер, компания, фамилия владельца |
10 |
Открытый адрес(увеличение на 1) |
Англо – русский словарь: английское слово, русское слово |
11 |
Открытый адрес(двойное хеширование) |
Железнодорожная справка: номер поезда, пункт отправления, пункт назначения, время отправления |
12 |
Цепное хеширование |
Регистрация малого предприятия: номер лицензии, название, учредитель |
13 |
Открытый адрес(двойное хеширование) |
Студент: номер зачетной книжки, номер группы ФИО |
14 |
Цепное хеширование |
Справочная межгорода: код города, название города |
15 |
Открытый адрес(увеличение на 1) |
Проверка проавописания по словарю правильных слов: слово (в тексте найти слова с орфографическими ошибками) |
16 |
Цепное хеширование |
Частотный словарь: слово, количество вхождений в текст |
17 |
|
|
Лабораторная работа 13
Тема. Граф. Операции над графом.
Цель.
Получение практических навыков по созданию и управлению структурой данных – граф
ЗАДАНИЕ
Общие для всех вариантов.
Разработать структуру представления графа согласно варианту.
Разработать процедуру заполнения графа из 10 узлов.
Для каждого варианта
Выполнить задание варианта, разместив, определение его подпрограмм и представления графа, в отдельном модуле (Можно представить на классе).
Создать приложение, демонстрирующее выполнение заданий варианта и общих операций.
При составлении тестов рассмотрите все указанные варианты:
Полный граф (все узлы связаны между собой)
Несвязанный граф – представлен несколькими несвязанными между собой подграфами
Граф не имеет несвязанных компонент и не является полным
ВАРИАНТЫ
1 |
Задание |
Характеристики графа и его представление |
2 |
Выделено некоторое множество узлов. Построение всех возможных путей от заданного исходного узла к заданному конечному узлу, проходящих через выделенное множество узлов |
Неориентированный Невзвешенный Матрица смежности |
3 |
Нахождение фундаментального множества циклов, не проходящих через заданное множество узлов. Исходный узел произвольный. |
Ориентированый Невзвешенный Список смежных вершин |
4 |
В |
Неориентированный Невзвешенный Список смежных вершин |
5 |
Выявление точек сочленения. Удаление узлов – точек сочленения. Поиск кратчайшего пути между узлами, принадлежащими различным подграфам. |
Ориентированный Невзвешенный Список смежных вершин |
6 |
Определить диаметр графа. Эксцентрисистет узла j – расстояние (вес пути) от j – ого узла к наиболее удаленному. Диаметр – наибольший из эксцентриситетов. |
Ориентированный Взвешенный Матрица смежности |
7 |
Определить кратчайшие пути от заданного узла ХО ко всем прочим узлам. Кратчайший путь определяется суммой весов ребер. |
Неориентированный Взвешенный Матрица смежности
|
9 |
Нахождение кратчайших путей во взвешенном графе между заданными вершинами. |
Неориентированный Взвешенный Матрица смежности
|
10 |
Для произвольных узлов найти кратчайший путь с минимальной стоимостью и проходящий (включающий) через некоторое заданное множество узлов. (1,в; 2.а;3.в) |
Неориентированный Взвешенный Список смежных вершин
|
11 |
Определить, какие из ребер можно удалить при соблюдении условия: длины кратчайших цепей от произвольного узла к произвольному узлу остаются прежними. Длина цепи – сумма всех входящих в нее ребер |
Неориентированный Взвешенный Список смежных вершин
|
12 |
Все ребра определенного цвета. Определить, есть ли цепь в графе от истока до стока, окрашенная в один цвет |
Ориентированный Взвешенный Матрица смежности
|
13 |
Все ребра определенного цвета. Задаются два произвольных узла Х и У . Определить все цепи от Х до У, такие, что все ребра, их составляющие окрашены в разные цвета |
НеОриентированный Взвешенный Матрица смежности
|
14 |
Определить, кратчайшие пути от истока до стока |
Ориентированный Взвешенный Список смежных вершин
|
15 |
Нахождение всех циклов в графе, не включающих заданное множество ребер. Граф ориентированный, взвешенный. Все ребра определенного цвета. Определить, есть ли цепь в графе от истока до стока, окрашенная в один цвет |
Ориентированный НеВзвешенный Список смежных вершин
|
16 |
Найти кратчайшие пути от истока графа к заданному узлу. Определить все множество узлов, кратчайшие пути к которым равны найденному |
Ориентированный НеВзвешенный Список смежных вершин
|
17 |
Выявление циклов в графе, включающих заданное множество ребер. |
НеОриентированный НеВзвешенный Матрица смежности
|
18 |
Нахождение цикла в графе с минимальной стоимостью. Стоимость цикла – сумма весов ребер. Исходный узел произвольный. |
Ориентированный Взвешенный Матрица смежности
|
19 |
Определить мосты в графе. Запаралелить мосты таким образом, чтобы при удалении моста не увеличивалось число компонент связности графа. При этом должно сохраниться направление перемещения по графу |
Ориентированный НеВзвешенный Матрица смежности
|
20 |
Граф неориентированный. Медиана - узел, сумма расстояний от которого до остальных узлов минимальна. Центр графа – узел, кратчайшее расстояние от которого до наиболее удаленного от него узла является минимальным. Определить медиану. Определить множество центральных узлов |
НеОриентированный НеВзвешенный Матрица смежности
|
21 |
Поиск истока в ориентированном графе. Исток - узел, от которого достижимы все узлы графа. Найти все истоки графа. |
Ориентированный НеВзвешенный Список смежных вершин
|
ыявление
мостов в графе. Определение кратчайшего
пути от узла ХО к узлу УО: ХО и УО
принадлежат: Одному подграфу Различным
подграфам Различным подграфам,
образующим последовательность
ХО---------------- ---------------- ∙ ∙ ∙ ∙ УО
Лабораторная работа 14
Тема. Шаблонные классы. Использование STL
Цель.
Получение практических навыков по использованию классов и алгоритмов STL при решении практических задач
Задание 1. Разработать шаблон контейнера и продемонстрировать его применение к стандартным типам и пользовательскому типу (классу).
Разработать шаблонный класс контейнер, указанного в варианте типа.
Разработайте консольное приложение, демонстрирующее работоспособность класса для стандартных типов: целого и вещественного.
Разработайте класс варианта, со списком полей определенным в варианте, методом вывода на экран значения класса и другими необходимыми методами.
Измените приложение, разработанное согласно п.2 данного задания, так, чтобы продемонстрировать возможность применения контейнера к классу.
Примечание. Для представления текстовых данных использовать динамическую память. В классе предусмотреть метод копирующего конструктора и перегрузить операцию присваивания.
Операции над элементами контейнера.
Для стека: втолкнуть элемент, вытолкнуть, определить количество элементов в стеке.
Для очереди: добавить, удалить, определить значение первого элемента.
Для списка: вставить элемент в заданную позицию (с проверкой позиции), удалить элемент в позиции, определить значение в позиции.
Для дека (очередь с двумя вершинами): вставить элемент в дек, удалить элемент из дека, определить значение последнего узла.
Задание 2. Применить контейнер STL.
Разработать новое консольное приложение, демонстрирующее применение контейнера STL, соответствующего типу контейнера, определенного в варианте.
Предусмотреть демонстрацию всех операций, допустимых над структурой, которая определена контейнером.
Номер |
Тип контейнера |
Класс |
1 |
Стек |
Студент (Фамилия, имя, номер группы) |
2 |
Список |
Книга (Автор, Название, Год издания, издательство) |
3 |
Очередь |
Детская игрушка (Название, Цена, Возрастная группа) |
4 |
Дек |
Комплексное число (действительная часть, мнимая часть) |
5 |
Стек |
Дата (День, Название месяца, Год) |
6 |
Список |
Сотрудник (Фамилия, Имя, должность) |
7 |
Очередь |
Тур (Страна, Время пребывания, Стоимость) |
8 |
Дек |
Товар (Название, Производитель, Цена) |
9 |
Стек |
Расписание поездов (Номер поезда, Пункт назначения, Время отправления) |
10 |
Список |
Штатное расписание(Название должности, оклад, количество единиц) |
11 |
Очередь |
Материальная ценность (Название, Инвентарный номер, Цена, Дата, Номер комнаты) |
12 |
Дек |
Страна(Название, Материк, Численность, Общая площадь) |
13 |
Стек |
Счет фактура (Название организации отпускающей товар, Номер, Дата, Сумма, Название организации покупающей товар) |
14 |
Список |
Успеваемость школьника (Фамилия, Название дисциплины, Оценка, Дата, Номер урока) |
Список литературы
Герберт Шилдт «Искусство программирования на С++» Издательство: БХВ-Петербург.: 2005.
Герберт Шилдт С++ Базовый курс, Издательство Вильямс, 3-е издание.: 2010 г.
Герберт Шилдт С++ Методики программирования Шилдта, Изд.:OZON.RU, 2010 г.