前记：之前对数据结构了解不够深入，主要可能还是之前上的一门“软件技术基础”的课程，那玩意儿，当时还没接触C语言就去学这个了，完全看不懂啊，讲的什么JB玩意儿，导致我对数据结构一直有一种惧怕的心理，哎。。。
约瑟夫环问题：大家都很熟悉，我就随便拷贝一下题目：约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数（其实我的程序是默认从第一个人开始报数），数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。
说一下我的解题思路：首先建立一个循环链表（其实就是一个单链表，然后把头尾指针连起来就OK了），链表节点所存储的值为人员的编号，从1到N，然后报数的过程其实就相当于遍历节点，数到M的人出列，然后输出他对应的节点编号，删除该节点申请的内存空间，如此循环，直到只剩下一个人，即链表的next指针指向自己，循环结束。
下面是代码：（纯手敲，写的不好的，请指正）
#include <iostream> using namespace std; #define N 10
class Node { public: int data; Node *next; }; Node *head=NULL; //头指针 void create_cycle_list(int n) { if(n<1) { cout<<"参数错误，人数不能少于1"<<endl; return ; } Node *p1,*p2; int index=0; while((++index)<n+1) { p1=new Node; p1->data=index; if(index==1)//头结点 { head=p1; } else p2->next=p1; p2=p1; } //p2->data=n; p2->next=head; Node *temp=head; //以下代码只是为了验证循环链表建立是否正确，可以注释掉 for(index=0;index<n;index++) { cout<<temp->data<<endl; temp=temp->next; } } //约瑟夫环问题 //n为总人数 //m为出列者喊道的数字（m的值 每一轮都是一样的） void josep(Node *head,int n,int m) { if(head==NULL) { cout<<"循环链表为空!"<<endl; return ; } Node *p=head; Node *temp; m%=n; m=m-1; int num=m; while(p!=p->next) //p==p->next表示循环链表只剩下一个数据 { while(--m) //移动指针到要删除的元素的上一个元素 { p=p->next; } temp=p->next; cout<<"出列人员的编号："<<temp->data<<endl; p->next=p->next->next; p=p->next; //表示从出列人员的下一个人继续报数 delete temp; temp=NULL; m=num; //给m重新赋值 } cout<<"出列人员的编号："<<p->data<<endl; delete p; //删除剩下的最后一个节点数据 p=NULL; } int main(int argc, char *argv[]) { create_cycle_list(N); josep(head,N,3); return 0; }
程序使用C-Free5.0编写，运行截图如下：
