算法3.单向循环链表// 03_单向循环链表.cpp : 此文件包含 main 函数。程序执行将在此处开始并结束。//#includeiostream#includestdlib.h#includetime.husingnamespacestd;structNode{Node(intdata0):data_(data),next_(nullptr){}intdata_;Node*next_;};// 约瑟夫环问题 - 不带头结点的单项循环链表应用voidJoseph(Node*head,intk,intm){Node*phead;Node*qhead;// q指向最后一个while(q-next_!head){qq-next_;}// 从第k个人开始报数的for(inti1;ik;i){qp;pp-next_;}// p - 第k个人for(;;){for(inti1;im;i){qp;pp-next_;}// 删除p指向的结点// q p nodecoutp-data_ ;if(pq){deletep;break;}q-next_p-next_;deletep;pq-next_;}}intmain(){Node*headnewNode(1);Node*n2newNode(2);Node*n3newNode(3);Node*n4newNode(4);Node*n5newNode(5);Node*n6newNode(6);Node*n7newNode(7);Node*n8newNode(8);head-next_n2;n2-next_n3;n3-next_n4;n4-next_n5;n5-next_n6;n6-next_n7;n7-next_n8;n8-next_head;Joseph(head,1,5);}#if0// 单向循环链表classCircleLink{public:CircleLink(){head_newNode();tail_head_;head_-next_head_;}~CircleLink(){Node*phead_-next_;while(p!head_){head_-next_p-next_;deletep;phead_-next_;}deletehead_;}public:// 尾插法 O(1)voidInsertTail(intval){Node*nodenewNode(val);node-next_tail_-next_;// node-next_ head_;tail_-next_node;tail_node;// 更新tail_指针指向新的尾节点}// 头插法voidInsertHead(intval){Node*nodenewNode(val);node-next_head_-next_;head_-next_node;if(node-next_head_){tail_node;}}// 删除节点voidRemove(intval){Node*qhead_;Node*phead_-next_;while(p!head_){if(p-data_val){// 找到删除节点 head// qq-next_p-next_;deletep;if(q-next_head_){tail_q;}return;}else{qp;pp-next_;}}}// 查询boolFind(intval)const{Node*phead_-next_;while(p!head_){if(p-data_val){returntrue;}}returnfalse;}// 打印链表voidShow()const{Node*phead_-next_;while(p!head_){coutp-data_ ;pp-next_;}coutendl;}private:structNode{Node(intdata0):data_(data),next_(nullptr){}intdata_;Node*next_;};Node*head_;// 指向头节点Node*tail_;// 指向末尾节点};intmain(){CircleLink clink;srand(time(NULL));clink.InsertHead(100);for(inti0;i10;i){clink.InsertTail(rand()%100);}clink.InsertTail(200);clink.Show();clink.Remove(200);clink.Show();clink.InsertTail(300);clink.Show();}#endif