PDA

Visualizza la versione completa : [C] Ordinamento lista dinamica secondo una chiave


walzer91
12-12-2011, 21:40
Ciao a tutti, questo è il mio primo post su questo forum e volevo intanto farvi i complimenti perchè è grazie a voi che ho risolto molti problemi riguardo la programmazione :) Ci tengo a sottolineare che ho usato la funzione cerca ma purtroppo non trovo una soluzione adeguata al mio caso. Volevo chiedere aiuto a voi che certamente siete più competenti di me. Sto studiando il linguaggio c per l'università e mi sono imbattuto in un problema che non riesco a risolvere. Ho una lista dinamica di dati, in particolare di informazioni su una persona, e dovrei ordinare questa lista in ordine dal più giovane al più anziano, vi posto il codice:



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

#define MAXN 15


typedef struct Person
{
char name[MAXN];
int age;
double weight;
struct Person *next;
} Person;

Person *createlist(Person *list);
void fillperson(Person *list);
void printlist(Person *list);
Person *bubblesort(Person *list);

int main()
{
Person *people;
char s;

people = (Person *) malloc(sizeof(Person));
people=NULL;
people=createlist(people);
printf("Inserire nuova voce? (s/n) ");
s=getchar();

while((s = getchar()) =='s')
{
getchar();
putchar('\n');
putchar('\n');
people=createlist(people);
putchar('\n');
printf("Inserire nuova voce? (s/n) ");
s=getchar();
}


printlist(people);
printlist(people);
free(people);
return 0;
}

Person *createlist(Person *list)
{
Person *nuovo;
Person *p;

nuovo = (Person *) malloc(sizeof(Person));
fillperson(nuovo);

if(list==NULL)
list=nuovo;
else
{
p=list;
while(p->next)
p=p->next;
p->next = (Person *) malloc (sizeof(Person));
p->next = nuovo;
}

return list;
}

void fillperson(Person *list)
{
printf("Inserire il nome della persona: ");
gets(list->name);
printf("Inserire l'eta' della persona: ");
scanf("%d",&(list->age));
printf("Inserire l'altezza della persona: ");
scanf("%lf",&(list->weight));
list->next=NULL;
}

void printlist(Person *list)
{
printf("\n\nInizio lista ---> \n\n");

while(list)
{
printf("Nome: %s\n",list->name);
printf("Eta': %d\n",list->age);
printf("Altezza: %.2lf\n\n\n",list->weight);
list=list->next;
}

printf("---> Fine lista\n\n");
}



So che probabilmente è di facile risoluzione ma io non riesco a capire come implementare il codice... Il mio professore di programmazione all'università, con tutto rispetto parlando, è un asino, quindi è escluso chiedere a lui -.- Pensate che addirittura pretende che si ordiniamo tutto con il bubblesort perchè è l'unico algoritmo di ordinamento che capisce e sa insegnare -.- infatti io purtroppo so usare solo quello... Comunque, se qualcuno saprebbe spiegarmi come fare la funzione per ordinare la lista sarebbe veramente una cosa gradita! Ancora meglio se potesse postare una funzione da lui fatta così da capire meglio... Se è possibile preferirei che se fosse necessario un algoritmo di ordinamento usaste il bubblesort, dato che l'esame lo devo fare con quel prof preferisco farlo come vuole lui e poi studiarmi le cose in futuro con calma... Vi ringrazio in anticipo, se servono altre informazioni chiedete pure!! :ciauz:

oregon
12-12-2011, 23:08
Non ho capito una cosa ... ma il bubble sort tu lo sai usare? Sai almeno scrivere un esempio di "scheletro" di funzione per l'ordinamento con il bubble sort?

walzer91
13-12-2011, 00:30
Ciao! Si, l'algoritmo del bubblesort è semplice, lo conosco e so usarlo, anche se sono ben consapevole della sua inefficienza devo continuare a usarlo perchè il prof è "particolare" per non dire di peggio...

oregon
13-12-2011, 10:08
Originariamente inviato da walzer91
Ciao! Si, l'algoritmo del bubblesort è semplice, lo conosco e so usarlo, anche se sono ben consapevole della sua inefficienza devo continuare a usarlo perchè il prof è "particolare" per non dire di peggio...

Ok ... scrivi un esempio di codice per il bubble sort e si vede di adattarlo alla tua lista...

O anche, guarda questo esempio

http://www.c.happycodings.com/Sorting_Searching/code5.html

walzer91
13-12-2011, 19:51
Ti ringrazio per la risposta celere e per l'utilissimo link!! Mi sa che hai trovato la soluzione al mio problema :) Posso disturbarti ancora un po'? Ho usato il bubblesort riadattato per la mia lista ma noto che mi elimina tutti gli elementi della lista tranne 2 :(

posto il codice così puoi vedere cosa ho combinato:




/* Il programma consente di inserire un numero di informazioni relative ad alcune persone, il cui numero è definito dall'utente a run-time, salvarle in una lista dinamica e stamparle in ordine crescente secondo il campo "age" di ogni persona */

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

#define MAXN 15


typedef struct Person /* Definizione delle lista "Person" */
{
char name[MAXN];
int age;
double weight;
struct Person *next;
} Person;


// Prototipi di funzioni usate nel programma

Person *createlist(Person *list);
void fillperson(Person *list);
void printlist(Person *list);
void bubblesort(Person *list);

/* Nel main è inserito il primo nodo della lista "people" e successivamente si inseriscono gli altri tramite funzione */

int main()
{
Person *people;
char s;

people = (Person *) malloc(sizeof(Person));
people=NULL;
people=createlist(people);
printf("Inserire nuova voce? (s/n) ");
s=getchar();

while((s = getchar()) =='s')
{
getchar();
putchar('\n');
putchar('\n');
people=createlist(people);
putchar('\n');
printf("Inserire nuova voce? (s/n) ");
s=getchar();
}


printlist(people);
bubblesort(people);
printlist(people);
free(people);
return 0;
}

// Funzione che aggiunge un nuovo nodo alla lista già esistente

Person *createlist(Person *list)
{
Person *nuovo;
Person *p;

nuovo = (Person *) malloc(sizeof(Person));
fillperson(nuovo);

if(list==NULL)
list=nuovo;
else
{
p=list;
while(p->next)
p=p->next;
p->next = (Person *) malloc (sizeof(Person));
p->next = nuovo;
}

return list;
}

// Funzione che acquisisce in imput i dati di ogni nodo

void fillperson(Person *list)
{
printf("Inserire il nome della persona: ");
gets(list->name);
printf("Inserire l'eta' della persona: ");
scanf("%d",&(list->age));
printf("Inserire l'altezza della persona: ");
scanf("%lf",&(list->weight));
list->next=NULL;
}

// Funzione per stampare l'intera lista

void printlist(Person *list)
{
printf("\n\nInizio lista ---> \n\n");

while(list)
{
printf("Nome: %s\n",list->name);
printf("Eta': %d\n",list->age);
printf("Altezza: %.2lf\n\n\n",list->weight);
list=list->next;
}

printf("---> Fine lista\n\n");
}

// Algoritmo di ordinamento

void bubblesort(Person *list)
{
Person *a = NULL;
Person *b = NULL;
Person *c = NULL;
Person *e = NULL;
Person *tmp = NULL;

while(e != list->next)
{
c = a = list;
b = a->next;

while(a!=e)
{
if(a->age > b->age)
{
if(a==list)
{
tmp = b->next;
b->next = a;
a->next = tmp;
list = b;
c = b;
}

else
{
tmp = b->next;
b->next = a;
a->next = tmp;
c->next = b;
c = b;
}
}

else
{
c = a;
a = a->next;
}

b = a->next;

if(b == e)
e = a;
}
}
}


Naturalmente sarà pieno di errori che un programmatore esperto non si sognerebbe di commettere però pensa che solo all'inizio XD Ti ringrazio nuovamente per la pazienza dimostrata e per la disponibilità :)

MacApp
13-12-2011, 23:41
Originariamente inviato da walzer91
Ciao! Si, l'algoritmo del bubblesort è semplice, lo conosco e so usarlo, anche se sono ben consapevole della sua inefficienza devo continuare a usarlo perchè il prof è "particolare" per non dire di peggio...

Non esiste in genere un miglior algoritmo di ordinamento rispetto ad un altro.



$ man qsort

Normally, qsort() is faster than mergesort(), which is faster than heapsort().
Memory availability and pre-existing order in the data can make this untrue.


Ci sono situazioni reali in cui il bubblesort è migliore (più conveninente) di qualunque altro algoritmo (ad esempio insieme già ordinato e poca memoria disponibile).

vedi anche:


http://en.wikipedia.org/wiki/Bubble_sort

In computer graphics it is popular for its capability to detect a very small error (like swap of just two elements) in almost-sorted arrays and fix it with just linear complexity (2n). For example, it is used in a polygon filling algorithm, where bounding lines are sorted by their x coordinate at a specific scan line (a line parallel to x axis) and with incrementing y their order changes (two elements are swapped) only at intersections of two lines.

Loading