作业社区
探索学习新天地，共享知识资源！
慕九州9493288 的学生作业：
一、代码实现 ball_clock.h #ifndef __BALL_CLOCK_H__ #define __BALL_CLOCK_H__ #include #include #include // 数据类型定义（此处为int类型，代表球的编号） typedef int data_t; // 链表节点结构体（用于栈和队列的基础节点） typedef struct node { data_t data; // 节点存储的数据（球的编号） struct node *next; // 指向后继节点的指针 }linknode_t; // 链式队列结构体 typedef struct { linknode_t *front; // 队头指针（指向头节点） linknode_t *rear; // 队尾指针（指向最后一个数据节点） }linkqueue_t; // 链式栈结构体 typedef struct { int n; // 栈中元素的数量 linknode_t *top; // 栈顶指针（指向栈顶节点） }linkstack_t; // 队列操作函数声明 extern linkqueue_t *create_empty_linkqueue(); // 创建空队列 extern int is_empty_linkqueue(linkqueue_t *q); // 判断队列是否为空 extern void enter_linkqueue(linkqueue_t *q,data_t data); // 入队操作 extern data_t delete_linkqueue(linkqueue_t *q); // 出队操作 // 栈操作函数声明 extern linkstack_t *create_empty_linkstack(); // 创建空栈 extern int is_empty_linkstack(linkstack_t *s); // 判断栈是否为空 extern void push_linkstack(linkstack_t *s,data_t data); // 入栈操作 extern data_t pop_linkstack(linkstack_t *s); // 出栈操作 extern data_t get_top_linkstack(linkstack_t *s); // 获取栈顶元素 // 辅助函数和核心函数声明 extern void printf_linklist(linknode_t *node); // 打印链表元素 extern int ball_clock(); // 球钟核心逻辑实现 #endif ball_clock_queue.c #include "ball_clock.h" /** * 创建一个空的链式队列（带头节点） * @return 成功返回队列指针，失败返回NULL */ linkqueue_t *create_empty_linkqueue() { // 为队列结构体分配内存 linkqueue_t *q = malloc(sizeof(linkqueue_t)); if(NULL == q) { printf("queue malloc is fail\n"); // 内存分配失败提示 return NULL; } // 为头节点分配内存（头节点不存储实际数据，简化操作） linknode_t *head = malloc(sizeof(linknode_t)); if(NULL == head) { printf("head node malloc is fail\n"); // 头节点分配失败 free(q); // 释放已分配的队列结构体内存 return NULL; } head->next = NULL; // 头节点初始无后继 // 队头和队尾均指向头节点（空队列状态） q->front = q->rear = head; return q; } /** * 判断队列是否为空 * @param q 队列指针 * @return 空返回1，非空返回0 */ int is_empty_linkqueue(linkqueue_t *q) { return q->front == q->rear ? 1 : 0; // 队头队尾指向同一节点（头节点）则为空 } /** * 入队操作（在队尾添加元素） * @param q 队列指针 * @param data 要入队的数据（球的编号） */ void enter_linkqueue(linkqueue_t *q,data_t data) { // 为新节点分配内存 linknode_t *temp = malloc(sizeof(linknode_t)); if(NULL == temp) { printf("data node malloc is fail\n"); // 内存分配失败提示 return; } temp->data = data; // 存储数据 // 将新节点插入队尾 temp->next = q->rear->next; // 新节点后继为原队尾的后继（NULL） q->rear->next = temp; // 原队尾的后继指向新节点 q->rear = temp; // 队尾指针更新为新节点 } /** * 出队操作（移除并返回队头元素） * @param q 队列指针 * @return 队头元素的数据（球的编号） */ data_t delete_linkqueue(linkqueue_t *q) { linknode_t *temp = NULL; data_t data; temp = q->front->next; // 暂存队头元素（头节点的后继） data = temp->data; // 获取队头元素数据 q->front->next = temp->next; // 头节点后继指向原队头的后继 free(temp); // 释放原队头节点内存 temp = NULL; // 若出队后队列为空，队尾指针指向头节点 if(NULL == q->front->next) { q->rear = q->front; } return data; // 返回出队元素的数据 } ball_clock_stack.c #include "ball_clock.h" /** * 创建一个空的链式栈 * @return 成功返回栈指针，失败返回NULL */ linkstack_t *create_empty_linkstack() { // 为栈结构体分配内存 linkstack_t *s = malloc(sizeof(linkstack_t)); if(NULL == s) { printf("stack malloc is fail\n"); // 内存分配失败提示 return NULL; } s->n = 0; // 初始化栈中元素数量为0 s->top = NULL; // 初始化栈顶指针为NULL（空栈） return s; } /** * 判断栈是否为空 * @param s 栈指针 * @return 空返回1，非空返回0 */ int is_empty_linkstack(linkstack_t *s) { return s->top == NULL ? 1 : 0; // 栈顶指针为NULL则为空 } /** * 入栈操作（在栈顶添加元素） * @param s 栈指针 * @param data 要入栈的数据（球的编号） */ void push_linkstack(linkstack_t *s,data_t data) { // 为新节点分配内存 linknode_t *temp = malloc(sizeof(linknode_t)); if(NULL == temp) { printf("data node malloc is fail\n"); // 内存分配失败提示 return; } temp->data = data; // 存储数据 // 将新节点插入栈顶（头插法） temp->next = s->top; // 新节点的后继指向原栈顶 s->top = temp; // 栈顶指针更新为新节点 s->n++; // 栈中元素数量加1 } /** * 出栈操作（移除并返回栈顶元素） * @param s 栈指针 * @return 栈顶元素的数据（球的编号） */ 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--; // 栈中元素数量减1 return data; // 返回出栈元素的数据 } /** * 获取栈顶元素（不移除） * @param s 栈指针 * @return 栈顶元素的数据（球的编号） */ data_t get_top_linkstack(linkstack_t *s) { return s->top->data; // 直接返回栈顶节点的数据 } main.c #include "ball_clock.h" // 球钟配置参数宏定义 #define BALL_NUM 27 // 球的总数 #define MIN_MAX 4 // 分钟栈最大容量（4个球代表5分钟，满则清空） #define FIVE_MIN_MAX 11 // 五分钟栈最大容量（11个球代表55分钟，满则清空） #define HOUR_MAX 11 // 小时栈最大容量（11个球代表11小时，满则清空） #define TRUE 1 // 循环控制常量 /** * 打印链表中的所有元素 * @param node 链表头指针（首个数据节点） */ void printf_linklist(linknode_t *node) { linknode_t *p = node; while(NULL != p) { printf("%d ",p->data); // 打印当前节点数据 p = p->next; // 移动到下一个节点 } printf("\n"); // 打印完成后换行 } /** * 判断队列是否恢复到初始状态（球按1~27顺序排列） * @param q 队列指针 * @return 恢复初始状态返回1，否则返回0 */ int is_orginal_queue(linkqueue_t *q) { int i = 0; linknode_t *p = q->front->next; // 从首个数据节点开始检查 // 检查每个位置是否与初始顺序（1~27）一致 for(i = 1;i data) { return 0; // 有不一致则返回0 } p = p->next; // 检查下一个节点 } return 1; // 全部一致返回1 } /** * 球钟核心逻辑：模拟球的流动，计算恢复初始状态所需的天数 * @return 恢复初始状态所需的天数 */ int ball_clock() { // 声明队列和栈指针：主队列（待使用的球）、分钟栈、五分钟栈、小时栈 linkqueue_t *ball_queue = NULL; linkstack_t *min_stack = NULL, *five_min_stack = NULL, *hour_stack = NULL; data_t ball = 0; // 临时存储当前处理的球 int half_day = 0; // 记录经过的半天数（12小时为一个半天，也就是一个计数周期） // 初始化队列和栈 ball_queue = create_empty_linkqueue(); min_stack = create_empty_linkstack(); five_min_stack = create_empty_linkstack(); hour_stack = create_empty_linkstack(); // 初始化队列：将1~27号球按顺序加入队列 for(ball = 1;ball front->next); // 循环模拟时间流逝，直到队列恢复初始状态 while(TRUE) { ball = delete_linkqueue(ball_queue); // 从队列取出一个球 // 步骤1：处理分钟栈（每球代表1分钟，满4球则清空） if(min_stack->n < MIN_MAX) { push_linkstack(min_stack,ball); // 球入分钟栈 continue; // 继续处理下一个球 } // 分钟栈满：将栈中所有球倒回队列（顺序反转） while(!is_empty_linkstack(min_stack)) { enter_linkqueue(ball_queue,pop_linkstack(min_stack)); } // 步骤2：处理五分钟栈（每球代表5分钟，满11球则清空） if(five_min_stack->n < FIVE_MIN_MAX) { push_linkstack(five_min_stack,ball); // 球入五分钟栈 continue; // 继续处理下一个球 } // 五分钟栈满：将栈中所有球倒回队列（顺序反转） while(!is_empty_linkstack(five_min_stack)) { enter_linkqueue(ball_queue,pop_linkstack(five_min_stack)); } // 步骤3：处理小时栈（每球代表1小时，满11球则清空） if(hour_stack->n < HOUR_MAX) { push_linkstack(hour_stack,ball); // 球入小时栈 continue; // 继续处理下一个球 } // 小时栈满：将栈中所有球倒回队列（顺序反转） while(!is_empty_linkstack(hour_stack)) { enter_linkqueue(ball_queue,pop_linkstack(hour_stack)); } // 所有栈都满：当前球直接放回队列尾部（代表12小时循环结束） enter_linkqueue(ball_queue,ball); half_day++; // 记录一个半天（12小时）为一次轮询计数周期 // 检查队列是否恢复初始状态，是则退出循环 if(is_orginal_queue(ball_queue)) { break; } } return half_day / 2; // 找到初始状态时一共轮询的次数N，等于N*12小时或N* 0.5天或N *(12*60=720)分钟 } /** * 主函数：调用球钟逻辑，打印结果 */ int main() { int day = 0; day = ball_clock(); // 获取恢复初始状态所需的天数 // 打印结果（天数和对应的分钟数） printf("Finding original queue need %d days or %d minutes\n",day,day * 24 * 60); return 0; } 二、结果 结果1：要想表示00:00到12：00最少需要多少个球? 12小时刚好是球钟轮询一个周期，既需要球数量：4+11+11+1 = 27 个球 结果2：假设，指示器都为空，球队列需要多长时间能回到原来的状态?【图片】
+10