[C++] esercizio liste

[xrwnis]

Avendo due liste L1 ed L2(ordinata), devo scrivere una procedura che sposti tutti gli elementi di L1 in L2 in modo che alla fine L2 risulti ancora ordinata. Qualche idea?? Grazie mille...

Ho scritto questa ma non funziona... Se conoscete un altro metodo potete anche postare tutto senza correggere questa...

void ordina(Pnodo L1,Pnodo & TL2,Pnodo L2)
{Pnodo tmp;
     if(L1!=NULL)
     {
        if(L2->next==NULL)
        {
            L2->next=L1;
            L2->next->next=NULL;
            L1=L1->next;
            return ordina(L1,TL2,TL2);              
        }    
             
        else if((L1->info>L2->info)&&(L1->info<L2->next->info))
        {
        
           tmp=L2->next;
           L2->next=L1;
           L2->next->next=tmp;                                               
           L1=L1->next;
           return ordina(L1,TL2,TL2);
        }
        else
        return ordina(L1,TL2,L2->next);

     }
}

[LeleFT]

Originariamente inviato da xrwnis
Se conoscete un altro metodo potete anche postare tutto senza correggere questa...

Come a dire... se qualcuno me lo corregge tante grazie, altrimenti fatemelo...

E' così?


Ciao.

[xrwnis]

L'ho detto perchè a volte può risultare più semplice ricominciare da capo piuttosto che trovare l'errore... E poi non sono sicura che il mio ragionamento sia il migliore...

[LeleFT]

Originariamente inviato da xrwnis
L'ho detto perchè a volte può risultare più semplice ricominciare da capo piuttosto che trovare l'errore...

Questo è vero: hai provato a ricominciare da capo?

E poi non sono sicura che il mio ragionamento sia il migliore...

Ma non hai spiegato qual è il tuo ragionamento...

Una buona base di partenza potrebbe essere l'algoritmo MergeSort, in particolare la procedura chiamata "merge".


Ciao.

[Vincenzo1968]

Originariamente inviato da LeleFT
...
Una buona base di partenza potrebbe essere l'algoritmo MergeSort, in particolare la procedura chiamata "merge".
...

Non mi pare una buona idea essendo la lista già ordinata.
Io farei cosi:

typedef struct tagLista
{
	int valore;
	struct tagLista* next;
} Lista;

Lista* NewNode(int val)
{
	Lista *n;

	n = (Lista *)malloc(sizeof(Lista));

	if( n == NULL )
		return NULL;

	n->valore = val;
	n->next = NULL;

	return n;
}

Lista* Append(Lista* first, int val)
{
	Lista *n = first, *nuovo;

	// catena vuota
	if ( first == NULL )
		return NewNode(val);

	n = first;
	while( n->next != NULL )
	{
		n = n->next;
	}

	nuovo = NewNode(val);
	n->next = nuovo;

	return first;
}

void Free(Lista* first)
{
	Lista *n1 = first, *n2;
	while ( n1 != NULL )
	{
		n2 = n1->next;
		free(n1);
		n1 = n2;
	}
}

Lista* ordina(Lista* L1, Lista* L2)
{
	Lista *n;
	Lista *tmp1, *tmp2;
	Lista *tmpPrev;

	if ( L1 == NULL )
		return L2;

	if ( L2 == NULL )
		return NULL;

	tmp1 = L1;
	while ( tmp1 != NULL )
	{
		tmp2 = L2;
		tmpPrev = NULL;
		while ( tmp2 != NULL )
		{
			if ( tmp2->valore > tmp1->valore )
			{
				n = (Lista *)malloc(sizeof(Lista));
				if ( !n )
				{
					printf("Memoria insufficiente");
					return L2;
				}
				n->valore = tmp1->valore;
				n->next = tmp2;		
				if ( tmpPrev )
					tmpPrev->next = n;
				break;
			}
			else if ( tmp2->next == NULL )
			{
				n = (Lista *)malloc(sizeof(Lista));
				if ( !n )
				{
					printf("Memoria insufficiente");
					return L2;
				}
				n->valore = tmp1->valore;
				n->next = NULL;		
				tmp2->next = n;
				break;
			}
			tmpPrev = tmp2;
			tmp2 = tmp2->next;
		}
		tmp1 = tmp1->next;
	}

	return L2;
}

void Print(Lista *first)
{
	Lista *n = first;

	while( n != NULL )
	{
		printf("%d\n", n->valore);
		n = n->next;
	}
}

int main()
{
	Lista* pLista = NULL;
	Lista* pLstTmp = NULL;

	pLista = Append(pLista, 1);
	pLista = Append(pLista, 3);
	pLista = Append(pLista, 5);
	pLista = Append(pLista, 8);
	pLista = Append(pLista, 13);

	pLstTmp = Append(pLstTmp, 6);
	pLstTmp = Append(pLstTmp, 4);
	pLstTmp = Append(pLstTmp, 2);
	pLstTmp = Append(pLstTmp, 21);

	pLista = ordina(pLstTmp, pLista);

	printf("\n");
	Print(pLista);
	printf("\n");

	Free(pLista);
	Free(pLstTmp);

	return 0;
}

[LeleFT]

Originariamente inviato da Vincenzo1968
Non mi pare una buona idea essendo la lista già ordinata.

Io parlavo della funzione "merge" che, guarda caso, prende due array già ordinati e li fonde...


Ciao.

[Vincenzo1968]

Originariamente inviato da LeleFT
Io parlavo della funzione "merge" che, guarda caso, prende due array già ordinati e li fonde...

Ciao.

Qui però abbiamo a che fare con liste concatenate, non con array(e una delle due, L1, non è affatto ordinata).
Il metodo che ho utilizzato lo trovi in ogni buon testo sugli algoritmi(per esempio, il Sedgewick).

[LeleFT]

Originariamente inviato da Vincenzo1968
Qui però abbiamo a che fare con liste concatenate, non con array(e una delle due, L1, non è affatto ordinata).
Il metodo che ho utilizzato lo trovi in ogni buon testo sugli algoritmi(per esempio, il Sedgewick).

E infatti io dicevo che quello era un punto di partenza... poi se non erro l'autore diceva che una delle due liste era ordinata...

Avendo due liste L1 ed L2(ordinata)

C'è una bella differenza tra "cercare una soluzione" e "farsi dare la soluzione"...


Ciao.