# include <stdio.h>
# include <malloc.h>
typedef struct Node
{
int data;
struct Node * next;
}NODE,*pnode;
typedef struct linklist
{
pnode phead;
pnode ptail;
int len;
}LINK,*plink;
static pnode getnode(int i);
void init_list(plink list);
static void creat_list(plink list,int n);
void print_list(plink list);
void joseph(plink list,int m);
int main(void)
{
int n,m;
printf ("输入队列长度:");
scanf ("%d",&n);
printf ("输入报数停止的数字:");
scanf ("%d",&m);
plink list;
list = (plink)malloc(sizeof(LINK));
init_list(list);
creat_list(list,n);
print_list(list);
joseph(list,m);
return 0;
}
static pnode getnode(int i) //新建并初始化结点
{
pnode node;
node = (pnode)malloc(sizeof(NODE));
if (!node)
{
printf ("分配内存错误\n");
exit(-1);
}
node->data = i;
node->next = NULL;
return node;
}
void init_list(plink list) //用第一个结点初始化循环链表
{
pnode ptr;
ptr = getnode(1);
list->phead = ptr;
list->ptail = list->phead;
ptr->next = list->phead;
list->len = 1;
}
static void creat_list(plink list,int n) //将其余数据存入循环单链表中
{
int i = 0;
pnode pnew;
for (i=2;i <= n;++i)
{
pnew = getnode(i);
list->ptail->next = pnew;
list->ptail = pnew;
pnew->next = list->phead;
list->len++;
}
printf ("原有队列:\n");
}
void print_list(plink list) //输出链表内容
{
pnode ptr;
ptr = list->phead;
do
{
printf ("%d ",ptr->data);
ptr = ptr->next;
}while(ptr != list->phead);
printf ("\n队列长度:%d\n",list->len);
}
void joseph(plink list,int m) //约瑟夫回环函数
{
int i;
pnode ptr1 = list->ptail;
pnode ptr2 = list->phead;
while(list->len != 1)
{
i = 1;
while(i <= m-1)
{
ptr1 = ptr1->next;
++i;
}
ptr2 = ptr1->next;
ptr1->next = ptr2->next;
free(ptr2);
list->len--;
}
printf ("\n最后的数字:%d\n",ptr1->data);
}