约瑟夫环.cpp

有回文字判断

/*计算机071 冯一超编写的约瑟夫环
单项循环链表实现 原创程序  
在结构体中定义了一个序号，使得空间变大，但是程序简单易懂      
*/

#include <stdio.h>
#include <malloc.h>
struct node 
{
	int num;//为方便表达，每个节点拥有一个序号
	int password;//密码
	struct node *next;
};
node * creatlist(int people)//构造链表
{
	int i=1;//序号
	int _password;
	node *r,*s;
	node *L=(node *)malloc(sizeof(node));//创造头结点
	r=L;
	while(i<=people)
	{
		printf("请输入第%d个人的密码：",i);
		scanf("%d",&_password);
		s=(node *)malloc(sizeof(node));
		s->num=i;
		s->password=_password;
		r->next=s;
		r=s;
		i++;
	}
	r->next=L;//循环链表
	return L;
}


void getoutseq(node *L,int firstp)//计算出列顺序并输出的函数
{
	int _password=firstp;
	node *p=L;
	node *r=L;//r为p的前驱节点
	int i=1;
	while(L->next!=L)//当L为非空表时一直循环，空表表示所有人已经出列，则退出循环
	{
		while (i<=_password)//根据密码移动指针
		{
			if (p->next!=L)//当p的下一个节点非头结点，直接向下移
				{
					r=p;//p移动前先备份
					p=p->next;
				}	
			else//当p的下一个节点是头节点，则令p指向一号节点
				{
					r=L;
					p=L->next;
				}
			i++;
		}
		printf("%d号出列\n",p->num);	
		_password=p->password;//获取节点中的密码
		r->next=p->next;//删除并释放p
		free(p);
		i=1;
		p=r;
	}
	printf("结束!\n");
}
/*
void print(node *L)//该函数用于打印每个节点的信息，方便测试
{
	node *p=L->next;
	while(p!=L)
	{
		printf("序号%d密码%d\n",p->num,p->password);
		p=p->next;
	}
	
}
*/
int main()
{
	node *list;
	int people;
	int firstp;
	printf("请输入人数：");
	scanf("%d",&people);
	putchar('\n');
	printf("请输入初始密码：");
	scanf("%d",&firstp);
	putchar('\n');
	list=creatlist(people);
/*	print(list);     //该语句用于测试
*/
	getoutseq(list,firstp);
	printf("按确定键退出。。。");
	getchar();
	getchar();
	return 0;
}