vuoi
o PayPal
tutte le volte che vuoi
Implementazione degli algoritmi di ordinamento
La funzione BubbleSort implementa l'algoritmo di ordinamento a bolle. L'algoritmo opera effettuando i seguenti passi:
- Ricerca del vettore i dove inserire elem
- Shift di tutti gli elementi V[j] di un posto per i < j < nelem
- Incremento di nelem di una unità
- Inserzione di elem in V[i]
La funzione InsertSort implementa l'algoritmo di ordinamento per inserzione. L'algoritmo opera effettuando i seguenti passi:
- Scelta di un elemento x dalla lista
- Scorrimento della lista al contrario partendo dall'ultimo elemento e si ferma quando ha trovato un elemento y < x
- Scorrimento della lista partendo dal primo elemento e si ferma quando ha trovato un elemento z > x
- Scambio di z con x
La funzione QuickSort implementa l'algoritmo di ordinamento rapido. L'algoritmo opera in questo modo:
- Sceglie un elemento x dalla lista
- Scorre la lista al contrario partendo dall'ultimo elemento e si ferma quando ha trovato un elemento y < x
- Scorre la lista partendo dal primo elemento e si ferma quando ha trovato un elemento z > x
- Scambia z con x
momento in cui l'elemento desiderato non è incluso nella lista.
ISTRUZIONE:
void lineSearch(vettore V, const int n, const int x, int &pos){
int found = 0;
for(i = 0; i < dim && !found; i++){
if(V[i] == x){
found = 1;
pos = 1;
}
}
return found;
}
Ricerca binaria: consiste nel definire un elemento centrale dato dall'operazione [(pos1+posn)/2], in base all'elemento da cercare procedere verso destra o verso sinistra partendo dall'elemento x precedentemente definito.
ISTRUZIONE:
void BinSearch(vettore V, const int dim, const int x, int &pos){
int found = 0;
int j, k, i;
k = (j + i) / 2;
do {
if (V[i] == k){
found = 1;
pos = k;
} else if(V[i] > k){
i = k + 1;
} else{
j = k - 1;
}
} while((!found) && (i <= j));
return found;
}
COMPLESSITÀ COMPUTAZIONALE
Complessità temporale: calcolo richiesto per l'esecuzione del programma.
Complessità spaziale: memoria occupata dal programma.
La complessità computazionale risulta molto utile in ci permette di
calcora i reltivicosti delle funzioni e quindi ci aiuta a capire quanto sia efficiente il programma. Esistono 5 tipi di complessità:
- Complessità costante: l'algoritmo esegue sempre lo stesso numero di operazioni, qualsiasi sia il numero di dati d'ingresso.
- Complessità lineare: algoritmi che eseguono un numero di operazioni proporzionale a n.
- Complessità n*logn: algoritmi ottimi.
- Complessità esponenziale k.
Un problema si definisce computazionalmente trattabile se esiste un algoritmo efficiente che lo risolve.
Lo stream è un flusso che può essere associato a un disco o a un'altra periferica. In tal modo si ha il vantaggio della indipendenza della scrittura dei programmi e della portabilità dei programmi.
Il concetto di TDA estende, quella che è l'idea di tipo di dato (insieme che può assumere una variabile), includendo anche le operazioni possibili sul dato stesso.
La struttura
èincapsulata dalle operazioni che si posso effettuare su di essa e senza le quali la struttura stessa non potrebbe essere usata. Una modifica nel realizzazione del TDA non influenzai moduli che ne fanno uso. I vantaggi del TDA consiste nel “proteggere” la struttura incapsulata senza poterla alterare (information hiding) e nel non influenzare i moduli che ne fanno uso in caso di modifica del TDA.” Non ci preoccupiamo (rifiutiamo di preoccuparsi) per come siamo fatti... ci preoccupiamo per che cosa può offrire al mondo esterno!!!!”. Le differenze tra tipo concreto e TDA sono le seguenti: il tipo concreto è “limitato” ai vincoli imposti sulla definizione e dall’uso del tipo, mentre il TDA esporta un’interfaccia, esporta un tipo, l’unico modo per accedere alla struttura sono le operazioni che si possono effettuare su di essa, l’application domain del tipo è definito tramite assiomi e precondizioni. La potenza del TDAIl TDA introduce anche il concetto di modulo che praticamente è atto a contenere l'interfaccia (il cosa deve fare) e il corpo della funzione (il come).
Le prime due domande da porsi sono: Come bisogna fare e come deve essere fatto!
L'incapsulamento consiste nel tenere riservate alcune entità. Tali entità potranno essere usate mediante un'interfaccia che offrirà all'utente dei servizi.
L'astrazione fondamentale dei linguaggi a oggetti è l'astrazione sui dati.
In fase di progettazione software è bene utilizzare alcune tecniche per dominare la complessità del problema che si ha di fronte.
I meccanismi di astrazione più diffusi sono:
- ASTRAZIONE SUL CONTROLLO (sottoprogramma)
- ASTRAZIONE SUI DATI (consiste nell'astrarre gli oggetti che costituiscono il sistema, descritti in termini di strutture dati e delle operazioni possibili su di essa)
- Inizializzazione (nelem = 0);
- Inserimento in testa(push);
- Inserimento in coda;
- Ricerca sequenziale;
- Eliminazione in testa(pop);
- Eliminazione di un elemento dato;
- Analisi dell'elemento in testa(top);
- Predicati isEmpty/isFull(nelem = 0/nelem = N);
- PILA (LIFO):
- Inizializzazione(nelem = 0)(start);
- Inserimento in testa(push);
- Eliminazione in testa(pop);
- Analisi dell'elemento in testa(top);
- Predicati isEmpty/isFull(nelem = 0/nelem = N);
- Inizializzazione(nelem = 0)(start);
- Inserimento in coda(push);
- Eliminazione in testa(pop);
- Analisi dell'elemento in testa(top);
- Predicati isEmpty e isFull.
q = new record;
q -> next = l;
l = q;
```
Inserimento di un elemento all'interno della lista:
```html
q = new record;
q -> next = succ;
prec -> next = q;
```
Inserimento in coda:
```html
q = new record;
temp -> next = q;
```
Eliminazione in testa:
```html
Record *temp = l;
l = l -> next;
delete temp;
```
Eliminazione di un elemento interno alla lista:
```html
Record *temp = temp -> next;
temp -> next = temp -> next -> next;
delete temp;
```
Eliminazione di un elemento in coda:
```html
record *temp = temp -> next;
temp -> next = 0;
delete temp;
```
METODOLOGIE TOP-DOWN E BOTTOM-UP
Top-Down: si parte dal problema principale e poi si scompone in sottoproblemi sempre più semplici.
Bottom-Up: si individuano le classi degli oggetti che caratterizzano il problema e si costruisce la soluzione partendo dai singoli oggetti per arrivare al problema principale.problema in questione e poi si implementano.
PROGRAMMAZIONE A OGGETTI
Si parla di programmazione basata sugli oggetti partendo dalle idee di tipo di dato astratto o classe (tipo) e oggetto (istanza di un tipo).
Si parla invece di programmazione orientata agli oggetti riferendosi alle tecniche di programmazione basate su:
- Classe
- Oggetto
- Ereditarietà
- Polimorfismo
classe serve per definire tipi di dati astratti. Tali dati, sotto forma di funzioni o operatori, sono utilizzati.
UN OGGETTO È UNA VARIABILE ISTANZA DI UNA CLASSE
Lo stato di un oggetto dipende dai valori assunti dalla struttura concreta esistente al di sotto del TDA.
Il C++ è un linguaggio general-purpose, cioè supporta:
- La programmazione procedurale
- La programmazione OO
- La programmazione generica
programmazione un linguaggio ibrido cioè supporta + paradigmi di programmazione.
LE CLASSI
Il C++ supporta esplicitamente il costrutto class. La classe è composta da:
- oggetti (istanza della classe).
- Una parte pubblica che contiene le variabili e le funzioni che dovrà utilizzare l'utente.
- Una parte privata contente tutte le strutture dati e le operazioni che non vogliono essere rese accessibili dall'esterno.
Una classe per essere definita come tale deve avere le seguenti caratteristiche:
- E' dotata di un'interfaccia (specifica) e di un corpo (implementazione).
- La struttura dati concreta e gli algoritmi che ne realizzano le operazioni sono tenuti nascosti all'interno dei modulo che implementa la classe.
- Lo stato di un oggetto evolve unicamente in base alle operazioni effettuate sull'oggetto stesso.
- Le operazioni sono utilizzabili a prescindere dagli aspetti implementativi; in questo modo si possono modificare gli algoritmi senza toccare
L'interfaccia.
L'ereditarietà.
L'ereditarietà consente di creare nuove classi per specializzazione o estensione di classi preesistenti. Tale tecnica è di fondamentale importanza nella programmazione OO.
L'ereditarietà consente di creare delle relazioni tra classi di tipo generali.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
