PDA

Visualizza la versione completa : [C++] Inserimento in lista ordinata(ricorsivamente)


gaten
27-04-2011, 17:49
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
27-04-2011, 17:56
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
28-04-2011, 19:55
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
29-04-2011, 15:10
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
29-04-2011, 15:46
non hai allocato temp ma hai definito solo il suo puntatore
temp->link "non esiste" e quindi ti da quel segmentation fault

gaten
29-04-2011, 16:15
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
29-04-2011, 19:51
up

gaten
30-04-2011, 02:34
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 *& :facepalm:

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

Loading