C语言程序设计教程（第三版）课后习题10.5 （单链表解法）

解题思路:
很多学生会采用数组的方法，用0或1代表是否被淘汰，这种解法有其优点，就是简单，代码比较少，但是缺点也很大，比如

不能充分利用数组空间，容易造成数组越界，或者算法效率低下等等，并且也不是题目的本意，当然，以解决问题为主，其实什么方法都行。这里的建议用单链表，可以克服以上的缺点，并且这也是这道题最官方的解法。

参考代码:

#include<stdio.h>

#include<malloc.h>

#include<assert.h>//断言

typedef struct SList

{

int data;

struct SList *next;  //data域存放这个人的序号，当然原始序号

}Node;

void Initial(Node **head);

void push_back(Node **head,int x);  //插入节点，就是人就坐

int main()

{

int i;

int n;

Node *head;

Initial(&head); //头节点的data域表示人的个数，当剩下一个人的时候，游戏结束

scanf("%d",&n);

for(i=1;i<=n;i++)

{

push_back(&head,i);  //要修改一级指针的值，是不是得传他的地址过去？

}

i=0;

Node *p=head->next;

while(++i)

{

if(head->data==1)

{

printf("%d\n",p->data);

break;

}

if(i%3==0) //如果是3的倍数，也就是题目中的数到3，这个人得离开

{

Node *q=p->next;

p->data=q->data;  

p->next=q->next;

free(q);

head->data--;  //相应的人数减少一个

continue;

}

p=p->next;   //如果数到1和2，那么接着往下数

}

return(1);

}

void Initial(Node **head)

{

(*head)=(Node*)malloc(sizeof(Node));

assert((*head)!=NULL);

(*head)->data=0;

(*head)->next=*head;

return;

}

void push_back(Node **head,int x)

{

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

assert(s!=NULL);

    s->data=x;

s->next=NULL;

if((*head)->data==0)  //构建链表，使得尾节点和第一节点连接起来，节点代表人，头尾相接表示坐成一圈

{

(*head)->next=s;

s->next=s;

}

else

{

Node *p=(*head)->next;

while(p->next!=(*head)->next)

p=p->next;

s->next=p->next;

p->next=s;

}

(*head)->data++;

}