Newsgroup: it.comp.lang.c
Titolo: fusione di liste

Salve ho il seguente problema
ho due liste singolarmante concatenate la cui ctruttura e':
struct nodo{
    int n;
    struct nodo  *next;
                };
le due liste hanno i campi n ordinati in modo crescente
cioe' ad esempio lista1{1,3,5} e lista 2{2,4,10}
il mio problema e' fondere le due liste in modo tale da avere alla fine
una nuova lista i cui campi n sono ordinati,
usando l'esempio precedente avro' nuovalista{1,2,3,4,10}
non devo pero' usare nodi addizionali per ottenere cio',alla fine del
processo le due liste devono scomparire e mi deve rimanere
solo la lista fusa
per fare cio' ho usato, senza risultati quuesta funzione
prima, seconda nuova puntano rispettivamente all'inizio della prima ,
seconda e nuova lista fusione
void fondi(struct nodo **prima,struct nodo **seconda,struct nodo
**nuova)
{
 struct nodo *ntmp,*lista1,*lista2;
   lista1=*prima;
   lista2=*seconda;
   ntmp=*nuova;
   while(lista1&&lista2)
    {
       if(lista1->n<=lista2->n)
          {
              ntmp=lista1;
              ntmp=ntmp->next;
              lista1=lista1->next;
             }
           else
            {
              ntmp=lista2;
                ntmp=ntmp->next;
                lista2=lista2->next;
              }
       }
    if(!lista1)
     {
       while(lista2)
        {
             ntmp=lista2;
             ntmp=ntmp->next;
               lista2=lista2->next;
            }
       }
       else
        {
          while(lista1)
             {
                ntmp=lista1;
                  ntmp=ntmp->next;
                  lista1=lista1->next;
               }
         }
}

ASD homework3 ?
stesso problema...  ;-)
byez

SnakeEyes wrote:

perdonami ma non ho capito la risposta.. :)

"Giovanni Casu" <qgio...@tin.itq> ha scritto nel messaggio
news:3AC60D2A...@tin.itq...

Quello che è sbagliato è l'ordine delle assegnazioni. In realtà si dovrebbe
assegnare "ntmp->next" e non "ntmp". Una possibile sintassi corretta dei
tuoi if è la seguente...
if (lista1->n<=lista2->n)
   {
  ntmp=lista1;
  lista1=lista1->next;
   }
   else
   {
  ntmp=lista2;
  lista2=lista2->next;
   }
...giusto per sapere da che parte partire...
nuova = ntmp;
...è l'inizio della lista ordinata. Quindi...
   while(lista1 && lista2)
   {
       if(lista1->n<=lista2->n)
       {
        ntmp->next=lista1;    /* Sto assegnando il valore del "next" */
        ntmp=ntmp->next;
        lista1=lista1->next;
       }
   else
   {
         ntmp->next=lista2;    /* Idem qui */
         ntmp=ntmp->next;
         lista2=lista2->next;
   }
}
...eccetera eccetera.
Vedrai che funziona.
Riz

 Riz
mi segnala un errore quando arriva alla riga
ntmp->next=lista1;
tieni presente che nuova e ntmp all'inizio puntano a niente
quindi all'inizio la lista fusione e' vuota ,cioe'(a parer mio)
prima di creare la lista fusione si ha:
ntmp->niente
ntmp->next=ancoraniente
se allora stabilisco che lista1->n<=lista2->n
dovrei assegnare l'oggetto puntato da lista1 a ntmp
avevo risolto questo problema aggiungendo uno alla volta gli elementi di lista2
a lista1 e mettendoli in ordine
ma il testo del problema chiede che lista1 e lista2 non esisteno piu' alla fine

scusa sono stato poco chiaro ... è solo una coincidenza , ma per ho un
esercizio da consegnare
che è molto simile al tuo problema...
;-)

 ;-)
la mia e' un'esercitazione
devo consegnarla quando ci sara' l'esame , credo fra 2 mesi


Scusate, esame di cosa?
Enrico S.

"Enrico S." wrote:

Algoritmi e Strutture Dati

"Giovanni Casu" <qgio...@tin.itq> ha scritto nel messaggio
news:3AC6447C...@tin.itq...

Tutto dipende da che cosa intendi per "non esistano piu' alla fine". Per me
ntmp era semplicemente un puntatore al primo nodo. Senza elementi
successivi. Alla fine del programma, ntmp (o nuova) puntava al primo
elemento della lista 1, ma nessuno degli interi era stato spostato dalla sua
locazione di memoria originale. La nuova lista è stata creata reindirizzando
i next opportunamente. E questo fa "sparire" le due liste separate iniziali,
ovviamente. Però gli interi sono ancora al posto di prima. Se invece vuoi
fare una terza lista, devi assegnare i puntatori in modo diverso, creando
prima la catena e copiando solo gli interi. Per questo non mi sembrava che
volessi fare così. E poi devi cancellare a mano le liste vecchie. Spero che
anche in un progetto per un esame ti lascino la libertà di usare uno schema
piuttosto che un altro... soprattutto se è piu' efficiente.
Vorrei sapere che tipo di errore ti dà in fase di assegnazione.
Probabilmente un errato abbinamento di tipo...comunque ti consiglio di
cambiare la procedura così:
void fondi(struct nodo *prima,struct nodo *seconda,struct nodo *nuova)
{
   struct nodo *ntmp,*lista1,*lista2;
   lista1=prima;
   lista2=seconda;
    ... ... ...
In effetti mi domandavo perché passare dei puntatori a puntatore, quando è
sufficiente passare la locazione del primo elemento della lista (è uno dei
vantaggi nell'uso delle liste, appunto). Così non dovrebbe dare problemi
(con la modifica di prima).
Riz

Dove frequenti l'università ? Sto anche io preparando lo stesso esame...
ciao

Marco Rizzardi wrote:Tutto dipende da che cosa intendi per "non esistano piu'


Mi da' Fault:access violation at blablabla
Non ho passato i puntatori ,ma i loro indirizzi, perche' credo che una volta
uscito dalla funzione i nuovi riferimenti ai nodi della lista sarebbe stati
distrutti

 ciao
A Cagliari Diploma di informatica , penso che a breve aggiungeranno due anni
per farne un corso di laurea
E tu?


Prova cosě : la tua soluzione proprio non la capisco.
#include <stdlib.h>
#include <stdio.h>
#include "c:\ASD\lista.h"
c_list* fondi(c_list** a, c_list** b)
{
 c_list* c;
 c = crea_lista();
 while(!vuota(*a) || !vuota(*b))
 {
  if(!vuota(*a) &&  leggi(*a, *a) < leggi(*b, *b))
  {
   c = insert(c, c, leggi(*a, *a));
   *a = canc_head(*a);
  }
  else if(!vuota(*b))
  {
    c = insert(c, c, leggi(*b, *b));
   *b = canc_head(*b);
  }
 }
 return c;
}
main()
{
 c_list* a, *b, *c;
 int n;
 a = crea_lista();
 b = crea_lista();
 a = insert(a, a, 3);
 a = insert(a, a, 1);
 b = insert(b, b, 4);
 b = insert(b, b, 2);
 c = fondi(&a, &b);
 while(!vuota(c))
 {
  n = leggi(c, c);
  printf("%d", n);
  c = succ(c, c);
 }
 printf("\n");
 while(!vuota(a))
 {
  printf("%d", leggi(a, a));
  a = succ(a, a);
 }
 printf("\n");
 while(!vuota(b))
 {
  printf("%d", leggi(b, b));
  b = succ(b, b);
 }
 return 0;
}
dove c_list č definito come
typedef struct c_list{
    int key;
    strcuct c_list* nect;
}c_list;

iGor wrote:

Scusa ma le funzioni che usi sono in lista.h?
se si' some sono fatte?


c_list* crea_lista(void)
{
 return NULL;
}
bool vuota(c_list* list)
{
 return list == NULL;
}
c_list* succ(c_list* list, c_list* nodo)
{
 return nodo->next;
}
c_list* insert(c_list* list, c_list* pos, int k)
{
 c_list* temp;
 temp = malloc(sizeof(c_list));
 if(vuota(list))
 {
  temp->next = NULL;
  temp->key = k;
  return temp;
 }
 temp->key = leggi(list, pos);
 temp->next = succ(list, pos);
 pos->key = k;
 pos->next = temp;
 return list;
}
c_list* canc_head(c_list* list) //cancella il nodo in testa
{
 c_list* temp;
 temp = list;
 list = succ(list, list);
 free(temp);
 return list;
}

iGor wrote:

la funzione leggi?

 solo la lista fusa
ecco il mio contributo:
struct nodo * SortedMerge ( struct nodo * l1,struct nodo * l2 )
{
  struct nodo *lm, *plm;
    if( l1->n < l2->n )
    {
      lm=plm=l1;
      l1=l1->next;
    }
    else
    {
      lm=plm=l2;
      l2=l2->next;
    }
    while( l1 && l2 )
    {
      if( l1->n < l2->n )
      {
        plm->next = l1;
        l1=l1->next;
      }
      else
      {
        plm->next = l2;
        l2=l2->next;
      }
    }
  if( l1 )   plm->next = l1;
  else      plm->next = l2;
  return lm;
}
Limiti: le liste in input devono avere almeno 1 elemento.
ciao
donCiccio

"Giovanni Casu" <qgio...@tin.itq> ha scritto nel messaggio
news:3AC7508E...@tin.itq...

me la ereo dimenticata
int leggi(c_list* list, c_list* nodo)
{
    return nodo->key;
}

 donCiccio
Dunque .. ho usato quatsa funzione per visualizzare la nuova lista
void display(struct nodo *lm)
{
     clrscr();
     do{
      printf(" %d \n", lm -> n);
       lm = lm -> next;
           }while( lm! = NULL);
}
dovrebbe essere corretta e mi restituisce il primo e l'ultimo elemento
in ordine crescente delle 2 liste
se le liste 1 e 2 sono l1=(1,3),l2=(2,4)
mi da' (1,4)
cmq e' il miglior risultato finora ottenuto

Don Ciccio sei un mito ho aggiunto un paio di righe alla tue funzione e
"funziona"!
plm->next = l1;
plm->next=plm;  //HO AGGIUNTO QUESTA
l1=l1->next;
plm non andava avanti ,gli si assegnava ogni volta il nodo giusto fino
all'ultimo
e per questo quando stampavo lm ottenevo il primo  e l'ultimo nodo
corretti
grazieeeee

Giovanni Casu wrote:

plm=plm->next //questa cioe'

Ho provato a modificare la funzione come hai detto ... ma se ho
lista a
1 -> 3 -> 5 -> null
lista b
2 -> 4-> 6 -> null
la lista c dopo la fusione di a e b  viene
1 -> 6 -> null
come mai ?  ecco lap rocedura puoi dirmi dove č l'errore ?  GRAZIE !
LISTA fondi(LISTA a, LISTA b)
{
  LISTA lm, plm;
  if((a -> d)<(b -> d)){
    lm = plm = a;
    a = a -> next;
  } else {
    lm = plm  = b;
    b = b -> next;
  }
  while(a && b){
    if((a -> d)<(b -> d)){
      plm -> next = a;
      plm -> next = plm;
      a = a -> next;
    } else {
      plm -> next = b;
      plm -> next = plm;
      b = b -> next;
    }
  }
  if(a)
    plm -> next = a;
  else
    plm -> next = b;
  return (lm);
}

ho visto solo adesso il secondo post... sorry
;-)

"Nick(r)" wrote:

ho sostituito il codice seguente al punto della parte if(a)....else..
return(lm);
 if( !l1 )
  {
    while(l2)
        {
             plm->next=l2;
               plm=plm->next;
               l2=l2->next;
            }
       }
       else
        {
          while(l1)
             {
                plm->next=l1;
                  plm=plm->next;
                  l1=l1->next;
               }
               }
  return lm;

  if( l1 )   plm->next = l1;
quest'ultima riga non hai isogno di trasformarla in un while, come hai fatto
in un post seguente, perche' da qui in poi la lista e' gia' ordinata, e'
quella di ingresso.
ciao
donCiccio

Dove studi? A torino quell'esame l'ho dato a novembre...
Ciiips
Enrico S.
--
Webmaster della Pagina NON Ufficiale del SonyCRX100
SonyCRX120,  SonyCRX140E/S, SonyCRX100EX, HP8100
HP8200, HP9100 & HP9200
http://www.freeweb.org/computer/SonyCRX100/

"Enrico S." wrote:

studio a cagliari
sono al primo anno del diploma in informatica
strutture dati e' nel secondo semestre