|
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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 |
//queue.h #pragma c9x on #ifndef _QUEUE_H_ #define _QUEUE_H_ #include <stdbool.h> //在此处插入Item的类型定义 typedef struct item { long arrive; //一位顾客加入队列的时间 int processtime; //该顾客需要咨询的时间 } Item; #define MAXQUEUE 10 typedef struct node { Item item; struct node * next; } Node; typedef struct queue { Node * front; //指向队列首的指针 Node * rear; //指向队列尾的指针 int items; //队列中项目的个数 } Queue; /* 操作：初始化队列 操作前：pq指向一个队列 操作后：该队列初始化为空队列 */ void InitializeQueue(Queue * pq); /* 操作：检查队列是否已满 操作前：pq指向一个先前已初始化过的队列 操作后：如果该队列满了，则返回true，否则返回false */ bool QueueIsFull(const Queue * pq); /* 操作：检查队列是否为空 操作前：pq指向一个先前已初始化过的队列 操作后：如果该队列为空，则返回true，否则返回false */ bool QueueIsEmpty(const Queue * pq); /* 操作：确定队列中项目的个数 操作前：pq指向一个先前已初始化过的队列 操作后：返回队列中项目的个数 */ int QueueItemCount(const Queue * pq); /* 操作：向队列尾部添加项目 操作前：pq指向一个先前已初始化过的队列 item是要添加到队列尾部的项目 操作后：如果队列未满，item被添加到 队列尾部，函数返回ture，否则 不改变队列，函数返回false */ bool EnQueue(const Item item, Queue * pq); /* 操作：从队列首端删除项目 操作前：pq指向一个先前已初始化过的队列 操作后：如果队列非空，队列首端的项目 被复制到*pitem，并被从队列中删除， 函数返回true，如果这个操作使队列 为空，把队列重置为空队列 如果队列开始时为空 不改变队列，函数返回false */ bool DeQueue(Item * pitem, Queue * pq); /* 操作：清空队列 操作前：pq指向一个先前已初始化过的队列 操作后：队列被清空 */ void EmptyTheQueue(Queue * pq); #endif |
|
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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 |
//queue.c #include <stdio.h> #include <stdlib.h> #include "queue.h" //局部函数声明 static void CopyToNode(Item item, Node * pn); static void CopyToItem(Node * pn, Item * pi); void InitializeQueue(Queue * pq) { pq->front = pq->rear = NULL; pq->items = 0; } bool QueueIsFull(const Queue * pq) { return pq->items == MAXQUEUE; } bool QueueIsEmpty(const Queue * pq) { return pq->items == 0; } int QueueItemCount(const Queue * pq) { return pq->items; } bool EnQueue(const Item item, Queue * pq) { Node * pnew; if (QueueIsFull(pq)) { return false; } pnew = (Node *) malloc(sizeof(Node)); if (pnew == NULL) { fprintf(stderr, "Unable to allocate memory!\n"); exit(1); } CopyToNode(item, pnew); pnew->next = NULL; if (QueueIsEmpty(pq)) { pq->front = pnew; } else { pq->rear->next = pnew; } pq->rear = pnew; pq->items++; return true; } bool DeQueue(Item * pitem, Queue * pq) { Node * pt; if (QueueIsEmpty(pq)) { return false; } CopyToItem(pq->front, pitem); pt = pq->front; pq->front = pq->front->next; free(pt); pq->items--; if (pq->items == 0) { pq->rear = NULL; } return true; } void EmptyTheQueue(Queue * pq) { Item dummy; while(!QueueIsEmpty(pq)) { DeQueue(&dummy, pq); } } static void CopyToNode(Item item, Node * pn) { pn->item = item; } static void CopyToItem(Node * pn, Item * pi) { *pi = pn->item; } |
|
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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 |
// 使用队列，做一个一段时间(小时)内，平均每小时接受顾客数的简单数据分析 // 每个顾客所消耗的时间是1-3分钟 最多排10个客户，超出长度的客户不再接受 // gcc -c queue.c gcc main.c queue.o #include <stdio.h> #include <stdlib.h> //为rand()、srand()函数提供原型 #include <time.h> //为time()函数提供原型 #include "queue.h" #define MIN_PER_PR 60.0 //顾客到达的平均间隔时间 bool newcustomer(double x); //有新顾客到来吗 Item customertime(long when); //设置顾客参量 int main(int argc, char const *argv[]) { Queue line; Item temp; //关于新顾客的数据 int hours; //模拟的小时数 int perhour; //每小时顾客的平均数 long cycle,cyclelimit; //循环计数器，计数器的上界 long turnaways = 0; //因队列已满而被拒绝的顾客数 long customers = 0; //被加入到队列的顾客数 long served = 0; //在模拟期间得到服务的顾客数 long sum_line = 0; //累计的队列长度 int wait_time = 0; //从当前到sigmund空闲所需的时间 double min_per_cust; //顾客到来的平均间隔时间 long line_wait = 0; //队列累计等待时间 InitializeQueue(&line); //初始化队列，开启服务窗口 srand(time(0)); //随机初始化rand()函数 puts("Case Study:Sigmund Lander's Advice Booth"); puts("Enter the number of simulation hours:"); // 模拟输入小时数 scanf("%d", &hours); // 转换成分钟数 cyclelimit = MIN_PER_PR * hours; puts("Enter the average number of customers per hour"); // 模拟输入平均每小时的顾客数 scanf("%d", &perhour); // 比如每小时顾客数为20，那平均间隔就是3分钟一个 min_per_cust = MIN_PER_PR / perhour; // 循环每分钟检查是否有顾客到来，根据队列(排队)情况，做出相应统计 for (cycle = 0; cycle < cyclelimit; ++cycle) { // 如果有新用户到来 因为平均间隔是个平均值，所以在函数中加入rand()增加一些随机性 // 当然，间隔越短，返回true(有新用户到来)的可能性更大 if (newcustomer(min_per_cust)) { // 如果有新顾客到来，是否还能排上队(超过10个就排不上了) if (QueueIsFull(&line)) { // 统计没排上队的顾客数+1 turnaways++; } else { // 统计排上队的顾客数+1 customers++; // 将顾客排到队伍中，随机一个[1,3]之间的，顾客需要消耗的时间 temp = customertime(cycle); EnQueue(temp, &line); } } // 看看当前时间点，正在处理的顾客处理完了吗 // 如果处理完了，看看还有没有需要处理的顾客(正在排队的顾客) if (wait_time <= 0 && !QueueIsEmpty(&line)) { // 处理完，并且有人排队，就继续处理。。 DeQueue(&temp, &line); // 获取这个顾客需要服务的时间（如果下一位顾客上来询问，就可以告诉他还要等多久。。） wait_time = temp.processtime; // 统计等待时间（根据当前顾客从排队，到接受服务等了多久，然后累加所有顾客的等待时间） line_wait += cycle - temp.arrive; // 统计服务顾客数+1 served++; } // 1分钟过去了，顾客的服务时间消耗掉1分钟。。 if (wait_time > 0) { wait_time--; } // 统计队列长度，如果一直排满10个，这个值会变得较大 sum_line += QueueItemCount(&line); } // 最后输出统计信息 if (customers > 0) { printf("customers accepted: %ld\n", customers); //排到队伍的顾客数 printf("customers served: %ld\n", served); //接受服务的顾客数 printf("turnaways: %ld\n", turnaways); //被拒绝的顾客数 printf("average queue size:%.2f\n", (double)sum_line / cyclelimit); //平均排队长度 printf("average wait time: %.2f minutes\n", (double)line_wait / served); //平均等待时间 } else { puts("No customers!"); } EmptyTheQueue(&line); puts("Bye!"); return 0; } /* x是顾客到来的平均间隔时间(以秒计) 如果这1分钟内有顾客到来，则返回true */ bool newcustomer(double x) { if (rand() * x / RAND_MAX < 1) { return true; } else { return false; } } /* when是顾客到来的时间 函数返回一个Item结构，该结构的顾客到来时间设置为when 需要的咨询时间设置为一个范围1到3之间的随机值 */ Item customertime(long when) { Item cust; cust.processtime = rand() % 3 + 1; cust.arrive = when; return cust; } |
