设为首页 加入收藏

TOP

利用C语言实现自杀环---约瑟夫环
2017-11-13 14:54:59 】 浏览:18
Tags:利用 语言 实现 自杀 --- 约瑟夫

运行环境: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语言中强制类型转换目的、基本格..

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

最新文章

热门文章

C 语言

C++基础

windows编程基础

linux编程基础

C/C++面试题目