循环链表实现约瑟夫环（数据结构C语言小白版）

循环链表实现约瑟夫环（数据结构C语言小白版）

循环链表实现约瑟夫环

• 问题描述
• • 先附上代码，欢迎评价
  • 一些小点

问题描述

约瑟夫（Joseph）问题的一种描述是：编号为1，2，3，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码〈正整数〉，一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。

先附上代码，欢迎评价

#include 
#include 
#include  
#include 
typedef int ElemType;
typedef struct LNode
{
	int order;
	ElemType data;
	struct LNode *next; 
}LNode,*linkList;

linkList InitList_L()
{
	linkList L;
	L=(linkList)malloc(sizeof(LNode));
	if(L ==NULL)
	{
		printf("申请内存空间失败n");
	}
	L->data=0;
	L->next=NULL;
	return L; 
	
	
} 
int main()
{
	int i,n,m,j=0;
	linkList p1,head;
	head=InitList_L();//设置头结点 
	p1=head;
	printf("请输入报数上限和参与人数"); 
	scanf("%d %d",&m,&n); 
	printf("请依次输入个人的密码:n");
	 for(i=1;i<=n;i++)
	 {
	 	
	 	p1->next=(linkList)malloc(sizeof(LNode));
	 	scanf("%d",&p1->next->data);
	 	p1->next->order=i;
	 	p1=p1->next;
	 }
	 p1->next=head->next;//尾指针指向头指针，构成循环链表
	 linkList p2;
	 p2=head->next;//p2指向第一个人 
	 printf("出列顺序:n") ;
	  
	 while(p2->next!=p2) 
	 {
	 	for(i=1;inext;
		 }
		 printf("%d",p2->order);
		 p1->next=p2->next;
		 m=p2->data;
		 free(p2);
		 p2=p1->next;//重新定义 
		 j++;
	 }
	 printf("%d ",p2->order);
	 free(p2);
	
}

一些小点

1. typedef struct LNode LNode; //将结构体类型struct LNode重命名为LNode
2. typedef struct LNode *linkList; //将struct LNode 重命名为linkList
   所以用linkList和LNode都可以实现对一个结点的初始化。
   3.p1=head;将p1和head一起设为头结点当p1便利一遍指向尾结点的next时，head依然可以指向头结点，就可以很简单的实现循环连结