[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