编号为1,2…n的人按顺时针方向围坐一圈,每个人持有一个密码(正整数)。开始任选一个整数作为报数上限m,从第一个人顺时针自1开始顺时针报数,报到m时停止报数。报到m的人出列,将他的密码作为新的m值,从他顺时针方向上的下一个人开始重新从1报下去,如此下去,直到所有的人全部出列为止。
例如,m的初值为20;n=7,7个人的密码依次是3,1,7,2,4,8,4。求出列的顺序。
求解思路:利用不带头结点的循环单链表求解
在本程序中,节点内有三部分,序号、密码和指针域
存在问题:无法输入初始报数人数,输入完密码回车后就开始死循环打印
#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
int data;//密码
int data_order;//序号
struct Node* next;
}Node,*LinkList;
//初始化循环单链表,返回值为指针
Node* IntCLinkList()
{
Node *CL;
CL=(Node*)malloc(sizeof(Node));
CL->next=NULL;
return(CL);
}
//建立循环单链表
int CreateCLinkList(LinkList CL)
{
Node *rear,*s;
int c;
rear=CL;
int i=1,count=0;
printf("Please input the key if no.%d preson:",i);
while(scanf("%d",&c)!=0)
{
s=(Node*)malloc(sizeof(Node));
s->data=c;
s->data_order=i;
rear->next=s;
rear=s;
i++;
count++;
printf("Please input the key if no.%d preson:",i);
}
return(count);//返回节点数 (初始人数)
}
//删除节点并返回新key
int DelNode(LinkList CL,int count,int *order_save)
{
int i,key;
Node *p,*q;
p=CL;//令P指向表头
//令P指向最后一个报数的前一个人
//定位到上一次删除节点的下一个
for(i=0;i<count;i++)
{
if(p->data_order!=(*order_save))
p=p->next;
else
break;
}
for(i=0;i<count-1;i++)
{
p=p->next;
}
q=p->next->next;
p->next=q;
p=p->next;
key=p->data;
*order_save=q->data_order;
printf("\n%5d",p->data_order);
return(key);
}
//显示输入
void showInput(LinkList CL)
{
Node *p;
p=CL->next;
while(p->next!=CL)
{
printf("%d %d\n",p->data,p->data_order);
p=p->next;
}
}
int main() {
int m=0,count,key,order_save;//保存上一次删除节点下一个节点的位置信息
Node *CL=IntCLinkList();
count=CreateCLinkList(CL);
showInput(CL);
printf("\nPlease input the sum of the first count:");
scanf("%d",&m);
if(m>count)
count=m%count;
while(count!=0)
{
key=DelNode(CL,count,&order_save);
m=key;
count--;
if(m>count)
count=m%count;
}
return 0;
}