Программирование на C++

10 способов прострелить себе ногу

Создание веб приложений

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

Подпись для третьего не придумал

Американец изнасиловал лошадь, потому что думал, что у них родится кентавр

Помощь обездоленным якутам на дальнем севере

Благотворительность (на правах рекламы)

пятница, 25 января 2013 г.

Перегрузка оператора вызова функций operator () в С++


Оператор вызова функций должен быть перегружен только как нестатический член класса!
Формат: 
тип operator () (список_параметров), где список параметров может быть неопределенным и значения могут быть определены по умолчанию.

Оператор вызова функций применяется в том случае, когда нужно использовать объект как функцию, в этом случае такие объекты называются объектами-функциями или функторами (functors). Рассмотрим пример на классе Point (точка):

class Point{
private:
 int x;
 int y;
public:
 Point(int x, int y){
  this->x=x;
  this->y=y;
 }
 Point() {}
 Point operator()(int i,int j){
  x=i;
  y=j;
  return *this;
 }
 Point operator+(Point obj){
  Point temp;
  temp.x = obj.x + x;
  temp.y = obj.y + y;
  return temp;
 }
 void show(){
  cout< < "x: "< < x< < " y: "< < y< < endl;
 }
};

int _tmain(int argc, _TCHAR* argv[])
{
 Point obj1(10, 20), obj2(1, 1); //вызываются конструкторы формата Point(x,y)

 obj1.show();
 obj1(7, 8); // вызывается оператор() который меняет наши значения.
 obj1.show();

 obj1 = obj2 + obj1(10, 10); // может быть использовано в выражениях
 obj1.show();

 getchar();
 return 0;
}
Результаты:
10,20
7,8
11,11

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

list  lst;
//инициализируем весь список
for_each(lst.begin(),lst.end(), Point(1,1));
///теперь все значения точек в списке поменяются на 1,1
///отличный способ использования stl

Также перегрузка этого оператора применяется в задаче индексирования многомерного массива и в задаче выделения подстроки.

Объект функция имеет такими преимуществами перед обычными функциями:

  • Каждому объекту функции соответствует свой тип.
  • Объект функции можно инициализировать на стадии выполнения перед ее вызовом.


понедельник, 21 января 2013 г.

Обфускация С# кода средствами VS2010

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

Dotfuscator Software Services, который встроен в VS2010.

Допустим, у нас есть какой то проект, возьмем мой - FormulaToTruthTable. Для того, чтобы начать, зайдем в Tools->Dotfuscator Software Services. 

Вылезет окошко с лицензией. Тщательно читаем еврейским методом и принимаем лицензию. После нескольких минут раздумываний появится окошко дотфускатора:
Программа содержит:
  • Дерево навигации (слева от синего окошка)
  • Рабочее поле (синее окошко)
  • И Build Output (там появляется информация во время построения кода)
Теперь правой клавишей по Dotfuscator1->Add Assemblies. Добавляем все .exe .dll файлы из проекта. В моем случае у меня 2 файла (выберите Input Assemblies в дереве для просмотра):
Далее выберем нужные нам свойства:
  • Honor instrumentation attributes - выбрав галочку, дотфускатор трансформирует все функциональные аттрибуты (к-ые влияют на юзабильность, функциональность программы). Они описаны здесь : msdn
  • Honor obfuscation attributes - для того, чтобы производилось обфусцирование с помощью специальных аттрибутов.
  • Library mode - говорит дотфускатору, что входная сборка является библиотекой.
  • Strip obfuscation attributes - (Strip - снимать (engl)) - снимает аттрибуты запутывания, т.е. не будут видны аттрибты обфусцирования, таким образом над методами не будут красоваться: [Obfuscation(Feature = "trigger", ApplyToMembers = true, Exclude = false)]
Я выбрал вот так:
Вообще дальше лучше ничего не менять, а то напортачите :D, так что сразу нажимайте Build->Build Project. После некоторого времени, В блоге появится вот такая статистика:
Build Finished.
Build Statistics    Total  Renamed  Percent Renamed
Types:                 10        6           60,00%
Methods:               67       58           86,57%
Fields:                34       33           97,06%
Это означает, что построение завершено. В папке Папка вашего проекта\obj\x86\Debug\Dotfuscated появится exe и все ваши dll файлы. Все ваши файлы обфусцированы и при запуске .exe все должно работать.
Результат в папке:

воскресенье, 20 января 2013 г.

Квайн (Quine) - С++

Квайн - это программа, которая печатает свой собственный код.
пример квайна:

Увы, один из вариантов является читом:
ifstream openfile("./Quine.cpp", ios::in);
 string temp;
 while ( getline(openfile, temp) )
 {
  cout < < temp < < endl;
 }
 openfile.close();
Так,как программа может и не знать, где находится файл с программой.
#include
char*i="\\#include ",n='\n',q='"',*p=
"%s%cchar*i=%c%c%s%c,n='%cn',q='%c',*p=%c%c%s%c,*m=%c%c%s%c%c;%s%c",*m=
"int main(){return!printf(p,i+1,n,q,*i,i,q,*i,q,n,q,p,q,n,q,m,q,n,m,n);}"
;int main(){return!printf(p,i+1,n,q,*i,i,q,*i,q,n,q,p,q,n,q,m,q,n,m,n);}
Пример с википедии, (partial quine)
Задача: написать максимально короткий квайн :3

суббота, 19 января 2013 г.

Проблема линковщика с шаблонами в С++

Б-же, как меня з%?%"а эта проблема, убил на нее 2.5 часа, ни один преподаватель в вузе не сказал про эту проблему. Чувствую butthurt. Надеюсь, теперь вы не совершите такую же ошибку...

Предположим, что у нас есть класс (ОН находится в .h файле)

template < typename T>
class Single_Linked_List
{
private:
 Node *head;
 Node *tail;
 Node *current;
 unsigned size;
public:
        void Push_Front(const T& element);
 void Push_Back(const T& element);
 T Pop_Front();
 T Pop_Back();
////и дохрена методов внизу с конструктором деструктором
};

У нас есть .cpp файл, где находится описание всех методов итд:

#include "Single_Linked_List.h"
////
описание всех методов

Теперь мы попробуем потестить наш класс односвязного списка:

        Single_Linked_List<int> sll;
 sll.Push_Front(1);
 sll.Push_Front(1);

ОШИБКА -_-, в чем проблема ?
error LNK2019: unresolved external symbol "public: __thiscall Single_Linked_List::~Single_Linked_List(void)" (??1?$Single_Linked_List@H@@QAE@XZ) referenced in function _wmain 1>ListE.obj : error LNK2019: unresolved external symbol "public: void __thiscall Single_Linked_List::Push_Front(int const &)" (?Push_Front@?$Single_Linked_List@H@@QAEXABH@Z) referenced in function _wmain 1>ListE.obj : error LNK2019: unresolved external symbol "public: __thiscall Single_Linked_List::Single_Linked_List(void)" (??0?$Single_Linked_List@H@@QAE@XZ) referenced in function _wmain 1> : fatal error LNK1120: 3 unresolved externals
Видно, что компилятор ПРОСТО не видит .cpp файл. Теперь, подключим в main.cpp вместо .h файла, .cpp файл. О, ЧУДО, оно работает БЛ%^#АТЬ.
Давайте еще подробнее разберемся что к чему:

Заголовочный файл (header - .h) - файл, где находится описание, но не реализация.
.cpp - файл, где находится реализация. На самом деле они ничем не отличаются, разделение на .h и .cpp файлы - это просто формальность, для того, чтобы отличить, где реализация, а где описание. При компиляции, компилятор включает все include файлы в единую единицу трансляции и делают из него .obj файл. Потом из всех .obj файлов собирается программа. Если в .obj файле есть 1 реализация функции func, то она будет видна и в других .obj файлах, НО, если реализаций много, то будет ошибка линковщика.
В нашем случае реализацию шаблонной функции можно инстанцировать (генерирование типов и функций) множеством способов (func<int>, func<float>, func<double>...) поэтому будет ошибка.

Итак, эту проблему можно решить несколькими способами:

  1. Подключать в main.cpp не .h файла, а его реализацию .cpp файл.
  2. Всю реализацию хранить вместе с описанием (.h или .hpp файлы)
  3. Подключить в конце .h файла .cpp файл.
  4. Использовать export template (не поддерживается многими компиляторами, в том числе VS2010, поэтому я не смогу его продемонстрировать, он реализован только в Comeau)
  5. Просто написать объявление всех вариантов использования списка в cpp файле, например: template class Single_Linked_List<int>; потом с float и т. д.
  6. Использовать глобальную функцию, где опробовать все используемые методы в main'е, например (сделать только объявление глобальной функции в .h и все): 
void TemporaryFunction ()
{
 Single_Linked_List sll;
 sll.Push_Front(0);
 sll.Display();
}

После того, как в .h файле мы сделали такую функцию, теперь в main.cpp работают:
конструктор, деструктор, Push_Front, Display. С другими методами будет ошибка.

Из всех вариантов мне нравится третий, так как он не нарушает самой идеи раздельной компиляции и прост в понимании и реализации. Есть ли есть варианты, добавления и так далее, пишите в комментарии, всем, спасибо, за внимание :)

четверг, 17 января 2013 г.

Хеш-таблица (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 + incrementi +2 * incrementi +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;
    
    Вывод:

    среда, 16 января 2013 г.

    Перегрузка оператора [] C++


    Сегодня я рассмотрю пример перегрузки оператора для класса, где одним из полей является массив шаблонного типа, а сам класс-шаблонный.
    Вспомним какие перегруженные операторы должны быть обязательно членами класса, какие нет.
    Из таблицы видно, что оператор [] должен быть обязательно членом класса, то есть никаких friend'ов и так далее. Вспомним, что, если какой-то operator (оператор) является членом класса, то this является неявным аргументом.
    Например, если оператор+ член класса, то мы его записываем так:
    R T::operator +(S b);
    Если, friend, то:
    R operator +(S a, T b);

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

    Класс:
    
    template < typename Type>
    class A {
    private:
     Type *mas;
     unsigned _size;
    public:
     A (unsigned size){
      _size=size;
      mas=new Type[_size];
      for (unsigned i=0; i< _size; i++){
       mas[i]=i;
      }
     }
     Type& operator[](const unsigned index) const;
    };
    
    Теперь само определение перегруженного оператора:
    
    template < typename Type> Type& A< Type>::operator[](const unsigned index) const{
     try { //поискать ошибку
      if (index< 0||index>_size){
       throw("out of range"); //вбросить
      }
      return mas[index]; //возвратить элемент
     }
     catch(const char *msg){ //поймать ошибку
      puts(msg);
      exit(1);
     }
    }
    Код для проверки:
    
    unsigned x;
    cout< < "Enter size of mas: ";
    cin>>x;
    A< unsigned> a(x);
    cout< < endl;
    for (unsigned i=0; i< x; i++){
     cout< < "Element: "< < i< < "  "< < a[i]< < endl;
    }
    
    Демонстрация:

    Двусвязный список (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;
    
            }
    
        }
    

    суббота, 12 января 2013 г.

    Очередь (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;
                }
            }
        }
    

    Стек (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();
    
    
    

    воскресенье, 6 января 2013 г.

    Установка и настройка библиотеки boost (C++) на VS 2010


    Boost libraries - библиотеки которые расширяют еще больше функциональность C++. Boost библиотека в наше время незаменима, так как в ней есть библиотеки, которые очень часто применяются сейчас в программировании приложений и в ней есть библиотеки, которых нету в стандартном перечне библиотек С++.
    Прежде чем мы начнем, надо скачать библиотеки с сайта:
    Ссылка на архив: boost .zip - это версия 1.52, если вы хотите более новой версии, то на главной, где есть Current Releases и там будет показано, какая новая версия уже доступна.
    Вот еще другой способ скачать:

    1. Заходим на главную boost.org
    2. Справа будет красная кнопка Get Boost , нажимаем по ней
         3. Далее нажимаем по ссылке Download
          4. Далее нас перебросят на страницу где можно будет скачать архив.

    Итак, преположим, что все скачано. Распаковываем архив.
    Теперь открываем Пуск->Все Программы->Microsoft Visual Studio->Visual Studio Tools->Visual Studio Command Prompt (2010).
    ИЛИ Ищем в директории вот такой батник:
    vcvarsall.bat
    Появилась командная строка для VC2010. Пишем туда (Метка диска где вы распаковали архив, для меня это диск D, вот какую строку я написал "D:")
    Появилась метка тома D:\>
    пишем туда: "cd <папка где лежит папка boost_1_52_0>", в моем случае она лежит по пути D:\libraries, поэтому в моем случае я введу "cd libraries"
    Теперь введем имя папки cd boost_1_52_0 в вашем случае это будет папка где будет лежать bootstrap.bat
    Теперь запустим тот самый батник bootstrap.bat, начнется построение exe файла bjam.exe. BJam- система построения boost'а. Он предназначен для построения С++ проектов. Пишет, что идет построение (building) и нужно подождать некоторое время пока закончится процесс.
    Все! Процесс закончился. В папке boost_*_**_* появился bjam.exe. И в консоли выходит информация, что построение закончилось.
    Не запускайте пока что его. Можно с помощью командной строки построить все скачанные библиотеки boost с помощью bjam. Напишем вот такую магическую строчку:
    "bjam toolset=msvc link=static threading=multi release stage"
    Сначала релизим статическую библиотеку(20 min :) )
    Потом дебажим
    "bjam toolset=msvc link=static threading=multi debug stage"
    Все. теперь все скомпилировано. Теперь нам надо настроить VS2010, для того, чтобы он видел  где находятся эти файлы.
    Запустим VS2010, запустим любой C++ проект. Включим Property Manager. View->Property Manager, там выберем во вкладке Debug Microsoft.Cpp.<Platform>.user, правая клавиша->Properties
    Далее выберем там VC Directories. Include Directories->Edit. Появилось окно Include Directories
    Теперь инклюдим наши библиотеки. Ищем путь к распакованному архиву.
    Теперь также делаем и для Library Directories (только папку выбираем уже libs)
    Видно, что при подключении файла из папки, VS2010 не выводит ошибок.
    Все получилось, все компилится, всем спасибо за внимание! :)


    суббота, 5 января 2013 г.

    Пирамидальная сортировка (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); 
    }
    

    пятница, 4 января 2013 г.

    Реализация сортировки слиянием (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);
    }