Newsgroup: it.comp.lang.c
Titolo: Grafo + liste di adiacenza (dov'e' l'errore?)

Ciao a tutti,
ho realizzato il programma che segue per implementare in C un grafo di n
elementi utilizzando le liste di adiacenza, ma c'e' qualcosa che non va
(credo nella funzione "cancella", per una cattiva gestione dei
puntatori), e non riesco proprio a correggere il codice.
Sapreste indicarmi dove e' (sono) l'errore (gli errori)?
Vi ringrazio per l'attenzione.
/* GRAFO.C -- implementa un grafo di NUM nodi utilizzando una lista  *
 *            di adiacenza per la sua rappresentazione               */
#include <stdio.h>
#include <stdlib.h>
/* NUM -- costante che indica il numero di nodi del grafo            */
#define NUM 5
/* celletta -- struttura che implementa le celle necessarie alla     *
 *             realizzazione della lista di adiacenza                *
 * membri: prossimo (puntatore all'indirizzo della cella successiva) *
 *         elemento (numero del nodo equivalente)                    */
struct celletta
{
struct celletta *prossimo;
int elemento;
};
/* inizializzazione di un vettore di puntatori a NUM cellette        */
struct celletta *nodo[NUM];
/* inserisci -- definisce un arco (relazione) tra nodi adiacenti     *
 * input: i (nodo di partenza), j (nodo di arrivo)                   *
 * output: nessuno                                                   */
void inserisci(int i, int j)
{
struct celletta *p;                    /* allocazione dinamica della */
p = malloc(sizeof(struct celletta));   /* memoria (per ogni celletta)*/
p->elemento = j;
p->prossimo = nodo[i-1];
nodo[i-1] = p;
printf("L'arco (%d,%d) e' stato inserito nel grafo.\n",i,j);
}
/* ricerca -- determina se un arco (relazione) e' presente nel grafo *
 * input: i (nodo di partenza), j (nodo di arrivo)                   *
 * output: 0 (l'arco non e' stato trovato), 1 (l'arco e' presente)   */
int ricerca(int i, int j)
{
struct celletta *next;
next = nodo[i-1];
while (next != NULL)
 {
 if (next->elemento == j)
  {
  printf("L'arco (%d,%d) e' presente nel grafo.\n",i,j);
  return 1;
  }
 next = next->prossimo;
 }
printf("L'arco (%d,%d) non e' presente nel grafo.\n",i,j);
return 0;
}
/* cancella -- elimina un arco (relazione) tra nodi adiacenti        *
 * input: i (nodo di partenza), j (nodo di arrivo)                   *
 * output: nessuno                                                   */
void cancella (int i, int j)
{
struct celletta *next, *temp;
next = nodo[i-1];
while (next != NULL)
 {
 if (next->elemento == j)
  {
  temp = next;
  next = (next->prossimo)->prossimo;
  free(temp);
  printf("L'arco (%d,%d) e' stato cancellato.\n",i,j);
  return;
  }
 next = next->prossimo;
 }
printf("L'arco (%d,%d) non e' stato cancellato: non esiste nel
grafo.\n",i,j);
}
/* visualizza -- stampa sul video l'elenco di tutti gli archi        *
 * input: nessuno                                                    *
 * output: nessuno                                                   */
void visualizza(void)
{
int a;
struct celletta *next;
printf("\nGli archi presento nel grafo sono:\n");
for (a=0; a<NUM; a++)
 {
 next = nodo[a];
 while (next != NULL)
  {
  printf("(%d,%d) ",(a+1),next->elemento);
  next = next->prossimo;
  }
 }
printf("\n\n");
}
/* main -- effettua un test di tutte le funzioni del programma       *
 * input: nessuno                                                    *
 * output: 0                                                         */
int main()
{
int a;
for (a=0; a<NUM; a++)        /* inizializza a NULL tutti gli elementi*/
 nodo[a] = NULL;      /* del vettore di puntatori             */
inserisci(1,2);
inserisci(1,3);
inserisci(1,4);
inserisci(3,2);
inserisci(3,4);
inserisci(4,5);
inserisci(5,1);
visualizza();
ricerca(3,2);
ricerca(3,3);
inserisci(3,5);
inserisci(2,4);
cancella(1,3);
cancella(2,5);
cancella(3,4);
visualizza();
return 0;
}

aladar <
ala...@ragemail.com
**nospam**> wrote:
a>Ciao a tutti,
a>ho realizzato il programma che segue per implementare in C un grafo di n
a>elementi utilizzando le liste di adiacenza, ma c'e' qualcosa che non va
a>(credo nella funzione "cancella", per una cattiva gestione dei
a>puntatori), e non riesco proprio a correggere il codice.
Potresti provare con qualcosa del genere:
-----------------------------------------------------------------------
void cancella(int i, int j)
{
        struct celletta **cur = &nodo[i - 1], *temp = NULL;
        while (*cur) {
                if ((*cur)->elemento == j) {
                        temp = *cur;
                        *cur = (*cur)->prossimo;
                        break;
                }
                cur = &((*cur)->prossimo);
        }
        printf("L'arco (%d,%d) ", i, j);
        if (temp) {
                free(temp);
                puts("e' stato cancellato.");
        } else
                puts("non e' stato cancellato: non esiste nel grafo.");
}
-----------------------------------------------------------------------
Ciao ciao,
Andrea
-- 
"...Unix, MS-DOS, and Windows NT (also known as the Good, the Bad, and 
 the Ugly)."
(by Matt Welsh)

Potresti provare con qualcosa del genere:
[...]
Grazie!!
Funziona e mi sembra una soluzione decisamente elegante (prendo appunti
per lo stile).
Ti ringrazio ancora per la disponibilita'.
Saluti,
Aladar