约瑟夫问题实现

/* doublylinkedlist.h */
#ifndef DOUBLYLINKEDLIST_H
#define DOUBLYLINKEDLIST_H

typedef struct node *link;
typedef unsigned char ElemType;

struct node {
    ElemType item;
    link prev, next;
};

link make_node(ElemType item);
void free_node(link p);
link search(ElemType key);
void insert(link p);
void delete(link p);
void traverse(void (*visit) (link));
void destroy(void);
void enqueue(link p);
link denqueue(void);

#endif

#include
#include "doublylinkedlist.h"
static link head = NULL;
static link tail = NULL;
static unsigned long count = 0;

link make_node(ElemType item)
{
    link p = malloc(sizeof *p);
    p->item = item;
    p->next = NULL;
    p->prev = NULL;
    return p;
}

void free_node(link p)
{
    if (p)
        free(p);
}

void insert(link p)
{
    if (!p)
        return;
    if (!head) {
        head = p;
        tail = p;
        p->next = NULL;
        p->prev = NULL;
        count++;
        return;
    }
    tail->next = p;
    head->prev = p;
    p->prev = tail;
    p->next = head;
    tail = p;
    count++;
}

void delete(link p)
{
    if (!p)
        return;
    if (head == tail) {
        head = tail = NULL;
        return;
    }
    p->prev->next = p->next;
    p->next->prev = p->prev;
    if (p == tail) {
        tail = p->prev;
    } else if (p == head) {
        head = p->next;
    }
    count--;
}

unsigned long get_count(void)
{
    return count;
}

link get_head(void)
{
    return head;
}

void traverse(void (*visit) (link))
{
    link p;
    p = head;
    visit(p);
    do {
        p = p->next;
        visit(p);
    } while (p != tail);
}


/*Josephus.c*/
#include
#include "doublylinkedlist.h"
#define N 100
#define M 3

void print_item_removed(link p)
{
    printf("%u has been removed!\n", p->item);
}

void print_item_exist(link p)
{
    printf("%u exist!\n", p->item);
}

int main()
{
    link p, phead;
    int i;
    for (i = 1; i <= N; i++) {
        p = make_node((ElemType)i);
        insert(p);
    }
    i = 1;
    p = phead = get_head();
#if 1
    while (get_count() >= M) {
        if (i % M == 0) {
            delete(p);
            print_item_removed(p);
        }
        p = p->next;
        i++;
    }
#endif
    printf("the left cell is :\n");
    printf("the number of the left cells is %d\n", get_count());
    traverse(print_item_exist);
    return 0;
}