// hxx修改的部分：）
template <typename T> LinkList<T>::LinkList()
{
    num = 0;
    head = cur_node = NULL;
}

template <typename T> LinkList<T>::LinkList(const T*t,int n)
{
    Node<T> *p;
    head = NULL;
    for(int i=n-1; i>=0; i--)
    {
        p = new Node<T>(t[i]);
        p->next = head;
        head = p;
    }
    num = n;
    cur_node = head;
}

template <typename T>
LinkList<T>::LinkList(const LinkList<T> &list)
{
    Node<T> *p, *pTail, *temp=list.head;
    if((num=list.num)==0)
    {
        head = cur_node = NULL;
        return;
    }
    head = pTail = new Node<T>(list.head->data);
    if(list.head == list.cur_node) cur_node = head;
    for(int i=1; i<num; i++)
    {
        temp = temp->next;
        p = new Node<T>(temp->data);
        if(temp == list.cur_node) cur_node = p;
        pTail->next = p;
        pTail = p;
    }
    pTail->next = NULL;
}

template <typename T> LinkList<T>::~LinkList()
{
    FreeList();
    cout << "析构一条链表。" << endl;
}

template <typename T>
typename LinkList<T>::Node<T> *LinkList<T>::GoTop()
{
    return cur_node = head;
}

template <typename T>
typename LinkList<T>::Node<T> *LinkList<T>::Go(int n)
{
    if((cur_node=head) == NULL) return cur_node;
    for(int i=0; i<n && cur_node!=NULL; i++)
        cur_node = cur_node->next;
    return cur_node;
}

template <typename T>
typename LinkList<T>::Node<T> *LinkList<T>::GoBottom()
{
    if((cur_node=head) == NULL) return cur_node;
    while(cur_node->next!=NULL)
        cur_node = cur_node->next;
    return cur_node;
}

template <typename T>
typename LinkList<T>::Node<T> *LinkList<T>::Skip(int n)
{
    int i;
    if(n > 0)
    {
        for(i=0; i<n && cur_node!=NULL; i++)
            cur_node = cur_node->next;
    }
    else if(n < 0)
    {
        int m = CurPos() + n;
        cur_node = (m < 0) ? NULL : Go(m);
    }
    return cur_node;
}

template <typename T> typename LinkList<T>::Node<T> *
LinkList<T>::Locate(const T &t, bool restart)
{
    static Node<T> *p = head;        // 局部静态指针变量

    if(head==NULL) return cur_node=NULL;
    if(restart) p = head;
    while(p!=NULL && p->data != t)
        p = p->next;
    cur_node = p;
    if(p!=NULL) p = p->next;
    return cur_node;
}

template <typename T>
typename LinkList<T>::Node<T> *LinkList<T>::CurNode() const
{
    return cur_node;
}

template <typename T> void LinkList<T>::DeleteCurNode()
{
    if(cur_node==NULL) return;
    Node<T> *pGuard = head;
    while(pGuard->next!=NULL && pGuard->next!=cur_node)
        pGuard = pGuard->next;
    if(cur_node==head)
    {
        num--;
        head = head->next;
        if (head==cur_node) head = NULL;
        delete cur_node;
        cur_node = head;
        if (pGuard != NULL && head != NULL) pGuard->next = head;
        return;
    }
    if(pGuard->next != NULL)
    {
        num--;
        pGuard->next = cur_node->next;
        delete cur_node;
        cur_node = pGuard->next;
    }
}

template <typename T> void LinkList<T>::FreeList()
{
    Node<T> *p;
    while(head!=NULL)
    {
        p = head;
        head = head->next;
        if (head==p)head=NULL;
        delete p;
    }
    cur_node = NULL;
    num = 0;
}

template <typename T>
void LinkList<T>::ShowList(int LinePerNode) const
{
    if(LinePerNode==0) cout << "head";
    Node<T> *p=head;
    while ( p!=NULL )
    {
        if(LinePerNode==0)
            cout << (p==cur_node ? " ★ " : " → ")
                 << p->data;
        else
            cout << (p==cur_node ? "★" : "  ")
                 << p->data << endl;
        p=p->next;
        if (p==head)break;                            // 防止出现环状数据
    }
    if(LinePerNode==0) cout << " → NULL" << endl;
}

//cpp部分
int Josephus(int num , int interval)
{
    LinkList<int> Jose;
    int i,j,win;
    for(i=1;i<=num;i++)
        Jose.Append(i);
    cout<<" 初始状态 ";
    Jose.CircleLink();                    // 之前版本还没数据就生成环形链~~~~
    for(Jose.GoTop();Jose.NumNodes()>1; )
    {
        Jose.ShowList();
        getch();    
        for(j=1;j<interval;j++)
        {
            Jose.Skip();
        }
        Jose.ShowCurData();
        cout<<" 号出圈.";
        Jose.DeleteCurNode();
    }
    Jose.ShowList();
    win=Jose.CurData();
    return win;
}