C语言修改列表练习，只修改下一个字段
Exercise on modifying a list in C language, modifying only the next field
练习是：该函数将整数列表 i 作为输入，并对其进行修改，以便所有偶数值都在奇数之前。只要所有偶数值都在奇数之前，值出现的顺序并不重要。该函数然后 returns 结果列表。该函数必须具有 O(n) 的计算复杂度和 O(1) 的内存成本。
基本上，该函数必须修改现有项目的下一个字段，而无需分配新内存。生成新列表以获得所需结果的解决方案将被视为无效。不允许更改项目的值。
这是“list.h”文件
/** @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_
这是“elemtype.h”文件：
/** @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_
这应该是解决方案，但我不知道如何继续，因为我不知道如何更改下一个字段：
#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;
}
无法编辑“list.h”文件
手头的任务是指针杂耍；那就是它。该列表充满了散布的偶数和奇数值的节点。任务是将它们连接到一个列表中，所有偶数，然后所有奇数，值，没有重新分配，没有节点覆盖（例如纯指针杂耍）。
有多种方法可以做到这一点。一个相当容易理解的是：
算法
- 设置两个列表（初始为空），一个“偶数”，一个“奇数”。
- 当您遍历原始列表修剪节点时，根据需要将它们放在“偶数”列表或“奇数”列表中。
- 完成后，link奇数列表到偶数列表的尾部；
- 最终结果没有被“偶数”列表指向，你就完成了。
演练
在（公认的可怕的）asci 艺术中，它看起来像这样。给出
的原始列表
head -> 1 -> 2 -> 3 -> 4 -> 5 ->|
创建两个空列表（例如两个空指针）。
even ->|
odd ->|
从列表中取出第一个节点，保留指向它的指针p，并推进头指针。
head -> 2 -> 3 -> 4 -> 5 ->|
even ->|
odd ->|
p -> 1
现在 link p 到正确的列表。在本例中，odd 列表。
head -> 2 -> 3 -> 4 -> 5 ->|
even ->|
odd -> 1 ->|
重复该过程，直到您拥有以下内容：
head ->|
even -> 2 -> 4 ->|
odd -> 1 -> 3 -> 5 ->|
现在你只剩下 link 将 odd 列表的头部连接到 even 列表的尾部：
even -> 2 -> 4 -> 1 -> 3 -> 5 ->|
你完成了。
代码
给定一个简单的列表结构（尝试使用您的同名）：
typedef struct Item Item;
struct Item
{
int value;
Node *next;
};
实现算法的代码如下。这具有保留原始元素顺序的附加功能，即使这不是必需的：
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;
}
还有其他方法可以做到这一点，但这是很容易理解的最基本的方法。只需将节点链接到它们各自的目标列表，直到源（输入列表）用完，然后 link 一个的头部到另一个的尾部。
备选
您可以将 linked 列表视为 deque。所有偶数节点都被推（移）到队列的前面，所有奇数都被推到尾部。完成后，偶数节点将排在列表的第一位，但与它们在输入列表中的原始顺序相反。在所有偶数之后，奇数节点将处于相同的原始顺序。对于我们的示例，结果将如下所示：
4 -> 2 -> 1 -> 3 -> 5 ->|
此方法需要少一个常规指针，少一个 pointer-to-pointer，但需要一些关于如何管理两者的额外逻辑。我把它留给你作为练习。
练习是：该函数将整数列表 i 作为输入，并对其进行修改，以便所有偶数值都在奇数之前。只要所有偶数值都在奇数之前，值出现的顺序并不重要。该函数然后 returns 结果列表。该函数必须具有 O(n) 的计算复杂度和 O(1) 的内存成本。
基本上，该函数必须修改现有项目的下一个字段，而无需分配新内存。生成新列表以获得所需结果的解决方案将被视为无效。不允许更改项目的值。
这是“list.h”文件
/** @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_
这是“elemtype.h”文件：
/** @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_
这应该是解决方案，但我不知道如何继续，因为我不知道如何更改下一个字段：
#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;
}
无法编辑“list.h”文件
手头的任务是指针杂耍；那就是它。该列表充满了散布的偶数和奇数值的节点。任务是将它们连接到一个列表中，所有偶数，然后所有奇数，值，没有重新分配，没有节点覆盖（例如纯指针杂耍）。
有多种方法可以做到这一点。一个相当容易理解的是：
算法
- 设置两个列表（初始为空），一个“偶数”，一个“奇数”。
- 当您遍历原始列表修剪节点时，根据需要将它们放在“偶数”列表或“奇数”列表中。
- 完成后，link奇数列表到偶数列表的尾部；
- 最终结果没有被“偶数”列表指向，你就完成了。
演练
在（公认的可怕的）asci 艺术中，它看起来像这样。给出
的原始列表head -> 1 -> 2 -> 3 -> 4 -> 5 ->|
创建两个空列表（例如两个空指针）。
even ->|
odd ->|
从列表中取出第一个节点，保留指向它的指针p，并推进头指针。
head -> 2 -> 3 -> 4 -> 5 ->|
even ->|
odd ->|
p -> 1
现在 link p 到正确的列表。在本例中，odd 列表。
head -> 2 -> 3 -> 4 -> 5 ->|
even ->|
odd -> 1 ->|
重复该过程，直到您拥有以下内容：
head ->|
even -> 2 -> 4 ->|
odd -> 1 -> 3 -> 5 ->|
现在你只剩下 link 将 odd 列表的头部连接到 even 列表的尾部：
even -> 2 -> 4 -> 1 -> 3 -> 5 ->|
你完成了。
代码
给定一个简单的列表结构（尝试使用您的同名）：
typedef struct Item Item;
struct Item
{
int value;
Node *next;
};
实现算法的代码如下。这具有保留原始元素顺序的附加功能，即使这不是必需的：
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;
}
还有其他方法可以做到这一点，但这是很容易理解的最基本的方法。只需将节点链接到它们各自的目标列表，直到源（输入列表）用完，然后 link 一个的头部到另一个的尾部。
备选
您可以将 linked 列表视为 deque。所有偶数节点都被推（移）到队列的前面，所有奇数都被推到尾部。完成后，偶数节点将排在列表的第一位，但与它们在输入列表中的原始顺序相反。在所有偶数之后，奇数节点将处于相同的原始顺序。对于我们的示例，结果将如下所示：
4 -> 2 -> 1 -> 3 -> 5 ->|
此方法需要少一个常规指针，少一个 pointer-to-pointer，但需要一些关于如何管理两者的额外逻辑。我把它留给你作为练习。