Связанные структуры

1 Структуры и алгоритмы компьютерной обработки данных РАЗДЕЛ 3 СВЯЗАННЫЕ СТРУКТУРЫ ДАННЫХ. ДРЕВОВИДНЫЕ СТРУКТУРЫ Примечание Данный материал является вспомогательной презентацией и сам по себе не может рассматриваться как конспект курса лекций или описание его полного содержания.

2 Линейный однонаправленный список: общее представление last first next... 0 ListItem

3 Линейный однонаправленный список: элемент списка template <class ITEM> struct ListItem { ITEM data; ListItem<ITEM> next; }; ListItem( const ITEM& data, ListItem<ITEM> next = 0 ) { this->data = data; this->next = next; }

4 Линейный однонаправленный список: определение класса template <class T> class List { public: class RemoveItemException{}; class InsertItemException{}; private: template <class ITEM> struct ListItem { //... }; ListItem<T> first; //... };

5 Инициализация template <class T> List::List() { first = 0; } // Возможно, еще какие-то действия // в зависимости от // содержания полей класса List //...

6 Проверка наличия элементов template <class T> bool List::isEmpty() { return first == 0; }

7 Добавление элемента связанные структуры в начало списка item first...

8 Добавление элемента в начало списка template <class T> void List::pushBegin( const T& data ) { ListItem<T> item = new ListItem<T>( data, first ); } first = item;

9 Добавление элемента в конец списка current item first... 0

10 Добавление элемента в конец списка template <class T> void pushend( const T& data ) { ListItem<T> item = new ListItem<T>(data); if( first == 0 ) { first = item; return; } ListItem<T> current = first; while( current->next!= 0 ) current = current->next; } current->next = item; return;

11 Удаление элемента из начала списка delitem first...

12 Удаление элемента из начала списка template <class T> void List::removeBegin() { ListItem<T> delitem; if( first == 0 ) throw RemoveItemException(); delitem = first; first = delitem->next; } delete delitem; return;

13 Удаление всего списка template <class T> void List::removeAll() { if( first == 0 ) throw RemoveItemException(); } while( first!= 0 ) { removebegin(); } return;

14 Удаление элемента из конца списка current first

15 Удаление элемента из конца списка template <class T> void List::removeEnd() { ListItem<T> current; if( first == 0 ) throw RemoveItemException(); current = first; if( current->next == 0 ) return removebegin(); } // Продолжение на следующем слайде...

16 Удаление элемента из конца списка / template <class T> void List::removeEnd() // Продолжение / // Цикл поиска элемента, // предшествующего последнему while( current->next->next!= 0 ) current = current->next; // Собственно удаление последнего элемента delete current->next; current->next = 0; } return;

17 Поиск элемента (есть или нет) template <class T> bool List::hasItem( const T& datatofind ) { ListItem<T> current; } current = first; while( current!= 0 ) { if( current->data == datatofind ) return true; current = current->next; } return false;

18 Реализация класса: демонстрационный пример и анализ Проектные проблемы Невозможно реализовать в классе List все операции над элементами списка, которые только могут потребоваться Содержание операции над объектом данных, хранящихся в списке, зависит от структуры этого объекта Необходимо дать возможность работать с отдельными объектами данных, хранящихся в списке, но не с внутренней реализацией списка Такие проблемы характерны и для других вмещающих типов

19 Итерация списка: вариант с SimpleVisitor // Абстрактный класс определяет общую схему // обработки объекта данных, хранящихся // в списке template <class T> class SimpleVisitor { public: virtual void process( T& data ) = 0; }; // Чтобы определить конкретную реализацию, // следует определить производный от // SimpleVisitor класс и предоставить // реализацию метода process

20 Итерация списка: вариант с SimpleVisitor template <class T> class ListIt { //... public: void iterate( SimpleVisitor<T>& visit ) { ListItem<T> current = first; while( current!= 0 ) { visit.process( current->data ); current = current->next; } }

21 Итерация списка: вариант с SimpleVisitor: пример Пользовательский тип хранимых объектов класс Rational Задачи итерирования вычисление суммы рациональных дробей, хранящихся в списке печать в выходной поток всех объектов, хранящихся в списке

22 Модернизация метода: используем функциональные объекты template <class T> class ListIt { //... public: template <class Op> void iterate( Op& callback ) { ListItem<T> current = first; while( current!= 0 ) { callback( current->data ); current = current->next; } }

23 Вариант с функциональным объектом: пример Пользовательский тип хранимых объектов класс Rational Задачи итерирования вычисление суммы рациональных дробей, хранящихся в списке Изменение значений хранимых объектов Не нужно наследовать SimpleVisitor Определяем класс с перегруженной операцией ()

24 Недостатки схемы с построением внутреннего итератора Способ обхода жестко определен в классе List Осуществляется просмотр всех элементов: это нужно не для всякого процесса Пример с реализацией процесса поиска элемента в предположении, что метода hasitem нет

25 ListFind: «прямолинейный» вариант class ListFind : public SimpleVisitor<int> { int valuetofind; bool found; public: ListFind( int uservalue ) : valuetofind( uservalue ), found( false ) {} void process( int& data ) { if( data == valuetofind ) found = true; } }; bool isfound() { return found; }

26 ListFind: использование механизма обработки исключений class ListFindModified : public SimpleVisitor<int> { int valuetofind; bool found; public: class ObjectFoundException {}; ListFindModified( int uservalue ) : valuetofind( uservalue ), found( false ) {} }; void process( int& data ) { if( data == valuetofind ) throw ObjectFoundException(); }

27 Недостатки внутреннего итератора (продолжение) Искусственность использования исключений в предложенном варианте Необходимость определять visitor или функциональный объект Не любой процесс сводится к независимой последовательной обработке Поиск повторяющихся элементов (-) Проверка упорядоченности (+, но не очень просто) Нельзя одновременно обрабатывать несколько списков (например, сравнить два списка)

28 Внешнее управление работой внутреннего итератора // Абстрактный итератор template <class T> class Iterator { public: virtual void start() = 0; virtual bool hasmore() = 0; virtual void next() = 0; virtual T get() = 0; };

29 Внешнее управление работой внутреннего итератора template <class T> class ListIt : public Iterator<T> { //... public: class BadIteratorException{}; void start() { currentit=first; } bool hasmore() { return currentit!=0; } void next() { if( currentit == 0 ) throw BadIteratorException(); currentit = currentit->next; } T get() { if( currentit == 0 ) throw BadIteratorException(); return &(currentit->data); private: ListItem<T> first; ListItem<T> currentit; };

30 Пример использования: внешняя реализация HasItem template <class T> bool HasItem( ListIt<T>& list, const T& checkdata ) { for( list.start(); list.hasmore(); list.next() ) // Необходима точная согласованность вызовов { T ptritem = list.get(); if( ptritem == checkdata ) return true; } return false; } // В каждый момент времени над списком может быть // запущен только ОДИН итератор

31 Построение внешнего итератора Информация о текущем положении итератора хранится в самостоятельном объекте Поскольку итератор использует внутреннее представление списка, обычно класс итератора определяют внутри класса списка (с предоставлением итератору дружественного доступа) Можно определить несколько классов итераторов, реализующих различные варианты итерации Прямая итерация Обратная итерация Итерация вставки

32 Построение внешнего итератора: демонстрационный пример

33 Список из сложных объектов: пример пользовательского типа class DataSet { int array; int size; public: DataSet( int customsize = 0 ); DataSet( const int ptr, int size ); DataSet( const DataSet& ref ); DataSet(); }; DataSet& operator=( const DataSet& arg2 ); int operator==( const DataSet& arg2 );

34 Деревья: теория и практика использования root leaves а б

35 Вершина (узел) дерева общего вида template <class T> struct TreeNode { typedef TreeNode<T> PtrTreeNode; PtrTreeNode parent; // Родительский узел }; int numchild; // Число узлов-потомков PtrTreeNode child; // Адрес начала массива // указателей на дочерние // узлы T ptrdata; //Указатель на объект данных

36 Вершина (узел) бинарного дерева template <class T> struct BinaryTreeNode { BinaryTreeNode<T> left; // Указатель на // корень левого // поддерева BinaryTreeNode<T> right; // Указатель на // корень правого // поддерева BinaryTreeNode<T> parent; // Указатель на // родительский // узел T data; // Объект данных };

37 Важные для практики частные случаи бинарных деревьев Во многих случаях информация о взаимном расположении узлов может определяться способом размещения древовидной структуры в памяти Удается обойтись без явных указателей на дочерние и родительские узлы «Упакованное» бинарное дерево

38 Высота бинарного дерева уровней

39 Полностью сбалансированное дерево уровня

40 Хранение сбалансированного дерева в виде одномерного массива Пусть r номер узла Тогда номер родителя: r/2 Номер корня левого поддерева: 2r Номер корня правого поддерева: 2r+1 Индекс элемента в массиве: r-1 Дерево можно «упаковать» в одномерный массив и операции над узлами свести к операциям над индексами элементов массива

41 Просмотр от самого левого узла к самому правому // Обработать бинарное дерево из n узлов с // корнем в узле noroot void ProcessTree( int noroot ) { if( noroot > n ) return; // выход из рекурсии // Обработать левое поддерево ProcessTree( noroot2 ); // Обработать корень дерева //... // Обработать правое поддерево ProcessTree( noroot2 + 1 ); }

42 Алгоритм бинарного поиска: постановка задачи поиска Задача поиска ставится следующим образом. Пусть имеется множество уникальных ключей { k, k2,..., k 1 n } k i, i 1, n На этом множестве определено отношение строгого порядка. С каждым из ключей связаны некоторые объекты данных из множества { j 1, m} j k s Требуется по заданному ключу найти и, следовательно, связанные с искомым ключом данные.

43 Использование бинарного дерева Пусть K(r) значение ключа, соответствующее узлу с номером r Разместим n ключей таким образом, чтобы: в левом поддереве относительно r все ключи, меньшие K(r) в правом поддереве относительно r все ключи, большие K(r)

44 Использование бинарного дерева: переформулируем для массива Пусть noroot номер обозреваемого корневого узла (индекс=noroot -1) Тогда: Индекс корня левого поддерева 2noRoot- 1 (там все ключи, меньшие K(noRoot)) Индекс корня правого поддерева (2noRoot+1)-1 (там все ключи, большие K(noRoot))

45 Подготовка дерева бинарного поиска struct SearchTreeNode { KeyType key; // Ключ DataType ptrdata; // Указатель на объект // данных, связанных с // данным ключом }; SearchTreeNode btree[ n ]; // Дерево поиска, // упакованное в массив Первоначально ключи должны быть упорядочены

46 Подготовка дерева бинарного поиска void PrepareTree( int noroot ) { if( noroot > n ) return; // выход из рекурсии // Подготовить левое поддерево PrepareTree( noroot2 ); // Занести ключ и информацию о данных в корень btree[ noroot-1 ].key = GetNextKey(); btree[ noroot-1 ].ptrdata = GetNextData(); } // Подготовить правое поддерево PrepareTree( noroot2 + 1 );

47 Поиск в подготовленном дереве bool BSearch( KeyType key, int& ixfound ) { int noroot = 1; while( noroot <= n ) { if( key == btree[ noroot-1 ].key ) { ixfound = noroot-1; return true; } if( key < btree[ noroot-1 ].key ) noroot = noroot2; else noroot = noroot2 + 1; } ixfound = -1; return false; }

48 Поиск в подготовленном дереве: иллюстрация работы алгоритма btree key ptrdata H D J B F I K A C E G key E E<H 1 H искомые данные 2 D 3 J E>D 4 B 5 F 6 I 7 K E<F 8 A 9 C 10 E 11 G ixfound 9 noroot-1

49 Сортировка с использованием бинарного дерева (heap sort) Другие названия: «сортировка сложным выбором», «пирамидальная сортировка» Алгоритм также использует обработку «упакованного» бинарного дерева В основе понятие пирамиды: Для любого узла r, имеющего одного потомка, справедливо: k( r) k(2 r Для любого узла r, имеющего двух потомков, справедливо: k( r) k(2 r) k( r) k(2 r 1) )

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

51 Пирамидальная сортировка: описание процесса сортировки for( last = n; // Номер последнего узла // в начале равен n last > 0; // Продолжаем, пока не рассмотрели // все узлы last-- ) { // Поменять местами узлы с номерами // 1 (корневой) и last //... // Восстановить пирамиду из дерева с узлами // от 1 до last-1 (просеивание) //... }

52 Пирамидальная сортировка: восстановление пирамиды (1)

53 Пирамидальная сортировка: восстановление пирамиды (2)

54 Пирамидальная сортировка: восстановление пирамиды (3)

55 Пирамидальная сортировка: восстановление пирамиды (4)

56 Пирамидальная сортировка: функция просеивания «дыр» template <class T> void Sift( T a, int root, int last ) { int hole = root; T x = a[ hole-1 ]; for( ; ; ) { int left = 2hole; int right = left + 1; int pretender; // Номер претендента if( left > last ) break; // Если лист // просеивание // закончено

57 Пирамидальная сортировка: функция просеивания «дыр» // Теперь нужно выбрать // претендента на заполнение «дыры» if( left == last ) pretender = left; else { if( a[ left-1 ] < a[ right-1 ] ) pretender = right; else pretender = left; }

58 Пирамидальная сортировка: функция просеивания «дыр» // Если претендент не лучше x // просеивание закончено if( a[ pretender-1 ] < x ) break; if( a[ pretender-1 ] == x ) break; // Иначе: претендент заполняет «дыру», // при этом образуется новая «дыра» a[ hole-1 ] = a[ pretender-1 ]; hole = pretender; } // Рано или поздно x «возвращается» // в дерево a[ hole-1 ] = x; } // конец функции Sift

59 Что нужно для сортировки всей последовательности? Подготовить пирамиду в самом начале (это достигается за n/2 просеиваний) Осуществить цикл из n-1 просеиваний, на каждой итерации которого элемент с наибольшим значением ключа занимает свое окончательное место

60 Иллюстрация первоначальной подготовки пирамиды (1) Листы дерева

61 Иллюстрация первоначальной подготовки пирамиды (2)

62 Иллюстрация первоначальной подготовки пирамиды (3)

63 Иллюстрация первоначальной подготовки пирамиды (4)

64 Иллюстрация первоначальной подготовки пирамиды (5)

65 Иллюстрация первоначальной подготовки пирамиды (6)

66 Иллюстрация первоначальной подготовки пирамиды (7)

67 Иллюстрация первоначальной подготовки пирамиды (8)

68 Пирамидальная сортировка: реализация template <class T> void HeapSort( T a, int n ) { int root, last; // Первоначальная подготовка пирамиды for( root = n/2; root > 0; root-- ) Sift( a, root, n ); // Цикл сортировки for( last = n; last > 1; last-- ) { T copy = a[ 0 ]; a[ 0 ] = a[ last-1 ]; a[ last-1 ] = copy; Sift( a, 1, last-1 ); } }

69 Двоичные деревья поиска общего вида Дерево поиска как динамическая структура Добавление узла в двоичное дерево поиска Удаление узла из дерева поиска Обеспечение сбалансированности дерева поиска

70 Определение типа для представления узла дерева template <class T> struct BinaryTreeNode { BinaryTreeNode<T> left; // Указатель на // корень левого // поддерева BinaryTreeNode<T> right; // Указатель на // корень правого // поддерева BinaryTreeNode<T> parent; // Указатель на // родительский // узел T data; // Объект данных };

71 Добавление узла в двоичное дерево поиска и поиск в бинарном дереве добавляется узел

72 Удаление узла из двоичного дерева поиска: пример 15 удаляется узел

73 Удаление узла из двоичного дерева поиска: общий случай todelete y заменяет узел todelete y x x У ДОЧЕРНИХ УЗЛОВ НЕ ЗАБЫТЬ ОБНОВИТЬ СВЕДЕНИЯ О РОДИТЕЛЯХ! У РОДИТЕЛЬСКИХ УЗЛОВ НЕ ЗАБЫТЬ ОБНОВИТЬ СВЕДЕНИЯ О ДОЧЕРНИХ УЗЛАХ!

74 Поддержание сбалансированности: красно-черные деревья самый длинный путь кратчайший путь черные узлы красные узлы NIL NIL NIL NIL NIL NIL NIL NIL

75 Узел красно-черного дерева typedef enum { BLACK, RED } NodeColor; template <class T> struct RBTreeNode { BinaryTreeNode<T> left; BinaryTreeNode<T> right; BinaryTreeNode<T> parent; NodeColor color; }; T data;

76 Определение сторожевого узла // Определение сторожевого узла // (фиктивного черного листа // красно-черного дерева #define NIL &sentinel RBTreeNode<TYPE> sentinel = { NIL, NIL, NULL, BLACK, 0 }; RBTreeNode<TYPE> root = NIL;

77 Вставка узла в красно-черное дерево Рассматриваем дерево поиска Первый этап вставка узла в бинарное дерево (узел окрашивается в красный цвет) Второй этап восстановление красночерных свойств дерева, если они нарушены варианты нарушений

78 Вставка узла в красно-черное дерево Вариант 1: красный «родитель» - красный «дядя» B B parent uncle parent uncle A C A C x x

79 Вставка узла в красно-черное дерево Вариант 2: красный «родитель» - черный «дядя» B A parent uncle A C x B x γ δ ε α β γ C α β δ ε

80 Самостоятельная работа Изучить реализацию функции вставки окраска узлов поворот фрагмента дерева вправо поворот фрагмента дерева влево Изучить реализацию функции удаления


Источник: http://docplayer.ru/34312140-Razdel-3-svyazannye-struktury-dannyh-drevovidnye-struktury.html


Закрыть ... [X]

Раздел 3 связанные структуры данных. древовидные структуры - PDF - Скрапбукинг идеи оформления страница



Связанные структуры Связанные структуры Связанные структуры Связанные структуры Связанные структуры Связанные структуры