报数问题——数据结构（循环链表）

解题思路:

定义有头结点的循环链表，输入数据时用头插法建立递增的链表。

DeleteLNode（）函数删除指定结点，并返回删除的结点的下一个结点。

定义outnum（）函数依次找出报数为3的人，每找到一个报数为3的人就执行DeleteLNode（）函数，直到链表只剩一个人，输出这个人的编号。

注意事项:

1. 头结点数据域为NULL

2. outnum（）函数，注意头结点不参与报数，遇到头结点多执行一次p=p->next，同时也要避免误删头结点

参考代码:

#include<stdio.h>

#include<malloc.h>

typedef struct LNode{

int num;

struct LNode *next;

}LNode,*linklist;

LNode *DeleteLNode(linklist &L,LNode *p)

{

LNode *q=p->next;

p->num=q->num;

p->next=q->next;

free(q);

return p;

}

void ListInsert(linklist &L,int n)

{

L=(linklist)malloc(sizeof(LNode));

L->next=L;//循环链表，等号左右不能搞反 

LNode *s;

for(int i=n;i>0;i--)

{

s=(LNode*)malloc(sizeof(LNode));

s->num=i;

s->next=L->next;

L->next=s;

}

}

void outnum(linklist &L,int n)

{

LNode *p=L->next;

while(n!=1)

{

for(int i=0;i<2;i++)

{

if(p->num==NULL) p=p->next;//移动到头结点需多移一位 

p=p->next;

}

if(p->num==NULL) p=p->next;//防止删除的是头结点，不能省 

p=DeleteLNode(L,p);

n--;

}

}

int main()

{

int n;

scanf("%d",&n);

if(n==1) printf("1");

else if(n==2) printf("2");

else

{

linklist l;

ListInsert(l,n);

outnum(l,n);

printf("%d",l->next->num);

}

return 0;

}