datas_003-1.cpp

约瑟夫环的数据结构算法 ＶＣ＋＋６．０实现

#include<stdio.h>

#include<stdlib.h>

typedef struct   LNode
	{
		int      data;							 // 数据域
		struct   LNode   *next;					 // 指针域
	}LNode , *LinkList;  

class intstack						//堆栈类
{
private:
	int a[100];
	int top;
public:
	intstack();
	void push(const int a);
	int pop();
};
intstack::intstack()
{
	top = 0;
}

void intstack::push( const int i )
{
	a[top++] = i;
}

int intstack::pop()
{
	if(top) return a[--top];
	else return 0;
}

int o=0;						//表长
void inprintf()					//提示输入表长
{
	printf("Please input the length of the list:");
	scanf("%d",&o);
	return;
}

void CreateList_L(LinkList &L,int n)			//创建
{
	LinkList q=L,p;
	intstack pstack;
	int i,j=o,pa;
	L = (LinkList)malloc(sizeof(LNode));
	L->next = L; 

	for (i = 0; i < n; i++)							//为了调整顺序把输入数据压入堆栈
	{
		printf("Please input the codes:");								
		scanf("%d",&pa); 
		pstack.push( pa );
	};
							
	for (i = 0; i < n-1; i++) 
	{
		p = (LinkList) malloc (sizeof (LNode));	 
		p->data=pstack.pop();						//弹出数据

		p->next = L->next;
		L->next = p;														//插入
		printf("The %d 'st code is :%d\n",j,p->data);
		j--;
	};
	L->data=pstack.pop();
	printf("The 1 'st code is :%d\n",L->data);				//把堆栈中最后一个数付给头节点
}														// CreateList_L



void main()
{
	inprintf();								//调用inprintf函数
	LinkList L;
	int i=0;	//循环
	int m=0;	//密码
	int t=0;	//长度
	int j=0;	//输出控制
	t=o;		

	printf("\n");

	CreateList_L(L,o);

	printf("\nPlease input the first code(m>0):");
	scanf("%d",&m);
	printf("\nThe out order are :\n\n"); 
	if (L->next==L)										//如果只有一个节点，直接输出
	{
		printf("The only node is : %d\n",L->data);
		return;
	};

	do												//节点多于一个
	{
		if(m==1)								//单独处理m等于1的情况	
		{
			for(i=1;i<t;i++)					
			{
				L=L->next;
			};
			m=L->next->data;
			L->next=L->next->next;
			L=L->next;
			j=j+1;
			printf("The %d 's out code is : %d\n",j,m);
			t--;
		}
		else									//m不为1的情况
		{
			for(i=1;i<m-1;i++)
			{
				L=L->next;
			};
			m=L->next->data;
			L->next=L->next->next;
			t--;
			if (L->next==L)							//当只剩两个个节点时
			{
				j++;
				printf("The %d 's out code is : %d\n",j,m);
				printf("The %d 's out code is : %d\n",j+1,L->data);
				return;
			}	
			j++;
			L=L->next;								//当只有一个节点时
			printf("The %d 's out code is : %d\n",j,m);
		}
	}
	while(L->next!=L);								//当只有一个节点时
	printf("The %d 's out code is : %d\n",j+1,L->data);

}