(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'''(); | ||
+ | } |
#include "Item.h" void PQinit(int); int PQempty(); void PQinsert(Item); Item PQdelmax();
#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--]; }
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]; }
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(); }