[C] Ordinamento di una lista

[Alcott]

Ciao a tutti.
Non capisco come mai questa mia funzione non lavori bene con le liste. Spero qualcuno possa illuminarmi perchè è da 4 ore ormai che tento invano di trovare l'errore.

typedef struct node *edgeInfo; //Informazione su un arco della rete

typedef struct node {
    	int edgeCost;
    	edgeInfo nextAdj; //puntatore al prossimo elemento
} edge;

...

//funzione per ordinare in maniera crescente una lista in base ai valori contenuti in edgeCost
void ordinaLista(edgeInfo pnt)
{
	edgeInfo aux1, aux2, elemTesta, agg;
	int i=0, powMin, flag=0, control;
	
	agg = elemTesta = pnt;
	while(elemTesta->nextAdj != NULL)
	{
		aux2 = elemTesta;
		powMin = elemTesta->edgeCost;
		control = 1; //mi controlla se il primo elemento della lista è attualmente il più basso
		for(aux1=elemTesta; aux1->nextAdj != NULL; aux1=aux1->nextAdj)
		{
			if(powMin > aux1->nextAdj->edgeCost){
				aux2 = aux1;
				control = 0;
				powMin = aux1->nextAdj->edgeCost;
			}
		}
		if (flag==0){ // lo esegue solo la prima volta
			if(control==1){ //l'elemento minore E' quello all'inizio della lista
				aux2 = elemTesta->nextAdj;
				elemTesta = aux2;
				flag = 1;
			}else{ //l'elemento minore NON è quello all'inizio della lista
				aux1 = aux2->nextAdj;
				aux2->nextAdj = aux1->nextAdj;
				aux1->nextAdj = elemTesta;
				agg = aux1;
				pnt = aux1;
				flag = 1;
			}
		}else{
			if(control==1){ //l'elemento minore E' quello all'inizio della lista
				agg = elemTesta;
				aux2 = elemTesta->nextAdj;
				elemTesta = aux2;
			}else{ //l'elemento minore NON è quello all'inizio della lista
				aux1 = aux2->nextAdj;
				aux2->nextAdj = aux1->nextAdj;
				aux1->nextAdj = elemTesta; // vedi con aux2 mi sa no
				agg->nextAdj = aux1;
				agg = aux1;
			}
		}
	}
}

Ringrazio chiunque possa darmi una mano

[byaur]

innanzi tutto posta l'errore...cioè che succede...
poi come chiami la funzione, che valori gli passi??


VVoVe:

[infinitejustice]

Mamma mia l'hai scritta tu?

struct linked{
int value;
struct linked *next;
} *first = NULL;

struct linked * merge(struct linked *a, struct linked *b){

struct linked head;
struct linked *node = &head;

while((a != NULL) && (b != NULL))
if(a->value <= b->value){
node->next = a;
node = a;
a = a->next;
}
else{
node->next = b;
node = b;
b = b->next;
}
node->next = (a == NULL) ? b : a;

return head.next;
}


struct linked *mergesort(struct linked *node){

struct linked *a = node;
struct linked *b = node->next;

if(node == NULL || node->next == NULL)
return node;

while((b != NULL) && (b->next != NULL)){
node = node->next;
b = b->next;
}

b = node->next;
node->next = NULL;

return merge(mergesort(a), mergesort(b));
}

Invocata con first = mergesort(first) con first puntatore al primo elemento. Sintetica ed asintoticamente efficente. La lista è ordinata in base a value

[Alcott]

Originariamente inviato da infinitejustice
Mamma mia l'hai scritta tu?

Grazie per aver distrutto la mia autostima come programmatore
Scherzi a parte cmq, grazie per l'aiuto: funziona benissimo quella postate da te.

Se c'è qualcuno che vuol sudare e ha tempo da perdere posto come andrebbe chiamata la funzione:

ordinalista(first);

con first che è il puntatore al primo elemento.
L'errore è che a volte quando stampo la lista, questa è completa ed ordinata, in altri casi, che ancora non ho capito quali, mi stampa solamente 1 o due elementi della lista.
Di nuovo grazie a tutti

[infinitejustice]

La lista, senza le funzioni di ordinamento, funziona correttamente (operazioni di creazione di nuovi elementi, aggiunta dei nuovi elementi e rimozione) ?

Cosi intanto limiti il problema a queste funzioni.


Poi, nn so che compilatore usi, hai provato ad usare il debugger?

E magari segna anche per quali particolari input (sequenza di valori della lista) si impalla.

[Alcott]

Ciao.
La lista è creata in maniera corretta. Prima di cercare di ordinarla la stampo a video ed è corretta.

Come compilatore, uso il gcc di Linux (FC4) ed in compilazione non ho nessun errore.