约瑟夫环问题是一道经典的数据结构的题目，问题描述为：编号为1,2,......,n的n个人按顺时针方向围坐在一张圆桌周围，每个人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始报数，报到m时停止报数，报到m的那个人出列，将他的密码作为新的m值，从他顺时针方向的下一个人开始重新从1报数，数到m的那个人又出列，如此下去，直至圆桌周围的人全部出列为止。
我选择用双向链表来存储每个人的信息，每个结点存储的内容有：name[20]，password，flag（顺逆时针的标志）以及prior和next指针。
typedef struct person
{
char name[20];
int password;
int flag;
struct person *prior, *next;
}Node;
在初始化整个链表时，每个人的password和flag是通过随机数随机获取的，flag=0表示按顺时针旋转报数，flag=1表示按逆时针旋转报数。初始化完毕，开始报数，第一个报数的人由用户输入获得，遍历整个链表，找到与输入的名字相同的那个结点，将其password，flag记录下来，再定义两个指针，一个指向刚刚找到结点的下一个（或前一个）结点，一个在以后的遍历中，将指向被删掉的结点。要注意的是双向链表的删除有两个语句。
定义：
#include <stdio.h> #include <stdlib.h> #include <time.h> #define N 10 typedef struct person { char name[20]; int password; int flag; struct person *prior; struct person *next; }Node;
初始化：
Node *create_link(int n) { int i=1; Node *head; Node *s,*p; srand((int)time(NULL)); head = (Node *)malloc(sizeof(Node)); printf("请输入姓名："); getchar(); scanf("%[^\n]",head->name); head->password = rand()%N+1; head->flag = rand()%2; p = head; while(i < n) { s = (Node *)malloc(sizeof(Node)); printf("请输入姓名："); getchar(); scanf("%[^\n]",s->name); s->password = rand()%N+1; s->flag = rand()%2; p->next = s; s->prior = p; p = s; i++; } p->next = head; head->prior = p; output(head); return head; }
run：void run(Node *head,Node *q,int n) { int i=0; int password = q->password; int flag = q->flag; Node *s,*r; s = r = q; while(i<(n-1)) { s = r; if(flag == 0) { r = s->next; while(password > 0) { s = s->next; password--; } } else { r = s->prior; while(password > 0) { s = s->prior; password--; } } flag = s->flag; password = s->password; printf("此次出局的是：%s\n",s->name); s->prior->next = s->next; s->next->prior = s->prior; free(s); i++; } printf("最后留下的是%s\n",r->name); }
输出函数：void output(Node *head) { Node *p = head; printf("flag=0表示顺时针，flag=1表示逆时针\n"); while(p->next != head) { puts(p->name); printf("password:%d\n",p->password); printf("flag:%d\n\n",p->flag); p = p->next; } puts(p->name); printf("password:%d\nflag:%d\n\n",p->password,p->flag); }
main函数：
int main(int argc, char *argv[]) { int n,i=0,flag=1; char name[20]; Node *head,*p; printf("请输入总人数："); scanf("%d",&n); head = create_link(n); printf("请输入第一位开始者的姓名\n"); getchar(); scanf("%[^\n]",name); p = head; do { while(i<n) { if(strcmp(p->name,name)==0) { flag = 0; break; } else { p = p->next; i++; } } if ( i == n) { printf("未找到该人，请重新输入："); getchar(); scanf("%[^\n]",name); p = head; i = 0; } }while(flag == 1); run(head,p,n); return EXIT_SUCCESS; }
运行结果：
在这里，特别告诉大家一个要注意的地方，我在接收name的时候，没有用gets（），（ps：因为它总是提示：警告： 不建议使用‘gets’(声明于 /usr/include/stdio.h:638) [-Wdeprecated-declarations]），这是因为gets是不会去检查字符串的长度的，那么如果输入的字符串过长，则会造成溢出现象，所以这里我换用了scanf（“%[^\n]”,name）;这样就会避免溢出所带来的可怕后果。关于这个“scanf扫描集”，建议大家阅读这篇博客，写的很清楚.博客地址
下面是用c++实现的约瑟夫环，代码思想基本一样，只是用了类，本人菜鸟一只，大家就凑合着看吧。
#include <stdio.h> #include <stdlib.h> #include <time.h> #include <string.h> #define N 10 typedef struct person { char name[20]; int password; int flag; struct person *prior; struct person *next; }node; class people { private: int n; node *head; node *p; public: void create_link(); void run(); void output(); void find_p(); void getvalue(); }; void people::create_link() { int i=1; node *s,*r; srand((int)time(NULL)); head = new node(); printf("请输入姓名："); getchar(); scanf("%[^\n]",head->name); head->password = rand()%N+1; head->flag = rand()%2; r = head; while(i < n) { s = new node(); printf("请输入姓名："); getchar(); scanf("%[^\n]",s->name); s->password = rand()%N+1; s->flag = rand()%2; r->next = s; s->prior = r; r = s; i++; } r->next = head; head->prior = r; } void people::output() { node *p = head; printf("flag=0表示顺时针，flag=1表示逆时针\n"); while(p->next != head) { puts(p->name); printf("password:%d\n",p->password); printf("flag:%d\n\n",p->flag); p = p->next; } puts(p->name); } void people::run() { int i=0; int password = p->password; int flag = p->flag; node *s; while(i<(n-1)) { s = p; if(flag == 0) { p = s->next; while(password > 0) { s = s->next; password--; } } else { p = s->prior; while(password > 0) { s = s->prior; password--; } } flag = s->flag; password = s->password; printf("此次出局的是：%s\n",s->name); s->prior->next = s->next; s->next->prior = s->prior; i++; } printf("最后留下的是%s\n",p->name); } void people::find_p() { int i = 0; int flag = 1; char name[20]; printf("请输入第一位开始者的姓名\n"); getchar(); scanf("%[^\n]",name); p = head; do { while(i<n) { if(strcmp(p->name,name)==0) { flag = 0; break; } else { p = p->next; i++; } } if ( i == n) { printf("未找到该人，请重新输入："); getchar(); scanf("%[^\n]",name); p = head; i = 0; } }while(flag == 1); } void people::getvalue() { printf("请输入总人数："); scanf("%d",&n); } int main(int argc, char *argv[]) { people s; s.getvalue(); s.create_link(); s.find_p(); s.run(); return 0; }
