equeue.cpp

○1 设计进程进程控制块PCB表结构

typedef  struct Process QueueDataType;
typedef struct 
   {
       PtrQueueType head;
       PtrQueueType rear;
       PtrQueueType emptyHead;
   }ptrQueue;
   typedef ptrQueue* pQueue;

pQueue createNullQueueWithHead()

   {
       pQueue tmpQueue;
       /*not a good handle below*/
       tmpQueue=(pQueue)malloc(sizeof(ptrQueue));
       tmpQueue->emptyHead=(PtrQueueType)malloc(sizeof(QueueDataType));
       tmpQueue->head=NULL;
       tmpQueue->rear=NULL;
       return tmpQueue;
   }
   int isEmpty(pQueue inQueue)
   {
       return inQueue->head==NULL;
//Correction: here at the last node ,after dequeue ,the rear may not be null
   }
   PtrQueueType deQueue(pQueue inQueue)
   {
       PtrQueueType tmpQueue;
       if(isEmpty(inQueue)||inQueue==NULL)
           {
               printf("in deQueue,inQueue is null\n");
               return NULL;
           }
       tmpQueue=inQueue->head;
       inQueue->head=inQueue->head->next;
       inQueue->emptyHead->next=inQueue->head;
       return tmpQueue;
   }
   void enQueue(pQueue inQueue,PtrQueueType inNode)
   {
       if(inQueue==NULL||inNode==NULL)
           {
               printf("in enQueue,inQueue is null\n");
               return ;
           }
       if(inQueue->rear==NULL&&inQueue->head==NULL)
//first node to be created.
       {
               inQueue->rear=(PtrQueueType)malloc(sizeof(QueueDataType));
               inQueue->rear=inNode;
               inQueue->head=inQueue->rear;
               inQueue->emptyHead->next=inQueue->head;
       }
       else
       {
           /*Correction : use the rear->next for the new enqueue's pos*/
      inQueue->rear->next=(PtrQueueType)malloc(sizeof(QueueDataType));
           inQueue->rear->next=inNode; 
           inQueue->rear=inQueue->rear->next;
           inQueue->rear->next=NULL;
       }
   }
   /*attention :this insert algorithm has effects only on the queue with an empty head*/
   void insert(pQueue inQueue,PtrQueueType inNode)
   {
           PtrQueueType p;
           if(inQueue==NULL||inNode==NULL)
           {
               printf("in insert,inQueue is null\n");
               return ;
           }
              p=inQueue->emptyHead;
           while(p->next!=NULL&&p->next->priorityNum<=inNode->priorityNum)
               p=p->next;
           /*maybe will have errors when stop at p->next==null*/   
          if(p==inQueue->emptyHead)/*Correction Adjust to the head*/
           {
                   inNode->next=p->next;   
                   p->next=inNode;
                   inQueue->head=inNode;
           }
           else
           {
                   inNode->next=p->next;   
                   p->next=inNode;
           }
            //Correction: To Adjust the rear
           while(p->next!=NULL)
               p=p->next;
           inQueue->rear=p;
      }