循环单链表解决约瑟夫环问题

/*
 * Copyright (c) 2010-~ zhouyongfei
 *
 * The source code is released for free distribution under the terms of the GNU General Public License
 *
 *
 * Author: alen Chou<[email protected]>
 * Created Time: 2010年06月10日 星期四 11时58分23秒
 * File Name: yusefu.c
 * Description: 约瑟夫问题描述：编号为1,2,3,4....n的n个人顺时针方向围坐一圈，每人持有一个密码（正整数）
 * 一开始选择一个数字作为报数的上限值m，从第一个人开始顺序报数，报道m的时候停止报数，报到m的人出列，将
 * 他持有的密码作为心的上限m值，并从他的下一个人从1开始报数,如此下去，直到所有人出列，设计一个程序，求出出列的顺序
 * 例如m的初值为20,n=7,7个人的密码一次是3,1,7,2,4,8,4，出列的顺序为6,1,4,7,2,3,5
 *
 */

#include<stdio.h>
#include<stdlib.h>
#include <unistd.h>

typedef struct node{
    int number;
    int pass;
    struct node *next;
}Node,*List;

/*
 *    初始化循环单链表
 *
 * */
void initList(List L)
{
    L->number = 0;
    L->pass = 0;
    L->next = L;
}

/*
 *    尾插法建立循环单链表
 *
 * */
void createFromTail(List head,int num[],int pas[],int length)
{
    int i;
    Node *pri;
    Node *tmp;
    head->number = num[0];
    head->pass = pas[0];
    pri = head ;
    for(i = 1;i<length;i++){
        tmp = (Node *)malloc(sizeof(Node));
        tmp->number = num[i];
        tmp->pass = pas[i];
        pri->next = tmp;
        pri = tmp;
        pri->next = head;
    }
}

/*
 *    从链表中删除
 *
 * */
void deleteFromList(List *head,Node *tmp)
{

    Node *tmp1;
    Node *tmp2;
    tmp1 = *head;
    tmp2 = tmp1;
    
    //如果链表剩了一个元素

    if(tmp->next == tmp){
        tmp->number = 0 ;
        tmp->pass = 0;
        return;
    }
    
    //如果此时删除了头节点，此时将头节点转移到头节点的下一个结点

    if((*head)->number == tmp->number){
        Node *x;
        Node *y;
        x = (*head)->next;
        while(x != (*head)){
            y = x;
            x = x->next;
        }
        y->next = (*head)->next;
        *head = (*head)->next;
    }else{
        //找到这个节点，删除他

        while(tmp1->number != tmp->number){
            tmp2 = tmp1;
            tmp1 = tmp1->next;
        }
        tmp2->next = tmp1->next;
    }
    

}


/*
 *    约瑟夫计数
 *
 * */
void yuesefu(List head, int m)
{
    Node *tmp;
    tmp = head;
    int time;
    time = m-1;
    int i = 0;
    printf("出队的顺序:(初始化的m=20)\n");
    
    while(tmp->number != 0){ //链表中此时没有结点，则退出


        for(i=0;i<time;i++){ //找到要删除的结点

            tmp = tmp->next;
        }
        printf("%d ",tmp->number);
        time = tmp->pass - 1;
        deleteFromList(&head,tmp);//删除结点

        tmp = tmp->next;//从下一个结点又开始计算

    }    
}

int main(int argc, char *argv[])
{
    int i;
    Node *p;
    
    int num[7] = {1,2,3,4,5,6,7};
    int pas[7] = {3,1,7,2,4,8,4};
    List head;
    head = (List)malloc(sizeof(List));
    initList(head);
    createFromTail(head,num,pas,sizeof(num)/sizeof(num[0]));

    p = head;
    printf("\n约瑟夫计数前，每个数和他的密码:\n");
    for(i = 0;i<sizeof(num)/sizeof(num[0]);i++){
        printf("%d,%d\n",p->number,p->pass);
        p = p->next;
    }

    printf("\n");
    yuesefu(head,20);
    printf("\n");
    return 0;
}