约瑟夫环 - f

一、笔记：
单向循环链表，表头只记录头和尾的值，不再链表的循环中；
在进行游戏时，需要找到单向链表要删除的前一个节点和自己，以便于链表能够连接上循环起来；
二、头文件Joseph.h:

#pragma oncetypedef int Element_t;typedef struct _node {Element_t val;struct _node* next;
}node_t;typedef struct {node_t* head;node_t* tail;
}Joseph_t;void initJosephGame(Joseph_t* header,int n);
void showJoseph(const Joseph_t* header);
void startGame(Joseph_t *header,int m);

三、源文件Joseph.c:

#include<stdio.h>
#include<stdlib.h>
#include"Joseph.h"void initJosephGame(Joseph_t* header, int n) {node_t* new_node;for (int i = 1; i <= n; i++) {new_node = malloc(sizeof(node_t));if (i == 1) {header->head = new_node;header->tail = new_node;}else {header->tail->next = new_node;header->tail = new_node;}new_node->next = header->head;new_node->val = i;}
}
void showJoseph(const Joseph_t* header) {node_t* pos = header->head;do {printf("%d\t", pos->val);pos = pos->next;} while (pos != header->head);printf("\n");
}
void startGame(Joseph_t* header, int m) {node_t* pre = NULL;node_t* cur = header->head;while(cur->next!=cur){//报数,要删除元素，需要找到前驱节点，保证链表的连接for (int i = 1; i < m; ++i) {pre = cur;cur = cur->next;}//删除pre->next = cur->next;printf("%d\t", cur->val);free(cur);cur = pre->next;}printf("have %d number!\n", cur->val);header->head = header->tail = cur;}

四、运行文件main.c:

#include"Joseph.h"
#include<stdio.h>void test01() {//记得初始化Joseph_t header = { NULL,NULL };initJosephGame(&header, 7);printf("************************\n");showJoseph(&header);printf("************************\n");startGame(&header, 2);printf("************************\n");//开始游戏只剩下一个元素之后，记得修改表头的值showJoseph(&header);
}
int main(){test01();return 0;
}