Файл: Лабораторная работа 1 5 Бинарные деревья 5 Цель работы 5 Краткие теоретические сведения 5 Постановка задачи 6.docx

2	нн 5 3 3 5 нн 9 7 3 9 нн 4 3 7 4 нн
3	нн 25 40 31 27 5 нн 17 30 25 19 15 нн 6 1 9 50 24 нн 6 22 8 7 10 нн
4	нн 20 42 35 20 нн 30 34 42 30 нн 12 35 34 12 нн
5	нн 47 22 46 29 34 нн 25 34 19 18 18 нн 33 7 38 27 24 нн 38 21 14 6 27 нн
6	нн 5 11 9 10 нн 8 7 7 14 нн 8 12 6 15 нн
7	нн 97 60 73 17 52 97 нн 41 52 90 30 60 41 нн 21 35 41 73 52 21 нн 95 46 17 90 35 95 нн 81 52 30 41 46 81 нн

---

8	нн 27 43 16 30 16 7 нн 16 1 30 25 20 13 нн 35 5 0 21 16 25 нн 18 18 12 46 27 48 нн 5 23 5 5 9 5 нн
9	нн 6 29 10 59 34 13 6 нн 23 4 53 28 7 23 21 нн 20 31 6 17 8 3 20 нн 50 25 4 43 40 22 38 нн 26 47 26 24 4 22 18 нн 22 10 5 17 4 35 19 нн

---

5. Методические указания

1. Написать программу, решающую задачу коммивояжера, указанную в варианте.

2. Для решения задачи коммивояжера использовать метод ветвей и границ.

3. Поэтапно продемонстрировать изменение исходной матрицы.

4. Исходная матрица может храниться в текстовом файле, либо объявлена в двумерном массиве в глобальной области.

6. Содержание отчета

1. Постановка задачи (общая и для конкретного варианта)

2. Анализ задачи

• 
  Определения функций для реализации поставленных задач
  
• 
  Определение функции main()
  

3. Блок-схемы основных функций

4. Текст программы

5. Тесты

---

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

STL – стандартная библиотека шаблонов в С++

4. 
   
   

   1. Цель работы:

Получить практические навыки при работе со стандартной библиотекой шаблонов.

2. Краткие теоретические сведения

STL-библиотека – набор алгоритмов, контейнеров, средств доступа к их содержимому и различных вспомогательных функций в С++. Библиотеки дают возможность сделать код намного короче, за счет обобщенного программирования.

Контейнерные классы

Контейнер – это объект, который хранит в себе другие объекты одного типа. Хранимые объекты могут быть объектами в смысле объектно-ориентированного программирования либо значениями встроенных типов. Данные, сохранённые в контейнере, принадлежат ему. Это означает, что, когда время существования контейнера истекает, то же самое происходит с сохранёнными в нём данными.

Библиотека STL (Standard Template Library) предоставляет целый набор шаблонных контейнерных классов. Они обладают некой базовой концепцией, которая обязует их иметь конкретные поля и методы. Например, все контейнеры имеют метод size(), который возвращает количество элементов в контейнере.

Последовательности

Базовую концепцию можно уточнять, добавляя требования. Последовательность – это важное уточнение, поскольку несколько типов контейнеров STL – vector, stack, queue, list, deque, forwart_list, priority_queue – являются последовательностями. Уточнение, заключается в том, что переход от элемента к элементу последовательности должен быть, по меньшей мере, однонаправленным, что гарантирует размещение элементов в определённом порядке, который не меняется от одного цикла итераций к другому.

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

• 
  insert() – метод вставки элементов.
  
• 
  erase() – метод удаления элементов.
  
• 
  clear() – метод удаляет все элементы контейнера.
  

Рассмотрим шесть типов контейнеров-последовательностей более подробно.

---

1. vector:

vector – это представление динамического массива в виде класса, где поддерживается автоматическое управление памятью, которое позволяет динамически менять размер объекта vector, увеличивая и уменьшая его при добавлении или удалении элементов. Он предоставляет произвольный доступ к элементам с помощью операции индексации [] и метода at().

2. deque:

Класс шаблона deque представляет собой двустороннюю очередь – тип, кратко называемый «дека». В том виде, в каком он реализован в STL, он напоминает контейнер vector, где поддерживается произвольный доступ к элементам. Основное различие между ними состоит в том, что вставка и удаление элементов из начала объекта deque – операция, выполняемая за постоянное время, в то время как для объекта vector эти операции линейны во времени.

3. list:

Класс шаблона list представляет собой двусвязный список. Каждый его элемент, за исключением первого и последнего, связан как с предшествующим элементом, так и последующим элементами, откуда следует, что по такому списку можно проходить в обоих направлениях. Различие между list и vector заключается в том, что list обеспечивает вставку и удаление за постоянное время в любой позиции списка. Также класс шаблона list имеет функции-члены, которые позволяют осуществить: слияние списков, сортировку списка, сворачивание повторяющихся элементов и другие.

4. forward_list:

В С++11 появился новый класс контейнера forward_list. Этот класс реализует односвязный список. В таком списке каждый элемент связан только со следующим элементом, но не с предыдущим.

5. queue:

Класс шаблона queue представляет собой простую очередь. Он не только не позволяет произвольный доступ к элементам очереди, но даже не разрешает выполнять итерацию по её элементам. Взамен queue ограничивается базовыми операциями, определяющими очередь.

6. stack:

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

Ассоциативные контейнеры

Ассоциативный контейнер – ещё одно расширение концепции контейнеров. Ассоциативный контейнер связывает значение с ключом, который служит для отыскания значения. Например, ключом может быть номер квартиры в доме, а значением

---