新档.txt

数据结构 c语言版 约瑟夫问题 顺序表方法实现

#include<stdio.h>
#include<iostream.h>
#define maxsize 20
typedef struct
{
int number;
int code;
}people;
void main()
{
int n,m,i,j,s;
people a[maxsize];
cout<<"输入总人数：";
cin>>n;
for(i=0;i<n;i++)
{
  a[i].number=i+1;
  cout<<"依次输入密码：";
  cin>>a[i].code;
}
cout<<"输入初始密码：";
cin>>m;
s=0;
for(j=n;j>0;j--)
{
  s=(s+m-1)%j;
  cout<<"第"<<s<<"个人出列"<<endl;
  m=a[s].code;
  for(i=s;i<=j;i++)
  {
   a[i].number=a[i+1].number;
   a[i].code=a[i+1].code;
  }
}
}














#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#define MAX_SIZE    100

typedef int ElemType;
typedef struct{
      ElemType data[MAX_SIZE];
      int length;
}SqList;

void DisplayElem(ElemType x)
{
         printf("%5d",x);
}

/*初始化为空表*/
void InitList(SqList &L)
{
          L.length=0;
}

/*获得顺序表的表长*/
int GetLength(SqList L)
{
          return L.length;
}

/*返回 顺序表中 第i个元素*/ 
int GetElem(SqList L,int i,ElemType &e)
{
    if(i<1 || i>L.length)
        return NULL;
    e=L.data[i-1];   return 1;
}

/*在顺序表中查找元素x,返回其位置，如果不在表中则返回0*/
int LocateElem(SqList L,ElemType x)
{
    int i;
    for(i=1;i<=L.length;i++)
    {
         if(L.data[i-1]==x)
              return i;
    }
    return 0;      /*not found*/
}

/*将元素x插入到顺序表的第i个位置处，如果失败则返回0，否则返回1*/
int InsertElem(SqList &L,ElemType x,int i)
{
    int j;
    if(i<1 || i>L.length+1 || L.length==MAX_SIZE)
       return 0;

    for(j=L.length;j>=i;j--)
         L.data[j]=L.data[j-1];

    L.data[i-1]=x;
    L.length++;

    return 1;
}

/*删除顺序表中的第i个元素*/
int DeleteElem(SqList &L,int i)
{
    int j;
    if(i<1 || i>L.length)
        return 0;

    for(j=i;j<=L.length;j++)
       L.data[j-1]=L.data[j];
    L.length--;
    return 1;
}

/*输出整个顺序表*/
void DisplayList(SqList L)
{
    int i;
    for(i=1;i<=L.length;i++)
       DisplayElem(L.data[i-1]);
}

/*求解约瑟夫环问题，n: 人数， m: 数的个数*/
void jose(int n,int m)
{
   SqList A;
   int i,e,count,ListLength;

   InitList(A);
   for(i=1;i<=n;i++)
      InsertElem(A,i,i);
    
   //DisplayList(A);
   //printf("\n");
   ListLength=n;
   while(ListLength!=1)
   {
       count=0;
       for(i=1;i<=m;i++)  
          count=(count+1)%ListLength;

       if(count==0) count=ListLength;
       DeleteElem(A,count);
       ListLength--;
           
       //DisplayList(A);
       //printf("\n");
  
   }
   DisplayList(A);
}



void main()
{
int m,n;
printf("please input m and n factors of the jose problem:\n");
scanf("%d%d",&m,&n);
jose(m,n);
}