Introduzione alle matrici nella struttura dei dati
L'array è un tipo di struttura dati utilizzata per archiviare dati omogenei in posizioni di memoria contigue. Questo implementa l'idea di memorizzare i vari oggetti in modo tale che possano essere recuperati o consultati in una sola volta.
Qui indice si riferisce alla posizione di un elemento nella matrice. Immaginiamo se P (L) è il nome dell'array in cui 'P' è il nome della variabile e 'L' è la lunghezza dell'array, ovvero il numero di elementi presenti nell'array. Quindi P (i) rappresenta l'elemento in corrispondenza di "i + 1" nella posizione dell'array.
Per esempio:
P (6) = 72 significa elemento in 6 + 1a posizione dell'array.
Need of Array: aiuta a rappresentare un gran numero di elementi usando una singola variabile. Rende inoltre più facile l'accesso dell'elemento all'archivio nella posizione di memoria utilizzando l'indice dell'array che rappresenta la posizione dell'elemento nell'array.
Come funzionano gli array nella struttura dei dati?
La matrice memorizza le variabili in posizioni contigue e fornisce loro un indice particolare. Quando qualcuno vuole recuperare i dati, la persona usa questo indice. Nell'array 'P' sopra indicato, dire l'indirizzo di base per array = 100, quindi gli elementi vengono memorizzati come di seguito:
La memoria allocata a un array può essere calcolata come:
- Matrice unidimensionale: memoria totale allocata a una matrice = numero di elementi * dimensione di un elemento. Ad esempio: nel caso precedente, memoria = 7 * (dimensione di int)
- Ordine principale di riga: memoria totale allocata all'array 2D = Numero di elementi * dimensione di un elemento
= Numero di righe * Numero di colonne * Dimensione di un elemento - Ordine principale colonna: memoria totale allocata all'array 2D = Numero di elementi * dimensione di un elemento
= Numero di righe * Numero di colonne * Dimensione di un elemento
Come definire le matrici?
Pertanto, la matrice può essere definita come una struttura di dati derivati per memorizzare dati omogenei di tipo di dati primitivo in posizioni di memoria contigue. Di seguito sono riportate le operazioni che possono essere eseguite su array:
1. Inserimento: si riferisce all'inserimento di un elemento nella matrice in corrispondenza di un indice specifico. Questo può essere eseguito con complessità O (n).
2. Eliminazione: si riferisce all'eliminazione di un elemento in un determinato indice. Questa operazione richiede lo spostamento degli elementi dopo l'eliminazione, quindi assume una complessità O (n).
3. Ricerca: si riferisce all'accesso a un elemento in un indice particolare di un array.
4. Attraversamento: si riferisce alla stampa di tutti gli elementi di un array uno dopo l'altro.
Proprietà delle matrici nella struttura dei dati
Di seguito sono riportate le proprietà degli array nella struttura dati:
- È un tipo di dati derivati, composto da una raccolta di vari tipi di dati primitivi come int, char, float, ecc.
- Gli elementi di un array sono memorizzati in blocchi contigui nella memoria primaria.
- Il nome dell'array memorizza l'indirizzo di base dell'array. Funziona come un puntatore al blocco di memoria in cui è stato memorizzato il primo elemento.
- Gli indici di array iniziano da 0 a N-1 in caso di array a dimensione singola in cui n rappresenta il numero di elementi in un array.
- Gli elementi dell'array possono essere composti solo da costanti e valori letterali.
Come creare array?
È possibile creare array utilizzando la sintassi seguente:
1. Matrice dimensionale: var = (c1, c2, c3, …… .cn)
Qui var si riferisce alla variabile di matrice che memorizza la posizione di base della matrice. E c1, c2 … sono elementi dell'array.
Esempio: int a = (4, 6, 7, 8, 9)
Lunghezza dell'array = n
2. Matrice multidimensionale : var = ((r 01, … r 0n ), (r 10, … ..r 1n )… .. (r m0 … .r mn ))
Qui var si riferisce al nome della matrice di m righe e n colonne.
Come accedere all'elemento array?
Gli indici di un array iniziano da 0 a -1, 0 che indica il primo elemento dell'array e -1 indica l'ultimo elemento dell'array. Allo stesso modo, -2 indica l'ultimo ma un elemento dell'array. Diciamo che esiste un array 'A' con 10 elementi. Quindi qui Una variabile memorizza il riferimento della prima variabile dell'array e questo si chiama "Indirizzo base" di un array. Dopo questo, se qualcuno vuole accedere all'elemento dell'array, l'indirizzo di quell'elemento viene calcolato usando la formula seguente.
Indirizzo di ith element = Indirizzo base + i * dimensione di ciascun elemento
Qui, la dimensione di ciascun elemento si riferisce alla memoria occupata da vari tipi di dati primitivi che l'array sta trattenendo. Ad esempio, int occupa 2 byte di spazio e float occupa 4 byte di spazio in C.
Accesso alla matrice multidimensionale
Diciamo che A (r l, …… .., r u ) (c u, ……, c l ) è un array multidimensionale e rl, r u, c u, c l sono i limiti inferiore e superiore per righe e colonne. Rispetto al numero di righe in A, dire NR = r u - r l +1 e il numero di colonne in A, dire NC = c l - c u +1.
Ora per trovare l'indirizzo di un elemento nell'array ci sono 2 metodi:
- Fila maggiore: dove attraversiamo riga per riga.
Indirizzo di A (i) (j) = Indirizzo base + ((i - r l ) * NC + (j- c l )) * dimensione di ciascun elemento.
- Colonna Maggiore: dove attraversiamo colonna per colonna.
Indirizzo di A (i) (j) = Indirizzo base + ((i - r l ) + (j- c l ) * NR) * dimensione di ciascun elemento.
Complessità: l' accesso a qualsiasi elemento dell'array è molto più semplice e può essere fatto nella complessità O (1).
Conclusione
Le matrici sono un modo molto singolare per strutturare i dati memorizzati in modo che possano essere facilmente accessibili e di cui è possibile eseguire query per recuperare il valore in un determinato numero utilizzando il valore dell'indice. Sebbene l'inserimento di un elemento in un array richieda molto tempo in quanto richiede un riarrangiamento completo e lo spostamento di elementi esistenti di un array. Tuttavia, viene utilizzato per implementare varie altre strutture di dati complessi come albero, coda o stack e utilizzato anche in vari algoritmi.
Articolo raccomandato
Questa è una guida agli array nella struttura dei dati. Qui discutiamo come creare e accedere agli elementi dell'array nella struttura dei dati insieme a Proprietà. Puoi anche consultare i nostri altri articoli correlati per saperne di più -
- Come creare array in PHP?
- Matrici in Java Programmazione Vantaggi e svantaggi
- Matrici in programmazione C (esempi)
- Le 10 domande principali per l'intervista sulla struttura dei dati