作业社区
探索学习新天地，共享知识资源！
zhuluoc 的学生作业：
linknode.h #ifndef __LINKNODE_H__ #define __LINKNODE_H__ #include #include #include //---------------------------------------------------- // 定义数据类型 typedef int data_t; // 定义链式栈节点结构体 typedef struct node { data_t data; struct node *next; } linknode_t; //---------------------------------------------------- #endif linkstack.h #ifndef __LINKSTACK_H__ #define __LINKSTACK_H__ #include "linknode.h" //---------------------------------------------------- // 定义链式栈结构体 typedef struct { linknode_t *top; // 栈顶指针 int icnt; // 当前栈中的元素 } linkstack_t; //---------------------------------------------------- extern linkstack_t *create_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); // 获取栈顶元素 #endif linkstack.c #include "linkstack.h" //---------------------------------------------------- // 创建栈 linkstack_t *create_linkstack() { // 创建空的链式栈，只有栈头，没有结点 linkstack_t *s = (linkstack_t *)malloc(sizeof(linkstack_t)); if (NULL == s) { printf("create link stack malloc error!\n"); return NULL; } s->top = NULL; s->icnt = 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 *t = (linknode_t *)malloc(sizeof(linknode_t)); if (NULL == t) { printf("create stack node malloc error!\n"); return -1; } t->data = data; t->next = s->top; // 入栈采用链表头插法 // 更新栈顶指针 s->top = t; // 更新栈元素个数 s->icnt++; return 0; } //---------------------------------------------------- // 出栈 data_t pop_linkstack(linkstack_t *s) { linknode_t *t = NULL; data_t data; // 保存要删除结点（栈顶元素） t = s->top; data = t->data; // 更新栈顶指针 s->top = t->next; // 释放结点 free(t); t = NULL; // 更新栈元素的个数 s->icnt--; return data; } //---------------------------------------------------- // 获取栈顶元素 data_t get_top_data(linkstack_t *s) { return s->top->data; } //---------------------------------------------------- linkqueue.h #ifndef __LINKQUEUE_H__ #define __LINKQUEUE_H__ #include "linknode.h" //---------------------------------------------------- // 队列长度：11(时) + 11(5分) + 4(分) + 1(队头节点) #define QULEN 27 typedef struct { linknode_t *front; linknode_t *rear; } linkqueue_t; //---------------------------------------------------- extern linkqueue_t *create_linkqueue(); // 创建队列 extern int is_empty_linkqueue(linkqueue_t *q); // 判断是否为空队列 extern void enter_linkqueue(linkqueue_t *q, data_t data); // 入队 extern data_t leave_linkqueue(linkqueue_t *q); // 出队 extern void print_linkqueue(linkqueue_t *q); // 遍历队列元素 extern int is_orginal_queue(linkqueue_t *q); // 判断队列是否回归到原始状态 #endif linkqueue.c #include "linkqueue.h" //---------------------------------------------------- // 创建队列 linkqueue_t *create_linkqueue() { linkqueue_t *q = NULL; linknode_t *h = NULL; // 创建队列头结点，指针域为空 h = (linknode_t *)malloc(sizeof(linknode_t)); if (NULL == h) { printf("link node create malloc error\n"); return NULL; } h->next = NULL; q = (linkqueue_t *)malloc(sizeof(linkqueue_t)); if (NULL == q) { printf("link queue create malloc error!\n"); return NULL; } // 队列的头指针和尾指针 初始化时均指向头结点 q->front = q->rear = h; return q; } //---------------------------------------------------- // 判断是否为空队列 int is_empty_linkqueue(linkqueue_t *q) { return q->front == q->rear; } //---------------------------------------------------- // 入队 void enter_linkqueue(linkqueue_t *q, data_t data) { linknode_t *t = (linknode_t *)malloc(sizeof(linknode_t)); if (NULL == t) { printf("link node create malloc error\n"); return; } t->data = data; // 使用链表尾插法入队 t->next = q->rear->next; q->rear->next = t; // 尾指针后移到最后 q->rear = t; } //---------------------------------------------------- // 出队 data_t leave_linkqueue(linkqueue_t *q) { linknode_t *t = NULL; data_t data; // 记录当前队头位置 t = q->front->next; data = t->data; // 释放队头指针 q->front->next = t->next; free(t); t = NULL; // 检查数据是否已出完 if (NULL == q->front->next) { q->rear = q->front; } return data; } //---------------------------------------------------- // 遍历队列元素 void print_linkqueue(linkqueue_t *q) { linknode_t *t = q->front->next; while (t) { printf("%-3d", t->data); t = t->next; } printf("\n"); } //---------------------------------------------------- // 判断是否回归到原始状态 int is_orginal_queue(linkqueue_t *q) { int i = 0; linknode_t *p = q->front->next; for (i = 1; i data) return 0; p = p->next; } return 1; } //---------------------------------------------------- main.c #include "linkqueue.h" #include "linkstack.h" int main() { int i = 0, half_day = 0; data_t ball = 0; linkstack_t *smin = NULL, *s5min = NULL, *shour = NULL; linkqueue_t *que = NULL; que = create_linkqueue(); if (NULL == que) return -1; // 按顺序初始化队列 for (i = 1; i icnt < 4) { // 如果分钟指示器没满，则将球入栈 push_linkstack(smin, ball); continue; } // 分钟栈满了，全部元素出栈并重新入队 while (!is_empty_linkstack(smin)) { enter_linkqueue(que, pop_linkstack(smin)); } // 5分钟栈没满栈时，将球入栈 if (s5min->icnt < 11) { push_linkstack(s5min, ball); continue; } // 当5分钱栈满时，全部出栈并重新入队 while(!is_empty_linkstack(s5min)) { enter_linkqueue(que, pop_linkstack(s5min)); } // 当时钟栈没满时，将球入栈 if (shour->icnt < 11) { push_linkstack(shour, ball); continue; } // 当时钟满时，全部出栈并重新入队 while (!is_empty_linkstack(shour)) { enter_linkqueue(que, pop_linkstack(shour)); } // 分钟、5分钟、时钟 栈均为满时，将球重新加入队列 enter_linkqueue(que, ball); half_day++; // // 检查队列是否重新回到最初状态 if (is_orginal_queue(que)) break; } printf("The queue restore to original need %d days\n", half_day / 2); return 0; } 输出结果： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 The number of days required to restore the original queue is 23 days
+15