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

Алексей Петрунёв alexeypetrunev на gmail.com
Ср Мар 31 04:01:13 MSK 2010


Здравствуйте. Написаны функции prioq_remove и prioq_heapify.
----------- следущая часть -----------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


#define RIGHT_CHILD(i)  (((i) * 2) + 2)
#define PARENT(i)       (((i) - 1) / 2)
#define INIT_SIZE 2
#define GROW_SIZE	32
typedef int (*prioq_compare_t)(struct prioq_head *a, struct prioq_head *b);

struct prioq_head{
	    int index;
};		

struct user_data{
        struct prioq_head head;
		int data;
};		

struct prioq{
        struct prioq_head **heap;
	    size_t size;
        size_t used;
        prioq_compare_t compare;
};	


/*Создание очереди */
struct prioq
*prioq_new(prioq_compare_t compare){
	    
    struct prioq *queue;
	struct prioq_head **hp;
 
	queue = (prioq *)malloc(sizeof(struct prioq));
	
	memset(queue,0,sizeof(struct prioq));//clear
	hp = (prioq_head**)malloc(INIT_SIZE*(sizeof(struct prioq_head*)));
	memset(hp,0,sizeof(struct prioq));//clear
	
	
	if (queue == NULL) {
		fprintf(stderr, "prioq_new(): out of memory !\n");
		return NULL;
	}	
    
	queue-> heap = hp;
	queue->size = INIT_SIZE;
	queue->used = 0;	
	queue->compare = compare;
	
	return queue;
}		
#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