OOP_Bakalavry_-_Laboratornye_raboty

ListItem

64 байта

Person Person

48 байт

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

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

ListItem* Next

8 байт

(например, Person), а два других поля будут содержать

ListItem* Prev

8 байт

адреса на следующий и предыдущий элемент списка

Item1

Person

Item3

Next

Person

Next

Head

Prev

Prev

Person

Item4 (Tail)

Next

Item2

Person

Prev = NULL

Next = NULL

Person

Prev

Next

Prev

В отличии от массива, память под каждый элемент массива резервируется отдельно от остальных в любом свободном пространстве памяти (кучи).

Нет необходимости заранее указывать размер списка, его расширение происходит динамически Обратиться к любому элементу списка можно переходя по адресам указателей Next от головы до нужного элемента

Рассмотрим на примере. Допустим, нам нужно создать список, хранящий в себе данные о людях (структура Person). Для этого мы создадим следующую структуру:

struct PersonListItem

{

Person Person; PersonListItem* NextItem;

}

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

Теперь, как же создать сам список? Для начала создадим первый элемент списка – голову списка:

PersonListItem* personListHead = new PersonListItem; personListHead→Person = ReadPerson(); // Jack Bauer personListHead→NextItem = NULL;

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

Теперь добавим еще один списка:

PersonListItem* personListItem = new PersonListItem;

personListItem→Person = ReadPerson();		// Tony Almeida
personListItem→NextItem	= NULL;
personListHead→NextItem	= personListItem;	// связывание нового элемента с головой

Теперь, если мы захотим получить доступ ко второму элементу списка, это можно сделать через указатель на начало списка:

personListHead→Person→Name = “Tom”	// меняем имя Jack на Tom	в 1 элементе
personListHead→NextItem→Person→Name = “John”	//меняем имя Tony на John	во 2 элементе

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

PersonListItem* currentItem = personListHead;

for(int i =0; i < 5; i++)

{

currentItem = currentItem→NextItem;

}

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

PersonListItem* currentItem = personListHead; while(currentItem→NextItem != NULL)

{

currentItem = currentItem→NextItem;

}

Данный пример после выполнения присвоит в currentItem адрес последнего элемента списка. Однако если при создании и добавлении элемента в список не присвоить в указатель на следующий элемент NULL, вы не сможете отловить конец списка, а данный пример превратится в бесконечный цикл. Также стоит помнить, что присвоение NULL в какой-либо уже добавленный элемент списка (например, personListHead→NextItem = NULL) приведет к потере данных всего последующего списка и утечке памяти.

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

struct PersonListItem
{
Person Person;
PersonListItem* NextItem;	// Следующий элемент списка
PersonListItem* PrevItem;	// Предыдущий элемент списка
}

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

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

struct PersonTreeItem
{
Person Person;
PersonTreeItem* LeftNode;	// Левая дочерняя ветвь
PersonTreeItem* RightNode;	// Правая дочерняя ветвь
}

Здесь представлен пример дерева с двумя потомками – левой и правой ветвями. Данный вид деревьев достаточно распространен в вычислительных алгоритмах, например, задачах оптимизации, сортировки и поиска данных. Обратите внимание, что дочерний узел не хранит в себе информации о родительском узле, что позволяет достаточно быстро “переставлять” одну ветвь дерева в другую. В более общем случае элемент дерева может хранить в себе неограниченное количество дочерних элементов.

TreeItem	64	байта
Person Person	48 байт				Для создания дерева необходимо организовать структуру,
					одно из полей которого будет хранить в себе информацию
TreeItem* Left	8	байт
					(например, Person), а два других поля будут содержать
TreeItem* Right	8	байт			адреса на левый и правый ветки дерева
			Root
			Person
			Left
			Right

Item1		Item2
Person		Person
Left = NULL		Left
Right = NULL		Right

Item3

Item4

Person

Left = NULL

Right = NULL

Person

Left = NULL

Right = NULL

Элементы дерева также хранятся отдельно друг от друга, храня в себе указатели на дочерние узлы дерева. Зная только расположение элемента Root, можно перейти сверху вниз к любому элементу дерева. Благодаря своей структуре, можно достаточно быстро «переставлять» местами любые ветви дерева между собой вне зависимости от их размера, что позволяет использовать деревья для организации быстрых алгоритмов поиска и сортировки

Списки и деревья являются лишь частными случаями такой структуры, как граф. Граф – структура данных, каждый элемент которого связан с неопределенным количеством других элементов графа. Как правило, в графе нельзя четко определить головной или корневой узел, им может быть любой элемент. По этому корневой узел выбирается условно и определяется конкретной реализацией и назначением графа. Организация элемента графа на языке Си++:

struct PersonGraphItem
{
Person Person;
PersonGraphItem* Neighbors;	// Массив «соседей» данного элемента
int NeighborsCount;	// Количество соседей
}

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

GraphItem 92 байта

Person Person

GraphItem* Neighbors[5]

int NeighborsCount

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

Item2

Person

Neighbors

NeighborsCount = 4

Item1
Person		Item3
Neighbors
		Person
NeighborsCount = 2
		Neighbors = 3
		NeighborsCount

		Item5
Item4		Person
		Neighbors
Person
		NeighborsCount = 1
Neighbors
NeighborsCount = 2

Граф – достаточно сложная структура для хранения данных, используют её крайне редко. В зависимости от задачи могут различать: направленные и ненаправленные графы, весовые и невесовые, цикличные и ацикличные и т.д.

Словарь (отображение) – структура данных, хранящая набор уникальных пар <ключ-значение>, где

вкачестве ключа и значения могут быть любые типы данных. Для понимания данной структуры представьте себе обычный словарь. В нём определенное слово (ключ), которое является уникальным

впределах данного словаря. Данному слову соответствует некоторое описание (значение), поясняющее первоначальное слово. Таким образом, словарь организует точное соответствие уникального ключа определенному значению. Обратившись к такому словарю по ключу, мы получим нужное значение, при условии существования ключа в словаре. Словарь не может содержать ключ без значения или значение без ключа.

Примером словаря можем послужить словарь отдела кадров <Person-Double>, где ключ Person указывает уникального человека в пределах предприятия, а Double – значение зарплаты данного человека. Или словарь расписания поездов <int-string[]>, где int – ключ-номер поезда, а string[] – массив строк-названий станций.

Стек – структура данных, работа которой организована по принципу “Первым пришел, последним вышел”. Для примера возьмем стопку тарелок. Сначала вы положите на стол первую тарелку, затем на неё вторую, а затем и третью. Но когда вам потребуется взять тарелку, вы будете забирать их в обратном порядке – сначала третью, затем вторую и только потом первую. Таким образом, тарелка, пришедшая первой, вышла последней. Работа стека организована аналогичным образом – помещая в неё последовательность элементов, вы сможете получить к ним доступ только в обратном порядке. Подобная структура данных часто используется в низкоуровневых программах, где требуется жесткий контроль памяти. Однако, данная структура может находит своё применение и пользовательских приложениях.

ПРИМЕЧАНИЕ: не путайте понятия стека как структуры данных и стека как области памяти – несмотря на идентичное название данные понятие принципиально отличаются.

Очередь – структура данных, организующая принцип «Первым пришел, первым вышел». Фактически, очередь противоположна стеку, и принцип её работы понятен из названия.

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

2.Завести переменные головы и хвоста списка. Переменные головы и хвоста списка должны быть локальными переменными функции main() и, при необходимости, должны передаваться в соответствующие функции, реализуемые далее.

ПРИМЕЧАНИЕ: представленные ниже прототипы функций являются лишь примером, а не конкретной инструкцией к действию. Входные параметры и возвращаемое значения в вашей реализации могут отличаться!

3.Создать функцию void Add(Person& person), помещающую переменную типа Person в конец списка. При реализации данной функции учтите, что если список пуст (т.е. Head == NULL), то новый элемент является первым элементом и становится головой списка. В любом другом случае, новый элемент помещается в конец списка.

4.Создать функцию void Show(), выводящую на экран содержимое списка. Если список пуст,

вывести соответствующее сообщение (List is empty!). Для реализации данной и всех последующих функций очень удобно предварительно реализовать функцию GetLength(), возвращающую длину списка.

5.Создать функцию Person& Get(int index), возвращающую ссылку (или указатель) на эле-

мент списка по указанному индексу. Функция должна учитывать те случаи, когда данный индекс для списка не существует, например, отрицательный индекс или индекс превышающий количество элементов массива. Также не забудьте, что индексация по правилам языка Си++ начинается с нуля. Для простоты реализации в случае несуществования индекса функция должна вернуть NULL.

6.Создать функцию void Remove(int index), удаляющую из списка элемент по указанному ин-

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

7.Создать функцию void Insert(Person& person, int index), помещающую переменную типа

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

8.Создать функцию void Clear(), очищающую содержимое списка. Не забудьте, что при очистке списка необходимо освободить память всех элементов списка, а также очистить указатели на голову и хвост списка.

*9. Создать функцию Person& MakeRandomPerson(), возвращающую переменную типа Person, инициализированную случайными данными. Сложностью реализации данной функции является то, что имена и фамилии должны быть человекоподобны, например, Иван, Артем, Сергей, Петров, Иванов и т.д. Для этого создайте два массива по 15 элементов, в которых будут заранее заданы человекоподобные имена и фамилии людей. При создании случайного человека, вам нужно лишь сгенерировать случайный индекс от 0 до 15 для определения имени, и такой же случайный индекс для выбора фамилии. Таким образом, вы реализуйте 152=225 комбинаций имен и фамилий. Дополнительно можете учесть соответствие имени и фамилии полу человека.

10. Создать программу, демонстрирующую работу с созданным двусвязным списком. На экран должно быть выведено меню, предлагающее выполнить ту или иную функцию. Любое вводимое пользователем действие должно сопровождаться вспомогательными комментариями. Например, при вызове функции Insert может быть следующий вариант диалога:

...

Please enter name and surname (ex. “Jack Bauer”):

> Tony Almeida

Please enter age (age must be more than 14): > 31

Please enter index of Person in List for inserting (0-4): > 3

Person inserted

…

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

*11. Создайте цветовую раскраску выводимой на экран информации. Чтобы улучшить воспри-

ятие информации, выводимой вашей программой на экран, воспользуйтесь раскраской текста. Дело в том, что консоль и командная строка также являются пользовательским интерфейсом. Существует огромное количество литературы и материалов, посвященных созданию удобных пользовательских интерфейсов для приложений с графическим интерфейсом (обычные оконные приложения, например, в ОС Windows). Однако мало кто воспринимает консоль как пользовательский интерфейс и заботится о грамотном выводе информации в консоли. Для текстовых интерфейсов существует не так уж много инструментов для улучшения восприятия информации. Их всего три:

1)Пустые/разделительные строки - позволяют отделить определенные абзацы и строки друг от друга. Также помимо пустой строки существуют варианты, где строка заполнена каким-нибудь символом, например ‘*’, ‘_’ или ‘#’.

2)Табуляция - позволяет производить аккуратный вывод табличных значений.

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

1.Add Person

2.Add Random Person 3.Insert Person

4.Get Person By Index 5.Remove Person By Index 6.Show All Persons 7.Clear List

Choose action 1

name and surname

>Tony Almeida age

>31

1.Add Person

2.Add Random Person

------List of Person: Main Menu------

1.Add Person

2.Add Random Person

3.Insert Person

4.Get Person By Index

5.Remove Person By Index

6.Show All Persons

7.Clear List

Choose action (1-7): 1

Please enter name and surname (ex. “Jack Bauer”):

> Tony Almeida

Please enter age (age must be more than 14): > 31

*Person added

------List of Person: Main Menu------

3.Insert Person

4.Get Person By Index 5.Remove Person By Index 6.Show All Persons 7.Clear List

Choose action 6

McClane John

34 Slayter Jack

41 Tony

Almeida 31

1.Add Person

2.Add Random Person 3.Insert Person

4.Get Person By Index 5.Remove Person By Index 6.Show All Persons 7.Clear List

Choose action

1.Add Person

2.Add Random Person

3.Insert Person

4.Get Person By Index

5.Remove Person By Index

6.Show All Persons

7.Clear List

Choose action (1-7): 6

*List of Person:

Surname: McClane

Name: John

Age: 34

Surname: Slayter

Name: Jack

Age: 41

Surname: Tony

Name: Almeida

Age: 31

------List of Person: Main Menu------

1.Add Person

2.Add Random Person

3.Insert Person

4.Get Person By Index

5.Remove Person By Index

6.Show All Persons

7.Clear List

Choose action (1-7):

Очевидно, что вариант справа более структурирован и воспринимается более комфортно. Заголовки и второстепенные сообщения обозначены черным; варианты действий и значимая информация о человеке выделена синим; если от пользователя требуется что-то ввести, сопроводительное сообщение выделяется фиолетовым, а само вводимое значение зеленым; информация о каждом человеке разделена пустыми строками и выравнена с помощью табуляции, а вывод шапки программы позволяет четко определить начало меню - всё это создает удобный пользовательский интерфейс в консоли. Если данный пример кажется вам не убедительным, обратите внимание, что эти же приёмы используются в Visual Studio для отображения исходного кода: пустые строки отделяют функции и блоки кода между собой, табуляция позволяет определить вложенность операторов относительно друг друга, а подсветка синтаксиса выделяет ключевые слова, названия переменных и типов данных. Всё это значительно упрощает восприятие исходного кода программы.

Найти способы изменения цвета выводимого текста вам предлагается самостоятельно.

*12. Создайте в отдельном проекте еще какую-либо структуру данных: словарь, стек или очередь.

Для стека создайте следующие функции:

Push - добавить элемент

Pop - удалить верхний элемент

Top - получить верхний элемент

Size - размер стека

IsEmpty - true, если стек пуст

Для очереди создайте следующие функции:

Push - добавить элемент

Pop - удалить первый элемент

Size - размер очереди

IsEmpty - true, если очередь пуста

Front() - получить первый элемент

Back - получить последний элемент Для словаря создайте следующие функции:

Add - добавить пару ключ-значение в словарь

GetByKey - получить значение по ключу

Size - получить количество элементов в словаре

RemoveByKey - удалить элемент словаря по заданному ключу

GetKeys - получить все ключи (в виде массива или еще каким-либо способом)

Clear - очистить словарь

Данное задание необязательно выполнять для структуры Person, можно создать стек для вещественных чисел или словарь где ключ-значение это char-char[] (по аналогии с обычным словарем). Внутренняя реализация структуры остается на ваше усмотрение.

ПРИМЕЧАНИЕ: задания со звездочкой необязательны и выполняются только из личного желания обучающегося.

Вопросы для проверки:

1.Что такое массив?

2.Что такое список? Какие списки бывают?

3.Чем отличается односвязный список от двусвязного? В чем плюсы и минусы каждого из них?

4.В чем отличие списка от массива?

5.Что такое граф?

6.Что такое словарь?

7.Что такое стек?

8.Что такое очередь?

9.В чем отличие стека от очереди?

10.В чем отличие словаря от списка? В чем отличие словаря от массива?

11. На какие виды делится оперативная память относительно выполняемой программы? 12. Что такое куча?

13. Для чего нужно динамическое выделение памяти и почему нельзя обойтись статической областью?

14. Почему необходимо освобождать динамически выделенную память? Что такое утечка памяти?

Содержание отчета:

-Титульный лист

-Содержание

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

1.2Введение и постановка задачи лабораторной работы – в введении представить ответы на вопросы для проверки в виде единого целостного текста без перечисления и указания самих вопросов. В постановке задачи перечислить все задачи, которые необходимо выполнить в работе – выделены жирным текстом в данном методическом пособии.

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

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

1.5Исходный код реализации функций Remove().

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

ПРИМЕЧАНИЕ: при проверке отчета преподавателем особое внимание уделяется правильности оформления. Отчет должен соответствовать стандарту оформления [ОС ТУСУР 6.1- 97] (можно найти на сайте кафедры или в Интернете). Обращайте внимание на размеры шрифтов и межстрочных интервалов, размеры полей и абзацных отступов, указания номеров страниц и т.д. В качестве примера оформления титульного листа, содержания, текстового параграфа и рисунков-графиков использовать приложения В, Д, И, К, Л [ОС ТУСУР

6.1-97].

Лабораторная №5 Классы

1. На основе предыдущих лабораторных реализуйте класс Person, представляющий следующую внутреннюю организацию:

public char Name[20]; public char Surname[20]; public int Age;

public Sex Sex;

public Person(); //конструктор класса

Класс Person должен быть реализован в отдельном файле Person.h. Для этого добавьте в папку Headers (Заголовочные файлы) новый файл с названием соответствующего файла.

2. Реализуйте класс PersonList, представляющий следующую внутреннюю организацию:

private PersonListItem* _head;	//указатель на голову	списка
private int _count;	//количество элементов в списке
public PersonList();	//конструктор класса
public void Add(Person* person);	//добавить человека в список
public Person* Find(int index);	//найти человека по указанному индексу
public int IndexOf(Person* person);	//вернуть индекс человека, если он есть в списке
public void Remove(Person* person);	//удалить человека из списка
public void RemoveAt(int index);	//удалить человека из списка по индексу
public void Clear();	//очистить список
public int GetCount();	//получить количество элементов

Остальные поля и методы, необходимые для реализации остаются на усмотрение разработчика. Данный класс должен быть реализован в отдельном заголовочном файле PersonList.h. Для использования класса Person, добавьте в начале файла строку:

#include “Person.h”

Хранение каждого класса в своём отдельном файле упрощает ориентирование в исходном коде программы разработчикам, позволяет в короткие сроки разобраться в архитектуре программы и находить необходимую функциональность. Более того, во многих компаниях вводится также ограничения на количество строк в одном классе/файле. Считается, что нормальный размер класса составляет 300 строк кода – при таком или меньшем количестве разработчику будет легко разобраться в работе класса. Максимальным количеством считается 1000 строк кода – при таком размере класса понять принцип его работы становиться очень трудно. Если вы превысили размер файла в 1000 строк кода, вероятно, вы неправильно продумали его работу, и часть его реализации стоит перенести в другой класс, либо выделить в совершенно новый класс. Еще одно правило создания класса – количество открытых (public) методов должно быть порядка 5, так как при большем числе дальнейшая поддержка подобного класса может стать затруднительной. Более подробно о повышении качества кода можно ознакомиться в книге Стива МакКоннелла «Совершенный код».

ПРИМЕЧАНИЕ: обратите внимание, что для переменных типа Person, добавляемых в список, память может быть выделена как динамически, так и в статической области памяти. Поэтому такие методы, как Remove ни в коем случае не должны освобождать память по указателям на персон при удалении. Фактически это означает, что при вызове метода Remove персона удаляется только из списка, но сама переменная Person должна остаться.