重写约瑟夫回环（循环单链表）

问题描述设有n个人围坐在圆桌周围现从某个位置m1≤m≤n上的人开始报数报数到k的人就站出来。下一个人即原来的第k1个位置上的人又从1开始报数再报数到k的人站出来。依此重复下去直到全部的人都站出来为止。试设计一个程序求出出列序列。思路子问题1查找第一个报数为 k 的子问题2何时退出#ifndef JOSEPH_CLINKLIST_H #define JOSEPH_CLINKLIST_H // 循环链表 // 最后一个结点的指针指向头结点 // // 有时候可以设置尾指针更方便表的连接操作 typedef struct Node { int elem; struct Node * next; }clinklist, *pclinklist; pclinklist clinklist_create(int size); void clinklist_insert(pclinklist list, int locate, int elem); void clinklist_delete_location(pclinklist list, int locate); void clinklist_delete(pclinklist list, pclinklist node); void clinklist_display(pclinklist list); pclinklist clinklist_find(pclinklist list, int location); int clinklist_is_tail(pclinklist list, pclinklist node); int clinklist_is_head(pclinklist head, pclinklist node); int clinklist_is_empty(pclinklist list); int clinklist_size(pclinklist list); void clinklist_update_head(pclinklist list); #endif#include stdio.h #include stdlib.h #include joseph.h int main() { int size 0; int m 0; int k 0; pclinklist list NULL; printf(输入人数 n ); scanf_s(%d, size); if (size 0) return -1; printf(输入报数起点 m ); scanf_s(%d, m); if (m 0 || m size) return -2; printf(输入报数到几退出 k ); scanf_s(%d, k); // 极端情况考虑k n , k n, k 1 if (k 0) return -3; list clinklist_create(size); clinklist_display(list); // 找到 m 点 pclinklist node clinklist_find(list, m - 1); printf(开始从 %d 报数\n, node-elem); int index 1; while (!clinklist_is_empty(list)) { if (index k) { printf(第 %d 号选手遗憾出局\n, node-elem); pclinklist new_node node-next; clinklist_delete(list, node); node new_node; if (clinklist_is_head(list, node)) node node-next; index 1; } else { node node-next; if (clinklist_is_head(list, node)) node node-next; index; } } return 0; } pclinklist clinklist_create(int size) { pclinklist node, head; head (pclinklist)malloc(sizeof(clinklist)); // 头结点 elem 表示链表大小头结点 next 指向第一个元素 head-elem size; head-next NULL; node head; for (int i 0; i size; i) { node-next (pclinklist)malloc(sizeof(clinklist)); node node-next; node-elem i 1; node-next NULL; } node-next head; return head; } void clinklist_display(pclinklist plist) { pclinklist head plist; pclinklist node head-next; while (1) { if (clinklist_is_head(head, node)) break; printf(%d\t, node-elem); node node-next; } printf(\n); } void clinklist_insert(pclinklist plist, int location, int elem) { pclinklist head plist; pclinklist inode NULL; int size clinklist_size(plist); if (location 0 || location size) return; inode (pclinklist)malloc(sizeof(clinklist)); inode-elem elem; if (location 0) { inode-next head-next; head-next inode; } else { pclinklist node clinklist_find(plist, location - 1); pclinklist next node-next; node-next inode; inode-next next; } clinklist_update_head(head); } void clinklist_delete_location(pclinklist plist, int location) { pclinklist head plist; int size clinklist_size(plist); if (location 0 || location size) return; if (location 0) { pclinklist dnode head-next; head-next dnode-next; free(dnode); } else { pclinklist node clinklist_find(plist, location - 1); pclinklist dnode node-next; node-next dnode-next; free(dnode); } clinklist_update_head(head); } void clinklist_delete(pclinklist plist, pclinklist node) { pclinklist prior plist; do { if (node prior-next) { prior-next node-next; free(node); break; } prior prior-next; } while (!clinklist_is_head(plist, prior)); clinklist_update_head(plist); } pclinklist clinklist_find(pclinklist list, int location) { pclinklist head list; pclinklist node head-next; if (location 0) return node; else { while (location ! 0) { if (clinklist_is_head(head, node)) break; node node-next; location--; } if (location ! 0) return NULL; return node; } } int clinklist_is_tail(pclinklist head, pclinklist node) { return (clinklist_is_empty(head) || node-next head) ? 1 : 0; } int clinklist_is_head(pclinklist head, pclinklist node) { return (head node) ? 1 : 0; } int clinklist_is_empty(pclinklist list) { return list list-next; } int clinklist_size(pclinklist list) { return list-elem; } void clinklist_update_head(pclinklist list) { pclinklist head list; pclinklist node head-next; int size 0; while (node ! head) { size; node node-next; } head-elem size; }