| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1856 人关注过本帖
标题:程序链表约瑟夫问题~~求指教~~~~~~~~~~~~~~~~~~~~~~~~~~~~
只看楼主 加入收藏
pokerLee
Rank: 2
等 级:论坛游民
帖 子:41
专家分:29
注 册:2012-11-4
结帖率:93.33%
收藏
已结贴  问题点数:20 回复次数:2 
程序链表约瑟夫问题~~求指教~~~~~~~~~~~~~~~~~~~~~~~~~~~~
程序如下:
程序代码:
#include
#include
#define MAX_NODE_NUM 100
#define TRUE 1U
#define FALSE 0U

typedef struct NodeType
{
    int id;
    int cipher;
    struct NodeType *next;
} NodeType;

/* 创建单向循环链表 */
static void CreaList(NodeType **, const int);
/* 运行"约瑟夫环"问题 */
static void StatGame(NodeType **, int);
/* 打印循环链表 */
static void PrntList(const NodeType *);
/* 得到一个结点 */
static NodeType *GetNode(const int, const int);
/* 测试链表是否为空, 空为TRUE,非空为FALSE */
static unsigned EmptyList(const NodeType *);

int main(void)
{
    int n, m;
    NodeType *pHead = NULL;
    while (1)
    {
        printf("请输入人数n(最多%d个): ", MAX_NODE_NUM);
        scanf("%d", &n);
        printf("和初始密码m: ");
        scanf("%d", &m);
        if (n > MAX_NODE_NUM)
        {
            printf("人数太多,请重新输入!\n");
            continue;
        }
        else
            break;
    }
    CreaList(&pHead, n);
    printf("\n------------ 循环链表原始打印 -------------\n");
    PrntList(pHead);
    printf("\n-------------删除出队情况打印 -------------\n");
    StatGame(&pHead, m);
}

static void CreaList(NodeType **ppHead, const int n)
{
    int i, iCipher;
    NodeType *pNew, *pCur;
    for (i = 1; i <= n; i++)
    {
        printf("输入第%d个人的密码: ", i);
        scanf("%d", &iCipher);
        pNew = GetNode(i, iCipher);
        if (*ppHead == NULL)
        {
            *ppHead = pCur = pNew;
            pCur->next = *ppHead;
        }
        else
        {
            pNew->next = pCur->next;
            pCur->next = pNew;
            pCur = pNew;
        }
    }
    printf("完成单向循环链表的创建!\n");
}

static void StatGame(NodeType **ppHead, int iCipher)
{
    int iCounter, iFlag = 1;
    NodeType *pPrv, *pCur, *pDel;
    pPrv = pCur = *ppHead;
    /* 将pPrv初始为指向尾结点,为删除作好准备 */
    while (pPrv->next != *ppHead)
        pPrv = pPrv->next;
    while (iFlag)
    {
        for (iCounter = 1; iCounter < iCipher; iCounter++)
        {
            pPrv = pCur;
            pCur = pCur->next;
        }
        if (pPrv == pCur)
            iFlag = 0;
        pDel = pCur; /* 删除pCur指向的结点,即有人出列 */
        pPrv->next = pCur->next;
        pCur = pCur->next;
        iCipher = pDel->cipher;
        printf("第%d个人出列, 密码: %d\n", pDel->id, pDel->cipher);
        free(pDel);
    }
    *ppHead = NULL;
    getchar();
}

static void PrntList(const NodeType *pHead)
{
    const NodeType *pCur = pHead;
    if (EmptyList(pHead))
        return;
    do
    {
        printf("第%d个人, 密码: %d\n", pCur->id, pCur->cipher);
        pCur = pCur->next;
    }
    while (pCur != pHead);
    getchar();
}

static NodeType *GetNode(const int iId, const int iCipher)
{
    NodeType *pNew;
    pNew = (NodeType *)malloc(sizeof(NodeType));
    if(!pNew)
    {
        printf("Error, the memory is not enough!\n");
        exit(-1);
    }
    pNew->id = iId;
    pNew->cipher = iCipher;
    pNew->next = NULL;
    return pNew;
}

static unsigned EmptyList(const NodeType *pHead)
{
    if(!pHead)
    {
        printf("The list is empty!\n");
        return TRUE;
    }
    return FALSE;
}
函数CreaList里面的else{}中pNew赋给了pCur->next后为什么还要赋给pCur?求指教!!
搜索更多相关主题的帖子: include 约瑟夫 
2016-05-10 21:19
xiaomaoshi
Rank: 2
等 级:论坛游民
威 望:1
帖 子:10
专家分:28
注 册:2016-5-10
收藏
得分:20 
pCur永远指向最后一个节点,pCur->next的值指向头节点,只有一个节点时,pCur->next指向自己。

如果此时要在链表尾插入节点,则pNew->next = pCur->next,保证新插入的尾节点pNew的next指向头结点。

pCur->next = pNew这个容易理解,把pNew变成了尾节点,然后把pNew的值赋给pCur,让pCur继续指向最后一个节点。
2016-05-10 21:39
吹水佬
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:451
帖 子:10607
专家分:43186
注 册:2014-5-20
收藏
得分:0 
程序代码:
/*
    约瑟夫问题
        据说著名犹太历史学家Josephus有过以下的故事:在罗马人占领乔塔帕特
    后,39个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死
    也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个
    人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到
    所有人都自杀身亡为止。然而Josephus和他的朋友并不想遵从,Josephus要他
    的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了
    这场死亡游戏。
        问题:如何算出排在第16个与第31个位置可逃过一死,也就是说最后剩下
    的两人就是Josephus和他的朋友。
        “倒推算法”有可能是最简单的计算方法。
        假设:
            n=41, m=3 
            最后剩下1个:1          将死掉的先复活,再倒数报数m次,每次排位过程: 
            最后剩下2个:2,1            2,1      1,2      2,1 
            最后剩下3个:2,1,3          3,2,1    1,3,2    2,1,3 
            最后剩下4个:1,3,4,2        4,2,1,3  3,4,2,1  1,3,4,2 
            直到所有都复活:
            28,6,41,4,27,40,18,12,39,26,8,38,17,25,37,2(16),11,36,24,16,35,5,23,34,7,15,33,22,10,32,1(31),21,31,14,3,30,20,9,29,13,19
            可见最后剩下的2个人是排在第16个与第31个位置。 
*/

#include "stdio.h"  

main()
{  
    int n=41, m=3;
    int a[n];
        // 按最后剩下的人数编号
    for (int i=0; i<n; i++)
    {
        a[i] = i+1;
    }
        // 从最后剩下的一个人起逐个复活
    for (int i=0; i<n; i++)
    {
            // 倒数报数m次
        for (int j=0; j<m; j++)
        {
            int tmp = a[i];
            for (int k=i; k>0; k--)
            {
                a[k] = a[k-1];
            }
            a[0] = tmp;
        }
            // 每次排位过程   
        for (int k=0; k<=i; k++)
        {
            if ((a[k] != 1) && (a[k] != 2))
                printf("%d,", a[k]);
            else
                printf("%d(%d),", a[k], k+1);   //显示最后剩下的2个人排位
        }
        printf("\n\n");
    }
}


[此贴子已经被作者于2016-5-10 23:23编辑过]

2016-05-10 23:18
快速回复:程序链表约瑟夫问题~~求指教~~~~~~~~~~~~~~~~~~~~~~~~~~~~
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.034290 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved