[C] Dubbi su inserimento ordinato in nuova lista

[desterix95]

Buongiorno, ho dei dubbi sulla funzione $text(void ord_insert)$ per l'inserimento ordinato di elementi in una nuova lista.
Questo è il codice nel quale ho inserito una lista, la funzione $text(void ord_insert)$ e la funzione $text(Funzione)$ che, data una lista iniziale, ne crea una nuova ordinata:

struct list {
	int value;
	struct list *next_ptr;
};
void ord_insert(struct list **ptrptr, int x) { //x valore da inserire
	while ((*ptrptr) != NULL && (*ptrptr)->value < x) {  
		ptrptr = &((*ptrptr)->next_ptr); 
}
	pre_insert(ptrptr,x);
};
void Funzione(struct list *ptr, struct list **ptrptr) {
	init(ptrptr);                                                      
	while (ptr != NULL) {
		ord_insert(ptrptr,ptr->value);
		ptr = ptr->next_ptr;
	}

}

Domande:
1) Intanto, la lista che ho scritto è una lista di valori interi in forma collegata con puntatori?
2) Come funziona il while di $text(void ord_insert)$? Se $text((*ptrptr))$ non è nullo e il primo valore della nuova lista è < di $v$, allora passo al successivo elemento della lista, se $text((*ptrptr))$ non trova nulla e il primo valore della nuova lista è > di $v$, allora non si esegue il while e $v$ lo inserisco in testa della lista? Ma non ho una limitazione solo nell'inserimento in testa? Voglio dire, io potrei avere una lista che per i primi due elementi è ordinata, poi no, qual è la condizione che mi rende la lista tutta ordinata?
3)Sempre in $text(void ord_insert), come mai viene scritto $text((*ptrptr)->value)$ cioè perchè con il $text(*)$? $text((*ptrptr))$ è un puntatore che punta a un altro puntatore, ma $text(value)$ non è una variabile di tipo $text(int)$? Quindi non andrebbe scritto $text((ptrptr)->value)$?
4) In $text(Funzione)$, a che serve $text(init(ptrptr))$? Che significa inizializzare una lista? Significa in pratica crearla?
Grazie

[Super Squirrel]

Il fatto che sia passato molto tempo da quando ho affrontato questi argomenti influisce sicuramente, ma non mi sembra comunque che il codice e le richieste siano molto chiari.
Prima di concentrarsi sull'inserimento ordinato, sai cos'è una lista e come funziona? Poi potresti spiegare meglio cosa vorresti fare? Tipo creare una lista di tot interi, ordinarla e poi effettuare inserimenti ordinati?

[desterix95]

No, data una lista di valori interi, creare una nuova lista con elementi ordinati. Gli elementi della nuova lista sono quelli della lista iniziale, ma ordinati

[Super Squirrel]

Nel codice da te postato quella che tu hai chiamato list non è una lista, ma un nodo (ossia il singolo elemento della lista). Bisogna quindi creare una struct/class per la lista che abbia come membro un puntatore che punterà alla testa o alla coda della lista ed eventuali metodi (per aggiungere nuovi elementi, per mostrare la lista...).
Fatto questo basta creare una nuova lista uguale a quella iniziale e poi ordinarne gli elementi con un qualsiasi algoritmo di ordinamento. Oppure visto che l'ordinamento di una lista risulta abbastanza artificioso e poco conveniente, potresti copiare gli elementi della lista iniziale in un array, ordinarlo e poi passare gli elementi nella nuova lista.

In ogni caso fammi sapere tu come avresti intenzione di procedere e dove sorgono i problemi.

[apatriarca]

"Super Squirrel":Nel codice da te postato quella che tu hai chiamato list non è una lista, ma un nodo (ossia il singolo elemento della lista). Bisogna quindi creare una struct/class per la lista che abbia come membro un puntatore che punterà alla testa o alla coda della lista ed eventuali metodi (per aggiungere nuovi elementi, per mostrare la lista...).

Una lista è un concetto astratto, definito semplicemente dal tipo di operazioni che la struttura dati deve soddisfare. Anche se in molti casi si preferisce nascondere l'implementazione dietro ad una classe (probabilmente perché questa classe implementerà una qualche interfaccia), non c'è alcuna ragione per cui non si possa lavorare direttamente con i nodi. In effetti questo tipo di implementazione è molto comune nei corsi universitari e in generale in linguaggi come il C. Ci sono in effetti vantaggi/svantaggi in entrambi i metodi.

"Super Squirrel":Fatto questo basta creare una nuova lista uguale a quella iniziale e poi ordinarne gli elementi con un qualsiasi algoritmo di ordinamento. Oppure visto che l'ordinamento di una lista risulta abbastanza artificioso e poco conveniente, potresti copiare gli elementi della lista iniziale in un array, ordinarlo e poi passare gli elementi nella nuova lista.

In ogni caso fammi sapere tu come avresti intenzione di procedere e dove sorgono i problemi.

Ordinare una lista non è necessariamente artificioso o poco conveniente. È infatti sufficiente fare ricorso ad algoritmi un po' diversi. L'odd-even merge sort è particolarmente efficace. Richiede l'implementazione di due funzioni di appoggio: una che divide l'array in due liste e un'altra per fare il merging. Un altro algoritmo molto semplice è ad esempio il bubble-sort.