这几天为了准备笔试忙着复习C语言,决定把当时学C时的一些经典问题再温习一下,当时啊,学的稀里糊涂的,呵呵,现在回头来仔细写一写代码,就算是纪念当时的个性十足的赵老师了吧!
约瑟夫问题的:编号为1,2,....,N的N个人按顺时针方向围坐一圈,每人持有一个密码(正整数),一开始任选一个正整数作为报数上限值M,从第一个人开始按顺时针方向自1开始顺序报数,报到M时停止报数。报M的人出列,将他的密码作为新的M值,从他在顺时针方向上的下一个人开始重新从1报数,如此下去,直至所有人全部出列为止。试设计一个程序求出出列顺序。
解决思路还是很简单的,主要是要会熟练运用单循环链表的数据结构,通过单循环链表模拟围坐的一圈人,然后根据相应的密码进行报数,然后删除相应的链表节点。下面是C代码:
- #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);
-
- 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;
-
- 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;
- 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;
- }
分享到:
相关推荐
用单链表解决约瑟夫环问题,数据结构实验报告。约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人...
VC++2012编程演练数据结构《2》单循环链表与约瑟夫问题
约瑟夫环的问题描述 问题描述:编号为1,2… n的n个人按顺时针方向围坐一圈,每人持有...利用单循环链表作为存储结构模拟此过程; ⑵.键盘输入总人数、初始报数上限值m及各人密码; ⑶.按照出列顺序输出各人的编号。
单链表解决约瑟夫环问题
约瑟夫环问题描述:n个人围成一圈报数(每个人用编号1—n表示即可),从1号开始,每数到m出圈一个,然后再从下一个开始重新报数,直至所有人全部出圈为止。试设计一个程序求出圈顺序,要求n、m由键盘输入。
用C++做的单循环链表简单表示了约瑟夫问题
数据结构问题,编程实现约瑟夫环,原题是严淑敏的《数据结构C语言版题集》实习一的第二题
程序源代码: #include typedef struct Node { int num; int pasword;
单链表只有向后结点,当单链表的尾链表不指向NULL,而是指向头结点时候,形成了一个环,成为单循环链表,简称循环链表。当它是空表,向后结点就只想了自己,这也是它与单链表的主要差异,判断node->next是否等于head...
有20个人排成一个圈,从第1个人开始循环报数,报到3或者3的倍数的离开圈子; 请编程计算并输出最后剩下三个人时是哪几个人。
NULL 博文链接:https://128kj.iteye.com/blog/1613674
本程序主要是以建立单循环链表的形式,利用单向循环链表存储结构模拟此过程,建立起一个约瑟夫环,然后根据之前创立的结点,输入结点里的一些数据,程序有主函数开始,首先,提示输入创建约瑟夫环环数以及每个环上所...
一个旅行社要从n个旅客中选出一名旅客,为他提供免费的环球旅行服务。旅行社安排这些旅客围成一个圆圈,从帽子中取出一张纸条,用上面写的正整数m()作为报数值。游戏进行时,从第s个人...其中数据结构采用单循环链表。
约瑟夫环,利用单循环链表存储结构模拟此过程
约瑟夫环控制台程序,C/C++,Microsoft Visual Studio 2010工程,简单高效
问题描述:约瑟夫生者死者游戏:30个旅客同乘一条船,因为严重超载,非常危险,大家一致同意将一半的旅客投入海中。30个旅客围成一圈,由第一个人开始,依次报数,数到第9人,便...试用数组和单循环链表来解决本问题。
用单循环链表实现的约瑟夫环C++源代码,有详细注释。
从1至m对带头结点的单循环链表循环计数,到m时,输出该结点的编号值,将该结点的密码作为新的m值,再从该结点的下一个结点起重新自1起循环计数;如此下去,直到单循环链表空时循环过程结束。输入的形式为一个以"回车...
自己写的约瑟夫环C++小程序 用的数据结构是单循环链表 输入约瑟夫环的长度-1
数据结构实验《约瑟夫环问题》 #include"iostream.h" #define N 100 typedef struct node//采用数据类型定义 { int number; struct node *next; }Lnode,*LinkList; LinkList InitRingList(int n)//建立一个单循环...