- /*
- 对于这个题目，大家既然都可以用数组循环的方式来解决，那么对基本的解决思想是有的，而用数组和链表的区别是：使用数组最大的障碍是下标，因为下标的连续性，导致我们无法判定活着的下一个人在什么位置，而需要遍历当前的人员后边的每一个位置，直到这个人是活的，才参与报数。而使用双向链表的优势在于，每个节点都记录的自己的前一个人的地址是什么，后一个人的地址是什么，便于直接访问。
- */
- #include <stdio.h>
- #include <stdlib.h>
- int main(int argc, const char * argv[]) {
-
- struct people{
- int num; //当前人员的号码
- struct people *top;//当前人员的前一个人员
- struct people *next;//当前人员的后一个人员
- };//声明一个结构体
- typedef struct people Note;
- int N=13,q=3;//N是总人数q是喊到q的人被杀
-
- Note *head,*tail,*pnew,*topNote,*nextNote;
- //head 链表的头
- //head 链表的尾
- //pnew 新添加的元素
- //topNote 上一个元素
- //nextNote 下一个元素
- head=(Note *)malloc(sizeof(Note));//创建头指针
- head->next=NULL;//头指针的下一个地址是空的，可以相当于一个人的时候
- head->num=1;//当前的人的编号
- tail=head;//尾指针指向头指针
- for (int i=2; i<=N; i++) { //初始化链表。为了便于人员编号循环从2开始
- pnew=(Note *)malloc(sizeof(Note));//创建当前人员
- pnew->num=i; //人员的编号
- pnew->top=tail;//新的人员进入链表之后，这个人员的前一个人就是原来链表的最后一个人
- pnew->next=NULL;//新的人员的后边没有人，复制NULL
- tail->next=pnew;//原链表中的后边一个人成了新添加的人员
- tail=pnew;//新的人员进入链表之后，链表的尾指针指向新添加的人员，形成新的链表
- }
- tail->next=head; //链表尾部的下一个节点指向头指针
- head->top=tail;//链表头部的上一个节点指向尾指针 完成环形链表
- //如果这里有疑问，可以打印出连表中每个节点Top next num 和地址，看于想象的是否相同
-
- pnew=tail;//杀人游戏开始，当前节点指向尾指针，因为从头指针还是报数，我们认为尾指针是0
- for (int i=1; i<N; i++) {//循环N-1次，循环一次杀一人
- for (int j=0; j<q; j++) {//循环q次，找到被杀人员pnew
- pnew=pnew->next;
- }
- topNote=pnew->top;//找出被杀人员的上一个人员
- topNote->next=pnew->next;//上一个人员的后边一个人，变成当前人员的后一个人。用数字来表示1 2 3,假设被杀的人员是2号，那么2号的上一个人员（也就是1号）他的右边的人员变成了2号右边的人员。下边相同
- nextNote=pnew->next;//找出被杀的下一个人员
- nextNote->top=pnew->top;//注释同上
- free(pnew);//释放当前空间
- pnew=topNote;//当前人员的上一个人员变成上一个活着的人
- }
- printf("存活的人员编号是：%d\n",pnew->num);//最后链表中只剩一个节点，为了验证，我们做以下操作
- printf("下一个活着的人员的编号是：%d\n",pnew->next->num);
- printf("上一个活着的人员的编号是：%d\n",pnew->top->num);
- return 0;
- }
|
收藏
淘帖
踩
![W1`%A}IVG6X$L_{D%`)]ZWX.jpg](static/image/common/none.gif "W1`%A}IVG6X$L_{D%`)]ZWX.jpg")
