ADTs de 1ª ordem: Fila de Prioridade: Difference between revisions
From Wiki**3
No edit summary |
|||
(One intermediate revision by the same user not shown) | |||
Line 51: | Line 51: | ||
} | } | ||
== | == Algoritmo de Ordenação == | ||
O algoritmo de ordenação com base em filas de prioridade é um exemplo de um cliente do ADT descrito acima. O princÃpio de funcionamento consiste na inserção dos elementos a ordenar na fila e depois removê-los ordenadamente. | |||
#include <stdlib.h> | |||
#include "Item.h" | |||
#include "PQ.h" | |||
void '''PQsort'''(Item a[], int l, int r) { | |||
int k; | |||
'''PQinit'''(); | |||
for (k = l; k <= r; k++) '''PQinsert'''(a[k]); | |||
for (k = r; k >= l; k--) a[k] = '''PQdelmax'''(); | |||
} |
Latest revision as of 08:30, 12 November 2008
Interface
#include "Item.h" void PQinit(int); int PQempty(); void PQinsert(Item); Item PQdelmax();
Implementação
Com Amontoado
#include <stdlib.h> #include "Item.h" static Item *pq; static int N; void PQinit(int maxN) { pq = malloc((maxN+1)*sizeof(Item)); N = 0; } int PQempty() { return N == 0; } void PQinsert(Item v) { pq[++N] = v; fixUp(pq, N); } Item PQdelmax() { exch(pq[1], pq[N]); fixDown(pq, 1, N-1); return pq[N--]; }
Com Vector
static Item *pq; static int N; void PQinit(int maxN) { pq = malloc(maxN*sizeof(Item)); N = 0; } int PQempty() { return N == 0; } void PQinsert(Item v) { pq[N++] = v; } Item PQdelmax() { int j, max = 0; for (j = 1; j < N; j++) if (less(pq[max], pq[j])) max = j; exch(pq[max], pq[N-1]); return pq[--N]; }
Algoritmo de Ordenação
O algoritmo de ordenação com base em filas de prioridade é um exemplo de um cliente do ADT descrito acima. O princÃpio de funcionamento consiste na inserção dos elementos a ordenar na fila e depois removê-los ordenadamente.
#include <stdlib.h> #include "Item.h" #include "PQ.h" void PQsort(Item a[], int l, int r) { int k; PQinit(); for (k = l; k <= r; k++) PQinsert(a[k]); for (k = r; k >= l; k--) a[k] = PQdelmax(); }