【C】约瑟夫环的双向链表解法

usr

约瑟夫环问题起源于一个犹太故事。
传说罗马人攻占了乔塔帕特，41个人藏在山洞中躲过了这场浩劫。这41人中包括历史学家Josephus约瑟夫和他的一个朋友。剩余的39人为了表示绝不屈服于罗马人于是决定集体自杀。所有这41人围成圈由第一个人开始顺时针报数，每报数为3的人就立刻自杀，然后再由下一个人重新开始报数，仍然是每报数为3的人就立刻自杀，直到所有人都死亡为止。
约瑟夫和他的朋友并不想自杀。于是约瑟夫想到了一个计策，他们两人同样参与到自杀方案中，但是最后却躲过了自杀。
下面的程序给出了约瑟夫环的解法，注意该程序需要StoneValley库的支持：

1. #include <stdio.h>
   
2. #include "../src/svstring.h"
   
3. 
   
4. // Function: cbftvs_print_list
   
5. // Desc:     Print item number in linked-list.
   
6. // Param:    pitem: pointer to each node in a list. param: N/A.
   
7. // Return:   CBF_CONTINUE only.
   
8. int cbftvs_print_list(void * pitem, size_t param)
   
9. {
   
10.         printf("%ld, ", *(long *)((P_NODE_D)pitem)->pdata);
    
11.         DWC4100(param);
    
12.         return CBF_CONTINUE;
    
13. }
    
14. 
    
15. // Function: main
    
16. // Desc:     Program entry.
    
17. // Param:    N/A.
    
18. // Return:   0: no error. 1: allocation failure.
    
19. int main(void)
    
20. {
    
21.         char c;
    
22.         long i, j;
    
23.         LIST_D jring;
    
24.         P_NODE_D pnew, pnode;
    
25.         const char * sfx[] = { "m", "ms", "is", "are" };
    
26.         strInitLinkedListDC(&jring);
    
27.         pnode = jring;
    
28.         printf("# A solution to Josephus's ring. <"); svPrintVersion(); printf("> #\n");
    
29. Lbl_Start:
    
30.         do
    
31.         {
    
32.                 printf("How many items will be there in a ring? ");
    
33.                 scanf("%ld", &j);
    
34.         }
    
35.         while (j < 1);
    
36.         for (i = 1; i <= j; ++i)
    
37.         {
    
38.                 if (NULL == (pnew = strCreateNodeD(&i, sizeof(long))))
    
39.                 {
    
40.                         puts("Error! Allocation failure while building ring.");
    
41.                         strFreeLinkedListDC(&jring, FALSE);
    
42.                         return 1; /* Allocation failure. */
    
43.                 }
    
44.                 if (NULL != pnode)
    
45.                 {
    
46.                         pnode->ppnode[NEXT] = pnew;
    
47.                         pnew->ppnode[PREV] = pnode;
    
48.                 }
    
49.                 else
    
50.                         jring = pnew;
    
51.                 pnode = pnew;
    
52.         }
    
53.         /* Make a ring. */
    
54.         pnode->ppnode[NEXT] = jring;
    
55.         jring->ppnode[PREV] = pnode;
    
56.         do
    
57.         {
    
58.                 printf("\tNow, there %s %ld ite%s in the ring.\nWhich number would you like \
    
59. to choose to delete ite%s sequentially? ", sfx[(j > 1) + 2], j, sfx[j > 1], sfx[j > 1]);
    
60.                 scanf("%ld", &i);
    
61.         }
    
62.         while (i < 1);
    
63.         for ( ;; )
    
64.         {
    
65.                 pnode = strLocateItemDC_R(jring, i - 1);
    
66.                 if (jring != pnode)
    
67.                 {
    
68.                         jring = pnode->ppnode[NEXT];
    
69.                         strRemoveItemLinkedListDC(pnode);
    
70.                         printf("\tRemove: %ld\n", *(long *)pnode->pdata);
    
71.                         strDeleteNodeD(pnode);
    
72.                 }
    
73.                 else
    
74.                         break;
    
75.         }
    
76.         if (NULL != pnode)
    
77.         {
    
78.                 printf("The rest of ite%s in the ring %s labeled with: ",
    
79.                 sfx[jring != jring->ppnode[NEXT]], sfx[(jring != jring->ppnode[NEXT]) + 2]);
    
80.                 strTraverseLinkedListDC_X(jring, NULL, cbftvs_print_list, 0, FALSE); puts("\b\b.");
    
81.         }
    
82.         strFreeLinkedListDC(&jring, FALSE);
    
83.         pnode = NULL;
    
84.         do
    
85.         {
    
86.                 fflush(stdin);
    
87.                 printf("Would you like to continue playing(Y/n)? ");
    
88.                 scanf("%c", &c);
    
89.                 switch (c)
    
90.                 {
    
91.                 case 'Y': case 'y': goto Lbl_Start;
    
92.                 case 'N': case 'n': return 0;
    
93.                 }
    
94.         }
    
95.         while (c != 'Y' && c != 'y' && c != 'N' && c != 'n');
    
96.         return 0;
    
97. }
    

复制代码

程序运行结果如下：

该程序的核心是strLocateItemDC_R函数，使用该函数可以向前、向后定位循环双向链表上的任意一个节点。