josephus_linkedlist.cpp

回顾基础

//【例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 

*/