La struttura dei dati è un modo per definire, archiviare e recuperare i dati in modo strutturale e sistematico. Una struttura dati può contenere diversi tipi di elementi dati.
La disponibilità della struttura dei dati può variare a seconda dei linguaggi di programmazione. Le strutture di dati comunemente disponibili sono elenco, array, stack, code, grafico, albero ecc.
L'algoritmo è una procedura passo passo, che definisce un insieme di istruzioni da eseguire in un certo ordine per ottenere l'output desiderato.
Un problema può essere risolto in più modi. Quindi, molti algoritmi di soluzione possono essere derivati per un dato problema. Analizziamo gli algoritmi disponibili per trovare e implementare l'algoritmo più adatto.
Un algoritmo viene generalmente analizzato in base a due fattori: tempo e spazio. Cioè, quantoexecution tempo e quanto extra space richiesto dall'algoritmo.
L'analisi asintotica di un algoritmo si riferisce alla definizione del limite / inquadramento matematico delle sue prestazioni in fase di esecuzione. Utilizzando l'analisi asintotica, possiamo concludere molto bene il caso migliore, il caso medio e lo scenario peggiore di un algoritmo.
L'analisi asintotica può fornire tre livelli di vincolo matematico del tempo di esecuzione di un algoritmo:
- Il caso migliore è rappresentato dalla notazione Ω (n).
- Il caso peggiore è rappresentato dalla notazione Ο (n).
- Il caso medio è rappresentato dalla notazione Θ (n).
Una struttura di dati lineare ha elementi di dati disposti in sequenza. La volta successiva può essere individuata nel successivo indirizzo di memoria. Viene memorizzato e vi si accede in modo sequenziale. Array e list sono esempi di struttura dati lineare.
Le seguenti operazioni vengono comunemente eseguite su qualsiasi struttura dati:
Insertion - aggiunta di un elemento di dati
Deletion - rimozione di un elemento di dati
Traversal - accedere e / o stampare tutti i dati
Searching - trovare un particolare dato
Sorting - disporre gli elementi di dati in una sequenza predefinita
Esistono tre approcci comunemente usati per sviluppare algoritmi:
Greedy Approach - trovare una soluzione scegliendo l'opzione migliore successiva
Divide and Conquer - immergere il problema al minimo possibile sotto-problema e risolverli in modo indipendente
Dynamic Programming - immergere il problema al minimo possibile sottoproblema e risolverli insieme
I problemi indicati di seguito trovano la loro soluzione utilizzando l'approccio dell'algoritmo avido -
- Problema del commesso viaggiatore
- Algoritmo Minimal Spanning Tree di Prim
- Algoritmo Minimal Spanning Tree di Kruskal
- Algoritmo Minimal Spanning Tree di Dijkstra
- Grafico - Colorazione mappa
- Grafico - Copertura vertice
- Problema dello zaino
- Problema di pianificazione del lavoro
I problemi indicati di seguito trovano la loro soluzione utilizzando l'approccio dell'algoritmo di divisione e conquista -
- Unisci ordinamento
- Ordinamento rapido
- Ricerca binaria
- La moltiplicazione della matrice di Strassen
- Coppia più vicina (punti)
I problemi indicati di seguito trovano la loro soluzione utilizzando l'approccio dell'algoritmo di divisione e conquista -
- Serie di numeri di Fibonacci
- Problema dello zaino
- Torre di Hanoi
- All pair shortest path by Floyd-Warshall
- Sentiero più breve di Dijkstra
- Pianificazione del progetto
Un elenco collegato è un elenco di elementi di dati collegati a collegamenti, ad esempio puntatori o riferimenti. La maggior parte dei moderni linguaggi di programmazione di alto livello non fornisce la caratteristica di accedere direttamente alla posizione di memoria, quindi, gli elenchi collegati non sono supportati in essi o sono disponibili sotto forma di funzioni integrate.
Nella struttura dati, lo stack è un tipo di dati astratto (ADT) utilizzato per archiviare e recuperare i valori nel metodo Last In First Out.
Gli stack seguono il metodo LIFO e l'aggiunta e il recupero di un elemento di dati richiede solo Ο (n) tempo. Le pile vengono utilizzate laddove è necessario accedere ai dati in ordine inverso o al loro arrivo. Gli stack sono usati comunemente nelle chiamate di funzioni ricorsive, nell'analisi di espressioni, nel primo attraversamento della profondità dei grafici, ecc.
Le operazioni seguenti possono essere eseguite su uno stack:
push() - aggiunge un oggetto da impilare
pop() - rimuove l'elemento in cima alla pila
peek() - dà valore all'elemento superiore senza rimuoverlo
isempty() - controlla se lo stack è vuoto
isfull() - controlla se lo stack è pieno
La coda è una struttura dati astratta, in qualche modo simile allo stack. A differenza dello stack, la coda viene aperta a entrambe le estremità. Un'estremità viene sempre utilizzata per inserire dati (accodamento) e l'altra viene utilizzata per rimuovere dati (rimozione dalla coda). La coda segue la metodologia First-In-First-Out, ovvero si accederà per primo all'elemento di dati memorizzato per primo.
Poiché le code seguono il metodo FIFO, vengono utilizzate quando è necessario lavorare su elementi di dati nella sequenza esatta del loro arrivo. Ogni sistema operativo mantiene le code di vari processi. Le code prioritarie e l'ampiezza del primo attraversamento dei grafici sono alcuni esempi di code.
Le operazioni seguenti possono essere eseguite su uno stack:
enqueue() - aggiunge un elemento in fondo alla coda
dequeue() - rimuove l'elemento dalla parte anteriore della coda
peek() - valorizza il frontale senza rimuoverlo
isempty() - controlla se lo stack è vuoto
isfull() - controlla se lo stack è pieno
La ricerca lineare tenta di trovare un elemento in un tipo di dati disposto in sequenza. Questi elementi di dati disposti in sequenza noti come array o elenco, sono accessibili nella posizione di memoria incrementale. La ricerca lineare confronta l'elemento di dati previsto con ciascuno degli elementi di dati nell'elenco o nella matrice. La complessità media caso-tempo della ricerca lineare è Ο (n) e la complessità del caso peggiore è Ο (n 2 ). I dati negli array / elenchi di destinazione non devono essere ordinati.
Una ricerca binaria funziona solo su elenchi o array ordinati. Questa ricerca seleziona la parte centrale che divide l'intero elenco in due parti. Per prima cosa viene confrontato il centro.
Questa ricerca confronta prima il valore di destinazione con la metà dell'elenco. Se non viene trovato, decide se.
Bubble sort è un algoritmo basato sul confronto in cui viene confrontata ogni coppia di elementi adiacenti e gli elementi vengono scambiati se non sono in ordine. Poiché la complessità temporale è Ο (n 2 ), non è adatta per grandi set di dati.
L'ordinamento per inserimento divide l'elenco in due sottoelenco, ordinato e non ordinato. Prende un elemento alla volta e lo trova nella posizione appropriata nel sottoelenco ordinato e lo inserisce lì. L'output dopo l'inserimento è un sottoelenco ordinato. Funziona in modo iterativo su tutti gli elementi di una sottoelenco non ordinata e li inserisce in una sottoelenco ordinata in ordine.
L'ordinamento della selezione è una tecnica di ordinamento sul posto. Divide il set di dati in due sottoelenchi: ordinato e non ordinato. Quindi seleziona l'elemento minimo dal sottoelenco non ordinato e lo inserisce nell'elenco ordinato. Questo itera a meno che tutti gli elementi di un sottoelenco non ordinato vengano consumati in un sottoelenco ordinato.
Entrambe le tecniche di ordinamento mantengono due sottoelenchi, ordinati e non ordinati, ed entrambi prendono un elemento alla volta e lo inseriscono in un sottoelenco ordinato. L'ordinamento per inserzione funziona sull'elemento corrente e lo posiziona nell'array ordinato nella posizione appropriata mantenendo le proprietà dell'ordinamento per inserzione. Invece, l'ordinamento per selezione cerca il minimo dal sottoelenco non ordinato e lo sostituisce con l'elemento corrente in mano.
Merge sort è un algoritmo di ordinamento basato sull'approccio di programmazione divide et impera. Continua a dividere l'elenco in un sottoelenco più piccolo fino a quando tutto il sottoelenco ha solo 1 elemento. E poi li unisce in modo ordinato fino a quando tutti i sottoelenchi vengono consumati. Ha una complessità di runtime di Ο (n log n) e necessita di Ο (n) spazio ausiliario.
L'ordinamento della shell può essere definito una variante dell'ordinamento per inserzione. L'ordinamento della shell divide l'elenco in un sottoelenco più piccolo basato su alcunigapvariabile e quindi ogni sottoelenco viene ordinato utilizzando l'ordinamento per inserimento. Nella migliore delle ipotesi, può eseguire fino a Ο (n log n).
L'ordinamento rapido utilizza l'approccio divide et impera. Divide l'elenco in "partizioni" più piccole utilizzando "pivot". I valori più piccoli del pivot sono disposti nella partizione sinistra e i valori maggiori sono disposti nella partizione destra. Ogni partizione viene ordinata in modo ricorsivo utilizzando l'ordinamento rapido.
Un grafico è una rappresentazione pittorica di un insieme di oggetti in cui alcune coppie di oggetti sono collegate da collegamenti. Gli oggetti interconnessi sono rappresentati da punti chiamati vertici e i collegamenti che collegano i vertici sono chiamati bordi.
L'algoritmo Depth First Search (DFS) attraversa un grafico in un movimento in profondità e utilizza uno stack per ricordare di ottenere il vertice successivo per avviare una ricerca quando si verifica un vicolo cieco in qualsiasi iterazione.
L'algoritmo di ricerca Breadth First (BFS) attraversa un grafico in un movimento verso l'ampiezza e utilizza una coda per ricordare di ottenere il vertice successivo per avviare una ricerca quando si verifica un vicolo cieco in qualsiasi iterazione.
Un albero è un grafo con connessione minima che non ha loop e circuiti.
Un albero binario ha una condizione speciale che ogni nodo possa avere al massimo due figli.
Un albero binario di ricerca è un albero binario con una disposizione speciale in cui il figlio sinistro di un nodo deve avere un valore inferiore al valore del suo genitore e il figlio destro del nodo deve avere un valore maggiore del suo valore genitore.
L'attraversamento dell'albero è un processo per visitare tutti i nodi di un albero. Poiché tutti i nodi sono collegati tramite bordi (collegamenti), iniziamo sempre dal nodo radice (testa). Ci sono tre modi che usiamo per attraversare un albero:
- Attraversamento in ordine
- Preordina Traversal
- Post-order Traversal
- Attraversamento in ordine - 10 14 19 27 31 35 42
- Attraversamento pre-ordine - 27 14 10 19 35 31 42
- Attraversamento post-ordine - 10 19 14 31 42 35 27
Gli alberi AVL sono un albero di ricerca binario con bilanciamento dell'altezza. L'albero AVL controlla l'altezza dei sottoalberi sinistro e destro e assicura che la differenza non sia maggiore di 1. Questa differenza è chiamata Fattore di equilibrio.
BalanceFactor = height(left-sutree) − height(right-sutree)Uno spanning tree è un sottoinsieme del grafico G, che ha tutti i vertici coperti con il minimo numero possibile di bordi. Uno spanning tree non ha cicli e non può essere disconnesso.
Dipende da quanto è connesso il grafico. Un grafo non orientato completo può avere un numero massimo di n n-1 di spanning tree, dove n è il numero di nodi.
Questo algoritmo tratta il grafico come una foresta e ogni nodo come un singolo albero. Un albero si connette a un altro solo e solo se ha il minor costo tra tutte le opzioni disponibili e non viola le proprietà MST.
L'algoritmo di Prim tratta i nodi come un singolo albero e continua ad aggiungere nuovi nodi allo spanning tree dal grafico dato.
In un grafico ponderato, uno spanning tree minimo è uno spanning tree che ha un peso minimo rispetto a tutti gli altri spanning tree dello stesso grafico.
Heap è una speciale struttura dati ad albero binario bilanciato in cui la chiave del nodo radice viene confrontata con i suoi figli e organizzata di conseguenza. Un min-heap, un nodo padre ha un valore chiave inferiore ai suoi figli e un nodo padre max-heap ha un valore maggiore dei suoi figli.
Una funzione ricorsiva è quella che chiama se stessa, direttamente o chiama una funzione che a sua volta la chiama. Ogni funzione ricorsiva segue le proprietà ricorsive -base criteria dove le funzioni smettono di chiamare se stesse e progressive approach dove le funzioni cercano di soddisfare i criteri di base in ogni iterazione.
Torre di Hanoi, è un puzzle matematico che consiste di tre torri (pioli) e più di un anello. Tutti gli anelli sono di dimensioni diverse e impilati l'uno sull'altro dove il disco grande è sempre al di sotto del disco piccolo. Lo scopo è spostare la torre del disco da un piolo all'altro, senza romperne le proprietà.
La serie di Fibonacci genera il numero successivo aggiungendo due numeri precedenti. Ad esempio - 0 1 1 2 3 5 8 13.
L'hashing è una tecnica per convertire un intervallo di valori chiave in un intervallo di indici di un array. Utilizzando le tabelle hash, possiamo creare un archivio dati associativo in cui l'indice dei dati può essere trovato fornendo i suoi valori chiave.
La ricerca in interpolazione è una variante migliorata della ricerca binaria. Questo algoritmo di ricerca funziona sulla posizione di rilevamento del valore richiesto.
Notazione prefisso - * + ab + cd
Notazione postfissa - ab + cd + *