球钟问题(用链式栈和链式队列实现).doc

球钟问题 球钟问题描述:球钟是一个利用球的移动来记录时间的简单装置。它有三个可以容纳若干个球的指示器：分钟指示器，五分钟指示器，小时指示器。若分钟指示器中有2个球，5分钟指示器中有6个球，小时指示器中有5个球，则时间为5:32。 工作原理: 每过一分钟，球钟就会从球队列的队首取出一个球放入分钟指示器，分钟指示器最多可容纳4个球。当放入第五个球时，在分钟指示器的4个球就会按照 他们被放入时的相反顺序加入球队列的队尾。而第五个球就会进入五分钟指示器。按此类推，五分钟指示器最多可放11个球，小时指示器最多可放11个球。当小时 指示器放入第12个球时，原来的11个球按照他们被放入时的相反顺序加入球队列的队尾，然后第12个球也回到队尾。这时，三个指示器均为空，回到初始状 态，从而形成一个循环。因此，该球种表示的时间范围是从00:00到11:59 思考：要想表示00:00到12：00最少需要多少个球?假设，指示器都为空，球队列需要多长时间能回到原来的状态?代码实现：Head.h#include /队typedef int DataType;struct node DataType data; struct node *next;typedef struct struct node *front; struct node *rear;LinkQueue;/栈typedef struct struct node *top; int n;LinkStack;extern LinkQueue *create_empty_linkqueue();extern int is_empty_linkqueue(LinkQueue *l);extern int enter_linkqueue(LinkQueue *l,DataType data);extern DataType delete_linkqueue(LinkQueue *l);extern LinkStack *create_empty_linkstack();extern int is_empty_linkstack(LinkStack *s);extern int push_linkstack(LinkStack *s,DataType data);extern DataType pop_linkstack(LinkStack *s);extern DataType get_top_data(LinkStack *s);extern void pop_ball_stack(LinkStack *s,LinkQueue *l);Stack_queue.c#include head.h#include /队的创建，入队，出队实现LinkQueue *create_empty_linkqueue() LinkQueue *q = (LinkQueue *)malloc(sizeof(LinkQueue); struct node *head = (struct node *)malloc(sizeof(struct node); head-next = NULL; q-front = q-rear = head; return q;int is_empty_linkqueue(LinkQueue *l) return l-front = l-rear;int enter_linkqueue(LinkQueue *l,DataType data) struct node *q = (struct node *)malloc(sizeof(struct node); q-data = data; q-next = NULL; l-rear-next = q; l-rear = q; return 0;DataType delete_linkqueue(LinkQueue *l) / DataType data; struct node *temp = l-front; / data = l-front-data; l-front = temp-next; free(temp); temp = NULL; return l-front-data; /栈的创建，出栈，进栈实现LinkStack *create_empty_linkstack() LinkStack *s = NULL; s = (LinkStack *)malloc(sizeof(LinkStack); s-top = NULL; s-n = 0; return s;int is_empty_linkstack(LinkStack *s) return s-top = NULL;int push_linkstack(LinkStack *s,DataType data) struct node *temp = NULL; temp = (struct node *)malloc(sizeof(struct node); temp-data = data; temp-next = s-top; s-top = temp; s-n+; return 0;DataType pop_linkstack(LinkStack *s) struct node *temp = NULL; DataType data; temp = s-top; data = temp-data; s-top = s-top-next; s-n-; free(temp); return data;DataType get_top_data(LinkStack *s) return s-top-data;void pop_ball_stack(LinkStack *s,LinkQueue *l) while(!is_empty_linkstack(s) enter_linkqueue(l,pop_linkstack(s); /return;Ball_clock.c#include head.h#define N 27int check_ball_clock(LinkQueue *l) int i = 0; struct node *q = l-front-next; for(i = 1;i data != i) return 0; q = q-next; return 1;int main() LinkQueue *l = NULL; LinkStack *s_1m = NULL, *s_5m = NULL, *s_1h = NULL; int i = 0,flag = 1,time = 0; int data = 0; l = create_empty_linkqueue(); s_1m = create_empty_linkstack(); s_5m = create_empty_linkstack(); s_1h = create_empty_linkstack(); printf(print all the number in the LinkQueue !n); for(i = 1;i N + 1;i+) enter_linkqueue(l,i); printf(%d ,i); printf(n*n); /for(i = 0;i n != 4) push_linkstack(s_1m,data); else pop_ball_stack(s_1m,l); if(s_5m-n != 11) push_linkstack(s_5m,data); else pop_ball_stack(s_5m,l); if(s_1h-n != 11) push_linkstack(s_1h,data); else pop_ball_stack(s_1h,l); enter_linkqueue(l,data); if(check_ball_clock(l) flag = 0; printf(It passed %d minute