第10章 栈和队列 计算机软件技术基础教程 教学课件

10.1栈

10.2栈的应用10.3队列 10.4队列应用举例

第10章栈和队列

返回主目录第10章栈和队列10.1栈

10.1.1栈的基本概念及其运算栈是被限定仅在表尾进行插入和删除运算的线性表。我们把表尾称为栈顶；表头称为栈底。当栈中没有数据元素时称为空栈。例如，线性表S为：S=(a0，a1，…，an)当我们把它看作栈来使用时，可以形象地描述为图10.1所示的形式。其中，a1是栈底元素，an是栈顶元素，入栈是指插入数据元素，出栈是指删除数据元素。图10.1栈的示意图从图10.1中可以看出，进栈是把数据元素放在栈顶，即最后进栈的数据元素在栈顶，而出栈是把栈顶的数据元素删除。因此，对于栈来说，最后进栈的数据元素最先出栈，故把栈称为后进先出(LIFO-LastInFirstOut)的数据结构，或先进后出(FILO-FirstInLastOut)的数据结构。栈的常用运算有以下五种：(1)置空栈——SetNull(S)，完成对栈的初始化。(2)判断栈是否为空——Empty(S)，若栈S为空，则返回真；否则，返回假。(3)进栈——Push(S，e)，在栈S的栈顶插入数据元素e。(4)出栈——Pop(S)，删除栈S的栈顶数据元素，并把出栈数据元素返回。(5)取栈顶元素——GetTop(S)，取栈S的栈顶数据元素，并把数据元素返回。该操作完成后，栈的状态不变。

10.1.2栈的存储结构栈的存储结构有两种：顺序存储结构和链式存储结构。

1.栈的顺序存储结构——顺序栈栈是一种特殊的线性表，因此可以用线性表的方法来存储栈。最简单的方法是用一维数组来存储。由于栈底是固定不变的；而栈顶是随进栈出栈操作动态变化的，因此为了实现对栈的操作，必须记住栈顶的当前位置。另外，对于栈来说，是有容量限制的。鉴于以上考虑我们把栈的顺序存储结构定义为：structStack{ datatypeelements[maxsize]； intTop；}其中，maxsize是栈的容量，datatype是栈中数据元素的数据类型，Top指示当前栈顶位置，栈底位置为0。在此定义下，我们来讨论栈的运算。图10.2说明了栈中数据元素和栈顶位置的关系。(1)置空栈：将栈进行初始化，主要是将栈顶指针Top初始化为–1。voidSetNuLLS(structStack*S){ S－>Top=–1；} /SetNuLLS/(2)判断栈是否为空：在进行出栈操作时，首先必须判断栈不为空，否则会出错。intEmptyS(structStack*s){ if(S－>Top>=0)return(0)； elsereturn(1)；} /*EmptyS*/(3)进栈：将数据元素E插入栈顶。structStack*PushS(structStack*S,datatypeE){if(S－>Top>=maxsize-1){printf("StackOverflow")； /上溢现象。/return(NULL)；}else{S－>Top++； S－>elements[S－>Top]=E； }return(s)；} /*PushS*/(4)出栈：首先判断栈是否为空，若空则表示下溢，否则删除栈顶数据元素。datatypePOPS(structStack*S){datatype*temp; if(EmptyS(S)){printf("StackUnderflow")；return (NULL)；}else{STop--; temp=(datatype*)malloc(sizeof(datatype));*temp=S－>elements[S－>Top+1];return(temp);}}/*PopS*/(5)取栈顶元素：只把栈顶元素的值取出，而不调整栈顶指针Top的值。datatype*GetTopS(structStack*S){datatype*temp;if(EmptyS(S)){printf("Stackisempty")；return (NULL)；}else{temp=(datatype*)malloc(sizeof(datatype));*temp=S－>elements[S－>Top];return (temp);}} /*GetTopS*/在前面的栈运算中，进栈运算采用Top指针加1后再插入数据元素，若采用先插入数据元素再使Top指针加1，那么以上五种运算该如何实现呢？请读者自行写出算法。对于顺序栈来说，其最大缺点是：当栈的容量不固定时，必须设置栈可容纳最多的数据元素作为栈的容量，这样就会浪费很多存储空间，也可能产生上溢现象。采用链式存储结构就不会产生类似的问题。栈的链式存储结构称为链栈。它是运算受限的单链表，其插入和删除操作仅在表头进行。链栈定义如下：structNode{datatypeelement; structNode*next;};structNode*top;图10.3是链栈示意图。栈顶是top指针，它惟一地确定一个链栈。当top等于NULL时，该链栈为空栈。下面仅给出链栈的出栈和进栈运算，其他运算请读者自行完成。voidPushL(structNode*S,datatypeE){structNode*p; /*进栈*/p=(structNode*)malloc(1,sizeof(structNode));p－>element=E;p－>next=S;S=p;}top /*PushL图10.3链栈的示意图datatypePopL(structNode*S) /*出栈*/{datatype*X; if(S==NULL){printf("Stackisunderflow"); return(NULL);}else{ X=(datatype*)malloc(sizeof(datatype));* X=S－>element; S=S－>next; return(X); } } /*PopL*/10.2栈的应用

10.2.1递归调用由于过程嵌套和递归调用属同一类型问题，因此，我们仅以递归调用为例来说明栈在第二类应用中的作用。递归调用是指一个过程（函数）通过调用语句直接或间接调用自身的过程。下面以计算Fibonacci序列为例来说明栈在递归调用中的作用。Fibonacci序列定义为： 0(n=0)Fib(n)=1(n=1)Fib(n-1)+Fib(n-2)(n>1)该计算过程的算法描述如下：intFib(intn){intfib；if(n==0)fib=0; else if(n==1)fib=1; elsefib=Fib(n-1)+Fib(n-2); return(fib);} /*Fib*/当n=5时，递归执行过程如图10.4所示。图10.4递归执行过程栈在该递归调用的执行过程中用来存放每次调用中产生的中间结果。栈的变化过程如图10.5所示。图10.5递归调用过程中栈的变化

10.2.2地图染色问题地图染色问题，可以根据四色定理来解决。四色定理是指可以用不多于四种的颜色对地图着色，使相邻的行政区域不重色。我们应用这个定理的结论，用回溯算法对一幅给定的地图染色。假设已知地图的行政区如图10.6所示，对每个行政区编号分别是(1)、(2)、(3)、(4)、(5)、(6)、(7)。同时用1#、2#、3#、4#表示各行政区的颜色。算法的基本思想是：从第(1)号行政区域开始染色，每个区域逐次用颜色1#、2#、3#、4#进行试探，若当前所取的颜色与周围已染色的行政区域不重色，则用栈记下该区域的颜色序号，

否则依次用下一颜色进行试探；若出现用1#到4#颜色均与相邻区域的颜色重色，则需退栈回溯，修改当前栈顶的颜色序号，再进行试探。直到所有行政区域都已分配合适的颜色。在计算机上实现此算法时，用一个关系矩阵R[n][n]来描述各行政区域间的相邻关系：1，行政区域i+1和j+1间是相邻的R[i][j]=0，行政区域i+1和j+1间是不相邻的除R之外，还需设置一个栈S，用来记录行政区域所染颜色的序号：S[i]=k表示行政区域i+1所染颜色的序号为k，k是1#、2#、3#、4#之一。图10.6行政区域的关系矩阵如图10.7所示。该算法用C语言实现如下：voidmapcolor(intR[][],intn,intS[]){intcolor，area，k；S[0]=1;/*第(1)行政区域染1#号颜色*/area=1;/*从第(2)行政区域开始试探染色*/color=1;/*从第1#号颜色开始试探*/图10.7关系矩阵Rwhile(area<n){ while(color<=4){k=0; /*指示已染色区域*/while((k<area)&&(S[k]*R[area][k]!=color)){k++;/*判断当前area区域与k区域是否重色，并找k区域能染的颜色*/}if(k<area)color++; /*area区域与k区域重色*/else{/*area区域与k区域不重色，再试探下一个行政区域*/S[area]=color;area++;color=1;}} /*while(color<=4)end*/if(color>4) /*area区域找不到合适的颜色*/{area-=1; /*回溯并修改area-区域所用颜色*/color=s[area]+1;}}} /*mapcolor*/输入图10.7所示的R矩阵，n为7，S为S[7]，则该算法运行过程中栈S的变化过程如图10.8所示。mapcolor在运行过程中，当area=5时，即对第(6)行政区染色时，无论color为1#、2#、3#、4#中的哪一个，都会产生与相邻区域重色的问题，这时必须修改栈顶的颜色，图10.8运行过程中栈S的变化过程而第(5)行政区的颜色为4#，已不存在与其他区域不重色的颜色，故需继续退栈(回溯)，变更第(4)行政区的颜色4#，由此，第(5)区的染色为3#，但仍无法对第(6)行政区染色，再次退栈，直至将第(3)行政区染为颜色3#时才能求得所有行政区的染色。在第8章中，给出交通灯设置问题，利用以上介绍的方法可以完成交通灯的设置，请读者自己动手试一试。10.3队列10.3.1队列的基本概念和运算队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(Front)，允许插入的一端称为队尾(Rear)。队列同现实生活中排队相仿，新来的成员总是加入队尾(即不允许“加塞”)，每次离开的成员总是队列头上的(即不允许中途离队)，即当前“最老的”成员离队。换而言之，先进入队列的成员总是先离开队列。因此队列亦称作先进先出(FirstInFirstOut)的线性表，简称为FIFO表。当队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,…,an之后，a1是队头元素，an是队尾元素。显然出队的次序也只能是a1,a2,…,an,也就是说队列的改变是依先进先出的原则进行的。图10.9是队列的示意图。队列的基本运算有以下五种：(1)SetNull(Q):置Q为一个空队列。(2)Empty(Q):判断队列Q是否为空队列。当Q是空队列时，返回“真”值，否则返回“假”值。(3)Front(Q):取队列Q的队头元素，队列中元素保持不变。(4)Enqueue(Q,x):将元素x插入队列Q的队尾,称为入队(列)。(5)Dequeue(Q):删除队列Q的队头元素，简称为出队(列)。函数返回原队头元素。图10.9队列示意图

10.3.2队列的存储结构

1.顺序队列队列的顺序存储结构称为顺序队列。顺序队列实际上是运算受限的顺序表，和顺序表一样，顺序队列也必须用一个数组来存放当前队列中的元素。由于队列的队头和队尾的位置均是变化的，因而需要设置两个指针，分别指示当前队头元素和队尾元素在数组中的位置。顺序队列的类型sequeue和一个实际的顺序队列指针sq可以说明如下：structsequeue{datatypedata[maxsize];intfront，rear;}; /*顺序队列的类型*/sequeuesq /*sq是顺序队列的指针*/为方便起见，我们规定头指针front总是指向当前队头元素的前一个位置，尾指针rear指向当前队尾元素的位置。一开始，队列的头、尾指针指向向量空间下界的前一个位置，在此设置为–1。若不考虑溢出，则入队运算可描述为：图10.10说明了在顺序队列中进行出队和入队运算时队列中的数据元素及其头、尾指针的变化情况。显然，当前队列中的元素个数(即队列的长度)是(sqrear)－(sqfront)。若sqfront=sqrear，则队列长度为0，即当前队列是空队列，如图10.10(a)和10.10(c)均表示空队列。队列为空时再做出队操作便会产生“下溢”。队满的条件是当前队列长度等于向量空间的大小，即：sq－>rear++; /*尾指针加1*/sq－>data[sq－>rear]=x; /*x入队*/出队运算可描述为：sq－>front++; /*头指针加1*/图10.10顺序队列运算时的头、尾指针变化情况(sq－>rear)－(sq－>front)=maxsize当队列满时，再进行入队操作会产生“上溢”。但是如果当前尾指针等于数组的上界(即sqrear=maxsize–1)时，即使队列不满(即当前队列长度小于maxsize)，再进行入队操作也会引起溢出。例如，若图10.10(d)是当前队列的状态，即maxsize=5，sqrear=4，sqfront=2，因为sqrear+1>naxsize–1，故此时不能做入队操作，但当前队列并不满，我们把这种现象称为“假上溢”。产生该现象的原因是被删元素的空间在该元素被删除以后就永远使用不到。为克服这一缺点，可以在每次出队时将整个队列中的元素向前移动一个位置，也可以在发生假上溢时将整个队列中的元素向前移动直至头指针为–1，但这两种方法都会引起大量元素的移动，所以在实际应用中很少采用。图10.11循环队列示意图通常采用的方法是：设想向量sqdata[maxsize]是一个首尾相接的圆环，即sqdata[0]接在sqdata[maxsize–1]之后，我们将这种意义下的队列称为循环队列，如图10.11所示。若当前尾指针等于数组的上界，则再做入队操作时，令尾指针等于数组的下界，这样就能利用到已被删除的元素空间，克服假上溢现象。因此入队操作时，在循环意义下的尾指针加1操作可描述为：if(sq－>rear+1>=maxsize)sq－>rear=0;elsesq－>rear++;如果利用“模”运算，上述循环意义下的尾指针加1操作，可以更简洁地描述为：sq－>rear=(sq－>rear+1)％maxsize同样，出队操作时，在循环意义下的头指针加1操作，也可利用“模”运算来实现：sq－>front=(sq－>front+1)％maxsize因为出队和入队分别要将头指针和尾指针在循环意义下加1，所以某一元素出队后，若头指针已从后面追上尾指针，即sqfront=sqrear，则当前队列为空；若某一元素入队后，如果利用“模”运算，上述循环意义下的尾指针加1操作，可以更简洁地描述为：sq－>rear=(sq－>rear+1)％maxsize同样，出队操作时，在循环意义下的头指针加1操作，也可利用“模”运算来实现：sq－>front=(sq－>front+1)％maxsize因为出队和入队分别要将头指针和尾指针在循环意义下加1，所以某一元素出队后，若头指针已从后面追上尾指针，即sqfront=sqrear，则当前队列为空；若某一元素入队后，尾指针已从后面追上头指针，即sqrear=sqfront，则当前队列为满。因此，仅凭等式sqfront=sqrear是无法区别循环队列是空还是满的。对此，有两种解决的办法：其一是引入一个标志变量以区别是空队列还是满队列；另一种更为简单的办法是入队前测试尾指针在循环意义下加1后是否等于头指针，若相等则认为是队满，即判别队满的条件是：(sq－>rear+1)％maxsize==sq－>front从而保证了sqrear==sqfront是队空的判别条件。应当注意，这里规定的队满条件使得循环向量中始终有一个元素的空间(即sqdata[sqfront])是空闲的，即maxsize个分量的循环向量只能表示长度不超过maxsize–1的队列。这样做避免了由于判别另设的标志而造成时间上的损失。在循环队列上实现的五种基本运算如下：1)置空队voidSetNullQS (sequeue*sq)/*置队列sq为空队*/{sq－>front=maxsize－1;sq－>rear=maxsize－1;} /*SetNullQS*/该算法中，令初始的队头、队尾指针等于maxsize-1，是因为循环向量中位置maxsize–1是位置0的前一个位置，当然也可将初始的队头、队尾指针置为–1。2)判队空intEmptyQS(sequeue*sq)/*判别队列sq是否为空*/{if(sq－>rear==sq－>front)return(1);elsereturn(0);} /*EmptyQS*/3)取队头元素datatype*FrontQS(sequeue*sq)/*取队列sq的队头元素*/{datatype*tmp; if(EmptyQS(sq){ printf("queueisempty");returnNULL;}else{tmp=(datatype*)malloc(sizeof(datatype));*tmp=sq－>data[(sq－>front+1)％maxsize];return(tmp);}} /*FrontQS*/注意：因为队头指针总是指向队头元素的前一个位置，所以上述算法中返回的队头元素是当前头指针的下一个位置上的元素。4)入队intEnqueueQS(sequeue*sq,datatypex)/*将新元素x插入队列sq的队尾*/{if(sq－>front==(sq－>rear+1)％maxsize){printf("queueisfull");return(0);}/*队满上溢*/else{sq－>rear=(sq－>rear+1)％maxsizesq－>data[sq－>rear]=x;return(1); }} /*EnqueueQS*/5)出队datatype*DequeueQS(sequeue*sq) /*删除队列sq的头元素，并返回该元素*/{datatype*tmp; if(EmptyQS(sq)){printf("queueisempty");returnNULL;}/*队空下溢*/else{tmp=(datatype*)malloc(sizeof(datatype));sq－>front=(sqfront+1)％maxsize;*tmp=sq－>data[sq－>front];return(tmp); }}

2.链队列队列的链式存储结构简称为链队列，它是被限制仅在表头删除并仅在表尾插入的单链表。显然仅有单链表的头指针不便于在表尾进行插入操作，为此再增加一个尾指针，指向链表上的最后一个结点。于是，一个链队列由一个头指针和一个尾指针惟一地确定。和顺序队列类似，我们也是将这两个指针封装在一起，将链队列的类型linkqueue定义为一个结构类型：typedefstruct{ linklist*front,*rear;}linkqueue;linkqueueq; /*q是链队列指针*/和单链表一样，为了运算方便，我们也在队头结点前附加一个头结点，且头指针指向头结点。由此可知，一个链队列q为空时(即qfront=qrear)，其头指针和尾指针均指向头结点。链队列的示意图如图10.12所示。在链队列上实现的五种基本运算如下：1)置空队voidSetNullQL(linkqueueq)/*生成空链队列q*/{ q－>front=malloc(sizeof(linklist));/*申请头结点*/ q－>front－>next=NULL;/*尾指针也指向头结点*/ q－>rear=q－>front;} /*SetNullQL*/图10.12链队列示意图2)判队空intEmptyQL(linkqueue*q)/*判别队列q是否为空*/{if(q－>front==q－>rear) return(1);/*空队列返回“真”*/elsereturn(0);} /*EmptyQL*/3)取队头结点数据datatype*FrontQL(linkqueue*q)/*取出链队列q的队头元素{if(EmptyQL(q)) /*队列空*/{ printf("queueisempty");returnNULL;}elsereturn(q－>front－>next); /*返回队头元素*/} /*FrontQL*/4)入队voidEnqueueQL(linkqueue*q,datatypex)/*将结点x加入队列q的尾端*/{q－>rear－>next=malloc(sizeof(linklist));/*新结点插入尾端*/q－>rear=q－>rear－>next;/*尾指针指向新结点*/q－>rear－>data=x;/*给新结点赋值*/q－>rear－>next=NULL;}/*EnqueueQL*/5)出队datatype*DequeueQL(linkqueue*q) /*将队头元素删除*/{datatype*tmp;if(EmptyQL(q)){ printf("queueisempty"); returnNULL;}else{s=q－>front－>next; /*指向被删除的头结点*/if(s－>next==NULL)/*当前链队列的长度等于1*/{q－>front－>next=NULL;q－>rear=q－>front; }else/*当前链队列的长度大于1*/{q－>front－>next=s－>next;/*修改头结点的指针*/}tmp=(datatype*)malloc(sizeof(datatype));*tmp=s－>datareturn(tmp); /*返回被删除结点的值*/}} /*DequeueQL*/若当前链队列的长度大于1，则出队操作只要修改头结点指针域即可，尾指针不变。当然，若要返回被删的队头元素，在释放结点*s之前，还应该保存*s的数据。若当前链队列的长度等于1，则出队操作时，除修改头结点的指针域外，还应该修改尾指针，这是因为此时尾指针也是指向被删结点的，在该结点被删除之后，尾指针应指向头结点。10.4队列应用举例

10.4.1离散事件仿真人们在日常社会生活中时常会通过排列以得到各种社会服务，例如银行业务系统、各种票证出售系统等。这种服务系统设有若干窗口，用户可以在营业时间内随时前去。如果当时有空闲窗口，可以立即得到服务；若窗口均有用户占用，则需排在人数最少的队列后面。由于用户的到达时间、服务时间等均为随机的事件，特别是用户到达的时间是离散的，故称为离散事件。现要编制一个程序来模拟这种活动，并计算一天中用户在此逗留的平均时间。为了计算平均时间，要求掌握每个用户的到达时间和离开时间。

1.具体问题假设服务系统有四个窗口对外接待客户，在营业时间内不断有客户进入并要求服务。由于每个窗口只能接待一个客户，因此进入该服务系统的客户需在某一窗口前排队。如果窗口的服务员忙，则进入的客户需排队等待，闲则可立即服务，服务结束则从队列中撤离。并计算一天中进入服务系统的客户的平均逗留时间。

2.分析为了模拟四窗口服务系统必须有四个队列与每一个窗口相对应，并能反映每一窗口当前排队的客户数。当有一个客户到达时，则排在队列最短的窗口等待服务。当有一个客户服务完毕，则离开相应的窗口，从队列中撤离。为了计算平均逗留时间，则必须记录客户的到达时间和离开时间。因此，影响系统队列变化的原因以下有两种：(1)新客户进入服务系统，该客户加入到队列最短的窗口队列中。(2)四个队列中有客户服务完毕而撤离。这两种原因共有五种情况，我们把这五种情况称为事件。由于这些事件是离散发生的，故称为离散事件。这些事件的发生是有先后顺序的，依次构成事件表。在该服务系统中，某一时刻有且仅有一个事件(五种事件中的一个)发生。一旦某一事件发生，则需改变系统状态(队列状态)，因此，整个服务系统的模拟就是按事件表的次序，依次根据事件来确定系统状态的变化,即事件驱动模拟。

3.模拟程序应如何运行假设事件表中最早发生的是新客户到达，则随之应得到两个时间：一是本客户处理业务所需时间；二是下一客户到达服务系统的时间间隔。此时模拟程序应做的工作有：(1)比较四个队列中的客户数，将新到客户插入到最短队列中。若队列原来是空的，则插入的客户为队头元素，此时应设定一个新的事件——刚进入服务系统的客户办完业务离开服务系统的事件插入事件表。(2)设定一个新的到达事件——下一客户即将到达服务系统的事件插入事件表。若发生的事件是某队列中的客户服务结束离开服务系统，则模拟程序应做以下两件工作：①从队头删除客户，并计算该客户在服务系统中的逗留时间；②当队列非空时(用户离开后)，应把新的队头客户设定为一个新的离开事件，计算该客户离开服务系统的时间，并插入事件表。当服务系统停止营业后，若事件表为空，则程序运行结束。

4.数据结构考虑在该仿真(模拟)程序中，主要应设置四个队列和一个有序事件表。队列采用单链表来实现，其中单链表中的每个结点代表一个客户应有两个数据：客户的到达时间和服务时间。该链队列有一个队头结点，包括的数据是队列中的客户数。事件表用单链表来实现，其中的每个结点代表一个事件，包括的数据项有：事件发生时间和事件类型。事件类型为0、1、2、3、4，其中0表示客户到达事件，1、2、3和4分别表示四个窗口的客户离开事件。事件表中最多有五个事件，当事件表为空时程序运行结束。根据上面的讨论，我们把数据结构说明如下：structqueuenode{intarrivetime,duration; structqueuenode*next;}structqueueheader{ structqueuenode*front,*rear; intqueuenodenum;}structeventnode{intoccurtime; inteventtype; structeventnode*next;}structeventlist{eventnode*front,*rear;inteventnum;}structqueueheader*queue[m];structeventlist*eventlst;

5.仿真程序的实现根据以上的分析，我们给出该仿真程序的关键部分。有兴趣的读者可以据此写出完整的仿真程序。voidSimulation(){totaltime=0; /*客户逗留时间*/count=0; /*客户数*/generate(pe);/*产生一个事件结点*pe*/pe－>occurtime=0; /*初始化事件表*/pe－>eventtype=0; /*第一个事件客户到达事件*/pe－>next=NULL; /*到达时刻为0*/eventlst－>front=pe;eventlst－>rear=pe;eventlst－>eventnum=1;for(i=0;i<4;i++) /*置空队列*/SetNullQL(queue[i]);while(!EmptyQL(eventlst)){delete_eventlist(eventlst,event);/*取发生事件并删除它*/if(event－>eventtype==0) /*客户到达事件发生*/{count++; /*统计客户数*/random(durtime,interaltime);/*产生该用户的服务时间和下一到达客户的到达时间间隔*/if((event－>occurtime+interaltime)<closetime){insert_eventlist(eventlst,(event－>occurtime+interaltime,0));/*插入到达事件*/}len=minlength();/*取最短队列号*/addqueue(queue[len],(event－>occurtime,durtime))/*把刚到达的新客户加入到minlen队列中*/if(queue[len].queuenum==1)insert_eventlist(eventlst,(event－>occurtime+durtime,len));} /*if(...==0)*/else{i=event－>eventtype;deletequeue(q[i]，f);/*删除第i队列的头元素赋给f*/totaltime+=event－>occurtime－f.arrivetime;/*客户逗留时间统计*/if(queue[i]－>queuenum!=0)insert_eventlist(eventlst,(event－>occurtime+queue[i]－>front－>duration,i));} /*else*/}/*while*/} /*Simulation*/读者可以自行分析程序的运行过程。由于程序的可读性较好，因此易于理解，在此就不对它作进一步说明，只对其中的几个函数作一简单介绍：generate():产生一个事件结点。delete_eventlist (eventlst,event)：从事件表eventlst中删除一个最早发生的事件结点；并赋值给event指针。Random (durtime,interaltime)：产生两个随机数durtime和interaltime，durtime是指服务时间，interaltime是指下一个客户到达的时间间隔。Insert_eventlist (eventlst,eventnode)：在事件表eventlst中插入事件eventnode。在程序中事件用(durtime,eventtype)来表示。minlength()：取得4个队列中最短的队列序号。Addqueue (queue[i]，(arrivetime,duration))：在队列queue[i]中插入客户(arrivetime,duration)。arrivetime表示到达时间，duration表示服务时间。deletequeue(queue[i],f)：在队列queue[i]中删除队头元素，表示客户离开，并把结点的值赋给f。

10.4.2划分子集问题

1.问题与分析已知集合A={a1,a2,…,an},并已知集合上的关系R={(ai,aj)|ai,aj属于A,i不等于j}，其中(ai,aj)表示ai与aj之间的冲突关系。现要求将集合A划分成互不相交的子集A1,A2,…,Am(m≤n)，使任何子集上的元素均无冲突关系，同时要求划分的子集个数较少。这类问题可以有各种各样的实际应用背景。例如在安排运动会比赛项目的日程时，需要考虑如何安排比赛项目，才能使同一运动员参加的不同项目不在同一日进行，同时又使比赛日程较短。我们就运动会比赛日程安排来说明解决这类问题的方法。设共有9个比赛项目，则A={1,2,3,4,5,6,7,8,9}。项目报名汇总后得到有冲突的项目如下：R={(2, 8),(9, 4),(