基于C++约瑟夫环问题

#include <stdio.h> /*定义类型*/ typedef struct node { int num; struct node *next; }LinkList; LinkList *head,*back,*temp,*s; /*创建列表*/ void creat_list(int i) { temp=(LinkList*)malloc(sizeof(LinkList)); temp->num=i; if(i==1) { head=temp; temp->next=head; back=head; } else { back->next=temp; temp->next=head; back=temp; } } /*找到开始的人*/ void begin(int m) { int i; temp=head; for(i=1;i<m-1;i++) { temp=temp->next; } } /*以n间隔输出编号并杀死该编号*/ void kill(int n,int N) { int i,total=N; if(n==1)//一开始时未考虑，输入（50,1,1）时结果错误 { printf("%d\t",temp->num); while(total>2)//想到的第一个算法，没有free步骤，内存泄露 { for(i=1;i<n;i++) {temp=temp->next;} printf("%d\t",temp->next->num); temp->next=temp->next->next; total--; } printf("\n\n!!<all killed>!!"); printf("\nexcept No.%d\n",temp->next->num); } else { while(total>1)//算法优化：增加一个指针，找到要删除的节点的前一个节点 { for(i=1;i<n-1;i++) {temp=temp->next;} s=temp; temp=temp->next; printf("%d\t",temp->num); s->next=temp->next; total--; free(temp); temp=s->next; } printf("\n\n!!<all killed>!!"); printf("\nexcept No.%d\n",temp->num); } } int main() { int m,n,i,N; printf("please enter people number (N<50)\n"); scanf("%d",&N); printf("please enter start number\n"); scanf("%d",&m); printf("please enter people blank length\n"); scanf("%d",&n); for(i=1;i<=N;i++) { creat_list(i); } begin(m); printf("the dead list is:\n"); kill(n,N); scanf("%d"); return 0; }