Urgente aiut liste circolari funzioni ricorsive

ANNARELLA

il 05 apr 2010, 10:04

7 risposte

ANNARELLA

Pochi posts

Iscritto da: mar, 2009

Messaggi:: 20

Urgente aiut liste circolari funzioni ricorsive

05 apr 2010, 10:39

Buongiorno a tutti...ho appena eseguito questi due esercizi: scrivere delle funzioni iterative che eseguono rispettivamnete l'inserimento e la cancellazione di un nodo in una lista circolare senza usare il doppio puntamento e che prevedano tutti i casi limite( lista nulla, inserimento coda, testa ecc...)...il mio problema è ora la loro trasformazione in funzioni ricorsive
Qualcuno può aiutarmi??? Ripeto nn sonouna programmatrice ma a lavoro mi servonoqueste cose...baci a tutti

CANCELLAZIONE NODO IN LISTA CIRCOLARE

Struct nodo * cancella(struct nodo * lista, int elemento)
{
Struct nodo *q=lista; //cursore di spostamento inizializzato a lista
Prev=lista;
if(lista ==NULL) //la lista è vuota non devo cancellare nulla
{
return NULL;
{
if(prev->elemento==elemento && prev->next!=lista) //se il primo elemento è quello da cancellare lo scambio con il secondo cosi lo tratto come il caso generale di cancellazione in “mezzo”
{
appoggio=q->next->elemento;
q->next->element=prev->elemento;
prev->element o= appoggio;
{
Do
{ q=q->next;
if(q->elemento ==elemento)
{
if(prev==q)// caso in cui la lista ha un solo elemento
free(q);
return NULL;
}else {
prev->next=q->next;
free(q);
}prev=q;
}while(q!=lista)
return lista;
}

INSERIMENTO NODO IN LISTA CIRCOLARE
Struct nodo * cancella(struct nodo * lista, int elemento)
{
Struct nodo * q=lista;
Struct nodo *Nuovo=malloc(sizeof(struct nodo));
Nuovo->elemento=elemento;

if(lista ==NULL) //la lista è vuota
{
Lista =Nuovo;
Nuovo->next=lista;
}else{
if(lista>elemento>Nuovo->elemento)
{
appoggio=Nuovo->elemento;
Nuovo->elemento=lista->elemento;
lista->element o= appoggio;
}
while(q->elemento <Nuovo->elemento)
{ q=q->next;
}
if(nodo->next!=lista)
{Nuovo->next=q->next;
q->next=Nuovo;
}else{
q->next=Nuovo;
Nuovo->next=lista;
}
return lista;
}

7 Risposte

A
ANNARELLA
Pochi posts
Iscritto da
mar, 2009
Messaggi:
20
Re: Urgente aiut liste circolari funzioni ricorsive
06 apr 2010, 09:10
Uffa non ci capiscopiù nulla...per trasformare queste funzioni in ricorsive dovrei farmi restituire anche l'ultimo nodo dato che punta per definizione di lista circolare al prmo???? qualcuno mi illumini
O
Overflow
Utente Attivo
Iscritto da
gen, 2008
Messaggi:
222
Re: Urgente aiut liste circolari funzioni ricorsive
06 apr 2010, 13:55
Ciao, hai parlato di "lista circolare senza usare il doppio puntamento" significa che c'è solo il puntatore all'elemento successo e non a quello precedente?
Scrivi come è composta la struttura nodo, perchè ho visto che utilizzi lista->prev quindi c'è il puntatore all'elemento precedente.
A
ANNARELLA
Pochi posts
Iscritto da
mar, 2009
Messaggi:
20
Re: Urgente aiut liste circolari funzioni ricorsive
06 apr 2010, 17:40
Ciao,
si ogni nodo della lista contiene solo due campi

quello che contiene l'elemento e quello che contiene il puntatore al successivo nodo.Il problema della ricorsione è per me la stessa definizione di lista circolare ossia che il puntatore dell'ultimo nodo "punta"al primo nodo della lisat (scusa il gioco di parole)

struct nodo {
int elemento;
struct elemento *next;
}

Overflow

Utente Attivo

Iscritto da: gen, 2008

Messaggi:: 222

Re: Urgente aiut liste circolari funzioni ricorsive

06 apr 2010, 18:32

Ciao, io ho scritto qualcosina in C. Andrebbe un pò rivisto il codice.


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

struct nodo {
	int elemento;
	struct nodo* next;
	struct nodo* prev;
	struct nodo* head;	/* puntatore la testa della lista, lo utilizzo per ciclare sulla lista. */
};

struct nodo* InserisciInTesta(struct nodo* l, int el);
struct nodo* InserisciInCoda(struct nodo* l, int el);
struct nodo* Cancella(struct nodo* l, int el);
void Print(struct nodo* l);

struct nodo* AggiornaHead(struct nodo* l, struct nodo* h);
int VerificaValore(struct nodo* l, int value);

int main()
{
	struct nodo* l=NULL;
	
	l = InserisciInCoda(l,15);	
	l = InserisciInCoda(l,37);	
	l = InserisciInTesta(l,84);
	l = InserisciInCoda(l,15);
	l = InserisciInTesta(l,92);
	l = InserisciInCoda(l,108);

	l = Cancella(l,108);
	l = Cancella(l,84);
	
	Print(l);

	return 0;
}

struct nodo* InserisciInTesta(struct nodo* l, int el)
{
	/* Inserisce un nodo in testa, cioè subito dopo la testa (head)*/
	struct nodo* p;

		p = (struct nodo*) malloc(sizeof(struct nodo));
		p->elemento = el;

		if(l == NULL)
		{		
			l = p;
			l->head = l;
			l->prev = p;
			p->next =l;
			l->next = l;
			p->prev = l;
		}
		else
		{
			if (!VerificaValore(l->next ,el))
				return l;
			p->head = l->head;
			p->next = l->next;
			p->next->prev = p;
			l->next = p;
			p->prev = l;
		}

		return l;
}

struct nodo* InserisciInCoda(struct nodo* l, int el)
{
	/* Inserisci un nodo prima della testa (head)*/
	struct nodo* p;

		p = (struct nodo*) malloc(sizeof(struct nodo));
		p->elemento = el;

		if(l == NULL)
		{		
			l = p;
			l->head = l;
			l->prev = p;
			p->next =l;
			l->next = l;
			p->prev = l;
		}
		else
		{
			if (!VerificaValore(l->next ,el))
				return l;
			p->head = l->head;
			p->next = l;
			p->prev = l->prev;
			l->prev->next = p;
			l->prev = p;
		}

		return l;
}

int VerificaValore(struct nodo* l, int value)
{
	
		if (l->elemento == value)
			return 0;
		else
		{
			if(l != l->head)
				if (!VerificaValore(l->next, value))
					return 0; /* trovato un elemento con quel valore, quindi non puoi scriverci*/
		}
		

	return 1; /* non c'è nessun elemento con quel valore, puoi scrivere*/

}

struct nodo* Cancella(struct nodo* l, int el)
{
	/* Cancella un elemento */
	
	if (l != NULL)
	{
	
		if (l->elemento == el)
		{
			l->prev->next = l->next;
			l->next->prev = l->prev;
			
			if (l == l->head)
			{
				l = l->next;
				l->head = l;
				AggiornaHead(l->next,l->head);
			}
		}
		else
		{	
			 Cancella (l->next,el);
		}
	}
	return l;
}

void Print(struct nodo* l)
{
	l = l->next;
	printf("%d - ",l->elemento);
	if (l != l->head)
		Print(l);

}
struct nodo* AggiornaHead(struct nodo* l, struct nodo* h)
{
	if(l != h)
	{
		l->head = h;
		l = AggiornaHead(l->next,h);
	}
	return l;	
}

l'unico problema è che io ho utilizzato una lista a doppio puntatore. Quindi c'è un puntatore per il successivo ed uno per il precedente.
C'è inoltre un puntatore head. E' il puntatore alla testa della lista. Lo utilizzo molto per ciclare sulla lista, quindi per terminare il ciclo sulla lista. Esempio:

A - B - C - Testa - E - F - G (lista di elementi circolare) tutti hanno un puntatore a Testa, ma Testa è l'unico elemento uguale a head cioè se stesso.

A
ANNARELLA
Pochi posts
Iscritto da
mar, 2009
Messaggi:
20
Re: Urgente aiut liste circolari funzioni ricorsive
07 apr 2010, 11:35
Il problema sorge proprio quando non uso il doppio puntamento perchè ricorsivamente essendo la lista circolare perdo il controllo della lista stessa!!!Potrei getsire a parte l'iserimentoin testa o usare un contatore...boooooooooooo

Overflow

Utente Attivo

Iscritto da: gen, 2008

Messaggi:: 222

Re: Urgente aiut liste circolari funzioni ricorsive

07 apr 2010, 15:23

Ciao ti ho riscritto il codice per l'inserirmento dei dati:


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

struct nodo
{
	int elemento;
	struct nodo* next;
	struct nodo* head;
};

struct nodo* AggiungiInTesta(struct nodo* l, int el);
struct nodo* AggiungiInCoda(struct nodo* l, int el);
void Print(struct nodo* l);

int VerificaValore(struct nodo* l, int value);

int main()
{
	struct nodo* l=NULL;

	l = AggiungiInTesta(l,61);
	l = AggiungiInTesta(l,20);
	l = AggiungiInCoda(l,61);
	l = AggiungiInTesta(l,54);
	l = AggiungiInCoda(l,19);
	l = AggiungiInTesta(l,78);
	l = AggiungiInCoda(l,14);
	l = AggiungiInTesta(l,19);
	l = AggiungiInCoda(l,963);

	Print(l);

	return 0;
}

struct nodo* AggiungiInCoda(struct nodo* l, int el)
{
	struct nodo* p;
		p = (struct nodo*) malloc(sizeof(struct nodo));
		p->elemento = el;

		if (l == NULL)
		{
			l = p;
			l->next = l;
			l->head = l;
		}
		else
		{
			if (l->elemento != p->elemento)
			{
				if(l->next == l->head) /* se il prossimo elemento è la testa della lista */		
				{
					/* aggiungo l'elemento in coda */
					p->next = l->next;
					l->next = p;
					p->head = l->head;
				}
				else
					AggiungiInCoda(l->next, el);
			}
		}

		return l;
}

struct nodo* AggiungiInTesta(struct nodo* l, int el)
{
	struct nodo* p;
		p = (struct nodo*) malloc(sizeof(struct nodo));
		p->elemento = el;

	if (l==NULL)
	{
		l = p;
		l->next = l;
		l->head = l;
	}
	else
	{
		if (!VerificaValore(l->next,el))
			return l;
		p->next = l->next ;
		l->next = p;
		p->head = l->head;
	}

	return l;
}

void Print(struct nodo* l)
{
   l = l->next;
   printf("%d - ",l->elemento);
   if (l != l->head)
      Print(l);

}

int VerificaValore(struct nodo* l, int value)
{
   
      if (l->elemento == value)
         return 0;
      else
      {
         if(l != l->head)
            if (!VerificaValore(l->next, value))
               return 0; /* trovato un elemento con quel valore, quindi non puoi scriverci*/
      }
      

   return 1; /* non c'è nessun elemento con quel valore, puoi scrivere*/

}

C'è l'inserimento in Testa e in Coda.
Io per inserimento in Testa intendo subito dopo il primo dato, es:

l = AggiungiInTesta(l,61);
l = AggiungiInTesta(l,14);

l: 61 - 14

l = AggiungiInTesta(l,61);
l = AggiungiInTesta(l,14);
l = AggiungiInTesta(l,36);

l: 61 - 36 - 14

Mentre con inserimento in Coda avviene così:

l = AggiungiInCoda(l,19);
l = AggiungiInCoda(l,18);

l: 18 - 19

l = AggiungiInCoda(l,19);
l = AggiungiInCoda(l,18);
l = AggiungiInCoda(l,28);
l = AggiungiInCoda(l,39);

l: 18 - 28 - 39 - 19

Spero sia giusta la cosa.

A
ANNARELLA
Pochi posts
Iscritto da
mar, 2009
Messaggi:
20
Re: Urgente aiut liste circolari funzioni ricorsive
11 apr 2010, 12:02
Ho provato il tuo codice...funziona perfettamente ma la lista non è ordinata allora ho pensato un'altra soluzione....

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

//dichiarazioni
struct nodo
{
int elemento; //campo che contiene il valore
struct nodo* next; //campo che contiene il punt al prossimo nodo
struct nodo* startlista; // puntatore alla testa della lista
};

//function che aggiunge il nuovo nodo in testa
struct nodo* Insert(struct nodo* lista, int elemento, struct nodo * startlista);
//function che stampa la lista per intero
void stampa(struct nodo* lista);

int main()
{
//inizializzo la lista!!!
struct nodo* lista = NULL;
struct nodo * startlista = lista;

lista = Insert(lista,56,startlista);
lista = Insert(lista,11,startlista);
lista = Insert(lista,20,startlista);
lista = Insert(lista,11,startlista);
lista = Insert(lista,26,startlista);
lista = Insert(lista,14,startlista);
lista = Insert(lista,28,startlista);
lista = Insert(lista,10,startlista);
lista = Insert(lista,986,startlista);
lista = Insert(lista,164,startlista);

//stampo la lista!!!
stampa(lista);

getchar();

return 0;
}

struct nodo* Insert(struct nodo* lista, int elemento, struct nodo * startlista)
{
if(lista==NULL || lista->next==lista || lista->elemento > elemento || lista->next==startlista || (lista->next)->elemento > elemento)
{
struct nodo * nuovo= malloc(sizeof(struct nodo));
nuovo->elemento=elemento;
if(lista==NULL)
{
nuovo->next=nuovo;
return nuovo;
}

if(lista->next==lista || lista->elemento > elemento)
{
nuovo->next=lista;
lista->next=nuovo;

if(lista->elemento > elemento)
{
return nuovo;
}

return lista;
}

nuovo->next=lista->next;
lista->next=nuovo;

return startlista;

} else {

return(lista->next,elemento,startlista);

}

return 0;

}

void stampa(struct nodo* lista)
{
lista = lista->next; //altrimenti è sempre nulla!!!//
printf("%d - ",lista->elemento);
if (lista != lista->startlista)
stampa(lista);

}

solo che l'output non si ferma più a video...mi stampa la lista all'infinito!!!

Devi accedere o registrarti per scrivere nel forum

7 risposte