3.cpp

约瑟夫环源代码,前中后序递归遍历二叉树

#include<stdio.h>
#include<malloc.h>
#define NULL 0
typedef struct node{
    int data;
    int num;
    node *next;
}node,*queue;

typedef struct{
	queue front;  
	queue rear;   
}sqQueue;

int initqueue(sqQueue &q){//构造队列
	q.front=q.rear=(queue)malloc(sizeof(node));
	if(!q.front)return 0;
	q.front->next=NULL;
	return 1;
}

void destroyqueue(sqQueue &q){//销毁队列
	while(q.front){
		q.rear=q.front->next;
		free(q.front);
		q.front=q.rear;
	}
}

int enqueue(sqQueue &q,int e,int num){//插入元素e为Q的新的队尾元素
	node *p=NULL;
	p=(queue)malloc(sizeof(node));
	if(!p)return 0;
	p->data=e;
	p->num=num;
	p->next=NULL;
	q.rear->next=p;
	q.rear=p;
	q.rear->next=q.front->next;
	return 1;
}
	
void main(){
	int n=0,m=0,a=1,b=0;
	sqQueue l;
	node *p,*q;
	p=NULL;
	q=NULL;
	if(initqueue(l)==0)printf("分配存储空间失败");
	printf("请输入人数n=");
	scanf("%d",&n);
	printf("请输入初始计数:");
	scanf("%d",&m);
	printf("请输入每个人的密码(以空格分开):");
	for(int i=0;i<n;i++){
		scanf("%d",&b);
		int j=i+1;
		if(!enqueue(l,b,j)){
			printf("输入失败，请重新输入!");
			i--;
		}
	}
	q=p=l.front->next;
	while(a<=n){	
		for(int i=1;i<m;i++){
			q=p;
			p=p->next;
		}
		m=p->data;
		printf("第%d个出列的是%d\n",a,p->num);
		a++;
		q->next=p->next;
		free(p);
	    p=q->next;
	}

}