线性表的应用（Joseph问题）

 

#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
    int num;
    struct node *next;
}LinkNode;
LinkNode *create_joseph_loop(int n)
{
    int i;
    LinkNode *tmp;
    LinkNode *head;
    LinkNode *p;
    head = (LinkNode *)malloc(sizeof(LinkNode));
    head->num = 1;
    p = head;
    for(i = 2;i <= n;i ++){
        tmp = (LinkNode *)malloc(sizeof(LinkNode));
        tmp->num = i;
        p->next = tmp;
        p = tmp;
    }
    p->next = head;
    return head;
}
void printf_joseph_loop(LinkNode *head)
{
    LinkNode *p;
    p = head;
    do{
        printf("%d ",p->num);
        p = p->next;
    }while(p != head);
    printf("\n");
    return;
}
void ans_joseph(LinkNode *head,int k,int m)
{
    int i;
    LinkNode *p;
    LinkNode *tmp;
    p = head;
    //找到第K个人
    for(i = 0;i < k - 1;i ++){
        p = p->next;
    }
    while(p->next != p){
        //开始计数,找到要删除的人
        for(i = 0;i < m - 1;i ++){
            p = p->next;
        }
        //删除p的后一个节点
        //
        //记录p的后一个节点
        tmp = p->next;
        printf("%d ",p->num);
        //将后一个节点数据赋值给p节点
        p->num = tmp->num;
        //将后一个节点删除
        p->next = tmp->next;
        free(tmp);
    }
    printf("%d\n",p->num);
    free(p);
    return;
}
int main(int argc, const char *argv[])
{
    LinkNode *head = create_joseph_loop(8);
    printf_joseph_loop(head);
    ans_joseph(head,3,4);
    return 0;
}