求大神编个约瑟夫环的问题，菜鸟能看懂的~ - C语言论坛

cwt648067724

等　级：新手上路
帖　子：5
专家分：0
注　册：2014-4-22

第 2 楼

得分:0

注：解决约瑟夫环问题的函数，编写时要注意:

1. 根据密码m点人数实际上只需要点到第m-1人，才好让第m人出列。

2.对循环链表跑圈点数时，实际上头结点不能算人数。可以通过求余减少跑圈人数。如果是双向循环，还可以考虑逆向点数。

3.找到第m-1人后，next如果是头结点，说明要出列的是首元，不能让头结点出列了。

//=====================================people.h
struct People
{
int id;
int password;
};

//相关操作原型

//=====================================people.cpp
//对People类型数据，实现基本的输入输出
void input(People *px)
{
}
void output(People *px)
{
}

//或通过重载操作符：>>和<<，实现基本的输入输出
ostream & operator << ( ostream &out, const People &x )
{
}

istream & operator >> ( istream &in, People &x )
{
}

//链表数据结构的实现,

//===========================================list.h
typedef
struct node
{
ElemType data;
struct node *next;
} Node;

typedef
struct
{
Node *head; //头指针
int count; //元素个数
} List;

//相关操作原型

//============================================list.cpp
//链表的基本操作
//1.初始化

//2.添加元素

//3.删除元素

//4.遍历输出?

//============================================main.cpp

#include "people.h"

typedef People ElemType; //确定链表容器真正容纳的数据类型

#include "list.h"

int main()
{
//创建链表
//根据约瑟夫问题原则，利用链表基本操作，解决问题。可做出独立函数

}

2014-04-22 19:59

Susake

来　自：女儿国的隔壁
等　级：贵宾
威　望：23
帖　子：2288
专家分：6481
注　册：2012-12-14

第 4 楼

得分:10

以前写的

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
    int data;
    struct Node *next;
}Node, *LinkList;
void Init_LinkList(LinkList &L)
{
    L = (LinkList)malloc(sizeof(Node));
    L->next = NULL;
}
void back_Input_LinkList(LinkList &L, int n)
{
    Node *p, *r = L;
    for (int i = 1; i <= n; i++)
    {
        p = (Node *)malloc(sizeof(Node));
        p->data = i;
        r->next = p;
        r = p;
    }
    r->next = L -> next;
}
int Joseph(LinkList &L, int n, int m)
{
    Node *p = L, *q;
    int i = 0, j = 0;
    while (p)
    {
        q = p;
        i++;
        if (j == n)
            return p->data;
        else if (i == m)
        {
            i = 0;
            j++;
            p = p->next;
            q->next = p -> next;
        }
        else
            p = p->next;
    }
}
int main(int argc, char *argv[])
{
    LinkList L;
    int n, m;
    while (scanf("%d%d", &n, &m) != EOF)
    {
        Init_LinkList(L);
        back_Input_LinkList(L, n);
        printf("%dn", Joseph(L, n, m));
    }
    return 0;
}

仰望星空...........不忘初心!

2014-04-22 19:59