Newsgroup: it.comp.programmare
Titolo: Scansione di una lista

Ciao a tutti!
Ho una struttura dati che rappresenta una lista linkata uniderazionale (gli
elementi sono numeri interi); devo scrivere un programma che, prese in input
n liste di interi ordinati, stampi gli elementi presenti in tutte le liste. 
Qual č il modo
piů efficiente per farlo?
Grazie in anticipo.
Riccardo Rossi.

 Riccardo Rossi.
Non se se è il più efficiente, ma è probabile che lo sia.
Copi la prima lista in un'altra lista (f).
Per ogni lista dalla seconda fino alla fine, calcoli l'intersezione fra gli
elementi della lista corrente ed f, ed il risultato lo rimetti in f.
Se f è vuoto allora nessun elemento è in comune e quindi termini.
Alla fine f contiene tutti gli elementi comuni a tutte le liste.
Giusto come idea ti faccio un piccolo esempio in C++ (veloce veloce,
sicuramente lo puoi implementare meglio...)
ciao,
Paolo.
#include <iostream>
#include <iterator>
#include <list> // il C++ ha una classe template per le liste
#include <algorithm> // e tutta una serie di algoritmi, come
set_intersection
#include <cstdlib>
#include <ctime>
using namespace std;
typedef list<int> list_int; // ecco una lista di liste di interi... miracoli
del C++
// riempie una lista con valori casuali minori di max
void random_fill(list<int>& l,const unsigned int max,const unsigned int N)
{
        for(unsigned int i=0;i<N;++i) l.push_back(rand() % max);
}
// stampa una lista
void print(const list<int>& l)
{
        copy(l.begin(),l.end(),ostream_iterator<int>(cout," "));
        cout << endl;
}
// dato un insieme di liste pone in f gli elementi comuni a tutte le liste
void trova_uguali(list<list_int>& L,list_int& f)
{
        f.clear();
        if(L.size()==0) return;
        list<list_int>::iterator it=L.begin();
        it->sort();
        // copia L1 in f
        copy(it->begin(),it->end(),back_inserter(f));
        while(++it!=L.end())
        {
                it->sort();
                list_int res;
set_intersection(it->begin(),it->end(),f.begin(),f.end(),back_inserter(res))
;
                f.clear();
                if (!res.size()) break;
                copy(res.begin(),res.end(),back_inserter(f));
        }
}
int main(int argc, char *argv[])
{
        // test per la funzione...
        // crea dieci liste con numeri casuali
        time_t t;
        srand((unsigned) time(&t));
        list<list_int> L;
        for(unsigned int i=0;i<10;++i)
        {
                list<int> a_list;
                random_fill(a_list,3,10);
                L.push_back(a_list);
        }
        // stampa le liste
        for(list<list_int>::iterator it=L.begin();it!=L.end();++it)
        {
                print(*it);
        }
        cout << "Trova gli elementi ==\n";
        list_int f;
        trova_uguali(L,f);
        print(f);
        list_int::iterator uit=unique(f.begin(),f.end());
        if (uit!=f.end())
        {
                cout << "oppure in unica copia: ";
                copy(f.begin(),uit,ostream_iterator<int>(cout," "));
                cout << endl;
        }
        cout << "\nPREMI INVIO...";
        std::cin.get();
        return 0;
}

...
P.S.
Se le liste sono già ordinate (io me ne ero dimenticato), puoi rimuovere il
metodo sort.

 ha scritto nel messaggio 
news:ckrpr6$39r$1...@lacerta.tiscalinet.it...

=====
Ciao!
Grazie per il suggerimento, ma non posso usare la classe list della STL, 
devo creare una classe da zero che ne replichi le funzioni. Prima di leggere 
il tuo messaggio, ho provato ad implementare il seguente algoritmo; 
funziona, ma non so se è il massimo in termini di efficienza:
0. supponiamo che lista[0] sia la prima lista, lista[0]->value mi dà il 
valore corrente, con lista[0] = lista[0]->next mi sposto sul prossimo 
elemento;
1. se lista[0]->value = lista[i]->value (all'inizio i = 1), incremento i per 
ripetere il controllo tra lista[0] e la lista successiva, e pongo una 
variabile b a true;
2. se lista[0]->value < lista[i]->value, faccio lista[0] = lista[0]->next, 
pongo i = 1 e b = false;
3. se lista[0]->value > lista[i]->value, faccio lista[i]->lista[i]->next e 
pongo b = false.
Infine, quando ho confrontato tutte le liste, se b vale true, stampo il 
valore corrente di lista[0], che contiene un elemento presente in tutte le 
liste, e mi sposto in avanti in tutte le liste. Questo ciclo viene ripetuto 
finché ci sono elementi nelle liste.
Non puoi immaginare quanto grande sia l'aiuto che mi stai dando.
Riccardo Rossi.

piů efficiente per farlo?
Parti con i=0
Se il capolista della lista i-esima e' minore del capolista della lista
0-esima, avanzi di un elemento, lungo la lista i-esima. Se e' maggiore,
poni i=0. Se non esiste, termini. Se e' uguale e i==N stampi il numero.
Altrimenti i++.
Con questo sistema ogni elemento di ogni lista e' esaminato esattamente
una volta (al piu') e si sfrutta il principio di localita' sulle liste;
in piu' finisci appena esaurita la piu' corta delle liste (conviene che
la lista con minor elemento finale abbia l'i piu' basso, sospetto). Non
ti servono variabili di appoggio (in questo codice si' perche' per fare
prima non ho usato liste linkate ma array e quindi mi serviva puntarli,
e ho usato -1 per terminarle).
#include <stdio.h>
#define	NUMLISTE 5
int lista[5][10] =
{
        { 10, 13, 15, 17, 19, 21, 23, 27, 29, -1 },
        { 17, 18, 19, 20, 21, 22, 23, -1, -1, -1 },
        { 11, 12, 13, 14, 17, 21, 23, -1, -1, -1 },
        { 15, 16, 17, 18, 19, 20, 21, 23, -1, -1 },
        { 16, 17, 21, 23, 27, -1, -1, -1, -1, -1 }
};
int ptr[NUMLISTE] = {0,0,0,0,0};
#define	CAPOLISTA(k)	lista[k][ptr[k]]
int main()
{
	size_t	i = 0;
	int	n;
	for(;;)
	{
		if (0 == i)
			n = CAPOLISTA(0);
		while (CAPOLISTA(i) < n)
		{
			ptr[i]++;
			if (-1 == CAPOLISTA(i))
				return 0;
		}
		if (n == CAPOLISTA(i))
		{
			if ((++i) < NUMLISTE)
				continue;
			printf("%d\n", n);
		}
		ptr[i = 0]++;
	}
}
Leonardo SE&O
-- 
Nach doiligh domhsa mo chailin a mholadh
'S ni he amhain mar bhi si or
Bhi si mar gath greine a dhul in eadan na gloinne
Is bhi sceimh mhna na finne le mo cailin or

 più efficiente per farlo?
Ne terrò conto all'esame ;)
Giuseppe A.
-- 
questo articolo e` stato inviato via web dal servizio gratuito 
http://www.newsland.it/news
 segnala gli abusi ad 
ab...@newsland.it

 Riccardo Rossi.
Dato che la struttura lista la definisci tu, potresti tenere conto del
numero di elementi presenti in ogni lista, e ordinare le liste in ordine
crescente sul numero di elementi, poi confrontare le liste a due a due.
Le liste vanno confrontate con lo "stesso" procedimento che usa il merge
sort (prendi il piu' piccolo dei due e avanza) con un costo di O(l1.length
+ l2.length).
In questo modo se l'ultima delle tue liste ha solo 2 elementi e le prime
due ne hanno piu' di 400 di cui 300 in comune, tu non perdi tempo a
controllarli tutti, dato che alla fine al piu' avrai 2 elementi :)
Saluti
Paolo "AIR" F.


 Giuseppe A.
Ciao beppe non ti avevo visto
