C语言队列排序函数作用求解释
看不懂这个函数的意思啊，求大家解释，这个是按照什么排序的啊，其中 用Item 代表int 类型
voidpqueue_sort_key(Pqueue pq1, Pqueue pq2){ int k, j; for (k = 1; k <= pq1->count; k++) { /* Verifichiamo le chiavi */ if (pq1->key[k] != pq2->key[k]) { /* Non corrisposte */ for (j = 1; j <= pq2->count; j++) { /* Cerchiamo quella corretta */ if (pq1->key[k] == pq2->key[j]) { /* Trovata! */ swap(&pq2->h[k], &pq2->h[j]); swap(&pq2->key[k], &pq2->key[j]); } } } }}#ifndef ITEM_H#define ITEM_H/************************************************* * Tipo valore dello stack. * Possibili valore: int, char, ecc... *************************************************/typedef int Item;#endif
/************************************************* * Coda di priorità. * Versioni supportate: * - HEAP interno * - Con/senza ordinamento HEAP * - Con/senza chiave esterna *************************************************/#include <stdio.h>#include <stdlib.h>#include "item.h"#include "pqueue.h"typedef Item *Heap;struct pqueue { Heap h; int *key; int size, count;};/************************************************* * Effettua uno scambio. *************************************************/static voidswap(int *i, int *j){ int tmp; tmp = *i; *i = *j; *j = tmp;}/************************************************* * Effettua un confronto. *************************************************/static intcmp(int i, int j){ if (i < j) { return (-1); } else if (i > j) { return (1); } return (0);}/************************************************** Ritorna il padre se presente.**************************************************/static intfather(Pqueue pq, int i){ if (pq == NULL) { fprintf(stderr, "father(): non esiste una coda\n"); return (-1); } if (i >= 2 && i <= pq->count) { return (i / 2); } return (i);}/************************************************* * Aggiorna l'HEAP dal basso. *************************************************/static voidheapify_down(Pqueue pq, int i, int n){ int j; /* indice del figlio di i con chiave minore */ if (pq == NULL) { fprintf(stderr, "heapify_down(): non esiste una coda\n"); return; } /* i ha almeno un figlio */ if ((2 * i) <= n) { /* i ha solo il figlio sinistro */ if ((2 * i) == n) { j = (2 * i); } /* i ha 2 figli */ else { j = cmp(pq->h[(2 * i)], pq->h[(2 * i) + 1]) < 0 ? (2 * i) : ((2 * i) + 1); } if (cmp(pq->h[j], pq->h[i]) < 0) { swap(&(pq->h[i]), &(pq->h[j])); swap(&(pq->key[i]), &(pq->key[j])); heapify_down(pq, j, n); } }}/************************************************* * Aggiorna l'HEAP dall'alto. *************************************************/static voidheapify_up(Pqueue pq, int i){ int j; if (pq == NULL) { fprintf(stderr, "heapify_up(): non esiste una coda\n"); return; } if (i > 1) { j = father(pq, i); if (cmp(pq->h[i], pq->h[j]) < 0) { swap(&(pq->h[i]), &(pq->h[j])); swap(&(pq->key[i]), &(pq->key[j])); heapify_up(pq, j); } }}/************************************************* * Crea una coda di priorità vuota che potrà * contenere al massimo n Item. *************************************************/Pqueuepqueue_new(int n){ Pqueue pq; int i; if (n == 0) { exit(EXIT_SUCCESS); } if ((pq = malloc(sizeof(struct pqueue))) == NULL) { fprintf(stderr, "Error: malloc()\n"); exit(EXIT_FAILURE); } if ((pq->h = malloc((n + 1) * sizeof(Item))) == NULL) { fprintf(stderr, "Error: malloc()\n"); exit(EXIT_FAILURE); } if ((pq->key = malloc((n + 1) * sizeof(Item))) == NULL) { fprintf(stderr, "Error: malloc()\n"); exit(EXIT_FAILURE); } for (i = 0; i < (n + 1); i++) { pq->h[i] = 0; pq->key[i] = i; } pq->size = (n + 1); pq->count = 0; return (pq);}/************************************************* * Distrugge la coda di priorità. *************************************************/voidpqueue_destroy(Pqueue pq){ if (pq == NULL) { fprintf(stderr, "pqueue_destroy(): non esiste una coda\n"); return; } free(pq->h); free(pq->key); free(pq);}/************************************************* * Restituisce la lunghezza della coda di priorità. *************************************************/intpqueue_length(Pqueue pq){ if (pq == NULL) { fprintf(stderr, "pqueue_length(): non esiste una coda\n"); return (-1); } return (pq->count);}/************************************************* * Inserisce l'Item nella coda di priorità con * ordinamento dall'alto dei valori. *************************************************/voidpqueue_insert(Pqueue pq, Item item){ int pos; if (pq == NULL) { fprintf(stderr, "pqueue_insert(): non esiste una coda\n"); return; } pos = (pq->count + 1); if (pos < pq->size) { /* Imposta valore */ pq->h[pos] = item; pq->count++; heapify_up(pq, pos); } else { fprintf(stderr, "pqueue_insert(): coda piena\n"); return; }}/************************************************* * Inserisce l'Item nella coda di priorità senza * ordinamento dall'alto dei valori. *************************************************/voidpqueue_insert_without_sort(Pqueue pq, Item item){ int pos; if (pq == NULL) { fprintf(stderr, "pqueue_insert(): non esiste una coda\n"); return; } pos = (pq->count + 1); if (pos < pq->size) { /* Imposta valore */ pq->h[pos] = item; pq->count++; } else { fprintf(stderr, "pqueue_insert(): coda piena\n"); return; }}voidpqueue_insert_key(Pqueue pq, Item item, int key){ int pos; if (pq == NULL) { fprintf(stderr, "pqueue_insert(): non esiste una coda\n"); return; } pos = (pq->count + 1); if (pos < pq->size) { /* Imposta valore */ pq->h[pos] = item; /* Imposta chiave */ pq->key[pos] = key; pq->count++; heapify_up(pq, pos); } else { fprintf(stderr, "pqueue_insert(): coda piena\n"); return; }}voidpqueue_insert_key_without_sort(Pqueue pq, Item item, int key){ int pos; if (pq == NULL) { fprintf(stderr, "pqueue_insert(): non esiste una coda\n"); return; } pos = (pq->count + 1); if (pos < pq->size) { /* Imposta valore */ pq->h[pos] = item; /* Imposta chiave */ pq->key[pos] = key; pq->count++; } else { fprintf(stderr, "pqueue_insert(): coda piena\n"); return; }}Itempqueue_extractmin(Pqueue pq){ int i; Item val; if (pq == NULL) { fprintf(stderr, "pqueue_extractmin(): non esiste una coda\n"); return (-1); } val = pq->h[1]; if (pq->count >= 2) { for (i = 2; i <= pq->count; i++) { if (i == pq->size) { break; } pq->h[i - 1] = pq->h[i]; } } pq->count--; heapify_down(pq, 1, pq->count); return (val);}Itempqueue_extractmin_without_sort(Pqueue pq){ int i; Item val; if (pq == NULL) { fprintf(stderr, "pqueue_extractmin(): non esiste una coda\n"); return (-1); } val = pq->h[1]; if (pq->count >= 2) { for (i = 2; i <= pq->count; i++) { if (i == pq->size) { break; } pq->h[i - 1] = pq->h[i]; } } pq->count--; return (val);}Itempqueue_extractmin_key(Pqueue pq, int *key){ int i; Item val; if (pq == NULL) { fprintf(stderr, "pqueue_extractmin_key(): non esiste una coda\n"); return (-1); } val = pq->h[1]; *key = pq->key[1]; if (pq->count >= 2) { for (i = 2; i <= pq->count; i++) { if (i == pq->size) { break; } pq->h[i - 1] = pq->h[i]; pq->key[i - 1] = pq->key[i]; } } pq->count--; heapify_down(pq, 1, pq->count); return (val);}Itempqueue_extractmin_key_without_sort(Pqueue pq, int *key){ int i; Item val; if (pq == NULL) { fprintf(stderr, "pqueue_extractmin_key(): non esiste una coda\n"); return (-1); } val = pq->h[1]; *key = pq->key[1]; if (pq->count >= 2) { for (i = 2; i <= pq->count; i++) { if (i == pq->size) { break; } pq->h[i - 1] = pq->h[i]; pq->key[i - 1] = pq->key[i]; } } pq->count--; return (val);}voidpqueue_sort(Pqueue pq, int i, int j){ int k; for (k = 2; k <= pq->count; k++) { if (pq->h[k] < pq->h[k - 1]) { swap(&pq->h[k], &pq->h[k - 1]); swap(&pq->key[k], &pq->key[k - 1]); k -= 2; } }}voidpqueue_sort_key(Pqueue pq1, Pqueue pq2){ int k, j; for (k = 1; k <= pq1->count; k++) { /* Verifichiamo le chiavi */ if (pq1->key[k] != pq2->key[k]) { /* Non corrisposte */ for (j = 1; j <= pq2->count; j++) { /* Cerchiamo quella corretta */ if (pq1->key[k] == pq2->key[j]) { /* Trovata! */ swap(&pq2->h[k], &pq2->h[j]); swap(&pq2->key[k], &pq2->key[j]); } } } }}