Question

编程：用带头节点的单循环链表(或无头节点)解决约瑟夫环问题，要能运行的（最好有截图）。

Answer 1

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Node{
    int val;
    struct Node *nxt;
}Node;
typedef struct Link{
    Node *curNode;
}Link;
int LinkInsert(Link *curLink,int val){
    if(curLink == NULL) return 0;
    Node *newNode = (Node*)malloc(sizeof(Node));
    if(newNode == NULL) return 0;
    newNode->val = val;
    if(curLink->curNode == NULL){
        newNode->nxt=newNode;
        curLink->curNode = newNode;
        return 1;
    }
    newNode->nxt=curLink->curNode->nxt;
    curLink->curNode->nxt = newNode;
    curLink->curNode = newNode;
    return 1;
}
int LinkDelete(Link *curLink){
    if(curLink == NULL || curLink->curNode==NULL) return 0;
    Node *curNode=curLink->curNode,*nxtNode=curNode->nxt;
    if(curNode == nxtNode){
        free(nxtNode);
        curLink->curNode=NULL;
        return 1;
    }
    curNode->val=nxtNode->val;
    curNode->nxt=nxtNode->nxt;
    free(nxtNode);
    return 1;
}
int makeJosephLink(Link *curLink,int n){
    int i;
    for(i=1;i<=n;i++)
        if(LinkInsert(curLink,i) == 0)
            return 0;
    curLink->curNode = curLink->curNode->nxt;
    return 1;
}
int doJosephStep(Link *curLink,int k){
    int i,ret;
    if(curLink == NULL) return 0;
    for(i=0;i<k-1;i++) curLink->curNode=curLink->curNode->nxt;
    ret=curLink->curNode->val;
    LinkDelete(curLink);
    return ret;
}
int lenOfNum(int x){
    int ret=0;
    do{
        ret++;
        x/=10;
    }while(x);
    return ret;
}
int printLink(Link *curLink,int n){
    if(curLink == NULL) return -1;
    Node *oriNode = curLink -> curNode;
    int firstNodeTimes=0,i=0,j;
    if(oriNode == NULL) return 0;
    while(curLink->curNode->nxt->val > curLink->curNode->val)    curLink->curNode=curLink->curNode->nxt;
    curLink->curNode=curLink->curNode->nxt;
    i=0;j=curLink->curNode->val;
    for(i=1;i<=n;i++){
        if(curLink->curNode->val != i){
            printf("[%*s]",lenOfNum(i)," ");
            continue;
        }
        printf("[%d]",curLink->curNode->val);
        curLink->curNode = curLink->curNode->nxt;
    }
    printf("\n");
    curLink->curNode=oriNode;
    return 1;
}
void doAll(int n,int k){
    Link JosephLink;
    JosephLink.curNode=NULL;
    makeJosephLink(&JosephLink,n);
    while(printLink(&JosephLink,n) && doJosephStep(&JosephLink,k));
}
int main(){
    int n,k;
    while(~scanf("%d%d",&n,&k)){
        printf("--------------------Joseph---------------------\n");
        doAll(n,k);
        printf("--------------------Joseph---------------------\n");
    }
    return 0;
}