Fusió ordenada de dues seqüències d'items amb valors creixents X23359

Preliminars

En aquest exercici treballarem sobre la següent estructura de dades, que ens serveix per a mantenir una seqüència de valors dins de items encadenats mitjançant punters.

struct Item {
 int value;
 Item* next;
};

Exercici

Implementeu una funció RECURSIVA que, donats dos Item* que apunten a seqüències d’items encadenats tals que tenen els seus valors ordenats creixentment, retorna un altre Item* que apunta a una nova seqüència que és la fusió ordenada de les dues seqüències originals. En altres paraules, la nova seqüència d’items no comparteix memòria amb les original, i la seva seqüència de valors és la que s’obtindria posant en una llista els valors de les dues seqüències originals i ordenant-los creixentment.

// Pre:  pitem1, pitem2 apunten als primers elements de seqüències correctes d'items encadenats.
//       Els últims elements de les seqüències apunten a NULL. Els propis pitem1,pitem2 podrien
//       ser NULL, cas en el qual no hi hauria elements a les respectives seqüències.
// Post: Retorna un Item* que representa la fusió ordenada de les dues seqüències originals.
//       Les seqüències de valors originals no han canviat.
Item* merge(Item* pitem1, Item* pitem2);

Aquí tenim un exemple de paràmetres entrada i sortida de la funció:

merge([1]->[4]->[4]->[8]->[9]->NULL, [2]->[2]->[4]->[5]->NULL) =
      [1]->[2]->[2]->[4]->[4]->[4]->[5]->[8]->[9]->NULL

Fixeu-vos que l’enunciat d’aquest exercici ja ofereix uns fitxers que haureu d’utilitzar per a compilar: Makefile, program.cpp, merge.hpp. Us falta crear el fitxer merge.cpp amb els corresponents includes i implementar-hi la funció anterior. Quan pugeu la vostra solució al jutge, només cal que pugeu un tar construït així:

tar cf solution.tar merge.cpp

Entrada

L’entrada té un nombre arbitrari de casos. Cada cas consisteix en dues línia, on cadascuna conté una llista de valors enters ordenats creixentment. Fixeu-vos en que el programa que us oferim ja s’encarrega de llegir aquestes entrades. Només cal que implementeu la funció abans esmentada.

Sortida

Per a cada cas, la sortida conté tres línies, les dues primeres amb les mateixes llistes originals, i la tercera amb la llista resultant de la fusió ordenada. Fixeu-vos en que el programa que us oferim ja s’encarrega d’escriure aquestes dades. Només cal que implementeu la funció abans esmentada.