题意:
就是约瑟夫斯问题,首先从一个人开始,越过k-2个人(因为第一个人已经被越过),第k个人出列。接着,再越过k-1个人,第k个人出列。这个过程沿着圆圈一直进行,直到最终只剩下一个人留下。依次输出每个出列的人
要点:
利用循环链表来实现,每次删除结点并输出这个结点的值。实际上最好用双向循环链表,但我用普通的循环链表强行完成了,比较容易WA,有很多特殊情况要考虑:
比如:如果s=1时,第一次删除的就是第w个结点,此时指针指向的就是w结点,所以删除很麻烦,要转一圈找到第w-1个结点来实现删除。
| 15087964 | Seasonal | 3750 | Accepted | 168K | 0MS | C++ | 1033B | 2016-01-20 21:07:17 |
#include<stdio.h>
#include<stdlib.h>
#include<string.h>typedef struct node
{char a[300];struct node *next;
}type;int main()
{type *p = (type *)malloc(sizeof(type)); //p为头指针type *head=p, *tail=p; //需要两个指针分别代表前驱和后继来建立链表int n,i;scanf("%d", &n);for (i = 1; i <= n;i++){tail = (type*)malloc(sizeof(type));scanf("%s", tail->a);head->next = tail;head = tail;}tail->next = p->next; //最后的结点的后继指向最开始的结点int w, s,j=1;scanf("%d,%d", &w, &s);head = p->next;while (j < w){head = head->next;j++;} //第一次数数时自身也要计数,后面就不用了,所以单独讨论if (s == 1) //注意s==1时是特殊的,要拎出来单独讨论{printf("%s\n", head->a);for (i = 1; i < n; i++)head = head->next; //绕一圈找到前驱type *temp=head->next;head->next = temp->next;free(temp);}else{for (i = 1; i <= s - 2; i++){head = head->next;}type *temp = head->next;head->next = temp->next;printf("%s\n", temp->a);free(temp);}n--;while(n--){for (i = 1; i <= s-1;i++){head = head->next; }type *temp = head->next;head->next = temp->next; //删除结点实现循环跳跃printf("%s\n", temp->a);free(temp);}return 0;
}