Liste C: Inserimento Ordinato

[antinomau96]

Salve a tutti,

sto realizzando un complesso programma in C (ANSI).

 

Ho definito questa struttura

 

typedef struct studente {
	char *nome;
	char *cognome;
	int matricola;
	char *nesame; /* nome esame */
	int vesame; /* voto esame */
	struct studente *link;
} Studente;

/* puntatore al primo componente della lista */
Studente *nextlist = NULL;

che mi serve per creare una lista concatenata (linked list)!

Il problema è che non riesco a realizzare una funzione per l'inserimento ordinato in base al cognome!

 

Per adesso ho scritto questa funzione:

 

void inserisciordinatocg (char* cg, char* nm, int matr, char* nexam, int vexam) {

	Studente *cur = nextlist;
	Studente *prec = NULL;
	Studente *ptr = (Studente*)malloc(sizeof(Studente));

	ptr->cognome = (char*)malloc(sizeof(char)*(strlen(cg)+1));
	strcpy(ptr->cognome, cg);
	cur->nome = (char*)malloc(sizeof(char)*(strlen(nm)+1));
	strcpy(cur->nome, nm);
	cur->matricola=matr;
	cur->nesame = (char*)malloc(sizeof(char)*(strlen(nexam)+1));
	strcpy(cur->nesame, nexam);
	cur->vesame = vexam;

	ptr->link = nextlist;


	/* se cur non esiste oppure il valore da inserire e' minore di quello corrente si effettua un inserimento in testa alla lista */
	if (!cur || (strcmp(cur->cognome, cg))>0) {
		ptr->link=nextlist;
		nextlist=ptr;
	} /* end of if */
	else {
		while (cur && (strcmp(cg, cur->cognome))>=0) {
			prec=cur;
			cur=cur->link;
		} /* end of while */
		prec->link=ptr;
		ptr->link=cur;
	} /* end of else */

prec->link = ptr;
	ptr->link = cur;


} /* end inserisciordinatocg */

come illustratoci dal prof!

Sul web e sui libri la funzione più riportata è quella con la ricorsione ma io vorrei semplicemente realizzare una funzione in questo modo come illustratoci dallo stesso prof perché mi risulta più semplice.

 

Qualcuno potrebbe illuminarmi sugli errori che compio e/o potrebbe aiutarmi a realizzare una funzione migliore e/o più semplice?

 

 

Grazie in anticipo a quanti mi risponderanno!

 

[antinomau96]

Ho sistemato la funzione ma quando provo ad inserire un elemento in moodo ordinato nella lista vuota mi restituisce un errore di segmentazione... suggerimenti?

Ecco la nuova funzione

void insord(char* cg, char* nm, int matr, char* nexam, int vexam) {
		
	Studente *prec = NULL;
	Studente *cur = nextlist;
	Studente *ptr = (Studente*)malloc(sizeof(Studente));

	ptr->link = NULL;
	
	ptr->cognome = (char*)malloc(sizeof(char)*(strlen(cg)+1));
	strcpy(ptr->cognome, cg);
	ptr->nome = (char*)malloc(sizeof(char)*(strlen(nm)+1));
	strcpy(ptr->nome, nm);
	ptr->matricola=matr;
	ptr->nesame = (char*)malloc(sizeof(char)*(strlen(nexam)+1));
	strcpy(ptr->nesame, nexam);
	ptr->vesame=vexam;

#ifdef debug
printf("\nDEBUG - InsO - com %s %s = %d", cg, cur->cognome, strcmp(cg, cur->cognome));
#endif
	while (cur && (strcmp(cg, cur->cognome)>0)) {
		/* passaggio al nodo successivo */
		prec = cur;
		cur = cur->link;
	} /* end of while */

	/* inserire un nuovo nodo all'inizio della lista */
	if (!prec) {
		ptr->link = nextlist;
		nextlist = ptr;
	} /* end of if */
	else {
		prec->link = ptr;
		ptr->link = cur;
	} /* end of else */

} /* end insord */

[Lief]

inizio a scriverti questo messaggio per dirti che avendo trovato qualche oretta ci sto lavorando.

però, per la prossima volta, evita di omettere parti di codice... non togliere gli include e non togliere il main... sono tutte parti che chi ti aiuta deve ricostruire per iniziare a testare il tuo codice (ed è una perdita di tempo).

 

Detto questo ti dico subito che i problemi iniziano in questa parte di codice:

cur->cognome, strcmp(cg, cur->cognome)

(nel printf del debug)

infatti cerchi di accedere a cur->cognome che è una zona di memoria che non hai riempito ma che in particolare non hai inizializzato (manca un malloc).

 

Detto questo ora cerco di fare un codice funzionante (e spero anche attinente a quel che vuoi fare, ma senza avere il main di esempio non posso essere certo che sia quel che vuoi fare davvero).

 

EDIT1. Ok nel codice c'è qualcosa che non quadra assolutamente. cerchi di comparare due stringhe ma in cur non c'è nulla quindi da ovviamente segmentation fault.

A questo punto mi sa che faccio prima a creare un codice per le liste da zero.

 

EDIT2. Era un po' che non toccavo le liste e ci è voluto un po' di tempo... l'unica cosa che ti posso dire è che ho dovuto cambiare parecchia roba (e il fatto che tu non volessi usare la ricorsione complica di parecchio le cose, il mio consiglio è di dare un'occhiata alla versione ricorsiva perchè a differenza di quel che dici è molto, molto, molto più semplice da creare "perché mi risulta più semplice" è una frase che se ti fossi esercitato sulla ricorsione non penseresti neanche)...

comunque ora il codice è corretto (e ho commentato tutto in modo che sia molto semplice da capire), conta che non credo che avrò altro tempo nei prossimi giorni quindi se qualcosa non va non potrò aiutarti:

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

typedef struct studente {
	char *nome;
	char *cognome;
	int matricola;
	char *nesame; /* nome esame */
	int vesame; /* voto esame */
	struct studente *link;
} Studente;

Studente* insord(Studente *root, char* cg, char* nm, int matr, char* nexam, int vexam) {
	//creazione Studente in base ai dati passati da parametro - allocazione memoria
	Studente *ptr = (Studente*)malloc(sizeof(Studente));

	//variabili temporanee
	Studente *temp = NULL;
	Studente *prec = NULL;

	//creazione Studente in base ai dati passati da parametro - singoli parametri
	ptr->cognome = (char*)malloc(sizeof(char)*(strlen(cg)+1));
	strcpy(ptr->cognome, cg);
	ptr->nome = (char*)malloc(sizeof(char)*(strlen(nm)+1));
	strcpy(ptr->nome, nm);
	ptr->matricola=matr;
	ptr->nesame = (char*)malloc(sizeof(char)*(strlen(nexam)+1));
	strcpy(ptr->nesame, nexam);
	ptr->vesame=vexam;
	ptr->link = NULL;

	//se la root è vuota ptr diventa la mia root
	if (root->cognome == NULL) {
		root->cognome = (char*)malloc(sizeof(char)*(strlen(cg)+1));
		strcpy(root->cognome, ptr->cognome);
		root->nome = (char*)malloc(sizeof(char)*(strlen(nm)+1));
		strcpy(root->nome, ptr->nome);
		root->matricola=ptr->matricola;
		root->nesame = (char*)malloc(sizeof(char)*(strlen(nexam)+1));
		strcpy(root->nesame, ptr->nesame);
		root->vesame=ptr->vesame;
		root->link = NULL;
		//appena inserito l'elemento ordinato concludo la funzione e ritorno la nuova root
		return root;
	//se la root è piena ma l'elemento successivo è Null
	}else if(root->link == NULL){
		// se ptr viene prima della root che ho già - sostituisco la root con ptr, setto l'elemento successivo alla root precedente
		if (strcmp(root->cognome, ptr->cognome)>0) {
			temp = root;
			root = ptr;
			root->link = temp;
		//se la root attuale viene prima di ptr - setto l'elemento successivo della root a ptr
		}else{
			root->link = ptr;
		}
		//appena inserito l'elemento ordinato concludo la funzione e ritorno la nuova root
		return root;
	}else {
	//se i primi 2 elementi sono pieni
		prec = root;
		temp = root->link;
		//controllo il primo elemento - se ptr viene prima della root attuale, scambio e inserisco
		if (strcmp(root->cognome, ptr->cognome)>0) {
			temp = root;
			root = ptr;
			root->link = temp;
			//appena inserito l'elemento ordinato concludo la funzione e ritorno la nuova root
			return root;
		}
		//se questo non succede controllo se l'elemento successivo del successivo è null.
		while (temp->link != NULL) {
			//se non lo è - controllo se l'elemento successivo viene prima o dopo ptr - se viene prima scambio
			if (strcmp(temp->cognome, ptr->cognome)>0) {
				ptr->link = temp;
				prec->link = ptr;
				//appena inserito l'elemento ordinato concludo la funzione e ritorno la nuova root
				return root;
			}
			//in caso contrario scorro la lista
			prec = temp;
			temp = temp->link;
		}
		//se l'elemento successivo del successivo è null allora siamo a fine lista - controllo se l'elemento successivo viene prima o dopo ptr - se viene prima scambio
		if (strcmp(temp->cognome, ptr->cognome)>0) {
			ptr->link = temp;
			prec->link = ptr;
		//se viene dopo accodo
		}else{
			temp->link = ptr;
		}
		//appena inserito l'elemento ordinato concludo la funzione e ritorno la nuova root
		return root;
	}

}

int main() {
	//creo la root vuota
	Studente *root = (Studente*)malloc(sizeof(Studente));
	Studente *temp = NULL;
	root->cognome = NULL;

	//creo una serie di parametri che possono costruire una struct di tipo Studente
	char cg[10] = "Rubino";
	char nm[10] = "nome";
	int matr = 10;
	char nexam[10] = "matematica";
	int vexam = 18;
	//richiamo la funzione per inserire il nuovo elemento nella root e assegno la root alla nuova root
	root = insord(root, cg, nm, matr, nexam, vexam);
	//stampo tutti gli elementi
	temp = root;
	while (temp != NULL) {
		printf("%s", temp->cognome);
		temp = temp->link;
	}
	temp = root;
	printf("\n");

	//creo una serie di parametri che possono costruire una struct di tipo Studente
	char cg2[10] = "Bianchi";
	char nm2[10] = "nome";
	int matr2 = 10;
	char nexam2[10] = "matematica";
	int vexam2 = 18;
	//richiamo la funzione per inserire il nuovo elemento nella root e assegno la root alla nuova root
	root = insord(root, cg2, nm2, matr2, nexam2, vexam2);
	//stampo tutti gli elementi
	temp = root;
	while (temp != NULL) {
		printf("%s ", temp->cognome);
		temp = temp->link;
	}
	temp = root;
	printf("\n");

	//creo una serie di parametri che possono costruire una struct di tipo Studente
	char cg3[10] = "Rossi";
	char nm3[10] = "nome";
	int matr3 = 10;
	char nexam3[10] = "matematica";
	int vexam3 = 18;
	//richiamo la funzione per inserire il nuovo elemento nella root e assegno la root alla nuova root
	root = insord(root, cg3, nm3, matr3, nexam3, vexam3);
	//stampo tutti gli elementi
	temp = root;
	while (temp != NULL) {
		printf("%s ", temp->cognome);
		temp = temp->link;
	}
	temp = root;
	printf("\n");

	//creo una serie di parametri che possono costruire una struct di tipo Studente
	char cg4[10] = "Verdi";
	char nm4[10] = "nome";
	int matr4 = 10;
	char nexam4[10] = "matematica";
	int vexam4 = 18;
	//richiamo la funzione per inserire il nuovo elemento nella root e assegno la root alla nuova root
	root = insord(root, cg4, nm4, matr4, nexam4, vexam4);
	//stampo tutti gli elementi
	temp = root;
	while (temp != NULL) {
		printf("%s ", temp->cognome);
		temp = temp->link;
	}
	temp = root;
	printf("\n");

	printf("FINE\n");
	return 0;
}

ti faccio vedere anche un esempio di inserimento ordinato in versione ricorsiva che ho trovato online (non è relativo al tuo esercizio ma ti da un'idea di quanto sia più semplice) (per mia semplicità l'esempio è in Java, che comunque è un linguaggio C-like quindi dovrebbe essere semplice da capire):

public LN insertOrdered (LN l, int value)
  {
    if (l == null || value < l.value)
      return new LN(value,l);
    else
      l.next = insertOrdered(l.next, value);

    return l;
  }

in pratica se:

BASE:

lista è vuota

oppure

valore passato è inferiore al valore contenuto nella lista

creo un nuovo nodo con il valore passato come parametro

 

in caso contrario:

PASSO INDUTTIVO:

prendi il next della lista passata come parametro e lo passi insieme al valore all funzione ricorsiva

 

ritorna la lista al chiamante.

 

In pratica arriverai sempre al caso BASE (quello dove crei il nodo della lista).

 

Chiaramente questo esempio dovrebbe essere adattato al tuo esercizio dove al posto di creare un nuovo nodo lo inserisci... ma tutto questo era per farti capire perchè la ricorsione è infinitamente più conveniente, devi infatti preoccuparti solo del caso base... trovato quello il passo induttivo (nel caso delle liste) non fa altro che richiamare la funzione sull'elemento successivo