c2_joseph.cpp

这个是严蔚敏版的数据结构上机教程中的部分源代码

/*
Joseph问题，循环链表实现，密码随机生成
BY:wangyucao
*/

#include<stdio.h>
#include<stdlib.h>
#include<memory.h>
#include<time.h>
#define OK 1
#define ERROR 0
#define OVERFLOW -1
//#define DEBUG

typedef struct Lnode{
       int num;
       int key;
       Lnode* next;
       }*Linklist;

int CreateList(Linklist &L,Linklist& t,int &nn)
{
     int n;
     Lnode *p,*q;
    // L=(Lnode*)malloc(sizeof(Lnode));
    // L->next=NULL;
     printf("有多少人在环中：");
     scanf("%d",&n);
	 nn=n;
     if(n<1) return ERROR;
     p=(Lnode *)malloc(sizeof(Lnode));       
     if(!p) return OVERFLOW;
     L=p;
	// randomize(); 
     int i=1;
     p->num=i++;
     p->key=(rand()+1)%20+1;
     n--;
     while(n>0)                              
     {
         q=(Lnode *)malloc(sizeof(Lnode));
         if(!q) return OVERFLOW;
         q->num=i++;
         q->key=(rand()+1)%20+1;
         p->next=q;
         p=p->next;
         n--;
     }
     p->next=L;
	 t=p;
     return OK;
}
int DisplayL(Linklist &L)
{
	Lnode *p=L;
	printf("\norder & key : (%d,%d)",p->num,p->key);
	p=p->next;
	while(p != L)
	{
		printf("|(%d,%d)",p->num,p->key);
		p=p->next;
	}
	return OK;
}

int Play(Linklist& L,int m,Linklist& tear,int n)
{
    int i=1;
	Lnode* p;
	Lnode* q;
	p=L;
    while(tear != p)
    {
		if(m>n) {
			m=m%n;
			if(m==0) m=n;
		}
        while(i!=m)
		{
			p=p->next;
			tear=tear->next;
			i++;
		}
		m=p->key;
		printf("%d->",p->num);
		q=p;
		p=p->next;
		tear->next=p;
		free(q);
		n--;
		i=1;
    }
	printf("%d\n",p->num);
	return OK;
}


int main()
{
    Linklist L;
	int m;
	int n;
	Linklist tear;
	srand(time(NULL));  
	CreateList(L,tear,n);
	DisplayL(L);
	printf("\n输入密码：");
	scanf("%d",&m);
	printf("\n出圈顺序为：");
	Play(L,m,tear,n);
    system("PAUSE");
    return OK;
}