1770: [编程入门]链表之报数问题

约瑟夫环问题。用循环链表解决。（也可以直接用公式法递推）

#include <bits/stdc++.h>
using namespace std;
 
typedef int ElementType;
struct cNode{
    ElementType data;
    struct cNode* Next;
};
typedef struct cNode* PtrtoCNode;
typedef PtrtoCNode CNode;
 
void tailinsert(ElementType data,CNode L);//尾插法建表
CNode deletenode(CNode p,CNode head);//报到的人删除
void ConnectCList(CNode head);//单链表头尾相连成循环链表
 
int main(){
    int n;
    cin >> n;
 
    CNode head = (CNode)malloc(n*sizeof(struct cNode));
    head->data = 0;
    head->Next = NULL;
 
    ElementType x;
 
    for(int i=1;i<=n;i++){
        tailinsert(i,head);
    }
 
    ConnectCList(head);
 
    //报数过程开始
    CNode p = head->Next;
 
    while(head->data!=1){
        for(int i=0;i<2;i++){
            p = p->Next;
        }
        p = deletenode(p,head);
    }
 
    cout << head->Next->data << endl;
 
    return 0;
}
 
void tailinsert(ElementType data,CNode L){
    CNode node = (CNode)malloc(sizeof(node));
    node->data = data;
    node->Next = NULL;
    if(L->data==0){
        L->Next = node;
        L->data++;
    }
    else{
        CNode temp = L->Next;
        while(temp->Next!=NULL){
            temp = temp->Next;
        }
        temp->Next = node;
        L->data++;
    }
}
 
CNode deletenode(CNode p,CNode head){
    CNode temp = head->Next;
    CNode t;
    CNode preserve;
    if(p==head->Next){//要删除结点是第一个结点的情况
        head->Next = p->Next;
        preserve = p->Next;
        p->Next = NULL;
        free(p);
        p = NULL;//free完记得置空
        head->data--;
        ConnectCList(head);
        return preserve;
    }
    else{
        while(temp->Next!=p){
            temp = temp->Next;
        }
        temp->Next = p->Next;
        preserve = p->Next;
        p->Next = NULL;
        free(p);
        p = NULL;//free完记得置空
        head->data--;
        return preserve;
    }
}
 
void ConnectCList(CNode head){
    CNode temp = head;
    for(int i=0;i<head->data;i++){
        temp = temp->Next;
    }
    temp->Next = head->Next;
}