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

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

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

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. Тесты.