Inserimento in una linked list ordinata

di il
2 risposte

Inserimento in una linked list ordinata

Ciao a tutti! Il professore ci ha chiesto di implementare una funzione per l'inserimento di un elemento in una linked list ordinata.
Non mi piace andare andare in giro a cercare funzioni già pronte e fare il classico copia/incolla perchè credo che non serva a nulla (anzi direi che è controproducente), per cui mi sono armato di un pò di pazienza ed ho implementato una funzione per l'inserimento. Fortunatamente funziona tutto a dovere però mi piacerebbe molta avere qualche parere/consiglio/correzione relativamente al mio algoritmo. Ecco il codice:

#include<iostream>
using namespace std;
// definisco la struttura del nodo
typedef struct nodo{
	int info;
	nodo *next;
};

void insert(int x,nodo *&head);

int main(){
	int x;
	nodo *head=NULL;
	//questo ciclo l'ho messo per creare una lista in modo da poter verificare il funzionamento o meno
for(int i=0;i<5;i++){
	cout<<"Inserisci valore: ";
	cin>>x;
	insert(x,head);
}      
	//stampo la lista per controllare se i valori sono stati inseriti correttamente
	while(head!=0){
		cout<<head->info<<endl;
		head=head->next;
	}
	return 0;
}

void insert(int x,nodo *&head){
       //inserito diventa 1 quando il nuovo nodo è stato inserito nella lista
	int inserito=0;
	//creo un nuovo nodo ed assegno al campo info il valore x inserito dall'utente
	nodo *nuovo;
	nuovo=new nodo;
	nuovo->info=x;
	//utilizzo current per muovermi nella lista lasciando invariata la head
	nodo *current;
	current=head;
	//se la lista e vuota oppure se il campo info del primo nodo è maggiore di x, inserisco il nuovo nodo come primo della lista
	if(head==NULL||head->info>x){
		nuovo->next=head;
		head=nuovo;
		inserito=1;
	}else{
		//fin quando il nuovo nodo non è stato inserito nella lista
		while(inserito==0){
			//se il puntatore al prox elemento è NULL, e quindi siamo arrivati all'ultimo nodo, metto il nuovo nodo
			//come ultimo della lista
			if(current->next==NULL){
				nuovo->next=current->next;
				current->next=nuovo;
				inserito=1;
			}else{
				//se il campo info del prossimo nodo è maggiore di x, inserisco il nuovo nodo tra il nodo corrente ed il successivo
				if(current->next->info>x){
					nuovo->next=current->next;
					current->next=nuovo;
					inserito=1;	
				}else{
					//altrimenti assegno a current l'indirizzo del prossimo nodo e ripeto il ciclo fino all'inserimento del nuovo elemento
					current=current->next;
				}
			}
		}
	}
}
Ho commentato nei punti dove magari può risultare poco chiaro...spero si capisca!!!
Grazie a tutti in anticipo

2 Risposte

  • Re: Inserimento in una linked list ordinata

    Riguardandolo ho fatto una piccola modifica...
    Ho inserito if(current->next==NULL) e if(current->next->info>x) in un'unica condizione, cioè:
    if(current->next==NULL||current->next->info>x)
  • Re: Inserimento in una linked list ordinata

    Ci sono alcune considerazioni filosofico/stilistiche che si possono fare

    1) la LISTA invece di un PUNTATORE AD UN NODO potrebbe essere un OGGETTO CHE CONTIENE UN PUNTATORE AL PRIMO NODO
    2) fai una scansione abbastanza impasticciata. Il metodo classico di scansione di una lista semplice (cioe' in cui ogni nodo ha SOLO il puntatore all'elemento siccessivo) e' quello di usare DUE puntatori: uno al NODO PRECEDENTE (P) ed uno al NODO CORRENTE (C)
    3) cercare il PRIMO nodo C per cui x <= C->info

    A questo punto puoi prendere in considerazioni i casi

    P==null, C==null
    P==null, C != null
    P !=null, C !=null
    P !=null, C==null

    Molto pulito, molto lineare, e ben separata la parte di SCANSIONE della lista dalla parte di MODIFICA

    Nota: invece del flag inserito usato per bloccare il loop, puoi usare break.
    break e continue sono piu' potenti di quanto non sembri, sopprattuto se usati con le label
Devi accedere o registrarti per scrivere nel forum
2 risposte