首页 > 代码库 > 数据结构和算法分析（10）表栈和队列的实际应用（二）
数据结构和算法分析（10）表栈和队列的实际应用（二）
本节继续介绍表、栈、队列在编程实践中的应用。
(1)行编辑程序:(允许用户输入出差错，并在发现错误时可以及时更正。)
功能：接受用户从终端输入的字符型的数据，并存入用户的数据区。由于不能保证不出差错，因此“每接受一个字符即存入用户数据区”的做法不是最恰当的；较好的做法是，设立一个输入的缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区。
算法原理：当用户发现刚刚键入的一个字符是错的时，可补进一个退格符“#”，以表示前一个字符无效；如果发现当前键入的行内差错较多或者难以补救，则可以键入一个退行符“@”，以表示当前行中的字符均无效。
1 #include <stdio.h> 2 3 #define STACK_SIZE 100 //自定义能够临时存储用户输入的字符数 4 #define STACKINCREMENT 10 5 #define OVERFLOW -2 6 typedef char ElemType; 7 struct StackNode{ 8 ElemType *base; 9 ElemType *top;10 int stacksize;11 };12 typedef struct StackNode *TempStack;13 void InitStack(TempStack S,int stackSize);14 void Push(TempStack S,ElemType e);15 void Pop(TempStack S,ElemType *e);16 void DestoryStack(TempStack S);17 void LineEdit(TempStack S);18 void ClearStack(TempStack S);19 20 void InitStack(TempStack S,int stackSize) {21 S->base = (ElemType *)malloc(stackSize*sizeof(ElemType));22 if(!S->base) { 23 printf("内存不足!\n");24 exit(OVERFLOW);25 }26 S->top = S->base;27 S->stacksize = stackSize;28 }29 void Push(TempStack S,ElemType e) {30 //这段话能够使程序有很好的扩容性 31 if((S->top-S->base)>=S->stacksize) {32 S->base = (ElemType*)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(ElemType));33 if(!S->base) {34 exit(OVERFLOW);35 }36 S->top = S->base + S->stacksize;37 S->stacksize += STACKINCREMENT;38 }39 *S->top++ = e;40 }41 void Pop(TempStack S,ElemType *e) {42 if(S->top == S->base) 43 return;44 *e = *--S->top;45 }46 void ClearStack(TempStack S) {47 S->top = S->base;48 }49 void DestoryStack(TempStack S) {50 S->top = S->base;51 free(S->base);52 S->top = NULL;53 S->base = NULL;54 }55 void LineEdit(TempStack S) {56 ElemType *p,ch,c;57 InitStack(S, STACK_SIZE);58 ch = getchar();59 while(ch != EOF) {60 //进行字符入栈操作 61 while(ch!=EOF&&ch!=‘\n‘) {62 switch(ch) {63 case ‘#‘:Pop(S,&c);break;64 case ‘@‘:ClearStack(S);break;65 default:Push(S,ch);break;66 }67 ch = getchar();68 }69 Push(S,ch);//最后的回车也要进入临时区 70 //遍历栈中的字符 71 p = S->base;72 while(p!=S->top) {73 printf("%c",*p);74 ++p;75 }76 ClearStack(S);77 if(ch!=EOF) ch = getchar();78 }79 }80 int main(){81 TempStack sq;82 LineEdit(sq);83 DestoryStack(sq);84 return 0;85 }
一个可调整的地方:
在接受终端输入时，每输入每一行字符(按回车)行编辑程序就自动执行一次，并返回临时栈中所有字符组成的字符串，并再次调用自身，当一行字符为空时程序运行结束。这个程序的缺点在于输出与处理没有分开。
(2)自调整链表:
自调整表如同一个规则的表，但是所有的插入都在表头进行。当一个元素被Find访问时，它就被移到表头而不改变其余项的相对位置。
1)数组实现:
1 /*---------------数组法实现自调整链表---------------*/ 2 #include <stdio.h> 3 #define LIST_SIZE 30 //数组大小 4 typedef char ElemeType; 5 6 struct ListNode{ 7 ElemeType *Array; 8 int num; 9 int Capicity;10 };11 typedef struct ListNode *List; 12 List CreateList(int size){13 List list=malloc(sizeof(struct ListNode));14 list->Array=malloc(size*sizeof(ElemeType));15 list->num=0;16 list->Capicity=size;17 return list;18 }19 void InitList(List list){20 int i;21 for(i=0;i<26;i++){22 list->Array[list->num]=(ElemeType)(‘A‘+list->num);23 list->num++;24 }25 }26 void printList(List list){27 int i;28 for(i=0;i<list->num;i++){ 29 putchar(list->Array[i]);30 putchar(‘ ‘); 31 } 32 }33 void find(ElemeType ch,List list){34 int i;35 for(i=0;i<list->num;i++){36 if(ch==list->Array[i]){37 int j;38 for(j=i;j>0;j--)39 list->Array[j]=list->Array[j-1];40 list->Array[0]=ch; 41 return; 42 }43 }44 printf("链表里没有这个元素%c",ch); 45 }46 int main(){47 List list=CreateList(LIST_SIZE);48 InitList(list); 49 printList(list);50 ElemeType temp[20]={51 ‘B‘,‘Z‘,‘B‘,‘C‘,‘W‘,52 ‘Z‘,‘R‘,‘E‘,‘B‘,‘V‘,53 ‘E‘,‘W‘,‘E‘,‘T‘,‘S‘,54 ‘B‘,‘C‘,‘K‘,‘B‘,‘C‘55 };//B出现5次，E、C出现3次，Z出现2次，W出现2次，R、K、T、V、S各一次56 int i;57 for(i=0;i<20;i++){58 find(temp[i],list);59 }60 printf("\n自调整后的链表是:\n");61 printList(list);62 printf("\n");63 return 0;64 }
2)链表实现:
1 /*---------------链表法实现自调整链表---------------*/ 2 #include <stdio.h> 3 typedef char ElemeType; 4 5 struct ElemeNode{ 6 ElemeType element; 7 struct ElemeNode *next; 8 }; 9 typedef struct ElemeNode *PtrToNode;10 typedef PtrToNode List;11 List createList(){12 List list=malloc(sizeof(struct ElemeNode));13 list->next=NULL;14 return list;15 }16 void InsertIntoList(ElemeType temp,List list){17 PtrToNode ptr=malloc(sizeof(struct ElemeNode));18 ptr->element=temp;19 ptr->next=list->next;20 list->next=ptr;21 }22 23 InitList(List list){24 int i;25 for(i=25;i>=0;i--){26 ElemeType temp=(ElemeType)((int)‘A‘+i);27 InsertIntoList(temp,list); 28 }29 }30 void printList(List list){31 PtrToNode ptr=list->next;32 while(ptr){33 putchar(ptr->element);34 putwchar(‘ ‘);35 ptr=ptr->next;36 }37 }38 int DeleteFromList(ElemeType element,List list){39 PtrToNode ptr=list;40 while(ptr->next->element!=element){41 ptr=ptr->next;42 }43 if(ptr->next==NULL){44 return 0;//没有此元素 45 }else{46 ptr->next=ptr->next->next;47 return 1;48 } 49 }50 void find(ElemeType element,List list){51 if(DeleteFromList(element,list))52 InsertIntoList(element,list);53 else54 printf("没有此元素!\n");55 }56 int main(){57 List list=createList();58 InitList(list);59 printList(list);60 ElemeType temp[20]={61 ‘B‘,‘Z‘,‘B‘,‘C‘,‘W‘,62 ‘Z‘,‘R‘,‘E‘,‘B‘,‘V‘,63 ‘E‘,‘W‘,‘E‘,‘T‘,‘S‘,64 ‘B‘,‘C‘,‘K‘,‘B‘,‘C‘65 };//B出现5次，E、C出现3次，Z出现2次，W出现2次，R、K、T、V、S各一次66 int i;67 for(i=0;i<20;i++){68 find(temp[i],list);69 }70 printf("\n自调整后的链表是:\n");71 printList(list);72 printf("\n");73 return 0; 74 }
(3)用一个数组实现多个栈:(除非数组中的每个单元都被使用否则不能有溢出声明)
算法原理:对与不支持指针的语言(例如java)采用游标法实现表:(与这个例子作对比:http://www.cnblogs.com/MenAngel/p/5539085.html)
1 /*---------------游标模式下栈的实现---------------*/ 2 #include <stdio.h> 3 #include <stdlib.h> 4 #define SpaceSize 60 5 6 typedef int PtrToNode; 7 typedef PtrToNode Stack; 8 typedef PtrToNode Position; 9 10 struct Node{ 11 int Element; 12 int flag;//记录元素出现的次数 13 Position Next;//Next指针指向的不是具体的结点的首地址，而是结点的下标 14 }; 15 //编译时预先分配的结点数组 16 struct Node CursorSpace[SpaceSize]; 17 //CursorSpace[0]是表头指针 18 static void InitialCursor(void){ 19 int i; 20 for(i=0;i<SpaceSize;i++){ 21 CursorSpace[i].Next=i+1; 22 } 23 CursorSpace[i].Next=0; 24 } 25 26 static Position CursorAlloc(void){ 27 Position p; 28 p=CursorSpace[0].Next; 29 CursorSpace[0].Next=CursorSpace[p].Next; 30 CursorSpace[p].Next=0; 31 return p;//当p的值为0时说明没有空间可用了 32 } 33 34 static void CursorFree(Position p){ 35 CursorSpace[p].Next=CursorSpace[0].Next; 36 CursorSpace[0].Next=p; 37 } 38 void InitStack(Stack *S){ 39 PtrToNode p=CursorAlloc(); 40 //新建的结点需要指向头结点 41 CursorSpace[p].Next=0; 42 *S=p; 43 } 44 45 int IsLast(Position p,Stack S){ 46 return CursorSpace[p].Next==0; 47 } 48 void InsertIntoStack(int x,Stack S){ 49 Position TmpCell; 50 TmpCell=CursorAlloc(); 51 if(TmpCell==0){ 52 printf("空间已经使用完，溢出！\n"); 53 //exit(0); 54 return; 55 } 56 CursorSpace[TmpCell].Element=x; 57 CursorSpace[TmpCell].flag=1; 58 CursorSpace[TmpCell].Next=CursorSpace[S].Next; 59 CursorSpace[S].Next=TmpCell; 60 } 61 void printStack(Stack stack){ 62 Position p=stack; 63 Position temp; 64 int i; 65 int w=0; 66 while((temp=CursorSpace[p].Next)!=0){ 67 //printf("%d",CursorSpace[temp].flag); 68 for(i=0;i<CursorSpace[temp].flag;i++){ 69 printf("%3d",CursorSpace[temp].Element); 70 w++; 71 if(w%30==0){ 72 printf("\n"); 73 } 74 } 75 p=CursorSpace[p].Next; 76 } 77 } 78 int main(){ 79 InitialCursor(); 80 Stack stack_a;InitStack(&stack_a); 81 Stack stack_b;InitStack(&stack_b); 82 Stack stack_c;InitStack(&stack_c); 83 Stack stack_d;InitStack(&stack_d); 84 int i; 85 int rand_num; 86 //程序准备的是60个，这里需要4+57=61个空间，一次最后一次操作将会溢出 87 for(i=0;i<=56;i++){ 88 rand_num=rand()%4+1; 89 switch(rand_num){ 90 case 1:InsertIntoStack(i,stack_a);break; 91 case 2:InsertIntoStack(i,stack_b);break; 92 case 3:InsertIntoStack(i,stack_c);break; 93 case 4:InsertIntoStack(i,stack_d);break; 94 default:printf("出现错误\n"); 95 } 96 } 97 printf("栈a中的元素有:\n"); 98 printStack(stack_a); 99 printf("\n栈b中的元素有:\n"); 100 printStack(stack_b); 101 printf("\n栈c中的元素有:\n");102 printStack(stack_c); 103 printf("\n栈d中的元素有:\n");104 printStack(stack_d); 105 printf("\n");106 return 0;107 }
(4)渡轮模拟问题:(队列的实际应用)
有一个渡口，每条渡船能一次性装载10辆汽车过河，车辆分为客车和货车两类。上渡轮有如下规定:
1.同类车辆先到先上船，客车先于货车上船；
2.每上3辆客车才允许上一辆货车，但若等待的客车不足4辆则用货车填补，反过来，若没有货车等待则用客车填补。
3.装满10辆后则自动开船，当等待时间较长时车辆不足10辆也应认为控制发船。
1)c语言版本:
1 /*---------------队列模拟渡轮问题---------------*/ 2 #include <stdio.h> 3 #include <stdlib.h> 4 #include <time.h> 5 #include <string.h> 6 #define YES 1 7 #define NO 0; 8 //采用链表法实现队列 9 struct CarNode{ 10 char name[5];//存车辆的名称 11 int id;//标志车辆的类型 12 struct CarNode *next; 13 }; 14 typedef struct CarNode *Car; 15 struct LinkQueueNode{ 16 Car front; 17 Car rear; 18 int flag; 19 int size;//队列元素的大小 20 }; 21 typedef struct LinkQueueNode *Queue; 22 23 void PrintInfo(){ 24 printf("请输入适当的数字完成特定的任务:\n"); 25 printf("1.---车辆进行登记 "); 26 printf("2.---渡轮进行登记 "); 27 printf("3.---当前排队情况 "); 28 printf("4.---汽车装上渡轮 "); 29 printf("5.---命令渡轮起航 "); 30 printf("6.---结束程序运行 \n"); 31 } 32 void InitQueue(Queue q,int flag){; 33 //让队列拥有一个元素，这个元素不存任何东西 34 q->front=q->rear=malloc(sizeof(struct CarNode)); 35 q->front=q->rear; 36 q->flag=flag; 37 //printf(q->front->name); 38 q->front->id=-1; 39 q->front->next=NULL; 40 q->size=0; 41 } 42 //将车加入队列 43 void EnQueue(Queue q){ 44 Car temp_car=malloc(sizeof(struct CarNode)); 45 if(q->flag==0){ 46 strcpy(temp_car->name,"客车"); 47 temp_car->id=q->size+1; 48 }else{ 49 strcpy(temp_car->name,"货车"); 50 temp_car->id=q->size+1; 51 } 52 temp_car->next=NULL; 53 q->rear->next=temp_car; 54 q->rear=temp_car; 55 q->size++; 56 //printf(q->rear->name); 57 } 58 Car DeQueue(Queue q){ 59 //printf(q->front->name); 60 Car temp_car=q->front->next; 61 q->front->next=q->front->next->next; 62 q->size--; 63 //printf(temp_car->name); 64 //printf("%d出队",temp_car->id); 65 return temp_car; 66 } 67 int IsEmptyQueue(Queue q){ 68 return q->size==0; 69 } 70 void printQueue(Queue temp_queue){ 71 Car temp_car=temp_queue->front->next; 72 while(temp_car!=NULL){ 73 printf(temp_car->name);printf("%d ",temp_car->id); 74 temp_car=temp_car->next; 75 } 76 printf("\n"); 77 } 78 void printBoat(Car *boat,int n){ 79 //printf("已经装到渡轮上的车有:\n"); 80 int i; 81 for(i=0;i<n;i++){ 82 printf(boat[i]->name);printf("%d ",boat[i]->id); 83 } 84 printf("\n"); 85 } 86 int main(){ 87 int flag=0;//用来接收用户输入的命令数字 88 int mark=NO;//mark标志渡轮是否已经到渡口 89 long t1,t2;//分别记录渡轮到达渡口和离开渡口的时间 90 //这里出现一个错误 91 Queue queue_human=malloc(sizeof(struct LinkQueueNode)); 92 Queue queue_thing=malloc(sizeof(struct LinkQueueNode)); 93 Car boat[10];//用数组记录渡轮上每个汽车的汽车号，和已经装的车数 94 int n; 95 InitQueue(queue_human,0); 96 InitQueue(queue_thing,1); 97 while(1){ 98 //1.显示功能菜单: 99 L: PrintInfo();100 do{101 scanf("%d",&flag);102 getchar();103 if(flag<1||flag>6)104 printf("功能%d没有被定义，请重新输入\n"); 105 }while(flag<1||flag>6);106 //将每个数字对应的功能实现 107 switch(flag){108 //将等待装船的各种车放在各自等待的队列中 109 case 1:{110 int num;int i;111 printf("此时间段有多少辆客车到达港口:\n");112 scanf("%d",&num);getchar(); 113 for(i=0;i<num;i++){114 EnQueue(queue_human); 115 }116 printf("此时间段有多少辆货车到达港口:\n");117 scanf("%d",&num);getchar(); 118 for(i=0;i<num;i++){119 EnQueue(queue_thing); 120 } 121 }break;122 //标记此事是否有渡船已到达港口 123 case 2:{124 if(mark==YES){125 printf("已经有渡船在渡口等待!\n");126 break;127 }128 mark=YES;129 printf("渡口来了一只船，车辆可以装船。\n");130 n=0;131 t1=time(0);132 }break; 133 case 3:{134 printf("等待过江的客车有:\n");135 printQueue(queue_human);136 printf("等待过江的货车有:\n");137 printQueue(queue_thing);138 }break; 139 case 4:{140 //当队列为空，已有轮渡在准备 141 if(IsEmptyQueue(queue_thing)&&IsEmptyQueue(queue_human)){142 printf("暂无车辆准备过河");143 if(mark==1&&n>0&&n<10){144 t2=time(0);145 long t=t2-t1;//渡轮到目前为止等待的秒数; 146 printf("轮渡未满,有%d辆车已经装船，等待其他汽车上渡轮,并且已经等待%d分%d秒。",n,t/60,t%60); 147 }148 break; 149 }150 //当没有轮渡时 151 if(mark!=1){152 printf("渡轮未到，请汽车稍后上渡轮");153 break; 154 }155 do{156 int temp_num=0;157 //printf("n=%d\n",n);158 //当有轮渡且队列不为空时159 //先上4辆客车 160 while(!IsEmptyQueue(queue_human)&&n<10&&temp_num<4){161 //printf("\n%d,%d\n",temp_num,n);162 boat[n]=DeQueue(queue_human);n++;163 //printBoat(boat,n);164 temp_num++;165 }166 //如果满10辆，自动开船，转到功能菜单167 if(n==10){168 printf("轮渡开走!\n");169 printBoat(boat,n);170 mark=0;171 n=0;172 goto L;173 }174 //如果未满10辆，判断4辆客车的名额是否用满，未用满用货车补175 if(temp_num==4){176 if(!IsEmptyQueue(queue_thing)){177 boat[n]=DeQueue(queue_thing);n++;178 temp_num++;179 }180 }181 else{182 //这里连货车的名额一块加上了，所以是小于5 183 while(!IsEmptyQueue(queue_thing)&&temp_num<5&&n<10)184 boat[n]=DeQueue(queue_thing);n++;185 printf(boat[temp_num]->name);186 temp_num++; 187 }188 if(n==10){189 printf("轮渡起航，载的车辆有:\n");190 printBoat(boat,n);191 mark=0;192 n=0;193 goto L;194 } 195 }while(!IsEmptyQueue(queue_human)||!IsEmptyQueue(queue_thing));196 }break;197 case 5:{198 if(n==0||mark==0)199 printf("轮渡上没有车过江或者港口没有渡轮！不能起航!\n");200 else{201 printf("轮渡起航，载的车辆有:\n");202 printBoat(boat,n);203 mark=NO;n=0;204 } 205 }break; 206 case 6:{207 if(!IsEmptyQueue(queue_human)||!IsEmptyQueue(queue_thing)){208 printf("还有汽车未渡江，暂且不能结束!\n");209 break;210 }211 if(n!=0){212 printf("渡轮上还有车,暂且不能结束!\n");213 break;214 }215 printf("程序运行结束\n");216 return 0; 217 }break; 218 default:printf("不知名错误!\n");break; 219 } 220 } 221 }
2)c++版:
c++版将会在后续的c++系列中涉及，用面向对象的思想解决。
(5)队列的离散时间模拟:
银行业务的模拟程序:
1.有多个窗口对外接待客户。(模拟时指定为4个)
2.从银行开门不断有客户进入银行。
3.对于刚进银行的客户，如果有空闲窗口则上前办理业务，否则插在最短队列后。
4.不考虑顾客中途离开，顾客到达事件随机，业务办理时间。
求在这一事件驱动模拟过程中客户在银行的平均逗留时间。
1 /*---------------模拟银行营业时的排队情况---------------*/ 2 #include <stdio.h> 3 #include <time.h> 4 #include <stdlib.h> 5 6 #define OK 1 7 #define ERROR 0 8 #define TRUE 1 9 #define FALSE 0 10 11 typedef int Status; 12 typedef struct Event{ 13 int OccurTime;//事件发生时刻 14 int NType;//事件类型，0表示到达事件，1至4表示四个窗口的离开事件 15 struct Event *next; 16 }Event,ElemType; 17 typedef struct{//单向链表结构 18 ElemType *head;//头指针 19 ElemType *tail;//尾指针 20 int len;//长度 21 }LinkList; 22 typedef LinkList EventList; //事件链表 23 typedef struct QElemType{ //队列元素 24 int ArriveTime;//到达时间 25 int Duration;//办理业务所需时间 26 struct QElemType *next; 27 }QElemType; 28 typedef struct{//队列结构 29 QElemType *head;//头指针 30 QElemType *tail;//尾指针 31 }LinkQueue; 32 33 /*-----全局变量-----*/ 34 EventList ev; 35 Event en; 36 LinkQueue q[5]; 37 QElemType customer; 38 int TotalTime,CustomerNum; 39 int CloseTime=50;//关闭时间，即营业时间长度 40 41 Event NewEvent(int occurT,int nType);//根据OccurTime和NType值，创建新事件 42 Status InitList(LinkList *L);//初始化事件链表 43 Status OrderInsert(LinkList *L,Event e);//将事件e按发生时间顺序插入有序链表L中 44 Status ListEmpty(LinkList *L);//判断链表L是否为空，为空返回TRUE，否则返回FALSE 45 Status DelFirst(LinkList *L,ElemType *e);//链表L不为空，删除其首结点，用e返回，并返回OK；否则返回ERROR 46 Status ListTraverse(LinkList *L);//遍历链表 47 Status InitQueue(LinkQueue *Q);//初始化队列Q 48 Status EmptyQueue(LinkQueue *Q);//若队列Q为空，返回TRUE，否则返回FALSE 49 Status DelQueue(LinkQueue *Q,QElemType *e);//若队列Q不为空，首结点出队，用e返回，并返回OK；否则返回ERROR 50 Status EnQueue(LinkQueue *Q,QElemType e);//结点e入队Q 51 int QueueLength(LinkQueue Q);//返回队列Q的长度，即元素个数 52 Status GetHead(LinkQueue *Q,QElemType *e);//若队列Q不为空，用e返回其首结点，并返回OK,否则返回ERROR 53 Status QueueTraverse(LinkQueue *Q);//遍历队列Q 54 int Min(int a[],int n); //返回长度为n的数组a第一个最小值的下标，从1开始 55 int ShortestQueue();//获取最短队列的编号 56 void OpenForDay();//初始化操作 57 void CustomerArrived();//顾客达到事件 58 void CustomerDepature();//顾客离开事件 59 void Bank_Simulation();//银行排队模拟 60 void PrintEventList();//输出事件队列 61 void PrintQueue();//打印当前队列 62 63 void PrintQueue(){ 64 int i; 65 for(i=1;i<=4;i++){ 66 printf("Queue %d have %d customer(s):",i,QueueLength(q[i])); 67 QueueTraverse(&q[i]); 68 } 69 printf("\n"); 70 } 71 void PrintEventList(){ 72 printf("Current Eventlist is：\n"); 73 ListTraverse(&ev); 74 } 75 int Min(int a[],int n){ 76 //返回长度为n的数组a第一个最小值的下标，从0开始 77 int i,tmp,ind=0; 78 tmp=a[0]; 79 for(i=1;i<n;i++){ 80 if(a[i]<tmp){ 81 tmp=a[i]; 82 ind=i; 83 } 84 } 85 return ind; 86 } 87 int ShortestQueue(){ 88 int i,a[4]; 89 for(i=1;i<=4;i++){ 90 a[i-1]=QueueLength(q[i]); 91 //printf("队%d的长度为%d\n",i,QueueLength(q[i])); 92 } 93 return Min(a,4)+1;//队列从1开始编号 94 } 95 96 Event NewEvent(int occurT,int nType){ 97 Event e; 98 e.OccurTime=occurT; 99 e.NType=nType;100 return e;101 }102 Status ListTraverse(LinkList *L){103 //遍历链表104 Event *p=L->head->next;105 if(!p){106 printf("List is empty.\n");107 return ERROR;108 }109 while(p!=NULL){110 printf("OccurTime:%d,Event Type:%d\n",p->OccurTime,p->NType);111 p=p->next;112 }113 printf("\n");114 return OK;115 }116 Status InitQueue(LinkQueue *Q){117 //初始化队列Q118 Q->head=Q->tail=(QElemType *)malloc(sizeof(QElemType));119 if(!Q->head){120 printf("Apply for memory error.LinkQueue initialize failed.\n");121 exit(0);122 }123 Q->head->next=NULL;124 return OK;125 }126 Status EmptyQueue(LinkQueue *Q){127 //若队列Q为空，返回TRUE，否则返回FALSE128 if(Q->head==Q->tail&&Q->head!=NULL)129 return TRUE;130 else131 return FALSE;132 }133 Status DelQueue(LinkQueue *Q,QElemType *e){134 //若队列Q不为空，首结点出队，用e返回，并返回OK；否则返回ERROR135 QElemType *p=Q->head->next;136 if(!p)137 return ERROR;138 *e=*p;139 Q->head->next=p->next;//修正队首指针140 free(p);141 if(!Q->head->next)//队空142 Q->tail=Q->head;143 return OK;144 }145 Status EnQueue(LinkQueue *Q,QElemType e){146 //结点e入队Q147 QElemType *p=(QElemType *)malloc(sizeof(QElemType));148 if(!p){149 printf("Apply for memory error,new element can‘t enqueue.\n");150 exit(0);151 }152 *p=e;153 p->next=NULL;154 Q->tail->next=p;//插入队尾155 Q->tail=p;//修改队尾指针156 return OK;157 }158 int QueueLength(LinkQueue Q){159 //返回队列Q的长度，即元素个数160 int count=0;161 QElemType *p=Q.head->next;162 while(p){163 p=p->next;164 count++;165 }166 return count;167 }168 Status GetHead(LinkQueue *Q,QElemType *e){169 //若队列Q不为空，用e返回其首结点，并返回OK,否则返回ERROR170 if(EmptyQueue(Q))171 return ERROR;172 *e=*(Q->head->next);173 return OK;174 }175 Status QueueTraverse(LinkQueue *Q){176 //遍历队列Q177 QElemType *p=Q->head->next;178 if(!p){179 printf("--Is empty.\n");180 return ERROR;181 }182 while(p){183 printf("(%d,%d) ",p->ArriveTime,p->Duration);184 p=p->next;185 }186 printf("\n");187 return OK;188 }189 Status InitList(LinkList *L){190 L->head=L->tail=(ElemType *)malloc(sizeof(ElemType));191 if(!L->head){192 printf("Apply for memory error.LinkList initialize failed.\n");193 exit(0);194 }195 L->head->next=NULL;196 return OK;197 }198 Status OrderInsert(LinkList *L,Event e){199 ElemType *p,*q,*newptr;200 newptr=(ElemType *)malloc(sizeof(ElemType));201 if(!newptr){202 printf("Apply for memory error，new node can‘t insert intot the Eventlist.\n");203 exit(0);204 }205 *newptr=e;206 if(TRUE==ListEmpty(L)){//链表为空207 L->head->next=newptr;208 L->tail=newptr;209 L->tail->next=NULL;210 return OK;211 }212 q=L->head;213 p=L->head->next;214 while(p){//遍历整个链表215 if(p->OccurTime>=newptr->OccurTime)216 break;217 q=p;218 p=p->next;219 }220 q->next=newptr;221 newptr->next=p;222 if(!p)//插入位置为链表尾部223 L->tail=newptr;224 return OK;225 }226 void OpenForDay(){227 //初始化操作228 int i;229 TotalTime=0; CustomerNum=0;230 InitList(&ev);//初始化事件队列231 en.OccurTime=0;232 en.NType=0;233 OrderInsert(&ev,en);234 for(i=1;i<=4;i++)235 InitQueue(&q[i]);//初始化四个窗口队列236 }237 Status ListEmpty(LinkList *L){238 //判断链表L是否为空，为空返回TRUE，否则返回FALSE239 if((L->head==L->tail)&&(L->head!=NULL))240 return TRUE;241 else242 return FALSE;243 }244 Status DelFirst(LinkList *L,ElemType *e){245 //链表L不为空，删除其首结点，用e返回，并返回OK；否则返回ERROR246 ElemType *p=L->head->next;247 if(!p)248 return ERROR;249 L->head->next=p->next;250 *e=*p;251 free(p);252 if(L->head->next==NULL)253 L->tail=L->head;254 return OK;255 }256 void CustomerArrived(){257 //顾客达到事件258 int durtime,intertime,i,t;259 QElemType e;260 ++CustomerNum;261 intertime=rand()%5+1;//间隔时间在5分钟内262 durtime=rand()%30+1;//办理业务时间在30分钟内263 t=en.OccurTime+intertime;264 if(t<CloseTime){//银行尚未关门265 printf("A new customer will arrive at:%d\n",en.OccurTime);//下一位顾客达到时间266 OrderInsert(&ev,NewEvent(t,0));267 i=ShortestQueue();//最短队列268 e.ArriveTime=en.OccurTime;269 e.Duration=durtime;270 EnQueue(&q[i],e);271 if(QueueLength(q[i])==1)272 OrderInsert(&ev,NewEvent(en.OccurTime+durtime,i));273 }274 }275 void CustomerDepature(){276 int i=en.NType;277 DelQueue(&q[i],&customer);278 printf("A customer leaves at:%d\n",en.OccurTime);//输出顾客离开时间279 TotalTime+=en.OccurTime-customer.ArriveTime;280 if(!EmptyQueue(&q[i])){281 GetHead(&q[i],&customer);282 OrderInsert(&ev,NewEvent(en.OccurTime+customer.Duration,i));283 }284 }285 void Bank_Simulation(){286 OpenForDay();287 srand((unsigned)time(NULL));288 while(!ListEmpty(&ev)){289 DelFirst(&ev,&en);//取出一个事件给en 290 if(en.NType==0)291 CustomerArrived();292 else293 CustomerDepature();294 //PrintEventList();295 //PrintQueue();296 }297 printf("Total time is: %d min,average time is: %g min.\n",TotalTime,(float)TotalTime/CustomerNum);298 }299 int main(){300 Bank_Simulation();301 return 0;302 }
这里还有一个地方模拟的不准确:
这个程序做到了在营业时间内允许用户到达队列，在营业时间以外，正在办理的用户需要完成办理业务，而已经在队列中的客户需要被迫离开。
数据结构和算法分析（10）表栈和队列的实际应用（二）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。