C, liste doppiamente collegate

davide.fruci

il 25 giu 2014, 18:06

35 risposte

davide.fruci

Utente Attivo

Iscritto da: mar, 2014

Messaggi:: 279

C, liste doppiamente collegate

25 giu 2014, 18:22

Sto studiando le liste doppiamente collegate.

Finora ho scritto l'inserimento in testa, questo:

#include <stdio.h>
#include <stdlib.h>

struct ElemListaDoppia{
	int info;
	struct ElemListaDoppia* next;
	struct ElemListaDoppia* prev;
};
typedef struct ElemListaDoppia TipoNodoListaDoppia;

struct RecordListaDoppia{
	
	TipoNodoListaDoppia* first;
	TipoNodoListaDoppia* last;
};
typedef struct RecordListaDoppia TipoListaDoppia;

void addTestaLista(TipoListaDoppia * lis, int e);

int main()
{
	TipoListaDoppia lista, print;
	int i;
	for(i = 0; i < 5; i++)
		addTestaLista(&lista, i);
}

void addTestaLista(TipoListaDoppia * lis, int e)
{
	
	TipoNodoListaDoppia* aux = (TipoNodoListaDoppia*)malloc(sizeof(TipoNodoListaDoppia));
	aux -> info = e;
	if (lis == NULL)
	{
		aux -> prev = NULL;
		aux -> next = NULL;
		lis -> first = aux;
		lis -> last = aux;
		return;
	}
	aux -> prev = NULL;
	aux -> next = lis -> first;
	lis -> first -> prev = aux;
	lis -> first = aux;
}

Ora vorrei stampare la lista ma non ci riesco.

Nel main ho fatto inserito cosa qui:

TipoListaDoppia temp = lista;
stampa(&temp);

E nella funzione stampa:


void stampa(TipoNodoListaDoppia *lis)
{
	if(lis == NULL)
		return;
	
	stampa(lis -> first -> next);
	printf("-> %d", lis->first->info);
	
}

Giustamente il compilatore mi dice:

ldc.c: In function ‘main’:
ldc.c:41:2: warning: passing argument 1 of ‘stampa’ from incompatible pointer type [enabled by default]
stampa(&print);
^
ldc.c:31:6: note: expected ‘struct TipoNodoListaDoppia *’ but argument is of type ‘struct TipoListaDoppia *’
void stampa(TipoNodoListaDoppia *lis);
^
ldc.c: In function ‘stampa’:
ldc.c:68:13: error: ‘TipoNodoListaDoppia’ has no member named ‘first’
stampa(lis -> first -> next);
^
ldc.c:69:21: error: ‘TipoNodoListaDoppia’ has no member named ‘first’
printf("-> %d", lis->first->info);

Come faccio a stampare?

35 Risposte

C
candaluar
Molto attivo
Iscritto da
ago, 2013
Messaggi:
1900
Re: C, liste doppiamente collegate
26 giu 2014, 10:43
Giustamente il compilatore mi dice:
...intanto allora metti a posto i warnings e gli errori
```
   if (lis == NULL)
   {
      aux -> prev = NULL;
      aux -> next = NULL;
      lis -> first = aux;
      lis -> last = aux;
```
se lis è NULL come puoi usare lis->first e lis->last?
davide.fruci
Utente Attivo
Iscritto da
mar, 2014
Messaggi:
279
Re: C, liste doppiamente collegate
26 giu 2014, 11:03
Ma quando è == NULL non vuol dire che la lista è vuota?
C
candaluar
Molto attivo
Iscritto da
ago, 2013
Messaggi:
1900
Re: C, liste doppiamente collegate
26 giu 2014, 11:08
Quello che vuol dire lis==NULL lo decidi tu
Quello che è certo, invece, è che un puntatore che punta a NULL (ovvero a niente di valido) non lo puoi utilizzare!
davide.fruci
Utente Attivo
Iscritto da
mar, 2014
Messaggi:
279
Re: C, liste doppiamente collegate
26 giu 2014, 11:36
Quindi come la risolvo questa cosa?
Quando la lista è vuota vorrei che la struttura che ci inserisco puntasse a NULL sia per next che per prev..

A parte questo, come stampo?

Nel caso di una lista lineare ero abituato a fare:
```
TipoSCL lista, aux;

//Carico lista
..
....

aux = lista;

while(aux != NULL)
{
       printf("aux -> info: %d", aux -> info);
       aux = aux -> next;
}
```
Con le liste doppie non ho capito come fare..
C
candaluar
Molto attivo
Iscritto da
ago, 2013
Messaggi:
1900
Re: C, liste doppiamente collegate
26 giu 2014, 11:39
Devi fare la stessa cosa!

davide.fruci

Utente Attivo

Iscritto da: mar, 2014

Messaggi:: 279

Re: C, liste doppiamente collegate

26 giu 2014, 12:04

Nel dispensa del mio corso:

void addTestaLista(TipoListaDoppia *lis, TipoInfo e)
{
    if (lis == NULL)
    { 
         printf ("ERRORE: lis non e’ una lista valida"); 
         exit(1);
    }
    TipoNodoListaDoppia* aux = (TipoNodoListaDoppia*) malloc(sizeof(TipoNodoListaDoppia));
    aux -> info = e;
    if (emptyLista(*lis))
    {
        aux -> prev = NULL;
        aux -> next = NULL;
        lis -> first = aux;
        lis -> last = aux
    }

ma emptyLista non c'è nella dispensa.. Che cosa fa?

C
candaluar
Molto attivo
Iscritto da
ago, 2013
Messaggi:
1900
Re: C, liste doppiamente collegate
26 giu 2014, 12:40
Basta che ci ragioni solo un attimo.
emptyLista() riceve in input un TipoListaDoppia (perchè lis è un puntatore a TipoListaDoppia e li vediamo che viene passato *lis); TipoListaDoppia non è altro che questa struttura
```
struct RecordListaDoppia{
   
   TipoNodoListaDoppia* first;
   TipoNodoListaDoppia* last;
};
```
a questo punto è semplice capire come si intende testare che la lista sia vuota
davide.fruci
Utente Attivo
Iscritto da
mar, 2014
Messaggi:
279
Re: C, liste doppiamente collegate
26 giu 2014, 12:46
Ovvero che first e last puntano a NULL?
C
candaluar
Molto attivo
Iscritto da
ago, 2013
Messaggi:
1900
Re: C, liste doppiamente collegate
26 giu 2014, 12:54
Esatto.
Ti consiglio caldamente di fare un "disegno" delle strutture che sono in gioco e di cercare di capire "su carta" come funziona, ancor prima di buttare giù in pseudocodice le operazioni principali; la codifica è solo ultimo passo.
davide.fruci
Utente Attivo
Iscritto da
mar, 2014
Messaggi:
279
Re: C, liste doppiamente collegate
26 giu 2014, 12:57
Ok..

Comunque io la stampa l'ho fatta così:

nel main chiamo:

stampa(&lista);

e
```
void stampa(TipoListaDoppia *lis)
{
	while(lis != NULL)
	{
		printf("%d -> ", lis -> first -> info);
		lis -> first = lis -> first -> next;
	}
}
```
Ma mi da Errore di segmentazione (core dump creato)..
C
candaluar
Molto attivo
Iscritto da
ago, 2013
Messaggi:
1900
Re: C, liste doppiamente collegate
26 giu 2014, 13:05
Quello che hai scritto denota che non hai capito la struttura (while(lis != NULL) non ha senso!): TipoListaDoppia è una cosa mentre i TipoNodoListaDoppia sono un'altra.
Davvero, fatti un bel disegno della struttura; non è con i tentativi che ce la farai, e se proprio vuoi andare avanti con i tentativi allora almeno correggi i warning che sicuramente ti vengono segnalati!
davide.fruci
Utente Attivo
Iscritto da
mar, 2014
Messaggi:
279
Re: C, liste doppiamente collegate
26 giu 2014, 13:08
Ma con le liste lineari ho sempre fatto così.. Anche tu hai detto che è la stessa cosa
C
candaluar
Molto attivo
Iscritto da
ago, 2013
Messaggi:
1900
Re: C, liste doppiamente collegate
26 giu 2014, 13:11
Infatti devi seguire lo stesso procedimento, ma non puoi utilizzare i puntatori a casaccio come stai facendo adesso
Dai, su, prendi carta e penna!!! Buon lavoro
davide.fruci
Utente Attivo
Iscritto da
mar, 2014
Messaggi:
279
Re: C, liste doppiamente collegate
26 giu 2014, 13:32
La struttura ce l'ho ben stampata in mente, è da ieri sera che sto facendo disegni

La struttura è tipo questa

Dove quei due pallini in basso, dai quali partono le frecce curve sarebbero la struttura che contiene first e last.

L'unico problema ce l'ho con la stampa..

Nel mio es ho fatto un inserimento in testa della lista da 0 a 4.
```
void stampa(TipoListaDoppia *lis)
{	
     printf("%d -> ", lis -> first -> info);
     lis -> first = lis -> first -> next;
     printf("%d -> ", lis -> first -> info);
}
```
Infatti eseguendo la funzione sopra mi stampa:

4 -> 3 -> che è giusto, dato che l'inserimento è in testa.

Sbaglio la condizione del ciclo, ovvero:
```
void stampa(TipoListaDoppia *lis)
{	
	while(lis->first->next != NULL)
	{
		printf("%d -> ", lis -> first -> info);
		lis -> first = lis -> first -> next;
	}
}
```
A me la condizione sembra giusta guardando il disegno..

Devi accedere o registrarti per scrivere nel forum

35 risposte