[cdev] Задача_6. гр 135

[Лена Довжко]

 	queue = malloc(sizeof(struct prioq));
        if (queue == NULL) {
 		fprintf(stderr, "prioq_new(): out of memory !\n");
 		return NULL;
 	} 	

 	memset(queue,0,sizeof(struct prioq));//clear
 	hp = malloc(INIT_SIZE*(sizeof(struct prioq_head*)));
 if (queue == NULL) {
 		fprintf(stderr, "prioq_new(): out of memory !\n");
 		return NULL;
 	} 	
 	memset(hp,0,sizeof(struct prioq));//clear
 	
 	
 		
     
> #define NEW_SIZE(q)	(((q)->size + GROW_SIZE) * sizeof(struct prioq_head *))
> #define OLD_SIZE(q)	((q)->size * sizeof(struct prioq_head *))
> 
> int prioq_put(struct prioq *queue, struct prioq_head *hp){
> 
>     int i;
> 	struct prioq_head** tmp;
> 
> 	if (queue == NULL || hp == NULL)
> 		fprintf(stderr, "prioq_put: NULL args\n");
> 
> 	if (queue->size == queue->used) {
> 		tmp = (struct prioq_head**)realloc(queue->heap, NEW_SIZE(queue));
> 		if (!tmp) {
> 			fprintf(stderr, "prioq_put: can't realloc heap\n");
> 			return -1;
> 		}
> 		memset(queue->heap + OLD_SIZE(queue), 0,
> 		       NEW_SIZE(queue) - OLD_SIZE(queue));
> 		queue->size += GROW_SIZE;
> 		queue->heap = tmp;
> 	}
> 
> 	i = queue->used++;
> 
> 	while (i && queue->compare(queue->heap[PARENT(i)], hp) < 0) {
>  		queue->heap[i] = queue->heap[PARENT(i)];
> 		queue->heap[i]->index = i;
> 		i = PARENT(i);
> 	}
> 
> 	queue->heap[i] = hp;
> 	hp->index = i;
>     
> 	return 0;
> 
> }	
> 
> /*Функция сравнения*/
> int
> compare(struct prioq_head *a, struct prioq_head *b)
> {
> 	struct user_data *ap = (struct user_data *) a;
> 	struct user_data *bp = (struct user_data *) b;
> 
> 	if (ap->data > bp->data)
> 		return 1;
> 	else if (ap->data < bp->data)
> 		return -1;
> 	return 0;
> }
> 
> /*---------------------------------------------*/
> #define LEFT_CHILD(i)   (((i) * 2) + 1) 
> int
> prioq_heapify(struct prioq *queue)
> {
>     int index, largest;	
> 	
> 	struct prioq_head* tmp;
> 	
> 	for (index = 0,largest = LEFT_CHILD(index);
> 	    largest < queue->used;
>         index = largest, largest = LEFT_CHILD(index)) {
> 		
>         if (queue->compare(queue->heap[largest],queue->heap[largest++]) < 0) {
>             largest++;			
>         }
> 	    if (queue->compare(queue->heap[index],queue->heap[largest])<0) {
> 			tmp = queue->heap[largest];
> 			queue->heap[largest] = queue->heap[index];
> 			queue->heap[index] = tmp;
> 		}
> 		else return 0;
> 	}	
> 	if ((largest == queue->used) 
> 		&& (queue->compare(queue->heap[index],queue->heap[largest]) < 0)) {
>         
> 		tmp = queue->heap[largest];
> 		queue->heap[largest] = queue->heap[index];
> 		queue->heap[index] = tmp;
> 	}
> 			
> }
> 
> 
> /*------------------------------------------------*/
> void 
> prioq_remove(struct prioq *queue, struct prioq_head *hp) 
> {
>     
> 	if (hp->index > queue->used)
>         fprintf(stderr,"prioq_remove: inedx out of range\n");
> 	
> 	int index = hp->index;
> 	
> 	while (index > 0){
> 	    queue->heap[index] = queue->heap[PARENT(index)];
>         index = PARENT(index);
> 	}
> 	
> 	queue->used-=1;
> 	
> 	int used = queue->used;
> 	queue->heap[0] = queue->heap[used];
> 
> 	prioq_heapify(queue);
> }	
> 
> 
> int main(void){
>     struct prioq *q=prioq_new(compare); 
>     struct user_data a,b,c;
> 	struct prioq_head *p,*s,*t;
> 	struct user_data *ab;
> 		
>     a.data = 0;
>     b.data = 5;
> 	p = &a.head;
> 	s = &b.head;
> 	
> 	
> 	
> 	prioq_put(q,p);
> 	prioq_put(q,s);
> 		
> 	prioq_remove(q,p);
> 	return 1;	
> }
>   	
> 
> 	_______________________________________________
> cdev mailing list
> cdev на wiki.syktsu.ru
> http://wiki.syktsu.ru/cgi-bin/mailman/listinfo/cdev
>