Raccomandato, 2020

Scelta Del Redattore

Differenza tra matrice e lista collegata

La principale differenza tra l' array e l' elenco collegato riguarda la loro struttura. Le matrici sono strutture di dati basate su indici in cui ogni elemento è associato a un indice. D'altra parte, l'elenco collegato si basa su riferimenti in cui ogni nodo è costituito dai dati e dai riferimenti all'elemento precedente e successivo.

Fondamentalmente, una matrice è un insieme di oggetti dati simili memorizzati in posizioni di memoria sequenziali sotto un'intestazione comune o un nome di variabile.

Mentre una lista collegata è una struttura dati che contiene una sequenza di elementi in cui ciascun elemento è collegato al suo elemento successivo. Ci sono due campi in un elemento dell'elenco collegato. Uno è il campo Dati, e altro è il campo di collegamento, campo Dati contiene il valore effettivo da memorizzare ed elaborare. Inoltre, il campo del link contiene l'indirizzo dell'elemento di dati successivo nell'elenco collegato. L'indirizzo utilizzato per accedere a un particolare nodo è noto come puntatore.

Un'altra differenza significativa tra un array e un elenco collegato è che Array ha una dimensione fissa e deve essere dichiarata precedente, ma l'Elenco collegato non è limitato alle dimensioni e si espande e si contrae durante l'esecuzione.

Grafico comparativo

Base per il confrontoschieramentoLista collegata
Di baseÈ un insieme consistente di un numero fisso di elementi di dati.È un insieme ordinato che comprende un numero variabile di elementi di dati.
TagliaSpecificato durante la dichiarazione.Non è necessario specificare; crescere e restringersi durante l'esecuzione.
Allocazione dello spazio di archiviazioneLa posizione dell'elemento viene allocata durante la compilazione.La posizione dell'elemento viene assegnata durante il tempo di esecuzione.
Ordine degli elementiMemorizzato consecutivamenteMemorizzato a caso
Accedere all'elementoAccesso diretto o casuale, ad es. Specifica l'indice o l'indice dell'array.Accesso sequenziale, vale a dire, attraversare a partire dal primo nodo nell'elenco dal puntatore.
Inserimento e cancellazione dell'elementoLento relativamente quando è richiesto lo spostamento.Più facile, veloce ed efficiente.
RicercaRicerca binaria e ricerca linearericerca lineare
Memoria richiestaDi menoDi Più
Utilizzo della memoriaInefficaceEfficiente

Definizione di matrice

Un array è definito come un insieme di un numero definito di elementi o elementi di dati omogenei. Significa che una matrice può contenere solo un tipo di dati, tutti gli interi, tutti i numeri in virgola mobile o tutti i caratteri. La dichiarazione di una matrice è la seguente:
int a [10];
Dove int specifica il tipo di dati o gli archivi di tipi di elementi. "A" è il nome di un array, e il numero specificato all'interno delle parentesi quadre è il numero di elementi che un array può memorizzare, questo è anche chiamato dimensione o lunghezza dell'array.

Vediamo alcuni dei concetti da ricordare sugli array:

  • È possibile accedere ai singoli elementi di un array descrivendo il nome dell'array, seguito da indice o pedice (che determina la posizione dell'elemento nell'array) all'interno delle parentesi quadre. Ad esempio, per recuperare il quinto elemento dell'array, è necessario scrivere una dichiarazione a [4].
  • In ogni caso gli elementi di una matrice verranno memorizzati in una posizione di memoria consecutiva.
  • Il primo elemento dell'array ha indice zero [0]. Significa che il primo e l'ultimo elemento saranno specificati rispettivamente come [0] e [9].
  • Il numero di elementi che possono essere memorizzati in una matrice, cioè la dimensione di una matrice o la sua lunghezza è data dalla seguente equazione:
    (limite superiore-limite inferiore) + 1
    Per l'array di cui sopra, sarebbe (9-0) + 1 = 10. Dove 0 è il limite inferiore dell'array e 9 è il limite superiore dell'array.
  • Gli array possono essere letti o scritti attraverso il loop. Se leggiamo l'array monodimensionale, richiede un loop per la lettura e altro per scrivere (stampare) l'array, ad esempio:
    un. Per leggere un array
    for (i = 0; i <= 9; i ++)
    {scanf ("% d", & a [i]); }
    b. Per scrivere un array
    for (i = 0; i <= 9; i ++)
    {printf ("% d", a [i]); }
  • Nel caso di un array 2-D, richiederebbero due cicli e un array analogamente n-dimensionale avrebbe bisogno di n loop.

Le operazioni eseguite sugli array sono:

  1. Creazione di array
  2. Attraversare un array
  3. Inserimento di nuovi elementi
  4. Cancellazione degli elementi richiesti.
  5. Modifica di un elemento.
  6. Unione di array

Esempio

Il seguente programma illustra la lettura e la scrittura dell'array.

#include
#include
void main ()
{
int a[10], i;
printf("Enter the array");
for ( i= 0; i <= 9; i++)
{
scanf ( "%d", &a[ i ] ) ;
}
printf( "Enter the array" );
for (i = 0 ; i <= 9 ; i++)
{
printf ( "%d\n", a[ i ] ) ;
}
getch ();
}

Definizione dell'elenco collegato

Elenco collegato è un elenco particolare di alcuni elementi di dati collegati tra loro. In questo ogni elemento punta all'elemento successivo che rappresenta l'ordinamento logico. Ogni elemento è chiamato nodo, che ha due parti.

INFO parte che memorizza le informazioni e POINTER che punta all'elemento successivo. Come sapete per l'archiviazione dell'indirizzo, abbiamo una struttura dati unica in C chiamata puntatori. Quindi il secondo campo della lista deve essere un tipo di puntatore.

I tipi di elenchi concatenati sono elenchi collegati singolarmente, elenchi concatenati, elenchi concatenati circolari, elenchi concatenati circolari.

Le operazioni eseguite sull'Elenco Collegato sono:

  1. Creazione
  2. attraversamento
  3. Inserimento
  4. cancellazione
  5. Ricerca
  6. Concatenazione
  7. Display

Esempio

Il seguente frammento illustra la creazione di un elenco collegato:

struct node
{
int num;
stuct node *next;
}
start = NULL;
void create()
{
typedef struct node NODE;
NODE *p, *q;
char choice;
first = NULL;
do
{
p = (NODE *) malloc (sizeof (NODE));
printf ("Enter the data item\n");
scanf ("%d", & p -> num);
if (p == NULL)
{
q = start;
while (q -> next ! = NULL)
{ q = q -> next
}
p -> next = q -> next;
q -> = p;
}
else
{
p -> next = start;
start = p;
}
printf ("Do you want to continue (type y or n) ? \n");
scanf ("%c", &choice) ;
}
while ((choice == 'y') || (choice == 'Y'));
}

Differenze chiave tra matrice e lista collegata

  1. Una matrice è la struttura di dati contiene una raccolta di elementi di dati di tipo simile mentre la lista collegata è considerata come struttura di dati non primitiva contiene una raccolta di elementi collegati non ordinati noti come nodi.
  2. Nell'array gli elementi appartengono agli indici, cioè, se vuoi entrare nel quarto elemento devi scrivere il nome della variabile con il suo indice o posizione all'interno della parentesi quadra.
    In una lista collegata, però, devi partire dalla testa e lavorare fino a raggiungere il quarto elemento.
  3. Mentre l'accesso a un array di elementi è veloce mentre l'elenco collegato richiede tempo lineare, è piuttosto lento.
  4. Operazioni come l'inserimento e la cancellazione negli array consumano molto tempo. D'altra parte, le prestazioni di queste operazioni negli elenchi collegati sono veloci.
  5. Gli array sono di dimensioni fisse. Al contrario, gli elenchi collegati sono dinamici e flessibili e possono espandersi e contrarre le sue dimensioni.
  6. In un array, la memoria viene assegnata durante la compilazione mentre in un elenco collegato viene allocata durante l'esecuzione o il runtime.
  7. Gli elementi vengono archiviati consecutivamente negli array mentre sono archiviati in modo casuale nelle liste collegate.
  8. Il requisito della memoria è meno dovuto ai dati effettivi memorizzati nell'indice dell'array. Per contro, c'è bisogno di più memoria negli elenchi collegati a causa della memorizzazione di ulteriori elementi di riferimento successivi e precedenti.
  9. Inoltre, l'utilizzo della memoria è inefficiente nell'array. Viceversa, l'utilizzo della memoria è efficiente nell'array.

Conclusione

Gli elenchi Array e Linked sono tipi di strutture dati differenti per struttura, metodi di accesso e manipolazione, requisiti di memoria e utilizzo. E hanno particolare vantaggio e svantaggio rispetto alla sua implementazione. Di conseguenza, uno può essere utilizzato secondo necessità.

Top