循环链表和约瑟夫环

循环链表和约瑟夫环

循环链表的实现

单链表只有向后结点，当单链表的尾链表不指向NULL，而是指向头结点时候，形成了一个环，成为单循环链表，简称循环链表。当它是空表，向后结点就只想了自己，这也是它与单链表的主要差异，判断node->next是否等于head。

代码实现分为四部分：

1. 初始化

2. 插入

3. 删除

4. 定位寻找

代码实现：

void ListInit(Node *pNode){
    int item;
    Node *temp,*target;
    cout<<"输入0完成初始化"<>item;
        if(!item)
            return ;
        if(!(pNode)){ //当空表的时候，head==NULL 
            pNode = new Node ;
            if(!(pNode))
                exit(0);//未成功申请 
            pNode->data = item;
            pNode->next = pNode;
        }
        else{
            //
            for(target = pNode;target->next!=pNode;target = target->next)
                ;
            temp = new Node;
            if(!(temp))
                exit(0);
            temp->data = item;
            temp->next = pNode;
            target->next = temp;
        }
    }
} 
void ListInsert(Node *pNode,int i){ //参数是首节点和插入位置 
    Node *temp;
    Node *target;
    int item;
    cout<<"输入您要插入的值:"<>item;
    if(i==1){
        temp = new Node;
        if(!temp)
            exit(0);
        temp->data = item;
        for(target=pNode;target->next != pNode;target = target->next)
        ;
        temp->next = pNode;
        target->next = temp;
        pNode = temp;
    }
    else{
        target = pNode;
        for (int j=1;jnext;
        temp = new Node;
        if(!temp)
            exit(0);
        temp->data = item;
        temp->next = target->next;
        target->next = temp;
    }
}
void ListDelete(Node *pNode,int i){
    Node *target,*temp;
    if(i==1){
        for(target=pNode;target->next!=pNode;target=target->next)
        ;
        temp = pNode;//保存一下要删除的首节点 ,一会便于释放 
        pNode = pNode->next;
        target->next = pNode;
        delete temp; 
    }
    else{
        target = pNode;
        for(int j=1;jnext;
        temp = target->next;//要释放的node
        target->next = target->next->next;
        delete temp; 
    }
}
int ListSearch(Node *pNode,int elem){ //查询并返回结点所在的位置 
    Node *target;
    int i=1;
    for(target = pNode;target->data!=elem && target->next!= pNode;++i)
        target = target->next;
    if(target->next == pNode && target->data!=elem)
        return 0;
    else return i;
}

---

约瑟夫问题

约瑟夫环(约瑟夫问题)是一个数学的应用问题：已知n个人(以编号1，2，3…n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列;他的下一个人又从1开始报数，数到m的那个人又出列;依此规律重复下去，直到圆桌周围的人全部出列。这类问题用循环列表的思想刚好能解决。

注意：编写代码的时候，注意报数为m = 1的时候特殊情况

#include
#include
using namespace std;
typedef struct Node{
    int data;
    Node *next;
};

Node *Create(int n){
    Node *p = NULL, *head;
    head = new Node;
    if (!head)
        exit(0);
    p = head; // p是当前指针 
    int item=1;
    if(n){
        int i=1;
        Node *temp;
        while(i<=n){
            temp = new Node;
            if(!temp)
                exit(0);
            temp->data = i++;
            p->next = temp;
            p = temp; 
        }
        p->next = head->next;
    }
    delete head;
    return p->next;
}
void Joseph(int n,int m){
    //n为总人数，m为数到第m个的退出
    m = n%m;

    Node *start = Create(n);

    if(m){//如果取余数后的m!=0，说明 m!=1 
        while(start->next!=start){
            Node *temp = new Node;
            if(!temp)
                exit(0);
            for(int i=0;inext;
            temp = start->next;
            start->next = start->next->next;
            start = start->next;
            cout<data<<" ";
            delete temp;
        }
    }
    else{
        for(int i=0;idata<<" ";
            temp = start;
            start = start->next;
            delete temp;
        }
    }
    cout<data<