//【例2.1】使用單鏈表求解約瑟夫環問題。

//#include "SinglyLinkedList.h"                              //單鏈表類
#include "HSLinkedList.h"                                  //帶頭結點的單鏈表類
//#include "CirHSLinkedList.h"                                  //帶頭結點的循環單鏈表類

void josephus(int number, int start, int distance)         //求解約瑟夫環，算法同順序表
{                                                          //參數指定環長度、起始位置、計數
//    SinglyLinkedList<char> jose;                           //創建單鏈表
    HSLinkedList<char> jose; 
//    CirHSLinkedList<char> jose;
    int i;
    for (i=number-1; i>=0; i--)
        jose.insert(0, 'A'+i);                             //在單鏈表頭插入元素
    cout<<"約瑟夫環("<<number<<","<<start<<","<<distance<<")，"<<jose;
/*
    cout<<"查找E：";
    Node<char> *find=jose.search('E');              //查找
    if (find!=NULL) 
        cout<<find->data<<"\n";
    cout<<"刪除E：";
    if (jose.remove('E'))
       jose.print();                                          //輸出約瑟夫環中所有元素
*/
    i = start;                                             //計數起始位置
    while (jose.length()>1)                                //多于一個對象時循環 
    {
        i = (i+distance-1) % jose.length();                //計數時按循環規律變化
        char old;
        if (jose.remove(i, old))                           //刪除指定位置元素
            cout<<"刪除"<<old<<"，";
        cout<<jose;
    }
    cout<<"被赦免者是"<<jose.get(0)<<"\n";
}
int main()
{
    josephus(5,0,2);
    return 0;
}

/*
程序運行結果如下：
約瑟夫環(5,0,2)，list: (A, B, C, D, E) 
刪除B，list: (A, C, D, E)
刪除D，list: (A, C, E)
刪除A，list: (C, E)
刪除E，list: (C)
被赦免者是C 

*/