Chinaunix首页 | 论坛 | 博客
  • 博客访问: 305144
  • 博文数量: 159
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 182
  • 用 户 组: 普通用户
  • 注册时间: 2013-11-02 10:42
文章分类

全部博文(159)

文章存档

2015年(18)

2014年(132)

2013年(9)

分类: C/C++

2013-11-08 21:26:16

/* 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;
}

阅读(1896) | 评论(0) | 转发(0) |
0

上一篇:单链表实现

下一篇:银行家算法

给主人留下些什么吧!~~