运行环境: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是多么聪明的一个人啊!