Problema con inserimento in lista doppiamente concatenata

sekupo

il 25 mag 2020, 11:05

24 risposte

24 Risposte - Pagina 2

sekupo

Pochi posts

Iscritto da: mag, 2020

Messaggi:: 26

Re: Problema con inserimento in lista doppiamente concatenata

26 mag 2020, 11:15

Provo a rifare il ciclo while del codice di prima aggiungendo i dati relativi al link prev(ps: ho aggiunto count per tenere traccia del numero di nodi):

void insert(list *l, int value)
{
	
    node *nuovo = (node*)malloc(sizeof(node));

    if(nuovo)
	{
		nuovo->data = value;
		nuovo->next = NULL;
		if(l->count == 0)
		{
			nuovo->prev = NULL;
			l->head = l->tail = nuovo;
			
			
		}
		else
		{
			while(l->head && value > l->head->data)
			{
				l->head = l->head->next;
			}
			    nuovo->next = l->head;
				l->head = nuovo;
				nuovo->prev = nuovo->next->prev;
				nuovo->next->prev = l->head;
				
		}
	}
	else{
		puts("Memoria non disponibile.");
	}
}

S
sekupo
Pochi posts
Iscritto da
mag, 2020
Messaggi:
26
Re: Problema con inserimento in lista doppiamente concatenata
26 mag 2020, 12:40
Dopo aver inserito il primo nodo mi trovo nella situazione in cui sia l->head che l->tail è lo stesso. Se volessi fare l'inserimento in ordine dovrei scorrere la lista finché il dato del nodo che voglio inserire sia minore di quello del nodo considerato.
nel momento che lo trovo faccio queste operazioni:
```
nuovo->prev = l->head->prev;//link al nodo precedente di quello in cui mi trovo
l->tail->prev = nuovo;//il nodo alla coda è più grande di quello che sto inserendo
nuovo->next = l->tail;//il successivo del nuovo nodo è appunto la coda
```
però non mi sembra qualcosa che si risolve con queste istruzioni perché non vale per tutti i casi, cioè è lo stesso problema che c'era prima.
Nippolo
Molto attivo
Iscritto da
mar, 2018
Messaggi:
1241
Re: Problema con inserimento in lista doppiamente concatenata
26 mag 2020, 23:21
In effetti non è semplicissimo!

Cmq ci ho riflettuto un po' e sono riuscito ad implementare la funzione (e senza aggiungere ulteriori membri alla struct list).
L'impostazione generale è la seguente:
```
void insert(list *l, int value)
{
    node *nuovo = (node*)malloc(sizeof(node));
    if(nuovo)
    {
	nuovo->data = value;
	node *temp = l->head;
	while(temp && value > temp->data)
        {
            temp = temp->next;
        }
       ...
    }
}
```
ovviamente ho omesso la parte relativa ai vari collegamenti.

Il mio approccio è stato quello di schematizzare tutti i casi possibili (ne ho contati 4):
1) aggiunta in testa in lista non vuota;
2) aggiunta in coda in lista non vuota;
3) aggiunta tra due nodi;
4) aggiunta in lista vuota.

Analizzandoli sono poi riuscito a ricavare uno schema generale valido per tutti e 4 i casi.
In pratica:
- inizio dall'assegnazione di nuovo->prev che varia in base al valore di temp (NULL o !NULL);
- a questo punto se nuovo->prev punta ad un nodo, bisognerà anche collegare quel nodo a nuovo;
- passo poi all'assegnazione di nuovo->next che è sempre la stessa in ogni caso;
- a questo punto se nuovo->next punta ad un nodo, bisognerà anche collegare quel nodo a nuovo, altrimenti (ossia nel caso in cui nuovo->next punti a NULL) bisognerà aggiornare la coda della lista (il membro tail in pratica);
- infine se occorre bisognerà aggiornare anche la testa della lista (ossia il membro head).
S
sekupo
Pochi posts
Iscritto da
mag, 2020
Messaggi:
26
Re: Problema con inserimento in lista doppiamente concatenata
27 mag 2020, 07:34
Alla fine l'unica cosa a cui sono arrivato pure io è stata pure quella del nodo tempo proprio perché la testa sarebbe dovuta rimanere fissa, ma il resto era un continuo crash del programma... Comunque grazie ancora per l'aiuto che stai dando, dovrò continuare a sbatterci la testa finché non mi sarò fatto un' immagine mentale chiara.
S
sekupo
Pochi posts
Iscritto da
mag, 2020
Messaggi:
26
Re: Problema con inserimento in lista doppiamente concatenata
27 mag 2020, 09:47
So che ancora non è finito però vorrei sapere se la strada è quella giusta, dato che a prima vista non sembra un'implementazione così elegante e compatta:
```
void insert(list* l, int value)
{
	node* nuovo = (node*)malloc(sizeof(node));
	if(nuovo)
	{
		nuovo->data = value;
		node* temp = l->head;
		while(temp && value > temp->data)
		{
			temp = temp->next;
		}
		if(temp)
		{
			if(!temp->next)//sono arrivato alla fine della lista: temp = coda
			{
				if(!temp->prev)//la testa e la coda coincidono in un unico nodo
				{    //inserimento in testa
					nuovo->prev = NULL;
					nuovo->next = l->tail;
					l->head->prev = nuovo;
					l->head = nuovo;
				}
				
				   //ci sono nodi prima della coda;
				    nuovo->prev = l->tail->prev;
					l->tail->prev->next = nuovo;
					nuovo->next = l->tail;
					l->tail->prev = nuovo;
			}
			else
			{//non sono arrivato alla fine della lista
				    nuovo->prev = temp->prev;
					temp->prev->next = nuovo;
					nuovo->next = temp;
					temp->prev = nuovo;
			}
			
		}
		
	    
	}
}
```
quindi la situazione è questa:
c'è solo un nodo ed io sto inserendo un elemento più piccolo del valore di questo;
ho trovato un valore più grande ma temp è adesso la coda, quindi sostituisco l->tail->prev(che non coincide con la testa) con il nuovo nodo;
ho trovato un valore più piccolo ma temp è un generico nodo della lista, ma non dovendo aggiornare la coda, le istruzioni sono le stesse di prima.
adesso dovrebbe esserci la condizione (!temp) cioè che sono arrivato a NULL senza trovare nessun data minore del value,quindi, devo inizializzare la lista con head e tail a NULL. Manchebbe solo il caso dovrei aggiornare la testa per inseire un value più piccolo.
Nippolo
Molto attivo
Iscritto da
mar, 2018
Messaggi:
1241
Re: Problema con inserimento in lista doppiamente concatenata
27 mag 2020, 12:43
Guarda che non c'è bisogno di separare caso per caso, in quanto essi presentano alcuni passaggi in comune.
Ad ogni modo ecco i 4 casi descritti nel mio precedente post:

Ora prova ad applicare la seguente procedura:
Nippolo ha scritto:
- inizio dall'assegnazione di nuovo->prev che varia in base al valore di temp (NULL o !NULL);
- a questo punto se nuovo->prev punta ad un nodo, bisognerà anche collegare quel nodo a nuovo;
- passo poi all'assegnazione di nuovo->next che è sempre la stessa in ogni caso;
- a questo punto se nuovo->next punta ad un nodo, bisognerà anche collegare quel nodo a nuovo, altrimenti (ossia nel caso in cui nuovo->next punti a NULL) bisognerà aggiornare la coda della lista (il membro tail in pratica);
- infine se occorre bisognerà aggiornare anche la testa della lista (ossia il membro head).
ad ogni caso e ti renderai conto che risulta sufficiente. A quel punto non ti resta che tradurla in codice.

sekupo

Pochi posts

Iscritto da: mag, 2020

Messaggi:: 26

Re: Problema con inserimento in lista doppiamente concatenata

27 mag 2020, 14:11

Così dovrebbe essere anche ordinato

 void insert(list* l, int value)
{
	node* nuovo = (node*)malloc(sizeof(node));
	if(nuovo)
	{
		nuovo->data = value;
		node* temp = l->head;
		while(temp && value > temp->data)
		{
			temp = temp->next;
		}
		if(temp)
		{
			if(!temp->prev)
			{
			nuovo->prev = NULL;
			nuovo->next = temp;
			temp->prev = nuovo;
			l->head = nuovo;
			}
			else
			{
			nuovo->prev = temp->prev;
			temp->prev->next = nuovo;
			nuovo->next = temp;
			temp->prev = nuovo;
			}
		}
		else
		{
			if(l->tail)
			{
			nuovo->prev = l->tail;
			l->tail->next = nuovo;
			nuovo->next = NULL;
			l->tail = nuovo;
			}
			else
			{
				nuovo->prev = nuovo->next = NULL;
				l->head = l->tail = nuovo;
			}
		}	    
	}
	else
	{
	puts("memoria non disponibile");
	}
}

Nippolo

Molto attivo

Iscritto da: mar, 2018

Messaggi:: 1241

Re: Problema con inserimento in lista doppiamente concatenata

27 mag 2020, 18:07

Praticamente hai separato i vari casi, in particolare i 4 blocchi di istruzioni si riferiscono rispettivamente ai casi 1), 3), 2) e 4).
Magari risulta un po' ridondante, ma mi sembra corretto!

Se ti può essere utile ecco il codice a cui avevo pensato:

void insert(list *l, int value)
{
    node *nuovo = (node*)malloc(sizeof(node));
    if(nuovo)
    {
	nuovo->data = value;
	node *temp = l->head;
	while(temp && value > temp->data)
        {
            temp = temp->next;
        }
        if(nuovo->prev = temp ? temp->prev : l->tail)
        {
            nuovo->prev->next = nuovo;
        }
        if(nuovo->next = temp)
        {
            temp->prev = nuovo;
        }
        else
        {
            l->tail = nuovo;
        }
        if(l->head == temp)
        {
            l->head = nuovo;
        }
    }
}

S
sekupo
Pochi posts
Iscritto da
mag, 2020
Messaggi:
26
Re: Problema con inserimento in lista doppiamente concatenata
27 mag 2020, 18:35
Eh si, ancora non ho acquisito la somma arte della sintesi . Comunque ti ringrazio veramente tanto per l'aiuto e per essermi stato dietro; cercherò di sbatterci ancora di più la testa .
Nippolo
Molto attivo
Iscritto da
mar, 2018
Messaggi:
1241
Re: Problema con inserimento in lista doppiamente concatenata
27 mag 2020, 19:48
Di niente!

Devi accedere o registrarti per scrivere nel forum

24 risposte