【C】约瑟夫环的双向链表解法
本帖最后由 new_starter 于 2020-11-1 22:01 编辑约瑟夫环问题起源于一个犹太故事。
传说罗马人攻占了乔塔帕特，41个人藏在山洞中躲过了这场浩劫。这41人中包括历史学家Josephus约瑟夫和他的一个朋友。剩余的39人为了表示绝不屈服于罗马人于是决定集体自杀。所有这41人围成圈由第一个人开始顺时针报数，每报数为3的人就立刻自杀，然后再由下一个人重新开始报数，仍然是每报数为3的人就立刻自杀，直到所有人都死亡为止。
约瑟夫和他的朋友并不想自杀。于是约瑟夫想到了一个计策，他们两人同样参与到自杀方案中，但是最后却躲过了自杀。
下面的程序给出了约瑟夫环的解法，注意该程序需要StoneValley库的支持：
#include <stdio.h>
#include "../src/svstring.h"
// Function: cbftvs_print_list
// Desc: Print item number in linked-list.
// Param: pitem: pointer to each node in a list. param: N/A.
// Return: CBF_CONTINUE only.
int cbftvs_print_list(void * pitem, size_t param)
{
printf("%ld, ", *(long *)((P_NODE_D)pitem)->pdata);
DWC4100(param);
return CBF_CONTINUE;
}
// Function: main
// Desc: Program entry.
// Param: N/A.
// Return: 0: no error. 1: allocation failure.
int main(void)
{
char c;
long i, j;
LIST_D jring;
P_NODE_D pnew, pnode;
const char * sfx[] = { "m", "ms", "is", "are" };
strInitLinkedListDC(&jring);
pnode = jring;
printf("# A solution to Josephus's ring. <"); svPrintVersion(); printf("> #\n");
Lbl_Start:
do
{
printf("How many items will be there in a ring? ");
scanf("%ld", &j);
}
while (j < 1);
for (i = 1; i <= j; ++i)
{
if (NULL == (pnew = strCreateNodeD(&i, sizeof(long))))
{
puts("Error! Allocation failure while building ring.");
strFreeLinkedListDC(&jring, FALSE);
return 1; /* Allocation failure. */
}
if (NULL != pnode)
{
pnode->ppnode = pnew;
pnew->ppnode = pnode;
}
else
jring = pnew;
pnode = pnew;
}
/* Make a ring. */
pnode->ppnode = jring;
jring->ppnode = pnode;
do
{
printf("\tNow, there %s %ld ite%s in the ring.\nWhich number would you like \
to choose to delete ite%s sequentially? ", sfx[(j > 1) + 2], j, sfx, sfx);
scanf("%ld", &i);
}
while (i < 1);
for ( ;; )
{
pnode = strLocateItemDC_R(jring, i - 1);
if (jring != pnode)
{
jring = pnode->ppnode;
strRemoveItemLinkedListDC(pnode);
printf("\tRemove: %ld\n", *(long *)pnode->pdata);
strDeleteNodeD(pnode);
}
else
break;
}
if (NULL != pnode)
{
printf("The rest of ite%s in the ring %s labeled with: ",
sfx], sfx[(jring != jring->ppnode) + 2]);
strTraverseLinkedListDC_X(jring, NULL, cbftvs_print_list, 0, FALSE); puts("\b\b.");
}
strFreeLinkedListDC(&jring, FALSE);
pnode = NULL;
do
{
fflush(stdin);
printf("Would you like to continue playing(Y/n)? ");
scanf("%c", &c);
switch (c)
{
case 'Y': case 'y': goto Lbl_Start;
case 'N': case 'n': return 0;
}
}
while (c != 'Y' && c != 'y' && c != 'N' && c != 'n');
return 0;
}
程序运行结果如下：
该程序的核心是strLocateItemDC_R函数，使用该函数可以向前、向后定位循环双向链表上的任意一个节点。
页:
[1]