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

信息 灵感 创新

I? =Information,Inspiration,Innovation

 
 
 

日志

 
 
关于我

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

网易考拉推荐

用C#学数据结构(5)  

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

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

链表(续)

约瑟夫环问题。

已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围,
从编号为k的人开始报数,数到m的那个人出列,
他的下一个人又从1开始报数,数到m的那个人又出列,
依此规律重复下去,直到圆桌周围的人全部出列,求出列序列

这个问题我在前面使用数组方法解决过,链接在这里:

http://379910987.blog.163.com/blog/static/335237972011621115036785/

此处使用链表来实现,简单易懂。

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

{

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

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

        J1.AddLast(i + 1);

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

    LinkedListNode<int> p=J1.First;

    int t = 1;

    while (J2.Count < n)//开始报数

    {

        if (t % m == 0)//需要出列

        {

            t = 1;

            //用一个链表保存,并出列

            int temp = p.Value;

            if ((temp + k) % n == 0)

                J2.AddLast(n);

            else

                J2.AddLast((temp+k)%n);

            if (p == J1.Last)//末尾就指向链表表头

                p = J1.First;

            else//否则移向下一个节点

                p = p.Next;

            //根据值删除原节点

            J1.Remove(temp);

        }

        else//不需要出列

        {

            t++;

            //向后移动节点

            if (p == J1.Last)//末尾就指向链表表头

                p = J1.First;

            else//否则移向下一个节点

                p = p.Next;

        }

    }

    return J2;

}

       上面的这段程序采用的是删除值的方法,好处是只需要一个类似指针的变量标记当前节点,但是缺点是删除采用的是Remove(value),该方法会删除值的第一个匹配项,所以对于有相同值的情况下就显得不太好,虽然许多时候我们可以使用GetHashCode等方式保证值的唯一性,但是总是让人有点不放心,最好的办法是直接删除节点,而不是转个弯通过值删除节点。下面是改进的方法,只是多引入了一个节点变量:

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

{

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

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

        J1.AddLast(i + 1);

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

    LinkedListNode<int> p=J1.First;

    LinkedListNode<int> outer;//出列者

    //移动到从k开始

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

    {

        if(p==J1.Last)

            p=J1.First;

        else

            p=p.Next;

    }

    while (J2.Count < n)

    {

        //先报数

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

        {

            if (p == J1.Last)

                p = J1.First;

            else

                p = p.Next;

        }

        outer = p;//此时刚好报到m

        J2.AddLast(outer.Value);               

        //移动到下一位

        if (p == J1.Last)

            p = J1.First;

        else

            p = p.Next;

        J1.Remove(outer);

        //将其移出链表,注意不能是J1.Remove(p);否则p不能指向链表中的节点了

    }

    return J2;

}

附截图:

用C学数据结构(5) - Castor - 趁年轻,多折腾~~
 

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

历史上的今天

评论

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

页脚

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