Хеш-таблица (Hash-Table). Реализация C++.

Хеш-таблица-динамическая структура данных, которая реализует интерфейс ассоциативного массива, то есть позволяет хранить пару <Ключ, Значение> и выполнять 3 операции: добавление новой пары, операции поиска, операции удаления по ключу.

Чтобы понять, что такое хеш-таблица, вспомним массив. Мы можем получить доступ к элементу с помощью его ключа, причем может быть такой случай, что есть ячейки содержащие элементы и есть не содержащие.
Представим ситуацию, что нам нужно найти элемент, например, массив состоит из строк большой длины. Нам придется нашу подстроку поиска сравнивать со всеми элементами массива, что неудобно, так как поиск займет O(n). НО мы хотим O(1). Решение есть! Использовать специальную хеш функцию, для того, чтобы мы имели доступ по индексу.

Пример:

• Каждой строке соответствует индекс равный (n=длина строки-1). Например: строка "Alex" индекс 3. Вот так можно записать строки. 
• Хеш функция у нас будет: Hash_Func(string)=Strlen(string) (то есть вычисление длины).
• Доступ к массиву мы получаем вот так: Mas[Hash_Func(string)].

length        value
------------------------
 2           "joe"
 3           "Alex"
 4           "Pavel"
Но! вот в чем беда! Если мы хотим вставить еще 1 имя, например "Petr", то этому имени будет соответствовать ОДИН И ТОТ ЖЕ КЛЮЧ 3, который является индексом 3. Это называется Коллизией, когда один и тот же ключ указывает на несколько значений ключа.
Иллюстрация коллизии (2 ключа относятся к одной и той же ячейки массива, ключи k2 и k3):

Разрешение случаев с коллизией является важной задачей Computer Science. Решениями проблемы являются:

1. Метод цепочек (открытое хеширование).
2. Метод открытой адресации (закрытое хеширование).

1. Идея метода цепочек состоит в том, что все элементы множества, которые относятся к одному и тому же ключу входят в связный список.

Итак! В этом примере, в i позициях содержится указатель на голову списка. Т.е. в массиве с ячейками (1,3,4); в остальных других хранится null (0,2,5);

Возвращаясь к нашему примеру с именами, переделаем его в соответствии с новым методом:
length        value
------------------------
 2           *head1 ["Joe"->"Rex"->Null]
 3           *head2 ["Alex"->"Petr"->"Oleg"->Null]
 4           *head3 ["Pavel"->Null]
В этом примере 0,1,5 элементы указатели равны Null
Процедура вставки происходит так: Вычисляется хеш-функция от строки и вставляется в голову списка (push_front) на определенный индекс равный значению функции.
Вставка происходит за O(1).
Поиск или удаление элемента зависит от длины списка, худший случай: O(n) - когда, все элементы хешируются в одну и ту же ячейку. Если функция распределяем n ключей по m ячейкам таблицы равномерно, то в каждом списке будет содержаться порядка k=n/m ключей. Это число называется коэффициентом заполнения хеш-таблицы. В этом случае время поиска: O(1+k), это показано в книжке Кормана, могу скинуть ссылку на нее, если интересно.
Добавлю, что в случае, когда коэффициент заполнения будет слишком велик, надо будет увеличить размер массива и, возможно, перестроить таблицу.

2. Идея метода открытой адресации состоит в том, что нету никаких списков, а все элементы хранятся в хеш-таблице. Ячейка хранит либо элемент либо NULL (по желанию ваш граничный элемент, в C# если использовать тип object, то null).

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

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

Общий прием состоит в следующем: если хеш-функция вырабатывает позицию для первого кандидата i = Hash_Func(key) Mod (capacity), то последующие позиции определяются как i + increment, i +2 * increment, i +3 * increment и так далее, все по модулю capacity. Величина increment вычисляется как: 
Hash_Func(key) Mod (capacity -1)

Пример:

i,i1,i2 ячейки заняты, i=2, i1=4, i2=6, i3=8, capacity=11
Последующие index=i+increment (increment = 2 Mod 10 = 2)

Хеш-таблицы имеют очень большое практическое применение:

• Для поиска информации о водители лишь по его номеру в водительском удостоверении.

• Таблица символов компилятора. Хеширование является методом ускорения поиска. Компилятор встре­чает некоторую лексему и пытается найти ее в своей базе данных или таб­лице символических имен. Таблица символических имен современного компилятора в MS Windows может содержать несколько тысяч или десятков тысяч лексем. Для ускорения поиска был придуман следующий прием. Компилятор, найдя лексему в тексте программы, определяет ее хеш-ключ. Наша лексема — это просто слово, состоящее из последовательности кодов символов. Для определения хеш-кода следует сложить все коды символов. Лексем с таким хеш-кодом в базе данных уже значительно меньше. Компи­лятор определяет номер списка с заданным кодом и перебирает этот спи­сок, а не всю базу данных.
• При программировании шахмат тоже используется хеширование. Основная особенность состоит в том, что хеш-индекс должен очень точно отражать позицию, и поиск должен производиться максимально быстро. У нас даже нет времени на перебор списков с одним индексом. Списков, как правило, нет вообще. Для каждого значения хеш-ключа существует только одна по­зиция. Если возникла коллизия и встретилась позиция с таким же ключом, то она записывается поверх прежней. Зачем при программировании шахмат и других подобных игр хеширование и запоминание позиций? Дело в том, что при переборе мы имеем не дерево игры в прямом смысле, а граф. По­зиции повторяются через некоторое количество полуходов, и даже в одну и ту же позицию можно прийти различными путями. Можно воспользоваться некоторой информацией о позиции, которая уже встречалась. Самое про­стое и эффективное — это использовать позицию, чтобы улучшить порядок ходов. Это особенно выразительно при итеративных углублениях. Улучше­ние упорядочивания ходов — основное назначение хеш-таблицы. Переста­новки или повторы позиций тоже играют свою роль. Особенно их много в конце игры.
• Для баз данных телефонных номеров.
• Каталог книг.
• Для хранения паролей пользователей.
• Браузер хранит адреса посещенных страниц в хеш-таблице.

Реализация на языке С++ доделывается, не хватает нескольких функций. Если, есть какие-то предложения, пишите в комментарии.

////////////////////////////////Hash_Table class//////////////////////////////////////////

template < typename TKey, typename TValue>
class Hash_Table {
private:
 unsigned static const defaultCapacity=17;
 std::vector< Single_Linked_List< std::pair< TKey,TValue> > > table;
 unsigned capacity;
 unsigned count;

public:
 Hash_Table();
 Hash_Table(unsigned divisor);
 ~Hash_Table();
 unsigned HashIntKey(int key) const;
 unsigned DataToKey(const TValue& Data) const;
 const TValue& Search(const TKey& key) const;
 void Insert(const TKey& key_val,TValue& el_value);
 void Output() const;// output the hash table
 void Delete(TValue element);
 const TValue& operator[](int key);
};

template < typename TKey, typename TValue>
unsigned Hash_Table< TKey,TValue>::HashIntKey(int key) const{
 return key%capacity;
}


template < typename TKey, typename TValue>
Hash_Table< TKey,TValue>::Hash_Table(){
 //////////////////////////////////////////////////////////////////////////
 count=0;
 capacity=defaultCapacity;
 //////////////////////////////////////////////////////////////////////////
 table.resize(defaultCapacity, Single_Linked_List >());
}

template < typename TKey, typename TValue>
Hash_Table< TKey,TValue>::Hash_Table(unsigned divisor){
 count=0;
 capacity=divisor;
 //////////////////////////////////////////////////////////////////////////
 table.resize(capacity, Single_Linked_List< pair< TKey,TValue> >());
}

template < typename TKey, typename TValue>
Hash_Table< TKey,TValue>::~Hash_Table(){
 table.clear();
}

template < typename TKey, typename TValue>
const TValue& Hash_Table< TKey,TValue>::Search(const TKey& key) const{
 unsigned pos=HashIntKey(key);
 //////////////////////////////////////////////////////////////////////////
 Single_Linked_List< pair< TKey,TValue> >& lst = table.at(pos);
 try {
  if(lst.GetSize()< 1) //if list hasnt elements
   throw inv_ex;
  for(Single_Linked_List< pair< TKey,TValue> >::iterator it = lst.begin(); it != lst.end(); ++it) {
   if(it->first == key){
    return (it->second); 
   } 
  }
 }
 catch(exception &e){
  cout< < e.what()< < endl;
 }
 Insert(key,TValue()); //insert element with default data
 return operator[](key);
}

template < typename TKey, typename TValue>
void Hash_Table< TKey,TValue>::Insert(const TKey& key_val,TValue& el_value){
 unsigned pos=HashIntKey((int)key_val); //get pos by hashing
 //////////////////////////////////////////////////////////////////////////
 pair< TKey,TValue> toInsert(key_val, el_value);
 //////////////////////////////////////////////////////////////////////////
 Single_Linked_List< pair >& lst = table.at(pos);
   //If key already store, replace data
  if(!lst.isEmpty()) {
  for(Single_Linked_List< pair >::iterator it = lst.begin(); it != lst.end(); ++it) {
   if(it->first == key_val){
    //it->second=el_value;
    it.SetValue(toInsert);
        return;
      } 
    }
  }
    //No items with that key, store a new one
  table[pos].Push_Front(toInsert);
 count++;
}

template < typename TKey, typename TValue>
void Hash_Table< TKey,TValue>::Output() const {
 int NumOfCollision = 0;
 //////////////////////////////////////////////////////////////////////////
 cout< < "Hash table capacity "< 1) {
   NumOfCollision += table[i].GetSize() - 1;
  }
  //////////////////////////////////////////////////////////////////////////
    for(Single_Linked_List< pair >::const_iterator it = table[i].begin(); it != table[i].end();it++) {
   cout< < "HashTable["< < i< < "]: "< < (it->second)< < endl;
    }
  }
 cout< < "N.Hash collisions: "< < NumOfCollision< < endl;
}


template < typename TKey, typename TValue>
const TValue& Hash_Table< TKey,TValue>::operator[](int key){
 unsigned pos=HashIntKey(key);
 //////////////////////////////////////////////////////////////////////////
 Single_Linked_List< pair< TKey,TValue> >& lst = table.at(pos);
 try {
  if(lst.GetSize()< 1)
   throw inv_ex;
  for(Single_Linked_List< pair< TKey,TValue> >::iterator it = lst.begin(); it != lst.end(); ++it) {
   if(it->first == key){
    return (it->second);
   } 
  }
 }
 catch(exception &e){
  cout< < e.what()< < endl;
 }
 Insert(key,TValue());
 return operator[](key);
}

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

Hash_Table< int,string> ht(9);
  ht.Insert(223, string("Ololoshenka"));
  ht.Insert(5345, string("This is matrix, Neo"));
  ht.Insert(1, string("Use yourrr power, Luke"));
  
  ht.Output();
 cout< < ht[1]< < endl;

Вывод:

Read More

Двусвязный список (Doubly Linked List). Реализация на C#

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

Пример двусвязного списка:

• Также есть головной элемент First, который является ссылочной переменной и указывает на начало списка. First.Prev=null (ограничитель)
• Ссылочная переменная Last, указывает на конец списка. Last.Next=null (ограничитель)
• Ссылочная переменная Current, которая указывает на текущий элемент (выступает обычно в роли итератора списка, т.е. элемента с помощью которого мы можем перемещаться по списку)
• Беззнаковая переменная целого типа uint size, которая содержит информацию о количестве элементов в списке.

Раньше я упомянул ограничители, это специальные ссылки которые ссылаются на null. Их используют для того, чтобы обозначить конец или начало списка. То есть для того, чтобы остановить пользователя от доступа в другие участки памяти, не относящиеся к списку.

Я покажу только самые базовые операции вставки в конец и начало, проиллюстрирую и подробно опишу, что происходит. По просьбам в комментарии могу описать другой метод в списке.

Push_Front:

Цель: Вставить новый элемент в начало списка, сделав его первым, надо, чтобы, First ссылался на этот объект.

Синим отмечены ссылки, левая - Prev, правая - Next, серая - Data (наши данные), стрелки - на что они ссылаются.

В начальном состоянии Prev и Next ссылаются на null, First.Prev = null, First.Next ссылается на след объект и т.д.

1. Мы сделаем так, чтобы новый объект ссылался на First
2. Потом мы сделаем так, чтобы и First и newNode ссылались на новый объект.
3. Теперь просто новый объект ссылается на предыдущий первый.

Push_Back:

Цель, добавить новый элемент в конец, Last должен ссылаться на новый объект.

В начальном состоянии Last.Next=null.

1. Last.Next теперь ссылается на новый объект.
2. newNode.Prev ссылается на Last.
3. Last ссылается на новый объект.

Каждый объект описан классом Node (Узел)

• object _Data - наши данные, которые содержатся в узле.
• Node _Next - ссылка на следующий элемент.
• Node _Prev - ссылка на предыдущий элемент.
• Ну и свойства их описывающие, для доступа к ним.

public class Node {
        private object _Data;
        private Node _Next;
        private Node _Prev;
        public object Value
        {
            get { return _Data; }
            set { _Data = value; }
        }
        public Node(object Data)
        {
            this._Data = Data;
        }
        public Node Next
        {
            get { return this._Next; }
            set { this._Next = value; }
        }
        public Node Prev
        {
            get { return this._Prev; }
            set { this._Prev = value; }
        }
    }

UML диаграмма двусвязного списка:

Код двусвязного списка:

class Doubly_Linked_List
    {
        private Node First;
        private Node Current;
        private Node Last;
        private uint size;

        public Doubly_Linked_List()
        {
            size = 0;
            First = Current = Last = null;
        }

        public bool isEmpty //проверка на пустоту
        {
            get
            {
                return size == 0;
            }
        }

        public void Insert_Index(object newElement, uint index) //вставить по индекусу
        {
            if (index < 1 || index > size) //вброс ошибки, если неправильный индекс
            {
                throw new InvalidOperationException();
            }
            else if (index == 1) //если начало
            {
                Push_Front(newElement);
            }
            else if (index == size) //если конец
            {
                Push_Back(newElement);
            }
            else //иначе ищем элемент с таким индексом
            {
                uint count = 1;
                Current = First;
                while (Current != null && count != index)
                {
                    Current = Current.Next;
                    count++;
                }
                Node newNode = new Node(newElement); //создаем объект
                Current.Prev.Next = newNode; 
                newNode.Prev = Current.Prev;
                Current.Prev = newNode;
                newNode.Next = Current;
            }
        }

        public void Push_Front(object newElement)
        {
            Node newNode=new Node(newElement);

            if (First == null)
            {
                First = Last = newNode;
            }
            else
            {
                newNode.Next = First; 
                First = newNode; //First и newNode указывают на один и тот же объект
                newNode.Next.Prev = First;
            }
            Count++;
        }

        public Node Pop_Front()
        {
            if (First == null)
            {
                throw new InvalidOperationException();
            }
            else
            {
                Node temp = First;
                if (First.Next != null)
                {
                    First.Next.Prev = null;
                }
                First = First.Next;
                Count--;
                return temp;
            }
        }

        public void Push_Back(object newElement)
        {
            Node newNode = new Node(newElement);

            if (First == null)
            {
                First = Last = newNode;
            }
            else
            {
                Last.Next = newNode;
                newNode.Prev = Last;
                Last = newNode;
            }
            Count++;
        }

        public Node Pop_Back()
        {
            if (Last == null)
            {
                throw new InvalidOperationException();
            }
            else
            {
                Node temp = Last;
                if (Last.Prev != null)
                {
                    Last.Prev.Next = null;
                }
                Last = Last.Prev;
                Count--;
                return temp;
            }
        }

        public void ClearList() //полностью очистить список
        {
            while (!isEmpty)
            {
                Pop_Front();
            }
        }

        public uint Count //свойство для size
        {
            get { return size; }
            set { size = value; }
        }

        public void Display() //вывести в прямом порядке
        {
            if (First == null)
            {
                Console.WriteLine("Doubly Linked List is empty");
                return;
            }
            Current = First;
            uint count=1;
            while (Current != null)
            {
                Console.WriteLine("Element " + count.ToString()+" : " + Current.Value.ToString());
                count++;
                Current = Current.Next;
            }
        }

        public void ReverseDisplay() //вывести в обратном порядке
        {
            if (Last == null)
            {
                Console.WriteLine("Doubly Linked List is empty");
                return;
            }
            Current = Last;
            uint count = 1;
            while (Current != null)
            {
                Console.WriteLine("Element " + count.ToString() + " : " + Current.Value.ToString());
                count++;
                Current = Current.Prev;
            }
        }

        public void DeleteElement(uint index){ //удалить элемент по индексу
            if (index < 1 || index > size)
            {
                throw new InvalidOperationException();
            }
            else if (index == 1)
            {
                Pop_Front();
            }
            else if (index == size)
            {
                Pop_Back();
            }
            else
            {
                uint count = 1;
                Current = First;
                while (Current != null && count != index)
                {
                    Current = Current.Next;
                    count++;
                }
                Current.Prev.Next = Current.Next;
                Current.Next.Prev = Current.Prev;
            }
        }

        public Node FindNode(object Data) //найти Node и вернуть его
        {
            Current = First;
            while (Current != null)
            {
                Current = Current.Next;
            }
            return Current;
        }

        public uint GetIndex(object Data) //достать индекс по значению элемента
        {
            Current = First;
            uint index = 1;
            while (Current != null)
            {
                Current = Current.Next;
                index++;
            }
            return index;

        }

    }

Read More

Очередь (Queue). C# Реализация на массиве.

Очередь - динамическая структура данных, которая работает по принципу "Первым вошел - первым вышел". По английски FIFO (first-in, first-out). 

Графическое представление очереди:

Видно, что у нас здесь 2 переменные back, front, которые являются указателями на конец и соответственно начало очереди. С помощью метода Dequeue мы можем вытаскивать элемент с начала очереди. С помощью метода Enqueue  - добавлять в конец.

Жизненный пример очереди - очередь в больнице. Когда подходим в очередь, то встаем в конец.(Enqueue) Первые элементы входят в кабинет.(Dequeue)

Или еще один пример, пуля в автомате. Та пуля, которая находится сверху вылетает быстрее других. Несколько пуль не могут вылететь одновременно. Пример не работает в случае футуристических автоматов :D

Применение стека:

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

Реализация выполнена на массиве, с некоторыми хитростями.

UML Диаграмма:

Действующие лица:

1. _array - массив, где хранятся наши элементы очереди.
2. capacity - количество элементов под которые выделено памяти, запомните, что не всегда size==capacity
3. defaultCapacity - количество элементов под которые выделено памяти в момент создания объекта Очередь.
4. head - переменная которая указывает на головной элемент.
5. tail - переменная которая указывает на задний элемент.
6. size - количество элементов в очереди.
7. Count - свойство для вывода size.

Реализация:

public class CQueue
    {
        private T[] _array;
        private int size;
        private const int defaultCapacity = 10;
        private int capacity;
        private int head;
        private int tail;

        public CQueue()
        {
            capacity = defaultCapacity;
            this._array = new T[defaultCapacity];
            this.size = 0;
            this.head = -1;
            this.tail = 0;
        }

        public bool isEmpty() //проверка на пустоту
        {
            return size == 0;
        }

        public void Enqueue(T newElement)
        {
            if (this.size == this.capacity)
            {
                T[] newQueue = new T[2 * capacity];
                Array.Copy(_array, 0, newQueue,0, _array.Length);
                _array = newQueue;
                capacity *= 2;
            }
            size++;
            _array[tail++%capacity] = newElement;
        }

        public T Dequeue()
        {
            if (this.size == 0)
            {
                throw new InvalidOperationException();
            }
            size--;
            return _array[++head%capacity];
        }


        public int Count
        {
            get
            {
                return this.size;
            }
        }
    }

Read More

Стек (Stack). C# Реализация на массиве.

Стек - динамическая структура данных, которая работает по принципу "Последним вошел - первым вышел". По английски LIFO (last-in, first-out).
Графическое представление стека:

Как можно видеть мы добавляем один элемент с помощью метода Push, и потом с помощью метода Pop мы его вытаскиваем.
Жизненный пример: Стопка тарелок, допустим для того чтобы накрыть на стол нам надо 3 тарелки, мы будем с вершины брать по одной тарелке, т.е. 3 раза вызовем метод S.Pop(). То есть, для того, чтобы снять n-3 тарелку, мы должны сначала снять n, n-1, n-2 тарелки.
Применение:

• Стек можно использовать для того, чтобы избавится от рекурсии, так идея вызова рекурсивных функций сама использует стек. Адрес возврата и локальные переменные рекурсивной функции записываются в стек, благодаря чему каждый следующий рекурсивный вызов этой функции пользуется своим набором локальных переменных и за счёт этого работает корректно. Единственный минус такого использования в том, что очень хорошо отъедает память :D, поэтому надо избегать программ, которая допускает большой глубины рекурсии.
• Стек используется при парсинге HTML/XML деревьев.
• Существует стек вызовов (call stack), в который заносится информация о возврате из функции. Например при вызове функции A() из функции main, в стек вызовов заносится адрес возврата, то есть адрес следующей функции, в которую должно передатся управление, например у нас функция (не рекурсивна) A() {return 0;}, то адрес возврата у нас будет адрес функции main(). К тому же заносится информация о локальных переменных и значения параметров функции.
• Например, у нас есть функция main из нее вызывается функция A(), из A() вызывается B(), то стек у нас будет вот такой: Head-> [B(),A(),main()]. B()-вершина стека, ниже будет А(), и на дне стека main(). При возврате из B() управление передастся к A(), при возврате из A() управление передастся к main().
• Также стек используется в калькуляторе. Например вот из этого:
• Input: (((8 + 1) - (7 - 4)) / (11 - 9))  Превратили в вот это с помощью стека (из инфиксной в обратную польскую)
  Output: 8 1 + 7 4 - - 11 9 - /
  
  

В C# внутреннее устройство класса стека основано на использовании массива, что меня очень удивило, так как реализация на массивах не очень оптимальна в плане выделения памяти.
В своей реализации я сделаю только самые базовые метода без Enumerator'а и других интересных фичей, поэтому, увы, foreach к моему стеку не работает. :(
UML диаграмма:

Реализация:

public class CStack< T>
    {
        private T []_array; //массив для хранения данных типа T
        private const int defaultCapacity=10; //вместимость по умолчанию, потом можно расширить
        private int size; //размер

        public CStack(){ //конструктор
            this.size=0;
            this._array=new T [defaultCapacity];
        }

        public bool isEmpty() //проверка на пустоту
        {
            return this.size == 0;
        }

        public virtual int Count //параметр для вывода размера 
        {
            get
            {
                return this.size;
            }
        }

        public T Pop() //метод взятия с вершины
        {
            if (this.size == 0)
            { //вброс ошибки при взятии с пустого стека (Overflow)
                throw new InvalidOperationException();
            }
            return this._array[--this.size];
        }

        public void Push(T newElement)
        {
            if (this.size == this._array.Length) //если у нас переполнение...
            { //знаю, что неоптимально, но это c#...
                T[] newArray = new T[2 * this._array.Length];
                Array.Copy(this._array, 0, newArray, 0, this.size);
                this._array = newArray; //просто создаем новый массив с двойным размером
            } 
            this._array[this.size++] = newElement; //вставляем элемент
        }

        public T Peek()
        {
            if (this.size == 0)
            {
                throw new InvalidOperationException();
            }
            return this._array[this.size - 1];
        }
    }

Демонстрация работы:

CStack stack = new CStack();
            stack.Push(3);
            stack.Push(18);
            Console.WriteLine("element Number "+stack.Count.ToString()+" is "+stack.Pop().ToString());
            Console.WriteLine("element Number " + stack.Count.ToString() + " is " + stack.Pop().ToString());
            Console.ReadLine();

Read More

Пирамидальная сортировка (Heapsort) + Реализация на С++

Сортировка основана на применении структуры данных - пирамида (сортирующего дерева, кучи). Пирамида - двоичное дерево, для которого выполняются условия:

1. Значение в любой вершине не меньше, чем значения её потомков.
2. Глубина листьев (расстояние до корня) отличается не более чем на 1 слой.
3. Последний слой заполняется слева направо

Пример представления массива в виде пирамиды:

Для организации такой кучи мы будем использовать одномерный массив. Для того, чтобы свойства кучи выполнялись, нужна функция, к-ая Max_Heapify(A,i), где i - индекс массива. Она опускает значение элемента A[i] вниз по пирамиде, до тех пор, пока поддерево с корнем отвечающим элементу A[i] не становится невозрастающей пирамидой, то есть все элементы ОТСОРТИРОВАНЫ. (или по другому бинарное дерево сбалансировано)

Пример работы Max_Heapify можно почитать на вики : Max_Heapify Example

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

inline unsigned Parent(unsigned i) {
 return floor((double)(i/2));
}

inline unsigned Left(unsigned i) {
 return ((2*i)+1);
}

inline unsigned Right(unsigned i) {
 return ((2*i)+2);
}

Реализуем функцию проталкивания меньшего элемента вниз пирамиды.
Пример проталкивания:

template < typename Type>
void Max_Heapify(Type mas[], unsigned index, unsigned heap_size){
 unsigned l=Left(index); //индекс лев. дочернего эл-та
 unsigned r=Right(index);  //индекс прав. дочернего эл-та

 unsigned largest; //хранит индекс большего эл-та
 if ((l< heap_size l="l" mas="mas">mas[index])) { //проверка, что левый элемент больше
  largest=l; //левый дочерний элемент больший элемент
 }
 else 
  largest=index; //mas[index] - больший элемент
 if ((r< heap_size mas="mas" r="r">mas[largest]))
  largest=r;
 if (largest!=index){ //если есть из дочерних элементов большие
  swap(mas[index],mas[largest]); //обменяемся с большим
  Max_Heapify(mas,largest, heap_size); //вызовем рекурсивно опять для того же элемента
 }
}

Для построения пирамиды из массива реализуем процедуру Build_Max_Heap
template < typename Type>
void Build_Max_Heap (Type mas[], unsigned heap_size){
 for (unsigned index=Parent(heap_size-1); index>0; index--){
  Max_Heapify(mas, index, heap_size);
 }
}

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

template < typename Type>
void Heapsort(Type mas[], unsigned mas_size){
 unsigned heap_size=mas_size;
 Build_Max_Heap(mas,heap_size);
 for (unsigned index=mas_size-1; index>=1; index--){
  swap(mas[0],mas[index]);
  heap_size--;
  Max_Heapify(mas,0, heap_size);
 }
}

Пирамидальная сортировка для ленивых :D

template < typename Iterator>
void heapsort(Iterator begin, Iterator end)
{
    std::make_heap(begin, end);
    std::sort_heap(begin, end);
}
int main {
    double valsToSort[] = {9,4,2,1,5,6};
    const int VSIZE = sizeof(valsToSort)/sizeof(*valsToSort);
    heapsort(valsToSort, valsToSort+VSIZE); 
}

Read More

Реализация сортировки слиянием (Merge Sort) на С++

const int INFINITY=1E10;

template < typename Type>
void Merge(Type mas[], int left, int m, int right) {
 int n1=m-left+1;
 int n2=right-m;
 vector < Type> L(n1+1);
 vector < Type> R(n2+1);
 for (int i=0; i< n1; ++i){
  L[i]=mas[left+i];
 }
 for (int i=0; i< n2; ++i){
  R[i]=mas[m+i+1];
 }

 L[n1]=INFINITY;
 R[n2]=INFINITY;

 for (int k=left,i=0,j=0;k< =right;++k) {
  if (L[i]< =R[j]){
   mas[k]=L[i]; 
   i++;
  }
  else {
   mas[k]=R[j];
   j++;
  }
 }
}

template < typename Type>
void Merge_Sort (Type mas[], int l, int r) {
 if (l>=r) return;
 int middle=(l+r)/2;
 Merge_Sort (mas,l,middle);
 Merge_Sort(mas,middle+1,r);
 Merge(mas,l,middle,r);
}

Read More

Сортировка вставками (Insertion Sort) + Реализация С++

Предположим, что у нас массив разбит на 2 части : отсортированную и не отсортированную. 
Основная идея сортировки вставками состоит в том, что при добавлении нового элемента в уже отсортированный список его стоит сразу вставлять в нужное место, а затем заново сортировать весь список. 
Этот процесс повторяется до тех пор, пока весь массив не станет отсортированным. В процессе работы меняются местами только соседние элементы.
В худшем случае сложность алгоритма : O(n^2), время работы алгоритма будет меньше, если большая часть массива уже отсортирована. Плюс в том, что требуется O(1) дополнительной памяти.
Реализация:

template < typename Type>
void Insertion_Sort(Type mas[],unsigned long size){
 Type temp;
 unsigned long index;
 unsigned long prevIndex;
 for (index=0; index=0 && mas[prevIndex]>temp;prevIndex--)
   mas[prevIndex+1]=mas[prevIndex]; //пока у нас пред. индекс >=0 и если пред элемент>a[index]
  mas[prevIndex+1]=temp; //заменим элемент
 }
}

Read More

Сортировка пузырьком (Bubble Sort) + Реализация С++

Идея сортировки пузырьком состоит в том, что на каждой итерации попарно сравниваются элементы и если элементы находятся в неправильном порядке, происходит их обмен.
Время работы O(n^2)
Алгоритм:

1. Начинаем с конца массива, берем элемент a[j], где j=n-1 и сравниваем попарно элементы a[j] и a[j-1]
2. Если a[j]<a[j-1], то swap(a[j],a[j-1]), т.е. более легкий элемент всплывает
3. Уменьшаем j и повторяем до тех пор, пока выполняетсяс j>i

Графическая иллюстрация (стырено с algolist):

Реализация:

template < typename Type >
void Bubble_Sort(Type mas[], unsigned long size){
 for (unsigned long i=0; i< size; i++)
  for (unsigned long j=size-1; j > i; j--)
   if (mas[j]< mas[j-1])
    swap (mas[j],mas[j-1]);
}

Read More

Сортировка выбором (Selection Sort) + Реализация С++

Идея сортировки выбором состоит в том, что на i-ом шаге итерации ищется минимальный элемент в одномерном массиве размером n и этот элемент меняется местами с i-эм элементом массива. т.е. swap(min(к-ый нашли),a[i]). В результате
Время работы алгоритма O(n^2), так как для нахождения минимального элемента происходит n сравнений + по в процессе увеличения количества итераций, число сравнений уменьшается(n-1,n-2...1)
Алгоритм:

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

Пример можно посмотреть здесь (стырено с algolist)

Реализация:

template < typename Type>
void Selection_Sort(Type mas[], unsigned long size){
 unsigned long minIndex;
 for (unsigned long i=0; i< size; i++){
  minIndex=i;
  for (unsigned long j=i+1; j< size; j++){
   if (mas[j]< mas[minIndex])
    minIndex=j;
  }
  if (minIndex!=i){
   swap(mas[minIndex],mas[i]);
  }
 }
}

Read More

Алгоритм Дейкстры. Реализация на очереди С++.

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

1. INITIALIZE_SINGLE_SOURCE(G,S)
2. S=0
3. Q=V[s] //добавляем стартовую вершину в очередь с приоритетом
4. While(!Q.empty()) //пока очередь не пуста
1. u=Extract_Min(Q) //берем вершину из очереди с минимальным расстоянием
2. for v из Adj[u] //для любой смежной вершины v к u
1. Relax (u,v,w) //производим релаксацию ребра

Процесс релаксации описан в алгоритме Форда-Беллмана:

Форд-Беллман

Реализация:

 
void Dijkstra_Shortest_Path(unsigned NumOfVertices, unsigned start){
int M [5][5] = {{0,6,0,7,0}, {0,0,5,8,-4}, {0,-2,0,0,0},{0,0,-3,0,9},{2,0,7,0,0}};
priority_queue< pair< unsigned int,double>, vector< pair > , Prioritize > Q;    
    int u,v,w;
    vector< double> d(NumOfVertices,INFINITY);
    d[start] = 0;
    Q.push(pair< unsigned int,double >(start,d[start]));
    while(!Q.empty())
    {
        u = Q.top().first;
    final.push(u);
        Q.pop();
        for(int v = 0 ; v < NumOfVertices ; v++)
        {
   if (M[u][v]) {
            w = M[u][v];
            cout< d[u] + w)
            {
                d[v] = d[u] + w;
                Q.push(pair(v,d[v]));
            }
   }
        }
    }
    for(int i=0; i< NumOfVertices; i++) 
   cout< <"Vertex "< < i< <" cost of vertex: "< < d[i]< < endl;
}

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

 
class Prioritize
{
public:
    int operator() ( const pair& p1, const pair& p2 )
    {
        return p1.second < p2.second;
    }
};

Read More

Топологическая сортировка+Поиск кратчайшего пути

Топологическая сортировка - линейное упорядочивание всех его вершин. Предположим, что граф не содержит циклов, так как если он содержит циклы, то такая сортировка не возможна.

Граф, который не содержит циклов, называется ациклическим.

Ориентированные ациклические графы используются для указания последовательности действия, где каждое действие зависит от других. Например: установка программ с помощью системы управления пакетами или сборка с помощью Makefil'ов. (wikipedie (c))

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

На рисунке представлена последовательность одевания утром. Первым делом идут носки (socks), потом трусы (undershorts) и самым последним идет пиджак у него время закрытия 4.

Для реализации топологической сортировки нам всего лишь нужно добавить в реализацию поиска в глубину глобальный стэк для вершин - stack<unsigned int> answer;
И! где мы красим вершину в черный после цикла, добавим добавление вершины в стек:

answer.push(u);

Теперь нам осталось всего лишь вывести стек) Вот и получили ответ.

Приложение: поиск кратчайшего пути в ациклическом графе.
Алгоритм выглядит так:

1. Сначала делаем топологическую сортировку графа
2. Для каждой вершины u в порядке топологической сортировки
1. Для каждой смежной вершине v к вершине u
1. Делаем релаксацию, т.е. запускаем старую добрую RELAX(u,v,w) 

Read More

Разложение Шеннона по таблице истинности

Мое разложение Шеннона получилось ну сильно неоптимальным, можно было легче сделать через манипуляции с таблицей истинности.
Разложение Шеннона-способ представление функции с помощью подфункций размером уже от (n-1) переменных.
Алгоритм (он у нас для n разбиений, все переменные для разбиения находятся в очереди):

1. Сначала мы берем СДНФ и разбиваем ее на конъюнкции
2. Эти конъюнкции уже разбиваем на те, которые относятся к первой переменной разбиения, которая равна в таблице истинности единице, и те которым соответсвует 0.
3. Запускаем процедуру декомпозиции

Сама идея процедуры очень проста, но реализовано все очень прожорливо, через вектора:

queue <int> variables - очередь, которая хранит в себе все переменные, которые мы выбрали для разбиения.

Мы разбиваем на конъюнкции , где xi=1 (plus) и xi=0 (minus) и смотрим 3 случая:

1. Все вектора конъюнкций не пусты
2. plus вектор пуст
3. minus вектор пуст

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

В общем на blogspote ограничение на 200 символов, так что по просьбе могу скинуть на хостинг проект.

Read More

Поиск в глубину у графа

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

1. DFS(G) - нужна для инициализации всех переменных и цикла для прохода по всем вершинам
2. DFS_VISIT(u) - где u - вершина, которую нужно посетить. Эта процедура обработки вершина, где проиходит окраска каждой вершины, обозначения времени открытия и закрытия вершины (закрытие - окраска в черный цвет, открытие - окраска в серый цвет).

DFS(G)

Для каждой вершины u из множества вершин Графа

Окрасить в белый цвет

Инициализировать счетчик времени нулем
Для каждой вершины u из множества вершин Графа

Если вершина окрашена в белый, т.е. не пройдена

Посетить ее, т.е. запустить процедуру DFS_VISIT(u)

DFS_VISIT(u)

Окрасить вершину в серый цвет
Увеличить счетчик времени time++
Обозначить время открытия d[u]=time
Для каждой вершины v смежной нашей вершине u

Если вершина v окрашена в белый, т.е. не пройдена

Обозначить u как вершину предшествующую вершине v
Рекурсивно вызвать процедуру обработки для v: DFS_VISIT(v)


Окрасить вершину u в черный цвет
Обозначить время закрытия f[u]=time=time+1

Использующиеся данные:

Глобальная область видимости:

vector<unsigned int> color; //вектор цветов, 0 - белый, 1 - серый, 2 - черный

vector<unsigned int> predcessors; //вектор предшественников, если хотите построить дерево глубины

vector<unsigned int> d; //вектор к-ый хранит время открытия вершины

vector<unsigned int> f;  //вектор к-ый хранит время закрытия вершины

unsigned int timer; //таймер

ConnectionMatrix-матрица смежности графа

Реализация процедуры DFS:

void DFS (unsigned int NumOfVertices, double **ConnectionMatrix){

color.assign(NumOfVertices,0); //инициализация всех векторов

predcessors.resize(NumOfVertices);

d.resize(NumOfVertices);

f.resize(NumOfVertices);

timer=0; //обнуляем таймер

for (int u=0; u<NumOfVertices; u++){

if (color[u]==0) //если не пройденна - посетить

DFS_VISIT(u, ConnectionMatrix, NumOfVertices);

}

}

Реализация DFS_VISIT:

void DFS_VISIT(unsigned int u, double **ConnectionMatrix, unsigned int NumOfVertices){

color[u]=1; //теперь вершина окрашена в серый

timer++; //увеличим время

d[u]=timer; //время открытия

for (unsigned int v=0; v<NumOfVertices; v++){

if (ConnectionMatrix[u][v])

if (color[v]==0){

predcessors[v]=u;

DFS_VISIT(v, ConnectionMatrix, NumOfVertices); //рекурсивынй вызов для                       вершины v

}

}

color[u]=2; //покрасим в черный

f[u]=timer=timer+1; //обозначим время закрытия вершины u

}

Read More

Поиск в ширину у графа

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

• Суть данного алгоритма в том, что в процессе обхода мы идем вширь, то есть, перед тем, как приступить к поиску вершин на расстоянии k+1, мы выполняем обход всех вершин на расстоянии k.
• Для отслеживания процесса обхода, мы окрашиваем вершины в белый, серый или черный цвета.
• Сначала мы все вершины у нас белые, начальную вершину мы красим серым цветом, для обозначения окраса у нас есть вектор colors[numOfVertices]:
1. color[i]=0 - белый цвет
2. color[i]=1 - серый цвет
3. color[i]=2 - черный цвет
• Еще у нас есть вектор расстояний d[numOfVertices] - очень удобная штука, чтобы посмотреть, есть ли у нас какие нибудь несвязные вершины.

Алгоритм:

1. Пока очередь не пуста:
1. Взять первый элемент из очереди u
2. Цикл для каждой связной с вершиной u вершиной (v)
1. если у нас вершина v не окрашенная
1. окрасит в серый
2. пометить в векторе, что d[v]=d[u]+1
3. добавить вершину в очередь
3. Окрасить вершину u в черный цвет

Реализация:

void BFS(unsigned int NumOfVertices, double **ConnectionMatrix, unsigned int start, unsigned int target){
  //BFS algorithm
 if (target==start) return;
 const double INFINITY=1E10;
 unsigned int u=start;
 //0-white, grey-1, black-2
 vector  d (NumOfVertices,INFINITY); //вектор расстояний
 d[start]=0;
 vector  color(NumOfVertices,0); //вектор закраски
 color[start]=1;
 vector  predcessors (NumOfVertices);
 predcessors[start]=-1;
 queue  q;
 q.push(start);
 while (!q.empty()) {
  u=q.front();
  q.pop();
  for (int v=0; v< NumOfVertices; v++) {
   if (color[v]==0&&ConnectionMatrix[u][v]) {
    color[v]=1;
    d[v]=d[u]+1;
    predcessors[v]=u;
    q.push(v);
   }
  }
  color[start]=2;
 }
 cout< path;
 for (int cur=target; cur!=-1; cur=predcessors[cur])
  path.push_back (cur);
 reverse (path.begin(), path.end());
 cout << "Path from " << start << " to " << target << ": ";
 for (size_t i=0; i

Read More

Алгоритм Форда-Беллмана. Реализация на С++

Алгоритм Форда-Беллмана применяется для нахождения кратчайшего пути от одной вершины до всех остальных во взвешенном графе.
Главное его преимущество перед алгоритмом Дейкстры в том, что он способен работать с отрицательными весами, НО имеет главный минус в производительности-работает за O(|V| × |E|), так как инициализация матрицы занимает время O(V) и на каждый проход надо V(E).

Случай 1: Граф без отрицательного цикла.
Для начала реализуем простейшую реализацию для графа без отрицательных весов, этот случай будет рассмотрен в другой статье. Увы, эта реализация будет бесконечно делать релаксацию, так как при суммарном весе цикла меньше 0, при обходе сколько угодно раз, длина кратчайшего пути будет выражаться большим по модулю отрицательным числом.

Итак, все действующие лица:

• Переменная numOfVertices обозначает количество вершин в графе.
• Переменная start нужна для обозначения номера начальной вершины.
• Вектор расстояний d[numOfVertices] который имеет размер такой же как и количество вершин в графе (numOfVertices), он хранит в себе ВСЕ КРАТЧАЙШИЕ РАССТОЯНИЯ от нашей стартовой вершины до ВСЕХ ДРУГИХ.
• Структура Edge (Ребро) для описания ребра, ясно, что ребро связывает вершину u с вершиной v и имеет вес w.

struct Edge {

 unsigned int u;

 unsigned int v;

 double w;

};

•  Будем использовать вектор для хранения ребер vector<Edge>EdgeList, так как к вектору удобно обращаться по индексу;
•  Переменная const double INFINITY=1E+10 для инициализации расстояний в начале работы функции.
• Введем функцию релаксации ребер Relax (unsigned int index, vector <double> &d) для того, чтобы алгоритм был более понятен, какой кусок кода за что отвечает. index-индекс текущего ребра, d - вектор расстояний.

void Relax (unsigned int index, vector <double> &d){

 if (d[EdgeList[index].v]>d[EdgeList[index].u]+EdgeList[index].w){

d[EdgeList[index].v]=d[EdgeList[index].u]+EdgeList[index].w;

}

}

          Процесс релаксации ребра заключается в проверке ребра на то, можно ли улучшить путь из вершины u в v.
Примеры с картиночками можно почитать у Кормена на странице 670.

Сам алгоритм состоит в том, чтобы:

1. Cначала инициализируем все расстояния бесконечными величинами, а расстояние стартовой вершины нулем.
2. Цикл for для каждой вершины
1. Вложенный цикл где для каждого ребра идет процесс релаксации
3. Вывод расстояний

Простейшая неоптимизированная реализация:

void Bellman_Ford_Shortest_Path(double start, unsigned int numOfVertices){

 vector<double> d (numOfVertices, INFINITY);

 d[start]=0;

 for (unsigned int i=0; i<numOfVertices-1; i++){

  for (unsigned int j=0; j<EdgeList.size();j++){

   Relax(j,d);//РЕЛАКСАЦИЯ РЕБРА

  }

 }

 for (int i=0; i<d.size(); i++){

  if (d[i]<INFINITY){ //ЕСЛИ ЕСТЬ ПУТЬ

   cout<<"vertex "<< i+1 <<") "<<d[i]<<endl;

  }

  else cout<<"vertex "<< i+1 <<") "<<"No way to this vertex"<<endl;

 }

}

Брр. тега <code> На блогспоте не вижу, очень неудобно внедрять код.

Read More