Quelli che sto per illustrare sono due algoritmi, scritti in C, che, dati prima un'array e dopo una lista, stampano tutti i valori di questi saltando idoppioni. Non è che in questo periodo mi stia annoiando, anzi... Il fatto è che ho trovato interessante questo algoritmo ottimizzato e dunque lo reputo alquanto utile da utilizzare in programmi che devono effettuare il controllo su eventuali doppioni in liste, array e altre diavolerie simili e perciò, ve lo propongo. Per prima cosa si deve partire dal presupposto che per controllare se esistono eventuali doppioni in una lista, questa deve essere controllata dalla prima all'ultima posizione svolgendo un test di controllo per ogni elemento. L'ottimizzazione consiste nel fare questo test dalla posizione 0 alla posizione di indice e-1 (ossia l'indice da 0 fino alla posizione corrente).
Vabbé, è inutile stare a parlare quando un codice vale più di mille parole:
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <time.h>
/* Funzione che controlla se l'elemento v[e] è presente tra le posizioni 0 ed e-1 */
int presente(int *v, int e)
{
int j;
for (j = 0; j < e; j++)
if (v[j] == v[e])
return 1;
return 0;
}
int main(void)
{
/* Crea un array in heap */
int i, n = 10;
int *v = (int *)malloc(sizeof(int)*n);
srand(time(NULL));
/* Crea elementi a caso, li inserisce nell'array e li stampa */
printf("Array originale: ");
for (i = 0; i < n; i++) {
v[i] = (int)(4+rand() / (RAND_MAX+1.)*100);
printf("%d ", v[i]);
}
/* Stampa l'array saltando i doppioni */
printf("\nStampa array senza doppioni: ");
for (i = 0; i < n; i++) {
if (!presente(v, i))
printf("%d ", v[i]);
}
printf("\n");
return 0;
}
Lo stesso discorso può essere implementato con le liste. È da notare che stavolta l'indice 0 è rappresentato ovviamente dalla testa della lista, che deve essere salvata in un puntatore ausiliario altrimenti si rischia di perderla (ahahahaaaaaaah!!!!11!!!1!11 ma che battuta cr3tin4 aUsHaUshAusH!!!!!!!!111!!!!!11!! x',','d), e inoltre il valore da controllare deve essere passato come parametro alla funzione (dato che è impossibile accedere ai valori attraverso un indice):
#include <stdio.h>
#include <malloc.h>
#include <time.h>
/* Struttura che rappresenta un nodo della lista */
struct nodo
{
int val;
struct nodo *next;
};
typedef struct nodo Lista;
/* Funzione che inserisce un elemento in fondo alla lista */
void incoda(Lista **l, int val)
{
if (!(*l)) {
*l = (Lista *)malloc(sizeof(Lista));
(*l)->val = val;
(*l)->next = NULL;
}
else
incoda(&((*l)->next), val);
}
/* Funzione che controlla se val è presente tra la testa della lista ed il valore alla posizione e-1 */
int presente(Lista *l, int e, int val)
{
int i;
for (i = 0; i < e; i++) {
if (l->val == val)
return 1;
l = l->next;
}
return 0;
}
int main(void)
{
Lista *l = NULL; /* Lista */
int n = 10, i;
srand(time(NULL));
for (i = 0; i < n; i++)
incoda(&l, rand() % 100); /* Inserisce n numeri a caso */
i = 0;
Lista *l_testa = l; /* Puntatore alla testa della lista */
/* Stampa la lista originale */
printf("Lista originale: ");
while (l) {
printf("%d ", l->val);
l = l->next;
}
l = l_testa;
/* Stampa la lista escludendo i doppioni */
printf("\nLista senza doppioni: ");
while (l) {
if (!presente(l_testa, i, l->val))
printf("%d ", l->val);
i++;
l = l->next;
}
printf("\n");
return 0;
}
Se avete suggerimenti o notate stranezze non esitate ad illuminarmi attraverso i commenti! Altrimenti vorrà dire che il mio codice è perfetto e quindi cippa!