josephus.cpp

这个是编译原理课程的词法分析器

#include<iostream.h>
#include<conio.h>

/*
 * 定义单链存储结构
 */
typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*LinkList;

/*
 * 主函数
 */
void main(){
	// 定义初始报数上限值m、人数n
	int m,n,t[30],j(0);     
	cout<<"输入初始报数上限值m(正整数):";
	cin>>m; 
	cout<<"输入人数n(正整数<=30):";
	cin>>n; 
	cout<<"输入每个人的密码(以空格符为分隔号):"<<endl;
	for(int i=0;i<n;i++)
		cin>>t[i];      
	LinkList p,head;
	head=new LNode;
	head->data=0;
	head->next=0;
	p=head;
	// 初始化单向循环链表
	for(i=1;i<n;i++){
		struct  LNode *s=new LNode;
		s->data=i;
		p->next=s;  
		p=p->next;      
	}
	p->next=head;
	//处理出列顺序
	while(p->data!=p->next->next->data&&j<m){    
		if(j==m-1){
			int n=p->next->data;    
			m=t[n];
			j=0;
			cout<<n+1<<endl;
			if(p->data==p->next->next->data)
				break;              
			p->next=p->next->next;      
		}
		if(p->data==p->next->next->data){
			// 倒数第二个出列者
			cout<<p->next->data+1<<endl;    
			break;  
		}   
  	p=p->next;
  	j++;        
	}   
	// 最后一个出列者
  cout<<p->data+1<<endl;  
  getch();
}