c# 链表结构（2）-循环链表

骑猪看日落 2021-12-11 01:39 269阅读 0赞

一个经常碰到的笔试题：一堆小朋友，共有N个，围成一个圈，每个小朋友递增地编号，1，2，3，4，......现在，从第一个小朋友开始计数，每数到3的小朋友站出来离开，然后从下一个小朋友开始计数。直到所有的小朋友离开，求小朋友离开的顺序编号。

例如：1 2 3 4

【第一次3离开】剩下 1 2 4

【第二次2离开】剩下 1 4

【第三次4离开】剩下 1

........

下面以苹果代替小朋友，数到3的苹果被吃掉，输出被吃的苹果的编号。

先创建一个苹果结点类Apple.cs

1 using System;
     2 using System.Collections.Generic;
     3 using System.Text;
     4 
     5 namespace CsharpLinkedList
     6 {
        
     7     //一个苹果结点
     8     public class AppleNode
     9     {
        
    10         //当前苹果的信息，用Int32，为空时不出错
    11         public Int32 Apple { get; set; }
    12 
    13         //下一个苹果
    14         public AppleNode Next { get; set; }
    15 
    16         //无参数构造函数，初始化
    17         public AppleNode()
    18         {
        
    19             //从1开始计数,0表示空
    20             this.Apple = 0;
    21             //下一结点为空
    22             this.Next = null;
    23         }
    24 
    25         //传参数构造函数
    26         public AppleNode(Int32 number)
    27         {
        
    28             this.Apple = number;
    29             this.Next = null;
    30 
    31         }
    32 
    33         //传参数构造函数
    34         public AppleNode(AppleNode node)
    35         {
        
    36             this.Apple = node.Apple;
    37             this.Next = node.Next;
    38         }
    39     }
    40 }

接着，创建一个操作方法接口IEat.cs（觉得这里有点画蛇添足了~）

1 using System;
     2 using System.Collections.Generic;
     3 using System.Linq;
     4 using System.Text;
     5 
     6 namespace CsharpLinkedList
     7 {
        
     8     interface IEat
     9     {
        
    10         /// <summary>
    11 /// 开始启动
    12 /// </summary>
    13         void Begin(int num);
    14 
    15         void Work();
    16 
    17     }
    18 }

然后，创建一个操作类，EatApple.cs，并实现IEat的接口。

1 using System;
      2 using System.Collections.Generic;
      3 using System.Text;
      4 
      5 namespace CsharpLinkedList
      6 {
        
      7     public class EatApple:IEat
      8     {
        
      9         //一条链表
     10         AppleNode allApple=new AppleNode();
     11 
     12         //返回链表
     13         public AppleNode AllApple
     14         {
        
     15             get
     16             {
        
     17                 return this.allApple;
     18             }
     19         }
     20 
     21         //链表流指针
     22         AppleNode point = new AppleNode();
     23         
     24 
     25         /// <summary>
     26 /// 初始化链表
     27 /// </summary>
     28 /// <param name="num">苹果个数</param>
     29         public void Begin(int num)
     30         {
        
     31             for (int i = 1; i <=num; i++)
     32             {
        
     33                 //第一个结点
     34                 if (allApple == null||allApple.Apple==0)
     35                 {
        
     36                     allApple.Apple = 1;
     37                     allApple.Next = null;
     38                     point = allApple;
     39                     continue;
     40                 }
     41 
     42                 //实例化一个结点
     43                 AppleNode appleNode = new AppleNode();
     44                 appleNode.Apple = i;
     45                 appleNode.Next = null;
     46 
     47                 //增加一个结点到链表上
     48                 point.Next = appleNode;
     49                 point = appleNode;
     50             }
     51 
     52             //尾结点的后结点，指向第一个结点
     53             point.Next = allApple;
     54                         
     55         }
     56 
     57         /// <summary>
     58 /// 进行计数，凡是数到3的为符合条件
     59 /// </summary>
     60         public void Work()
     61         {
        
     62             if (allApple.Apple == 0)
     63                 return;
     64             
     65             //temp指向第一个结点
     66             AppleNode temp = new AppleNode(allApple);
     67             int count=1;
     68 
     69             while (temp.Apple!=0)
     70             {
        
     71                 if (count == 3)
     72                 {
        
     73                     //输出符合的
     74                     Console.WriteLine(temp.Apple.ToString());
     75                     //这个符合，标记为删除
     76                     temp.Apple = 0;
     77                     //从下一个开始重新计数
     78                     count = 0;
     79                 }
     80 
     81 
     82                 temp = temp.Next;
     83 
     84                 //找到下一个满足条件的结点
     85                 while(temp.Apple==0)
     86                 {
        
     87                     temp = temp.Next;
     88                 }
     89 
     90                 count++;
     91                
     92             }
     93             temp = null;
     94 
     95             allApple = null;
     96 
     97         }
     98 
     99         /// <summary>
    100 /// 测试初始化，遍历链表
    101 /// </summary>
    102 /// <param name="link">输入一个链表</param>
    103         public void TestBegin(AppleNode link)
    104         {
        
    105             if (link != null&&link.Apple!=0)
    106             {
        
    107                 AppleNode temp = new AppleNode();
    108                 temp = link;
    109                 while (temp.Apple != 0 && temp != null)
    110                 {
        
    111                     Console.WriteLine(temp.Apple.ToString());
    112                     if (temp.Next != null)
    113                         temp = temp.Next;
    114                     else
    115                         break;
    116                 }
    117             }
    118         }
    119 
    120     }
    121 }

最后，主函数类Program.cs

1 using System;
     2 using System.Collections.Generic;
     3 using System.Linq;
     4 using System.Text;
     5 
     6 namespace CsharpLinkedList
     7 {
        
     8     class Program
     9     {
        
    10         static void Main(string[] args)
    11         {
        
    12             EatApple eatApple = new EatApple();
    13             eatApple.Begin(7);
    14            // eatApple.TestBegin(eatApple.AllApple);循环链表，死循环
    15             eatApple.Work();
    16 
    17             //下面的执行不了
    18             object t=Console.ReadLine();
    19             Console.WriteLine(t.ToString());
    20         }
    21     }
    22 }

运行结果如下（7个苹果时）：

![2012021015192523.png][]

有个很奇怪的问题，当输出完毕时，控制窗口就停止响应了。这是什么原因呢？还请各位同学指点。不胜感激哦~

感谢 [none2180][] 的指点！在下一篇关于c\#链表结构的随笔中，将修正此Bug。

转载于:https://www.cnblogs.com/oneivan/archive/2012/02/10/2345459.html

[2012021015192523.png]: /images/20211210/f981bda32b1b4ef69a8cb4461d205756.png
[none2180]: http://www.cnblogs.com/onepiece_wang/