Strutture dati e algoritmi - Array

L'array è un contenitore che può contenere un numero fisso di elementi e questi elementi dovrebbero essere dello stesso tipo. La maggior parte delle strutture di dati fa uso di array per implementare i propri algoritmi. Di seguito sono riportati i termini importanti per comprendere il concetto di Array.

  • Element - Ogni elemento memorizzato in un array è chiamato elemento.

  • Index - Ogni posizione di un elemento in un array ha un indice numerico, che viene utilizzato per identificare l'elemento.

Rappresentazione di array

Gli array possono essere dichiarati in vari modi in diverse lingue. Per illustrazione, prendiamo la dichiarazione di array C.

Gli array possono essere dichiarati in vari modi in diverse lingue. Per illustrazione, prendiamo la dichiarazione di array C.

Come per l'illustrazione sopra, di seguito sono riportati i punti importanti da considerare.

  • L'indice inizia con 0.

  • La lunghezza dell'array è 10, il che significa che può memorizzare 10 elementi.

  • Ogni elemento è accessibile tramite il suo indice. Ad esempio, possiamo recuperare un elemento con indice 6 come 9.

Operazioni di base

Di seguito sono riportate le operazioni di base supportate da un array.

  • Traverse - stampa tutti gli elementi dell'array uno per uno.

  • Insertion - Aggiunge un elemento all'indice dato.

  • Deletion - Elimina un elemento all'indice dato.

  • Search - Cerca un elemento utilizzando l'indice specificato o il valore.

  • Update - Aggiorna un elemento all'indice dato.

In C, quando un array viene inizializzato con size, assegna i valori predefiniti ai suoi elementi nell'ordine seguente.

Tipo di dati Valore predefinito
bool falso
char 0
int 0
galleggiante 0.0
Doppio 0.0f
vuoto
wchar_t 0

Operazione trasversale

Questa operazione consiste nell'attraversare gli elementi di un array.

Esempio

Il seguente programma attraversa e stampa gli elementi di un array:

#include <stdio.h>
main() {
   int LA[] = {1,3,5,7,8};
   int item = 10, k = 3, n = 5;
   int i = 0, j = n;   
   printf("The original array elements are :\n");
   for(i = 0; i<n; i++) {
      printf("LA[%d] = %d \n", i, LA[i]);
   }
}

Quando compiliamo ed eseguiamo il programma sopra, produce il seguente risultato:

Produzione

The original array elements are :
LA[0] = 1 
LA[1] = 3 
LA[2] = 5 
LA[3] = 7 
LA[4] = 8

Operazione di inserimento

L'operazione di inserimento consiste nell'inserire uno o più elementi di dati in un array. In base al requisito, è possibile aggiungere un nuovo elemento all'inizio, alla fine o a un determinato indice dell'array.

Qui, vediamo un'implementazione pratica dell'operazione di inserimento, in cui aggiungiamo dati alla fine dell'array -

Esempio

Di seguito è riportata l'implementazione dell'algoritmo di cui sopra:

#include <stdio.h>

main() {
   int LA[] = {1,3,5,7,8};
   int item = 10, k = 3, n = 5;
   int i = 0, j = n;
   
   printf("The original array elements are :\n");

   for(i = 0; i<n; i++) {
      printf("LA[%d] = %d \n", i, LA[i]);
   }

   n = n + 1;
	
   while( j >= k) {
      LA[j+1] = LA[j];
      j = j - 1;
   }

   LA[k] = item;

   printf("The array elements after insertion :\n");

   for(i = 0; i<n; i++) {
      printf("LA[%d] = %d \n", i, LA[i]);
   }
}

Quando compiliamo ed eseguiamo il programma sopra, produce il seguente risultato:

Produzione

The original array elements are :
LA[0] = 1 
LA[1] = 3 
LA[2] = 5 
LA[3] = 7 
LA[4] = 8 
The array elements after insertion :
LA[0] = 1 
LA[1] = 3 
LA[2] = 5 
LA[3] = 10 
LA[4] = 7 
LA[5] = 8

Per altre varianti dell'operazione di inserimento di array fare clic qui

Operazione di cancellazione

L'eliminazione si riferisce alla rimozione di un elemento esistente dall'array e alla riorganizzazione di tutti gli elementi di un array.

Algoritmo

Ritenere LA è un array lineare con N elementi e K è un numero intero positivo tale che K<=N. Di seguito è riportato l'algoritmo per eliminare un elemento disponibile alla K- esima posizione di LA.

1. Start
2. Set J = K
3. Repeat steps 4 and 5 while J < N
4. Set LA[J] = LA[J + 1]
5. Set J = J+1
6. Set N = N-1
7. Stop

Esempio

Di seguito è riportata l'implementazione dell'algoritmo di cui sopra:

#include <stdio.h>

void main() {
   int LA[] = {1,3,5,7,8};
   int k = 3, n = 5;
   int i, j;
   
   printf("The original array elements are :\n");
	
   for(i = 0; i<n; i++) {
      printf("LA[%d] = %d \n", i, LA[i]);
   }
    
   j = k;
	
   while( j < n) {
      LA[j-1] = LA[j];
      j = j + 1;
   }
	
   n = n -1;
   
   printf("The array elements after deletion :\n");
	
   for(i = 0; i<n; i++) {
      printf("LA[%d] = %d \n", i, LA[i]);
   }
}

Quando compiliamo ed eseguiamo il programma sopra, produce il seguente risultato:

Produzione

The original array elements are :
LA[0] = 1 
LA[1] = 3 
LA[2] = 5 
LA[3] = 7 
LA[4] = 8 
The array elements after deletion :
LA[0] = 1 
LA[1] = 3 
LA[2] = 7 
LA[3] = 8

Operazione di ricerca

È possibile eseguire una ricerca di un elemento della matrice in base al suo valore o al suo indice.

Algoritmo

Ritenere LA è un array lineare con N elementi e K è un numero intero positivo tale che K<=N. Di seguito è riportato l'algoritmo per trovare un elemento con un valore ITEM utilizzando la ricerca sequenziale.

1. Start
2. Set J = 0
3. Repeat steps 4 and 5 while J < N
4. IF LA[J] is equal ITEM THEN GOTO STEP 6
5. Set J = J +1
6. PRINT J, ITEM
7. Stop

Esempio

Di seguito è riportata l'implementazione dell'algoritmo di cui sopra:

#include <stdio.h>

void main() {
   int LA[] = {1,3,5,7,8};
   int item = 5, n = 5;
   int i = 0, j = 0;
   
   printf("The original array elements are :\n");
	
   for(i = 0; i<n; i++) {
      printf("LA[%d] = %d \n", i, LA[i]);
   }
    
   while( j < n){
      if( LA[j] == item ) {
         break;
      }
		
      j = j + 1;
   }
	
   printf("Found element %d at position %d\n", item, j+1);
}

Quando compiliamo ed eseguiamo il programma sopra, produce il seguente risultato:

Produzione

The original array elements are :
LA[0] = 1 
LA[1] = 3 
LA[2] = 5 
LA[3] = 7 
LA[4] = 8 
Found element 5 at position 3

Operazione di aggiornamento

L'operazione di aggiornamento si riferisce all'aggiornamento di un elemento esistente dall'array in un determinato indice.

Algoritmo

Ritenere LA è un array lineare con N elementi e K è un numero intero positivo tale che K<=N. Di seguito è riportato l'algoritmo per aggiornare un elemento disponibili al K ° posizione di LA.

1. Start
2. Set LA[K-1] = ITEM
3. Stop

Esempio

Di seguito è riportata l'implementazione dell'algoritmo di cui sopra:

#include <stdio.h>

void main() {
   int LA[] = {1,3,5,7,8};
   int k = 3, n = 5, item = 10;
   int i, j;
   
   printf("The original array elements are :\n");
	
   for(i = 0; i<n; i++) {
      printf("LA[%d] = %d \n", i, LA[i]);
   }
    
   LA[k-1] = item;

   printf("The array elements after updation :\n");
	
   for(i = 0; i<n; i++) {
      printf("LA[%d] = %d \n", i, LA[i]);
   }
}

Quando compiliamo ed eseguiamo il programma sopra, produce il seguente risultato:

Produzione

The original array elements are :
LA[0] = 1 
LA[1] = 3 
LA[2] = 5 
LA[3] = 7 
LA[4] = 8 
The array elements after updation :
LA[0] = 1 
LA[1] = 3 
LA[2] = 10 
LA[3] = 7 
LA[4] = 8