编程小技巧

    返回首页    发表留言
本文作者:李德强
          技巧二十五:小朋友手拉手
 
 

        今天跟大家分享的小技巧是关于循环链表的,我们先来看这样一个问题,有N个小朋友手拉手围成一个圈,第一个小朋友做为开始者,随机报一个数n,然后从这个小朋友右手边从1开始依次报数,报到n这个数的小朋友出局,他出局后,他左右两边的两个小朋友将手拉在一起,组成一个新的圈子,他右侧的这个小朋友做为开始者重新随机报一个数,以此重复下去,直到圈子中只剩下一个小朋友为止。我们需要使用程序实现这一个过程。在实现程序之前,我们先来用图形演示一下这个过程:

                                  

 

                                  

 

                                  

 

                                  

 

                                  

 

        下面我们就使用循环数组来实现这一过程,我们首先要定义循环链表的数据结构:

 

typedef struct s_Node
{
	int id;
	struct s_Node *next;
} s_Node;

typedef struct s_Link
{
	s_Node *header;
} s_Link;

        其中s_Link为循环链表数据结构,它很简单,只有一个头节点,用于每次开始报数的起始位置。s_Node为链表的节点数据结构,id表示小朋友的编号,next用于存放下一个小朋友节点的地址。我们还需要实现一个创建链表的功能函数,它可以根据需要创建N个手拉手小朋友:

 

void link_create(s_Link *link, int n)
{
	s_Node **p = &link->header;
	for (int i = 0; i < n; i++)
	{
		s_Node *node = malloc(sizeof(s_Node));
		node->id = i;
		*p = node;
		p = &(*p)->next;
	}
	*p = link->header;
}

        与创建链表相对应,我们还需要实现小朋友离开圈子的功能函数,这个函数也是我们的这个问题的核心功能,在头节点的小朋友报一个随机数n,于是从他开始依次从1报数,报到n的小朋友出局。也就是说是从头节点开始依次向下到n个节点出局,所以我们的出局函数如下:

 

void link_remove(s_Link *link, int num)
{
	s_Node **p = &link->header;
	for (int i = 0; i < num; i++)
	{
		p = &(*p)->next;
	}
	s_Node *del = *p;
	*p = (*p)->next;
	link->header = *p;
	free(del);
}

        最后来看一下在N等于10,也就是有10个小朋友时程序运行的结果:

 

		0 1 2 3 4 5 6 7 8 9 
rnd =  4,	5 6 7 8 9 0 1 2 3 
rnd =  6,	2 3 5 6 7 8 9 0 
rnd =  9,	5 6 7 8 9 0 2 
rnd = 10,	9 0 2 5 6 7 
rnd = 15,	6 7 9 0 2 
rnd = 12,	0 2 6 7 
rnd =  9,	6 7 0 
rnd = 10,	0 6 
rnd =  4,	6 

 

        本例程序下载(请将下载后的文件修改为example.tar.gz解压即可)

 

        今天的小技巧你学会了吗?

 

 

    返回首页    返回顶部
  看不清?点击刷新

 

  Copyright © 2015-2018 问渠网 辽ICP备15013245号