思维导图
作业
使用单向循环链表完成约瑟夫环问题
#include <myhead.h>//定义链表节点结构体
typedef struct Node
{int position; //节点存储的位置编号struct Node* next; //指点下一个的节点
}Node,*Node_ptr;//创建循环链表的函数
Node_ptr fun_creation(int n)
{Node_ptr L = NULL; //头节点Node_ptr Q = NULL; //当前节点Node_ptr W = NULL; //临时节点for(int i = 1;i<=n;i++){W = (Node_ptr)malloc(sizeof(Node)); //动态分配新节点的内存//初始化W->position = i; //设置新节点的位置编号W->next = NULL; //新节点的下一个节点初始化为NULLif(L == NULL){L = W; //如果头结点为空，则新节点即为头结点Q = W; //当前节点也指向新节点}else{Q->next = W; //将新节点链接到链表的末尾Q = W; //当前节点移动到新节点}}if(n>0){Q->next = L; //将链表的末尾节点链接到头结点，形成循环链表}return L; //返回头结点
}//解决约瑟夫环问题的函数
void fun_Josephs_ring(int n,int m)
{Node_ptr L = fun_creation(n); //创建包含n个节点的循环链表Node_ptr Q = L; //创建并初始化第一个节点Node_ptr W = NULL; //创建并初始化前一个节点//找到最后一个节点的前一个节点，以便能正确删除第一个节点while(Q->next != L){Q = Q->next;}W = Q; //前一个节点while(n>0){//当链表中还有节点时循环for(int i=0;i<m-1;++i){//报数m次，找到要删除的节点的前一个节点W = Q; Q = Q->next;}//删除当前节点W->next = Q->next; //将前一个节点的下一个节点指向当前节点的下一个节点printf("count:%d\n",Q->position); //输出被删除节点的位置编号free(Q); //释放被删除节点的内存Q = W->next; //当前节点移动到下一个节点n--; //链表中节点数减1}//输出最后一个剩下的节点的位置编号printf("last：%d\n",L->position);
}
int main(int argc, const char *argv[])
{int n = 7; //人数int m = 3; //报数间隔fun_Josephs_ring(n,m); //调用函数解决问题return 0;
}
