[C++] Inserimento in lista ordinata(ricorsivamente)

[gaten]

Salve ragazzi,

stò cercando di capire come inserire un elemento in una lista ordinata, IN MODO RICORSIVO.
Per esempio, supponiamo che la lista è la seguente:

[3][-]--->[4][-]--->[7][-]---> NULL

Adesso, vorrei inserire l'elemento 5, che dovebbe essere inserito trà 4 e 7, quindi otterrei una struttura di questo tipo:

[3][-]--->[4][-]--->[5][-]--->[7][-]---> NULL

Io ho iniziato a mettere giù un pò di codice:

#include<iostream>


using namespace std;


typedef struct nodo {
  int value;
  struct nodo *link;
};


nodo inserimento(nodo *head, int elemento);


int main()
{
nodo *head=NULL;

inserimento(head, elemento);
}


nodo inserimento(nodo *head, int elemento){
 
  if(head==NULL){
    (*head)->value=elemento;
    (*head)->link=NULL;
  }
  ......

}

Adesso, non riesco a capire come continuare il tutto.
Qualcuno potrebbe aiutarmi a completare il programma?

Grazie anticipatamente,
gaten

[Celebron]

a livello di logica la funzione ricorsiva che agisce sui nodi la farei così


(se valore del nodo successivo attualmente in esame è > del valore che voglio inserire) || (se nodo successivo a quello attuale == NULL)
inserisci
return

altrimenti ricorri su nodo successivo

[gaten]

Per adesso, sono riuscito ad inserire un solo valore nella lista, ecco il codice:

L'ho provato è funziona perfettamente:

#include<iostream>
using namespace std;

struct nodo {
  int value;
  struct nodo *link;
};

typedef struct nodo *lista;

// prototipi delle funzioni
lista inserimento(lista &head, int elemento);
lista stampa_lista(lista &head);

int main()
{
	lista head=NULL;
	int elemento;

	inserimento(head, elemento);
	stampa_lista(head);
}



lista inserimento(lista &head, int elemento){

	
	/* nel caso in cui non ci sono nodi */	
	if (head == NULL)
	{
		head=new nodo;
		cin>>head->value;
		head->link=NULL;
	}		
}

lista stampa_lista(lista &head){
	
	cout<<"Valori lista:"<<endl;		
	cout<<head->value<<endl;

}

Ho due dubbi:
1) Se non passo la lista per riferimento (&head) nelle funzioni, mi restituisce come errore: "Errore di segmentazione", perchè?

2) se dichiaro la struttura così non va bene:

typedef struct nodo_lista *lista;
struct nodo_lista{
	int value;
	lista link;
};

Adesso vorrei capire come inserire altri elementi nella lista, in modo ordinato.

Grazie anticipatamente.

[gaten]

Ragazzi, io ho creato questo codice per l'inserimento di elementi in una lista ordinata:

#include <iostream>
using namespace std;


typedef struct nodo{
	int valore;
	nodo *link;
 }lista;


void insert( lista *head,int elemento);


int main(){
	
	lista *head=NULL;
	
	int n;
	//Inseriamo da tastiera il nuovo numero da inserire.
	cout << "Elemento Da inserire: "<<endl;
	cin>> n;

	insert(head,n);
	
	//Stampa della lista!
	lista *temp;
	temp=head;
	while (temp != NULL) {
		
		cout << temp->valore;
		temp=temp->link;
	}
	
	return 0;
}

lista insert( lista *head,int elemento){

	lista *temp;
	temp->link=head;
	while (temp->link != NULL and elemento>temp->link->valore) {
		temp=temp->link;
	}
	
	if (temp->link==NULL) {
		temp->link=new lista;
		temp->link->valore=elemento;
		temp->link->link=NULL;
	}
		
}

ma mi dà errore nella funzione precisamente in questa riga:

temp->link=head;

ecco l'errore:
Program received signal: “EXC_BAD_ACCESS”.
sharedlibrary apply-load-rules all


grazie anticipatamente,
gaten

[Celebron]

non hai allocato temp ma hai definito solo il suo puntatore
temp->link "non esiste" e quindi ti da quel segmentation fault

[gaten]

Ho risolto grazie alla tua delucidazione ma ora non mi stampa!
Questa è la funzione:

#include <iostream>
using namespace std;


typedef struct nodo{
	int valore;
	nodo *link;
 }lista;


lista insert( lista *head,int elemento);
void stampa(lista *head);

int main(){
	
	lista *head=NULL;
	
	int n;
	//Inseriamo da tastiera il nuovo numero da inserire.
	cout << "Elemento Da inserire: "<<endl;
	cin>> n;

	insert(head,n);
	stampa(head);
	return 0;
}

lista insert( lista *head,int elemento){

	lista *temp;
	temp=new lista;
	temp->link=head;
	while (temp->link != NULL and elemento>temp->link->valore) {
		temp=temp->link;
	}
	
	if (temp->link==NULL) {
		temp->link=new lista;
		temp->link->valore=elemento;
		temp->link->link=NULL;
	}
		
}

void stampa(lista *head){
	
	lista *temp;
	temp=head;	
	
	while (temp != NULL){
		cout<<temp->valore<<endl;
		temp=temp->link;
	}
}

Questo è il mio codice attuale,
Grazie

[gaten]

up

[gaten]

Finalmente ci sono riuscito.
Volevo solo chiarire 2 dubbi, per farveli individuare ho preferito mettere dei punti "?".

1) perchè il programma mi funziona solo se passo la testa in questo modo:

lista insert( lista *&head, int elemento);

cioè, perchè passare *&

2) precisamente con:

head=temp;              // ?

questo cosa faccio? perchè?


Questo il codice:

#include<iostream>

using namespace std;

/* Tipo di dato lista */
typedef struct nodo{
    int valore;
    nodo *link;
} lista;



/* Prototipi delle functions */
lista insert( lista *&head, int elemento);
void stampa(lista *head);



int main()
{

    lista *head=NULL;

    char choise;
    int elemento;

    do {
        cout << "Elemento da inserire: "<<endl;
        cin>>elemento;
        insert(head, elemento);
        cout<<"Continuare l'inserimento?(s/n)"<<endl;
        cin>>choise;

    } while(choise=='s' || choise=='S');


    stampa(head);


    return 0;
}


/* function per inserire in modo ordinato gli elementi nella lista */
lista insert(lista *&head, int elemento) {

    lista *temp, *prec, *current;

    current=head;

    /* se il nodo corrente, cioè nel primo caso la testa(NULL) => vedi [ current=head ] e' nullo
     * o l'elemento e' <= del valore del puntatore corrente => nel nostro caso sempre NULL, poichè non
     * esiste alcun nodo,
     * INSERISCO L'ELEMENTO IN TESTA ALLA LISTA
     */
    if(current == NULL || elemento <= current->valore){

        temp=new lista;         // alloco dinamicamente memoria per un nodo temporaneo(temp)
        temp->valore=elemento;  // salvo l'elemento nel nodo temporaneo
        temp->link=current;     // il nuovo nodo creato, punterà a current che equivale alla testa, quindi il valore viene messo dietro la testa
        head=temp;              // ?

    } else {

        /* altrimenti se il nodo corrente non è nullo, cioè vale a dire esiste almeno un nodo
         * e l'elemento da inserire è maggiore di quelli precedenti,
         * fin quando il nodo corrente non punterà a NULL e l'elemento da inserire
         * è > di quelli già presenti nella lista,
         * salverò ad ogni iterazione il nodo subito precedente a quello che ha valore più grande dell'elemento da inserire.
         * es. |3|->|8|->|22|->NULL, se volessi inserire 5, savlerei il nodo con valore 3, in quanto alla itererazione successiva,
         * avremo un nodo che ha valore > dell'elemento da inserire(uscendo così dal while).
         */
        while(current != NULL && elemento > current->valore){

            prec=current;           // salvo il nodo precedente
            current=current->link;  // scorro la lista

        }

        temp=new lista;         // alloco dinamicamente memoria per un nodo temporaneo(temp)
        temp->valore=elemento;  // salvo l'elemento nel nodo temporaneo
        temp->link=current;     // il nodo che viene inserito, punterà a quello successivo, nel nostro esempio al nodo ->|8|
        prec->link=temp;        // il nodo precedente, nel nostro caso |3|-> punterà al nuovo nodo inserito, nel nostro esempio |5|
    }
}


/* function per stampare gli elementi della lista */
void stampa(lista *head) {

    lista *tmp;
    tmp=head;

    cout<<"Lista stampata:"<<endl;

    while (tmp != NULL) {
        cout<<tmp->valore<<endl;
        tmp=tmp->link;
    }
}