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

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

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

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

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

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

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

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

Показаны сообщения с ярлыком C#. Показать все сообщения
Показаны сообщения с ярлыком C#. Показать все сообщения

суббота, 15 июня 2013 г.

Конвертер Hex String в Brush (Color) в Windows 8 (C#)

В приложениях Windows 8 для хранения цветов используется модель - RGBA (Red, Green, Blue, Alpha). Эта модель (цветовое пространство) известна всем со школы. 
В C# байты сначала идут - Alpha - Red - Green - Blue. Для каждого значения по 2 байта. 
Пример #FF000000 - Черный цвет, #FFFF0000 - Красный цвет.
Для тех, кто не знает, что такое Alpha - оно отвечает за прозрачность картинки, то есть, если у вас например RGBA = #FF000000 , здесь Alpha = 255, то есть картинка полностью непрозрачна, если Alpha = 0, то картинка полностью прозрачна.
Итак мне понадобилось сделать для моего приложения Windows Store простенький конвертер из Hex Строкового значения в объект типа SolidColorBrush. Преобразует строки типа - #FFFFFFFF. Проверок на длину строки нету.

public static class HexToColorConverter
    {
        public static SolidColorBrush GetColorFromHex(string hexColor)
        {
            hexColor = hexColor.Replace("#", ""); //удаляем решетку
            byte a = byte.Parse(hexColor.Substring(0, 2), System.Globalization.NumberStyles.HexNumber); //получаем alpha
            byte r = byte.Parse(hexColor.Substring(2, 2), System.Globalization.NumberStyles.HexNumber); //получаем красный
            byte g = byte.Parse(hexColor.Substring(4, 2), System.Globalization.NumberStyles.HexNumber); //получаем зеленый
            byte b = byte.Parse(hexColor.Substring(6, 2), System.Globalization.NumberStyles.HexNumber); //получаем синий
            return new SolidColorBrush(Color.FromArgb(a, r, g, b));
        }
    }

пятница, 14 июня 2013 г.

Хранение пароля и логина в приложении Windows 8 (C#)


Для хранения логинов и паролей в Windows 8 приложениях, Microsoft представила новый API, называемый PasswordVault (Хранилище паролей). При добавлении в это хранилище, происходит автоматическое шифрование данных, что очень удобно, если вы не хотите изобретать велосипед. Это только основы, для всех методов ссылка на MSDN
Для удобного взаимодействия с PasswordVault, я сделал 3 простых метода:
  • Метод добавления данных (SaveCredential)
  • Получения данных (GetCredential)
  • Удаления данных (RemoveCredential)
Особенности:

  • Помним, что для использования PasswordVault, требуется подключение библиотеки Windows.Security.Credentials
  • Для получения пароля или удаления данных, нужно знать логин
  • Если не найдены данные, то выкидывается исключение, к-ое надо обработать
  • Посмотреть добавленные данные можно в Control Panel -> User Accounts .. -> Credential Manager


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

private const string RESOURCE_NAME = "MyAppCredential"; //для добавления нужно название нашего ресурса
 
private void SaveCredential(string userName, string password)
{
    var vault = new PasswordVault(); //инициализируем хранилище
    var credential = new PasswordCredential(RESOURCE_NAME, userName, password);
    //добавляем данные, с помощью метода Add
    vault.Add(credential);
}
 
private void GetCredential()
{
    string userName; 
    string password;
 
    var vault = new PasswordVault();
    try
    {
        var credential = vault.FindAllByResource(RESOURCE_NAME).FirstOrDefault();
        if (credential != null)
        {
            // Получаем пароль и логин
            userName = credential.UserName;
            //ДЛЯ ПОЛУЧЕНИЯ ПАРОЛЯ НУЖНО ЗНАТЬ ЛОГИН
            password = vault.Retrieve(RESOURCE_NAME, userName).Password;
        }
    }
    catch (Exception)
    {
        // Если ничего не найдено, то обработать ошибку
    }
}
 
private void RemoveCredential(string userName)
{
    var vault = new PasswordVault();
    try
    {
        // Удаляем данные
        //ДЛЯ УДАЛЕНИЯ ДАННЫХ НУЖНО ЗНАТЬ ЛОГИН
vault.Remove(vault.Retrieve(RESOURCE_NAME, userName)); } catch (Exception) { // Если ничего не найдено, то обработать ошибку } }

воскресенье, 10 марта 2013 г.

Шаблон проектирования Команда (Command) + Реализация на C#

Существуют ситуации, когда у нас есть просто данные, над которыми нужно провести одну лишь единственную операцию, например, у нас есть кино на DVD диске и нам нужно всего лишь либо, запустить фильм, либо остановить, либо нажать на паузу и так далее. Также нам может понадобится такое действие, которое может отменить предыдущее (например операция undo в блокноте). Я могу написать функции (или методы), которые будут исполнять нашу команду и обрабатывать ее, но у нас будет очень много похожего кода, так как у нас не будет базового класса, который будет иметь поля схожие для всех команд. К тому же код будет очень не гибким. Фактически это КЛАСС, который инкапсулирует один единственный метод execute(). Это позволяет нам хранить команды в каких то контейнерах, обрабатывать их с помощью наших обработчиков.
(Пример стыбзен с википедии). Мы проектируем калькулятор со стандартными операциями сложения, деления, умножения, вычитания
Все строится сначала на классе Command:

abstract class Command
  {
    public abstract void Execute(); //метод выполнения команды
    public abstract void UnExecute(); //метод отмены
  }
Теперь делаем производные классы от команды. Причем этот класс должен хранить получателя(Calculator), класс, который принимает команды и обрабатывает их.

class CalculatorCommand : Command
  {
 char @operator; //оператор
 int operand;
 Calculator calculator; //ОБЪЕКТ ПОЛУЧАЮЩИЙ КОМАНДЫ (Receiver)
 
    // Constructor
 public CalculatorCommand(Calculator calculator,
    char @operator, int operand)
    {
      this.calculator = calculator;
      this.@operator = @operator;
      this.operand = operand;
    }
 
    public char Operator
    {
      set{ @operator = value; }
    }
 
    public int Operand
    {
      set{ operand = value; }
    }
 //здесь мы просто вызываем метод нашего получателя, на вход которого мы отправляем оператор и операнд
    public override void Execute() 
    {
      calculator.Operation(@operator, operand);
    }
 
    public override void UnExecute()
    {
      calculator.Operation(Undo(@operator), operand);
    }
 
    // Private helper function : приватные вспомогательные функции
    private char Undo(char @operator)
    {
      char undo;
      switch(@operator)
      {
        case '+': undo = '-'; break;
        case '-': undo = '+'; break;
        case '*': undo = '/'; break;
        case '/': undo = '*'; break;
        default : undo = ' '; break;
      }
      return undo;
    }
  }
Теперь нужен класс который будет получать команды и их обрабатывать.

// "Receiver" : получатель
 
  class Calculator
  {
    private int curr = 0;
 
    public void Operation(char @operator, int operand)
    {
      switch(@operator)
      {
        case '+': curr += operand; break;
        case '-': curr -= operand; break;
        case '*': curr *= operand; break;
        case '/': curr /= operand; break;
      }
      Console.WriteLine(
        "Current value = {0,3} (following {1} {2})",
        curr, @operator, operand);
    }
  }
Теперь нужен класс, который будет отдавать команды на обработку калькулятору..

class User
  {
    // Initializers
    private Calculator _calculator = new Calculator();
    private List _commands = new List();
 
    private int _current = 0;
 
    public void Redo(int levels)
    {
      Console.WriteLine("\n---- Redo {0} levels ", levels);
 
      // Делаем возврат операций
      for (int i = 0; i < levels; i++)
        if (_current < _commands.Count - 1)
          _commands[_current++].Execute();
    }
 
    public void Undo(int levels)
    {
      Console.WriteLine("\n---- Undo {0} levels ", levels);
 
      // Делаем отмену операций
      for (int i = 0; i < levels; i++)
        if (_current > 0)
          _commands[--_current].UnExecute();
    }
 
    public void Compute(char @operator, int operand)
    {
 
      // Создаем команду операции и выполняем её
      Command command = new CalculatorCommand(
        _calculator, @operator, operand);
      command.Execute();
 
      // Добавляем операцию к списку отмены
      _commands.Add(command);
      _current++;
    }
  }
Ну и пример работы с нашим калькулятором

class MainApp
  {
    static void Main()
    {
      // Создаем пользователя.
      User user = new User();
 
      // Пусть он что-нибудь сделает.
      user.Compute('+', 100);
      user.Compute('-', 50);
      user.Compute('*', 10);
      user.Compute('/', 2);
 
      // Отменяем 4 команды
      user.Undo(4);
 
      // Вернём 3 отменённые команды.
      user.Redo(3);
 
      // Ждем ввода пользователя и завершаемся.
      Console.Read();
    }
  }
Итак, теперь обобщим все, что мы здесь написали, вот схемка шаблона:
Ну, кто не силен в английском, могу объяснить, сначала наш вызывающий (по английски Invoker) (в нашем случае User), вызывает команду (причем команда передается в виде объекта) и посылает ее получателю (Calculator), где команда успешно обрабатывается калькулятором.
Благодаря такому шаблону, мы можем без труда можем добавить свои команды, которые с помощью метода execute() будут также выполнятся. Всего лишь надо унаследовать все от Command.

вторник, 26 февраля 2013 г.

Шаблон проектирования Абстрактная фабрика (Abstract factory) Реализация C#

Абстрактная фабрика - порождающий шаблон проектирования, используемый для создания ГРУППЫ объектов, реализующих одно поведение, то есть объекты одного типа, причем не специфируя их конкретные классы.

Абстрактная фабрика используется, когда:
  1. Система должна работать с группами объектов и объекты в этом семействе должны использоваться совместно.
  2. Система не должна зависеть от того, как создаются компоненты и взаимодействуют.
  3. Когда надо, чтобы при изменении класса конкретного продукта, не приходилось изменять класс клиента (класс, взаимодействующий  с созданными продуктами)
Действующие лица:
  • AbstractProduct — абстрактный продукт
    • определяет интерфейс для создания объектов, создаваемых методом CreateProduct, то есть он содержит виртуальные функции CreateProduct, где уже в ConcreteFactory переопределяются (override).
  • ConcreteProduct — конкретный продукт
    • реализует интерфейс Product (то есть у нас есть класс AbstractProduct, от которого у нас несколько производных классов, типа ConcreteProductA, либо ConcreteProductB и так далее)
  • AbstractProduct — абстрактный создатель
    • предназначен, для реализации интерфейса от производных классов типа ConcreteProduct
  • ConcreteFactory — конкретная фабрика
    • переопределяет фабричный метод таким образом, чтобы он создавал и возвращал объект класса ConcreteProduct.
  • Client - клиент
    • дает команды на получение продукта определенного семейства, к тому же в параметры передается фабрика, к-ая создает все объекты, фактически это наш интерфейс взаимодействия, с помощью которого, мы решаем какие объекты создать.

Диаграмма:
Шаблон:


//сам интерфейс абстрактной фабрики
//два абстрактных методов, к-ые переопределяются в наследниках
    abstract class AbstractFactory
    {
        public abstract AbstractProductA CreateProductA();
        public abstract AbstractProductB CreateProductB();
    }

    // "ConcreteFactory1" 
    class ConcreteFactory1 : AbstractFactory
    {
//переопредление методов интерфейсных для 1ой фабрики
        public override AbstractProductA CreateProductA()
        {
            return new ProductA1();
        }
        public override AbstractProductB CreateProductB()
        {
            return new ProductB1();
        }
    }

    // "ConcreteFactory2" 
    class ConcreteFactory2 : AbstractFactory
    {
//переопредление методов интерфейсных для 2ой фабрики
        public override AbstractProductA CreateProductA()
        {
            return new ProductA2();
        }
        public override AbstractProductB CreateProductB()
        {
            return new ProductB2();
        }
    }
//пошли уже наши интерфейсы продуктов
    // "AbstractProductA" 
    abstract class AbstractProductA
    {
    }

    // "AbstractProductB" 
    abstract class AbstractProductB
    {
//метод, который показывает, как продукт B взаимодействует с объектом А
        public abstract void Interact(AbstractProductA a);
    }
//реализация продуктов
    // "ProductA1" 
    class ProductA1 : AbstractProductA
    {
    }

    // "ProductB1" 
    class ProductB1 : AbstractProductB
    {
//определение
        public override void Interact(AbstractProductA a)
        {
            Console.WriteLine(this.GetType().Name + " interacts with " + a.GetType().Name);
        }
    }

    // "ProductA2" 
    class ProductA2 : AbstractProductA
    {
    }

    // "ProductB2" 
    class ProductB2 : AbstractProductB
    {
        public override void Interact(AbstractProductA a)
        {
            Console.WriteLine(this.GetType().Name + " interacts with " + a.GetType().Name);
        }
    }
//интерфейс взаимодействия, с помощью которого мы решаем какого типа создать объекты
    // "Client" - the interaction environment of the products 
    class Client
    {
        private AbstractProductA abstractProductA;
        private AbstractProductB abstractProductB;

        // Constructor, создается группа объектов, причем все в зависимости от типа фабрики
        public Client(AbstractFactory factory)
        {
            abstractProductB = factory.CreateProductB();
            abstractProductA = factory.CreateProductA();
        }
//запуск клиента
        public void Run()
        {
            abstractProductB.Interact(abstractProductA);
        }
    }

Main():

        static void Main(string[] args)
        {
            // Abstract factory #1 
            AbstractFactory factory1 = new ConcreteFactory1();
            Client c1 = new Client(factory1);
            c1.Run();

            // Abstract factory #2 
            AbstractFactory factory2 = new ConcreteFactory2();
            Client c2 = new Client(factory2);
            c2.Run();

            // Wait for user input 
            Console.Read();

        }
Вывод: Итак, все как в фабричном методе, только мы создаем ГРУППЫ объектов, и также у нас клиент занимается созданием объектов и анализ взаимодействия созданных объектов.

Шаблон проектирования Фабричный метод (Factory Method) Реализация C#

Фабричный метод используется для создания одного! объекта с определенным интерфейсом (типом).

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

Фабричный метод используется, когда:
  1. Заранее известно, когда создавать объект, но не известен его тип.
  2. Созданные фабричным методом объекты должны определятся уже в подклассе.
  3. Класс делегирует свои методы производному классу, после чего происходит определение, какой класс принимает какие методы.
Диаграмма:

Действующие лица:
  • Product — продукт
    • определяет интерфейс объектов, создаваемых абстрактным методом;
  • ConcreteProduct — конкретный продукт
    • реализует интерфейс Product (то есть у нас есть интерфейс IProduct, от которого у нас несколько производных классов, типа ConcreteProductA, либо ConcreteProductB и так далее)
  • Creator — создатель
    • предназначен, для реализации интерфейса от производных классов типа ConcreteCreator
    • содержит фабричный метод для создания объекта типа Product, который переопределяется в классах ConcreteCreatorA, ConcreteCreatorB;
  • ConcreteCreator — конкретный создатель
    • переопределяет фабричный метод таким образом, чтобы он создавал и возвращал объект класса ConcreteProduct.
На основе класса Factory создается один или несколько классов фабрик (причем эти фабрики имеют тип), и эти фабрики создают конкретные модели.

Шаблон:
//абстрактный класс создателя, который имеет абстрактный метод FactoryMethod, принимающий тип продукта
public abstract class Creator
{
    public abstract Product FactoryMethod(int type);
}
 
 
public class ConcreteCreator : Creator
{
    public override Product FactoryMethod(int type)
    {
        switch (type)
        {
            //возвращает объект A, если type==1
            case 1: return new ConcreteProductA();
            //возвращает объект B, если type==2 
            case 2: return new ConcreteProductB(); 
            default: throw new ArgumentException("Invalid type.", "type");
        }
    }
}

public abstract class Product { } //абстрактный класс продукт
 //конкретные продукты с разной реализацией
public class ConcreteProductA : Product { } 
 
public class ConcreteProductB : Product { }
 //
Потом в Main()

static void Main()
{       //создаем создателя
        Creator creator = new ConcreteCreator();
 for (int i = 1; i <= 2; i++)
 {
            //создаем сначала продукт с типом 1, потом с типом 2
     var product = creator.FactoryMethod(i);
     Console.WriteLine("Where id = {0}, Created {1} ", i, product.GetType());
 }
}
Здесь сначала создается сам конкретный создатель, который потом будет использоваться в создании продуктов, сначала ConcreteProductA, вывод на экран типа, потом ConcreteProductB, и также вывод его типа.

Итак, подводим итоги:

Самый главный недостаток, это необходимость создания объекта Creator для того, чтобы создать любой продукт с помощью метода FactoryMethod().

понедельник, 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 все должно работать.
Результат в папке:

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

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