题目：约瑟夫环问题_约瑟夫环问题描述

题目：约瑟夫环问题由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“约瑟夫环问题描述”。

数据结构上机实验报告

02090401 12 雒文杰 题目：约瑟夫环问题

一．问题描述

设有n个人围做一圈，现从某个人开始报数，数到m的人出列，接着从出列的下一个人开始重新报数，数到m的人又出列，如此下去，直到所有人都出列为止。试设计确定他们的出列次序序列的程序。

二．基本要求

运用循环单链表解决约瑟夫环问题。

三．算法说明

本程序采用循环单链表的算法来解决约瑟夫环问题：建立一个循环单链表，按顺序查找指定结点，找到后删除，最后打印删除的编号序列。

四 ．源程序清单 #include #include #define n 7 #define NULL 0 struct clist {int data,order;

/* 人的序号, 密码*/ struct clist *next;

/* 指向下一个节点的指针 */ };typedef struct clist cnode;typedef cnode *clink;clink createclist(int *array,int len)

/* 建立循环链表 */ {clink head;clink before;clink new_node;int i;head=(clink)malloc(sizeof(cnode));if(!head)return NULL;head->data=array[0];head->order=1;head->next=NULL;before=head;for(i=1;i

if(!new_node)

return NULL;

new_node->data=array[i];

new_node->order=i+1;

new_node->next=NULL;

before->next=new_node;

before=new_node;} new_node->next=head;return head;} void main(){clink head,ptr;int find,j,i,a,list[n];printf(“Please input 'm'n”);for(i=0;i

printf(“n”);} head=createclist(list,n);printf(“input first 's'n”);scanf(“%d”,&a);for(i=1;inext;ptr=head->next;head->next=ptr->next;find=ptr->data;printf(“order is %dn”,ptr->order);free(ptr);for(j=1;j

head=head->next;

ptr=head->next;

head->next=ptr->next;

find=ptr->data;

printf(“order is %dn”,ptr->order);

free(ptr);

/* 让最后一个人也出列 */ } }