发信人: Jobs (温少), 信区: DotNET        
标  题: 数据结构双向链表的C#实现
发信站: BBS 水木清华站 (Thu Jan  2 13:14:38 2003)


/**
*  
*  

    @author     <a href="wen">mailto:szuJobs@hotmail.com">wenshaojin</a>
    @created    January 2, 2003
    @version    1

*
**/
using System;
using System.Collections;
using System.IO;

namespace Matrix.Common.Collections
{
    /// <summary>
    /// 双向链表
    /// </summary>
    public class DoublyLinkedList : IEnumerable
    {
        private DoublyLinkedListNode _first;
        private int _count;

        public DoublyLinkedList()
        {
            _count = 0;
            _first = null;
        }

        public int Count
        {
            get
            {
                return _count;
            }
        }

        public object this[int pos]
        {
            get
            {
                if(pos < 0)
                {
                    throw new ArgumentOutOfRangeException("pos");
                }

                DoublyLinkedListNode current = this._first;

                int index = 0;

                while(index < pos && current != null)
                {
                    index ++;
                    current = current.Right;
                }

                if(current != null)
                {
                    return current.Data;
                }
                else
                {
                    throw new ArgumentOutOfRangeException("pos");
                }
            }
        }

        private DoublyLinkedListNode FindNode(int pos)
        {
            //p will eventually point to k'th node
            DoublyLinkedListNode p = this._first;
            for(int i=0; i<pos && p != null; i++) // move p to pos'th
            {
                p = p.Right;
            }

            if(pos > 0 && p == null) // no pos'th
            {
                throw new ArgumentOutOfRangeException("pos");
            }

            return p;
        }

        private void InsertBefore(DoublyLinkedListNode p, object data)
        {
            DoublyLinkedListNode y = new DoublyLinkedListNode();
            y.Data = data;

            y.Left = p.Left;
            y.Right = p;
            p.Left.Right = y;
            p.Left = y;
        }

        private void Delete(DoublyLinkedListNode p)
        {
            if(p == this._first)
            {
                this._first = this._first.Right;
                this._first.Left = null;
            }
            else if(p.Right == null)
            {
                p.Left.Right = null;
            }
            else
            {
                p.Left.Right = p.Right;
                p.Right.Left = p.Left;
            }
        }

        public void Delete(int pos)
        {
            if(pos < 0)
            {
                throw new ArgumentOutOfRangeException("pos");
            }

            DoublyLinkedListNode p = FindNode(pos);

            if(p == null)
            {
                throw new ArgumentOutOfRangeException("pos");
            }

            this.Delete(p);

            _count --;
        }

        public void Insert(int pos, object data)
        {
            if(pos < 0)
            {
                throw new ArgumentOutOfRangeException("pos");
            }

            if(pos == 0)
            {
                DoublyLinkedListNode y = new DoublyLinkedListNode();
                y.Data = data;

                if(this._first == null)
                {
                    this._first = y;
                }
                else
                {
                    y.Right = this._first;
                    this._first.Left = y;
                    this._first = y;
                }
            }
            else
            {
                DoublyLinkedListNode p = FindNode(pos);

                InsertBefore(p, data);
            }

            _count ++;
        }

        public void MoveToFirst(int pos)
        {
            if(pos < 0 || this._first == null)
            {
                throw new ArgumentOutOfRangeException("pos"); //// no pos'th
            }

            if(pos == 0)
            {
                return;
            }

            DoublyLinkedListNode q = FindNode(pos);

            if(q == null)
            {
                throw new ArgumentOutOfRangeException("pos");
            }

            this.Delete(q);

            this._first.Left = q;
            q.Right = this._first;
            q.Left = null;
            this._first = q;
        }

        public void Swap(int posA, int posB)
        {
            if(posA <0 || posA >= this._count)
            {
                throw new ArgumentOutOfRangeException("posA");
            }

            if(posB <0 || posB >= this._count)
            {
                throw new ArgumentOutOfRangeException("posB");
            }

            DoublyLinkedListNode p = FindNode(posA);
            DoublyLinkedListNode q = FindNode(posB);

            this.Swap(p, q);
        }

        private void Swap(DoublyLinkedListNode p , DoublyLinkedListNode q)
        {
            if(p == q)
            {
                return;
            }

            DoublyLinkedListNode pLeft = p.Left;
            DoublyLinkedListNode pRight = p.Right;
            DoublyLinkedListNode qLeft = q.Left;
            DoublyLinkedListNode qRight = q.Right;

            if(qRight == p)
            {
                p.Left = qLeft;
                if(qLeft != null)
                {
                    qLeft.Right = p;
                }

                if(pRight != null)
                {
                    pRight.Left = q;
                }
                q.Right = pRight;

                q.Left = p;
                p.Right = q;

            }
            else if(pRight == q)
            {
                q.Left = pLeft;
                if(pLeft != null)
                {
                    pLeft.Right = q;
                }

                if(qRight != null)
                {
                    qRight.Left = p;
                }
                p.Right = qRight;

                p.Left = q;
                q.Right = p;
            }
            else
            {
                q.Left = pLeft;
                if(pLeft != null)
                {
                    pLeft.Right = q;
                }

                q.Right = pRight;
                if(pRight != null)
                {
                    pRight.Left = q;
                }

                Output(q);

                p.Left = qLeft;
                if(qLeft != null)
                {
                    qLeft.Right = p;
                }

                p.Right = qRight;
                if(qRight != null)
                {
                    qRight.Left = p;
                }

                Output(p);
            }

            if(this._first == p)
            {
                this._first = q;
            }
            else if(this._first == q)
            {
                this._first = p;
            }

            Console.WriteLine("_first");
            Output(this._first);
            Console.WriteLine("---------------------");
        }

        public void Add(object data)
        {
            DoublyLinkedListNode y = new DoublyLinkedListNode();
            y.Data = data;

            if(this._first == null)
            {
                this._first = y;
                _count ++;
                return;
            }

            DoublyLinkedListNode current = this._first;

            while(current.Right != null)
            {
                current = current.Right;
            }

            current.Right = y;
            y.Left = current;

            _count ++;
        }

        public void Clear()
        {
            this._first = null;
            _count = 0;
        }

        private void Output(DoublyLinkedListNode node)
        {
            if(node == null)
            {
                return;
            }

            DoublyLinkedListNode left = node.Left;
            DoublyLinkedListNode right = node.Right;

            Console.WriteLine("left : " + (left != null ? left.Data.ToString()
: "null"));
            Console.WriteLine("node : " + node.Data);
            Console.WriteLine("right : " + (right != null ? right.Data.ToStrin
g() : "null"));
            Console.WriteLine();
        }

        public void Output()
        {
            int count = this.Count;
            for(int i=0; i<count; i++)
            {
                DoublyLinkedListNode node = this.FindNode(i);

                this.Output(node);
            }
        }

        public IEnumerator GetEnumerator()
        {
            return new DoublyLinkedListEnumerator(this);
        }

        private class DoublyLinkedListNode
        {
            public object Data;
            public DoublyLinkedListNode Left;
            public DoublyLinkedListNode Right;
        }

        private class DoublyLinkedListEnumerator : IEnumerator
        {
            private DoublyLinkedList _list;
            private DoublyLinkedListNode _location;

            public DoublyLinkedListEnumerator(DoublyLinkedList list)
            {
                this._list = list;
            }

            public bool MoveNext()
            {
                if(this._location == null)
                {
                    this._location = _list._first;
                }
                else
                {
                    this._location = this._location.Right;
                }

                return this._location != null;
            }

            public void Reset()
            {
                this._location = _list._first;
            }

            public object Current
            {
                get
                {
                    return this._location.Data;
                }
            }
        }
    }
}

--

※ 来源:·BBS 水木清华站 smth.org·[FROM: 218.17.75.188]
上一篇
返回上一页
回到目录
回到页首
下一篇