Динамические структуры данных. 1) Получить практические навыки работы с однонаправленными списками;

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

1) Получить практические навыки работы с однонаправленными списками;

2) получить практические навыки работы с двунаправленными списками;

3) получить практические навыки работы с деревьями.

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

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

• однонаправленные списки;
• двунаправленные списки;
• стек;
• очередь;
• бинарные деревья.

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

Однонаправленные списки

Наиболее простой динамической структурой является однонаправленный список, элементами которого служат объекты структурного типа (рис.).

Рис.. Линейный однонаправленный список

Описание простейшего элемента такого списка выглядит следующим образом:

struct имя_типа

{

информационное поле;

адресное поле;

};

· информационное поле – это поле любого, ранее объявленного или стандартного, типа;

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

struct point

{

int data; //информационное поле

point* next; //адресное поле

};

Информационных полей может быть несколько.

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

//создание однонаправленного списка

//добавление в конец

point* make_list(int n)

{

point*beg;//указатель на первый элемент

point*p,*r;//вспомогательные указатели

beg=new(point);//выделяем память под первый элемент

cout<<"\n?";

cin>>beg->data;//вводим значение информационного поля

beg->next=0;//обнуляем адресное поле

//ставим на этот элемент указатель p (последний элемент)

p=beg;

for(int i=0;i<n-1;i++)

{

r=new(point);//создаем новый элемент

cout<<"\n?";

cin>>r->data;

r->next=0;

p->next=r;//связываем p и r

//ставим на r указатель p (последний элемент)

p=r;

}

return beg;//возвращаем beg как результат функции

}

Для обработки списка организуется цикл, в котором нужно переставлять указатель p с помощью оператора p=p->next на следующий элемент списка до тех пор, пока указатель p не станет равен 0, т. е. будет достигнут конец списка.

void print_list(point* beg)

//печать списка

{

point* p=beg;//начало списка

while(p!=0)

{

cout<<p->data<<"\t";

p=p->next;//переход к следующему элементу

}

}

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

Рис. Добавление элемента в список

point* add_point(point* beg, int k)

//добавление элемента с номером k

{

point*p=beg;//встали на первый элемент

point*New=new(point);//создали новый элемент

cout<<"Key?";cin>>New->data;

if(k==0)//добавление в начало, если k=0

{

New->next=beg;

beg=New;

return beg;

}

for(int i=0;i<k-1&&p!=0;i++)

p=p->next;//проходим по списку до(k-1) элемента или до конца

if(p!=0)//если k-й элемент существует

{

New->next=p->next;//связываем New и k-й элемент

p->next=New;//связываем (k-1)элемент и New

}

return beg;

}

Рис. Удаление элемента из списка

point* del_point(point*beg,int k)

//удаление элемента с номером k из списка

{

point*p=beg;

if(k==0)//удаление первого элемента

{

beg=beg->next;

delete p;

return beg;

}

//проходим по списку до элемента с номером k-1

for(int i=1;i<k&&p->next!=0;i++)

p=p->next;

/*если такого элемента в списке нет, то возвращаем указатель на начало списка в качестве результата функции*/

if (p->next==0) return beg;

point* r=p->next;//ставим указатель r на k-й элемент

p->next=r->next;//связываем k-1 и k+1 элемент

delete r;//удаляем k-й элемент из памяти

return beg;

}

Двунаправленные списки

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

//формирование двунаправленного списка

struct point

{

char *key;//адресное поле – динамическая строка

point *next;//указатель на следующий элемент

point *pred;//указатель на предыдущий элемент

};

point* make_point()

//создание одного элемента

{

point*p=new(point);

p->next=0;p->pred=0;//обнуляем указатели

char s[50];

cout<<"\nEnter string:";

cin>>s;

p->key=new char[strlen(s)+1];//выделение памяти под строку

strcpy(p->key,s);

return p;

}

point*make_list(int n)

//создание списка

{

point *p,*beg;

beg=make_point();//создаем первый элемент

for(int i=1;i<n;i++)

{

p=make_point();//создаем один элемент

//добавление элемента в начало списка

p->next=beg;//связываем р с первым элементом

beg->pred=p;//связываем первый элемент с p

beg=p;// p становится первым элементом списка

}

return beg;

}

Очередь и стек

Очередь и стек – это частные случаи однонаправленного списка.

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

· top() – доступ к вершине стека

· pop() – удаление элемента из вершины;

· push() – добавление элемента в вершину.

Такой принцип обслуживания называют LIFO (last in – first out, последний пришел, первый ушел).

В очереди добавление осуществляется в один конец, а удаление из другого конца. Такой принцип обслуживания называют FIFO (first in – first out, первый пришел, первый ушел). Для очереди также определяют функции:

· front() – доступ к первому элементу;

· back() – доступ к последнему элементу;

· pop() – удаление элемента из конца;

· push() – добавление элемента в начало.

Бинарные деревья

Бинарное дерево – это динамическая структура данных, состоящая из узлов, ка­ждый из которых содержит, кроме данных, не более двух ссылок на различные бинарные деревья. На каждый узел имеется ровно одна ссылка.

Описать такую структуру можно следующим образом:

struct point

{

int data;//информационное поле

point *left;//адрес левого поддерева

point *right;//адрес правого поддерева

};

Начальный узел называется корнем дерева. Узел, не имеющий поддеревьев, называется листом. Исходящие узлы называются предками, входящие — потом­ками. Высота дерева определяется количеством уровней, на которых располага­ются его узлы.

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

В идеально сбалансированном дереве количество узлов справа и сле­ва отличается не более чем на единицу.

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

Деревья и списки являются рекурсивными структурами, т. к. каждое поддерево также является деревом. Таким образом, дерево можно определить как рекурсивную структуру, в которой каждый элемент является:

· либо пустой структурой;

· либо элементом, с которым связано конечное число поддеревьев.

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

Обход дерева

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

Рис. Бинарное дерево

На этом дереве можно определить три метода упорядочивания:

Слева направо: Левое поддерево – Корень – Правое поддерево;

Сверху вниз: Корень – Левое поддерево – Правое поддерево;

Снизу вверх: Левое поддерево – Правое поддерево – Корень.

Эти три метода можно сформулировать в виде рекурсивных алгоритмов.

void Run(point*p)

//обход слева направо

{

if(p)

{

<обработка p->data>

Run(p->left);//переход к левому поддереву

Run(p->right);//переход к правому поддереву

}

}

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

Формирование дерева

//построение дерева поиска

Point* first(int d)//формирование первого элемента дерева

{

Point* p=new Point;

p->key=d;

p->left=0;

p->right=0;

return p;

}

//добавление элемента d в дерево поиска

Point* Add(Point*root,int d)

{

Point*p=root;//корень дерева

Point*r;

//флаг для проверки существования элемента d в дереве

bool ok=false;

while(p&&!ok)

{

r=p;

if(d==p->key)ok=true;//элемент уже существует

else

if(d<p->key)p=p->left;//пойти в левое поддерево

else p=p->right;//пойти в правое поддерево

}

if(ok) return p;//найдено, не добавляем

//создаем узел

Point* New_point=new Point();//выделили память

New_point->key=d;

New_point->left=0;

New_point->right=0;

// если d<r->key, то добавляем его в левое поддерево

if(d<r->key)r->left=New_point;

// если d>r->key, то добавляем его в правое поддерево

else r->right =New_point;

return New_point;

}

//построение идеально сбалансированного дерева

point* Tree(int n,point* p)

{

point*r;

int nl,nr;

if(n==0){p=NULL;return p;}

nl=n/2;

nr=n-nl-1;

r=new point;

cout<<"?";

cin>>r->data;

r->left=Tree(nl,r->left);

r->right=Tree(nr,r->right);

p=r;

return p;

}

Постановка задачи

1. Сформировать однонаправленный список, тип информационного поля указан в варианте.
2. Распечатать полученный список.
3. Выполнить обработку списка в соответствии с заданием.
4. Распечатать полученный список.
5. Удалить список из памяти.
6. Сформировать двунаправленный список, тип информационного поля указан в варианте.
7. Распечатать полученный список.
8. Выполнить обработку списка в соответствии с заданием.
9. Распечатать полученный список.
10. Удалить список из памяти.
11. Сформировать идеально сбалансированное бинарное дерево, тип информационного поля указан в варианте.
12. Распечатать полученное дерево.
13. Выполнить обработку дерева в соответствии с заданием, вывести полученный результат.
14. Преобразовать идеально сбалансированное дерево в дерево поиска.
15. Распечатать полученное дерево.

Варианты

№ варианта	Однонаправленный	Двунаправленный	Бинарное дерево
	Тип информационного поля int. Удалить из списка все элементы с четными информационными полями.	Тип информационного поля char*. Добавить в список элемент с заданным номером.	Тип информационного поля char. Найти количество элементов с заданным ключом.
	Тип информационного поля double. Удалить из списка все элементы с четными номерами (2, 4, 6 и. т. д.).	Тип информационного поля char*. Добавить в список элементы с номерами 1, 3, 5 и т. д.	Тип информационного поля int. Найти максимальный элемент в дереве.
	Тип информационного поля int. Удалить из списка первый элемент с четным информационным полем.	Тип информационного поля double. Добавить в список элемент после элемента с заданным информационным полем.	Тип информационного поля char*. Найти количество листьев в дереве.
	Тип информационного поля int. Удалить из списка последний элемент с четным информационным полем.	Тип информационного поля char*. Добавить в список элемент с заданным номером.	Тип информационного поля double. Найти минимальный элемент в дереве.
	Тип информационного поля char*. Добавить в список элемент после элемента с заданным информационным полем.	Тип информационного поля int. Удалить из списка все элементы с четными информационными полями.	Тип информационного поля char. Найти высоту дерева.
	Тип информационного поля char*. Добавить в список элемент с заданным номером.	Тип информационного поля double. Удалить из списка все элементы с четными номерами (2, 4, 6 и. т. д.).	Тип информационного поля int. Найти среднее арифметическое элементов дерева.
	Тип информационного поля double. Добавить в список после каждого элемента с отрицательным информационным полем элемент с информационным полем равным 0.	Тип информационного поля int. Удалить из списка первый элемент с четным информационным полем.	Тип информационного поля char*. Найти количество элементов дерева, начинающихся с заданного символа.
	Тип информационного поля char*. Добавить в список элементы с номерами 1, 3, 5 и т. д.	Тип информационного поля int. Удалить из списка последний элемент с четным информационным полем.	Тип информационного поля char. Найти количество элементов с заданным ключом.
	Тип информационного поля int. Удалить из списка все элементы с четными информационными полями.	Тип информационного поля char*. Добавить в список элементы с номерами 1, 3, 5 и т. д.	Тип информационного поля double. Найти максимальный элемент в дереве.
	Тип информационного поля double. Удалить из списка все элементы с четными номерами (2, 4, 6 и. т. д.).	Тип информационного поля char*. Добавить в список элемент после элемента с заданным информационным полем.	Тип информационного поля int Найти количество листьев в дереве.
	Тип информационного поля int. Удалить из списка первый элемент с четным информационным полем.	Тип информационного поля char*. Добавить в список элемент с заданным номером.	Тип информационного поля double. Найти минимальный элемент в дереве.
	Тип информационного поля int. Удалить из списка последний элемент с четным информационным полем.	Тип информационного поля char*. Добавить в список элемент с заданным номером.	Тип информационного поля char. Найти высоту дерева.
	Тип информационного поля char*. Добавить в список элемент после элемента с заданным информационным полем.	Тип информационного поля double. Удалить из списка все элементы с отрицательными информационными полями.	Тип информационного поля int. Найти среднее арифметическое элементов дерева.
	Тип информационного поля char*. Добавить в список элемент с заданным номером.	Тип информационного поля int. Удалить из списка последний элемент с четным информационным полем.	Тип информационного поля char. Найти количество элементов с заданным ключом.
	Тип информационного поля double. Добавить в список после каждого элемента с отрицательным информационным полем элемент с информационным полем равным 0.	Тип информационного поля int. Удалить из списка все элементы с четными номерами (2, 4, 6 и. т. д.).	Тип информационного поля char*. Найти количество элементов дерева, начинающихся с заданного символа
	Тип информационного поля char*. Добавить в список элементы с номерами 1, 3, 5 и т. д.	Тип информационного поля int. Удалить из списка первый элемент с четным информационным полем.	Тип информационного поля int. Найти максимальный элемент в дереве.
	Тип информационного поля int. Удалить из списка все элементы с четными информационными полями.	Тип информационного поля char*. Добавить в список элемент с заданным номером.	Тип информационного поля double. Найти количество листьев в дереве.
	Тип информационного поля double. Удалить из списка все элементы с четными номерами (2, 4, 6 и. т. д.).	Тип информационного поля char*. Добавить в список элемент с заданным номером.	Тип информационного поля int. Найти минимальный элемент в дереве.
	Тип информационного поля int. Удалить из списка первый элемент с четным информационным полем.	Тип информационного поля char*. Добавить в список элементы с номерами 1, 3, 5 и т. д.	Тип информационного поля char. Найти высоту дерева.
	Тип информационного поля int. Удалить из списка последний элемент с четным информационным полем.	Тип информационного поля char*. Добавить в список элемент после элемента с заданным информационным полем.	Тип информационного поля double. Найти среднее арифметическое элементов дерева.
	Тип информационного поля char*. Добавить в список элемент после элемента с заданным информационным полем.	Тип информационного поля int. Удалить из списка все элементы с четными информационными полями.	Тип информационного поля char*. Найти количество элементов дерева, начинающихся с заданного символа.
	Тип информационного поля char*. Добавить в список элемент с заданным номером.	Тип информационного поля double. Удалить из списка все элементы с четными номерами (2, 4, 6 и. т. д.).	Тип информационного поля char. Найти количество элементов с заданным ключом.
	Тип информационного поля double. Добавить в список после каждого элемента с отрицательным информационным полем элемент с информационным полем равным 0.	Тип информационного поля int. Удалить из списка первый элемент с четным информационным полем.	Тип информационного поля char*. Найти количество листьев в дереве.
	Тип информационного поля char*. Добавить в список элементы с номерами 1, 3, 5 и т. д.	Тип информационного поля int. Удалить из списка последний элемент с четным информационным полем.	Тип информационного поля double. Найти максимальный элемент в дереве.
	Тип информационного поля int. Удалить из списка все элементы с четными информационными полями.	Тип информационного поля char*. Добавить в список элементы с номерами 1, 3, 5 и т. д.	Тип информационного поля double. Найти минимальный элемент в дереве.

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

1. Описания структур для формирования списков/деревьев, а также функции для их обработки сохранить в библиотечном файле с расширением .h (например, point.h). Функцию main() сохранить в файле с расширением .cpp. Библиотечный файл подключить с помощью директивы #include “имя_файла.h”.

2. Для выделения памяти под информационные поля типа char* использовать операцию new, для удаления из памяти – операцию delete.

3. Для формирования элементов списков/дерева написать отдельные функции.

4. Для формирования списков/дерева, удаления добавления элементов, поиска заданных элементов написать отдельные функции.

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

6. Если в списке/дереве отсутствуют элементы, соответствующие критерию поиска (например, при удалении элемента с номером k, k больше, чем количество элементов в списке), должно быть выведено сообщение о том, что требуемые элементы не найдены.

7. Интерфейс реализовать с помощью текстового меню.

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

1. Постановка задачи (общая и для конкретного варианта).
2. Определения функций для реализации поставленных задач.
3. Определение функции main().
4. Тесты.

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