[C] liste

[ricky_86]

ciao, ho da fare come esercizio una lista particolare

typedef struct nd{
int val;
int nd *next;
int nd *max;
}TLISTA;

inserisci nella lista lInt i valori contenuti in vettInt facendo puntare un elemento al successivo attraverso il campo next ed utilizzando il campo max per far puntare ogni elemento della lista ad un altro elemento secondo il seguente criterio:

per ogni elemento x di lInt, max punta all'elemento di lInt che contiene il valore massimo tra tutti gli elementi lInt che precedono l'elemento x, elemento x incluso.
Quindi max del primo elemento di lInt punta all'elemento stesso; max del secondo elementodi lInt punta al più grande tra il primo e il secondo elemento di l'Int; max del terzo elemento di lInt punta al più grande tra il 1°, il 2° e il 3° elemento di lInt e così via.


dopo aver dichiarato lint di tipo TLISTA e int vettInt[VETTINT] nel main ho provato a fare questa funzione

TLISTA *insertlista(TLISTA *l, int v){
TLISTA *t=(TLISTA*) malloc(sizeof(TLISTA));

if (t!=NULL){
t->val=v;
t->next=l;
t->max=l;
if (t->next > t->max) t->max=l;
return t;
}
else return l;
}

ha senso questa cosa che ho scritto ????
per quanto riguarda il campo next penso sia giusto ma col campo max non ho molte idee...

[Vincenzo1968]

Occhio che ci sono diversi errori a partire dalla dichiarazione della struttura. Non va dichiarata così:

typedef struct nd{
int val;
int nd *next;
int nd *max;
}TLISTA;

ma così:

typedef struct nd
{
	int val;
	struct nd *next;
	struct nd *max;
}TLISTA;

Per gestire il puntatore al nodo che contiene il valore massimo è sufficiente creare un nodo temporaneo(inizializzato col valore del primo nodo della lista) e confrontarlo, mentre si scorre la lista per l'inserimento, con i valori di ogni nodo:

#include <stdio.h>
#include <malloc.h>

typedef struct nd
{
	int val;
	struct nd *next;
	struct nd *max;
}TLISTA; 

TLISTA* NewNode(int val)
{
	TLISTA *n;

	n = (TLISTA*)malloc(sizeof(TLISTA));
	if( !n )
		return NULL;

	n->val = val;
	n->next = NULL;
	n->max = NULL;

	return n;
}

TLISTA* insertlista(TLISTA* first, int val)
{	
	TLISTA *n = first, *nuovo, *maxnode;

	if ( first == NULL )
	{
		nuovo = NewNode(val);
		nuovo->max = nuovo;
		return nuovo;
	}

	n = first;
	maxnode = first->max;
	while( n->next != NULL )
	{
		n = n->next;
		if ( n->val > maxnode->val )
			maxnode = n;
	}

	nuovo = NewNode(val);
	n->next = nuovo;
	if ( val > maxnode->val )
		maxnode = nuovo;
	nuovo->max = maxnode;

	return first;
}

void freelista(TLISTA* first)
{
	TLISTA *n1 = first, *n2;
	while ( n1 != NULL )
	{
		n2 = n1->next;
		free(n1);
		n1 = n2;
	}
}

void printlista(TLISTA *first)
{
	TLISTA *n = first;

	while( n != NULL )
	{
		printf("val -> %d, max -> %d\n", n->val, n->max->val);
		n = n->next;
	}
}

int main()
{
	TLISTA* lint = NULL;
	int vettInt[10] = {5,8,3,2,1,21,55,89,144,13};
	int k;

	for (k = 0; k < 10; k++)
	{
		lint = insertlista(lint, vettInt[k]);
	}

	printf("\n");
	printlista(lint);
	printf("\n");

	freelista(lint);

	return 0;
}

Il codice sopra produce il seguente output:

val -> 5, max -> 5
val -> 8, max -> 8
val -> 3, max -> 8
val -> 2, max -> 8
val -> 1, max -> 8
val -> 21, max -> 21
val -> 55, max -> 55
val -> 89, max -> 89
val -> 144, max -> 144
val -> 13, max -> 144

[Kenger]

Ad ogni inserimento basterebbe confrontare il valore all'interno del nuovo nodo e il valore all'interno dell'ultimo nodo della lista o sbaglio?
Certo, senza un puntatore alla coda della lista te la devi scorrere tutta lo stesso, ma con il puntatore sarebbe un bel miglioramento ^^

[Vincenzo1968]

Originariamente inviato da Kenger

Ad ogni inserimento basterebbe confrontare il valore all'interno del nuovo nodo e il valore all'interno dell'ultimo nodo della lista o sbaglio?
Certo, senza un puntatore alla coda della lista te la devi scorrere tutta lo stesso, ma con il puntatore sarebbe un bel miglioramento ^^

Effettivamente, mantenendo un puntatore all'ultimo nodo, la procedura per l'inserimento è più efficiente:

#include <stdio.h>
#include <malloc.h>

typedef struct nd
{
	int val;
	struct nd *next;
	struct nd *max;
}TLISTA; 

typedef struct tagLista
{
	TLISTA *first;
	TLISTA *last;
} Lista;

TLISTA* NewNode(int val)
{
	TLISTA *n;

	n = (TLISTA*)malloc(sizeof(TLISTA));
	if( !n )
	{
		printf("Memoria insufficiente.\n");
		return NULL;
	}

	n->val = val;
	n->next = NULL;
	n->max = NULL;

	return n;
}

void insertlista(Lista *lista, int val)
{	
	TLISTA *nuovo;

	if ( lista->first == NULL )
	{
		nuovo = NewNode(val);
		nuovo->max = nuovo;
		lista->first = lista->last = nuovo;
		return;
	}

	nuovo = NewNode(val);
	if ( val > lista->last->val )
		nuovo->max = nuovo;
	else
		nuovo->max = lista->last->max;

	lista->last->next = nuovo;
	lista->last = nuovo;
}

void freelista(Lista* lista)
{
	TLISTA *n1 = lista->first, *n2;
	while ( n1 != NULL )
	{
		n2 = n1->next;
		free(n1);
		n1 = n2;
	}
}

void printlista(Lista *lista)
{
	TLISTA *n = lista->first;

	while( n != NULL )
	{
		printf("val -> %d, max -> %d\n", n->val, n->max->val);
		n = n->next;
	}
}

int main()
{
	Lista lint;

	int vettInt[10] = {5,8,3,2,1,21,55,89,144,13};
	int k;

	for (k = 0; k < 10; k++)
	{
		insertlista(&lint, vettInt[k]);
	}

	printf("\n");
	printlista(&lint);
	printf("\n");

	freelista(&lint);

	return 0;
}

[Kenger]

Esattamente quello che intendevo anche se temo che stiamo solo complicando la vita al thread starter