[TSP] aiuto con algoritmo
Salve a tutti,
ho provato ad abbozzare un algoritmo per il TSP euclideo. Dovrei però provarne la validità in termini di precisione (quanto la soluzione si discosta dall'ottimo) e di complessità dell'algoritmo.
Ho sfruttato il metodo "Graham scan" per ottenere l'inviluppo convesso dell'insieme dei nodi (che chiamo percorso iniziale). Ora scelgo il nodo più vicino ad un arco e lo faccio entrare nel percorso, ripeto questa operazione finché il percorso non tocca tutti i nodi.
Ho provato l'algoritmo (a mano, con carta e matita) su diversi insiemi di punti (dai 10 ai 20 punti) e ho sempre trovato il percorso ottimo. Ma come posso davvero valutarne la precisione?
So che il primo passo (Graham scan) ha costo $ O(nlog(n)) $ , il passo successivo devo calcolare per ogni nodo la distanza da ogni arco, quindi qual'è la complessità complessiva?
Spero di essere riuscito a spiegarmi...
Vi ringrazio in anticipo per ogni suggerimento
ps: non so se questo algoritmo è uguale ad altri già esistenti, io ho cercato un po' sul web ma non ho trovato niente (ho trovato moltissimi algoritmi per il TSP, ma non questo).
ho provato ad abbozzare un algoritmo per il TSP euclideo. Dovrei però provarne la validità in termini di precisione (quanto la soluzione si discosta dall'ottimo) e di complessità dell'algoritmo.
Ho sfruttato il metodo "Graham scan" per ottenere l'inviluppo convesso dell'insieme dei nodi (che chiamo percorso iniziale). Ora scelgo il nodo più vicino ad un arco e lo faccio entrare nel percorso, ripeto questa operazione finché il percorso non tocca tutti i nodi.
Ho provato l'algoritmo (a mano, con carta e matita) su diversi insiemi di punti (dai 10 ai 20 punti) e ho sempre trovato il percorso ottimo. Ma come posso davvero valutarne la precisione?
So che il primo passo (Graham scan) ha costo $ O(nlog(n)) $ , il passo successivo devo calcolare per ogni nodo la distanza da ogni arco, quindi qual'è la complessità complessiva?
Spero di essere riuscito a spiegarmi...
Vi ringrazio in anticipo per ogni suggerimento
ps: non so se questo algoritmo è uguale ad altri già esistenti, io ho cercato un po' sul web ma non ho trovato niente (ho trovato moltissimi algoritmi per il TSP, ma non questo).
Risposte
Perdonami qualè la differenza fra TSP 'normale' credo ed euclideo?
Se me lo spieghi mi fai un favore e provo ad aiutarti.
Comunque l'algoritmo che hai usato tu è quello del nodo più vicino?
Se me lo spieghi mi fai un favore e provo ad aiutarti.
Comunque l'algoritmo che hai usato tu è quello del nodo più vicino?
La differenza è che nel TSP euclideo si usano le distanze euclidee. Vedi http://en.wikipedia.org/wiki/Travelling_salesman_problem#Euclidean_TSP
No, non ho usato l'algoritmo del nodo più vicino. Io prima trovo l'inviluppo convesso, che uso come percorso iniziale. A questo punto faccio entrare i restanti nodi uno alla volta, scegliendo sempre il nodo più vicino ad un arco.
Cioè trovato l'inviluppo convesso ho un insieme di nodi che si trovano sul percorso iniziale (quelli appunto dell'inviluppo convesso) e un insieme di nodi che non sono ancora nel percorso. Io scelgo tra i nodi che non sono nel percorso quello più vicino ad un arco e quindi sostituisco l'arco con due nuovi archi per far entrare il nodo nel percorso.
Spero di essere riuscito a spiegarmi.
No, non ho usato l'algoritmo del nodo più vicino. Io prima trovo l'inviluppo convesso, che uso come percorso iniziale. A questo punto faccio entrare i restanti nodi uno alla volta, scegliendo sempre il nodo più vicino ad un arco.
Cioè trovato l'inviluppo convesso ho un insieme di nodi che si trovano sul percorso iniziale (quelli appunto dell'inviluppo convesso) e un insieme di nodi che non sono ancora nel percorso. Io scelgo tra i nodi che non sono nel percorso quello più vicino ad un arco e quindi sostituisco l'arco con due nuovi archi per far entrare il nodo nel percorso.
Spero di essere riuscito a spiegarmi.
Ora un pò di più.
Sembra un insieme di algoritmi tipo 'toppe' o k-albero ma sostanzialmente diverso.
Il succo è che tu vuoi valutarne la bontà?
Dovresti provarlo su tanti problemi ,con matrici dei costi + o meno simmetrici per vedere un attimo il rapporto:
(V(ottimo)-V(tuo))/V(ottimo) che valore ti da ..
certo provare a mano è decisamente noioso!!
Prova a scrivere qualcosa in C++ (java) quello che vuoi e vediamo se riusciamo a farlo così provare mediante pc sarà facile e potrai valutare,una volta scritta la funzione vediamo anche la sua complessità.
Sembra un insieme di algoritmi tipo 'toppe' o k-albero ma sostanzialmente diverso.
Il succo è che tu vuoi valutarne la bontà?
Dovresti provarlo su tanti problemi ,con matrici dei costi + o meno simmetrici per vedere un attimo il rapporto:
(V(ottimo)-V(tuo))/V(ottimo) che valore ti da ..
certo provare a mano è decisamente noioso!!
Prova a scrivere qualcosa in C++ (java) quello che vuoi e vediamo se riusciamo a farlo così provare mediante pc sarà facile e potrai valutare,una volta scritta la funzione vediamo anche la sua complessità.
i casi np-complessi io non gli ho ancora affrontati.
Ma da quello che ho capito vuoi dimostrare che il tuo algoritmo è corretto, giusto?
Allora con una dimostrazione per assurdo penso tu riesca a dimstrarne la "bontà": con questa frase sei già a buon punto "Io scelgo tra i nodi che non sono nel percorso quello più vicino ad un arco e quindi sostituisco l'arco con due nuovi archi per far entrare il nodo nel percorso."
Poi per l'inviluppo complesso in sè mi sembra ci siano dimostrazioni rigorose in giro, perchè è un problema molto conosciuto.
Se è tutt'altro quello che vuoi dimostrare allora non so aiutarti, perchè sono argomenti di algortimi avanzati.
ciao
Ma da quello che ho capito vuoi dimostrare che il tuo algoritmo è corretto, giusto?
Allora con una dimostrazione per assurdo penso tu riesca a dimstrarne la "bontà": con questa frase sei già a buon punto "Io scelgo tra i nodi che non sono nel percorso quello più vicino ad un arco e quindi sostituisco l'arco con due nuovi archi per far entrare il nodo nel percorso."
Poi per l'inviluppo complesso in sè mi sembra ci siano dimostrazioni rigorose in giro, perchè è un problema molto conosciuto.
Se è tutt'altro quello che vuoi dimostrare allora non so aiutarti, perchè sono argomenti di algortimi avanzati.
ciao
Intanto ringrazio entrambi per le risposte e i suggerimenti.
Volevo semplicemente provare a creare un nuovo algoritmo per risolvere il TSP (cioè che fornisse una buona soluzione in tempi ragionevoli), e così ho abbozzato l'algoritmo che ho descritto sopra. L'ho provato con carta e penna ed ho visto che forniva dei buoni risultati (addirittura nelle prove che ho fatto erano ottimi).
Non sono però in grado di calcolare da solo:
1) quanto è precisa la soluzione (cioè quanto si discosta dall'ottimo)
2) qual'è il costo computazionale
Per la prima penso che dovrò per forza fare come suggerito da edge; sto provando a scriverlo in C, ma vado un po' a rilento...
Per il secondo punto invece credo che esista un modo per calcolarne la complessità anche senza scrivere in codice, magari basta uno pseudocodice?
Volevo semplicemente provare a creare un nuovo algoritmo per risolvere il TSP (cioè che fornisse una buona soluzione in tempi ragionevoli), e così ho abbozzato l'algoritmo che ho descritto sopra. L'ho provato con carta e penna ed ho visto che forniva dei buoni risultati (addirittura nelle prove che ho fatto erano ottimi).
Non sono però in grado di calcolare da solo:
1) quanto è precisa la soluzione (cioè quanto si discosta dall'ottimo)
2) qual'è il costo computazionale
Per la prima penso che dovrò per forza fare come suggerito da edge; sto provando a scriverlo in C, ma vado un po' a rilento...
Per il secondo punto invece credo che esista un modo per calcolarne la complessità anche senza scrivere in codice, magari basta uno pseudocodice?
Conosci il C++? Il c non lo conosco, anche se siamo lì su tante cose.
Sicuramente basta lo pseudo codice..
Se hai problemi posta (l'idea è interessante e lodevole)
Sicuramente basta lo pseudo codice..
Se hai problemi posta (l'idea è interessante e lodevole)
"giacomo.bezzi":
1) quanto è precisa la soluzione (cioè quanto si discosta dall'ottimo)
2) qual'è il costo computazionale
Sono due domande al limite del paradossale.
Il tsp euclideo è un problema NP-completo quindi il suo costo computazionale è per definizione polinomiale non deterministico, che nella pratica diventa esponenziale. E la cosa vale per qualsiasi algoritmo tu abbia sviluppato.
Di fatto ti è impossibile definire la precisione della soluzione senza sapere o poter valutare la soluzione esatta.
L'unica cosa sicura del TSP euclideo è che nella soluzione ottima non ci sono archi che si incrociano.
Comunque le migliori procedure note per risolvere questi problemi sono quelle iterative, ovvero trova una soluzione e migliorala. E per questi casi si può sempre valutare la velocità di 'convergenza'.
"giggi1999":
Il tsp euclideo è un problema NP-completo quindi il suo costo computazionale è per definizione polinomiale non deterministico, che nella pratica diventa esponenziale. E la cosa vale per qualsiasi algoritmo tu abbia sviluppato.
Inteso per algoritmi che forniscono una soluzione ottima? Per algoritmi approssimati questo è falso.
"giggi1999":
Di fatto ti è impossibile definire la precisione della soluzione senza sapere o poter valutare la soluzione esatta.
Sono d'accordo, ma esistono molti percorsi "noti" sui quali si può provare l'algoritmo e avere almeno una idea di quanto si discosta dall'ottimo.
Ho fatto uno pseudo codice.
Non ho scritto la parte relativa all'algoritmo Graham scan perché si trovano sul web molti pseudo codici e anche sorgenti liberamente scaricabili (ad esempio http://en.wikipedia.org/wiki/Graham_scan#Pseudocode)
Quindi in questo pseudo codice assumo che nel vettore "percorso[]" inizialmente ci stiano i nodo dell'inviluppo convesso.
Mi auguro che si capisca, altrimenti fatemi sapere se ci sono parti poco chiare.
Grazie ancora a tutti per le risposte
Non ho scritto la parte relativa all'algoritmo Graham scan perché si trovano sul web molti pseudo codici e anche sorgenti liberamente scaricabili (ad esempio http://en.wikipedia.org/wiki/Graham_scan#Pseudocode)
Quindi in questo pseudo codice assumo che nel vettore "percorso[]" inizialmente ci stiano i nodo dell'inviluppo convesso.
struct punto {
int x;
int y;
}
punto nodi[] //insieme dei nodi non sul percorso
punto percorso[] //insieme dei nodi sul percorso, inizialmente quelli dell'inviluppo convesso trovati con Graham scan
//----calcola la distanza di un nodo rispetto ad un arco----
int calcoladistanza(punto a, punto b, punto c) {
int d1, d2, d3, p, h;
d1=sqrt(((a.x-b.x)^2)+(a.y-b.y)^2));
d2=sqrt(((a.x-c.x)^2)+(a.y-c.y)^2));
d3=sqrt(((b.x-c.x)^2)+(b.y-c.y)^2));
p=(d1+d2+d3)/2;
h=(sqrt(p(p-d1)(p-d2)(p-d3)))/(2*d3);
return h;
}
//----Inserisco il nuovo nodo nel percorso e lo elimino dalla lista dei nodi fuori percorso----
void InserisciTogli(int nuovoNodo, int posizione) {
punto percorsoTemp[];
punto nodiTemp[];
for(int i=1; i<(percorso.length+1); i++) { //faccio entrare il nuovo nodo nel percorso
if(i<posizione)
percorsoTemp[i]=percorso[i];
else if(i==posizione)
percorsoTemp[i]=nodi[nuovoNodo];
else if(i>posizione)
percorsoTemp[i]=percorso[i+1];
}
percorso[] = percorsoTemp[];
if(nodi.length==1) //se era l'ultimo nodo fuori dal percorso
nodi[] = NULL;
else {
for(int i=1; i<(nodi.length-1); i++) { //elimino il nodo entrato nel percorso dalla lista dei nodi fuori percorso
if(i<posizione)
percorsoTemp[i]=percorso[i];
if(i==posizione)
percorsoTemp[i]=nodi[nuovoNodo];
if(i>posizione)
percorsoTemp[i]=percorso[i+1];
}
nodi[] = nodiTemp[];
}
return;
}
void main() {
int minh = -1;
int h, nuovoNodo, posizione;
while(nodi != NULL) {
for(int i=1; i<nodi.length; i++) {
for(int j=1; j<percorso.length-1; j++) {
h = calcoladistanza(nodi[i], nodi[j], nodi[j+1])
if(h<hmin || hmin==-1){
hmin = h;
nuovoNodo = i;
posizione = j;
}
}
}
minh=-1;
InserisciTogli(nuovoNodo, posizione);
}
Mi auguro che si capisca, altrimenti fatemi sapere se ci sono parti poco chiare.
Grazie ancora a tutti per le risposte
E' abbastanza chiaro. Alcune parti andrebbero implementate in maniera differente per evitare di ripetere operazioni. Anche l'uso della struttura array "rallenta" il tutto, quindi facciamo conto di usare una lista: l'operazione di aggiunta (nodo alla lista) avrà costo elementare [e se pensi anche di scrivere un codice da provare al computer, credo proprio sia meglio tu implementi una lista].
Questo però me lo devi spiegare meglio:
Come vedi c'è un ciclo che si basa sul numero degli elementi di 'nodi' e 'percorso' ma ti riferisci solo a 'nodi' per i calcoli... sicuro sia corretto? Rivedilo un po'
Comunque, possiamo provare a stimare la complessità sulla base di $n$ come numero di nodi iniziali. Al totale aggiungeremo poi la complessità del GS.
Il ciclo esterno esamina ogni nodo (del percorso!) ed il successivo; per ognuna di queste coppie calcola la distanza con tutti i restanti nodi, e seleziona quello che ha distanza minore, che aggiunge fra questi. Possiamo evitare di calcolare nella complessità il costo del calcolo della distanza fra i nodi del percorso (poiché l'operazione possiamo farla una volta sola).
Doppio ciclo più inserimento, quindi abbiamo la prima approssimazione in $O(n)=n^2$. In questo caso però $n$ rappresenta il numero complessivo e forse possiamo essere più precisi.
Questo però me lo devi spiegare meglio:
for(int i=1; i<nodi.length; i++) {
for(int j=1; j<percorso.length-1; j++) {
h = calcoladistanza(nodi[i], nodi[j], nodi[j+1])
if(h<hmin || hmin==-1){
hmin = h;
nuovoNodo = i;
posizione = j;
}
}
}Come vedi c'è un ciclo che si basa sul numero degli elementi di 'nodi' e 'percorso' ma ti riferisci solo a 'nodi' per i calcoli... sicuro sia corretto? Rivedilo un po'
Comunque, possiamo provare a stimare la complessità sulla base di $n$ come numero di nodi iniziali. Al totale aggiungeremo poi la complessità del GS.
Il ciclo esterno esamina ogni nodo (del percorso!) ed il successivo; per ognuna di queste coppie calcola la distanza con tutti i restanti nodi, e seleziona quello che ha distanza minore, che aggiunge fra questi. Possiamo evitare di calcolare nella complessità il costo del calcolo della distanza fra i nodi del percorso (poiché l'operazione possiamo farla una volta sola).
Doppio ciclo più inserimento, quindi abbiamo la prima approssimazione in $O(n)=n^2$. In questo caso però $n$ rappresenta il numero complessivo e forse possiamo essere più precisi.
"Rggb":
Questo però me lo devi spiegare meglio:
for(int i=1; i<nodi.length; i++) { for(int j=1; j<percorso.length-1; j++) { h = calcoladistanza(nodi[i], nodi[j], nodi[j+1]) if(h<hmin || hmin==-1){ hmin = h; nuovoNodo = i; posizione = j; } } }
Come vedi c'è un ciclo che si basa sul numero degli elementi di 'nodi' e 'percorso' ma ti riferisci solo a 'nodi' per i calcoli... sicuro sia corretto?
Ecco come dovrebbe essere:
for(int i=1; i<nodi.length; i++) {
for(int j=1; j<percorso.length-1; j++) {
h = calcoladistanza(nodi[i], percorso[j], percorso[j+1])
if(h<hmin || hmin==-1){
hmin = h;
nuovoNodo = i;
posizione = j;
}
}
}
cioè calcola la distanza tra il nodo (fuori dal percorso) e ogni arco del percorso.
Mi sono anche accorto che con questa procedura non calcola la distanza tra il nodo e l'ultimo arco (per intenderci quello che va dall'ultimo al primo nodo sul percorso).
Ma questa operazione può essere aggiunta dopo il for.
La complessità del GS è $O(nlog(n))$ quindi sommato a $O(n^2)$ da sempre $O(n^2)$, giusto?
"Rggb":
Il ciclo esterno esamina ogni nodo (del percorso!) ed il successivo; per ognuna di queste coppie calcola la distanza con tutti i restanti nodi, e seleziona quello che ha distanza minore, che aggiunge fra questi.
Questa operazione però è ripetuta finché la lista di nodi fuori percorso è vuota (cioè fino a quando tutti i nodi sono entrati nel percorso), quindi non dovrebbe essere $O(n^3)$?
Sto provando a scrivere un programmino, per fare qualche prova, ma come si vede sono un po' arrugginito in programmazione... in effetti non avevo pensato alle liste, grazie del suggerimento!
"giacomo.bezzi":
Mi sono anche accorto che con questa procedura non calcola la distanza tra il nodo e l'ultimo arco (per intenderci quello che va dall'ultimo al primo nodo sul percorso).
Ma questa operazione può essere aggiunta dopo il for.
Si, appunto; non è questo il problema. Poi, se e quando implementerai un programma da provare al calcolatore, magari saremo precisi, ma per adesso ci va bene così.
"giacomo.bezzi":
Questa operazione però è ripetuta finché la lista di nodi fuori percorso è vuota (cioè fino a quando tutti i nodi sono entrati nel percorso), quindi non dovrebbe essere $O(n^3)$?
Certo, infatti parlavo del doppio ciclo interno. Proviamo a questo punto a fare delle verifiche e vediamo se $O(n)=n^3$ possa tornare.
Quante volte viene eseguito il doppio ciclo interno (ovvero quante volte ripete il ciclo while() esterno) e quante operazioni vengono fatte al suo interno? Impostiamo un po' di cose: diciamo $n$=numero di nodi totali, $k$ numero di nodi già nel path, $m$ numero di nodi restanti; chiaramente $n=k+m$.
Avendo $m$ elementi in 'nodi' il ciclo while verrà eseguito $m$ volte; vediamo cosa succede:
- la prima volta ci saranno $m$ elementi in 'nodi' e $k$ elmenti in 'percorso', per un totale di $m*k$ operazioni;
- la seconda volta, rispettivamente $m-1$ e $k+1$ - totale $(m-1)*(k+1)$ operazioni;
...
- l'ultima volta ci sarà 1 nodo e dovranno essere eseguite $k+m-1=n-1$ operazioni.
Quindi $O(n)=n^3$ secondo me è eccessivo. Lo sviluppo di sopra mi ricorda una formula già vista... dopo provo a cercare
Bene, si tratta comunque di un tempo polinomiale, quindi è un algoritmo trattabile.
Ora cerco di scrivere un codice in modo da poterne valutare (a grandi linee almeno) la precisione. Mi sa che avrò bisogno di di aiuto perché è passato un po' di tempo dall'ultimo programmino che ho scritto. Comunque mi metto al lavoro!
Intanto grazie ancora a tutti per le risposte.
Ora cerco di scrivere un codice in modo da poterne valutare (a grandi linee almeno) la precisione. Mi sa che avrò bisogno di di aiuto perché è passato un po' di tempo dall'ultimo programmino che ho scritto. Comunque mi metto al lavoro!
Intanto grazie ancora a tutti per le risposte.
Salve ancora a tutti,
nei giorni scorsi non ho più avuto il tempo di provare a scrivere il codice perché sono stato sommerso di impegni.
Oggi però ero intenzionato a scriverlo ma mi sono bloccato al primo scoglio...
Ho preso un sorgente in C per l'algoritmo Graham scan, e volevo aggiungere i restanti passi dell'algoritmo.
Il sorgente l'ho preso qui: http://www.chrisharrison.net/projects/convexHull/c99.c.
Ho modificato il codice in modo da poter inserire i nodi da stdin e qualche piccolo dettaglio, e fin qui nessun problema.
Poi però volevo creare una nuova lista dove inserire i nodi che non entrano nell'inviluppo convesso, ma non ci sono riuscito
.
Ho creato la nuova lista e creato due funzioni per aggiungere e stampare gli elementi, ma quando il programma arriva alla funzione stampa mi dice: "Segmentation fault".
Dopo aver passato quasi tutto il pomeriggio a tentare e ritentare mi appello al vostro aiuto per qualche suggerimento.
Grazie in anticipo!
nei giorni scorsi non ho più avuto il tempo di provare a scrivere il codice perché sono stato sommerso di impegni.
Oggi però ero intenzionato a scriverlo ma mi sono bloccato al primo scoglio...
Ho preso un sorgente in C per l'algoritmo Graham scan, e volevo aggiungere i restanti passi dell'algoritmo.
Il sorgente l'ho preso qui: http://www.chrisharrison.net/projects/convexHull/c99.c.
Ho modificato il codice in modo da poter inserire i nodi da stdin e qualche piccolo dettaglio, e fin qui nessun problema.
Poi però volevo creare una nuova lista dove inserire i nodi che non entrano nell'inviluppo convesso, ma non ci sono riuscito
.Ho creato la nuova lista e creato due funzioni per aggiungere e stampare gli elementi, ma quando il programma arriva alla funzione stampa mi dice: "Segmentation fault".
Dopo aver passato quasi tutto il pomeriggio a tentare e ritentare mi appello al vostro aiuto per qualche suggerimento.
Grazie in anticipo!
"Welcome in segfault world!" 
Ho dato una scorsa al sorgente, Visto che usa una lista? Però se usi la funzione addPoint dovrebbe andare, quindi dove ti dà segfault...nella stampa? Ovvero?
PS. Normalmente questo errore è perché fai riferimento ad un valore non allocato (es. un null pointer quando dovrebbe esserci qualcosa in memoria tipo una stringa, o nel nostro caso una struttura nodo)
Ho dato una scorsa al sorgente, Visto che usa una lista?
Però se usi la funzione addPoint dovrebbe andare, quindi dove ti dà segfault...nella stampa? Ovvero?PS. Normalmente questo errore è perché fai riferimento ad un valore non allocato (es. un null pointer quando dovrebbe esserci qualcosa in memoria tipo una stringa, o nel nostro caso una struttura nodo)
Ho creato una funzione "addRimanente" che scorre la lista fino all'ultimo elemento ed inserisce il nuovo elemento, ed una "printRimanenti" simile a "printPoints" e ovviamente una lista "rimanenti".
Poi ho messo la chiamata ad "addRimanente" in "grahamScan, dopo il secondo if (if(!isConvexPoint(P))) e la chiamata a "printRimanenti" in "mainGraham" dopo "printPoints".
L'errore avviene proprio quando il programma prova a stampare gli elementi di "rimanenti". Infatti commentando la chiamata a printRimanenti il programma va.
Vorrei mettere il sorgente così si capisce meglio cosa ho fatto ma se lo posto qui viene troppo lungo... se serve lo salvo su googledocs e metto il link, o c'è un modo migliore per farlo?
Poi ho messo la chiamata ad "addRimanente" in "grahamScan, dopo il secondo if (if(!isConvexPoint(P))) e la chiamata a "printRimanenti" in "mainGraham" dopo "printPoints".
L'errore avviene proprio quando il programma prova a stampare gli elementi di "rimanenti". Infatti commentando la chiamata a printRimanenti il programma va.
Vorrei mettere il sorgente così si capisce meglio cosa ho fatto ma se lo posto qui viene troppo lungo... se serve lo salvo su googledocs e metto il link, o c'è un modo migliore per farlo?
Posta solo il codice delle funzioni che hai fatto, non dovrebbe essere troppo lungo.
Ok, ecco le funzioni:
void addRimanente(struct point Point) {
struct point *tempPoint, *curPoint;
//ALLOCATE A NEW POINT STRUCTURE AND INITIALIZE INTERNAL VARIABLES
tempPoint = (struct point*)malloc(sizeof(struct point));
tempPoint->x=Point.x;
tempPoint->y=Point.y;
tempPoint->next=NULL;
tempPoint->prev=NULL;
if (firstFuori==NULL) //TEST IF LIST IS EMPTY
{
firstRimanente=tempPoint;
return;
}
curPoint=firstRimanente;
while (curPoint->next!=NULL) //CONTINUE THROUGH LIST UNTIL THE LAST ELEMENT
curPoint=curPoint->next;
//ADD ELEMENT
curPoint->next=tempPoint;
tempPoint->prev=curPoint;
return;
}
void printRimanenti()
{
struct point *curPoint=firstRimanente;
while (curPoint->next!=NULL) {
printf("(%d, %d)\n", curPoint->x, curPoint->y);
curPoint=curPoint->next;
}
}
Cominciamo dalle banalità (tanto per essere sicuri, non si sa mai); 'firstRimanente' è static? 'firstFuori' è static? L'hai inizializzato?
"firstFuori" è "firstRimanente", ho sbagliato copiando il codice...
"firstRimanente" l'ho dichiarata tra le variabili globali (dopo "firstPoint"):
ed inizializzata in "grahamInit" (anche qui dopo "firstPoint"):
"firstRimanente" l'ho dichiarata tra le variabili globali (dopo "firstPoint"):
struct point* firstRimanente;
ed inizializzata in "grahamInit" (anche qui dopo "firstPoint"):
firstRimanente=NULL;
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo