41885

Информатика и системы вычисления. Сборник лабораторных работ.

Лабораторная работа

Информатика, кибернетика и программирование

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

Русский

2013-10-26

108.14 KB

13 чел.

Лабораторная работа 7

Тема. Линейные двунаправленные связанные списки

Цель.

  1.  Получить практические навыки по созданию и по управлению двунаправленными списками

Задание

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

Требования  к разработке.

Во всех вариантах для основного списка реализовать операции:

  1.  вывод списка от первого элемента к последнему;
  2.  вывод списка от последнего элемента к первому;
  3.  создание списка из n элементов, вставляя новый элемент перед первым элементом;

а так же дополнительные операции, определенные заданием варианта.

ВАРИАНТЫ

Вариант

Вид списка

Тип информационной части узла списка

Дополнительные Операции

1.

Список с двумя указателями

Номер абонемента, Название книги, дата выдачи, дата возврата, дата фактического возврата.

1. Вставить новый узел  в список после последнего узла с таким же номером абонента(дата фактического возврата еще не заполнена).

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

3. Удалить узлы, в которых дата возврата и дата фактического возврата совпадают.

4. Определить количество книг, заданного абонемента.

2.

Список с головным элементом

Номер мед. полиса, Дата обращения, Код диагноза (число).

5. Вставка нового узла перед первым узлом с заданным значением Мед. полиса, если такого нет, то узел вставить в конец списка.

6. Удаление из списка всех узлов с заданным значением Кода диагноза.

7. Переместить все узлы с одинаковым  мед. полисом в новый список.

8. Определить количество обращений в одну и туже дату с одним и тем же диагнозом.

3.

Циклический список с указателем на вершину

Номер счета в банке, дата, вид операции (приход или расход), сумма вклада.

Примечание:

По одному счету может быть несколько узлов.

9. Вставка нового узла перед первым узлом.

10. Удаление сведений по счету (всех узлов), у которого общая сумма вклада равна нулю ( сумма по приходу, минус сумма по расходу).

11. Создать новый список из исходного, которого будет содержать остаток по всем видам операций одного счета, указав вид операции – приход, и текущую дату.

12. Определить количество узлов по одному номеру счета.

4.

Циклический список с головным элементом

Номер автобусного маршрута, время отправления (целое число), номер автобуса, стоимость одной поездки, дата отправления.

Примечание:

По одному номеру автобуса может быть несколько узлов.

13. Вставить новый узел после последнего узла с заданным номером автобуса.

14. Удалить все узлы заданного автобуса.

15. Подсчитать, сколько раз автобус выходил на маршрут в течении заданного дня.

16. Сколько рейсов в течении указанного дня сделал каждый автобус.

5.

Список с двумя указателями

Код товара, дата продажи, цена, отметка о возврате.

17. Отсортировать список, располагая элементы в хронологическом порядке.

18. Удалить все узлы по заданному товару, проданному в указанную дату.

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

20. Определить, какой вид товара чаще возвращают.

6.

Список с головным элементом

Номер железнодорожного билета, станция назначения, номер поезда, номер вагона, номер места, стоимость проезда, дата продажи, дата отправления поезда, время в пути.

21. Вставить новый узел в список, упорядоченный по номеру вагона.

22. Удалить сведения о билетах, пассажиры которых добрались уже до места (оценка по текущей дате).

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

24. Определить номер вагона в который продано больше всего билетов.

7.

Циклический список с указателем на вершину

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

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

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

27. Удалить информацию обо всех автомобилях заданной марки из исходного списка, поиск первого узла модельного ряда, осуществить с помощью нового списка.

28. Определить, каких автомобилей меньше всего. Если таких автомобилей несколько, то указать марку первого встреченного.

8.

Циклический список с головным элементом

Марка автомобиля, страна изготовитель, год выпуска, цена. Дата продажи (заполняется не сразу).

29. Упорядочить созданный список из n узлов  так, чтобы узлы были упорядочены по стране изготовителю (будут сформированы подсписки по стране).

30. Вставить новый узел со сведениями об автомобиле какой-то страны в начало своего подсписка.

31. Установить дату продажи проданному автомобилю.

32. Удалить все узлы по проданным автомобилям.

9.

Список с двумя указателями

Инвентарный номер книги, указатель на список областей знаний (к которым относится книга, при создании списка указатель равен NULL), Автор, Название, Год издания.

Примечание. Список областей знаний это тоже линейный список, информационная часть которого содержит название области.

33. Вставить новый узел со сведениями о книге после последнего узла.

34. Сформировать новый список из значений списков по областям знаний, включив название области только один раз.

35. Удалить узлы  со сведениями по книгам определенного автора и изданные после указанного года.

36. Часть списка, начиная с узла с заданным номером и до конца списка, перенести в начало списка

10.

Список с головным элементом

Код товара, дата продажи, цена, отметка о возврате, дата возврата.

37. Упорядочить список по правилу: сначала проданные, но не возвращенные, а затем возвращенные.

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

39. Удалить товар, который продан до указанной даты.

40. Определить количество проданного в указанную дату товара.

11.

Циклический список с указателем на вершину

Номер мед. полиса, указатель на линейный список (узлы которого содержат: Код заболевания и Дата регистрации заболевания зарегистрировано), фамилия больного.

41. Вставить в начало списка заболеваний пациента новый узел.

42. Сформировать новый список, включив в него информацию о пациентах, у которых зарегистрировано более 5 заболеваний.

43. Удалить из списка кодов заболеваний указанного пациента, узел с указанным кодом.

44. Определить количество заболеваний у заданного пациента.

12.

Циклический список с головным элементом

Номер зач. книжки, Номер группы, Фамилия студента, Указатель на линейный список сведений по результатам сессии (узел этого списка содержит: Название дисциплины, Оценка, Номер семестра).

45. Упорядочить исходный список по номеру группы.

46. Вставить сведения о новом студенте, об успеваемости которого еще нет сведений, перед узлом, номер зачетной книжки в котором меньше номера зач. книжки нового студента.

47. Удалить все сведения о студентах заданной группы.

48. Определить количество групп, в которых сдавали заданный экзамен.

13.

Список с двумя указателями

Номер зач. книжки, Номер группы, Оценка.

49. Вставить новый узел перед первым узлом с таким же ключом, если такого узла еще нет, то вставить перед первым узлом, у которого ключ больше.

50. Удалить узлы с указанным номером зачетной книжки.

51. Сформировать новый список из исходного,  включив в него узлы с оценкой неуд, исключив их при этом из исходного списка.

52. Определить средний балл студента с указанной зачетной книжкой.

14.

Список с головным элементом

Номер телефона (из 7 цифр), время разговора (целое число), номер телефона вызываемого абонента.

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

54. Удалить последний узел  с заданным значением телефона.

55. Подсчитать суммарное время разговора с заданного телефона.

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

Лабораторная работа 8

Тема: Функция -  шаблон. Перегрузка операторов. Перегрузка функций. Рекурсивные функции.

Цель.

  1. получить навыки по разработке и применению функции – шаблона
  2. получить навыки по использованию нестандартных типов;
  3. получить практический опыт по разработке рекурсивных функций.

Задание

  1. Разработайте функцию сортировки массива и протестируйте ее.
  2. Перегрузите функцию сортировки для каждого из указанных в варианте типов элементов.
  3. Разработайте функцию шаблон для сортировки элементов произвольного типа.
  4. Перегрузите (операцию) операции сравнения, которые используются в алгоритме  сортировки для сравнения значений структуры. В сравнении значений типа структура будут использоваться ключи сортировки, которые в структуре определены курсивом.
  5. Реализуйте рекурсии.
  6. Для первого задания на рекурсии разработайте функцию. Опишите рекурсивную зависимость в виде табличной функции. Определите глубину рекурсии.
  7. Для второй задачи разработайте рекурсивную функцию для обработки списковой структуры согласно варианту. Информационная часть узла – простого типа – целого. Для создания списка может быть разработана простая или рекурсивная функция по желанию (в тех вариантах, где не требуется рекурсивное создание списка).
  8. Разработайте программу, демонстрирующую работу всех функций.

Варианты

Номер

Сортировка

Перегрузка функции для типов

Рекурсия

1

обменная

Int, double,

Struct{int x; int y;}

  1. Найти наибольший общий делитель двух целых чисел
  2. Создание и вывод линейного однонаправленного списка из n элементов

2

вставками

Short, float, Struct{double x; int y;}

  1. Найти n-ое число Фибоначчи.
  2. В однонаправленном списке из n элементов найти элемент с заданным значением и вернуть на него указатель.

3

выбора

Char, int,

Struct{short x; int y;}

  1. Определить делится ли число на каждую из своих цифр.
  2. Не используя связанный стек проверить баланс скобок в арифметическом выражении, которое передано как строка.

4

шейкер

Char,double,

Struct{int x; char y;}

  1. Определить является ли текст – палиндромом.
  2. Удалить из связанного однонаправленного списка все элементы, равные заданному.

5

Улучшенная обменная сортировка

Int, short,

Struct{unsigned x; int y;}

  1. Дан массив из n элементов вещественного типа. Вычислить среднее значение всех элементов массива.
  2. Создание связанного стека из n элементов.

6

Вставками с использованием второго массива.

Unsigned long, double,

Struct{char  x[20]; doble y; }

  1. Сколько квадратов можно отрезать от прямоугольника со сторонами a и в.
  2. Удаление связанного стека.

7

Сортировка вставками

Int, short,

Struct{unsigned x; int y; char z}

  1. Найти максимальный элемент в массиве из n элементов.
  2. Создание очереди на однонаправленном списке.

8

Поразрядная сортировка посредством второго массива

Int, long,

Struct{float x; double y; }

  1. Перевести число из 10-системы счисления в систему с основанием В(1<В≤10)
  2. Удаление очереди, реализованной на однонаправленном списке

9

Обменная

Double, char,

Struct{long x; char y; }

  1. Бинарный поиск элемента в массиве
  2. Создание двунаправленного списка.

10

Шейкер сортировка

Unsigned short, long,

Struct{long x; double y; }

  1. Вычислить значение цифрового корня для некоторого целого числа N.
  2. Найти в двухнаправленном списке количество четных элементов.

11

Сортировать по правилу: положительные, отрицательные, нули

Unsigned long, long,

Struct{char x; double y; }

  1. Вычислить x1(x2+x3)(x4+x5+x6)....(x46+x47+...+x55).
  2.  Удаление двунаправленного списка

12

Сортировка методом подсчета.

Unsignedint, long,

Struct{chsr x[5]; double y; }

  1. Сортировка массива по возрастанию
  2. Создать новый однонаправленный список из исходного однонаправленного списка, записав его элементы наоборот.

13

Вставками

Unsigned short,float ,

Struct{long x; double y; }

  1. Дана последовательность из N чисел Х1,Х2,....,ХN. Вычислить значение выражения: Хnn+Xn-1)(Хn+Xn-1+Xn-2)(Хn+Xn-1+Xn-3)... (Хn+Xn-1+Xn-3+...+X1). Массив не использовать.
  2. Удалить из однонаправленного списка нули.

14

Шейкер сортировка

Unsigned short, unsigned long,  Struct{long x; double y; }

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

15

Метод Хоара

short, long, float

Struct{char  x; int y; }

  1. Ханойская башня.
  2. Удалить однонаправленный список.

16

Обменная

Unsigned short, long,

Struct{long x; double y; }

  1. Прохождение лабиринта
  2. Определить симметрично ли число, цифры которого последовательно записаны в узлах двунаправленного списка

Примеры выполнения перегрузки функции и  использования шаблона функции

Перегрузка функции swap

  #include "stdafx.h"

using namespace std;

void  swap(int &x, int &y);

void  swap(float&x, float &y);

void  swap(double &x, double &y);

main()

{

 int x=2,y=3;

swap(x,y);

 float a=5.0,b=7.0;

swap(a,b);

 double c=9.1,d=8.2;

swap(c,d);

cout << c <<' '<< d;

cin.get();

}

void  swap(int &x, int &y)

{

 int w=x;

x=y;

y=w;

}

void  swap(float&x, float &y)

{

 float w=x;

x=y;

y=w;

}

void  swap(double &x, double &y)

{

 double w=x;

x=y;

y=w;

}

Функция шаблон

#include "stdafx.h"

#include "iostream.h"

template<class T>

void swap(T &x,T &y);

int main()

{

int x=2,y=3;

swap(x,y);

float a=5.0,b=7.0;

swap(a,b);

double c=9.1,d=8.2;

swap(c,d);

cout << c <<' '<< d;

cin.get();

cout<<a<<' '<<b;

return 0;

}

template<class T>

void swap(T &x,T &y)

{T z=x;

x=y;

y=z;

}

Перегрузка бинарной операции(внешняя функция)== для структур данных.

#include "stdafx.h"

using namespace std;

struct data{int x;int y;};

int operator == (data z1,data z2);

main()

{ data l={1,2};

data m={1,2};

if (m==l)

  cout<<"yes";

else

 cout<<"no";

 

cin.get();

}

int operator ==(data z1,data z2)

{ if (z1.x==z2.x && z1.y==z2.y)

return 1;

 return 0;

}

Рекурсивная функция

#include "stdafx.h"

#include "iostream.h"

// Задача1.дана последовательность целых чисел, заканчивающаяся нулем

// вывести сначала положительные, а затем отрицательные значения

 void rec11();

//Задача2. Вычислить xn

такое определение алгоритма говорит об его рекурсивной природе

int rec2(int x, int n);

int main()

{

rec11();

cout<<rec2(2,3);

int x=3, n=-3;

if (n<0)

 cout<<(1.0/rec2(x,-n));

return 0;

}

void rec11()

{int n;

cin>>n;

if (n==0)

 return;

else

 if(n>0)

 {

  cout<<n;

  rec11();

 }

 else

 {rec11();

  cout<<n;

 }

}

int  rec2(int x, int n)

{

if (n==0)

{

 if (x==0)

  return -1;

 else

  return 1;

}

else

 // step recursii rec2(x,n)=x*rec2(x,n-1)

 return x*rec2(x,n-1);

 

}

Лабораторная работа №9

Тема: Создание класса. Перегрузка операций.

Задание.

  1. Разработайте АТД согласно варианту задания.
  2. Реализуйте АТД варианта, используя пользовательский тип – класс, в отдельном модуле.

Включите в класс методы:

  1. конструктор по умолчанию;
  2. конструктор с параметрами;
  3. копирующий конструктор и деструктор, если используется динамическая память для представления данных.

Перегрузите операции:

  1. операцию >> для вывода экземпляров класса в поток ostream.
  2. Выполните перегрузку дополнительных операций, указанных в задании варианта.
  3. Разработайте программу, демонстрирующую применение класса.

ВАРИАНТЫ

Номер

варианта

Класс варианта 

Операции перегружаемые

1

Линейный многочлен N – ой степени (узел содержит коэффициент, степень)

+ Сложить два многочлена

= Присвоить

2

Линейный многочлен N – ой степени (узел содержит коэффициент, степень)

- Дифференцировать многочлен

< Сравнить  два многочлена

3

Линейный многочлен N – ой степени (узел содержит коэффициент, степень)

= = Равенство двух многочленов

>> копирование многочлена

4

Массив одномерный динамический целых чисел

[] индексация элемента

+ Слияние двух массивов

5

Массив одномерный динамический вещественных чисел

- Удаление из одного массива элементов другого

= = Равенство двух массивов

6

Массив двухмерный n*n целых чисел

* умножение матрицы на числовую константу (константа может быть и справа и слева)

+сложение двух матриц

7

Множество целых чисел

|| Объединение двух множеств

= = Равенство двух множеств

8

Множество символов

&& Пересечение двух множеств

> Cравнение двух множеств

9

Множество целых чисел

- Дополнение одного множества до другого

< Сравнение двух множеств

10

Очередь

>>Добавить элемент в очередь

[] доступ к первому элементу очереди

11

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

[] доступ к элементу в заданной позиции

+ Добавить элемент в конец списка

12

Вектор задан координатами своих вершин

* Перпендикулярны ли два вектора

+ Сумма двух векторов

13

Дата задана тремя параметрами: день, номер месяца, год

- Разность между двумя датами

+ Получение новой даты, отстоящей от исходной на заданное количество дней

14

Строка, завершающаяся терминальным нулем

+ Конкатенация строк

[] Вставить новый символ в указанную позицию

15

Линейный список Стек

>> Включить элемент в стек

- Исключить элемент из стека

= Присваивание

Лабораторная работа №10(дерево)

Тема: Двоичное бинарное дерево

Цель: получение навыков по созданию иерархических структур

ЗАДАНИЕ

  1. Разработать класс бинарное дерево, включив в него методы: конструктор по умолчанию и вывод бинарного дерева, используя прямой обход дерева.
  2. Разработать производный класс для дерева определенного вариантом. В класс включить методы:
  3. Конструктор с параметром (для сбалансированного дерева) – число узлов.
  4. Копирующий конструктор
  5. Деструктор
  6. Методы для операций, определенных в варианте.
  7. В нечетном варианте использовать  бинарное дерево поиска, а в четном – сбалансированное бинарное дерево поиска (ЕСЛИ ВАРИАНТ НЕ ПРЕДУСМАТРИВАЕТ СВОЮ СТРУКТУРУ).

Варианты

1.Информационная часть узла содержит целое значение.

  1. Определить сумму значений находящихся в листьях дерева.
  2. Обойти дерево алгоритмом прямого обхода
  3. Удалить максимальный элемент дерева (считать, что такой элемент один)
  4. Вставить новый элемент

  1. Информационная часть узла содержит символьное значение.
  2. Определить сумму цифр, содержащихся в дереве, применив алгоритм симметричного обхода
  3. Найти первое вхождение заданного символа и вернуть указатель на узел
  4. Найти максимальное значение среди листьев дерева

  1. Информационная часть узла содержит целое значение.
  2. Определить среднее арифметическое всех узлов непустого дерева
  3. Найти сумму максимального и минимального элементов дерева
  4. Удалить самый левый лист дерева

  1. Информационная часть узла содержит слово.
  2. Определить длину пути в дереве от корня до узла с заданным  значением.
  3. Определить число листьев в дереве
  4. Определить высоту дерева

  1. Информационная часть узла содержит символьное значение.
  2. Определить уровень, на котором находится узел с заданным значением.
  3. Вставить новый узел в дерево
  4. Удалить узел, содержащий заданное значение (первое вхождение)

  1. Информационная часть узла целое число.
  2. Заменить в дереве все отрицательные значения на их модули
  3. Найти минимальное значение, хранящееся в дереве.
  4. Обойти дерево в ширину”.

  1. Информационная часть узла - символ.
  2. Выполнить алгоритм обратного обхода дерева.
  3. Определить, количество цифр в дереве.
  4. Удалить узлы, содержащие цифры.

  1. Информационная часть узла содержит символ значение.
  2. Определить, содержится ли в дереве заданный символ.
  3. Вывести значения всех узлов поддерева с заданным значением узла.
  4. Определить высоту поддерева с заданным значением узла.

  1. Информационная часть узла содержит текст и количество в нем цифр
  2. Определите количество узлов, текст которых содержит максимальное число цифр.
  3. Удалить узел, не содержащий в тексте цифр.
  4. Обойти дерево в обратном порядке и вывести значения его узлов.

  1. Англо русский словарь построен как двоичное дерево поиска, упорядоченное по английскому слову. Каждый узел дерева содержит информацию: английское слово, русское слово, количество обращений.
  2. Включить узел в дерево
  3. Сформировать новое двоичное дерево поиска, упорядочивая узлы по числу обращений
  4. Вывести новый и старый словарь по иерархии сверху вниз.

  1. На междугородней телефонной станции картотека абонентов, содержащая сведения: номер телефона и сведения о владельце, организована как бинарное упорядоченное дерево.

Определите операции:

  1. Формирование списка абонентов, упорядоченного по номеру телефона.
  2. Поиск сведений о владельце по введенному номеру
  3. Формирует извещение на оплату разговора по введенному номеру и времени за разговор

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

Определите операции:

  1. Поиск информации по номеру введенного поезда
  2. Формирование списка поездов, отправляющихся с заданной станции
  3. Определить, количество поездов, которые следуют до заданной станции.

  1. Формулу вида

<формула>::=цифра | (<формула> знак <формула>)

<знак>::= +|*|-

можно представить в виде бинарного дерева. Формула из одной цифры – это дерево из одной вершины. Формула вида F1 # F2  представлена деревом, у которого в корне – операция #,  левое дерево это формула F1 , а правое – F2.

Определите операции:

  1. Построить дерево указанного вида
  2. Вычислить значение дерева
  3. Распечатать формулу дерева

  1. Составить программу формирующую “перекрестные ссылки”, т.е. печатающую список слов, которые встречаются в анализируемом файле. А для каждого слова  - список номеров строк, в которых это слово встречается. Информация по слову хранится в узле бинарного дерева поиска, упорядоченного по значению слова. Список номеров строк храниться в отдельном  связанном списке, указатель на который хранит соответствующий узел дерева.
  2. Построить дерево указанного вида
  3. Найти слово, встретившееся в тексте в максимальном числе строк
  4. Вычислить значение дерева
  5. Распечатать формулу дерева

Лабораторная работа 11

Тема: Структура данных – файл. Файловые потоки С++

Цель. Получение навыков по обработке данных, хранящихся во внешней памяти.

Задание 1. Создание модуля с операциями над текстовым файлом.

  1. Разработать функции для выполнения операций над текстовым файлом  С++:
  2. создание текстового файла, содержащего числовые значения по одному на строку;
  3. вывод содержимого текстового файла;
  4. добавление новой записи в конец файла:
  5. разработать функции для дополнительных операций, указанных в варианте
  6. Разработать приложение и выполнить тестирование всех функций.
  7. Создать модуль и перенести в него все отлаженные функции. Исключить функции из приложения. Отладить приложение, подключив к нему модуль с функциями.
  8. Разработать функции для реализации дополнительных операций, определенных вариантом и сохранить их в модуле с остальными функциями.

Текстовый файл

Дополнительные операции

1

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

2

Скопировать числа исходного файла, которые кратны 7, в новый файл

3

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

4

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

5

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

6

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

7

Создать новый файл из значений исходного, поделив каждое числое на число, равное количеству строк в файле.

8

Создать новый файл из значений исходного, поменяв местами первое число и и последнее.

9

Создать новый файл из значений исходного, заменив все отрицательные числа файла, на квадрат минимального числа исходного файла.

10

Создать новый файл из значений исходного, умножив каждое четное число на максимальное число в файле.

11

Создать новый файл из значений исходного, разделив все нечетные по абсолютной величине числа на среднее арифметическое чисел в файле

12

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

13

Создать новый файл из значений исходного, поделив каждое число на наибольший общий делитель чисел файла.

14

Создать новый файл из значений исходного, добавив к каждому числу наибольшее и наименьшее из чисел файла исходного файла.

15

Создать новый файл из значений исходного, увеличив его на среднее арифметическое всех отрицательных чисел исходного файла.

16*

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

17*

Создать новый файл из значений исходного, размещая в каждой строке три числа: исходное, количество цифр в числе, сумма цифр в числе.

18*

Создать новый файл из значений исходного, размещая на строке по три числа из исходного файла.

19*

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

20*

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

Задание 2. Создание модуля с операциями над двоичными файлами. Файл состоит из записей определенной структуры. Записи имеют ключ, уникальный в пределах файла, создается он как счетчик: количество записей + 1.

  1. Подготовьте тестовые данные в текстовом файле с кодировкой ASCII.
  2. Разработайте структуру записи двоичного файла согласно варианту задания.
  3. Разработайте функции для операций:
  4. преобразование тестовых данных в двоичный файл
  5. отображение всех записей двоичного файла
  6. манипулирование записями в двоичном файле: согласно операций определенных в варианте

Удаление записи производить путем замены на последнюю запись.

  1. Сохраните функции в новом модуле.
  2. Разработать приложение, демонстрирующее выполнение всех операций, подключив к нему модуль с функциями.

1

Структура записи

Читательский абонемент: номер читательского - целое пятизначное число, ФИО, Адрес

Доп. операция

  1.  Поиск записи с заданным значением ключа.
  2.  Удаление найденного значения.

2

Структура записи

Счет в банке: номер счета 7 разрядное число, ФИО, Адрес

Доп. операция

  1.  Поиск записи с заданным значением ключа.
  2.  Обновить значение одного поля.

3

Структура записи

Владелец телефона: номер телефона – последовательность символов, адрес, ФИО

Доп. операция

  1.  Сформировать текстовый файл из фамилий владельцев, чьи номера начинаются с введенных первых трех цифр(например, 434)
  2.  Удалить сведения о владельцах телефонов, которые начинаются с заданной цифры.

4

Структура записи

Владельцев автомобилей. номер машины, марка, сведения о владельце, сведения об угоне (логического типа).

Доп. операция

  1.  Список автомобилей числящихся в угоне.
  2.  Установить факт угона автомобиля с заданным номером.

5

Структура записи

Пациент поликлиники: номер карточки, код хронического заболевания, Фамилия лечащего врача

Доп. операция

  1.  Сформировать двоичный файл с записями о пациентах с заданным кодом заболевания.
  2.  Заменить фамилию, имя, отчество врача у указанных пациентов(список пациентов – это массив номеров карточек)

6

Структура записи

Товар: название, код – шестиразрядное число, завод изготовитель, цена, страна(название0

Доп. операция

  1.  Сформировать текстовый файл о поставках заданной страны, размещая на строке все сведения о товаре, кроме страны. Название страны записать в первой строке файла.
  2.  Добавить новую запись о товаре в конец файла.

7

Структура записи

Специализация вуза: код специальности, название вуза, название специальности

Доп. операция

  1.  Сформировать список вузов, которые ведут подготовку специалистов по специальности с указанным номером. Список представить в текстовом файле.
  2.  Изменить код специальности по названию специальности

8

Структура записи

Книга: ISBN – двенадцатизначное число,  Автор, Название, год издания

Доп. операция

  1.  Создать новый типизированный файл и перенести в него записи о книгах указанного автора за указанный год.
  2.  Удалить книги изданные в указанном году.

9

Структура записи

Страховой полис: номер, компания, фамилия владельца

Доп. операция

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

10

Структура записи

Англо – русский словарь: английское слово, русское слово

Доп. операция

  1.  Сформировать список английских слов, начинающихся с указанной буквы и их русский перевод.
  2.  Обновить запись, записав новый вариант русского переводв по заданному слову.

11

Структура записи

Железнодорожная справка: номер поезда, пункт отправления, пункт назначения, время отправления

Доп. операция

  1.  Сформировать справку по поездам, отправляющимся в указанный пункт назначения. Результаты записать в новый двоичный файл такой же структуры, как и исходный.
  2.  Удалить сведения по указанному поезду.

12

Структура записи

Регистрация малого предприятия: номер лицензии(текстовое значение), название, учредитель, признак действия лицензии(0 действует, 1 отозвана)

Доп. операция

  1.  Сформировать список лицензий одного заданного учредителя. Записать полученные данные в текстовый файл, располагая записи построчно.
  2.  Отозвать указанные лицензии. Номера отзываемых лицензий находятся в текстовом файле, каждый номер на отдельной строке.

13

Структура записи

Студент: номер зачетной книжки, номер группы, ФИО

Доп. операция

  1.  Сформировать список студентов одной группы в двоичном файле той же структуры, что и исходный.
  2.  Перевести некоторых студентов в другую группу. Номера зачетных книжек переводимых студентов находятся в текстовом файле, каждый номер на отдельной строке. Номер новой группы известен и передается в операцию.

14

Структура записи

Справочная межгорода: код города, название города, страна

Доп. операция

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

15

Структура записи

Расписание занятий группы: номер группы, Название дисциплины, номер пары, номер недели, номер дня недели, вид занятия, номер аудитории.

Доп. операция

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

16

Структура записи

Частотный словарь: слово, количество вхождений в текст

Доп. операция

  1.  Определить, какое слово встречалось чаще всего в тексте.
  2.  Добавить в файл новую запись по слову.

Обновить количество вхождений некоторых слов, увеличив их количество на 1.

17

Структура записи

Читательский билет: Номер, инвентарный номер книги, дата выдачи, дата возврата

Доп. операция

  1.  Сформировать список читателей, которые не вернули книги в срок (дата возврата<текущей), полученные данные записать в двоичный файл.
  2.  Найти запись по заданным критериям : номер, инвентарный номер и вернуть указатель на запись.
  3.  Удалить запись о книге, которую читатель вернул в библиотеку.

18

Структура записи

Вызов такси: Номер, Фамилия водителя, время выезда, отметка о присутствии в гараже

Доп. операция

  1.  Сформировать список машин, находящихся в гараже. Полученные данные записать в двоичный файл с той же структурой.
  2.  Обновить сведения о машины при выезде из гаража.

19

Структура записи

Продажи товаров: Код товара, название, цена, дата продажи.

Доп. операция

  1.  Посчитать сумму, на которую были продан товары за указанную дату.
  2.  Сформировать двоичный файл на основе записей исходного файла, содержащий сведения о товаре : код товара, количество продаж, цена товара.
  3.  Произвести расчет выручки от продаж на основе данных нового файла.

20

Структура записи

Сотрудник: Табельный номер, Должность, оклад, количество детей

Доп. операция

  1.  Увеличить оклад вдвое тех сотрудников, которые занимают указанные в текстовом файле должности.
  2.  Удалить сотрудников с табельными номерами, которые хранятся в двоичном файле.

  1.  Файловые потоки.
  2.  Классы потоков

ifstream – класс входных файловых потоков ( для чтения данных)

ostream – класс выходных файловых потоков (для создания файлов и добавления записей)

fstream – класс двунаправленных  потоков (для обеих типов операций)

Файл – это экземпляр соответствующего класса.

  1.  Операции над файлами

Файл – это экземпляр соответствующего класса – поток..

  1.  Создание потока 

Способ 1. Без связывания с файлом

 ifstream if; // для ввода данных в файл

 ostream of; // для чтения данных из файла

 fstream ff;   // для чтения и записи

Способ 2. Связывая его с файлом

 ifstream if(“A.txt”);

 ostream of(“A.txt”);

fstream ff(“A.txt”);

  1.  Открытие потока и связывание его с файлом

Так как поток это объект класса, то открытие осуществляет метод

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.

  1.  ifstream if;

 if.open(“A.txt”); // по умолчанию для чтения

  1.  ostream of;

 of.open(“A.txt”); // по умолчанию для записи

  1.  ifstream ff

 ff.open(“A.txt”); по умолчанию для записи и чтения

Способ2.

  1.  ifstream if(“A.txt”, ios::in|ios::trunc); для записи 
  2.  ofstream o(“A.txt”, ios::out|ios::trunc); для чтения
  3.  ifstream ff(“A.txt”, ios::in| ios::out ); для модификации
    1.  Ввод – вывод потоковый

Методы обмена с потоками

  1. Операция извлечения из потока >>. Аналогично извлечению из стандартного потока cout.

Пример.

ofstream o(“A.txt”, ios::out|ios::trunc);

int x;

o>>x;

  1. Операция включения в поток<<. Аналогично включению в стандартный поток cin.

ifstream if(“A.txt”, ios::in|ios::trunc);

int x=10;

if<<x;

  1. Методы для чтения из потока класса 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()

  1. Методы неформатированного вывода класса ostream

flush()

put( c )

seekg(pos)

seekg(offs, org)

tellg()

write(buf,num)

  1.  Закрытие файла

ofstream o(“A.txt”, ios::out|ios::trunc);

int x;

if>>x;

if.close(); //закрытие

  1.  Методы для управления ошибками потоков

В базовом классе 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.  Форматирование данных

Способ 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;

  1.  Пример.Операции с текстовым файлом.

#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;

}

  1.  Пример. Операции с двоичным файлом

#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. Разработайте шаблонный класс – хеш таблица, для поиска информации в коллекциях данных с помощью хеш функции. Хеш функцию подберите самостоятельно.
  2. Разработайте приложение, которое использует хеш таблицу для организации прямого доступа к элементам множества (массив данных), структура элементов которого приведена в варианте. Множество реализуйте через класс - шаблон с операциями вставки, удаления, поиска, вывода и включите в него хеш таблицу. Предусмотрите возможность создания наследников хеш-таблицы.
  3. Разработайте такие тесты, чтобы возникли коллизии.
  4. Выведите список индексов, которые формируются при вставке элементов в таблицу.

ВАРИАНТЫ

Метод хеширования (способ реализации коллизий)

Структура элемента множества(ключ – подчеркнутое поле)

1

С открытой адресацией (увеличение на 1)

Читательский абонемент: номер читательского - целое пятизначное число, ФИО, Адрес

2

С открытой адресацией(увеличение на номер выполняемого подбора)

Счет в банке: номер счета 7 разрядное число, ФИО, Адрес

3

С открытой адресацией (двойное хеширование)

Владелец телефона: номер телефона – последовательность символов, адрес

4

Цепное хеширование

Владельцев автомобилей. номер машины, марка, сведения о владельце.

5

Цепное хеширование

Пациент поликлиники: номер карточки, код хронического заболевания, Фамилия лечащего врача

6

Цепное хеширование

Товар: название, код – шестиразрядное число

7

Цепное хеширование

Специализация вуза: код специальности, название вуза

8

Открытый адрес(двойное хеширование)

Книга: ISBN – двенадцатизначное число,  Автор, Название

9

Цепное хеширование

Страховой полис: номер, компания, фамилия владельца

10

Открытый адрес(увеличение на 1)

Англо – русский словарь: английское слово, русское слово

11

Открытый адрес(двойное хеширование)

Железнодорожная справка: номер поезда, пункт отправления, пункт назначения, время отправления

12

Цепное хеширование

Регистрация малого предприятия: номер лицензии, название, учредитель

13

Открытый адрес(двойное хеширование)

Студент: номер зачетной книжки, номер группы ФИО

14

Цепное хеширование

Справочная межгорода: код города, название города

15

Открытый адрес(увеличение на 1)

Проверка проавописания по словарю правильных слов: слово (в тексте найти слова с орфографическими ошибками)

16

Цепное хеширование

Частотный словарь: слово, количество вхождений в текст

17

Лабораторная работа 13

Тема. Граф. Операции над графом.

Цель.

  1. Получение практических навыков по созданию и управлению структурой данных – граф

ЗАДАНИЕ

Общие для всех вариантов.

  1. Разработать структуру представления графа согласно варианту.
  2. Разработать процедуру заполнения графа из 10 узлов.

Для каждого варианта

  1. Выполнить задание варианта, разместив, определение его подпрограмм и представления графа, в отдельном модуле (Можно представить на классе).
  2. Создать приложение, демонстрирующее выполнение заданий варианта и общих операций.
  3. При составлении тестов рассмотрите все указанные варианты:
  4. Полный граф (все узлы связаны между собой)
  5. Несвязанный граф – представлен несколькими несвязанными  между собой подграфами
  6. Граф не имеет несвязанных компонент и не является полным

ВАРИАНТЫ

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

Цель.

  1. Получение практических навыков по использованию классов и алгоритмов STL при решении практических задач

Задание 1. Разработать шаблон контейнера и продемонстрировать его применение к стандартным типам и пользовательскому типу (классу).

  1. Разработать шаблонный класс контейнер, указанного в варианте типа.
  2. Разработайте консольное приложение, демонстрирующее работоспособность класса для стандартных типов: целого и вещественного.
  3. Разработайте класс варианта, со списком полей определенным в варианте, методом вывода на экран значения класса и другими необходимыми методами.
  4. Измените приложение, разработанное согласно п.2 данного задания, так, чтобы продемонстрировать возможность применения контейнера к классу.

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

Операции над элементами контейнера.

Для стека: втолкнуть элемент, вытолкнуть, определить количество элементов в стеке.

Для очереди: добавить, удалить, определить значение первого элемента.

Для списка: вставить элемент в заданную позицию (с проверкой позиции), удалить элемент в позиции, определить значение в позиции.

Для дека (очередь с двумя вершинами): вставить элемент в дек, удалить элемент из дека, определить значение последнего узла.

Задание 2. Применить контейнер STL.

  1. Разработать новое консольное приложение, демонстрирующее применение контейнера STL, соответствующего типу контейнера, определенного в варианте.
  2. Предусмотреть демонстрацию всех операций, допустимых над структурой, которая определена контейнером.

Номер

Тип контейнера

Класс

1

Стек

Студент (Фамилия, имя, номер группы)

2

Список

Книга (Автор, Название, Год издания, издательство)

3

Очередь

Детская игрушка (Название, Цена, Возрастная группа)

4

Дек

Комплексное число (действительная часть, мнимая часть)

5

Стек

Дата (День, Название месяца, Год)

6

Список

Сотрудник (Фамилия, Имя, должность)

7

Очередь

Тур (Страна, Время пребывания, Стоимость)

8

Дек

Товар (Название, Производитель, Цена)

9

Стек

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

10

Список

Штатное расписание(Название должности, оклад, количество единиц)

11

Очередь

Материальная ценность (Название, Инвентарный номер, Цена, Дата, Номер комнаты)

12

Дек

Страна(Название, Материк, Численность, Общая площадь)

13

Стек

Счет фактура (Название организации отпускающей товар, Номер, Дата, Сумма, Название организации покупающей товар)

14

Список

Успеваемость школьника (Фамилия, Название дисциплины, Оценка, Дата, Номер урока)

Список литературы

  1. Герберт Шилдт  «Искусство программирования на С++» Издательство: БХВ-Петербург.: 2005.
  2. Герберт Шилдт  С++ Базовый курс, Издательство Вильямс, 3-е издание.: 2010 г.
  3. Герберт Шилдт  С++ Методики программирования Шилдта, Изд.:OZON.RU, 2010 г.


 

А также другие работы, которые могут Вас заинтересовать

3763. Обеспечение качества 203.5 KB
  Обеспечение качества Объективные предпосылки изменения отношения к качеству и эволюция управления качеством Вопросы качества продукции и его повышения всегда находились в центре общественного внимания. Изменение акцента в оценке товара для удовлет...
3764. Рекомбинационные генетические карты 500.5 KB
  Рекомбинационные генетические карты. Хромосомная теория наследственности и кроссинговер Первое предположение о том, что элементы наследственности находятся в хромосомах, поскольку хромосомный материал в равной степени распределяется дочерними клет...
3765. Маркетинговая деятельность на промышленном предприятии 222 KB
  Маркетинговая деятельность на промышленном предприятии. Цели и содержание маркетинговой деятельности промышленного предприятия Основу маркетинговой деятельности промышленного предприятия составляют: исследования рынка, разработка программы создания...
3766. Інтелект-шоу ЕОМ - ЕВРИКА 4.78 MB
  Інтелект-шоу ЕОМ - ЕВРИКА для учнів 9-11 класів Сьогодні ми проводимо інтелектуальну гру „ЕОМ-Еврика” на зразок телевізійного інтелект-шоу „LG-Еврика”. На уроках ми вже вивчили теми, які пропонуються Вам на конкурс. У інтелектуально...
3767. Національна символіка України 4.39 MB
  Національна символіка України Згадаймо, як 26 квітня 1989 року на велелюдному мітингові, що зібрався на площі Ринок у Львові з нагоди третьої річниці Чорнобильської аварії, замайоріли синьо-жовті прапори з жалобними стрічками. А кілька днів по тому...
3768. Нерудні корисні копалини Дніпропетровщини 10.09 MB
  Нерудні корисні копалини Мета: Поглибити та систематизувати знання про групи нерудних корисних копалин України, Дніпропетровщини, Кривого Рогу. Їх розміщення та використання. Формувати світогляд на основі пізнання світу, сформувати в учн...
3769. Українське відродження або нова русифікація 1.49 MB
  Вступ День 2 листопада 1998 р. починався як звичайний робочий день, котрі заповнюють більшість нашого життя. Залишилася в минулому виборча лихоманка, а Верховна Рада України, нарешті, пережила "спікеріаду" й занурилася до роботи. Здавалося, що на як...
3770. Звукоподражание в современном английском языке 157 KB
  Введение Настоящая курсовая работа посвящена изучению агломератов английских звукоподражательных единиц. Основные понятия настоящей работы: Звукоподражание (ономатопея) – условное воспроизведение звуков природы и звучаний, сопровождающих некото...
3771. Орнамент — один из древнейших видов изобразительной деятельности человека 589 KB
  Введение. В народном декоративном искусстве все основано на отработанных профессиональных навыках и приемах, выработанных на протяжении многих поколений. Эти приемы настолько совершенны, что их применение позволяет достичь большой художественной выр...