[C] Inserire elementi ordinati in lista linkata

[allalala]

come faccio a fare una cosa del genere??ossia come faccio ad inserirla già in maniera ordinata??(non si tratta i numeri ma caratteri)

[Laikius91]

Ti passo il codice provato e funzionante!

list insord (char el, list l) 
{
	
	if (empty(l)) return cons (el, l);
  	else if (el <= head (l) ) return cons(el, l);
	else return cons (head(l), insord (el, tail(l)));
	
}

In questo codice sono utilizzate:

list cons (element el, l); che ritorna una lista con in testa l'elemento el;

element head (l); che ritorna il primo elemento della lista l;

Spero sia tutto chiaro, ovviamente questa è la versione ricorsiva del codice!

[allalala]

senza usare la ricorsione come potrei fare??

[Celebron]

di base se la lista si considera ordinata ad ogni passo, è sufficiente che controlli ogni volta il nodo successivo

se è maggiore, inserisci subito, se è minore, passi al nodo successivo (si tratterebbe quindi di un while con controlli)
non dovrebbero esserci casi particolare da trattare tranne l'ultimo. Ovvero se il nodo successivo è NULL e ancora non hai inserito, inserisci in coda.

[allalala]

me lo potresti illistrare proprio dal punto di vista del codice??perchè in grosso modo ho provato anch'io così ma quando vado ad eseguire mi si blocca il programma...

[Laikius91]

Proprio perchè sono buono, eccoti la versione iterativa!
Attenzione che in questa non sono usate le primitive delle liste, ma i puntatori ad esse!

list insord (char c, list l)
{
	int set = 0;
	
	list temp, old, act = l;
	
	while (act != NULL && !set)
	{				
		if (c < act->value) 
				set = 1;
	
		else
		{
			old = act;
			act = act->next;		
		}
	}
		
	temp = (list) malloc (sizeof (item));
	temp->value = c;
	temp->next = act;
		
	if (act == l) return temp;
	else 
	{
		old->next = temp;
		return l;
	}

}

Spero vada bene!

[toni00c]

Originariamente inviato da Laikius91
Proprio perchè sono buono, eccoti la versione iterativa!
Attenzione che in questa non sono usate le primitive delle liste, ma i puntatori ad esse!
=========================
Spero vada bene!

piccola domanda inerente a questo interessante topic ;
che cosa sarebbe in pratica la primitiva di una lista ?

purtroppo nel mio fedele libro di C deitel non ne trovo traccia !

[Laikius91]

Originariamente inviato da toni00c
piccola domanda inerente a questo interessante topic ;
che cosa sarebbe in pratica la primitiva di una lista ?

purtroppo nel mio fedele libro di C deitel non ne trovo traccia !

In C, il tipo "lista" non esiste di per sè... occorre definirlo come ADT (abstract data type).
Senza entrare troppo nel dettaglio, ogni ADT è definito in base a:

1) Dominio dei valori che può assumere;
2) Funzioni primitive, come, nel caso delle liste, creare una nuova lista, aggiungere alla lista un nuovo elemento, ottenere il primo elemento della lista, ottenere la lista privata del primo elemento... da queste primitive si possono ottenere altre funzioni assai utili per l'ADT;
3) Predicati che ritornano valori di tipo booleano rispondendo a determinati "quesiti", quale, nel caso delle liste, se la lista sia vuota.

L'implementazione non è immediata e non può essere tutta esplicitata qui, ma spero comunque di essere stato chiaro!

[toni00c]

Originariamente inviato da Laikius91
In C, il tipo "lista" non esiste di per sè... occorre definirlo come ADT (abstract data type).
Senza entrare troppo nel dettaglio, ogni ADT è definito in base a:

1) Dominio dei valori che può assumere;
2) Funzioni primitive, come, nel caso delle liste, creare una nuova lista, aggiungere alla lista un nuovo elemento, ottenere il primo elemento della lista, ottenere la lista privata del primo elemento... da queste primitive si possono ottenere altre funzioni assai utili per l'ADT;
3) Predicati che ritornano valori di tipo booleano rispondendo a determinati "quesiti", quale, nel caso delle liste, se la lista sia vuota.

L'implementazione non è immediata e non può essere tutta esplicitata qui, ma spero comunque di essere stato chiaro!

ciao adesso comincio a capire meglio il concetto
in poche parole occorre definire un ADT usando typedef e successivamente le primitive ( che dovrebbero corrispondere alle funzioni di quell ADT ) (?) , separando l'implementazione dall interfaccia , dico bene ?

è un argomento alquanto delicato


definendo una lista con ADT , quali vantaggi ottengo rispetto al creare una normale lista concatenata ad esempio ?
questo è quello che più vorrei capire
stiamo parlando di estendibilità o sbaglio?

[Laikius91]

Dunque dunque, la faccenda è un po' complicata.. come dici tu, lo scopo di creare e definire un ADT è quello di permetterne poi l'utilizzo a prescindere dall'implementazione concreta.

Mettiamo che tu voglia utilizzare le liste di elementi generici: per prima cosa occorre definire il tipo lista utilizzando l'implementazione che preferisci (non esiste solo quella collegata tramite puntatori, anche se è la più efficiente). Quindi, con un paio di typedef, arrivi ad ottenere il tipo list.
Ora puoi definire alcune funzioni, vedi quelle che ho elencato sopra, che possono essere più o meno intuitive e complicate: lo scopo di definirle qui è quello che dopo potrai utilizzare senza andare a complicarti la vita pensando come sono state definite!

Esempio pratico: nel mio modulo list.h/list.c mi creo il mio ADT list e definisco, tra le varie funzioni, la funzione list cons (element el, list l);, che mi ritorna la lista l con l'elemento el in testa, che non è proprio immediata, perchè richiede l'utilizzo della malloc, delle strutture e dei puntatori ad esse.. Dopodichè, ogni volta che dovrai aggiungere un elemento alla tua lista, invocherai la cons, senza preoccuparti di come sia stata realizzata!

Mica male no?