荔园在线

荔园之美,在春之萌芽,在夏之绽放,在秋之收获,在冬之沉淀

[回到开始] [上一篇][下一篇]


发信人: Jobs (温少), 信区: DotNET
标  题: 数据结构双向链表的C#实现
发信站: 荔园晨风BBS站 (Thu Jan  2 13:16:44 2003), 站内信件

/**
 *
 *

    @author     <a href="mailto:szuJobs@hotmail.com>wen shaojin</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.ToString()
 : "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站 bbs.szu.edu.cn·[FROM: 218.17.75.188]


[回到开始] [上一篇][下一篇]

荔园在线首页 友情链接:深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店