注册 登录
编程论坛 数据结构与算法

高手过来帮帮忙哦!

sunqianao 发布于 2010-05-19 17:53, 457 次点击
3.约瑟夫环.
[问题描述]设有n个人围坐一圈,现从某个人开始报数,数到m的人出列,接着从下一个人开始重新开始报数,数到m的人又出列,如次下去,直到所有的人都出列为止。试设计确定他们出列的顺序的程序
1)在顺序存储结构上实现以上过程。
2)在循环链表上实现以上过程。
3 回复
#2
2010-05-19 21:41
顺序表的方法,我总想不出多好的,见谅哈.
#include <stdio.h>
#define maxsize 100
int main()
{
    int i,k,j;
    int array[maxsize];
    int m,n;
    j=0;k=0;
    scanf("%d",&m);
    for(i=0;i<m;i++)
    array[i]=i+1;
    scanf("%d",&n);
    for(i=0;k<m;i=(i+1)%m,j++)
    {
        while(array[i]==0) i=(i+1)%m;
        if(j==n-1)
        {
            printf("%d ",array[i]);
            array[i]=0;

            k++;
            j=0;i=(i+1)%m;
            if(k<m) while(array[i]==0) i=(i+1)%m;
        }

    }
    return 0;
}

链表:
#include <stdio.h>
#include <malloc.h>

typedef int ElemType;
typedef struct node
{
    ElemType data;
    struct node *next;
}LNode,*LinkList;

LinkList Creatlist(ElemType m)
{
    LinkList L,p,q;
    ElemType i;
    L=(LinkList)malloc(sizeof(LNode));
    L->data=1;
    p=L;
    for(i=1;i<m;i++)
    {
        q=(LinkList)malloc(sizeof(LNode));
        q->data=i+1;
        p->next=q;p=q;
    }
    p->next=L;
    return L;
}


void Joseph(LinkList L,int n)
{
    LinkList p,q;
    int i;
    i=0;
    p=(LinkList)malloc(sizeof(LNode));
    p->next=L;q=L;
    while(p->next!=p)
    {
        p=p->next;q=q->next;
        i++;
        if(i==n-1)
        {
            p->next=q->next;
            printf("%d ",q->data);
            free(q);
            q=p->next;
            i=0;
        }
    }
    printf("%d ",p->data);
    printf("\n");
}

void printlist(LinkList L)
{
    LinkList p;
    p=L;
    printf("%d ",p->data);
    p=p->next;
    while(p!=L)
    {
        printf("%d ",p->data);
        p=p->next;
    }
    printf("\n");
}


int main()
{
    int m;int n;
    LinkList L;
    scanf("%d",&m);
    L=Creatlist(m);
    printlist(L);
    scanf("%d",&n);
    Joseph(L,n);
    return 0;
}
#3
sunqianao2010-05-19 21:54
辛苦了!谢谢哈!
#4
2010-05-19 22:13
以下是引用sunqianao在2010-5-19 21:54:48的发言:

辛苦了!谢谢哈!

希望能幫到你
1