智博数据结构——约瑟夫问题

约瑟夫问题

例题：N个人围成一个圆形（联想循环链表）,首先第一个人从1开始一个人一个人顺时针报数，报到第M个人，令其出列。然后再从下一个人从1顺时针报数，报道第M个人，在令其出列，如此下去，求出列顺序。

假设m=8，n=3

循环链表https://mp.csdn.net/postedit/85985566

#include "CircleLinkList.h"
#include <stdio.h>
#define  M 8
#define  N 3
typedef struct MUNUM
{CircleLinkNode node;int val;
}MyNum;void Myprint(CircleLinkNode*data)
{MyNum*num = (MyNum*)data;printf("%d ", num->val);
}
int MyComare(CircleLinkNode*data1, CircleLinkNode*data2)
{MyNum*num1 = (MyNum*)data1;MyNum*num2 = (MyNum*)data2;if (num1->val==num2->val){return CIRCLELINKLIST_TRUE; //CIRCLELINKLIST_TRUE=1}return CIRCLELINKLIST_FALSE;//CIRCLELINKLIST_FALSE=0
}
int main()
{CircleLinkList *list = Init_CircleLinkList();//插入MyNum num[M];for (int i = 0; i < 8;i++){num[i].val = i + 1;insert_CircleLinkList(list, i, (CircleLinkNode*)&num[i]);}//打印Print_CircleLinkList(list, Myprint);printf("-------------------\n");int index = 1;//辅助指针CircleLinkNode * pCurrent = list->head.next;while ( Size_CircleLinkList(list)>1){if (index ==N){MyNum* temNum = (MyNum*)pCurrent;printf("%d", temNum->val);//缓存待删除节点的下一个节点CircleLinkNode*pNext = pCurrent->next; // 将pCurrent下一个节点赋值给pNext为了进行判断此时的pNext是否是头节点//根据值删除RemoveByValue_CircleLinkList(list, pCurrent, MyComare);pCurrent = pNext;if (pCurrent ==&(list->head)){pCurrent = pCurrent->next;}index = 1;}pCurrent = pCurrent->next;if (pCurrent == &(list->head)){pCurrent = pCurrent->next; //若当前节点头节点，直接跳过指向下一个节点}index++;}if (Size_CircleLinkList(list) ==1){MyNum* temp=(MyNum*)Front_CircleLinkList(list);printf("%d", temp->val);}else{printf("error");}//FreeSpace_CircleLinklist(list);return 0;
}