快捷搜索:

C语言的最小堆排列实现进程的优先调度

(中国软件网讯)在进程中实现优先级算法可以使用最小堆排列来实现。

一般在优先级调度算法中要实现的操作1.从后备作业队列中选择一个优先级最高的作业将他们调入内存,分配必要的资源。此处的优先级越高关键字越小2.创建进程并且放入到后备作业队列中3,。改变一个进程的优先级重新排列后备作业队列的顺序此处的c语言实现仅仅使用一个数组代表关键字,若再真实的操作系统中,真可以使用结构体数组来代替示例中的简单数组。

view plainprint?

struct Process { int key;int* pointer;//指向进程的入口代码//更多的其他信息}process

view plainprint?

#include #define HEAP_SIZE 5//定义堆的大小,记住此时的大小不包含堆数组的0号元素,0号元素储存的是 堆的大小;//================Min_heapify================== /*此函数的作用是使以i为根的堆成为最小堆;

*/ void Min_heapify(int *array,int i){ int heap_size=array[0];int l=0;int r=0;int least=0;//此处不使用递归节约时间;while(i>0){ l=2*i;r=2*i+1;if(l<=heap_size&&array[l]

least=l;else least=i;if(r<=heap_size&&array[r]

least=r;if(least!=i){ int temp;temp=array[i];array[i]=array[least];array[least]=temp;} i/=2;}

} //=================Build_min_heap=============== /*此函数是建立以数组array的最小堆;*/ void Build_min_heap(int* array){ int heap_size=array[0];for(int i=(heap_size/2);i>0;i——)

Min_heapify(array,i);} //============= Heap_extract_min============= /*此函数是返回最小堆的最小的关键字*/ int Heap_extract_min(int*array){ int min;int heap_size=array[0];if(heap_size<1)

printf("heap underflow ");min=array[1];array[1]=array[heap_size];array[0]-=1;Min_heapify(array,1);return min;} //=========== Heap_prior_increase=============== /*此函数的作用是增加堆中某个元素的优先值,优先级高的关键字小;*/ void Heap_prior_increase(int*array,int i,int key){ if(key>array[i]&&key<0){ printf("the prior you want to increse cann't be relize ");return ;} array[i]=key;while(i>1&&array[i/2]>array[i]){ int temp;temp=array[i];array[i]=array[i/2];array[i/2]=temp;i/=2;} } //=========== Min_heap_insert===================== /*此函数的作用是插入元素;*/ void Min_heap_insert(int*array,int key){ int heap_size;array[0]+=1;heap_size=array[0];array[heap_size]=-2;Heap_prior_increase(array,heap_size,key);} int main(){ printf(" ^_^welcome to wuhan university^_^ ");int test;int heap_array[HEAP_SIZE+1]={3,2,1,4,-1,-1};//此处的第一个元素是堆的大小;Build_min_heap(heap_array);Heap_prior_increase(heap_array,3,3);printf(" heap_array:");for(int i=0;i<6;i++)

printf(" %d ",heap_array[i]);Min_heap_insert(heap_array,6);printf(" heap_array:");for(int i=0;i<6;i++)

printf(" %d ",heap_array[i]);Min_heap_insert(heap_array,2);printf(" heap_array:");for(int i=0;i<6;i++)

printf(" %d ",heap_array[i]);test=Heap_extract_min(heap_array);printf(" Heap_extract_min=%d ",test) ;printf(" ^_^welcome to wuhan university^_^ ");getchar();

您可能还会对下面的文章感兴趣: