Newsgroup: it.comp.lang.c
Titolo: linked list bidirezionali

ciao a tutti....devo creare una linked list bidirezionale, dove next 
punta all'elemento successivo e previous a quello precedente
ecco cosa avevo pensato.......ma nn capisco perchè è sbagliato:
vi ringrazio in anticipo per l'aiuto
#include <stdio.h>
#include <stdlib.h>
typedef char DATA;
struct linked_list {
    DATA d;
    struct linked_list *next;
    struct linked_list *previous;
};
typedef struct linked_list ELEMENT;
typedef ELEMENT *LINK;
LINK creazione_lista_bid(char s[])
{
    int i;
    LINK head, temp1, a[10];
    i = 0;
    if  (s[0] == '\0')
    return NULL;
    else {
        head = malloc(sizeof(ELEMENT));
        head -> d =s[0];
        i = i + 1;
;       temp1 = head -> next;
        a[i] = temp1;
        head -> next = creazione_lista_bid(s +1);
        head -> previous = a[i];
        i = i-1;
        return head;
    }
}
int main(int argc, char *argv[])
{
  LINK a;
  char temp, temp2;
  a = creazione_lista_bid("casa");
  temp = a -> next -> next -> d;
  temp2 = a -> next -> next -> previous -> d;
  printf("%c\n", temp);
  printf("%c\n", temp2);
  system("PAUSE");
  return 0;
}
-- 
Renato Zero
Provaci a riemergere, da quei sogni che il tuo silenzio ha ucciso...che 
ne sai, dell'origine, delle lacrime, se non ha mai pianto...provaci, a 
scommettere, che al traguardo tu non sarai secondo...agile è 
quest'anima,  non puoi vincerla, non la puoi ingannare più......PROVA A 
PRENDERMI......

 vi ringrazio in anticipo per l'aiuto
modificando il tuo codice farei così:
#include <stdio.h>
#include <stdlib.h>
typedef char DATA;
struct linked_list {
    DATA d;
    struct linked_list *next;
    struct linked_list *previous;
};
typedef struct linked_list ELEMENT;
typedef ELEMENT *LINK;
LINK creazione_lista_bid(char s[])
{
    static int i=0;
    LINK head, temp1;
    static LINK a[10];
    if  (s[0] == '\0') {
       --i;
       return NULL;
    }
    else {
        head = malloc(sizeof(ELEMENT));
        head -> d =s[0];
        a[i] = head;
        i++;
        head -> next = creazione_lista_bid(s +1);
        --i;
        head -> previous = a[i];
        return head;
    }
}
int main(int argc, char *argv[])
{
  LINK a;
  char temp, temp2;
  a = creazione_lista_bid("1234");
  temp = a -> next -> next -> d;
  temp2 = a -> next -> next -> previous -> d;
  printf("%c\n", temp);
  printf("%c\n", temp2);
  system("PAUSE");
  return 0;
}
evitando variabili static e di tener traccia dei nodi precedenti in un 
array di dimensione fissa farei così:
#include <stdio.h>
#include <stdlib.h>
typedef char DATA;
struct linked_list {
    DATA d;
    struct linked_list *next;
    struct linked_list *previous;
};
typedef struct linked_list ELEMENT;
typedef ELEMENT *LINK;
LINK helper(char *s, LINK prev) {
    LINK head;
    if  (*s == '\0')
       return NULL;
    else {
        head = (LINK)malloc(sizeof(ELEMENT));
        head->d = *s;
        head->next = helper(s+1,head);
        head->previous = prev;
        return head;
    }
}
LINK creazione_lista_bid(char *s) {
    return helper(s,NULL);
}
int main(int argc, char *argv[]) {
    LINK a;
    char temp, temp2;
    a = creazione_lista_bid("1234");
    temp = a -> next -> next -> d;
    temp2 = a -> next -> next -> previous -> d;
    printf("%c\n", temp);
    printf("%c\n", temp2);
    system("PAUSE");
    return 0;
}
ciao.

        head -> previous = a[i];
Tolta la chiamata ricorsiva, il risultato di questo codice è
head->previous = a[1] = temp1 = (dati non inizializzati).
Indovina cosa succede quando tenti di dereferenziare head->previous, che
punta ad un indirizzo di memoria sconosciuto? ;-)
Prova a usare qualche printf() per mostrare cosa succede durante
l'esecuzione, così da avere un'idea del punto preciso e del motivo per cui
va in crash o smette di funzionare correttamente. Ad esempio:
 a = creazione_lista_bid("casa");
 printf("a->next = %p\n", a->next);
 printf("a->next->next = %p\n", a->next->next);
 temp = a -> next -> next -> d;
 printf("%c\n", temp);
 printf("a->next->next->previous = %p\n", a->next->next->previous);
 temp2 = a -> next -> next -> previous -> d;
 printf("%c\n", temp2);
 return 0;

l'idea che avevo in mente era di questo tipo:
http://img388.imageshack.us/my.php?...immagine0nu.jpg
ho realizzato una versione iterativa, ma ho un porblema cn rear...cioè 
nel mani nn so cm usarlo, crearlo ecc...e cm fare perchè, a una 
variabile LINK, che nel mio caso è a, gli vengano passati due valori, 
head e rear.
ecco la versione iterativa:
#include <stdio.h>
#include <stdlib.h>
typedef char DATA;
struct linked_list {
DATA d;
struct linked_list *next;
struct linked_list *previous;
};
typedef struct linked_list ELEMENT;
typedef ELEMENT *LINK;
LINK creazione_lista_bid(char s[])
{
LINK head = NULL, rear , tail, prev;
int i;
if (s[0] != '\0') /*primo elemento*/
{
head = malloc(sizeof(ELEMENT));
head -> d = s[0];
head -> previous = NULL;
tail = head;
/*aggiungi in coda*/
for (i = 1; s[i] != '\0'; ++i)
{
tail -> next = malloc(sizeof(ELEMENT));
prev = tail;
tail = tail -> next;
tail -> d = s[i];
tail -> previous = prev;
}
tail -> next = NULL;
rear = tail;
}
return head;
}
int main(int argc, char *argv[])
{
LINK a, b;
int temp, temp2;
a = creazione_lista_bid("casa");
/*controllo i valori*/
temp = a -> next -> d;
temp2 = a -> next -> next -> next -> previous -> d;
printf("%c\n", temp);
printf("%c\n", temp2);
system("PAUSE");
return 0;
}
grazie infinite x la pazienza!!! :D


 head e rear.
non è che si capisca molto cosa intendi. provo ad interpretare: vorresti 
usare la variabile rear in main per accedere agli elementi della lista 
partendo dall'ultimo?
puoi fare in vari modi, ad esempio:
1. potresti far restituire da creazione_lista_bid() una struttura 
contenete due campi LINK (head e rear) e poi assegnare i due campi a 2 
variabili LINK in main o accedere direttamente ad essi;
2. dichiari una variabile LINK in main (rear) e potresti passare un 
puntatore a LINK come parametro aggiuntivo a creazione_lista_bid(). in 
questo modo puoi modificare a cosa punta rear all'interno della funzione;
3. potresti usare delle variabili globali;
4. boh? ecc... :)
ciao.
p.s. ma la versione ricorsiva faceva schifo? :)

nn era completa la prima versione che ho postato....e l'ho rifatta nel 
modo iterativo, che mi risulta più semplice.....
cmq questo è il link della foto:
http://img388.imageshack.us/my.php?image=immagine0nu.jpg
funziona ora..hehe....cosi capisci meglio cosa cerco di fare...
alla fine head rappresenta la "testa" della lista...e rear la 
"fine"...voglio vare in modo che si possa accedere alla lista sia dalla 
fine che dall'inizio...usando next per andare anvanti e previous per 
tornare indietro. Ecco cosa vevo pensato, seguendo anche il tuo 
suggerimento, e infatti cosi funziona.....solo che mi daresti un altro 
aiuto x creare la versione ricorsiva di questa?? ti ringrazio!!!
#include <stdio.h>
#include <stdlib.h>
typedef char DATA;
struct linked_list {
    DATA d;
    struct linked_list *next;
    struct linked_list *previous;
};
typedef struct linked_list ELEMENT;
typedef ELEMENT *LINK;
LINK creazione_lista_bid(char s[], LINK *rear)
{
    LINK head = NULL, tail, prev;
    int i;
    if (s[0] != '\0')  /*primo elemento*/
    {
        head = malloc(sizeof(ELEMENT));
        head -> d = s[0];
        head -> previous = NULL;
        tail = head;
        /*aggiungi in coda*/
        for (i = 1; s[i] != '\0'; ++i)
        {
            tail -> next = malloc(sizeof(ELEMENT));
            prev = tail;
            tail = tail -> next;
            tail -> d = s[i];
            tail -> previous = prev;
        }
        tail -> next = NULL;
        *rear = tail;
    }
    return head;
}
int main(int argc, char *argv[])
{
  LINK a, *pp, rear;
  int temp, temp2, temp3;
  pp = &rear;
 a = creazione_lista_bid("casa", pp);
 temp = a -> next ->  d;
 temp2 = a -> next -> next -> next -> previous -> d;
 temp3 = rear -> previous -> previous -> d;
 printf("%c\n", temp);
 printf("%c\n", temp2);
 printf("%c\n", temp3);
  system("PAUSE");
  return 0;
}
-- 


 aiuto x creare la versione ricorsiva di questa?? ti ringrazio!!!
la butto lì, ti conviene verificare però:
#include <stdio.h>
#include <stdlib.h>
typedef char DATA;
struct linked_list {
    DATA d;
    struct linked_list *next;
    struct linked_list *previous;
};
typedef struct linked_list ELEMENT;
typedef ELEMENT *LINK;
LINK helper(char *s, LINK prev, LINK * rear)
{
    LINK head;
    if (*s == '\0') {
       *rear = prev;
       return NULL;
    }
    else {
       head = (LINK) malloc(sizeof(ELEMENT));
       head->d = *s;
       head->next = helper(s + 1, head, rear);
       head->previous = prev;
       return head;
    }
}
LINK creazione_lista_bid(char *s, LINK * rear)
{
    return helper(s, NULL, rear);
}
int main(int argc, char *argv[])
{
    LINK a, *pp, rear;
    int temp, temp2, temp3;
    pp = &rear;
    a = creazione_lista_bid("1234", pp);
    temp = a->next->d;
    temp2 = a->next->next->next->previous->d;
    temp3 = rear->previous->previous->d;
    printf("%c\n", temp);
    printf("%c\n", temp2);
    printf("%c\n", temp3);
    system("PAUSE");
    return 0;
}
ciao.

 la butto lì, ti conviene verificare però:
[...]
Sì, funziona perfettamente. Ho usato il seguente codice di test, così potete
verificarlo anche voi:
void test_lista(LINK head, LINK rear)
{
   LINK p;
   for (p = head; p != NULL; p = p->next)
      printf("'%c' ", p->d);
   putchar('\n');
   for (p = rear; p != NULL; p = p->previous)
      printf("'%c' ", p->d);
   putchar('\n');
}