C语言单链表实现约瑟夫环

2018-12-31
次阅读
2 分钟阅读时长

前言

前两天朋友给我发来一个题目,问我能不能用C语言链表实现。

13个人围成一圈,从第1个人开始顺序报号1,2,3。凡报到“3”者退出圈子,找出最后留在圈子中的人原来的序号。要求用链表实现。

看了题目以后发现其实是 约瑟夫环,是一个数学应用问题。

约瑟夫环

约瑟夫环 又称为 约瑟夫问题丢手绢问题

一群人围在一起坐成环状,从某个编号开始报数,数到某个数的时候,此人出列,下一个人重新报数,一直循环,直到所有人出列,约瑟夫环结束。

例如有序号分别为 1、2、3 的人围成一个圈, 从 1 开始报数,数到 3 的淘汰。

第一轮,淘汰:3,剩余 1、2、

第二轮,淘汰:1,剩余 2

2 号就是最后留在圈子中的人。

代码实现

代码中用了链式队列的思想来模拟报数,头部取出,尾部插入。

#include <stdio.h>
#include <malloc.h>

/**
 * 结构体
 */
struct PerNode {
    // 序号
    int m_iNumber;
    // 下一个元素的指针
    struct PerNode * m_pNextPer;
};

/*
**函数功能:采用malloc函数动态地创建并初始化一个单向链表
**入口参数:iLstLen为拟创建链表的结点数
**返回值:新创建链表的头结点的指针
*/
struct PerNode * crtPrLst(int iLstLen) {
    // 生成头节点
    struct PerNode *headNode = malloc(sizeof(struct PerNode));

    struct PerNode * perNode = headNode;
    perNode->m_pNextPer = NULL;

    // 用于存放临时生成的元素
    struct PerNode *temp;

    // 创建链表
    for (int i = iLstLen; i >= 1 ; i--) {
        temp = malloc(sizeof(struct PerNode));
        temp->m_iNumber = i;
        temp->m_pNextPer = perNode->m_pNextPer;
        perNode->m_pNextPer = temp;
    }

    return headNode;
}

/**
 * 删除并返回链表的第一个元素
 * @param pTmp
 * @return
 */
struct PerNode * pop(struct PerNode * pTmp) {
    if (pTmp == NULL) {
        return NULL;
    }

    // 取出第一个元素
    struct PerNode * temp = pTmp->m_pNextPer;

    if (temp == NULL) {
        return NULL;
    }

    // 移除第一个元素
    pTmp->m_pNextPer = temp->m_pNextPer;

    return temp;
}

/**
 * 向链表的末尾添加一个元素
 * @param pTmp
 * @param value
 */
void push(struct PerNode * pTmp, int value) {
    struct PerNode * l = pTmp->m_pNextPer;

    // 遍历到最后一个元素
    while (l != NULL && l->m_pNextPer != NULL) {
        l = l->m_pNextPer;
    }

    // 新建一个元素
    struct PerNode * node = malloc(sizeof(struct PerNode));
    node->m_iNumber = value;
    node->m_pNextPer = NULL;

    // 如果最后一个元素不为空则插入到它的后面
    if (l != NULL) {
        l->m_pNextPer = node;
    }
}

struct PerNode * josephus(struct PerNode *pTmp) {
    // 计数器,用来报数
    int i = 0;
    // 最后留在圈子中的元素
    struct PerNode * p;

    while (1) {
        // 模拟报数
        i++;
        // 取出一个元素
        struct PerNode * node = pop(*&pTmp);
        // 如果元素为 NULL,则说明没有人了
        if (node == NULL) {
            break;
        }

        // 如果这个人报数不是 3,则放回链表尾部
        if (i % 3 != 0) {
            push(*&pTmp, node->m_iNumber);
        }

        // 记录当前的元素
        p = node;
    }

    return p;
}

/**
 * 打印链表
 * @param l
 */
void printLink(struct PerNode * l)
{
    while (l != NULL) {
        printf("%d \n", l->m_iNumber);
        l = l->m_pNextPer;
    }

    printf("---------\n");
}

int main() {
    // 创建一个长度为13的链表
    struct PerNode *pHead = crtPrLst(13);
    // 找出最后在圈子中的人
    pHead = josephus(pHead);
    // 打印它的序号
    printf("%d \n", pHead->m_iNumber);
    
    return 0;
}

2018 年最后一篇文章。

本文作者:她和她的猫
本文地址https://her-cat.com/posts/2018/12/31/realization-of-josephus-ring-with-c-language-single-chain-table/
版权声明:本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!