Фундаментальные структуры данных в С#

Я хотел бы знать, как люди реализуют следующие структуры данных в С# без использования реализаций библиотеки базового класса: -

  • Связанный список
  • Таблица хешей
  • Двоичное дерево поиска
  • Красно-черное дерево
  • B-Tree
  • Биномиальная куча
  • Куча Фибоначчи

и любые другие фундаментальные структуры данных, о которых люди могут подумать!

Мне любопытно, что я хочу улучшить свое понимание этих структур данных, и было бы неплохо увидеть версии С#, а не типичные примеры C в Интернете!

Ответы

Ответ 1

В этой статье приведен ряд статей MSDN. Тем не менее, я действительно не читал текст сам. Я считаю, что структура коллекций .NET имеет сломанный интерфейс и не может быть расширена очень хорошо.

Там также C5, libray, который я изучаю прямо сейчас.

По причине, упомянутой выше, у меня был проект по реализации моей собственной библиотеки коллекций для .NET, но я остановил этот проект после того, как первый тест показал, что даже простой, не потокобезопасный общий Vector реализация медленнее, чем нативный List<T>. Поскольку я позаботился о том, чтобы не создавать какой-либо неэффективный IL-код, это означает, что .NET просто не подходит (пока) для записи на-парных замен для встроенных структур данных и что платформа .NET должна использовать некоторые из -scenes для оптимизации встроенных классов коллекции.

Ответ 2

Вот общее двоичное дерево поиска. Единственное, чего я не делал, это реализовать IEnumerable <T> поэтому вы можете пересечь дерево с помощью счетчика. Однако это должно быть достаточно прямым.

Особая благодарность Скотту Митчел за его статью BSTTree, я использовал ее как ссылку на метод удаления.

Node Класс:

    class BSTNode<T> where T : IComparable<T>
    {
        private BSTNode<T> _left = null;
        private BSTNode<T> _right = null;        
        private T _value = default(T);

        public T Value
        {
            get { return this._value; }
            set { this._value = value; }
        }

        public BSTNode<T> Left
        {
            get { return _left; }
            set { this._left = value; }
        }

        public BSTNode<T> Right
        {
            get { return _right; }
            set { this._right = value; }
        }        
    }

И фактический класс Tree:

    class BinarySearchTree<T> where T : IComparable<T>
    {
        private BSTNode<T> _root = null;
        private int _count = 0;

        public virtual void Clear()
        {
            _root = null;
            _count = 0;
        }

        public virtual int Count
        {
            get { return _count; }
        }

        public virtual void Add(T value)
        {
            BSTNode<T> newNode = new BSTNode<T>();
            int compareResult = 0;

            newNode.Value = value;

            if (_root == null)
            {
                this._count++;
                _root = newNode;
            }
            else
            {
                BSTNode<T> current = _root;
                BSTNode<T> parent = null;

                while (current != null)
                {
                    compareResult = current.Value.CompareTo(newNode.Value);

                    if (compareResult > 0)
                    {
                        parent = current;
                        current = current.Left;
                    }
                    else if (compareResult < 0)
                    {
                        parent = current;
                        current = current.Right;
                    }
                    else
                    {
                        // Node already exists
                        throw new ArgumentException("Duplicate nodes are not allowed.");
                    }
                }

                this._count++;

                compareResult = parent.Value.CompareTo(newNode.Value);
                if (compareResult > 0)
                {
                    parent.Left = newNode;
                }
                else
                {
                    parent.Right = newNode;
                }
            }
        }

        public virtual BSTNode<T> FindByValue(T value)
        {
            BSTNode<T> current = this._root;

            if (current == null)
                return null;   // Tree is empty.
            else
            {
                while (current != null)
                {
                    int result = current.Value.CompareTo(value);
                    if (result == 0)
                    {
                        // Found the corrent Node.
                        return current;
                    }
                    else if (result > 0)
                    {
                        current = current.Left;
                    }
                    else
                    {
                        current = current.Right;
                    }
                }

                return null;
            }
        }

        public virtual void Delete(T value)
        {

            BSTNode<T> current = this._root;
            BSTNode<T> parent = null;

            int result = current.Value.CompareTo(value);

            while (result != 0 && current != null)
            {
                if (result > 0)
                {
                    parent = current;
                    current = current.Left;
                }
                else if (result < 0)
                {
                    parent = current;
                    current = current.Right;
                }

                result = current.Value.CompareTo(value);
            }

            if (current == null)
                throw new ArgumentException("Cannot find item to delete.");



            if (current.Right == null)
            {
                if (parent == null)
                    this._root = current.Left;
                else
                {
                    result = parent.Value.CompareTo(current.Value);
                    if (result > 0)
                    {
                        parent.Left = current.Left;
                    }
                    else if (result < 0)
                    {
                        parent.Right = current.Left;
                    }
                }
            }
            else if (current.Right.Left == null)
            {
                if (parent == null)
                    this._root = current.Right;
                else
                {
                    result = parent.Value.CompareTo(current.Value);
                    if (result > 0)
                    {
                        parent.Left = current.Right;
                    }
                    else if (result < 0)
                    {
                        parent.Right = current.Right;
                    }
                }
            }
            else
            {

                BSTNode<T> furthestLeft = current.Right.Left;
                BSTNode<T> furthestLeftParent = current.Right;

                while (furthestLeft.Left != null)
                {
                    furthestLeftParent = furthestLeft;
                    furthestLeft = furthestLeft.Left;
                }

                furthestLeftParent.Left = furthestLeft.Right;

                furthestLeft.Left = current.Left;
                furthestLeft.Right = current.Right;

                if (parent != null)
                {
                    result = parent.Value.CompareTo(current.Value);
                    if (result > 0)
                    {
                        parent.Left = furthestLeft;
                    }
                    else if (result < 0)
                    {
                        parent.Right = furthestLeft;
                    }
                }
                else
                {
                    this._root = furthestLeft;
                }
            }

            this._count--;
        }
    }
}

Ответ 3

Я бы рекомендовал два ресурса для структур данных, которые вы упомянули: Во-первых, есть исходный код .NET Framework (информацию можно найти в блоге ScottGu здесь).

Другим полезным ресурсом являются коллекции Wintellect Power Collections, найденные в Codeplex здесь.

Надеюсь, это поможет!

Ответ 4

NGenerics

"Библиотека классов, предоставляющая общие структуры данных и алгоритмы, не реализованные в стандартной платформе .NET.