c++算法解决约瑟夫环问题

下面这个程序是我上学期学数据结构时写的作业,我们学校用的教材是严蔚敏老师的,我写的代码在VC++6.0上编译连接生成可执行程序:
///////////////////////////////////////////////////////////////////
#include
#include

typedef struct lnode
{
int nNumber; // 编号
int nPassword; // 密码
struct lnode *pNext;
} LNODE, *PLINKLIST;

int *Joseph( int *pPassword, int nSize, int m, int *&pNumber )
{
// *************************************************************************
// 参数:
// pPassword [in] 存储密码的一维数组首地址
// nSize [in] 数组 pPassword 中元素的个数,等于人数
// m [in] 报数上限值
// pNumber [out] 存储出列顺序的一维数组首地址,若传入的参数为 NULL ,
// 本函数将为其分配存储空间,调用者负责释放本函数分配的存储空间
// 返回值:
// 若人数大于 0 , 函数返回存储出列顺序的一维数组首地址 pNumber
// 若人数小于等于 0 , 函数返回 NULL
// *************************************************************************

if ( nSize <= 0 )
{ // 若人数小于等于 0 , 返回 NULL
return NULL;
}

// 处理第一个结点,第一个结点的指针域指向其自身
PLINKLIST pFirst = ( PLINKLIST ) malloc( sizeof ( LNODE ) );
pFirst->pNext = pFirst;
pFirst->nNumber = 1;
pFirst->nPassword = pPassword[0];

// 创建循环链表时, pRear 指向上次刚创建的结点
PLINKLIST pRear = pFirst;

// 采用尾插法创建循环链表
for ( int i = 1; i < nSize; i++ )
{
PLINKLIST p = ( PLINKLIST ) malloc( sizeof ( LNODE ) );
p->nNumber = i + 1;
p->nPassword = pPassword[i];

p->pNext = pRear->pNext;
pRear->pNext = p;

pRear = pRear->pNext;
}

// 若引用的指针变量 pNumber 为 NULL,由本函数为其分配存储空间
if ( NULL == pNumber)
{
pNumber = ( int * ) malloc( nSize * sizeof ( int ) );
}

// 数组 pNumber 的下标
int nSuffix = 0;

// 存储当前报数值
int nCount = 0;

// 循环报数,指针 p 指向当前报数结点的前一个结点,当只剩 1 人时终止循环
PLINKLIST p = pRear;
while ( p->pNext != p )
{
// 当前报数值自增 1
nCount++;

if ( nCount == m )
{ // 若当前报数值等于报数上限值

// 将当前报数值清 0
nCount = 0;

// 更改报数上限值为报数结点的密码( p 指向当前报数结点的前一个结点)
m = p->pNext->nPassword;

// 记录报数结点的编号
pNumber[nSuffix++] = p->pNext->nNumber;

// 删除报数的结点,删除后 p 指向即将报数结点的前一个结点
PLINKLIST t = p->pNext;
p->pNext = t->pNext;
free( t );
t = NULL;
}
else
{ // 若当前报数值不等于报数上限值

// p 指向下一个结点,继续循环报数
p = p->pNext;
}
}

// 此时,只剩 1 人,将其编号存入数组,释放对应结点的存储空间
pNumber[nSuffix] = p->nNumber;
free( p );
p = NULL;

// 返回存储出列顺序的一维数组首地址 pNumber
return pNumber;
}

int main()
{
int n = 0;
printf( "请输入人数:" );
scanf( "%d", &n );

int m = 0;
putchar( '\n' );
printf( "请输入报数上限值:" );
scanf( "%d", &m );
putchar( '\n' );

printf( "请依次输入每个人的密码\n" );
int *psw = ( int * ) malloc( n * sizeof ( int ) );
for ( int i = 0; i < n; i++ )
{
printf( "第 %d 个人的密码:", i + 1 );
scanf( "%d", &psw[i] );
}

int *pNumber = NULL;

printf( "\n出列顺序为:" );
for ( int *p = Joseph( psw, n, m, pNumber ); p < pNumber + n; p++ )
{
printf( "%d ", *p );
}
putchar( '\n' );

free( psw );
psw = NULL;

free( pNumber );
pNumber = NULL;

return 0;
}

下面这个程序是我上学期学数据结构时写的作业,我们学校用的教材是严蔚敏老师的,我写的代码在VC++6.0上编译连接生成可执行程序:
///////////////////////////////////////////////////////////////////
#include
#include
typedefstructlnode
{
intnNumber;//编号
intnPassword;//密码
structlnode*pNext;
}LNODE,*PLINKLIST;
int*Joseph(int*pPassword,intnSize,intm,int*&pNumber)
{
//*************************************************************************
//参数:
//pPassword[in]存储密码的一维数组首地址
//nSize[in]数组pPassword中元素的个数,等于人数
//m[in]报数上限值
//pNumber[out]存储出列顺序的一维数组首地址,若传入的参数为NULL,
//本函数将为其分配存储空间,调用者负责释放本函数分配的存储空间
//返回值:
//若人数大于0,函数返回存储出列顺序的一维数组首地址pNumber
//若人数小于等于0,函数返回NULL
//*************************************************************************
if(nSize<=0)
{//若人数小于等于0,返回NULL
returnNULL;
}
//处理第一个结点,第一个结点的指针域指向其自身
PLINKLISTpFirst=(PLINKLIST)malloc(sizeof(LNODE));
pFirst->pNext=pFirst;
pFirst->nNumber=1;
pFirst->nPassword=pPassword[0];
//创建循环链表时,pRear指向上次刚创建的结点
PLINKLISTpRear=pFirst;
//采用尾插法创建循环链表
for(inti=1;i{
PLINKLISTp=(PLINKLIST)malloc(sizeof(LNODE));
p->nNumber=i+1;
p->nPassword=pPassword[i];
p->pNext=pRear->pNext;
pRear->pNext=p;
pRear=pRear->pNext;
}
//若引用的指针变量pNumber为NULL,由本函数为其分配存储空间
if(NULL==pNumber)
{
pNumber=(int*)malloc(nSize*sizeof(int));
}
//数组pNumber的下标
intnSuffix=0;
//存储当前报数值
intnCount=0;
//循环报数,指针p指向当前报数结点的前一个结点,当只剩1人时终止循环
PLINKLISTp=pRear;
while(p->pNext!=p)
{
//当前报数值自增1
nCount++;
if(nCount==m)
{//若当前报数值等于报数上限值
//将当前报数值清0
nCount=0;
//更改报数上限值为报数结点的密码(p指向当前报数结点的前一个结点)
m=p->pNext->nPassword;
//记录报数结点的编号
pNumber[nSuffix++]=p->pNext->nNumber;
//删除报数的结点,删除后p指向即将报数结点的前一个结点
PLINKLISTt=p->pNext;
p->pNext=t->pNext;
free(t);
t=NULL;
}
else
{//若当前报数值不等于报数上限值
//p指向下一个结点,继续循环报数
p=p->pNext;
}
}
//此时,只剩1人,将其编号存入数组,释放对应结点的存储空间
pNumber[nSuffix]=p->nNumber;
free(p);
p=NULL;
//返回存储出列顺序的一维数组首地址pNumber
returnpNumber;
}
intmain()
{
intn=0;
printf("请输入人数:");
scanf("%d",&n);
intm=0;
putchar('\n');
printf("请输入报数上限值:");
scanf("%d",&m);
putchar('\n');
printf("请依次输入每个人的密码\n");
int*psw=(int*)malloc(n*sizeof(int));
for(inti=0;i{
printf("第%d个人的密码:",i+1);
scanf("%d",&psw[i]);
}
int*pNumber=NULL;
printf("\n出列顺序为:");
for(int*p=Joseph(psw,n,m,pNumber);p{
printf("%d",*p);
}
putchar('\n');
free(psw);
psw=NULL;
free(pNumber);
pNumber=NULL;
return0;
}