PDA

Visualizza la versione completa : inserimento in ordine di un elemento in una lista linguaggio c


SSSS90
15-05-2014, 12:44
Salve ho un problema di comprensione di un punto di questo esercizio...che ho nei miei appunti..
vi posto prima il codice completo:

Ecco il codice completo:


/*Creazione di una lista*/
#include<stdlib.h>
#include<stdio.h>
/*#include<assert.h>*/
/*Prototipi di funzione*/
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
struct Sinfo{

int value;
};
typedef struct Sinfo Tinfo;

struct SNode{
Tinfo info; /*rappresenta il campo informativo del nodo*/
struct SNode *link; /*link è un puntatore che punta a una struttura successiva SNode*/
};
typedef struct SNode TNode;
typedef TNode *TList;

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/*funzione per la creazione di una lista vuota*/
TList Crea_Lista(); /*TList è il valore ritornato,Crea_Lista è il nome della funzione,questa funzione ci servirà per inizializzare
una lista,più in generale è stata creata una lista vuota,poichè il valore Tlist restituito dalla funzione è NULL*/
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

/*Funzione per leggere il tipo Tinfo relativo a un nodo*/
Tinfo Leggi_Info(); /*Tinfo è il valore ritornato,perchè la funzione dovrà proprio leggere Tinfo dal nodo
e quindi quello che ritorna e' proprio il valore letto*/
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
TList Inserisci_Elemento(Tlist lista,TInfo info);
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void Stampa_Lista(TList Lista);
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
int main()
{
TList lista;
Tinfo info;
int i,dim;


lista=Crea_Lista(); /*Comando per creare lista vuota*/
printf("Quanti elementi vuoi inserire");
scanf("%d",&dim);
for(i=0;i<dim;i++) /*il ciclo for serve per inserire tutti gli elementi della lista uno alla volta
all'interno della lista*/
{
info=Leggi_info();

lista=Inserisci_Elemento(lista,info); /*inserisce l'elemento info,cioè l'elemento che abbiamo letto all'interno della lista*/
}


}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
TList Crea_Lista(){
return NULL;
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Tinfo Leggi_info(){

Tinfo info; /*possiamo chiamarla info poichè è una variabile locale e non crea problemi*/
printf("Inserisci numero");
scanf("%d",&info.value);
return info; /*perchè return info e non return info.value*/
}

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//inserimento in ordine
//Questo tipo di funzione può essere suddivisa in tre fasi:
/*a)Ricerca della posizione in cui inserire l'elemento(es ho inserito il num 3 e il num 6 e voglio inserire il 5,devo allora ricercare
la posizione in cui inserire il numero 5*
b)Allocazione dinamica
c)Aggiornamento dei collegamenti:Una volta inserito l'elemento 5 immezzo a 3 e 6,Dobbiamo collegare il puntatore
del nodo che abbiamo appena inserito(nodo5) al nodo successivo e inoltre il nodo precedente (nodo contente 3)deve puntare
al nodo che abbiamo appena inserito(il nodo che conterrà 5,il nodo centrale volendo immaginare)*/
TList Inserisci_Elemento(Tlist lista,TInfo info){
TList prec,curr,newnode; /*Ho creato tre nodi,un nodo precedente,un nodo corrente e un nuovo nodo che andremo ad allocare*/
prec=NULL;
curr=lista; /*impostiamo curr al primo nodo della lista*/

///////////////////////////////////////////////////////////////////

/*a)PRIMA FASE*/
while(curr!=NULL &&info.value>curr->info.value){ /*scorriamo tutta la lista fino alla fine della lista(curr!=NULL)*/
/*inoltre se il numero che vogliamo inserire all'interno della lista (info.value) e' maggiore
del nodo che stiamo visitando(curr->info.value) allora deve scorrere in avanti...per cui:*/
prec=curr; /*il nodo precedente diventa curr*/
curr=curr->link; /* curr si sposta al nodo successivo*/
}
}
///////////////////////////////////////////////////////////////////
//Vediamo un es di funzionamento dell'inserimento dell'elemento visto nel codice precedente:
//abbiamo una lista on 4 6 8 e dobbiamo inserire 7,7>4 si allora andiamo avanti 7>6 si allora andiamo avanti,7>8no allora dopo 6 scriviamo 7
//dopo questi ragionamenti la lista diventa 4 6 7 8
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/*b)SECONDA FASE*/
newnode=(TNode*)malloc(sizeof(TNode));
assert(newnode!=NULL);
newnode->info=info;

/*c)TERZA FASE*/
if(prec==NULL){ /*se l'elemento precedente è uguale a NULL questo significa che l'elemento e' quello di testa,diciamo questo
perchè prec l'abbiamo impostato a NULL cioè la lista è vuota è come se avesse un solo elemento il cui valore è nullo(NULL)*/
newnode->link=lista; /*newnode punterà al nodo successivo che e' appunto lista*/
lista=newnode; /*passiamo il valore di newnode a lista,cioè lo assegniamo a lista*/
return lista; } /*per farcelo poi ritornare*/
else{ /*altrimenti significa che stiamo inserendo l'elemento o in posizione centrale o in coda*/
prec->link=newnode; /*il nodo precedente deve puntare al nodo che abbiamo inserito(newnode)*/
newnode->link=curr; /*il nuovo nodo deve puntare a curr*/
return lista;}
}
//////////////////////////////////////////////////////////////////////////////////
void Stampa_Lista(TList Lista){
Tlist curr; /*creiamo un elemento corrente*/
curr=lista /*lista è il puntatore al primo nodo della lista,quindi impostiamo curr al primo nodo della lista*/
while(curr!=NULL ) /*Ora stampiamo il campo info di ciascuno nodo fintanto chè l'elemento corrente è diverso da NULL(curr!=NULL)*/
/*Cioè quando siamo arrivati a un nodo che e' NULL significa che siamo arrivati alla fine della lista*/
/* sarebbe stato equivalente fare Stampa_Info(curr->info); una volta definita la funzione stampa,prox tutorial*/
printf("%d",curr->info.value);/* stampa del campo value del nostro nodo che si chiama info*/
curr=curr->link;
}




BREVE SPIEGAZIONE ESERCIZIO:

l'esercizio inizializza prima una lista e poi chiede di inserire degli interi ,non in ordine uno per volta, che poi verrano stampati in ordine a video.Cioè devo realizzare la seguente cosa:
inserisci un numero: 10;
inserisci un numero: 2;
inserisci un numero: 3;
inserisci un numero 1;

1 2 3 10


La parte di codice che mi crea qualche perplessità è la seguente:



printf("Quanti elementi vuoi inserire");
scanf("%d",&dim);
for(i=0;i<dim;i++) /*il ciclo for serve per inserire tutti gli elementi della lista uno alla volta
all'interno della lista*/
{
info=Leggi_info();

lista=Inserisci_Elemento(lista,info);

acquisisco il numero di elementi ,cioè dim (ad es 4 elementi )e poi parte il ciclo for in cui è contenuta la prima la funzione :

[info=Leggi_info();/CODE] che acquisisce un """solo""" numero(es 10), e ritorna il solo unico valore appena inserito :
[CODE]return info. A questo punto parte la funzione:

lista=Inserisci_Elemento(lista,info);
in cui vi è la seguente istruzione che mi suscita non poche perplessità:

while(curr!=NULL &&info.value>curr->info.value:

la mia domanda è ma se fino ad ora ho acquisito un unico numero come faccio a fare il confronto tra
: info.value che è il valore che voglio inserire nella lista(che poi è l'unico numero di cui abbiamo parlato fino a ora ,"10"per intenderci) e curr->info.value che è il generico nodo che stiamo visitando(ad esempio il secondo nodo),al cui interno ancora non abbiamo caricato alcun valore....?(Finora abbiamo caricato solo 10!!!)

Spero di essere stato chiaro...Cosa c'è di sbagliato nel mio ragionamento

oregon
15-05-2014, 13:05
E il confronto

curr!=NULL

secondo te a che serve?

SSSS90
15-05-2014, 16:39
questo è il mio ragionamento:inserisco il valore 10 viene salvato in info.value e ritornato dalla funzione Leggi_info,il valore di info viene passato alla seconda funzione contenuta nel ciclo for cioe:lista=Inserisci_Elemento(lista,info);

Entriamo nella funzione Inserisci_Elemento ,in essa prec=NULL. curr=list=NULL perchè la lista è stata inizializzata a nulla grazie alla funzione:Crea_Lista();

Quindi il ciclo :while(curr!=NULL &&info.value>curr->info.value) non parte poichè curr=NULL.. A questo punto viene allocato il nuovo nodo e nel campo info del nodo viene salvato 10.
Subito dopo viene eseguito:newnode->link=lista,siccome (prec==NULL);

Con questa istruzione(qui ho delle perplessità..!!!)lista che è ancora inizializzata a NULL(?) viene associata al campo link del nuovo nodo(ma n ha senso!!!) viene eseguita:

lista=newnode;
return lista;
a questo punto ritorniamo nel main :

lista=Inserisci_Elemento(lista,info)

SSSS90
15-05-2014, 17:30
inoltre mi da alcuni errori di compilazione:
`Tlist' was not declared in this scope
alla riga:
TList Inserisci_Elemento(Tlist lista,TInfo info);
come mai?
ci sto sbattendo la testa da mezza giornata..qualcuno ha qualche idea

Alex'87
15-05-2014, 17:40
Il tuo tipo si chiama TList e tu hai scritto Tlist.

SSSS90
15-05-2014, 18:01
un altro errore di compilazione è questo:
hai qualche consiglio:


`TNode*Inserisci_Elemento' redeclared as different kind of symbol
alla seguente riga di codice:
TList Inserisci_Elemento(Tlist lista,TInfo info){

Alex'87
15-05-2014, 19:46
Anche lì hai scritto Tlist ^^'

SSSS90
15-05-2014, 19:53
grz

SSSS90
15-05-2014, 20:03
cerco di sintetizzare la domanda di prima ponendola in modo meno confusionario..ma l'istruzione :

newnode->link=lista; che fa e soprattutto alla prima iterazione quanto vale?:confused::confused:
leggendo così l'istruzione la interpreto nel seguente modo:prendi lista che nella prima iterazione dovrebbe valere null e inseriscila nel campo link del nuovo nodo....ma che senso ha che il campo link del nuovo nodo sia Null..mica la lista è finita...non ci sono altri numeri da inserire?Spero di essere stato chiaro...

SSSS90
16-05-2014, 12:38
qualcuno sa come risolvere il mio dubbio?

Loading