priority_queue.c

完全由C语言实现的图的相关操作

#include "stdafx.h"
Status init_priority_queue(priority_queue* pq)
{
  //初始化优先队列pq
    pq->n=1;
    return OK;
}

/*Edge* IninEdge(int a,int b,int c)
{
  Edge* t=(Edge*) malloc (sizeof(Edge)); 
  t->v=a;
  t->w=b;
  t->weight = c;  
  return t;    
} 
 */
 Status Destory_priority_queue(priority_queue* pq)
 {//销毁优先队列
   int i; 
   for(i=1;i<pq->n;i++)
   free(pq->h[i]) ;     
   free(pq);
   return OK;     
 } 

Status max_heapify(priority_queue* pq,int i)
{
  //每次插入后进行的堆调整，因为每次都插入到最后，前面的元素都符合堆的要求，
  //调整成功返回0，不成功返回-1
  Edge* temp; 
 while(i>1)
 {
   int p = i/2 ;
   if(pq->h[i]->weight<pq->h[p]->weight)
   {
     //swap(pq->h[i],pq->h[p]); 
     temp = pq->h[i];
     pq->h[i]= pq->h[p];
     pq->h[p] =temp;         
     i=p;
   }
   else break;
 } 
 return OK;
}
/*
int min_heapAdjust(priority_queue& pq,int n)
{
//已知pq[1....n-1]中记录的关健字除pq[1]外均满足堆的定义，本函数调整L[1]的关健字
//使L[1...n-1]成为一个小顶堆,调整成功返回0，不成功返回-1
 int s = 1;
 Edge rc = pq.h[1];
 for(;s<=n-1;)
 {
    int j = 2*s;
    if(j<n-1 && pq.h[j].weight>pq.h[j+1].weight) ++j; //j为左右兄弟中最小的那个元素的下标
    if(rc.weight<=pq.h[j].weight)break; //找到rc所放的位置
   
        pq.h[s]=pq.h[j];
        s=j;
   
 } 
 pq.h[s]=rc;
 return 0;
}
*/

Status min_heapAdjust(priority_queue* pq,int n)
{//已知pq[1....n-1]中记录的关健字除pq[1]外均满足堆的定义，本函数调整L[1]的关健字
//使L[1...n-1]成为一个小顶堆,调整成功返回0

 int i=1;
 Edge* temp;
 int left,right, smallest; 
 for(;;)
 {
   left=i*2;
   right=left+1;
  if(left>=n)
   break;
  if(right>=n)
   smallest=left;
  else
  {
      if(pq->h[left]->weight<pq->h[right]->weight)
    smallest=left;
   else
    smallest=right;
  }
  if(pq->h[smallest]->weight<pq->h[i]->weight)
  {
  // swap(pq.h[smallest],pq.h[i]);
   temp =pq->h[smallest] ;
   pq->h[smallest] =  pq->h[i] ;
   pq->h[i] = temp ; 
   i=smallest;
  }
  else
   break;
 }
 return OK;
}


Status insert_priority_queue(priority_queue* pq,Edge* t)
{
  //向队列pq中插入一元素 t, 操作成功返回0，操作失败返回-1
   if(pq->n>MAX_NUM) return OVERFLOW;
   pq->h[pq->n]=t;
   max_heapify(pq,pq->n); //插入后要进行调整
   pq->n++;
   return OK;
}

Edge* extract_min(priority_queue* pq)
{//队列pq中返回最小值，并也删除了最小值 
 
  Edge* temp =pq->h[1];
  pq->h[1]=pq->h[ pq->n-1 ] ; //把最后一个元素调整为根
  --pq->n; //删除第一个元素，也就是最小的元素
  min_heapAdjust(pq,pq->n);
  return temp;

}

Edge* Get_Min(priority_queue* pq)
{
  //仅仅从队列pq中获得了最小值
  return pq->h[1];
}

int isEmpty(priority_queue* pq)
{
  //队列为空返回true, 否则返回false
    return pq->n>1? 0 :1 ;
}