4. 综合练习

一.球钟问题

球钟是⼀个利用球的移动来记录时间的简单装置。它有三个可以容纳若干个球的指示器：分钟指示器，五分钟指示器，小时指示器。若分钟指示器中有2个球，5分钟指示器中有6个球，小时指示器中有5个球，则时间为5:32。

工作原理：

每过一分钟，球钟就会从球队列的队首取出一个球放入分钟指示器，分钟指示器最多可容纳4个球。当放入第五个球时，在分钟指示器内的4个球就会按照他们被放入时的相反顺序加入球队列的队尾。而第五个球就会进入五分钟指示器。按此类推，五分钟指示器最多可放11个球，小时指示器最多可放11个球。当小时指示器放入第12个球时，原来的11个球按照他们被放入时的相反顺序加入球队列的队尾，然后第12个球也回到队尾。这时，三个指示器均为空，回到初始状态，从而形成一个循环。因此，该球种表示的时间范围是从00:00到11:59

要想表示00:00到12：00最少需要多少个球?

假设，指示器都为空，球队列需要多长时间能回到原来的状态?

即从初始球队列中球的顺序，经过球的循环后球队列中的球再次与初始顺序相同。

二. 综合练习代码

head.h

#ifndef _HEAD_H_
#define _HEAD_H_

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

#define N 123

typedef int data_t;

typedef struct node
{
    data_t data;
    struct node *next;
}linknode_t;

//链式栈栈头类型
typedef struct 
{
    linknode_t *top;
    int n;
}linkstack_t;

//链式队列的队列头的类型 
typedef struct 
{
    linknode_t *front;
    linknode_t *rear;
}linkqueue_t;

//链式栈的操作
extern linkstack_t *create_empty_linkstack();
extern int is_empty_linkstack(linkstack_t *s);
extern int push_linkstack(linkstack_t *s,data_t data);
extern data_t pop_linkstack(linkstack_t *s);
extern data_t get_top_data(linkstack_t *s);

//链式队列的操作
extern linkqueue_t *create_empty_linkqueue();
extern int is_empty_linkqueue(linkqueue_t *q);
extern int enter_linkqueue(linkqueue_t *q,data_t data);
extern data_t delete_linkqueue(linkqueue_t *q);

#endif

linkqueue.c

#include "head.h"

linkqueue_t *create_empty_linkqueue()
{
    linknode_t *head = NULL;
    linkqueue_t *q = NULL;

    head = (linknode_t *)malloc(sizeof(linknode_t));
    head->next = NULL;

    q = (linkqueue_t *)malloc(sizeof(linkqueue_t));
    q->front = q->rear = head;

    return q;
}

int is_empty_linkqueue(linkqueue_t *q)
{
    return q->front == q->rear;
}

int enter_linkqueue(linkqueue_t *q,data_t data)
{
    linknode_t *temp = NULL;

    temp = (linknode_t *)malloc(sizeof(linknode_t));
    temp->data = data;

    /*temp->next = q->rear->next;*/
    temp->next = NULL;
    q->rear->next = temp;

    q->rear = temp;

    return 0;
}

data_t delete_linkqueue(linkqueue_t *q)
{
    linknode_t *temp = NULL;

    temp = q->front;

    q->front = temp->next;

    free(temp);
    temp = NULL;

    return q->front->data;
}

linkstack.c

#include "head.h"

linkstack_t *create_empty_linkstack()
{
    linkstack_t *s = NULL;

    s = (linkstack_t *)malloc(sizeof(linkstack_t));
    s->top = NULL;
    s->n = 0;

    return s;
}

int is_empty_linkstack(linkstack_t *s)
{
    return s->top == NULL;
}

int push_linkstack(linkstack_t *s,data_t data)
{
    linknode_t *temp = NULL;

    temp = (linknode_t *)malloc(sizeof(linknode_t));
    temp->data = data;

    temp->next = s->top;
    s->top = temp;

    s->n++;

    return 0;
}

data_t pop_linkstack(linkstack_t *s)
{
    linknode_t *temp = NULL;
    data_t data;

    temp = s->top;
    data = temp->data;

    s->top = temp->next;

    free(temp);
    temp = NULL;

    s->n--;

    return data;
}

data_t get_top_data(linkstack_t *s)
{
    return s->top->data;
}

ballclock.c

#include "head.h"

int print_linklist(linknode_t *head)
{
    linknode_t *p = head->next;

    while(p)
    {
        /*printf("%-3d",p->data);*/
        printf("%-3d\t",p->data);
        p = p->next;
    }
    putchar('\n');

    return 0;
}

int is_orginal_queue(linkqueue_t *q)
{
    int i = 1;
    linknode_t *p = q->front->next;

    for(i = 1;i <= N;i++)
    {
        if(i != p->data)
            return 0;

        p = p->next;
    }

    return 1;
}

int ball_clock()
{
    linkstack_t *min_stack = NULL,
                *min5_stack = NULL,
                *hour_stack = NULL;
    linkqueue_t *ball_queue = NULL;
    int half_day = 0;
    int ball = 0;

    min_stack = create_empty_linkstack();
    min5_stack = create_empty_linkstack();
    hour_stack = create_empty_linkstack();

    ball_queue = create_empty_linkqueue();

    for(ball = 1;ball <= N;ball++)
    {
        enter_linkqueue(ball_queue,ball);
    }

    print_linklist(ball_queue->front);

    while(1)
    {
        ball = delete_linkqueue(ball_queue);

        if(min_stack->n < 4)
        {
            push_linkstack(min_stack,ball);
            continue;
        }

        while(!is_empty_linkstack(min_stack))
        {
            enter_linkqueue(ball_queue,pop_linkstack(min_stack));
        }

        if(min5_stack->n < 11)
        {
            push_linkstack(min5_stack,ball);
            continue;
        }

        while(!is_empty_linkstack(min5_stack))
        {
            enter_linkqueue(ball_queue,pop_linkstack(min5_stack));
        }

        if(hour_stack->n < 11)
        {
            push_linkstack(hour_stack,ball);
            continue;
        }

        while(!is_empty_linkstack(hour_stack))
        {
            enter_linkqueue(ball_queue,pop_linkstack(hour_stack));
        }

        enter_linkqueue(ball_queue,ball);

        half_day++;

        if(is_orginal_queue(ball_queue))
            break;
    }

    return half_day / 2;
}

int main()
{
    int day_count = 0;

    day_count = ball_clock();

    printf("Restoring orignal queue need %d days\n",day_count);

    return 0;
}