我想知道人们如何不使用基类库实现在C中实现以下数据结构：

• 链表
• 哈希表
• 二进制搜索树
• 红黑树
• B树
• 二项式堆
• 斐波那契堆

以及人们能想到的任何其他基本数据结构！

我很好奇，因为我想提高我对这些数据结构的理解，很高兴看到Cversions而不是互联网上的典型C示例！

解决方案

回答

关于此主题有一系列MSDN文章。但是，我自己还没有真正阅读过该文本。我相信.NET的collections框架有一个损坏的接口，不能很好地扩展。

还有C5，我现在正在研究的一个图片库。

由于上述原因，我已经有一个项目为.NET实现我自己的集合库，但是在第一个基准测试表明即使是直接的，非线程安全的通用Vector实施都比较慢时，我已经停止了该项目。比本地的" List <T>"好。由于我一直在小心不要产生任何效率低下的IL代码，因此这意味着.NET根本不适合(至今)为内部数据结构编写按比例替换，并且.NET框架必须使用一些隐藏的替换-场景知识以优化内置集合类。

回答

对于我们提到的数据结构，我建议使用两种资源：
首先，有.NET Framework源代码(有关信息，请参见ScottGu的博客)。

另一个有用的资源是在Codeplex上找到的Wintellect的Power Collections。

希望这可以帮助！

回答

这是通用的二进制搜索树。我唯一没有做的就是实现IEnumerable <T>，因此我们可以使用枚举器遍历树。但是，这应该很简单。

特别感谢Scott Mitchel的BSTTree文章，我将其用作delete方法的参考。

节点类：

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--;
        }
    }
}

回答

也可以查看Rotor 2(http://research.microsoft.com/sscli/)或者使用反射器(http://www.red-gate.com/products/reflector/)，看看微软是如何做到的！！

回答

NGenerics

"一个类库，提供未在标准.NET框架中实现的通用数据结构和算法。"