Linguaggio C: Liste - ValleSoftware

(Liste concatenate o liste linkate)

1. Generalità

1. Operazioni sulle liste: cancellazione e inserimento di un nodo

1. Lista concatenata circolare semplice

1. Lista concatenata doppia o bidirezionale

1. Programma C: file e lista

1.Generalità

La lista è un insieme di elementi tra loro concatenati.

Differenza, strutturale, tra array e lista.

- Array: gli elementi occupano posizioni consecutive di memoria e quindi ogni elemento, una volta noto l’indirizzo di memoria del primo elemento (nome dell’array), risulta individuato dalla sua posizione nell’array; pertanto, prima dell’uso dell’array, deve essere riservata una opportuna area di memoria per tutti gli elementi, in pratica, al momento della dichiarazione dell’array, bisogna indicare il numero massimo di elementi.

- Lista: un elemento può occupare una qualsiasi locazione della memoria disponibile; questo implica che per individuare un elemento bisogna memorizzare il suo indirizzo. D’altra parte, non essendoci alcun vincolo sulla posizione in memoria dei singoli elementi, al momento della dichiarazione della lista non bisogna riservare della memoria e quindi non è necessario conoscere quale sarà il numero massimo di elementi della lista. Le liste possono essere utilizzate con una maggiore libertà rispetto agli array, ma pagano questa libertà con una maggiore complicazione dal punto di vista degli algoritmi di gestione. Rispetto agli array:

- Vantaggi:

- Non è necessario specificare, al momento della dichiarazione, le dimensioni della lista. L’unica limitazione alle dimensioni di una lista è data dalla memoria disponibile.

- Gli inserimenti di nuovi elementi e le cancellazioni di elementi già esistenti non richiedono alcuna rielaborazione di tutto l’insieme dei dati: non bisogna fare nessuno spostamento o compattamento dei dati.

- Svantaggi:

- Per utilizzare le liste si deve ricorrere ai puntatori.

- L’accesso agli elementi di una lista può essere solo sequenziale: a partire dal primo elemento si devono scorrere tutti gli elementi fino a quando non si arriva all’elemento cercato.

Nei linguaggi di programmazione più evoluti del C, l’utilizzo dei puntatori e la ricerca sequenziale sono “nascosti”, nel senso che il programmatore si limita a richiamare delle funzioni che gli permettono di gestire le liste senza ricorrere ai puntatori.

Ogni elemento della lista (Nodo) contiene due dati

- Info: informazione vera e propria

- Pnext: Puntatore (indirizzo) all’elemento successivo

Coda: lista che ha una gestione di tipo FIFO (First In First Out): il primo elemento inserito è il primo elemento estratto. Gli inserimenti devono essere fatti sempre in fondo e le estrazioni avvengono sempre dalla testa; pertanto, per un gestione efficiente della coda sarebbe opportuno conoscere sempre l’indirizzo del primo e dell’ultimo nodo. Il funzionamento della coda è simile alla coda di persone in “coda” a uno sportello postale.

Pila: lista che ha una gestione di tipo LIFO (Last In First Out): l’ultimo elemento inserito è il primo elemento estratto. Gli inserimenti ed estrazioni avvengono sempre in testa; per rappresentare una pila può essere utilizzato anche un array, a patto di conoscere il numero massimo di elementi da memorizzare. Il funzionamento della pila è simile alla pila di piatti da lavare.

Per poter accedere alla lista è indispensabile conoscere l’indirizzo del primo elemento (P0); l’ accesso ai singoli nodi è sequenziale: per accedere al Nodo C è necessario passare dal Nodo A e dal Nodo B.

2. Operazioni sulle liste: cancellazione di un nodo

2. Operazioni sulle liste: inserimento di un nodo

3. Lista concatenata circolare semplice

4. Lista concatenata doppia o bidirezionale

5. Programma C: file e lista

/*--- listaNumeri.c -----
Creare il file "Numeri.txt"; e scrivere in esso, uno per riga, una serie di numeri interi generati in modo casuale.
Leggere i numeri memorizzati nel  file "Numeri.txt" e inserirli in una lista circolare semplice.
Successivamente 
- eliminare un nodo dalla lista; se il nodo scelto non esiste segnalarlo;
- ordinare la lista in modo crescente;
- inserire un nuovo nodo nella lista ordinata;
- ricercare un nodo a scelta;
- stampare la lista;
----------------------------------------
Note 
1) --- struct e typedef --- 
struct: "struttura" che mette insieme dati di diverso tipo
	struct NUMEROLISTA
	{
  		int valore;
  		struct NUMEROLISTA *next;
	}
viene definita una struct, di nome “NUMEROLISTA”, composta da 
	- una variabile di tipo intero di nome “valore”
	- un puntatore, di nome “next”, a una struct di nome “NUMEROLISTA”
typedef struct NUMEROLISTA
{
  int valore;
  struct NUMEROLISTA *next;
} NODO;

typedef ... 
    ... NODO;	viene definito un nuovo tipo di variabile; a questo nuovo tipo di variabile viene assegnato il nome NODO, cosicché è possibile definire:
NODO a		a: variabile di tipo NODO
NODO *p	        p: puntatore a una variabile di tipo NODO 
-----------------------------------
2) --- percorso e nome file ---
char nomeFile[] = "Numeri.txt";   
se il file è nella stessa cartella dell’ “.exe” non è necessario indicare il percorso; se è in una cartella diversa bisogna indicarlo, ad es.: char nomeFile[] = "C:\\percorsofile\\Numeri.txt". Nella scrittura del percorso utilizzare la doppia barra ( \\ ).
-----------------------------------------
3) --- Generazione di numeri casuali: le funzioni srand(...) e rand() --
  La funzione srand(...) cambia il numero di base (seed/seme)  
  per la generazione dei numeri pseudo-casuali di rand(), 
  altrimenti rand() genererebbe sempre gli stessi numeri,ad ogni 
  esecuzione del programma.
  Per poter fornire a srand un seme sempre diverso viene
  utilizzata la funzione time(NULL), presente nell’ header file time.h 
  della libreria standard del C, che restituisce il numero di secondi
  trascorsi tra l'istante attuale e il I Gennaio 1970. 
  rand() genera dei numeri compresi tra 0 e RAND_MAX (32767). Per avere 
  dei numeri compresi tra 1  e 100 viene utilizzata la seguente procedura:
 - il numero generato da rand() viene diviso per il valore della costante
MAXRAND (#define MAXRAND 100) e si prende il resto; - al resto si somma il valore 1. 
Si può esaminare il comportamento di srand( ) e rand() nell'articolo 
"Linguaggio C: generazione di numeri casuali"

*/

#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <process.h>
#include <ctype.h>
#include <float.h>
#include <math.h>

#define MAX 10
#define MAXRAND 100

typedef struct NUMEROLISTA
{
  int valore;
  struct NUMEROLISTA *next;
} NODO;

FILE *fp;
char nomeFile[] = "Numeri.txt"; 
NODO *pPrimo = NULL, *pUltimo= NULL;

//--- dichiarazione (prototipo) dellle funzioni utilizzate ---
void creareFile();
void leggereFileCreareLista();
void inserisci(int valore);
void eliminare();
void ordinare();
void inserireNuovo();
void ricercare();
void stampare(NODO*);
NODO* allocare();

int main(int argc, char *argv[])
{
	char scelta = 'z';
	while (scelta <= '7' || scelta == 'z')
	{
		system("CLS");
		printf("\n\n --- File e lista --- \n\n");
		printf("     1-creare file (Numeri.txt) \n");
		printf("     2-leggere file e creare lista\n");
		printf("     3-eliminare nodo dalla lista\n");
		printf("     4-ordinare lista\n");
		printf("     5-inserire nuovo nodo in lista\n");
		printf("     6-stampare lista\n");
		printf("     7-fine\n");
		printf("\n\n");
		printf("     scegliere: ");
		char scelta = getchar();
		printf("\n\n");
		
		switch (scelta)
		{
		case '1':
		{   creareFile();
			printf("\n Premere un tasto per continuare ");
			getch();
			break;
		}
		case '2':
		{   leggereFileCreareLista();
			printf("\n Premere un tasto per continuare ");
			getch();
			break;
		}
		case '3':
		{   
			eliminare();
			printf("\n Premere un tasto per continuare ");
			getch();
			break;
		}
		case '4':
		{
			ordinare();
			printf("\n Premere un tasto per continuare ");
			getch();
			break;
		}
		case '5':
		{  
		 	inserireNuovo();
			printf("\n Premere un tasto per continuare ");
			getch();
		 	break;
		}
		case '6':
		{
		   	stampare(pPrimo);
	  	   	printf("\n Premere un tasto per continuare ");
		   	getch();
		   	break;
		}
		case '7':
		{
		   exit(0);
		   break;
		}
		}//chiusura switch
	}//chiusura while
	system("PAUSE");
 printf("\n\n  FINE - premere un tasto per continuare \n ");
 getch();
}
//---
void creareFile()
{
int n;	
char strnum[5];
if ( (fp = fopen(nomeFile, "w")) == NULL)
  {
    printf("\nError opening file in creazione \n");
    exit(2);
  }

  srand(time(NULL)); 
  printf("\t");
  for (int i=0; i<MAX;i++)
  {
         n = rand() % MAXRAND +1; 
  	 printf("%d\t", n);
  	 sprintf(strnum, "%4d",n);
  	 fprintf(fp, "%s\n",strnum);
  }
  fclose(fp);
  //
  printf("\n\n  File Numeri.txt creato \n");
  return;
}

//------------------- leggereFileCreareLista ---------
void leggereFileCreareLista()
{
	int n;	
	char strnum[5];
	
 	if (!pPrimo) 
	{
		if ( (fp = fopen(nomeFile, "r")) == NULL)
  			{
    			printf("\nError opening file in lettura\n");
          		}
 		printf("\tFile:\t");
 	 	while(fscanf (fp, "%s", strnum) != EOF)
			{
				n = atoi(strnum);
				inserisci(n);	
				printf ("%d\t",n);
 			}		
		fclose(fp);
		stampare(pPrimo);
		printf ("\n\n Lista creata\n");
	}
	else
	{
		printf("\n Lista gia' creata\n");
        	stampare(pPrimo);
	}
return;
}
//----------- alloca spazio per inserire nuovo nodo --------
 NODO *allocare()
 {
 	NODO *pNuovo;
 	
	 pNuovo = (NUMEROLISTA*)malloc(sizeof(struct NUMEROLISTA)); 
	 if  (pNuovo == NULL)
	 {
		printf("\n memoria insufficiente per inserire il nuovo nodo ");
		getch();
	 }
	return pNuovo;
 }
//--------------- inserisci ----------------
void inserisci(int n)
{

	NODO *p, *prec,  *pnuovo;
        // allocare lo spazio per inserire il nuovo nodo
	 pnuovo = allocare();
	 if  (pnuovo == NULL) return;
	//---- valorizza i campi del nuovo nodo
	pnuovo->valore = n;
	//--- lista vuota: viene creato il primo nodo 
	if (!pPrimo)
		pPrimo = pnuovo;
	else
		pUltimo->next = pnuovo;
	
        pUltimo = pnuovo;
	pUltimo->next = pPrimo;
}
//----------- stampare --------------
void stampare (NODO *pInizio)
{
	NODO *p = pInizio;
	int conta = 0;
	printf("\n\tLista:\t");
 	if (!pInizio)
 	{
 		printf ("\n lista vuota \n");
 		return;
	 }
 	 do {
			printf("%d\t", p->valore);
			p = p->next;
			conta++;
			} while (p != pInizio);

printf ("\n");
}
//------- eliminare -------------
void eliminare()
{
	int n;
	NODO *p, *pPrec;
	int trovato = 0;
	int conta = 0;
	int nele=0;
	stampare(pPrimo);
	printf("\n");

//scansione degli elementi della lista dal primo all'ultimo alla ricerca del nodo 
//da cancellare
	printf("\tNodo da eliminare: ");
	scanf ("%d", &n);
	if (n==0) return;
	//--- trova l'ultimo nodo della lista cioè quello che punta al primo: pUltimo
	pUltimo = NULL;
	p = pPrimo;
	do {
		if (p->next == pPrimo) pUltimo = p;
		p = p->next;
		conta++;
		} while (p != pPrimo);

//per capire quando si è arrivati alla fine della lista circolare è stato introdotto 
//il controllo sul numero degli elementi (nele, conta) della lista, visto che il  //puntatore dell'ultimo nodo punta al primo nodo e non a NULL.

for (p = pPrimo, pPrec = pUltimo, nele=0; (nele<conta) && (!trovato); p = p->next, nele++)
      {
      	if ( p->valore == n)
      		{
      			if (p==pPrimo)
      				{
	   				pPrimo = p->next;
				 }
    			pPrec->next = p->next;
			free(p);  //--- cancella nodo
			stampare(pPrimo);
			trovato = 1;			
		}
		//----- continua nel ciclo: nodo non trovato 
		pPrec = p;	
	}	
	if (trovato)
		printf("\n\n eliminato nodo  %d \n", n);	
	else
printf("\n\n non trovato nodo %d - conta: %d  - nele: %d \n", n,conta,nele);
return;
}
//------------ ordinare ----------
void ordinare()
{
	int v[MAX];
	int i, c, scambia,nelem;
	NODO *p;
	p = pPrimo;
	i=0;
	
	if (!pPrimo) return;
	
	printf("\n lista non ordinata \n ");	
	stampare(pPrimo);

	do {
		v[i] = p->valore;
		i++;
		p = p->next;
		} while (p != pPrimo);

	nelem = i;   
	do {
    	scambia = 0;
		for (i=0; i<(nelem-1); i++ )
		{
			if (v[i] > v[i+1])
			 {
				c= v[i];
				v[i] = v[i+1];
				v[i+1] = c;
				scambia = 1;				
			 } 
		}
	} while (scambia);
	pPrimo = NULL; 
	pUltimo = NULL;
	printf("\t");
 	for (i=0; i<nelem ; i++ )
		{
			inserisci(v[i]);
		}
	
	printf("\n lista ordinata \n ");	
	stampare(pPrimo);
	printf ("\n fine ordinamento \n");
}
//------------ inserire nuovo -----------
void inserireNuovo()
{
	int n;
	NODO *p,  *pPrec, *pNuovo;
	int inserito = 0;
	int conta = 0;
	int nele=0;
	printf("\n lista prima dell'inserimento del nuovo nodo' \n ");	
	stampare(pPrimo);
	printf("\n  Nodo da inserire: ");
	scanf ("%d", &n);
	if (n==0) return;
	//--  trova l'ultimo nodo della lista cioè quello che punta al primo: pUltimo
	pUltimo = NULL;
	p = pPrimo;
	do {
		if (p->next == pPrimo) pUltimo = p;
		p = p->next;
		conta++;
		} while (p != pPrimo);
	
	pNuovo = allocare();
	if  (pNuovo == NULL) return;
	//---------- inserimento del nodo in prima posizione perchè <= del primo nodo 
        pNuovo -> valore = n;
	if (pPrimo->valore >= n)
	    {
    		pNuovo->next = pPrimo;
		pPrimo = pNuovo;
		pUltimo->next = pPrimo;	
		}
        else
   		{
	  	  for (p = pPrimo, pPrec = pUltimo; (!inserito); p = p->next)
      		    {
      		     if ( p->valore >= n)
      			{
      			  pNuovo->next = p;
		          pPrec->next = pNuovo;		
      			  inserito = 1;			
			}
				
			if (p==pUltimo && !inserito)
				{
					pNuovo->next = pPrimo;
					pUltimo->next = pNuovo;
					inserito = 1;
				}
			  //----- continua nel ciclo: nodo non inserito 
			pPrec = p;	
		} // --- chiude for	
	   }//--- chiude else
	printf("\n");
	stampare(pPrimo);
	printf("\n lista dopo inserimento nuovo nodo \n\n");
	return;
}

(Liste concatenate o liste linkate)

Potrebbe anche piacerti

Numeri triangolari: alcuni algoritmi

Linguaggio C: Puntatori e Dichiarazioni complesse

Linguaggio C

Lascia un commento Annulla risposta