频道栏目
首页 > 程序开发 > 软件开发 > C语言 > 正文
利用C语言实现自杀环---约瑟夫环
2017-11-11 15:09:28      个评论    来源:dangzhangjing97的博客  
收藏   我要投稿

运行环境:win10,VS2013

约瑟夫环是一个数学的应用问题:已知n个人(以编号1,2,3…n分别表示)围坐在一张圆桌周围。从编号为k的人开始从1报数,数到M的那个人出列;他的下一个人又从1开始报数,数到M的那个人又出列;依此规律重复下去,直到剩余一个人

这里写图片描述

这里写图片描述

这里写图片描述

这里写图片描述

LinkList.c

#include
#include
#include
typedef int DataType;//定义数据类型
//节点的构造
typedef struct Node
{
    DataType data;
    struct Node*pNext;
}Node,*PNode;
//初始化
void InitLinkList(PNode* pHead)
{
    assert(pHead);//断言
    (*pHead) = NULL;
}
//构造新节点
PNode BuyNode(DataType x)
{
    PNode pCur = (PNode)malloc(sizeof(Node));
    if (NULL == pCur)
        return NULL;
    else
    {
        pCur->data = x;
        pCur->pNext = NULL;
        return pCur;
    }
}
//打印链表
void PrintLinkList(PNode pHead)
{
    assert(pHead);
    if (NULL == pHead)
        printf("NULL");
    else
    {
        while (pHead)
        {
            printf("%d--->", pHead->data);
            pHead = pHead->pNext;
        }
        printf("NULL");
    }
    printf("\n");
}
//尾插
PNode PushBack(PNode* pHead,DataType x)
{
    assert(pHead);
    PNode pTail = NULL;
    PNode pCur = BuyNode(x);//调用BuyNode()函数,对给出的data构造节点
    if (NULL == (*pHead))
    {
        (*pHead) = pCur;
    }
    else
    {
        pTail = (*pHead);
        while (pTail->pNext)
        {
            pTail = pTail->pNext;
        }
        pTail->pNext = pCur;
    }
    return pHead;
}
//约瑟夫环函数
PNode JosephCircle(PNode pHead, size_t M)
{
    PNode pCur = pHead;
    PNode pDel = NULL;
    assert(pHead);
    //如果链表是空链表或者只有一个节点,都返回头指针
    if (NULL == pHead||NULL==pHead->pNext)
        return pHead;
    //给链表构环
    while (pCur->pNext)
    {
        pCur = pCur->pNext;
    }
    pCur->pNext = pHead;
    pCur = pHead;
    //循环删除节点
    while (pCur != pCur->pNext)
    {
        int count = M;//报数为count
        while (--count)
        {
            pCur = pCur->pNext;
        }
        //替换法删除节点(通过删除需要删除节点的下一个节点)
        pDel = pCur->pNext;
        pCur->data = pDel->data;
        pCur->pNext = pDel->pNext;
        free(pDel);
        pDel = NULL;
    }
    //解环
    pCur->pNext = NULL;
    return pCur;
}

test.c

void test()
{
    struct Node* pHead;
    struct Node* p;
    InitLinkList(&pHead);
    PushBack(&pHead, 2);
    PushBack(&pHead, 3);
    PushBack(&pHead, 4);
    PushBack(&pHead, 5);
    PushBack(&pHead, 6);
    PushBack(&pHead, 7);
    PushBack(&pHead, 8);
    PushBack(&pHead, 9);
    PrintLinkList(pHead);//打印链表
    p=JosephCircle(pHead, 3);
    PrintLinkList(p);
}
int main()
{
    test();
    system("pause");
    return 0;
}

运行结果:

这里写图片描述

ps:由此可见,Josephus是多么聪明的一个人啊!

点击复制链接 与好友分享!回本站首页
上一篇:C语言中强制类型转换目的、基本格式、C中变量的本质含义
下一篇:最后一页
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站