[C] - Ordinare una lista

[Napoli82]

Ciao a tutti,

qualcuno saprebbe dirmi come implementare in C i "classici" algoritmi di ordinamento come "QuickSort" o "MergeSort" o "InsertionSort" o altri ancora tenendo presente che essi debbono ordinare una lista lineare e non i soliti array?

Per intenderci ogni nodo della lista può avere una struttura del tipo:

 struct nodoLista {
  char *info;
  struct nodoLista *next;
 };

ed il risultato deve essere una lista i cui nodi siano nell'ordine alfabetico rispetto al campo info.

Ciao e grazie x l'aiuto.

[infinitejustice]

struct linked * merge(struct linked *, struct linked *);
struct linked *mergesort(struct linked *);

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));
}

Questo lo feci a suo tempo per interi... quindi basta che modifichi l'istruzione di confronto da int a stringa



p.s. notare avatar per san valentino

[Napoli82]

Scusami ma...

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

...non lo capisco. Ed in effetti anche il compilatore mi da un warning: head non è inizializzato, cosa contiene?

[infinitejustice]

la struct si kiama linked nel mio caso.
Head è una variabile di tipo struct linked e *node la punta

Come sai il Mergesort ha bisogno di un aiutino ausiliario (spazio) per fare il merging

Se lavori su un array l'aiutino è un array... se è una lista allora è una lista

[infinitejustice]

Guarda questo se vuoi vedere è tutto il codice

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

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


void add(int);
void show(void);
struct linked * merge(struct linked *, struct linked *);
struct linked *mergesort(struct linked *);


void main(){

	add(25);
	show();
	first = mergesort(first);
	show();
}


void add(int nr){

	srand(time(NULL));

	while(nr--){
		if(!(new = (struct linked *)malloc(sizeof(struct linked))))
			abort();
		(*(new)).value = rand()%100;
		(*(new)).next = NULL;
		(*(new)).next = first;
		first = new;
		}
}


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));
}

void show(){

	struct linked *temp;
	for(temp = first; temp->next != NULL; temp = temp->next)
		printf("%d ", temp->value);
	printf("\n");
}