AppletTalk.com Java discussions newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  Ordinare numeri da due liste          AppletTalk.com Forum Index -> Java (Italian) View previous topic :: View next topic   Author Message Newbie Guest Posted: Fri Jun 23, 2006 5:43 pm    Post subject: Ordinare numeri da due liste Ciao a tutti, Mi trovo con due liste ordinate L1 ed L2 i cui elementi sono formati da un campo "valore" (un numero intero) e da un campo "prox" che punta all'elemento successivo ("nil" quando non ci sono altri elementi). Gli elementi sono disposti in ciascuna lista in ordine crescente di valore. Qual è secondo voi l'algoritmo Java più ottimale per fargli stampare *in ordine crescente* la combinazione degli elementi di entrambe le liste? Ad esempio, se la prima lista e' formata dai valori 3, 7, 8, 23, e la seconda dai valori 5, 6, 30, dovrei fargli stampare la lista 3, 5, 6, 7, 8, 23, 30. Ringrazio in anticipo chiunque sappia aiutarmi Paolo -- questo articolo e` stato inviato via web dal servizio gratuito http://www.newsland.it/news segnala gli abusi ad abuse (AT) newsland (DOT) it Back to top Giambo Guest Posted: Fri Jun 23, 2006 10:47 pm    Post subject: Re: Ordinare numeri da due liste Newbie wrote: Quote: Mi trovo con due liste ordinate L1 ed L2 i cui elementi sono formati da un campo "valore" (un numero intero) e da un campo "prox" che punta all'elemento successivo ("nil" quando non ci sono altri elementi). Come sono implementate le liste ? Cioe', usi una struttura dati standard di Java ? -- Giambo - Occhio al filtro antispam _e_ alla whitelist ! Back to top Pietro Guest Posted: Mon Jun 26, 2006 2:13 pm    Post subject: Re: Ordinare numeri da due liste Newbie ha scritto: Quote: Ciao a tutti, Mi trovo con due liste ordinate L1 ed L2 i cui elementi sono formati da un campo "valore" (un numero intero) e da un campo "prox" che punta all'elemento successivo ("nil" quando non ci sono altri elementi). Gli elementi sono disposti in ciascuna lista in ordine crescente di valore. Qual è secondo voi l'algoritmo Java più ottimale per fargli stampare *in ordine crescente* la combinazione degli elementi di entrambe le liste? Ad esempio, se la prima lista e' formata dai valori 3, 7, 8, 23, e la seconda dai valori 5, 6, 30, dovrei fargli stampare la lista 3, 5, 6, 7, 8, 23, 30. Ringrazio in anticipo chiunque sappia aiutarmi Paolo Metti i dati in un'unica lista e ordina questa, complessità: O(n*log(n)+n) = O(nlog(n)) quindi è il miglior modo Back to top CarMas Guest Posted: Mon Jun 26, 2006 4:35 pm    Post subject: Re: Ordinare numeri da due liste Pietro ha scritto: Quote: Metti i dati in un'unica lista e ordina questa, complessità: O(n*log(n)+n) = O(nlog(n)) quindi è il miglior modo Dici col mergesort? Una cosa tipo questa: http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/merge/mergen.htm Non vorrei dire una stupidaggine, ma probabilmente ci si guadagna pure qualcosa rispetto alla stima della complessita', perche' l'ipotesi di partenza e' gia' di due liste ordinate (quindi rimane solo la parte di merge). Quindi io mi sentirei di consigliare all'autore del post originale di fare un semplice ciclo di confronto fra i primi elementi di entrambe le liste e prendere il piu' piccolo, procedendo finche' una delle due liste non e' vuota e a quel punto prendere tutti gli eventuali elementi rimasti nell'altra lista. Caso peggiore 2n confronti direi. Saluti CarMas Back to top Pietro Guest Posted: Tue Jun 27, 2006 12:57 pm    Post subject: Re: Ordinare numeri da due liste CarMas ha scritto: Quote: Dici col mergesort? Una cosa tipo questa: http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/merge/mergen.htm Non vorrei dire una stupidaggine, ma probabilmente ci si guadagna pure qualcosa rispetto alla stima della complessita', perche' l'ipotesi di partenza e' gia' di due liste ordinate (quindi rimane solo la parte di merge). Quindi io mi sentirei di consigliare all'autore del post originale di fare un semplice ciclo di confronto fra i primi elementi di entrambe le liste e prendere il piu' piccolo, procedendo finche' una delle due liste non e' vuota e a quel punto prendere tutti gli eventuali elementi rimasti nell'altra lista. Caso peggiore 2n confronti direi. Saluti CarMas Si se sono già ordinate è sicuramente più veloce.. però deve scriversi l'ultimo pezzo del merge.. Visto il link postato da te però questo dovrebbe essere molto facile... Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         AppletTalk.com Forum Index -> Java (Italian) All times are GMT Page 1 of 1   Jump to: Select a forum Java Newsgroups----------------Java DiscussionsWeb-based java games comp.lang.java 3D Graphics API's for Java Java: Support and criticism Java System Announcements comp.lang.java.api JavaBeans Java and CORBA Java and Databases comp.lang.java.developer Java GUI Toolkits Java Help comp.lang.java.javascript JVM, native methods and hardware comp.lang.java.misc Java Language Programming Security and Java comp.lang.java.setup Java Software Tools comp.lang.java.tech ibm.software.java.linux  Non-English Java Newsgroups----------------Java Language (German)Language Java (Français)Java (Italian)  You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum Powered by phpBB © 2001, 2006 phpBB Group SEO toolkit © 2004-2006 webmedic.