Strutture dati e algoritmi - Guida rapida

La struttura dei dati è un modo sistematico per organizzare i dati al fine di utilizzarli in modo efficiente. I seguenti termini sono i termini di base di una struttura dati.

Interface- Ogni struttura dati ha un'interfaccia. L'interfaccia rappresenta l'insieme di operazioni supportate da una struttura dati. Un'interfaccia fornisce solo l'elenco delle operazioni supportate, il tipo di parametri che possono accettare e il tipo di ritorno di queste operazioni.
Implementation- L'implementazione fornisce la rappresentazione interna di una struttura dati. L'implementazione fornisce anche la definizione degli algoritmi utilizzati nelle operazioni della struttura dati.

Caratteristiche di una struttura dati

Correctness - L'implementazione della struttura dati dovrebbe implementare correttamente la sua interfaccia.
Time Complexity - Il tempo di esecuzione o il tempo di esecuzione delle operazioni della struttura dati deve essere il più ridotto possibile.
Space Complexity - L'utilizzo della memoria di un'operazione di struttura dati dovrebbe essere il meno possibile.

Necessità della struttura dei dati

Poiché le applicazioni stanno diventando complesse e ricche di dati, ci sono tre problemi comuni che le applicazioni devono affrontare oggigiorno.

Data Search- Considera un inventario di 1 milione (10 ⁶ ) articoli di un negozio. Se l'applicazione deve cercare un elemento, deve cercare un elemento in 1 milione (10 ⁶ ) elementi ogni volta che rallenta la ricerca. Man mano che i dati crescono, la ricerca diventerà più lenta.
Processor speed - La velocità del processore, sebbene molto elevata, diminuisce se i dati crescono fino a un miliardo di record.
Multiple requests - Poiché migliaia di utenti possono cercare i dati contemporaneamente su un server web, anche il server veloce non riesce durante la ricerca dei dati.

Per risolvere i problemi sopra menzionati, le strutture dati vengono in soccorso. I dati possono essere organizzati in una struttura di dati in modo tale che non sia necessario cercare tutti gli elementi e che i dati richiesti possano essere cercati quasi istantaneamente.

Casi del tempo di esecuzione

Ci sono tre casi che vengono solitamente utilizzati per confrontare i tempi di esecuzione di varie strutture dati in modo relativo.

Worst Case- Questo è lo scenario in cui una particolare operazione della struttura dati richiede il tempo massimo possibile. Se il tempo del caso peggiore di un'operazione è ƒ (n), questa operazione non richiederà più del tempo ƒ (n) dove ƒ (n) rappresenta la funzione di n.
Average Case- Questo è lo scenario che descrive il tempo medio di esecuzione di un'operazione di una struttura dati. Se un'operazione richiede ƒ (n) tempo in esecuzione, allora m operazioni richiederanno mƒ (n) tempo.
Best Case- Questo è lo scenario che descrive il minor tempo possibile di esecuzione di un'operazione di una struttura dati. Se un'operazione richiede ƒ (n) tempo in esecuzione, l'operazione effettiva potrebbe richiedere tempo come numero casuale che sarebbe massimo come ƒ (n).

Terminologia di base

Data - I dati sono valori o un insieme di valori.
Data Item - Il dato si riferisce alla singola unità di valori.
Group Items - Gli elementi di dati suddivisi in elementi secondari sono chiamati elementi di gruppo.
Elementary Items - Gli elementi di dati che non possono essere divisi sono chiamati elementi elementari.
Attribute and Entity - Un'entità è quella che contiene determinati attributi o proprietà, a cui possono essere assegnati valori.
Entity Set - Entità con attributi simili formano un insieme di entità.
Field - Il campo è una singola unità elementare di informazioni che rappresenta un attributo di un'entità.
Record - Record è una raccolta di valori di campo di una determinata entità.
File - File è una raccolta di record delle entità in un determinato set di entità.

Provalo Opzione online

Non hai davvero bisogno di configurare il tuo ambiente per iniziare ad imparare il linguaggio di programmazione C. La ragione è molto semplice, abbiamo già creato un ambiente di programmazione C online, in modo che tu possa compilare ed eseguire tutti gli esempi disponibili online contemporaneamente quando svolgi il tuo lavoro teorico. Questo ti dà fiducia in ciò che stai leggendo e per controllare il risultato con diverse opzioni. Sentiti libero di modificare qualsiasi esempio ed eseguirlo online.

Prova il seguente esempio usando il Try it opzione disponibile nell'angolo in alto a destra della casella del codice di esempio -

#include <stdio.h>
int main(){
   /* My first program in C */
   printf("Hello, World! \n");
   return 0;
}

Per la maggior parte degli esempi forniti in questo tutorial, troverai l'opzione Prova, quindi usala e goditi il tuo apprendimento.

Configurazione dell'ambiente locale

Se sei ancora disposto a configurare il tuo ambiente per il linguaggio di programmazione C, hai bisogno dei seguenti due strumenti disponibili sul tuo computer, (a) Editor di testo e (b) Il compilatore C.

Editor di testo

Questo verrà utilizzato per digitare il tuo programma. Esempi di pochi editor includono Blocco note di Windows, comando OS Edit, Brief, Epsilon, EMACS e vim o vi.

Il nome e la versione dell'editor di testo possono variare a seconda dei sistemi operativi. Ad esempio, il Blocco note verrà utilizzato su Windows e vim o vi possono essere utilizzati su Windows, Linux o UNIX.

I file che crei con il tuo editor sono chiamati file sorgente e contengono il codice sorgente del programma. I file sorgente per i programmi C sono in genere denominati con l'estensione ".c".

Prima di iniziare la programmazione, assicurati di disporre di un editor di testo e di avere esperienza sufficiente per scrivere un programma per computer, salvarlo in un file, compilarlo e infine eseguirlo.

Il compilatore C.

Il codice sorgente scritto nel file sorgente è la sorgente leggibile dall'uomo per il tuo programma. Deve essere "compilato", per trasformarsi in linguaggio macchina in modo che la tua CPU possa effettivamente eseguire il programma secondo le istruzioni fornite.

Questo compilatore del linguaggio di programmazione C verrà utilizzato per compilare il codice sorgente in un programma eseguibile finale. Partiamo dal presupposto che tu abbia le conoscenze di base su un compilatore del linguaggio di programmazione.

Il compilatore più frequentemente utilizzato e disponibile gratuitamente è il compilatore GNU C / C ++. In caso contrario, è possibile disporre di compilatori HP o Solaris se si dispone dei rispettivi sistemi operativi (OS).

La sezione seguente ti guida su come installare il compilatore GNU C / C ++ su vari sistemi operativi. Stiamo citando C / C ++ insieme perché il compilatore GNU GCC funziona sia per i linguaggi di programmazione C che C ++.

Installazione su UNIX / Linux

Se stai usando Linux or UNIX, quindi controlla se GCC è installato sul tuo sistema immettendo il seguente comando dalla riga di comando:

$ gcc -v

Se hai il compilatore GNU installato sulla tua macchina, dovrebbe stampare un messaggio come il seguente:

Using built-in specs.
Target: i386-redhat-linux
Configured with: ../configure --prefix = /usr .......
Thread model: posix
gcc version 4.1.2 20080704 (Red Hat 4.1.2-46)

Se GCC non è installato, dovrai installarlo da solo utilizzando le istruzioni dettagliate disponibili su https://gcc.gnu.org/install/

Questo tutorial è stato scritto sulla base di Linux e tutti gli esempi forniti sono stati compilati sulla versione Cent OS del sistema Linux.

Installazione su Mac OS

Se utilizzi Mac OS X, il modo più semplice per ottenere GCC è scaricare l'ambiente di sviluppo Xcode dal sito Web di Apple e seguire le semplici istruzioni di installazione. Dopo aver configurato Xcode, sarai in grado di utilizzare il compilatore GNU per C / C ++.

Xcode è attualmente disponibile su developer.apple.com/technologies/tools/

Installazione su Windows

Per installare GCC su Windows, è necessario installare MinGW. Per installare MinGW, andare alla home page di MinGW, www.mingw.org e seguire il collegamento alla pagina di download di MinGW. Scarica l'ultima versione del programma di installazione MinGW, che dovrebbe essere denominato MinGW- <version> .exe.

Durante l'installazione di MinWG, come minimo, devi installare gcc-core, gcc-g ++, binutils e il runtime MinGW, ma potresti volerne installare di più.

Aggiungi la sottodirectory bin della tua installazione di MinGW al tuo file PATH variabile d'ambiente, in modo da poter specificare questi strumenti sulla riga di comando con i loro semplici nomi.

Quando l'installazione è completa, sarai in grado di eseguire gcc, g ++, ar, ranlib, dlltool e molti altri strumenti GNU dalla riga di comando di Windows.

L'algoritmo è una procedura passo passo, che definisce un insieme di istruzioni da eseguire in un certo ordine per ottenere l'output desiderato. Gli algoritmi sono generalmente creati indipendentemente dai linguaggi sottostanti, cioè un algoritmo può essere implementato in più di un linguaggio di programmazione.

Dal punto di vista della struttura dei dati, di seguito sono riportate alcune importanti categorie di algoritmi:

Search - Algoritmo per cercare un elemento in una struttura dati.
Sort - Algoritmo per ordinare gli elementi in un certo ordine.
Insert - Algoritmo per inserire un elemento in una struttura dati.
Update - Algoritmo per aggiornare un elemento esistente in una struttura dati.
Delete - Algoritmo per eliminare un elemento esistente da una struttura dati.

Caratteristiche di un algoritmo

Non tutte le procedure possono essere chiamate algoritmo. Un algoritmo dovrebbe avere le seguenti caratteristiche:

Unambiguous- L'algoritmo dovrebbe essere chiaro e non ambiguo. Ciascuno dei suoi passaggi (o fasi) e i loro input / output dovrebbero essere chiari e portare a un solo significato.
Input - Un algoritmo dovrebbe avere 0 o più input ben definiti.
Output - Un algoritmo dovrebbe avere 1 o più output ben definiti e dovrebbe corrispondere all'output desiderato.
Finiteness - Gli algoritmi devono terminare dopo un numero finito di passaggi.
Feasibility - Dovrebbe essere fattibile con le risorse disponibili.
Independent - Un algoritmo dovrebbe avere istruzioni passo passo, che dovrebbero essere indipendenti da qualsiasi codice di programmazione.

Come scrivere un algoritmo?

Non esistono standard ben definiti per la scrittura di algoritmi. Piuttosto, dipende dal problema e dalle risorse. Gli algoritmi non vengono mai scritti per supportare un particolare codice di programmazione.

Come sappiamo, tutti i linguaggi di programmazione condividono costrutti di codice di base come loop (do, for, while), controllo del flusso (if-else), ecc. Questi costrutti comuni possono essere usati per scrivere un algoritmo.

Scriviamo algoritmi in modo graduale, ma non è sempre così. La scrittura dell'algoritmo è un processo e viene eseguita dopo che il dominio del problema è ben definito. Cioè, dovremmo conoscere il dominio del problema, per il quale stiamo progettando una soluzione.

Esempio

Proviamo a imparare la scrittura di algoritmi utilizzando un esempio.

Problem - Progettare un algoritmo per aggiungere due numeri e visualizzare il risultato.

Step 1 − START
Step 2 − declare three integers a, b & c
Step 3 − define values of a & b
Step 4 − add values of a & b
Step 5 − store output of step 4 to c
Step 6 − print c
Step 7 − STOP

Gli algoritmi dicono ai programmatori come codificare il programma. In alternativa, l'algoritmo può essere scritto come:

Step 1 − START ADD
Step 2 − get values of a & b
Step 3 − c ← a + b
Step 4 − display c
Step 5 − STOP

Nella progettazione e nell'analisi degli algoritmi, di solito il secondo metodo viene utilizzato per descrivere un algoritmo. Rende facile per l'analista analizzare l'algoritmo ignorando tutte le definizioni indesiderate. Può osservare quali operazioni vengono utilizzate e come scorre il processo.

Scrittura step numbers, è facoltativo.

Progettiamo un algoritmo per ottenere una soluzione di un dato problema. Un problema può essere risolto in più di un modo.

Quindi, molti algoritmi di soluzione possono essere derivati per un dato problema. Il passaggio successivo consiste nell'analizzare gli algoritmi di soluzione proposta e implementare la soluzione più adatta.

Analisi dell'algoritmo

L'efficienza di un algoritmo può essere analizzata in due diverse fasi, prima e dopo l'implementazione. Sono i seguenti:

A Priori Analysis- Questa è un'analisi teorica di un algoritmo. L'efficienza di un algoritmo viene misurata assumendo che tutti gli altri fattori, ad esempio la velocità del processore, siano costanti e non abbiano alcun effetto sull'implementazione.
A Posterior Analysis- Questa è un'analisi empirica di un algoritmo. L'algoritmo selezionato viene implementato utilizzando il linguaggio di programmazione. Questo viene quindi eseguito sul computer di destinazione. In questa analisi vengono raccolte statistiche effettive come il tempo di esecuzione e lo spazio necessario.

Impareremo a conoscere l' analisi algoritmica a priori . L'analisi degli algoritmi si occupa dell'esecuzione o del tempo di esecuzione delle varie operazioni coinvolte. Il tempo di esecuzione di un'operazione può essere definito come il numero di istruzioni del computer eseguite per operazione.

Complessità algoritmo

Supponiamo X è un algoritmo e n è la dimensione dei dati di input, il tempo e lo spazio utilizzati dall'algoritmo X sono i due fattori principali che determinano l'efficienza di X.

Time Factor - Il tempo viene misurato contando il numero di operazioni chiave come i confronti nell'algoritmo di ordinamento.
Space Factor - Lo spazio viene misurato contando lo spazio di memoria massimo richiesto dall'algoritmo.

La complessità di un algoritmo f(n) fornisce il tempo di esecuzione e / o lo spazio di archiviazione richiesto dall'algoritmo in termini di n come la dimensione dei dati di input.

Complessità spaziale

La complessità dello spazio di un algoritmo rappresenta la quantità di spazio di memoria richiesta dall'algoritmo nel suo ciclo di vita. Lo spazio richiesto da un algoritmo è uguale alla somma delle seguenti due componenti:

Una parte fissa che è uno spazio necessario per memorizzare determinati dati e variabili, che sono indipendenti dalla dimensione del problema. Ad esempio, semplici variabili e costanti utilizzate, dimensione del programma, ecc.
Una parte variabile è uno spazio richiesto dalle variabili, la cui dimensione dipende dalla dimensione del problema. Ad esempio, allocazione dinamica della memoria, spazio dello stack di ricorsione, ecc.

La complessità spaziale S (P) di qualsiasi algoritmo P è S (P) = C + SP (I), dove C è la parte fissa e S (I) è la parte variabile dell'algoritmo, che dipende dalla caratteristica dell'istanza I. è un semplice esempio che cerca di spiegare il concetto -

Algorithm: SUM(A, B)
Step 1 -  START
Step 2 -  C ← A + B + 10
Step 3 -  Stop

Qui abbiamo tre variabili A, B e C e una costante. Quindi S (P) = 1 + 3. Ora, lo spazio dipende dai tipi di dati di determinate variabili e tipi di costanti e verrà moltiplicato di conseguenza.

Complessità temporale

La complessità temporale di un algoritmo rappresenta la quantità di tempo richiesta dall'algoritmo per essere eseguito fino al completamento. I requisiti di tempo possono essere definiti come una funzione numerica T (n), dove T (n) può essere misurato come numero di passi, a condizione che ogni passo consuma tempo costante.

Ad esempio, l'aggiunta di due interi a n bit richiede npassi. Di conseguenza, il tempo di calcolo totale è T (n) = c ∗ n, dove c è il tempo impiegato per la somma di due bit. Qui, osserviamo che T (n) cresce linearmente all'aumentare della dimensione dell'input.

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 benissimo concludere il caso migliore, il caso medio e lo scenario peggiore di un algoritmo.

L'analisi asintotica è vincolata all'input, cioè, se non c'è alcun input per l'algoritmo, si conclude che funziona in un tempo costante. Oltre all '"input" tutti gli altri fattori sono considerati costanti.

L'analisi asintotica si riferisce al calcolo del tempo di esecuzione di qualsiasi operazione in unità matematiche di calcolo. Ad esempio, il tempo di esecuzione di un'operazione viene calcolato come f (n) e può essere calcolato come g (n ² ) per un'altra operazione . Ciò significa che il tempo di esecuzione della prima operazione aumenterà linearmente con l'aumento din e il tempo di esecuzione della seconda operazione aumenterà esponenzialmente quando naumenta. Allo stesso modo, il tempo di esecuzione di entrambe le operazioni sarà quasi lo stesso sen è notevolmente piccolo.

Di solito, il tempo richiesto da un algoritmo rientra in tre tipi:

Best Case - Tempo minimo richiesto per l'esecuzione del programma.
Average Case - Tempo medio richiesto per l'esecuzione del programma.
Worst Case - Tempo massimo richiesto per l'esecuzione del programma.

Notazioni asintotiche

Di seguito sono riportate le notazioni asintotiche comunemente utilizzate per calcolare la complessità del tempo di esecuzione di un algoritmo.

Ο Notazione
Notazione Ω
θ Notazione

Notazione Big Oh, Ο

La notazione Ο (n) è il modo formale per esprimere il limite superiore del tempo di esecuzione di un algoritmo. Misura la complessità temporale del caso peggiore o il tempo più lungo che un algoritmo può impiegare per essere completato.

Ad esempio, per una funzione f(n)

Ο(f(n)) = { g(n) : there exists c > 0 and n₀ such that f(n) ≤ c.g(n) for all n > n₀. }

Notazione Omega, Ω

La notazione Ω (n) è il modo formale per esprimere il limite inferiore del tempo di esecuzione di un algoritmo. Misura la migliore complessità temporale del caso o la migliore quantità di tempo che un algoritmo può impiegare per completare.

Ad esempio, per una funzione f(n)

Ω(f(n)) ≥ { g(n) : there exists c > 0 and n₀ such that g(n) ≤ c.f(n) for all n > n₀. }

Notazione Theta, θ

La notazione θ (n) è il modo formale per esprimere sia il limite inferiore che il limite superiore del tempo di esecuzione di un algoritmo. È rappresentato come segue:

θ(f(n)) = { g(n) if and only if g(n) =  Ο(f(n)) and g(n) = Ω(f(n)) for all n > n₀. }

Notazioni asintotiche comuni

Di seguito è riportato un elenco di alcune notazioni asintotiche comuni:

costante	-	Ο (1)
logaritmico	-	Ο (log n)
lineare	-	Ο (n)
n log n	-	Ο (n log n)
quadratico	-	Ο (n ² )
cubo	-	Ο (n ³ )
polinomio	-	n ^{Ο (1)}
esponenziale	-	2 ^{Ο (n)}

Un algoritmo è progettato per ottenere una soluzione ottimale per un dato problema. Nell'approccio dell'algoritmo avido, le decisioni vengono prese dal dominio della soluzione dato. Essendo avido, viene scelta la soluzione più vicina che sembra fornire una soluzione ottimale.

Gli algoritmi avidi cercano di trovare una soluzione ottimale localizzata, che alla fine può portare a soluzioni ottimizzate a livello globale. Tuttavia, gli algoritmi generalmente avidi non forniscono soluzioni ottimizzate a livello globale.

Conteggio delle monete

Questo problema è contare fino a un valore desiderato scegliendo le monete meno possibili e l'approccio avido costringe l'algoritmo a scegliere la moneta più grande possibile. Se ci vengono fornite monete da ₹ 1, 2, 5 e 10 e ci viene chiesto di contare ₹ 18, la procedura avida sarà:

1 - Seleziona una moneta da ₹ 10, il conteggio rimanente è 8
2 - Quindi seleziona una moneta da ₹ 5, il conteggio rimanente è 3
3 - Quindi seleziona una moneta da ₹ 2, il conteggio rimanente è 1
4 - E infine, la selezione di una moneta da ₹ 1 risolve il problema

Tuttavia, sembra che funzioni bene, per questo conteggio dobbiamo scegliere solo 4 monete. Ma se modifichiamo leggermente il problema, lo stesso approccio potrebbe non essere in grado di produrre lo stesso risultato ottimale.

Per il sistema valutario, dove abbiamo monete del valore 1, 7, 10, contare le monete per il valore 18 sarà assolutamente ottimale, ma per contare come 15, potrebbe utilizzare più monete del necessario. Ad esempio, l'approccio avido utilizzerà 10 + 1 + 1 + 1 + 1 + 1, per un totale di 6 monete. Considerando che lo stesso problema potrebbe essere risolto utilizzando solo 3 monete (7 + 7 + 1)

Quindi, possiamo concludere che l'approccio avido sceglie una soluzione ottimizzata immediata e potrebbe fallire laddove l'ottimizzazione globale è una delle principali preoccupazioni.

Esempi

La maggior parte degli algoritmi di rete utilizza l'approccio avido. Ecco un elenco di alcuni di loro:

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

Ci sono molti problemi simili che utilizzano l'approccio avido per trovare una soluzione ottimale.

Nell'approccio divide et impera, il problema alla mano viene suddiviso in sotto-problemi più piccoli e quindi ogni problema viene risolto in modo indipendente. Quando continuiamo a dividere i sottoproblemi in sotto-problemi ancora più piccoli, potremmo eventualmente raggiungere uno stadio in cui non è più possibile alcuna divisione. Quei sottoproblemi "atomici" più piccoli possibili (frazioni) sono risolti. La soluzione di tutti i sottoproblemi viene infine unita per ottenere la soluzione di un problema originale.

In generale, possiamo capire divide-and-conquer approccio in un processo in tre fasi.

Dividi / Spezza

Questo passaggio comporta la suddivisione del problema in sottoproblemi più piccoli. I sottoproblemi dovrebbero rappresentare una parte del problema originale. Questo passaggio generalmente richiede un approccio ricorsivo per dividere il problema fino a quando nessun sottoproblema è ulteriormente divisibile. In questa fase, i problemi secondari diventano di natura atomica ma rappresentano ancora una parte del problema reale.

Conquista / Risolvi

Questo passaggio riceve molti sottoproblemi minori da risolvere. Generalmente, a questo livello, i problemi sono considerati "risolti" da soli.

Unisci / Combina

Quando i sottoproblemi più piccoli vengono risolti, questa fase li combina ricorsivamente fino a formulare una soluzione del problema originale. Questo approccio algoritmico funziona in modo ricorsivo e i passaggi di conquista e unione funzionano così vicini da apparire come uno solo.

Esempi

I seguenti algoritmi informatici si basano su divide-and-conquer approccio di programmazione -

Unisci ordinamento
Ordinamento rapido
Ricerca binaria
La moltiplicazione della matrice di Strassen
Coppia più vicina (punti)

Ci sono vari modi disponibili per risolvere qualsiasi problema del computer, ma quelli menzionati sono un buon esempio di approccio divide et impera.

L'approccio alla programmazione dinamica è simile al divide et impera nella scomposizione del problema in possibili sottoproblemi sempre più piccoli. Ma a differenza di divide et impera, questi problemi secondari non vengono risolti in modo indipendente. Piuttosto, i risultati di questi problemi secondari più piccoli vengono ricordati e utilizzati per problemi secondari simili o sovrapposti.

La programmazione dinamica viene utilizzata dove abbiamo problemi, che possono essere suddivisi in sottoproblemi simili, in modo che i loro risultati possano essere riutilizzati. Per lo più, questi algoritmi vengono utilizzati per l'ottimizzazione. Prima di risolvere il sotto-problema in mano, l'algoritmo dinamico cercherà di esaminare i risultati dei sotto-problemi risolti in precedenza. Le soluzioni dei sottoproblemi vengono combinate per ottenere la migliore soluzione.

Quindi possiamo dire che -

Il problema dovrebbe essere suddiviso in più piccoli sottoproblemi sovrapposti.
Una soluzione ottimale può essere ottenuta utilizzando una soluzione ottimale di sottoproblemi più piccoli.
Gli algoritmi dinamici utilizzano Memoization.

Confronto

In contrasto con gli algoritmi avidi, in cui viene affrontata l'ottimizzazione locale, gli algoritmi dinamici sono motivati per un'ottimizzazione complessiva del problema.

Contrariamente agli algoritmi di divisione e conquista, in cui le soluzioni vengono combinate per ottenere una soluzione globale, gli algoritmi dinamici utilizzano l'output di un sottoproblema più piccolo e quindi cercano di ottimizzare un sotto-problema più grande. Gli algoritmi dinamici utilizzano Memoization per ricordare l'output di sottoproblemi già risolti.

Esempio

I seguenti problemi del computer possono essere risolti utilizzando un approccio di programmazione dinamica:

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

La programmazione dinamica può essere utilizzata sia dall'alto verso il basso che dal basso verso l'alto. E ovviamente, il più delle volte, fare riferimento all'output della soluzione precedente è più economico del ricalcolo in termini di cicli della CPU.

Questo capitolo spiega i termini di base relativi alla struttura dei dati.

Definizione dei dati

La definizione dei dati definisce un dato particolare con le seguenti caratteristiche.

Atomic - La definizione dovrebbe definire un unico concetto.
Traceable - La definizione dovrebbe essere in grado di essere mappata su qualche elemento di dati.
Accurate - La definizione dovrebbe essere univoca.
Clear and Concise - La definizione dovrebbe essere comprensibile.

Oggetto dati

Data Object rappresenta un oggetto con dati.

Tipo di dati

Il tipo di dati è un modo per classificare vari tipi di dati come numero intero, stringa, ecc. Che determina i valori che possono essere utilizzati con il tipo di dati corrispondente, il tipo di operazioni che possono essere eseguite sul tipo di dati corrispondente. Esistono due tipi di dati:

Tipo di dati integrato
Tipo di dati derivato

Tipo di dati integrato

I tipi di dati per i quali una lingua ha un supporto integrato sono noti come tipi di dati incorporati. Ad esempio, la maggior parte delle lingue fornisce i seguenti tipi di dati incorporati.

Integers
Booleano (vero, falso)
Floating (numeri decimali)
Carattere e archi

Tipo di dati derivato

Quei tipi di dati che sono indipendenti dall'implementazione in quanto possono essere implementati in uno o nell'altro modo sono noti come tipi di dati derivati. Questi tipi di dati vengono normalmente creati dalla combinazione di tipi di dati primari o incorporati e dalle operazioni associate su di essi. Ad esempio:

List
Array
Stack
Queue

Operazioni di base

I dati nelle strutture dati vengono elaborati da determinate operazioni. La particolare struttura dati scelta dipende in gran parte dalla frequenza dell'operazione che deve essere eseguita sulla struttura dati.

Traversing
Searching
Insertion
Deletion
Sorting
Merging

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.

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

Un elenco collegato è una sequenza di strutture di dati, che sono collegate tra loro tramite collegamenti.

L'elenco collegato è una sequenza di collegamenti che contiene elementi. Ogni collegamento contiene una connessione a un altro collegamento. L'elenco collegato è la seconda struttura di dati più utilizzata dopo l'array. Di seguito sono riportati i termini importanti per comprendere il concetto di elenco collegato.

Link - Ogni collegamento di un elenco collegato può memorizzare un dato chiamato elemento.
Next - Ogni collegamento di un elenco collegato contiene un collegamento al collegamento successivo denominato Avanti.
LinkedList - Un elenco collegato contiene il collegamento di connessione al primo collegamento denominato Primo.

Rappresentazione dell'elenco collegato

L'elenco collegato può essere visualizzato come una catena di nodi, in cui ogni nodo punta al nodo successivo.

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

L'elenco collegato contiene un elemento di collegamento chiamato per primo.
Ogni collegamento contiene uno o più campi dati e un campo di collegamento chiamato successivo.
Ogni collegamento è collegato al collegamento successivo utilizzando il collegamento successivo.
L'ultimo collegamento porta un collegamento come nullo per contrassegnare la fine dell'elenco.

Tipi di elenchi collegati

Di seguito sono riportati i vari tipi di elenchi collegati.

Simple Linked List - La navigazione degli elementi è solo in avanti.
Doubly Linked List - Gli elementi possono essere spostati avanti e indietro.
Circular Linked List - L'ultimo elemento contiene il collegamento del primo elemento come successivo e il primo elemento ha un collegamento all'ultimo elemento come precedente.

Operazioni di base

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

Insertion - Aggiunge un elemento all'inizio dell'elenco.
Deletion - Elimina un elemento all'inizio della lista.
Display - Visualizza l'elenco completo.
Search - Cerca un elemento utilizzando la chiave data.
Delete - Elimina un elemento utilizzando la chiave fornita.

Operazione di inserimento

L'aggiunta di un nuovo nodo nell'elenco collegato è un'attività in più fasi. Lo impareremo con i diagrammi qui. Per prima cosa, crea un nodo utilizzando la stessa struttura e trova la posizione in cui deve essere inserito.

Immagina di inserire un nodo B (NewNode), tra A (LeftNode) e C(RightNode). Quindi punta B. accanto a C -

NewNode.next −> RightNode;

Dovrebbe assomigliare a questo -

Ora, il nodo successivo a sinistra dovrebbe puntare al nuovo nodo.

LeftNode.next −> NewNode;

Questo metterà il nuovo nodo al centro dei due. Il nuovo elenco dovrebbe apparire così:

Passaggi simili dovrebbero essere eseguiti se il nodo viene inserito all'inizio dell'elenco. Durante l'inserimento alla fine, il penultimo nodo della lista dovrebbe puntare al nuovo nodo e il nuovo nodo punterà a NULL.

Operazione di cancellazione

L'eliminazione è anche un processo in più fasi. Impareremo con la rappresentazione pittorica. Innanzitutto, individuare il nodo di destinazione da rimuovere, utilizzando algoritmi di ricerca.

Il nodo sinistro (precedente) del nodo di destinazione ora dovrebbe puntare al nodo successivo del nodo di destinazione -

LeftNode.next −> TargetNode.next;

Ciò rimuoverà il collegamento che puntava al nodo di destinazione. Ora, utilizzando il codice seguente, rimuoveremo ciò a cui punta il nodo di destinazione.

TargetNode.next −> NULL;

Dobbiamo usare il nodo cancellato. Possiamo tenerlo in memoria altrimenti possiamo semplicemente rilasciare la memoria e cancellare completamente il nodo di destinazione.

Operazione inversa

Questa operazione è completa. Dobbiamo fare in modo che l'ultimo nodo sia puntato dal nodo principale e invertire l'intero elenco collegato.

Per prima cosa, arriviamo alla fine della lista. Dovrebbe puntare a NULL. Ora, indicheremo il suo nodo precedente -

Dobbiamo assicurarci che l'ultimo nodo non sia l'ultimo nodo. Quindi avremo un nodo temporaneo, che assomiglia al nodo head che punta all'ultimo nodo. Ora, faremo in modo che tutti i nodi del lato sinistro puntino ai loro nodi precedenti uno per uno.

Ad eccezione del nodo (primo nodo) puntato dal nodo principale, tutti i nodi dovrebbero puntare al loro predecessore, rendendoli il loro nuovo successore. Il primo nodo punterà a NULL.

Faremo in modo che il nodo head punti al nuovo primo nodo utilizzando il nodo temporaneo.

L'elenco collegato è ora invertito. Per vedere l'implementazione dell'elenco collegato nel linguaggio di programmazione C, fare clic qui .

La lista doppiamente collegata è una variante della lista collegata in cui la navigazione è possibile in entrambi i modi, avanti e indietro facilmente rispetto alla lista collegata singola. Di seguito sono riportati i termini importanti per comprendere il concetto di lista doppiamente collegata.

Link - Ogni collegamento di un elenco collegato può memorizzare un dato chiamato elemento.
Next - Ogni collegamento di un elenco collegato contiene un collegamento al collegamento successivo denominato Avanti.
Prev - Ogni collegamento di un elenco collegato contiene un collegamento al collegamento precedente denominato Prec.
LinkedList - Un elenco collegato contiene il collegamento di connessione al primo collegamento denominato Primo e all'ultimo collegamento denominato Ultimo.

Rappresentazione di elenchi doppiamente collegati

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

La lista doppiamente collegata contiene un elemento di collegamento chiamato primo e ultimo.
Ogni collegamento contiene uno o più campi dati e due campi di collegamento denominati successivo e precedente.
Ogni collegamento è collegato al collegamento successivo utilizzando il collegamento successivo.
Ogni collegamento è collegato al collegamento precedente utilizzando il collegamento precedente.
L'ultimo collegamento porta un collegamento come nullo per contrassegnare la fine dell'elenco.

Operazioni di base

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

Insertion - Aggiunge un elemento all'inizio dell'elenco.
Deletion - Elimina un elemento all'inizio della lista.
Insert Last - Aggiunge un elemento alla fine dell'elenco.
Delete Last - Elimina un elemento dalla fine della lista.
Insert After - Aggiunge un elemento dopo un elemento dell'elenco.
Delete - Elimina un elemento dalla lista utilizzando il tasto.
Display forward - Visualizza l'elenco completo in avanti.
Display backward - Visualizza l'elenco completo in modo arretrato.

Operazione di inserimento

Il codice riportato di seguito mostra l'operazione di inserimento all'inizio di un elenco a doppia connessione.

Esempio

//insert link at the first location
void insertFirst(int key, int data) {

   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
	
   if(isEmpty()) {
      //make it the last link
      last = link;
   } else {
      //update first prev link
      head->prev = link;
   }

   //point it to old first link
   link->next = head;
	
   //point first to new first link
   head = link;
}

Operazione di cancellazione

Il codice seguente mostra l'operazione di eliminazione all'inizio di un elenco a doppio collegamento.

Esempio

//delete first item
struct node* deleteFirst() {

   //save reference to first link
   struct node *tempLink = head;
	
   //if only one link
   if(head->next == NULL) {
      last = NULL;
   } else {
      head->next->prev = NULL;
   }
	
   head = head->next;
	
   //return the deleted link
   return tempLink;
}

Inserimento alla fine di un'operazione

Il codice riportato di seguito mostra l'operazione di inserimento nell'ultima posizione di un elenco a doppia connessione.

Esempio

//insert link at the last location
void insertLast(int key, int data) {

   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
	
   if(isEmpty()) {
      //make it the last link
      last = link;
   } else {
      //make link a new last link
      last->next = link;     
      
      //mark old last node as prev of new link
      link->prev = last;
   }

   //point last to new last node
   last = link;
}

Per vedere l'implementazione nel linguaggio di programmazione C, fare clic qui .

L'elenco collegato circolare è una variazione dell'elenco collegato in cui il primo elemento punta all'ultimo elemento e l'ultimo elemento punta al primo elemento. Sia l'elenco collegato singolarmente che l'elenco collegato in modo doppio possono essere trasformati in un elenco collegato circolare.

Elenco collegato singolarmente come circolare

In un elenco collegato singolarmente, il puntatore successivo dell'ultimo nodo punta al primo nodo.

Elenco doppiamente collegato come circolare

Nella lista doppiamente concatenata, il puntatore successivo dell'ultimo nodo punta al primo nodo e il puntatore precedente del primo nodo punta all'ultimo nodo facendo la circolare in entrambe le direzioni.

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

L'ultimo collegamento punta al primo collegamento dell'elenco in entrambi i casi di elenco collegato sia singolarmente che doppiamente.
Il precedente del primo collegamento punta all'ultimo della lista in caso di lista doppiamente collegata.

Operazioni di base

Di seguito sono riportate le operazioni importanti supportate da un elenco circolare.

insert - Inserisce un elemento all'inizio della lista.
delete - Elimina un elemento dall'inizio della lista.
display - Visualizza l'elenco.

Operazione di inserimento

Il codice seguente mostra l'operazione di inserimento in un elenco collegato circolare basato su un singolo elenco collegato.

Esempio

//insert link at the first location
void insertFirst(int key, int data) {
   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data= data;
	
   if (isEmpty()) {
      head = link;
      head->next = head;
   } else {
      //point it to old first node
      link->next = head;
		
      //point first to new first node
      head = link;
   }   
}

Operazione di cancellazione

Il codice seguente illustra l'operazione di eliminazione in un elenco collegato circolare basato su un singolo elenco collegato.

//delete first item
struct node * deleteFirst() {
   //save reference to first link
   struct node *tempLink = head;
	
   if(head->next == head) {  
      head = NULL;
      return tempLink;
   }     

   //mark next to first link as first 
   head = head->next;
	
   //return the deleted link
   return tempLink;
}

Operazione elenco display

Il codice seguente mostra l'operazione dell'elenco di visualizzazione in un elenco collegato circolare.

//display the list
void printList() {
   struct node *ptr = head;
   printf("\n[ ");
	
   //start from the beginning
   if(head != NULL) {
      while(ptr->next != ptr) {     
         printf("(%d,%d) ",ptr->key,ptr->data);
         ptr = ptr->next;
      }
   }
	
   printf(" ]");
}

Per conoscere la sua implementazione nel linguaggio di programmazione C, fare clic qui .

Uno stack è un tipo di dati astratto (ADT), comunemente utilizzato nella maggior parte dei linguaggi di programmazione. Si chiama pila poiché si comporta come una pila del mondo reale, ad esempio: un mazzo di carte o una pila di piatti, ecc.

Uno stack del mondo reale consente operazioni da una sola estremità. Ad esempio, possiamo posizionare o rimuovere una carta o un piatto solo dalla parte superiore della pila. Allo stesso modo, Stack ADT consente tutte le operazioni sui dati solo a un'estremità. In qualsiasi momento, possiamo accedere solo all'elemento superiore di uno stack.

Questa caratteristica rende la struttura dati LIFO. LIFO sta per Last-in-first-out. Qui si accede per primo all'elemento posizionato (inserito o aggiunto) per ultimo. Nella terminologia dello stack, viene chiamata l'operazione di inserimentoPUSH viene chiamata l'operazione di operazione e rimozione POP operazione.

Rappresentazione in pila

Il diagramma seguente illustra uno stack e le sue operazioni:

Uno stack può essere implementato mediante Array, Structure, Pointer e Linked List. Lo stack può essere di dimensioni fisse o può avere un senso di ridimensionamento dinamico. Qui, implementeremo lo stack utilizzando gli array, il che lo rende un'implementazione dello stack di dimensioni fisse.

Operazioni di base

Le operazioni sullo stack possono comportare l'inizializzazione dello stack, il suo utilizzo e quindi la de-inizializzazione. Oltre a questi elementi di base, uno stack viene utilizzato per le seguenti due operazioni principali:

push() - Spingere (immagazzinare) un elemento sullo stack.
pop() - Rimozione (accesso) di un elemento dalla pila.

Quando i dati vengono inseriti nello stack.

Per utilizzare uno stack in modo efficiente, dobbiamo controllare anche lo stato dello stack. Per lo stesso scopo, la seguente funzionalità viene aggiunta agli stack:

peek() - ottenere l'elemento dati superiore dello stack, senza rimuoverlo.
isFull() - controlla se lo stack è pieno.
isEmpty() - controlla se lo stack è vuoto.

In ogni momento, manteniamo un puntatore agli ultimi dati PUSH nello stack. Poiché questo puntatore rappresenta sempre la parte superiore dello stack, da qui denominatotop. Iltop il puntatore fornisce il valore superiore dello stack senza rimuoverlo effettivamente.

Per prima cosa dovremmo conoscere le procedure per supportare le funzioni dello stack -

sbirciare()

Algoritmo della funzione peek () -

begin procedure peek
   return stack[top]
end procedure

Implementazione della funzione peek () nel linguaggio di programmazione C -

Example

int peek() {
   return stack[top];
}

è pieno()

Algoritmo della funzione isfull () -

begin procedure isfull

   if top equals to MAXSIZE
      return true
   else
      return false
   endif
   
end procedure

Implementazione della funzione isfull () nel linguaggio di programmazione C -

Example

bool isfull() {
   if(top == MAXSIZE)
      return true;
   else
      return false;
}

è vuoto()

Algoritmo della funzione isempty () -

begin procedure isempty

   if top less than 1
      return true
   else
      return false
   endif
   
end procedure

L'implementazione della funzione isempty () nel linguaggio di programmazione C è leggermente diversa. Inizializziamo top a -1, poiché l'indice nell'array inizia da 0. Quindi controlliamo se il top è sotto zero o -1 per determinare se lo stack è vuoto. Ecco il codice -

Example

bool isempty() {
   if(top == -1)
      return true;
   else
      return false;
}

Operazione push

Il processo di inserimento di un nuovo elemento di dati nello stack è noto come operazione push. L'operazione push prevede una serie di passaggi:

Step 1 - Controlla se la pila è piena.
Step 2 - Se lo stack è pieno, produce un errore ed esce.
Step 3 - Se la pila non è piena, aumenta top per indicare il prossimo spazio vuoto.
Step 4 - Aggiunge un elemento dati alla posizione dello stack, dove punta in alto.
Step 5 - Restituisce il successo.

Se l'elenco collegato viene utilizzato per implementare lo stack, al passaggio 3 è necessario allocare lo spazio in modo dinamico.

Algoritmo per l'operazione PUSH

Un semplice algoritmo per l'operazione Push può essere derivato come segue:

begin procedure push: stack, data

   if stack is full
      return null
   endif
   
   top ← top + 1
   stack[top] ← data

end procedure

L'implementazione di questo algoritmo in C è molto semplice. Vedere il codice seguente -

Example

void push(int data) {
   if(!isFull()) {
      top = top + 1;   
      stack[top] = data;
   } else {
      printf("Could not insert data, Stack is full.\n");
   }
}

Operazione Pop

L'accesso al contenuto mentre lo si rimuove dallo stack è noto come operazione pop. In un'implementazione di matrice dell'operazione pop (), l'elemento data non viene effettivamente rimosso, invecetopviene decrementato in una posizione inferiore nello stack per puntare al valore successivo. Ma nell'implementazione dell'elenco collegato, pop () rimuove effettivamente l'elemento dati e rilascia lo spazio di memoria.

Un'operazione Pop può comportare i seguenti passaggi:

Step 1 - Controlla se la pila è vuota.
Step 2 - Se lo stack è vuoto, produce un errore ed esce.
Step 3 - Se lo stack non è vuoto, accede all'elemento di dati in cui top sta indicando.
Step 4 - Diminuisce il valore di top di 1.
Step 5 - Restituisce il successo.

Algoritmo per l'operazione Pop

Un semplice algoritmo per l'operazione Pop può essere derivato come segue:

begin procedure pop: stack

   if stack is empty
      return null
   endif
   
   data ← stack[top]
   top ← top - 1
   return data

end procedure

L'implementazione di questo algoritmo in C è la seguente:

Example

int pop(int data) {

   if(!isempty()) {
      data = stack[top];
      top = top - 1;   
      return data;
   } else {
      printf("Could not retrieve data, Stack is empty.\n");
   }
}

Per un programma stack completo in linguaggio di programmazione C, fare clic qui .

Il modo per scrivere espressioni aritmetiche è noto come a notation. Un'espressione aritmetica può essere scritta in tre notazioni diverse ma equivalenti, cioè senza cambiare l'essenza o l'output di un'espressione. Queste notazioni sono:

Notazione infissa
Notazione prefisso (polacco)
Notazione Postfix (Reverse-Polish)

Queste notazioni prendono il nome dal modo in cui usano l'operatore nell'espressione. Impareremo lo stesso qui in questo capitolo.

Notazione infissa

Scriviamo espressione in infix notazione, ad esempio a - b + c, dove vengono utilizzati gli operatori in-tra operandi. È facile per noi umani leggere, scrivere e parlare in notazione infissa, ma lo stesso non va bene con i dispositivi informatici. Un algoritmo per elaborare la notazione infissa potrebbe essere difficile e costoso in termini di consumo di tempo e spazio.

Notazione prefisso

In questa notazione, l'operatore è prefixed agli operandi, cioè l'operatore viene scritto prima degli operandi. Per esempio,+ab. Questo è equivalente alla sua notazione infissaa + b. La notazione del prefisso è anche nota comePolish Notation.

Notazione postfissa

Questo stile di notazione è noto come Reversed Polish Notation. In questo stile di notazione, l'operatore èpostfixed agli operandi, cioè l'operatore viene scritto dopo gli operandi. Per esempio,ab+. Questo è equivalente alla sua notazione infissaa + b.

La tabella seguente cerca brevemente di mostrare la differenza in tutte e tre le notazioni:

Sr.No.	Notazione infissa	Notazione prefisso	Notazione postfissa
1	a + b	+ ab	ab +
2	(a + b) ∗ c	∗ + abc	ab + c ∗
3	a ∗ (b + c)	∗ a + bc	abc + ∗
4	a / b + c / d	+ / ab / cd	ab / cd / +
5	(a + b) ∗ (c + d)	∗ + ab + cd	ab + cd + ∗
6	((a + b) ∗ c) - d	- ∗ + abcd	ab + c ∗ d -

Espressioni di analisi

Come abbiamo discusso, non è un modo molto efficiente per progettare un algoritmo o un programma per analizzare le notazioni infisse. Invece, queste notazioni con infisso vengono prima convertite in notazioni con suffisso o prefisso e quindi calcolate.

Per analizzare qualsiasi espressione aritmetica, dobbiamo occuparci anche della precedenza e dell'associatività degli operatori.

Precedenza

Quando un operando si trova tra due diversi operatori, quale operatore prenderà l'operando per primo, viene deciso dalla precedenza di un operatore sugli altri. Ad esempio:

Poiché l'operazione di moltiplicazione ha la precedenza sull'addizione, b * c verrà valutato per primo. In seguito viene fornita una tabella di precedenza degli operatori.

Associatività

L'associatività descrive la regola in cui gli operatori con la stessa precedenza vengono visualizzati in un'espressione. Ad esempio, nell'espressione a + b - c, sia + che - hanno la stessa precedenza, quindi quale parte dell'espressione verrà valutata per prima è determinata dall'associatività di tali operatori. Qui, sia + che - sono associativi a sinistra, quindi l'espressione verrà valutata come(a + b) − c.

La precedenza e l'associatività determinano l'ordine di valutazione di un'espressione. Di seguito è riportata una tabella di precedenza e associatività degli operatori (dalla più alta alla più bassa):

Sr.No.	Operatore	Precedenza	Associatività
1	Esponenziazione ^	Più alta	Right Associative
2	Moltiplicazione (∗) e divisione (/)	Secondo più alto	Associativo di sinistra
3	Addizione (+) e sottrazione (-)	Il più basso	Associativo di sinistra

La tabella sopra mostra il comportamento predefinito degli operatori. In qualsiasi momento della valutazione dell'espressione, l'ordine può essere modificato utilizzando le parentesi. Ad esempio:

In a + b*c, la parte dell'espressione b*csarà valutato per primo, con la moltiplicazione come precedenza sull'addizione. Usiamo qui la parentesi pera + b da valutare prima, come (a + b)*c.

Algoritmo di valutazione Postfix

Vedremo ora l'algoritmo su come valutare la notazione suffissa -

Step 1 − scan the expression from left to right 
Step 2 − if it is an operand push it to stack 
Step 3 − if it is an operator pull operand from stack and perform operation 
Step 4 − store the output of step 3, back to stack 
Step 5 − scan the expression until all operands are consumed 
Step 6 − pop the stack and perform operation

Per vedere l'implementazione nel linguaggio di programmazione C, fare clic qui .

La coda è una struttura dati astratta, in qualche modo simile a Stack. A differenza degli stack, una coda è 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.

Un esempio reale di coda può essere una strada a senso unico a una corsia, in cui il veicolo entra per primo, esce per primo. Altri esempi del mondo reale possono essere visti come code alle biglietterie e alle fermate degli autobus.

Rappresentazione in coda

Poiché ora sappiamo che in coda, accediamo a entrambe le estremità per motivi diversi. Il diagramma seguente riportato di seguito cerca di spiegare la rappresentazione della coda come struttura dati:

Come negli stack, una coda può anche essere implementata utilizzando array, elenchi collegati, puntatori e strutture. Per semplicità, implementeremo le code utilizzando un array unidimensionale.

Operazioni di base

Le operazioni di coda possono comportare l'inizializzazione o la definizione della coda, il suo utilizzo e quindi la sua cancellazione completa dalla memoria. Qui proveremo a capire le operazioni di base associate alle code:

enqueue() - aggiungi (immagazzina) un articolo alla coda.
dequeue() - rimuovere (accedere) un elemento dalla coda.

Sono necessarie poche altre funzioni per rendere efficiente l'operazione di coda sopra menzionata. Questi sono -

peek() - Ottiene l'elemento all'inizio della coda senza rimuoverlo.
isfull() - Controlla se la coda è piena.
isempty() - Controlla se la coda è vuota.

In coda, rimuoviamo sempre dalla coda (o accediamo) i dati, indicati da front puntatore e mentre accodiamo (o memorizziamo) i dati nella coda ci aiutiamo rear puntatore.

Impariamo prima le funzioni di supporto di una coda:

sbirciare()

Questa funzione aiuta a vedere i dati in frontdella coda. L'algoritmo della funzione peek () è il seguente:

Algorithm

begin procedure peek
   return queue[front]
end procedure

Implementazione della funzione peek () nel linguaggio di programmazione C -

Example

int peek() {
   return queue[front];
}

è pieno()

Poiché stiamo utilizzando un array a dimensione singola per implementare la coda, controlliamo semplicemente che il puntatore posteriore raggiunga MAXSIZE per determinare che la coda è piena. Nel caso in cui manteniamo la coda in una lista collegata circolare, l'algoritmo sarà diverso. Algoritmo della funzione isfull () -

Algorithm

begin procedure isfull

   if rear equals to MAXSIZE
      return true
   else
      return false
   endif
   
end procedure

Implementazione della funzione isfull () nel linguaggio di programmazione C -

Example

bool isfull() {
   if(rear == MAXSIZE - 1)
      return true;
   else
      return false;
}

è vuoto()

Algoritmo della funzione isempty () -

Algorithm

begin procedure isempty

   if front is less than MIN  OR front is greater than rear
      return true
   else
      return false
   endif
   
end procedure

Se il valore di front è minore di MIN o 0, indica che la coda non è ancora inizializzata, quindi vuota.

Ecco il codice di programmazione C -

Example

bool isempty() {
   if(front < 0 || front > rear) 
      return true;
   else
      return false;
}

Accodamento operazione

Le code mantengono due puntatori dati, front e rear. Pertanto, le sue operazioni sono relativamente difficili da implementare rispetto a quelle degli stack.

I seguenti passaggi dovrebbero essere eseguiti per accodare (inserire) i dati in una coda:

Step 1 - Controlla se la coda è piena.
Step 2 - Se la coda è piena, produce un errore di overflow ed esce.
Step 3 - Se la coda non è piena, incrementare rear puntatore per puntare il successivo spazio vuoto.
Step 4 - Aggiungi un elemento di dati alla posizione della coda, dove punta la parte posteriore.
Step 5 - restituire il successo.

A volte, controlliamo anche se una coda è inizializzata o meno, per gestire eventuali situazioni impreviste.

Algoritmo per l'operazione di accodamento

procedure enqueue(data)      
   
   if queue is full
      return overflow
   endif
   
   rear ← rear + 1
   queue[rear] ← data
   return true
   
end procedure

Implementazione di enqueue () nel linguaggio di programmazione C -

Example

int enqueue(int data)      
   if(isfull())
      return 0;
   
   rear = rear + 1;
   queue[rear] = data;
   
   return 1;
end procedure

Operazione di rimozione dalla coda

L'accesso ai dati dalla coda è un processo di due attività: accedere ai dati dove frontsta puntando e rimuovere i dati dopo l'accesso. Per eseguire i passaggi seguentidequeue operazione -

Step 1 - Controlla se la coda è vuota.
Step 2 - Se la coda è vuota, produce un errore di underflow ed esce.
Step 3 - Se la coda non è vuota, accedere ai dati dove front sta indicando.
Step 4 - Incremento front puntatore per puntare al successivo elemento di dati disponibile.
Step 5 - Restituire il successo.

Algoritmo per l'operazione di rimozione dalla coda

procedure dequeue
   
   if queue is empty
      return underflow
   end if

   data = queue[front]
   front ← front + 1
   return true

end procedure

Implementazione di dequeue () nel linguaggio di programmazione C -

Example

int dequeue() {
   if(isempty())
      return 0;

   int data = queue[front];
   front = front + 1;

   return data;
}

Per un programma Queue completo in linguaggio di programmazione C, fare clic qui .

La ricerca lineare è un algoritmo di ricerca molto semplice. In questo tipo di ricerca, viene eseguita una ricerca sequenziale su tutti gli elementi uno per uno. Ogni elemento viene controllato e se viene trovata una corrispondenza, viene restituito quel particolare elemento, altrimenti la ricerca continua fino alla fine della raccolta dei dati.

Algoritmo

Linear Search ( Array A, Value x)

Step 1: Set i to 1
Step 2: if i > n then go to step 7
Step 3: if A[i] = x then go to step 6
Step 4: Set i to i + 1
Step 5: Go to Step 2
Step 6: Print Element x Found at index i and go to step 8
Step 7: Print element not found
Step 8: Exit

Pseudocodice

procedure linear_search (list, value)

   for each item in the list
      if match item == value
         return the item's location
      end if
   end for

end procedure

Per conoscere l'implementazione della ricerca lineare nel linguaggio di programmazione C, fare clic qui .

La ricerca binaria è un algoritmo di ricerca veloce con complessità di runtime di Ο (log n). Questo algoritmo di ricerca funziona sul principio del divide et impera. Affinché questo algoritmo funzioni correttamente, la raccolta dei dati dovrebbe essere nella forma ordinata.

La ricerca binaria cerca un elemento particolare confrontando l'elemento più centrale della raccolta. Se si verifica una corrispondenza, viene restituito l'indice dell'elemento. Se l'elemento centrale è maggiore dell'elemento, l'elemento viene cercato nel sotto-array a sinistra dell'elemento centrale. In caso contrario, l'elemento viene cercato nel sotto-array a destra dell'elemento centrale. Questo processo continua anche sul sottoarray finché la dimensione del sottoarray non si riduce a zero.

Come funziona la ricerca binaria?

Affinché una ricerca binaria funzioni, è obbligatorio ordinare l'array di destinazione. Impareremo il processo di ricerca binaria con un esempio pittorico. Quello che segue è il nostro array ordinato e supponiamo di dover cercare la posizione del valore 31 utilizzando la ricerca binaria.

Per prima cosa, determineremo metà dell'array usando questa formula:

mid = low + (high - low) / 2

Eccolo, 0 + (9-0) / 2 = 4 (valore intero di 4,5). Quindi, 4 è la metà della matrice.

Ora confrontiamo il valore memorizzato nella posizione 4, con il valore che si sta cercando, cioè 31. Troviamo che il valore nella posizione 4 è 27, che non è una corrispondenza. Poiché il valore è maggiore di 27 e abbiamo un array ordinato, sappiamo anche che il valore di destinazione deve essere nella parte superiore dell'array.

Modifichiamo il nostro valore medio + 1 e troviamo di nuovo il nuovo valore medio.

low = mid + 1
mid = low + (high - low) / 2

La nostra nuova metà ora ha 7 anni. Confrontiamo il valore memorizzato nella posizione 7 con il nostro valore target 31.

Il valore memorizzato nella posizione 7 non è una corrispondenza, piuttosto è più di quello che stiamo cercando. Quindi, il valore deve essere nella parte inferiore di questa posizione.

Quindi, calcoliamo di nuovo la metà. Questa volta sono le 5.

Confrontiamo il valore memorizzato nella posizione 5 con il nostro valore target. Troviamo che sia una corrispondenza.

Concludiamo che il valore target 31 è memorizzato nella posizione 5.

La ricerca binaria dimezza gli elementi ricercabili e quindi riduce il conteggio dei confronti da effettuare a numeri molto inferiori.

Pseudocodice

Lo pseudocodice degli algoritmi di ricerca binaria dovrebbe essere simile a questo:

Procedure binary_search
   A ← sorted array
   n ← size of array
   x ← value to be searched

   Set lowerBound = 1
   Set upperBound = n 

   while x not found
      if upperBound < lowerBound 
         EXIT: x does not exists.
   
      set midPoint = lowerBound + ( upperBound - lowerBound ) / 2
      
      if A[midPoint] < x
         set lowerBound = midPoint + 1
         
      if A[midPoint] > x
         set upperBound = midPoint - 1 

      if A[midPoint] = x 
         EXIT: x found at location midPoint
   end while
   
end procedure

Per conoscere l'implementazione della ricerca binaria utilizzando array nel linguaggio di programmazione C, fare clic qui .

La ricerca in interpolazione è una variante migliorata della ricerca binaria. Questo algoritmo di ricerca funziona sulla posizione di rilevamento del valore richiesto. Affinché questo algoritmo funzioni correttamente, la raccolta dei dati deve essere in una forma ordinata e distribuita equamente.

La ricerca binaria ha un enorme vantaggio in termini di complessità temporale rispetto alla ricerca lineare. La ricerca lineare ha la complessità nel caso peggiore di Ο (n) mentre la ricerca binaria ha Ο (log n).

Ci sono casi in cui la posizione dei dati di destinazione può essere nota in anticipo. Ad esempio, nel caso di un elenco telefonico, se vogliamo cercare il numero di telefono di Morphius. Qui, la ricerca lineare e anche la ricerca binaria sembreranno lente poiché possiamo saltare direttamente allo spazio di memoria in cui sono memorizzati i nomi che iniziano con "M".

Posizionamento nella ricerca binaria

Nella ricerca binaria, se i dati desiderati non vengono trovati, il resto dell'elenco viene diviso in due parti, inferiore e superiore. La ricerca viene eseguita in uno di essi.

Anche quando i dati vengono ordinati, la ricerca binaria non sfrutta i vantaggi per sondare la posizione dei dati desiderati.

Rilevamento della posizione nella ricerca in interpolazione

La ricerca per interpolazione trova un particolare elemento calcolando la posizione della sonda. Inizialmente, la posizione della sonda è la posizione dell'elemento più centrale della collezione.

Se si verifica una corrispondenza, viene restituito l'indice dell'articolo. Per dividere l'elenco in due parti, utilizziamo il seguente metodo:

mid = Lo + ((Hi - Lo) / (A[Hi] - A[Lo])) * (X - A[Lo])

where −
   A    = list
   Lo   = Lowest index of the list
   Hi   = Highest index of the list
   A[n] = Value stored at index n in the list

Se l'elemento centrale è maggiore dell'elemento, la posizione della sonda viene nuovamente calcolata nel sotto-array a destra dell'elemento centrale. In caso contrario, l'elemento viene cercato nel sottoarray a sinistra dell'elemento centrale. Questo processo continua anche sul sottoarray fino a quando la dimensione del sottoarray non si riduce a zero.

La complessità di runtime dell'algoritmo di ricerca di interpolazione è Ο(log (log n)) paragonato a Ο(log n) della BST in situazioni favorevoli.

Algoritmo

Poiché è un'improvvisazione dell'algoritmo BST esistente, stiamo menzionando i passaggi per cercare l'indice del valore dei dati 'target', utilizzando il rilevamento della posizione -

Step 1 − Start searching data from middle of the list.
Step 2 − If it is a match, return the index of the item, and exit.
Step 3 − If it is not a match, probe position.
Step 4 − Divide the list using probing formula and find the new midle.
Step 5 − If data is greater than middle, search in higher sub-list.
Step 6 − If data is smaller than middle, search in lower sub-list.
Step 7 − Repeat until match.

Pseudocodice

A → Array list
N → Size of A
X → Target Value

Procedure Interpolation_Search()

   Set Lo  →  0
   Set Mid → -1
   Set Hi  →  N-1

   While X does not match
   
      if Lo equals to Hi OR A[Lo] equals to A[Hi]
         EXIT: Failure, Target not found
      end if
      
      Set Mid = Lo + ((Hi - Lo) / (A[Hi] - A[Lo])) * (X - A[Lo]) 

      if A[Mid] = X
         EXIT: Success, Target found at Mid
      else 
         if A[Mid] < X
            Set Lo to Mid+1
         else if A[Mid] > X
            Set Hi to Mid-1
         end if
      end if
   End While

End Procedure

Per conoscere l'implementazione della ricerca per interpolazione nel linguaggio di programmazione C, fare clic qui .

La tabella hash è una struttura dati che memorizza i dati in modo associativo. In una tabella hash, i dati vengono archiviati in un formato array, in cui ogni valore di dati ha il proprio valore di indice univoco. L'accesso ai dati diventa molto veloce se conosciamo l'indice dei dati desiderati.

Diventa così una struttura di dati in cui le operazioni di inserimento e ricerca sono molto veloci indipendentemente dalla dimensione dei dati. Hash Table utilizza un array come supporto di memorizzazione e utilizza la tecnica hash per generare un indice in cui deve essere inserito un elemento o da cui deve essere individuato.

Hashing

L'hashing è una tecnica per convertire un intervallo di valori chiave in un intervallo di indici di un array. Useremo l'operatore modulo per ottenere un intervallo di valori chiave. Si consideri un esempio di tabella hash di dimensione 20 e gli elementi seguenti devono essere archiviati. Gli articoli sono nel formato (chiave, valore).

(1,20)
(2,70)
(42,80)
(4,25)
(12,44)
(14,32)
(17,11)
(13,78)
(37,98)

Sr.No.	Chiave	Hash	Indice array
1	1	1% 20 = 1	1
2	2	2% 20 = 2	2
3	42	42% 20 = 2	2
4	4	4% 20 = 4	4
5	12	12% 20 = 12	12
6	14	14% 20 = 14	14
7	17	17% 20 = 17	17
8	13	13% 20 = 13	13
9	37	37% 20 = 17	17

Sondaggio lineare

Come possiamo vedere, può capitare che la tecnica di hashing venga utilizzata per creare un indice dell'array già utilizzato. In tal caso, possiamo cercare la successiva posizione vuota nell'array guardando nella cella successiva finché non troviamo una cella vuota. Questa tecnica è chiamata sondaggio lineare.

Sr.No.	Chiave	Hash	Indice array	Dopo il rilevamento lineare, indice di matrice
1	1	1% 20 = 1	1	1
2	2	2% 20 = 2	2	2
3	42	42% 20 = 2	2	3
4	4	4% 20 = 4	4	4
5	12	12% 20 = 12	12	12
6	14	14% 20 = 14	14	14
7	17	17% 20 = 17	17	17
8	13	13% 20 = 13	13	13
9	37	37% 20 = 17	17	18

Operazioni di base

Di seguito sono riportate le operazioni principali di base di una tabella hash.

Search - Cerca un elemento in una tabella hash.
Insert - inserisce un elemento in una tabella hash.
delete - Elimina un elemento da una tabella hash.

DataItem

Definire un elemento di dati con alcuni dati e una chiave, in base al quale deve essere condotta la ricerca in una tabella hash.

struct DataItem {
   int data;
   int key;
};

Metodo hash

Definire un metodo di hashing per calcolare il codice hash della chiave dell'elemento dati.

int hashCode(int key){
   return key % SIZE;
}

Operazione di ricerca

Ogni volta che si deve cercare un elemento, calcolare il codice hash della chiave passata e individuare l'elemento utilizzando tale codice hash come indice nell'array. Utilizzare il rilevamento lineare per portare l'elemento avanti se l'elemento non viene trovato nel codice hash calcolato.

Esempio

struct DataItem *search(int key) {
   //get the hash
   int hashIndex = hashCode(key);
	
   //move in array until an empty
   while(hashArray[hashIndex] != NULL) {
	
      if(hashArray[hashIndex]->key == key)
         return hashArray[hashIndex];
			
      //go to next cell
      ++hashIndex;
		
      //wrap around the table
      hashIndex %= SIZE;
   }

   return NULL;        
}

Inserisci operazione

Ogni volta che deve essere inserito un elemento, calcolare il codice hash della chiave passata e individuare l'indice utilizzando tale codice hash come indice nell'array. Utilizzare il rilevamento lineare per la posizione vuota, se viene trovato un elemento nel codice hash calcolato.

Esempio

void insert(int key,int data) {
   struct DataItem *item = (struct DataItem*) malloc(sizeof(struct DataItem));
   item->data = data;  
   item->key = key;     

   //get the hash 
   int hashIndex = hashCode(key);

   //move in array until an empty or deleted cell
   while(hashArray[hashIndex] != NULL && hashArray[hashIndex]->key != -1) {
      //go to next cell
      ++hashIndex;
		
      //wrap around the table
      hashIndex %= SIZE;
   }
	
   hashArray[hashIndex] = item;        
}

Elimina operazione

Ogni volta che un elemento deve essere eliminato, calcolare il codice hash della chiave passata e individuare l'indice utilizzando tale codice hash come indice nella matrice. Utilizzare il rilevamento lineare per portare l'elemento avanti se un elemento non viene trovato nel codice hash calcolato. Una volta trovato, memorizza un elemento fittizio lì per mantenere intatte le prestazioni della tabella hash.

Esempio

struct DataItem* delete(struct DataItem* item) {
   int key = item->key;

   //get the hash 
   int hashIndex = hashCode(key);

   //move in array until an empty 
   while(hashArray[hashIndex] !=NULL) {
	
      if(hashArray[hashIndex]->key == key) {
         struct DataItem* temp = hashArray[hashIndex]; 
			
         //assign a dummy item at deleted position
         hashArray[hashIndex] = dummyItem; 
         return temp;
      } 
		
      //go to next cell
      ++hashIndex;
		
      //wrap around the table
      hashIndex %= SIZE;
   }  
	
   return NULL;        
}

Per conoscere l'implementazione dell'hash nel linguaggio di programmazione C, fare clic qui .

L'ordinamento si riferisce alla disposizione dei dati in un formato particolare. L'algoritmo di ordinamento specifica il modo in cui disporre i dati in un ordine particolare. Gli ordini più comuni sono in ordine numerico o lessicografico.

L'importanza dell'ordinamento risiede nel fatto che la ricerca dei dati può essere ottimizzata a un livello molto alto, se i dati vengono memorizzati in modo ordinato. L'ordinamento viene utilizzato anche per rappresentare i dati in formati più leggibili. Di seguito sono riportati alcuni esempi di ordinamento in scenari di vita reale:

Telephone Directory - La rubrica telefonica memorizza i numeri di telefono delle persone ordinate per nome, in modo che i nomi possano essere cercati facilmente.
Dictionary - Il dizionario memorizza le parole in ordine alfabetico in modo che la ricerca di qualsiasi parola diventi facile.

Ordinamento sul posto e Ordinamento non sul posto

Gli algoritmi di ordinamento possono richiedere uno spazio aggiuntivo per il confronto e l'archiviazione temporanea di pochi elementi di dati. Questi algoritmi non richiedono spazio aggiuntivo e si dice che l'ordinamento avvenga sul posto o, ad esempio, all'interno dell'array stesso. Questo è chiamatoin-place sorting. Bubble sort è un esempio di ordinamento sul posto.

Tuttavia, in alcuni algoritmi di ordinamento, il programma richiede uno spazio maggiore o uguale agli elementi da ordinare. Viene chiamato l'ordinamento che utilizza uno spazio uguale o maggiorenot-in-place sorting. Merge-sort è un esempio di ordinamento non sul posto.

Ordinamento stabile e non stabile

Se un algoritmo di ordinamento, dopo aver ordinato i contenuti, non cambia la sequenza di contenuti simili in cui compaiono, viene chiamato stable sorting.

Se un algoritmo di ordinamento, dopo aver ordinato i contenuti, cambia la sequenza di contenuti simili in cui compaiono, viene chiamato unstable sorting.

La stabilità di un algoritmo è importante quando desideriamo mantenere la sequenza di elementi originali, come ad esempio in una tupla.

Algoritmo di ordinamento adattivo e non adattivo

Un algoritmo di ordinamento si dice che sia adattivo, se sfrutta gli elementi già "ordinati" nell'elenco che deve essere ordinato. Cioè, durante l'ordinamento se l'elenco di origine ha qualche elemento già ordinato, gli algoritmi adattivi ne terranno conto e proveranno a non riordinarli.

Un algoritmo non adattivo è uno che non tiene conto degli elementi che sono già ordinati. Cercano di forzare il riordino di ogni singolo elemento per confermare la loro ordinamento.

Termini importanti

Alcuni termini sono generalmente coniati durante la discussione delle tecniche di ordinamento, ecco una breve introduzione ad essi:

Ordine crescente

Si dice che sia presente una sequenza di valori increasing order, se l'elemento successivo è maggiore del precedente. Ad esempio, 1, 3, 4, 6, 8, 9 sono in ordine crescente, poiché ogni elemento successivo è maggiore dell'elemento precedente.

Ordine decrescente

Si dice che sia presente una sequenza di valori decreasing order, se l'elemento successivo è minore di quello corrente. Ad esempio, 9, 8, 6, 4, 3, 1 sono in ordine decrescente, poiché ogni elemento successivo è minore dell'elemento precedente.

Ordine non crescente

Si dice che sia presente una sequenza di valori non-increasing order, se l'elemento successivo è minore o uguale al suo elemento precedente nella sequenza. Questo ordine si verifica quando la sequenza contiene valori duplicati. Ad esempio, 9, 8, 6, 3, 3, 1 sono in ordine non crescente, poiché ogni elemento successivo è minore o uguale a (nel caso di 3) ma non maggiore di qualsiasi elemento precedente.

Ordine non decrescente

Si dice che sia presente una sequenza di valori non-decreasing order, se l'elemento successivo è maggiore o uguale al suo elemento precedente nella sequenza. Questo ordine si verifica quando la sequenza contiene valori duplicati. Ad esempio, 1, 3, 3, 6, 8, 9 sono in ordine non decrescente, poiché ogni elemento successivo è maggiore o uguale a (nel caso di 3) ma non inferiore al precedente.

Bubble sort è un semplice algoritmo di ordinamento. Questo algoritmo di ordinamento è un algoritmo basato sul confronto in cui viene confrontata ogni coppia di elementi adiacenti e gli elementi vengono scambiati se non sono in ordine. Questo algoritmo non è adatto per insiemi di dati di grandi dimensioni poiché la sua complessità media e peggiore è di Ο (n ² ) doven è il numero di elementi.

Come funziona Bubble Sort?

Prendiamo un array non ordinato per il nostro esempio. Il Bubble sort richiede Ο (n ² ) tempo, quindi lo manteniamo breve e preciso.

Bubble sort inizia con i primi due elementi, confrontandoli per verificare quale sia il maggiore.

In questo caso, il valore 33 è maggiore di 14, quindi è già nelle posizioni ordinate. Successivamente, confrontiamo 33 con 27.

Troviamo che 27 è minore di 33 e questi due valori devono essere scambiati.

Il nuovo array dovrebbe essere simile a questo:

Successivamente confrontiamo 33 e 35. Troviamo che entrambi sono in posizioni già ordinate.

Quindi passiamo ai due valori successivi, 35 e 10.

Sappiamo allora che 10 è minore di 35. Quindi non vengono ordinati.

Scambiamo questi valori. Troviamo che abbiamo raggiunto la fine dell'array. Dopo un'iterazione, l'array dovrebbe apparire così:

Per essere precisi, ora stiamo mostrando come dovrebbe apparire un array dopo ogni iterazione. Dopo la seconda iterazione, dovrebbe apparire così:

Notare che dopo ogni iterazione, almeno un valore si sposta alla fine.

E quando non è richiesto alcuno scambio, l'ordinamento a bolle apprende che un array è completamente ordinato.

Ora dovremmo esaminare alcuni aspetti pratici del Bubble sort.

Algoritmo

Assumiamo list è un array di nelementi. Assumiamo inoltre cheswap funzione scambia i valori degli elementi dell'array dati.

begin BubbleSort(list)

   for all elements of list
      if list[i] > list[i+1]
         swap(list[i], list[i+1])
      end if
   end for
   
   return list
   
end BubbleSort

Pseudocodice

Osserviamo nell'algoritmo che Bubble Sort confronta ogni coppia di elementi dell'array a meno che l'intero array non sia completamente ordinato in ordine crescente. Ciò potrebbe causare alcuni problemi di complessità come se l'array non avesse più bisogno di essere scambiato poiché tutti gli elementi sono già in ascesa.

Per facilitare il problema, utilizziamo una variabile flag swappedche ci aiuterà a vedere se è avvenuto o meno uno scambio. Se non si è verificato alcuno scambio, ovvero l'array non richiede più elaborazioni per essere ordinato, uscirà dal ciclo.

Lo pseudocodice dell'algoritmo BubbleSort può essere scritto come segue:

procedure bubbleSort( list : array of items )

   loop = list.count;
   
   for i = 0 to loop-1 do:
      swapped = false
		
      for j = 0 to loop-1 do:
      
         /* compare the adjacent elements */   
         if list[j] > list[j+1] then
            /* swap them */
            swap( list[j], list[j+1] )		 
            swapped = true
         end if
         
      end for
      
      /*if no number was swapped that means 
      array is sorted now, break the loop.*/
      
      if(not swapped) then
         break
      end if
      
   end for
   
end procedure return list

Implementazione

Un altro problema che non abbiamo affrontato nel nostro algoritmo originale e nel suo pseudocodice improvvisato è che, dopo ogni iterazione, i valori più alti si depositano alla fine dell'array. Quindi, l'iterazione successiva non deve includere elementi già ordinati. A tale scopo, nella nostra implementazione, restringiamo il ciclo interno per evitare valori già ordinati.

Per conoscere l'implementazione del Bubble Sort nel linguaggio di programmazione C, fare clic qui .

Questo è un algoritmo di ordinamento basato sul confronto sul posto. Qui viene mantenuto un sottoelenco che è sempre ordinato. Ad esempio, la parte inferiore di un array viene mantenuta per essere ordinata. Un elemento che deve essere "inserito" in questo sotto-elenco ordinato, deve trovare la sua posizione appropriata e quindi deve essere inserito lì. Da qui il nome,insertion sort.

L'array viene ricercato in sequenza e gli elementi non ordinati vengono spostati e inseriti nel sottoelenco ordinato (nello stesso array). Questo algoritmo non è adatto per insiemi di dati di grandi dimensioni poiché la sua complessità media e peggiore è di Ο (n ² ), doven è il numero di elementi.

Come funziona l'ordinamento di inserzione?

Prendiamo un array non ordinato per il nostro esempio.

L'ordinamento di inserzione confronta i primi due elementi.

Si scopre che sia 14 che 33 sono già in ordine crescente. Per ora, 14 è in un sottoelenco ordinato.

L'ordinamento per inserzione va avanti e confronta 33 con 27.

E scopre che 33 non è nella posizione corretta.

Scambia 33 con 27. Controlla anche con tutti gli elementi della sotto-lista ordinata. Qui vediamo che il sottoelenco ordinato ha solo un elemento 14 e 27 è maggiore di 14. Quindi, il sottoelenco ordinato rimane ordinato dopo lo scambio.

Ormai abbiamo 14 e 27 nella sotto-lista ordinata. Successivamente, confronta 33 con 10.

Questi valori non sono in un ordine ordinato.

Quindi li scambiamo.

Tuttavia, lo scambio rende 27 e 10 non ordinati.

Quindi, li scambiamo anche.

Ancora una volta troviamo 14 e 10 in un ordine non ordinato.

Li scambiamo di nuovo. Alla fine della terza iterazione, abbiamo un sottoelenco ordinato di 4 elementi.

Questo processo continua fino a quando tutti i valori non ordinati sono coperti in un sottoelenco ordinato. Vedremo ora alcuni aspetti di programmazione dell'ordinamento per inserzione.

Algoritmo

Ora abbiamo un quadro più ampio di come funziona questa tecnica di ordinamento, quindi possiamo derivare semplici passaggi da cui possiamo ottenere l'ordinamento per inserzione.

Step 1 − If it is the first element, it is already sorted. return 1;
Step 2 − Pick next element
Step 3 − Compare with all elements in the sorted sub-list
Step 4 − Shift all the elements in the sorted sub-list that is greater than the 
         value to be sorted
Step 5 − Insert the value
Step 6 − Repeat until list is sorted

Pseudocodice

procedure insertionSort( A : array of items )
   int holePosition
   int valueToInsert
	
   for i = 1 to length(A) inclusive do:
	
      /* select value to be inserted */
      valueToInsert = A[i]
      holePosition = i
      
      /*locate hole position for the element to be inserted */
		
      while holePosition > 0 and A[holePosition-1] > valueToInsert do:
         A[holePosition] = A[holePosition-1]
         holePosition = holePosition -1
      end while
		
      /* insert the number at hole position */
      A[holePosition] = valueToInsert
      
   end for
	
end procedure

Per conoscere l'implementazione dell'ordinamento per inserzione nel linguaggio di programmazione C, fare clic qui .

L'ordinamento della selezione è un semplice algoritmo di ordinamento. Questo algoritmo di ordinamento è un algoritmo basato sul confronto sul posto in cui l'elenco è diviso in due parti, la parte ordinata all'estremità sinistra e la parte non ordinata all'estremità destra. Inizialmente, la parte ordinata è vuota e la parte non ordinata è l'intero elenco.

L'elemento più piccolo viene selezionato dall'array non ordinato e scambiato con l'elemento più a sinistra, e quell'elemento diventa una parte dell'array ordinato. Questo processo continua a spostare il limite dell'array non ordinato di un elemento a destra.

Questo algoritmo non è adatto per grandi insiemi di dati poiché la sua complessità media e nel caso peggiore è di Ο (n ² ), doven è il numero di elementi.

Come funziona l'ordinamento della selezione?

Considera il seguente array raffigurato come esempio.

Per la prima posizione nell'elenco ordinato, l'intero elenco viene scansionato in sequenza. La prima posizione in cui è attualmente memorizzato 14, cerchiamo in tutta la lista e troviamo che 10 è il valore più basso.

Quindi sostituiamo 14 con 10. Dopo un'iterazione 10, che sembra essere il valore minimo nell'elenco, appare nella prima posizione dell'elenco ordinato.

Per la seconda posizione, dove risiede 33, iniziamo a scansionare il resto della lista in modo lineare.

Troviamo che 14 è il secondo valore più basso nell'elenco e dovrebbe apparire al secondo posto. Scambiamo questi valori.

Dopo due iterazioni, due valori minimi vengono posizionati all'inizio in modo ordinato.

Lo stesso processo viene applicato al resto degli elementi dell'array.

Di seguito è una rappresentazione pittorica dell'intero processo di smistamento:

Ora, impariamo alcuni aspetti di programmazione dell'ordinamento di selezione.

Algoritmo

Step 1 − Set MIN to location 0
Step 2 − Search the minimum element in the list
Step 3 − Swap with value at location MIN
Step 4 − Increment MIN to point to next element
Step 5 − Repeat until list is sorted

Pseudocodice

procedure selection sort 
   list  : array of items
   n     : size of list

   for i = 1 to n - 1
   /* set current element as minimum*/
      min = i    
  
      /* check the element to be minimum */

      for j = i+1 to n 
         if list[j] < list[min] then
            min = j;
         end if
      end for

      /* swap the minimum element with the current element*/
      if indexMin != i  then
         swap list[min] and list[i]
      end if
   end for
	
end procedure

Per conoscere l'implementazione dell'ordinamento di selezione nel linguaggio di programmazione C, fare clic qui .

Merge sort è una tecnica di ordinamento basata sulla tecnica divide et impera. Con la complessità temporale nel caso peggiore complexity (n log n), è uno degli algoritmi più rispettati.

Unisci ordinamento divide prima l'array in due metà uguali, quindi le combina in modo ordinato.

Come funziona Merge Sort?

Per comprendere l'ordinamento di tipo merge, prendiamo un array non ordinato come segue:

Sappiamo che l'unione dell'ordinamento divide prima l'intero array in modo iterativo in metà uguali a meno che non vengano raggiunti i valori atomici. Vediamo qui che un array di 8 elementi è diviso in due array di dimensione 4.

Ciò non modifica la sequenza di aspetto degli elementi nell'originale. Ora dividiamo questi due array a metà.

Dividiamo ulteriormente questi array e otteniamo un valore atomico che non può più essere diviso.

Ora, li combiniamo esattamente nello stesso modo in cui sono stati suddivisi. Si prega di notare i codici colore forniti a questi elenchi.

Confrontiamo prima l'elemento per ogni elenco e poi li combiniamo in un altro elenco in modo ordinato. Vediamo che 14 e 33 sono in posizioni ordinate. Confrontiamo 27 e 10 e nell'elenco di destinazione di 2 valori mettiamo 10 per primo, seguito da 27. Modifichiamo l'ordine di 19 e 35 mentre 42 e 44 sono posti in sequenza.

Nella successiva iterazione della fase di combinazione, confrontiamo elenchi di due valori di dati e li uniamo in un elenco di valori di dati trovati posizionando tutti in un ordine ordinato.

Dopo la fusione finale, l'elenco dovrebbe apparire così:

Ora dovremmo imparare alcuni aspetti di programmazione del merge sorting.

Algoritmo

L'ordinamento unito continua a dividere l'elenco in metà uguali fino a quando non può più essere diviso. Per definizione, se è solo un elemento nell'elenco, viene ordinato. Quindi, l'ordinamento di unione combina gli elenchi ordinati più piccoli mantenendo ordinato anche il nuovo elenco.

Step 1 − if it is only one element in the list it is already sorted, return.
Step 2 − divide the list recursively into two halves until it can no more be divided.
Step 3 − merge the smaller lists into new list in sorted order.

Pseudocodice

Vedremo ora gli pseudocodici per le funzioni di merge sort. Come i nostri algoritmi sottolineano due funzioni principali: dividi e unisci.

Merge sort funziona con la ricorsione e vedremo la nostra implementazione nello stesso modo.

procedure mergesort( var a as array )
   if ( n == 1 ) return a

   var l1 as array = a[0] ... a[n/2]
   var l2 as array = a[n/2+1] ... a[n]

   l1 = mergesort( l1 )
   l2 = mergesort( l2 )

   return merge( l1, l2 )
end procedure

procedure merge( var a as array, var b as array )

   var c as array
   while ( a and b have elements )
      if ( a[0] > b[0] )
         add b[0] to the end of c
         remove b[0] from b
      else
         add a[0] to the end of c
         remove a[0] from a
      end if
   end while
   
   while ( a has elements )
      add a[0] to the end of c
      remove a[0] from a
   end while
   
   while ( b has elements )
      add b[0] to the end of c
      remove b[0] from b
   end while
   
   return c
	
end procedure

Per conoscere l'implementazione dell'ordinamento di tipo merge nel linguaggio di programmazione C, fare clic qui .

L'ordinamento della shell è un algoritmo di ordinamento altamente efficiente e si basa su un algoritmo di ordinamento per inserzione. Questo algoritmo evita grandi spostamenti come nel caso dell'ordinamento per inserzione, se il valore più piccolo si trova all'estrema destra e deve essere spostato all'estrema sinistra.

Questo algoritmo utilizza l'ordinamento per inserzione su elementi ampiamente distribuiti, prima per ordinarli e poi ordina gli elementi meno distanziati. Questa spaziatura è definita comeinterval. Questo intervallo è calcolato in base alla formula di Knuth come -

Formula di Knuth

h = h * 3 + 1
where −
   h is interval with initial value 1

Questo algoritmo è abbastanza efficiente per set di dati di medie dimensioni poiché la sua complessità media e peggiore è di Ο (n), dove n è il numero di elementi.

Come funziona l'ordinamento della shell?

Consideriamo il seguente esempio per avere un'idea di come funziona l'ordinamento della shell. Prendiamo lo stesso array che abbiamo usato nei nostri esempi precedenti. Per il nostro esempio e per la nostra facilità di comprensione, prendiamo l'intervallo di 4. Crea una sottoelenco virtuale di tutti i valori situati nell'intervallo di 4 posizioni. Questi valori sono {35, 14}, {33, 19}, {42, 27} e {10, 44}

Confrontiamo i valori in ogni sottoelenco e li scambiamo (se necessario) nell'array originale. Dopo questo passaggio, il nuovo array dovrebbe apparire così:

Quindi, prendiamo un intervallo di 2 e questo intervallo genera due sottoelenchi: {14, 27, 35, 42}, {19, 10, 33, 44}

Confrontiamo e scambiamo i valori, se necessario, nell'array originale. Dopo questo passaggio, l'array dovrebbe apparire così:

Infine, ordiniamo il resto dell'array utilizzando l'intervallo di valore 1. L'ordinamento della shell utilizza l'ordinamento per inserimento per ordinare l'array.

Di seguito è riportata la descrizione dettagliata:

Vediamo che sono stati necessari solo quattro scambi per ordinare il resto dell'array.

Algoritmo

Di seguito è riportato l'algoritmo per l'ordinamento della shell.

Step 1 − Initialize the value of h
Step 2 − Divide the list into smaller sub-list of equal interval h
Step 3 − Sort these sub-lists using insertion sort
Step 3 − Repeat until complete list is sorted

Pseudocodice

Di seguito è riportato lo pseudocodice per l'ordinamento della shell.

procedure shellSort()
   A : array of items 
	
   /* calculate interval*/
   while interval < A.length /3 do:
      interval = interval * 3 + 1	    
   end while
   
   while interval > 0 do:

      for outer = interval; outer < A.length; outer ++ do:

      /* select value to be inserted */
      valueToInsert = A[outer]
      inner = outer;

         /*shift element towards right*/
         while inner > interval -1 && A[inner - interval] >= valueToInsert do:
            A[inner] = A[inner - interval]
            inner = inner - interval
         end while

      /* insert the number at hole position */
      A[inner] = valueToInsert

      end for

   /* calculate interval*/
   interval = (interval -1) /3;	  

   end while
   
end procedure

Per conoscere l'implementazione dell'ordinamento della shell nel linguaggio di programmazione C, fare clic qui .

Formula di Knuth

h = h * 3 + 1
where −
   h is interval with initial value 1

Questo algoritmo è abbastanza efficiente per insiemi di dati di medie dimensioni in quanto la sua complessità media e nel caso peggiore di questo algoritmo dipende dalla sequenza di gap la più nota è Ο (n), dove n è il numero di elementi. E il caso peggiore della complessità spaziale è O (n).

Come funziona l'ordinamento della shell?

Confrontiamo i valori in ogni sottoelenco e li scambiamo (se necessario) nell'array originale. Dopo questo passaggio, il nuovo array dovrebbe apparire così:

Quindi, prendiamo un intervallo di 1 e questo intervallo genera due sottoelenchi: {14, 27, 35, 42}, {19, 10, 33, 44}

Confrontiamo e scambiamo i valori, se necessario, nell'array originale. Dopo questo passaggio, l'array dovrebbe apparire così:

Infine, ordiniamo il resto dell'array utilizzando l'intervallo di valore 1. L'ordinamento della shell utilizza l'ordinamento per inserimento per ordinare l'array.

Di seguito è riportata la descrizione dettagliata:

Vediamo che sono stati necessari solo quattro scambi per ordinare il resto dell'array.

Algoritmo

Di seguito è riportato l'algoritmo per l'ordinamento della shell.

Step 1 − Initialize the value of h
Step 2 − Divide the list into smaller sub-list of equal interval h
Step 3 − Sort these sub-lists using insertion sort
Step 3 − Repeat until complete list is sorted

Pseudocodice

Di seguito è riportato lo pseudocodice per l'ordinamento della shell.

procedure shellSort()
   A : array of items 
	
   /* calculate interval*/
   while interval < A.length /3 do:
      interval = interval * 3 + 1	    
   end while
   
   while interval > 0 do:

      for outer = interval; outer < A.length; outer ++ do:

      /* select value to be inserted */
      valueToInsert = A[outer]
      inner = outer;

         /*shift element towards right*/
         while inner > interval -1 && A[inner - interval] >= valueToInsert do:
            A[inner] = A[inner - interval]
            inner = inner - interval
         end while

      /* insert the number at hole position */
      A[inner] = valueToInsert

      end for

   /* calculate interval*/
   interval = (interval -1) /3;	  

   end while
   
end procedure

Per conoscere l'implementazione dell'ordinamento della shell nel linguaggio di programmazione C, fare clic qui .

L'ordinamento rapido è un algoritmo di ordinamento altamente efficiente e si basa sul partizionamento di array di dati in array più piccoli. Un array di grandi dimensioni è partizionato in due array, uno dei quali contiene valori inferiori al valore specificato, ad esempio pivot, in base al quale viene creata la partizione e un altro array contiene valori maggiori del valore pivot.

Quicksort partiziona un array e quindi chiama se stesso in modo ricorsivo due volte per ordinare i due sottoarray risultanti. Questo algoritmo è abbastanza efficiente per set di dati di grandi dimensioni poiché la sua complessità media e nel caso peggiore sono rispettivamente O (nLogn) e image.png (n ² ).

Partizione in ordinamento rapido

La seguente rappresentazione animata spiega come trovare il valore pivot in un array.

Il valore pivot divide l'elenco in due parti. E ricorsivamente, troviamo il pivot per ogni sottoelenco fino a quando tutti gli elenchi non contengono un solo elemento.

Algoritmo pivot di ordinamento rapido

Sulla base della nostra comprensione del partizionamento nell'ordinamento rapido, proveremo ora a scrivere un algoritmo per esso, che è il seguente.

Step 1 − Choose the highest index value has pivot
Step 2 − Take two variables to point left and right of the list excluding pivot
Step 3 − left points to the low index
Step 4 − right points to the high
Step 5 − while value at left is less than pivot move right
Step 6 − while value at right is greater than pivot move left
Step 7 − if both step 5 and step 6 does not match swap left and right
Step 8 − if left ≥ right, the point where they met is new pivot

Pseudocodice pivot di ordinamento rapido

Lo pseudocodice per l'algoritmo di cui sopra può essere derivato come -

function partitionFunc(left, right, pivot)
   leftPointer = left
   rightPointer = right - 1

   while True do
      while A[++leftPointer] < pivot do
         //do-nothing            
      end while
		
      while rightPointer > 0 && A[--rightPointer] > pivot do
         //do-nothing         
      end while
		
      if leftPointer >= rightPointer
         break
      else                
         swap leftPointer,rightPointer
      end if
		
   end while 
	
   swap leftPointer,right
   return leftPointer
	
end function

Algoritmo di ordinamento rapido

Usando l'algoritmo pivot in modo ricorsivo, ci ritroviamo con partizioni più piccole possibili. Ogni partizione viene quindi elaborata per l'ordinamento rapido. Definiamo l'algoritmo ricorsivo per quicksort come segue:

Step 1 − Make the right-most index value pivot
Step 2 − partition the array using pivot value
Step 3 − quicksort left partition recursively
Step 4 − quicksort right partition recursively

Pseudocodice di ordinamento rapido

Per approfondire, vediamo lo pseudocodice per l'algoritmo di ordinamento rapido -

procedure quickSort(left, right)

   if right-left <= 0
      return
   else     
      pivot = A[right]
      partition = partitionFunc(left, right, pivot)
      quickSort(left,partition-1)
      quickSort(partition+1,right)    
   end if		
   
end procedure

Per conoscere l'implementazione rapida dell'ordinamento nel linguaggio di programmazione C, fare clic qui .

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 denominati comeverticese vengono chiamati i collegamenti che collegano i vertici edges.

Formalmente, un grafico è una coppia di insiemi (V, E), dove V è l'insieme dei vertici e Eè l'insieme dei bordi, che collega le coppie di vertici. Dai un'occhiata al grafico seguente:

Nel grafico sopra,

V = {a, b, c, d, e}

E = {ab, ac, bd, cd, de}

Struttura dei dati del grafico

I grafici matematici possono essere rappresentati nella struttura dei dati. Possiamo rappresentare un grafo usando un array di vertici e un array bidimensionale di bordi. Prima di procedere oltre, familiarizziamo con alcuni termini importanti:

Vertex- Ogni nodo del grafico è rappresentato come un vertice. Nell'esempio seguente, il cerchio etichettato rappresenta i vertici. Quindi, da A a G sono vertici. Possiamo rappresentarli usando un array come mostrato nell'immagine seguente. Qui A può essere identificato dall'indice 0. B può essere identificato usando l'indice 1 e così via.
Edge- Edge rappresenta un percorso tra due vertici o una linea tra due vertici. Nell'esempio seguente, le linee da A a B, da B a C e così via rappresentano i bordi. Possiamo usare un array bidimensionale per rappresentare un array come mostrato nell'immagine seguente. Qui AB può essere rappresentato come 1 nella riga 0, colonna 1, BC come 1 nella riga 1, colonna 2 e così via, mantenendo le altre combinazioni come 0.
Adjacency- Due nodi o vertici sono adiacenti se sono collegati tra loro tramite un bordo. Nell'esempio seguente, B è adiacente ad A, C è adiacente a B e così via.
Path- Path rappresenta una sequenza di bordi tra i due vertici. Nell'esempio seguente, ABCD rappresenta un percorso da A a D.

Operazioni di base

Di seguito sono riportate le operazioni principali di base di un grafico:

Add Vertex - Aggiunge un vertice al grafico.
Add Edge - Aggiunge un bordo tra i due vertici del grafico.
Display Vertex - Visualizza un vertice del grafico.

Per saperne di più su Graph, leggi il tutorial sulla teoria dei grafi . Impareremo come attraversare un grafico nei prossimi capitoli.

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.

Come nell'esempio sopra, l'algoritmo DFS passa da S ad A a D a G a E a B prima, poi a F e infine a C. Impiega le seguenti regole.

Rule 1- Visita il vertice adiacente non visitato. Contrassegnalo come visitato. Mostralo. Mettilo in una pila.
Rule 2- Se non viene trovato alcun vertice adiacente, fai apparire un vertice dalla pila. (Apparirà tutti i vertici dalla pila, che non hanno vertici adiacenti.)
Rule 3 - Ripeti la regola 1 e la regola 2 fino a quando la pila è vuota.

Passo	Traversal	Descrizione
1		Inizializza lo stack.
2		marchio Scome visitato e metterlo nella pila. Esplora qualsiasi nodo adiacente non visitato daS. Abbiamo tre nodi e possiamo sceglierne uno qualsiasi. Per questo esempio, prenderemo il nodo in ordine alfabetico.
3		marchio Acome visitato e metterlo nella pila. Esplora qualsiasi nodo adiacente non visitato da A. EntrambiS e D sono adiacenti a A ma ci occupiamo solo dei nodi non visitati.
4		Visitare De contrassegnalo come visitato e mettilo nella pila. Ecco, abbiamoB e C nodi, che sono adiacenti a Ded entrambi non sono visitati. Tuttavia, sceglieremo di nuovo in ordine alfabetico.
5		Noi scegliamo B, contrassegnalo come visitato e mettilo nella pila. QuiBnon ha alcun nodo adiacente non visitato. Quindi, facciamo scoppiareB dalla pila.
6		Controlliamo lo stack in alto per tornare al nodo precedente e controlliamo se ha nodi non visitati. Qui troviamoD essere in cima alla pila.
7		Solo il nodo adiacente non visitato proviene da D è Cadesso. Quindi visitiamoC, contrassegnalo come visitato e mettilo nella pila.

Come Cnon ha alcun nodo adiacente non visitato, quindi continuiamo a far scoppiare la pila finché non troviamo un nodo che ha un nodo adiacente non visitato. In questo caso, non ce n'è e continuiamo a scoppiare finché lo stack non è vuoto.

Per conoscere l'implementazione di questo algoritmo nel linguaggio di programmazione C, fare clic qui .

L'algoritmo Breadth First Search (BFS) attraversa un grafico con un movimento in larghezza e utilizza una coda per ricordarsi di ottenere il vertice successivo per avviare una ricerca, quando si verifica un vicolo cieco in qualsiasi iterazione.

Come nell'esempio riportato sopra, l'algoritmo BFS attraversa prima da A a B a E a F poi a C e G infine a D. Impiega le seguenti regole.

Rule 1- Visita il vertice adiacente non visitato. Contrassegnalo come visitato. Mostralo. Inseriscilo in una coda.
Rule 2 - Se non viene trovato alcun vertice adiacente, rimuovere il primo vertice dalla coda.
Rule 3 - Ripetere la regola 1 e la regola 2 fino a quando la coda non è vuota.

Passo	Traversal	Descrizione
1		Inizializza la coda.
2		Partiamo dalla visita S (nodo iniziale) e contrassegnarlo come visitato.
3		Vediamo quindi un nodo adiacente non visitato da S. In questo esempio, abbiamo tre nodi ma scegliamo alfabeticamenteA, contrassegnalo come visitato e accodalo.
4		Successivamente, il nodo adiacente non visitato da S è B. Lo contrassegniamo come visitato e lo accodiamo.
5		Successivamente, il nodo adiacente non visitato da S è C. Lo contrassegniamo come visitato e lo accodiamo.
6		Adesso, Sviene lasciato senza nodi adiacenti non visitati. Quindi, rimuoviamo la coda e troviamoA.
7		A partire dal A noi abbiamo Dcome nodo adiacente non visitato. Lo contrassegniamo come visitato e lo accodiamo.

In questa fase, non ci sono nodi non contrassegnati (non visitati). Ma come per l'algoritmo continuiamo a rimuovere l'accodamento per ottenere tutti i nodi non visitati. Quando la coda si svuota, il programma è finito.

L'implementazione di questo algoritmo nel linguaggio di programmazione C può essere vista qui .

L'albero rappresenta i nodi collegati dai bordi. Discuteremo albero binario o albero di ricerca binario in modo specifico.

L'albero binario è una struttura dati speciale utilizzata per scopi di archiviazione dei dati. Un albero binario ha una condizione speciale che ogni nodo può avere un massimo di due figli. Un albero binario ha i vantaggi sia di un array ordinato che di un elenco collegato poiché la ricerca è veloce come in un array ordinato e le operazioni di inserimento o eliminazione sono veloci come in un elenco collegato.

Termini importanti

Di seguito sono riportati i termini importanti rispetto all'albero.

Path - Il percorso si riferisce alla sequenza di nodi lungo i bordi di un albero.
Root- Il nodo nella parte superiore dell'albero è chiamato root. C'è solo una radice per albero e un percorso dal nodo radice a qualsiasi nodo.
Parent - Qualsiasi nodo tranne il nodo radice ha un bordo verso l'alto a un nodo chiamato padre.
Child - Il nodo al di sotto di un dato nodo connesso dal suo bordo verso il basso è chiamato il suo nodo figlio.
Leaf - Il nodo che non ha alcun nodo figlio è chiamato nodo foglia.
Subtree - Il sottoalbero rappresenta i discendenti di un nodo.
Visiting - La visita si riferisce al controllo del valore di un nodo quando il controllo è sul nodo.
Traversing - Attraversare significa passare attraverso i nodi in un ordine specifico.
Levels- Il livello di un nodo rappresenta la generazione di un nodo. Se il nodo radice è al livello 0, il suo successivo nodo figlio è al livello 1, il suo nipote è al livello 2 e così via.
keys - La chiave rappresenta un valore di un nodo in base al quale deve essere eseguita un'operazione di ricerca per un nodo.

Rappresentazione dell'albero di ricerca binaria

L'albero di ricerca binario mostra un comportamento speciale. 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.

Implementeremo l'albero utilizzando l'oggetto nodo e collegandoli tramite riferimenti.

Nodo dell'albero

Il codice per scrivere un nodo ad albero sarebbe simile a quanto riportato di seguito. Ha una parte dati e riferimenti ai suoi nodi figlio sinistro e destro.

struct node {
   int data;   
   struct node *leftChild;
   struct node *rightChild;
};

In un albero, tutti i nodi condividono un costrutto comune.

BST Operazioni di base

Le operazioni di base che possono essere eseguite su una struttura dati ad albero di ricerca binario, sono le seguenti:

Insert - Inserisce un elemento in un albero / crea un albero.
Search - Cerca un elemento in un albero.
Preorder Traversal - Attraversa un albero in modalità pre-ordine.
Inorder Traversal - Attraversa un albero in modo ordinato.
Postorder Traversal - Attraversa un albero in modo post-ordine.

In questo capitolo impareremo a creare (inserire in) una struttura ad albero e cercare un elemento di dati in un albero. Impareremo i metodi di attraversamento degli alberi nel prossimo capitolo.

Inserisci operazione

Il primo vero inserimento crea l'albero. Successivamente, ogni volta che deve essere inserito un elemento, individuare prima la sua posizione corretta. Inizia la ricerca dal nodo radice, quindi se i dati sono inferiori al valore della chiave, cerca la posizione vuota nella sottostruttura sinistra e inserisci i dati. Altrimenti, cerca la posizione vuota nella sottostruttura destra e inserisci i dati.

Algoritmo

If root is NULL 
   then create root node
return

If root exists then
   compare the data with node.data
   
   while until insertion position is located

      If data is greater than node.data
         goto right subtree
      else
         goto left subtree

   endwhile 
   
   insert data
	
end If

Implementazione

L'implementazione della funzione di inserimento dovrebbe essere simile a questa:

void insert(int data) {
   struct node *tempNode = (struct node*) malloc(sizeof(struct node));
   struct node *current;
   struct node *parent;

   tempNode->data = data;
   tempNode->leftChild = NULL;
   tempNode->rightChild = NULL;

   //if tree is empty, create root node
   if(root == NULL) {
      root = tempNode;
   } else {
      current = root;
      parent  = NULL;

      while(1) {                
         parent = current;

         //go to left of the tree
         if(data < parent->data) {
            current = current->leftChild;                
            
            //insert to the left
            if(current == NULL) {
               parent->leftChild = tempNode;
               return;
            }
         }
			
         //go to right of the tree
         else {
            current = current->rightChild;
            
            //insert to the right
            if(current == NULL) {
               parent->rightChild = tempNode;
               return;
            }
         }
      }            
   }
}

Operazione di ricerca

Ogni volta che si deve cercare un elemento, avviare la ricerca dal nodo radice, quindi se i dati sono inferiori al valore della chiave, cercare l'elemento nella sottostruttura sinistra. Altrimenti, cerca l'elemento nella sottostruttura a destra. Segui lo stesso algoritmo per ogni nodo.

Algoritmo

If root.data is equal to search.data
   return root
else
   while data not found

      If data is greater than node.data
         goto right subtree
      else
         goto left subtree
         
      If data found
         return node
   endwhile 
   
   return data not found
   
end if

L'implementazione di questo algoritmo dovrebbe essere simile a questa.

struct node* search(int data) {
   struct node *current = root;
   printf("Visiting elements: ");

   while(current->data != data) {
      if(current != NULL)
      printf("%d ",current->data); 
      
      //go to left tree

      if(current->data > data) {
         current = current->leftChild;
      }
      //else go to right tree
      else {                
         current = current->rightChild;
      }

      //not found
      if(current == NULL) {
         return NULL;
      }

      return current;
   }  
}

Per conoscere l'implementazione della struttura dei dati dell'albero di ricerca binario, fare clic qui .

L'attraversamento è un processo per visitare tutti i nodi di un albero e può anche stampare i loro valori. Poiché tutti i nodi sono collegati tramite bordi (collegamenti), iniziamo sempre dal nodo radice (testa). Cioè, non possiamo accedere in modo casuale a un nodo in un albero. Ci sono tre modi che usiamo per attraversare un albero:

Attraversamento in ordine
Preordina Traversal
Post-order Traversal

In genere, attraversiamo un albero per cercare o individuare un determinato elemento o chiave nell'albero o per stampare tutti i valori in esso contenuti.

Attraversamento in ordine

In questo metodo di attraversamento, viene visitato prima il sottoalbero sinistro, poi la radice e successivamente il sottoalbero destro. Dobbiamo sempre ricordare che ogni nodo può rappresentare una sottostruttura stessa.

Se viene attraversato un albero binario in-order, l'output produrrà valori chiave ordinati in ordine crescente.

Partiamo da Ae, seguendo l'attraversamento in ordine, ci spostiamo sulla sua sottostruttura sinistra B. Bè anche attraversato in ordine. Il processo continua finché tutti i nodi non vengono visitati. L'output dell'attraversamento in ordine di questo albero sarà:

D → B → E → A → F → C → G

Algoritmo

Until all nodes are traversed −
Step 1 − Recursively traverse left subtree.
Step 2 − Visit root node.
Step 3 − Recursively traverse right subtree.

Preordina Traversal

In questo metodo di attraversamento, viene visitato per primo il nodo radice, quindi la sottostruttura sinistra e infine la sottostruttura destra.

Partiamo da Ae dopo l'attraversamento del preordine, visitiamo prima A stesso e quindi spostarsi nella sua sottostruttura sinistra B. Bè anche attraversato il preordine. Il processo continua finché tutti i nodi non vengono visitati. L'output dell'attraversamento del preordine di questo albero sarà:

A → B → D → E → C → F → G

Algoritmo

Until all nodes are traversed −
Step 1 − Visit root node.
Step 2 − Recursively traverse left subtree.
Step 3 − Recursively traverse right subtree.

Post-order Traversal

In questo metodo di attraversamento, il nodo radice viene visitato per ultimo, da cui il nome. Per prima cosa attraversiamo la sottostruttura sinistra, quindi la sottostruttura destra e infine il nodo radice.

Partiamo da Ae, dopo l'attraversamento post-ordine, visitiamo prima la sottostruttura di sinistra B. Bè anche attraversato dopo l'ordine. Il processo continua finché tutti i nodi non vengono visitati. L'output dell'attraversamento post-ordine di questo albero sarà:

D → E → B → F → G → C → A

Algoritmo

Until all nodes are traversed −
Step 1 − Recursively traverse left subtree.
Step 2 − Recursively traverse right subtree.
Step 3 − Visit root node.

Per verificare l'implementazione in C dell'attraversamento degli alberi, fare clic qui .

Un albero di ricerca binario (BST) è un albero in cui tutti i nodi seguono le proprietà indicate di seguito:

Il valore della chiave del sottoalbero sinistro è inferiore al valore della chiave del suo nodo padre (radice).
Il valore della chiave del sottoalbero destro è maggiore o uguale al valore della chiave del suo nodo padre (radice).

Pertanto, BST divide tutti i suoi sottoalberi in due segmenti; il sottoalbero sinistro e il sottoalbero destro e può essere definito come -

left_subtree (keys) < node (key) ≤ right_subtree (keys)

Rappresentazione

BST è una raccolta di nodi disposti in modo tale da mantenere le proprietà BST. Ogni nodo ha una chiave e un valore associato. Durante la ricerca, la chiave desiderata viene confrontata con le chiavi in BST e, se trovata, viene recuperato il valore associato.

Di seguito è una rappresentazione pittorica di BST -

Osserviamo che la chiave del nodo radice (27) ha tutte le chiavi di minor valore nel sottoalbero di sinistra e le chiavi di valore più alto sul sottoalbero di destra.

Operazioni di base

Di seguito sono riportate le operazioni di base di un albero:

Search - Cerca un elemento in un albero.
Insert - Inserisce un elemento in un albero.
Pre-order Traversal - Attraversa un albero in modalità pre-ordine.
In-order Traversal - Attraversa un albero in modo ordinato.
Post-order Traversal - Attraversa un albero in modo post-ordine.

Nodo

Definisci un nodo con alcuni dati, riferimenti ai suoi nodi figlio sinistro e destro.

struct node {
   int data;   
   struct node *leftChild;
   struct node *rightChild;
};

Operazione di ricerca

Ogni volta che si deve cercare un elemento, avviare la ricerca dal nodo radice. Quindi, se i dati sono inferiori al valore chiave, cerca l'elemento nella sottostruttura sinistra. Altrimenti, cerca l'elemento nella sottostruttura a destra. Segui lo stesso algoritmo per ogni nodo.

Algoritmo

struct node* search(int data){
   struct node *current = root;
   printf("Visiting elements: ");
	
   while(current->data != data){
	
      if(current != NULL) {
         printf("%d ",current->data);
			
         //go to left tree
         if(current->data > data){
            current = current->leftChild;
         }  //else go to right tree
         else {                
            current = current->rightChild;
         }
			
         //not found
         if(current == NULL){
            return NULL;
         }
      }			
   }
   
   return current;
}

Inserisci operazione

Ogni volta che deve essere inserito un elemento, individuare prima la sua posizione corretta. Inizia la ricerca dal nodo radice, quindi se i dati sono inferiori al valore della chiave, cerca la posizione vuota nella sottostruttura sinistra e inserisci i dati. Altrimenti, cerca la posizione vuota nella sottostruttura destra e inserisci i dati.

Algoritmo

void insert(int data) {
   struct node *tempNode = (struct node*) malloc(sizeof(struct node));
   struct node *current;
   struct node *parent;

   tempNode->data = data;
   tempNode->leftChild = NULL;
   tempNode->rightChild = NULL;

   //if tree is empty
   if(root == NULL) {
      root = tempNode;
   } else {
      current = root;
      parent = NULL;

      while(1) {                
         parent = current;
			
         //go to left of the tree
         if(data < parent->data) {
            current = current->leftChild;                
            //insert to the left
				
            if(current == NULL) {
               parent->leftChild = tempNode;
               return;
            }
         }  //go to right of the tree
         else {
            current = current->rightChild;
            
            //insert to the right
            if(current == NULL) {
               parent->rightChild = tempNode;
               return;
            }
         }
      }            
   }
}

Cosa succede se l'input dell'albero di ricerca binario arriva in un modo ordinato (crescente o decrescente)? Quindi apparirà così:

Si osserva che la prestazione nel caso peggiore di BST è la più vicina agli algoritmi di ricerca lineare, ovvero Ο (n). Nei dati in tempo reale, non possiamo prevedere il modello dei dati e le loro frequenze. Quindi, sorge la necessità di bilanciare la BST esistente.

Prende il nome dal loro inventore Adelson, Velski & Landis, AVL treessono l'albero di ricerca binario di 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 è chiamataBalance Factor.

Qui vediamo che il primo albero è bilanciato e i due alberi successivi non sono bilanciati -

Nel secondo albero, la sottostruttura sinistra di C ha altezza 2 e il sottoalbero destro ha altezza 0, quindi la differenza è 2. Nel terzo albero, il sottoalbero destro di Aha altezza 2 e manca la sinistra, quindi è 0 e la differenza è di nuovo 2. L'albero AVL consente che la differenza (fattore di equilibrio) sia solo 1.

BalanceFactor = height(left-sutree) − height(right-sutree)

Se la differenza di altezza tra i sottoalberi sinistro e destro è maggiore di 1, l'albero viene bilanciato utilizzando alcune tecniche di rotazione.

Rotazioni AVL

Per bilanciarsi, un albero AVL può eseguire i seguenti quattro tipi di rotazioni:

Rotazione a sinistra
Rotazione a destra
Rotazione sinistra-destra
Rotazione destra-sinistra

Le prime due rotazioni sono rotazioni singole e le due rotazioni successive sono rotazioni doppie. Per avere un albero sbilanciato, abbiamo bisogno almeno di un albero di altezza 2. Con questo semplice albero, capiamoli uno per uno.

Rotazione a sinistra

Se un albero diventa sbilanciato, quando un nodo viene inserito nella sottostruttura destra della sottostruttura destra, allora eseguiamo una singola rotazione sinistra -

Nel nostro esempio, node Aè diventato sbilanciato quando un nodo viene inserito nella sottostruttura destra della sottostruttura destra di A. Eseguiamo la rotazione sinistra facendoA la sottostruttura sinistra di B.

Rotazione a destra

L'albero AVL può diventare sbilanciato, se un nodo viene inserito nella sottostruttura sinistra della sottostruttura sinistra. L'albero ha quindi bisogno di una giusta rotazione.

Come illustrato, il nodo sbilanciato diventa il figlio destro del suo figlio sinistro eseguendo una rotazione a destra.

Rotazione sinistra-destra

Le doppie rotazioni sono versioni leggermente complesse delle versioni già spiegate delle rotazioni. Per capirli meglio, dovremmo prendere nota di ogni azione eseguita durante la rotazione. Controlliamo prima come eseguire la rotazione sinistra-destra. Una rotazione sinistra-destra è una combinazione di rotazione sinistra seguita da rotazione destra.

Stato	Azione
	Un nodo è stato inserito nella sottostruttura destra della sottostruttura sinistra. Questo faCun nodo sbilanciato. Questi scenari fanno sì che l'albero AVL esegua la rotazione da sinistra a destra.
	Per prima cosa eseguiamo la rotazione sinistra sulla sottostruttura sinistra di C. Questo faA, la sottostruttura sinistra di B.
	Nodo C è ancora sbilanciato, tuttavia ora è a causa della sottostruttura sinistra della sottostruttura sinistra.
	Ora faremo ruotare a destra l'albero, creando B il nuovo nodo radice di questa sottostruttura. C ora diventa la sottostruttura destra della propria sottostruttura sinistra.
	L'albero è ora equilibrato.

Rotazione destra-sinistra

Il secondo tipo di doppia rotazione è la rotazione destra-sinistra. È una combinazione di rotazione a destra seguita da rotazione a sinistra.

Stato	Azione
	Un nodo è stato inserito nella sottostruttura sinistra della sottostruttura destra. Questo faA, un nodo sbilanciato con fattore di equilibrio 2.
	Per prima cosa, eseguiamo la rotazione corretta C nodo, fabbricazione C la sottostruttura destra della propria sottostruttura sinistra B. Adesso,B diventa la sottostruttura destra di A.
	Nodo A è ancora sbilanciato a causa del sottoalbero destro del suo sottoalbero destro e richiede una rotazione sinistra.
	A left rotation is performed by making B the new root node of the subtree. A becomes the left subtree of its right subtree B.
	The tree is now balanced.

A spanning tree is a subset of Graph G, which has all the vertices covered with minimum possible number of edges. Hence, a spanning tree does not have cycles and it cannot be disconnected..

By this definition, we can draw a conclusion that every connected and undirected Graph G has at least one spanning tree. A disconnected graph does not have any spanning tree, as it cannot be spanned to all its vertices.

We found three spanning trees off one complete graph. A complete undirected graph can have maximum n^n-2 number of spanning trees, where n is the number of nodes. In the above addressed example, n is 3, hence 3³⁻² = 3 spanning trees are possible.

General Properties of Spanning Tree

We now understand that one graph can have more than one spanning tree. Following are a few properties of the spanning tree connected to graph G −

A connected graph G can have more than one spanning tree.
All possible spanning trees of graph G, have the same number of edges and vertices.
The spanning tree does not have any cycle (loops).
Removing one edge from the spanning tree will make the graph disconnected, i.e. the spanning tree is minimally connected.
Adding one edge to the spanning tree will create a circuit or loop, i.e. the spanning tree is maximally acyclic.

Mathematical Properties of Spanning Tree

Spanning tree has n-1 edges, where n is the number of nodes (vertices).
From a complete graph, by removing maximum e - n + 1 edges, we can construct a spanning tree.
A complete graph can have maximum n^n-2 number of spanning trees.

Thus, we can conclude that spanning trees are a subset of connected Graph G and disconnected graphs do not have spanning tree.

Application of Spanning Tree

Spanning tree is basically used to find a minimum path to connect all nodes in a graph. Common application of spanning trees are −

Civil Network Planning
Computer Network Routing Protocol
Cluster Analysis

Let us understand this through a small example. Consider, city network as a huge graph and now plans to deploy telephone lines in such a way that in minimum lines we can connect to all city nodes. This is where the spanning tree comes into picture.

Minimum Spanning Tree (MST)

In a weighted graph, a minimum spanning tree is a spanning tree that has minimum weight than all other spanning trees of the same graph. In real-world situations, this weight can be measured as distance, congestion, traffic load or any arbitrary value denoted to the edges.

Minimum Spanning-Tree Algorithm

We shall learn about two most important spanning tree algorithms here −

Kruskal's Algorithm
Prim's Algorithm

Both are greedy algorithms.

Heap is a special case of balanced binary tree data structure where the root-node key is compared with its children and arranged accordingly. If α has child node β then −

key(α) ≥ key(β)

As the value of parent is greater than that of child, this property generates Max Heap. Based on this criteria, a heap can be of two types −

For Input → 35 33 42 10 14 19 27 44 26 31

Min-Heap − Where the value of the root node is less than or equal to either of its children.

Max-Heap − Where the value of the root node is greater than or equal to either of its children.

Both trees are constructed using the same input and order of arrival.

Max Heap Construction Algorithm

We shall use the same example to demonstrate how a Max Heap is created. The procedure to create Min Heap is similar but we go for min values instead of max values.

We are going to derive an algorithm for max heap by inserting one element at a time. At any point of time, heap must maintain its property. While insertion, we also assume that we are inserting a node in an already heapified tree.

Step 1 − Create a new node at the end of heap.
Step 2 − Assign new value to the node.
Step 3 − Compare the value of this child node with its parent.
Step 4 − If value of parent is less than child, then swap them.
Step 5 − Repeat step 3 & 4 until Heap property holds.

Note − In Min Heap construction algorithm, we expect the value of the parent node to be less than that of the child node.

Let's understand Max Heap construction by an animated illustration. We consider the same input sample that we used earlier.

Max Heap Deletion Algorithm

Let us derive an algorithm to delete from max heap. Deletion in Max (or Min) Heap always happens at the root to remove the Maximum (or minimum) value.

Step 1 − Remove root node.
Step 2 − Move the last element of last level to root.
Step 3 − Compare the value of this child node with its parent.
Step 4 − If value of parent is less than child, then swap them.
Step 5 − Repeat step 3 & 4 until Heap property holds.

Some computer programming languages allow a module or function to call itself. This technique is known as recursion. In recursion, a function α either calls itself directly or calls a function β that in turn calls the original function α. The function α is called recursive function.

Example − a function calling itself.

int function(int value) {
   if(value < 1)
      return;
   function(value - 1);

   printf("%d ",value);   
}

Example − a function that calls another function which in turn calls it again.

int function1(int value1) {
   if(value1 < 1)
      return;
   function2(value1 - 1);
   printf("%d ",value1);   
}
int function2(int value2) {
   function1(value2);
}

Properties

A recursive function can go infinite like a loop. To avoid infinite running of recursive function, there are two properties that a recursive function must have −

Base criteria − There must be at least one base criteria or condition, such that, when this condition is met the function stops calling itself recursively.
Progressive approach − The recursive calls should progress in such a way that each time a recursive call is made it comes closer to the base criteria.

Implementation

Many programming languages implement recursion by means of stacks. Generally, whenever a function (caller) calls another function (callee) or itself as callee, the caller function transfers execution control to the callee. This transfer process may also involve some data to be passed from the caller to the callee.

This implies, the caller function has to suspend its execution temporarily and resume later when the execution control returns from the callee function. Here, the caller function needs to start exactly from the point of execution where it puts itself on hold. It also needs the exact same data values it was working on. For this purpose, an activation record (or stack frame) is created for the caller function.

Questo record di attivazione conserva le informazioni sulle variabili locali, i parametri formali, l'indirizzo di ritorno e tutte le informazioni passate alla funzione chiamante.

Analisi della ricorsione

Si potrebbe obiettare perché usare la ricorsione, poiché lo stesso compito può essere fatto con l'iterazione. Il primo motivo è che la ricorsione rende un programma più leggibile e grazie ai più recenti sistemi CPU avanzati, la ricorsione è più efficiente delle iterazioni.

Complessità temporale

In caso di iterazioni, prendiamo il numero di iterazioni per contare la complessità temporale. Allo stesso modo, in caso di ricorsione, assumendo che tutto sia costante, proviamo a calcolare il numero di volte in cui viene effettuata una chiamata ricorsiva. Una chiamata fatta a una funzione è Ο (1), quindi il numero (n) di volte che viene fatta una chiamata ricorsiva rende la funzione ricorsiva Ο (n).

Complessità spaziale

La complessità dello spazio viene conteggiata come la quantità di spazio extra necessaria per l'esecuzione di un modulo. In caso di iterazioni, il compilatore non richiede quasi alcuno spazio aggiuntivo. Il compilatore continua ad aggiornare i valori delle variabili utilizzate nelle iterazioni. Ma in caso di ricorsione, il sistema deve memorizzare il record di attivazione ogni volta che viene effettuata una chiamata ricorsiva. Quindi, si ritiene che la complessità spaziale della funzione ricorsiva possa essere superiore a quella di una funzione con iterazione.

La Torre di Hanoi, è un puzzle matematico che consiste di tre torri (pioli) e più di un anello è come raffigurato -

Questi anelli sono di diverse dimensioni e impilati in ordine crescente, cioè quello più piccolo si trova sopra quello più grande. Ci sono altre varianti del puzzle in cui il numero di dischi aumenta, ma il numero di torri rimane lo stesso.

Regole

La missione è spostare tutti i dischi in un'altra torre senza violare la sequenza di disposizione. Alcune regole da seguire per la Torre di Hanoi sono:

Solo un disco può essere spostato tra le torri in un dato momento.
È possibile rimuovere solo il disco "superiore".
Nessun disco di grandi dimensioni può sedersi su un disco di piccole dimensioni.

Di seguito è riportata una rappresentazione animata della risoluzione di un puzzle della Torre di Hanoi con tre dischi.

Il puzzle della Torre di Hanoi con n dischi può essere risolto al minimo 2ⁿ−1passi. Questa presentazione mostra che un puzzle con 3 dischi ha preso2³ - 1 = 7 passi.

Algoritmo

Per scrivere un algoritmo per la Torre di Hanoi, prima dobbiamo imparare come risolvere questo problema con una quantità minore di dischi, diciamo → 1 o 2. Contrassegniamo tre torri con il nome, source, destination e aux(solo per aiutare a spostare i dischi). Se disponiamo di un solo disco, può essere facilmente spostato dal piolo di origine a quello di destinazione.

Se abbiamo 2 dischi -

Per prima cosa, spostiamo il disco più piccolo (in alto) su aux peg.
Quindi, spostiamo il disco più grande (inferiore) nel piolo di destinazione.
Infine, spostiamo il disco più piccolo da aux a piolo di destinazione.

Quindi ora siamo in grado di progettare un algoritmo per la Torre di Hanoi con più di due dischi. Dividiamo la pila di dischi in due parti. Il disco più grande (n- ^esimo disco) è in una parte e tutti gli altri (n-1) dischi si trovano nella seconda parte.

Il nostro obiettivo finale è spostare il disco ndall'origine alla destinazione e quindi inserire tutti gli altri (n1) dischi. Possiamo immaginare di applicare lo stesso in modo ricorsivo a tutti i set di dischi dati.

I passaggi da seguire sono:

Step 1 − Move n-1 disks from source to aux
Step 2 − Move n^th disk from source to dest
Step 3 − Move n-1 disks from aux to dest

Un algoritmo ricorsivo per la Torre di Hanoi può essere guidato come segue:

START
Procedure Hanoi(disk, source, dest, aux)

   IF disk == 1, THEN
      move disk from source to dest             
   ELSE
      Hanoi(disk - 1, source, aux, dest)     // Step 1
      move disk from source to dest          // Step 2
      Hanoi(disk - 1, aux, dest, source)     // Step 3
   END IF
   
END Procedure
STOP

Per verificare l'implementazione nella programmazione C, fare clic qui .

La serie di Fibonacci genera il numero successivo aggiungendo due numeri precedenti. La serie di Fibonacci inizia da due numeri:F₀ & F₁. I valori iniziali di F ₀ e F ₁ possono essere presi rispettivamente 0, 1 o 1, 1.

La serie di Fibonacci soddisfa le seguenti condizioni:

F_n = F_n-1 + F_n-2

Quindi, una serie di Fibonacci può essere simile a questa:

F ₈ = 0 1 1 2 3 5 8 13

o, questo -

F ₈ = 1 1 2 3 5 8 13 21

A scopo illustrativo, Fibonacci di F ₈ viene visualizzato come -

Algoritmo iterativo di Fibonacci

Per prima cosa proviamo a disegnare l'algoritmo iterativo per le serie di Fibonacci.

Procedure Fibonacci(n)
   declare f₀, f₁, fib, loop 
   
   set f₀ to 0
   set f₁ to 1
   
   display f₀, f₁
   
   for loop ← 1 to n
   
      fib ← f₀ + f₁   
      f₀ ← f₁
      f₁ ← fib

      display fib
   end for
	
end procedure

Per conoscere l'implementazione dell'algoritmo di cui sopra nel linguaggio di programmazione C, fare clic qui .

Algoritmo ricorsivo di Fibonacci

Impariamo come creare un algoritmo ricorsivo serie di Fibonacci. I criteri di base della ricorsione.

START
Procedure Fibonacci(n)
   declare f₀, f₁, fib, loop 
   
   set f₀ to 0
   set f₁ to 1
   
   display f₀, f₁
   
   for loop ← 1 to n
   
      fib ← f₀ + f₁   
      f₀ ← f₁
      f₁ ← fib

      display fib
   end for

END

Per vedere l'implementazione dell'algoritmo di cui sopra nel linguaggio di programmazione c, fare clic qui .