单循环链表解决约瑟夫环问题
这几天为了准备笔试忙着复习C语言，决定把当时学C时的一些经典问题再温习一下，当时啊，学的稀里糊涂的，呵呵，现在回头来仔细写一写代码，就算是纪念当时的个性十足的赵老师了吧！约瑟夫问题的：编号为1，2，....,N的N个人按顺时针方向围坐一圈,每人持有一个密码(正整数)，一开始任选一个正整数作为报数上限值M，从第一个人开始按顺时针方向自1开始顺序报数，报到M时停止报数。报M的人出列，将他的密码作为新的M值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。
解决思路还是很简单的，主要是要会熟练运用单循环链表的数据结构，通过单循环链表模拟围坐的一圈人，然后根据相应的密码进行报数，然后删除相应的链表节点。下面是C代码：
<div class="dp-highlighter"><div class="bar">
[*]#include <stdio.h>
[*] #include <stdlib.h>
[*] #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;
[*]}
页:
[1]