单链表应用:约瑟夫问题
输入格式
输入两个整数 n,m。
输出格式
输出一行 n个整数,按顺序输出每个出圈人的编号。
样例
输入 :10 3
输出 :3 6 9 2 7 1 8 5 10 4
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
#define error 0
#define ok 1
#define overflow -2
typedef int status;
typedef int elemtype;
typedef struct lnode{
elemtype data;//数据域
struct lnode *next;//指针域
}lnode, *linklist;
//带头结点单链表的3个基本函数及1个辅助函数:
status initlist(linklist &l) //初始化;
{
l=(linklist)malloc(sizeof(lnode));
l->next=NULL;
return ok;
}
status inputlist(linklist &l) //输入,尾插法 ;
{ int i,n ; linklist p,q;
//printf("please input the length of the linklist:");
scanf("%d",&n);
q=l;
//printf("please input the data of the linklist:");
for (i=n;i>=1;i--) {
p=(linklist)malloc(sizeof(lnode));
scanf("%d",&p->data);
p->next=NULL;
q->next=p;
q=p;
}
return ok;
}
status listtraverse(linklist l)// 输出,先输出数据元素、后输出长度;
{
int j; linklist p;
p=l->next; j=0;
//printf("the data of the linklist:");
p=l->next;
while (p!=NULL)
{ printf("%d ",p->data);
p=p->next;
j++;
}
printf("\n");
//printf("the length of the linklist:");
printf("%d\n",j);
return ok;
}
status destroylist(linklist &l) //撤销;
{ linklist p,q;
q=l;p=l->next;
while (p!=NULL)
{ q->next=p->next;
free(p);
p=q->next;
}
free(l);
return ok;
}
//按位序删除(带头结点)
status listdelete(linklist l,int i,elemtype &e)
{
if(i<1)
return false;
lnode *p; //指针p指向当前扫描到的结点
int j=0; //当前p指向的第几个结点
p=l; //L指向头节点,头结点是第0个结点(不存数据)
while(p!=NULL && j<i-1) //循环找到第i-1个结点
{
p=p->next;
j++;
}
if(p==NULL) //i值不合法
return false;
if(p->next==NULL) //第i-1结点之后已无其他结点
return false;
lnode *q=p->next; //令q指向被删除的结点
e=q->data; //用e返回元素值
p->next = q->next; //将*q结点从链中“断开”
free(q); //释放结点的存储空间
return true; //删除成功
}
int main()
{
int m,n,e;
linklist la,p;
initlist (la);
cin>>n;cin>>m;
for(int i=1;i<=n;i++)
{
la->next=(linklist)malloc(sizeof(lnode));
la->next->data=i;
//cout<<i<<" ";
//la->data=i;
}
p=la->next;
int flag=1;
//la=la->next;
while(la)
{
if(flag!=m){
listdelete(la,1,e);
la->next->data=e;
//p=p->next;
flag++;
//cout<<flag<<" ";
}
else{
listdelete(la,1,e);
cout<<e<<" ";
flag=1;
}
la=la->next;
}
destroylist(la);
return 0;
}