#include<iostream>
using namespace std;
struct node{
int ID;
int pwd;
int num;
node* next;
int Length;
};
node* head=NULL;
node* tail=NULL;
int a[7]={3,1,7,2,4,8,4};
/*struct list{
node;
node* current;
node* head;
node* tail;
};*/
//创建链表,并返回链表的头和尾节点
node* creatlist()
{
head=(node*)malloc(sizeof(node));
tail=head;
tail->next=head;
//head->Length=1;
return head;
}//创建链表
//判表非空
int isEmpty(){
if(head==tail&&head==NULL)
return 0;
else
return 1;
}//判表非空
//删除当前节点
/*void deleteCurrentNode(node* current){
if(isEmpty()){
if(current==head)
{
head=head->next;
tail->next=head->next;
}
else
if(current==tail)
{
}
}
}*/
//插入新的节点，并返回当前刚插入的接点的地址
node* insert(){
node* p=(node*)malloc(sizeof(node));
tail->next=p;
p->next=head;//head=p->next;注意方向,这样写会出现严重的错误.
tail=p;
return p;
}
//创建一个循环链表，包含n个节点，并含有各个人的密码
node* initL(int n)
{
node* p;
node* current;
p=creatlist();
p->ID=1;
p->pwd=3;
for(int i=0;i<n;i++){
current=insert();
//cout<<"请输入第"<<i+1<<"个人的密码："<<endl;
//cin>>current->pwd;
current->ID=i+2;
current->pwd=a[i+1];
}
head=p;
return p;
}
void find(int m){
node* pBegin=head;//遍历开始的指针
node* p;
node* p1;
while(head!=head->next){
p=pBegin;
p->num=1;//第一个节点报数1
while((p->num)!=m)//找报数为m的节点
{
p1=p;//记录下p的位置，当p向后指是从而能找到p的前一个位置
p=p->next;
p->num=p1->num+1;//注意此处不要写成p->num++,显然是错误的，因为p 已经指向新的节点，而新节点的num是
//是没有初始化的
}
//循环结束，找到报数为m的节点
pBegin=p->next;//记录当前节点的下一个位置，作为下次遍历开始的位置
m=p->pwd;
cout<<p->ID<<" ";//注意此处应打印ID，而不是他们报的数num
if(p==tail)
{
p1->next=p->next;
tail=p1;
free(p);
}
else
{
if(p==head)
{
tail->next=head->next;
head=head->next;
free(p);
}
else
{
p1->next=p->next;
free(p);
}
}
}
cout<<head->ID<<" ";
}
int main(){
initL(6);
find(6);
return 0;
}
//总结：本题不需要使用头节点，因为头节点不能赋值，故而当循环遍历时会出现问题，本题开始没有考虑到这一点
//，从而出现了上面这种很别扭的局面。即定义了头节点，却又对其赋值，实际上等于没有头节点。
//测试已经创建的链表
/*int main(){
node* p=NULL;
tail=head=creatlist();
tail->num=3;
for(int i=0;i<3;i++){
insert();
}
p=head->next;
for(int j=0;j<3;j++)
{cout<<(p->pwd)<<" ";
p=p->next;}
return 0;
}*/
