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

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› C++›C++教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

一个经常碰到的笔试题：一堆小朋友，共有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 }