The exercise is: The function takes as input a list of integers, i, and modifies it so that all even values are before the odd ones. The order in which the values appear is not important as long as all even values are before the odd ones. The function then returns the resulting list. The function must have computational complexity O (n) and a memory cost of O (1).
Basically, the function must modify the next field of the existing Items, without allocating new memory. Solutions that produce a new list to obtain the required result will not be considered valid. It is not allowed to change the values of the Items.
This is the "list.h" file
/** @file
Questo file contiene la definizione del tipo `Item` e la documentazione delle
funzioni primitive (e non) relative alle liste. Si noti che il comportamento di
queste funzioni è indipendente dalla definizione di `ElemType`.
*/
#ifndef LIST_H_
#define LIST_H_
#include "elemtype.h"
#include <stdbool.h>
#include <stdio.h>
/*****************************************************************************/
/* Item & Primitives */
/*****************************************************************************/
/** @brief Definizione del tipo `struct Item`. */
struct Item {
ElemType value; /*!< Valore associato all'`Item`. */
struct Item *next; /*!< Puntatore all'`Item` successivo. */
};
/** @brief Definizione di un nome alternativo per `struct Item`. */
typedef struct Item Item;
/** @brief La funzione `ListCreateEmpty()` crea e ritorna una lista vuota, ovvero
`NULL`.
@return Lista vuota (`NULL`).
*/
Item *ListCreateEmpty(void);
/** @brief La funzione `ListInsertHead()` aggiunge un nuovo elemento in testa ad
una lista e ritorna il puntatore alla nuova lista.
@param[in] e Puntatore all'elemento da aggiugnere in testa alla lista.
@param[in] i Lista a cui aggiungere il nuovo elemento. `i` può essere una lista
vuota (NULL).
@return Lista risultante.
*/
Item *ListInsertHead(const ElemType *e, Item *i);
/** @brief La funzione `ListIsEmpty(`) verifica se una lista è vuota.
@param[in] i Lista su cui eseguire la verifica.
@return `true` se la lista è vuota, `false` altrimenti.
*/
bool ListIsEmpty(const Item *i);
/** @brief La funzione `ListGetHead()` ritorna un puntatore all'elemento in testa
alla lista, senza rimuoverlo.
@param[in] i Lista da cui estrarre il valore in testa. Questa lista non può
essere vuota, nel caso in cui lo sia la funzione termina il programma
con codice di errore `1`.
@returns Puntatore all'elemento (costante) in testa alla lista.
*/
const ElemType *ListGetHeadValue(const Item *i);
/** @brief La funzione `ListGetTail()` ritorna la lista privata dell'elemento in
testa. La funzione NON dealloca la memoria occupata dalla testa
della lista.
@param[in] i Lista da cui ottenere la coda. La lista non può essere vuota,
nel caso in cui lo sia la funzione termina il programma con codice di
errore `2`.
@return Lista ottenuta dopo l'eliminazione della testa. Il valore di ritorno
potrebbe essere una lista vuota (`NULL`).
*/
Item *ListGetTail(const Item *i);
/** @brief La funzione `ListInsertBack()` aggiunge un elemento in coda ad una
lista (anche vuota) e ritorna la lista risultante.
@param[in] i Lista a cui aggiungere l'elemento specifciato. Questa lista può
essere vuota (`NULL`).
@param[in] e Puntatore all'elemento da aggiugnere in testa alla lista. Il valore
contenuto in e non viene modificato.
@return Lista ottenuta dopo l'aggiunta dell'elemento.
*/
Item *ListInsertBack(Item *i, const ElemType *e);
/** @brief La funzione `ListDelete()` libera la memoria occupata dagli elementi di
una lista.
@param[in] i Lista di cui liberare la memoria, può essere vuota (`NULL`).
@return Non ci sono valori di ritorno.
*/
void ListDelete(Item *i);
/*****************************************************************************/
/* Non Primitives */
/*****************************************************************************/
/** @brief La funzione `ListWrite()` stampa la lista specificata su file.
Nello specifico, la funzione stampa il carattere "[" seguito dagli
elementi della lista, separati dai caratter ", ", e dal carattere "]".
La stampa degli elementi dipende dalla definizione di `ElemType`.
@param[in] i Lista da stampare su file: può essere vuota e non viene modificata.
@param[in] f `FILE *` su cui stampare la lista.
@return Non ci sono valori di ritorno.
*/
void ListWrite(const Item *i, FILE *f);
/** @brief La funzione `ListWriteStdout()` stampa la lista specificata su `stdout`.
Nello specifico, la funzione stampa il carattere "[" seguito dagli
elementi della lista, separati dai caratter ", ", e dal carattere "]".
La stampa degli elementi dipende dalla definizione di `ElemType`.
@param[in] i Lista da stampare su `stdout`: può essere vuota e non viene modificata.
@return Non ci sono valori di ritorno.
*/
void ListWriteStdout(const Item *i);
#endif // LIST_H_
This is "elemtype.h" file:
/** @file
Questo file contiene la definizione di `ElemType` per il tipo `int` e la
documentazione delle funzioni a esso associate.
*/
#ifndef ELEMTYPE_INT_H_
#define ELEMTYPE_INT_H_
#include <stdbool.h>
#include <stdio.h>
/** @brief Definizione di `struct ElemType`. */
typedef int ElemType;
/** @brief La funzione `ElemCompare()` confronta due elementi.
@param[in] e1 Puntatore al primo elemento di cui eseguire il confronto. Il
valore contenuto in `e1` non viene modificato.
@param[in] e2 Puntatore al secondo elemento di cui eseguire il confronto. Il
valore contenuto in `e2` non viene modificato.
@return La funzione ritorna un valore intero che indica la relazione tra i due
elementi, ovvero:
- `< 0` (ad esempio `-1`) se il contenuto del primo è minore di quello del secondo;
- `0` se i contenuti dei due elementi sono uguali;
- `> 0` (ad esempio `1`) se il contenuto del primo è maggiore di quello del secondo.
*/
int ElemCompare(const ElemType *e1, const ElemType *e2);
/** @brief La funzione `ElemCopy()` crea e ritorna una copia dell'elemento dato.
@param[in] e Puntatore all'elemento da copiare. Il valore contenuto in `e` non
viene modificato.
@return Copia dell'elemento `e`.
*/
ElemType ElemCopy(const ElemType *e);
/** @brief La funzione `ElemSwap()` scambia i due elementi specificati.
@param[in] e1 Puntatore al primo elemento da scambiare.
@param[in] e2 Puntatore al secondo elemento da scambiare.
@return Non ci sono valori di ritorno.
*/
void ElemSwap(ElemType *e1, ElemType *e2);
/** @brief La funzione `ElemDelete()` libera la memoria occupata dall'elemento
specificato.
@param[in] e Puntatore all'elemento di cui liberare la memoria.
@return Non ci sono valori di ritorno.
*/
void ElemDelete(ElemType *e);
/** @brief La funzione `ElemRead()` legge un elemento da file.
@param[in] f `FILE *` da cui leggere un elemento.
@param[out] e Elemento letto da file.
@return Se la lettura va a buon fine la funzione ritorna `1`, altrimenti ritorna `0`
in caso di errore di corrispondenza, errore di lettura o fine del file. Se
si verifica un errore di lettura o si raggiunge la fine del file prima che
qualunque dato possa essere letto correttamente la funzione ritorna EOF,
ovvero un numero negativo.
*/
int ElemRead(FILE *f, ElemType *e);
/** @brief La funzione `ElemReadStdin()` legge un elemento da `stdin`.
@param[out] e Elemento letto da `stdin`.
@return Se la lettura va a buon fine la funzione ritorna `1`, altrimenti ritorna `0`
in caso di errore di corrispondenza, errore di lettura o fine del file. Se
si verifica un errore di lettura o si raggiunge la fine del file prima che
qualunque dato possa essere letto correttamente la funzione ritorna EOF,
ovvero un numero negativo.
*/
int ElemReadStdin(ElemType *e);
/** @brief La funzione `ElemWrite()` stampa un elemento su file.
@param[in] e Puntatore all'elemento da stampare su file. Il valore contenuto in
e non viene modificato.
@param[in] f `FILE *` su cui stampare l'elemento.
@return Non ci sono valori di ritorno.
*/
void ElemWrite(const ElemType *e, FILE *f);
/** @brief La funzione `ElemWriteStdout()` stampa un elemento su `stdout`.
@param[in] e Puntatore all'elemento da stampare su `stdout`. Il valore
contenuto in `e` non viene modificato.
@return Non ci sono valori di ritorno.
*/
void ElemWriteStdout(const ElemType *e);
#endif // ELEMTYPE_INT_H_
This should be the solution but I don't know how to proceed, because I don't know how to change the next field:
#include"list.h"
Item* PariDispari(Item* i) {
if(ListIsEmpty(i) ||ListIsEmpty(ListGetTail(i)))
return NULL;
Item* tmp = ListGetTail(i);
while (!ListIsEmpty(tmp)) {
if (tmp->value % 2 == 0) {
tmp->next = ListGetHeadValue(i);
}
tmp = ListGetTail(tmp);
}
return i;
}
The "list.h" file cannot be edited
CodePudding user response：
The task at hand is about pointer juggling; that's it. The list is filled with nodes of even and odd values interspersed. The task is to wire them into a list of all even, then all odd, values, with NO reallocations, and NO node overwrites (e.g. pure pointer juggling).
There are multiple ways you can do this. A fairly easy one to understand is this:
Algorithm
- Setup two lists (initially empty), one "even", one "odd".
- As you walk the original list pruning nodes, put them on the "even" list or the "odd" list as warranted.
- When finished, link the odd list to the tail of the even list;
- The final result is not pointed to by the "even" list and you're done.
Walkthrough
In (admittedly dreadful) asci art, it looks something like this. Given an original list of
head -> 1 -> 2 -> 3 -> 4 -> 5 ->|
Create two empty lists (e..g two null pointers).
even ->|
odd ->|
Take the first node off the list, keeping a pointer p to it, and advance the head pointer.
head -> 2 -> 3 -> 4 -> 5 ->|
even ->|
odd ->|
p -> 1
Now link p to the proper list. In this case, the odd list.
head -> 2 -> 3 -> 4 -> 5 ->|
even ->|
odd -> 1 ->|
That process repeats until you have the following:
head ->|
even -> 2 -> 4 ->|
odd -> 1 -> 3 -> 5 ->|
And now all you have left is linking the head of the odd list to the tail of the even list:
even -> 2 -> 4 -> 1 -> 3 -> 5 ->|
And you're finished.
Code
Given a simple list structure (tried to use your same name):
typedef struct Item Item;
struct Item
{
int value;
Node *next;
};
The code to accomplish the algorithm is below. This has the added feature of preserving the order of the original elements, even though that is not a requirement:
Item* PariDispari(Item* src)
{
Item *even = NULL;
Item **ppEven = &even; // always point to the next place to hang an even node.
Item *odd = NULL;
Item **ppOdd = &odd; // always points to the next plain to hang an odd node.
while (src != NULL)
{
// remember node, then advance src.
Item *p = src;
src = src->next;
if (p->value % 2) // odd ?
{
// tack on to end of odd list, then move ppOdd down
// to the next member of the node we just linked.
*ppOdd = p;
ppOdd = &p->next;
}
else
{
// tack on to end of even list, then move ppEven down
// to the next member of the node we just linked.
*ppEven = p;
ppEven = &p->next;
}
}
// terminate the odd list, then link the head of the
// odd list to the tail of the even list
*ppOdd = NULL;
*ppEven = odd;
// this is our final list;
return even;
}
There are other ways to do this, but this is easily the most basic to understand. Just keep chaining nodes to their respective target lists until the source (the input list) is exhausted, then link the head of one to the tail of the other.
Alternative
You could treat the linked list like a deque. All even nodes are pushed (moved) on to the front of the queue, all odds are pushed on to the tail. When you're done the the even nodes will be first in the list, but will be in opposite order of their original order in the input list. The odd nodes will be in the same original order after all the evens. For our example the result would look like this:
4 -> 2 -> 1 -> 3 -> 5 ->|
This method requires one less regular pointer, and one less pointer-to-pointer, but some additional logic on how to manage both. I leave that as an exercise for you.