数据结构：循环链表求解约瑟夫环有关问题

数据结构：循环链表求解约瑟夫环问题

打开博客，竟然有两个多月没更新博客了。最近一直在忙着准备实习招聘，所以没有学习什么Android的新的东西，而是在学习招聘中最被重视之一的数据结构与算法，而自己又非科班出身，哎......也许没那么难，加油！另外，对于这个博客，我是想专门写一些安卓的知识方便自己回顾还有比我新手的来参考的，就像我收藏的很多专门讲Android的博客那样。终有一天时机到了，会推倒重写这个Blog！

约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。

一看到这个问题就想到用循环链表来实现，贴出个人写的代码，思路也体现在代码中咯。

<span style="font-size:14px;">/*
*	约瑟夫环问题
*	作者: leelit
*	时间: 2015/3/6
*/

#include "stdafx.h"
#include "malloc.h"
#include "stdio.h"

/*循环链表结点*/
typedef struct ListNode
{
	int number;  
	struct ListNode *next;
}ListNode;

ListNode *createList(int n);
ListNode *removeList(ListNode *p);
int Josephus(int number, int start, int loop);

int main(int argc, char* argv[])
{
	int c = Josephus(10,1,1);
	printf("%d\n",c);
	return 0;
}


/*
*	功能：创建一个n个结点的循环链表，链表
*		  数据域即为约瑟夫环的编号，从1开始递增
*/
ListNode *createList(int n)
{
	if(n < 1)  
	{
		printf("wrong input");
		return NULL;
	}

	ListNode *head = (ListNode *)malloc(sizeof(ListNode));
	ListNode *p;
	head->number = 1; 
	head->next = head;
	p = head;

	for(int i = 1; i < n; i++)
	{
		ListNode *s = (ListNode *)malloc(sizeof(ListNode));
		s->number = i+1;  
		p->next = s;
		s->next = head;
		p = s;
	}
	return head;
}

/*
*	功能：删除某个结点
*	参数：被删除结点的指针
*	返回：被删除结点的指针域，即下一个结点的指针
*/
ListNode *removeList(ListNode *p)
{
	ListNode *next = p->next;
	free(p);
	return next;
}

/*
*	功能：求解约瑟夫环问题
*	参数：number 环的大小； start 开始的编号； loop 走的步数  
*	返回：约瑟夫环的解
*/
int Josephus(int number, int start, int loop)
{		
	if(start > number)  // 开始的地方不能大于环的大小
	{
		printf("start can not be bigger than number\n");
		return -1;
	}

	if(loop < 1)  // 走的步数至少为1
	{
		printf("loop at least is 1\n");
		return -1;
	}

	ListNode *one = createList(number);  // 创建一个循环链表
	ListNode *p = one;  
		
	for(int i = 1; i < start; i++)  
	{
		p = p->next;  // 此处p是开始结点
	}
	
	while(p->next != p)  // 循环到最后一个就是自己啦，那就是解啦
	{
		for(int j = 1; j < loop; j ++)
		{
			p = p->next;  // 此处p是删除结点的前驱结点
		}
		ListNode *s = p->next;  // 要删除的结点
		p->next = s->next;  // 把表链上
		p = removeList(s);  // removeList返回：被删除结点的指针域，即下一个结点的指针
	}
	return p->number;
	
 }</span>

希望可以给研究约瑟夫环问题没有头绪的人一点参考吧(*^_^*) …

数据结构：循环链表求解约瑟夫环有关问题

相关推荐