注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

信息 灵感 创新

I? =Information,Inspiration,Innovation

 
 
 

日志

 
 
关于我

we are 5. Mathematics, Computation, Programming, Engineering, and Making fun of life.

网易考拉推荐

用C#学数据结构(6)  

2011-07-31 20:47:24|  分类: C# & .NET |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

声明:本人非计算机专业人士,没有过多的时间、经历和能力深入研究数据结构的实现,所以本系列文章不处理数据结构的实现,主要是练习各种数据结构的使用。欢迎大家交流讨论。
链表(续)

用C#实现循环链表

可以将循环链表看作是双链表的一种特例,即链表尾部节点的Next属性不是null,而是指向了头结点,可以利用现有的LinkedListNode类作为循环链表的节点。

下面将提供一个完整的循环链表类CircleLinkedList,该类和LinkedList类似,都是构建于LilnkedListNode之上,而且内部使用一个LinkedList维护循环链表,该循环链表具有泛型特性,可用于多种场合。

//本类由Castor原创,转载注明出处

public class CircleLinkedList<T>//需要SystemSystem.Collections.Generic命名空间的支持

{

    //内部实现链表

    private LinkedList<T> ll;

    //当前节点

    private LinkedListNode<T> current;

    //头结点,注意头结点不参与数据存储

    private LinkedListNode<T> head;

    /// <summary>

    /// 循环链表构造函数

    /// </summary>

    public CircleLinkedList()

    {

        ll = new LinkedList<T>();

        T value = default(T);

        head = new LinkedListNode<T>(value);

        ll.AddFirst(head);

        current = head;

    }

    /// <summary>

    /// 遍历器

    /// </summary>

    /// <returns>返回除头结点外的所有节点,提供foreach支持</returns>

    public IEnumerator<LinkedListNode<T>> GetEnumerator()

    {

        LinkedListNode<T> p = ll.First;

        p = p.Next;

        while (p != null)

        {

            yield return p;

            p = p.Next;

        }

    }

    #region 属性

    /// <summary>

    /// 只读属性,返回循环链表中的节点数目,不包括Head结点

    /// </summary>

    public int Count

    {

        //不包括Head节点

        get { return ll.Count - 1; }

    }

    /// <summary>

    /// 只读属性,当前节点

    /// </summary>

    public LinkedListNode<T> Current

    {

        get { return current; }

    }

    /// <summary>

    /// 只读属性,头结点

    /// </summary>

    public LinkedListNode<T> Head

    {

        get { return head; }

    }

    /// <summary>

    /// 只读属性,返回循环链表第一个节点

    /// </summary>

    public LinkedListNode<T> First

    {

        get

        {

            if (ll.First.Next == null)

                throw new IndexOutOfRangeException("循环链表为空,无法获取第一个节点");

            else

                return ll.First.Next;

        }

    }

    /// <summary>

    /// 只读属性,返回循环链表最后一个节点

    /// </summary>

    public LinkedListNode<T> Last

    {

        get

        {

            if (ll.First.Next == null)

                throw new IndexOutOfRangeException("循环链表为空,无法获取最后一个节点");

            else

                return ll.Last;

        }

    }

    #endregion

 

    #region 添加节点方法

    /// <summary>

    /// 将一个节点或值插入到循环链表的最前面

    /// 注意仍在Head节点后面

    /// </summary>

    /// <param name="node">待插入节点</param>

    public void AddFirst(LinkedListNode<T> node)

    {

        ll.AddAfter(head, node.Value);

    }

    /// <summary>

    /// 将一个节点或值插入到循环链表的最前面

    /// 注意仍在Head节点后面

    /// </summary>

    /// <param name="value">待插入值</param>

    public void AddFirst(T value)

    {

        ll.AddAfter(head, value);

    }

    /// <summary>

    /// 将一个节点或值插到循环链表最后面

    /// </summary>

    /// <param name="node">待插入节点</param>

    public void AddLast(LinkedListNode<T> node)

    {

        ll.AddLast(node);

    }

    /// <summary>

    /// 将一个节点或值插到循环链表最后面

    /// </summary>

    /// <param name="value">待插入值</param>

    public void AddLast(T value)

    {

        ll.AddLast(value);

    }

    /// <summary>

    /// 将一个值或者节点插入到指定节点后面

    /// </summary>

    /// <param name="node">节点</param>

    /// <param name="newNode">待插入节点</param>

    public void AddAfter(LinkedListNode<T> node, LinkedListNode<T> newNode)

    {

        ll.AddAfter(node, newNode);

    }

    /// <summary>

    /// 将一个值或者节点插入到指定节点后面

    /// </summary>

    /// <param name="node">节点</param>

    /// <param name="value">待插入值</param>

    public void AddAfter(LinkedListNode<T> node, T value)

    {

        ll.AddAfter(node, value);

    }

    /// <summary>

    /// 将一个节点或者值插入到指定节点前面

    /// 注意该节点不能是头结点Head,但可以是First

    /// </summary>

    /// <param name="node">节点</param>

    /// <param name="newNode">新节点</param>

    public void AddBefore(LinkedListNode<T> node, LinkedListNode<T> newNode)

    {

        if (node == head)

            throw (new IndexOutOfRangeException("前插参数错误,你不可能把一个节点或值插入到Head节点前面"));

        ll.AddBefore(node, newNode);

    }

    /// <summary>

    /// 将一个节点或者值插入到指定节点前面

    /// 注意该节点不能是头结点Head,但可以是First

    /// </summary>

    /// <param name="node">节点</param>

    /// <param name="value"></param>

    public void AddBefore(LinkedListNode<T> node, T value)

    {

        if (node == head)

            throw (new IndexOutOfRangeException("前插参数错误,你不可能把一个节点或值插入到Head节点前面"));

        ll.AddBefore(node, value);

    }

    #endregion

 

    #region 移动节点方法

    /// <summary>

    /// 将当前节点向后循环移动一位,跳过head节点

    /// </summary>

    public void MoveNext()

    {

        if (ll.First.Next == null)

            throw new IndexOutOfRangeException("循环链表为空,无法移动当前节点");

        if (current == ll.Last)

            current = ll.First.Next;

        else

            current = current.Next;

    }

    /// <summary>

    /// 将当前节点向前移动一位,跳过head节点

    /// </summary>

    public void MovePrevious()

    {

        if (ll.First.Next == null)

            throw new IndexOutOfRangeException("循环链表为空,无法移动当前节点");

        if (current.Previous == ll.First)//要跳过head节点

            current = ll.Last;

        else

            current = current.Previous;

    }

    /// <summary>

    /// 将当前节点移动到最后一个节点,如果为空,则直接为head节点

    /// </summary>

    public void MoveLast()

    {

        current = ll.Last;

    }

    /// <summary>

    /// 将当前节点移动到第一节点

    /// </summary>

    public void MoveFirst()

    {

        if (ll.First.Next == null)

            throw new IndexOutOfRangeException("循环链表为空,无法移动到第一个节点");

        current = ll.First.Next;

    }

    /// <summary>

    /// 将当前节点移动到头结点

    /// </summary>

    public void MoveHead()

    {

        current = ll.First;

    }

    #endregion

 

    #region 移除节点方法

    /// <summary>

    /// 移出第一节点,Current变为下一个节点,但是如果第一节点也是最后一个节点,Current将变为head节点

    /// </summary>

    public void RemoveFirst()

    {

        if (ll.First.Next == null)//head后已经没有节点了

            throw new IndexOutOfRangeException("循环链表为空,无法移出第一个节点");

        else//head后还有节点

        {

            if (ll.Count == 2)//第一节点也是最后一个节点

            {

                ll.RemoveLast();

                current = head;

            }

            else

            {

                LinkedListNode<T> temp = current;

                current = current.Next;

                ll.Remove(temp);

            }

        }

    }

    /// <summary>

    /// 移出末尾节点,如果当前节点恰好为末尾节点,当前节点将变为第一节点

    /// </summary>

    public void RemoveLast()

    {

        if (ll.First.Next == null)//head后已经没有节点了

            throw new IndexOutOfRangeException("循环链表为空,无法移出最后一个节点");

        else

        {

            current = ll.First.Next;

            ll.RemoveLast();

        }

    }

    /// <summary>

    /// 移出当前节点,循环链表中当前节点顺移到下一位

    /// 如果Current已经是head节点,将不做任何操作

    /// 如果当前节点恰好为尾节点,当前节点将变为第一节点

    /// 如果当前节点是循环链表中唯一可用节点(既是第一节点又是尾节点),则移出后Current变为head节点

    /// </summary>

    public void RemoveCurrent()

    {

        if (current == head) return;//为首节点不移出

        if (ll.First.Next == null)

            throw new IndexOutOfRangeException("循环链表为空,无法移出当前节点");

        LinkedListNode<T> temp = current;

        //移动当前节点

        if (current.Next == null)//为尾节点

        {

            if (current == ll.First.Next)//又恰好为第一节点

                current = head;

            else//一般尾节点

                current = ll.First.Next;

        }

        else

            current = current.Next;

        ll.Remove(temp);

    }

    #endregion

}

用该类解决约瑟夫环问题将会更简单,因为其本身就有维护循环链表的功能:

public static LinkedList<int> Josephus(int n, int m, int k)

{

    LinkedList<int> J = new LinkedList<int>();

    CircleLinkedList<int> ring = new CircleLinkedList<int>();

    for (int i = 1; i <= n; i++)

        ring.AddLast(i);

    ring.MoveFirst();

    for (int i = 1; i < k; i++)

        ring.MoveNext();

    while (ring.Count > 0)

    {

        for (int i = 1; i < m; i++)

            ring.MoveNext();

        J.AddLast(ring.Current.Value);

        ring.RemoveCurrent();

    }

    return J;

}

该方法将会返回一个链表,链表中的值就是出列顺序

  评论这张
 
阅读(892)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2016