Gli esercizi
Testi e soluzioni di alcuni esercizi
Costruzione di un heap
/*
** heap.c
**
** Letta in input una sequenza di numeri interi memorizzarla
** in una lista. Costruire un heap composto dagli elementi
** della lista, utilizzando come peso la frequenza di ognuno
** degli elementi. L'heap deve essere costruito facendo uso
** di un array o di una matrice. Stampare l'heap.
**
** Marco Liverani (liverani@mat.uniroma3.it) - Settembre 2001
*/
#include <stdlib.h>
#include <stdio.h>
#define MAX 100
struct nodo {
int info;
int flag;
struct nodo *next;
};
struct nodo *leggi_lista(void) {
int a, n, i;
struct nodo *p, *primo=NULL;
scanf("%d", &n);
for (i=0; i<n; i++) {
scanf("%d", &a);
p = malloc(sizeof(struct nodo));
p->info = a;
p->flag = 0;
p->next = primo;
primo = p;
}
return(primo);
}
void stampa_array(int h[MAX][2]) {
int i;
for (i=1; i<=h[0][0]; i++)
printf("%d (%d) ", h[i][0], h[i][1]);
printf("\n");
return;
}
void scambia(int *a, int *b) {
int c;
c = *a;
*a = *b;
*b = c;
return;
}
void inserisci(int h[MAX][2], int i, int f) {
int last;
last = h[0][0] + 1;
h[last][0] = i;
h[last][1] = f;
while (last>1 && h[last/2][1]<h[last][1]) {
scambia(&h[last/2][0], &h[last][0]);
scambia(&h[last/2][1], &h[last][1]);
last = last/2;
}
h[0][0]++;
return;
}
int frequenza(struct nodo *p, struct nodo *q) {
int f=0, flag=0;
while (q != NULL && flag == 0) {
if (q->info == p->info) {
if (q->flag == 1) {
flag = 1;
f = 0;
} else {
f++;
q->flag = 1;
}
}
q = q->next;
}
return(f);
}
int main(void) {
struct nodo *primo, *p;
int H[MAX][2], f;
H[0][0] = 0;
primo = leggi_lista();
p = primo;
while (p != NULL) {
f = frequenza(p, primo);
if (f > 0)
inserisci(H, p->info, f);
p = p->next;
}
stampa_array(H);
return(0);
}