约瑟夫生死游戏

1. 约瑟夫 1.1 方法1 Linear_List_YUSEFUHUAN.c #include "stdio.h" #include "stdlib.h" #include "stdbool.h" typedef bool status; //结点的声明 struct Node { int data; struct Node *next; }; status YueSeFu(int N,int n)//N表示创建多少个,n表示数数数 { struct Node *L=(struct Node *)malloc(sizeof(struct Node));//建立第一个结点(不带头结点) L->data=1; L->next=NULL; struct Node *rear=L;//找到尾结点,使用尾插法进行插入数据 struct Node *temp=NULL; for(int i=2;i<=N;i++) { temp=(struct Node *)malloc(sizeof(struct Node)); temp->data=i; temp->next=NULL; rear->next=temp; rear=temp; } rear->next=L; struct Node *move=L; struct Node *temp1=NULL; while(move->next!=move) { for(int i=2;i<=n;i++) { temp1=move; move=move->next; } temp1->next=move->next; move=move->next; } printf("胜利的数据:%d\n",move->data); } int main() { YueSeFu(7,3); return 0; } 1.2 方法2 yuesefu.c #include<stdio.h> #include<stdlib.h> #include<stdbool.h> typedef bool status; struct Node{ int num; struct Node* next; }; //初始化创建循环单链表 struct Node* loop_creat(){ struct Node* p = (struct Node*)malloc(sizeof(struct Node)); if(p==NULL){ printf("创建失败\n"); return NULL; } p->num = 0; p->next = p; return p; } //头插法 status loop_head_insert(struct Node* p,int data){ if(p->next==p){//链表为空 struct Node* new = (struct Node*)malloc(sizeof(struct Node)); if(new==NULL){ return false; } new->num = data; p->next = new; new->next = p; return true; } //链表中有数据 struct Node* new = (struct Node*)malloc(sizeof(struct Node)); new->num = data; struct Node* tmp = p->next; p->next = new; new->next = tmp; return true; } //遍历链表 status loop_travel(struct Node* p){ if(p->next == p){//链表为空 printf("链表为空\n"); return false; } struct Node* tmp = p; while(tmp->next!=p){ tmp = tmp->next; printf("%d ",tmp->num); } return true; } //删除结点__头删法 status loop_delete_head(struct Node* p){ if(p->next==p){//链表为空 printf("链表为空无法删除\n"); return false; } struct Node* temp1 = p->next; struct Node* temp2 = temp1->next;//后一个节点 p->next = temp2; temp1->next = NULL; free(temp1); return true; } //删除头结点 struct Node* delete_head_node(struct Node* p){ if(p->next==p){ printf("链表为空\n"); return NULL; } struct Node* tmp = p->next; while(tmp->next!=p){//遍历到最后一个节点 tmp = tmp->next; } tmp->next = p->next;//直接跳过头结点，使最后一个节点指向第一个节点 free(p);//释放头结点 p=NULL; return tmp->next;//返回第一个节点地址 } //不带头结点的遍历 status loop_travel_no_head(struct Node* s){ if(s==NULL){ printf("链表为空\n"); return false; } struct Node* tmp = s; do{ printf("%d ",tmp->num); tmp = tmp->next; }while(tmp!=s); } //不带头结点统计个数 int loop_ele_sum(struct Node* s){ if(s==NULL){ printf("链表为空\n"); return 0; } struct Node* tmp = s; int count = 0; do{ count++; tmp = tmp->next; }while(tmp!=s); return count; } //尾插法 status loop_back_insert(struct Node* p,int data){ if(p->next==p){//链表为空 struct Node* new = (struct Node*)malloc(sizeof(struct Node)); if(new==NULL){ return false; } new->num = data; p->next = new; new->next = p; return true; } struct Node* new = (struct Node*)malloc(sizeof(struct Node)); if(new==NULL){ return false; } struct Node* tmp = p; while (tmp->next!=p) { tmp = tmp->next; } new->num = data; tmp->next = new; new->next = p; return true; } //添加循环链表数据 struct Node* loop_add(int num){ //创建链表 struct Node* L = loop_creat(); for(int i=1;i<=num;i++){ loop_back_insert(L,i); } //删除头结点 struct Node* s = delete_head_node(L); return s; } //约瑟夫 // 1 2 3 4 5 6 7 // 1 2 4 5 6 7 // 1 2 4 5 7 // 1 4 5 7 // 1 4 5 // 1 4 // 4 status yusefu_game(int num,int people){ struct Node* s = loop_add(people); struct Node* cur = s;//当前节点 struct Node* pre = NULL;//保存前一个节点 int count=1; int ret = loop_ele_sum(s);// //遍历 printf("游戏选手如下\n"); loop_travel_no_head(s); printf("\n"); printf("开始游戏\n"); while(ret>1){ count++; cur = cur->next; if(count==num){ if(cur==s){//如果我们便利的第一个节点被杀，就将他指向他的下一个节点，方便我们遍历输出 s = cur->next; } pre->next = cur->next;//删掉节点 free(cur); cur = pre->next;//cur重新指向被删除节点的下一个节点 count = 1; //看看谁被杀了，谁活着 loop_travel_no_head(s); printf("\n"); ret--; } pre = cur;//保存前一个节点 } printf("恭喜你活下来：%d",cur->num); } int main() { // struct Node* L = loop_creat(); // printf("\n***************\n"); // loop_back_insert(L,1); // loop_back_insert(L,2); // loop_back_insert(L,3); // loop_back_insert(L,4); // loop_back_insert(L,5); // loop_back_insert(L,6); // loop_back_insert(L,7); // //删除头结点 // struct Node* s = delete_head_node(L); //遍历删除头结点后的链表 // loop_travel_no_head(s); // printf("\n***************\n"); // int ret = loop_ele_sum(s); // printf("%d\n",ret); printf("\n***************\n"); int num,people; printf("请输入数到几被杀死："); scanf("%d",&num); printf("请输入几个人参加游戏："); scanf("%d",&people); yusefu_game(num,people); return 0; }