Programmazione I - puntatore, algoritmi di ordinamento, tda

Puntatori in programmazione

Il puntatore viene utilizzato per:

• Il riferimento a variabili dinamiche.
• Il riferimento a funzioni.
• Gli array, in particolare per l'elaborazione di stringhe.
• I parametri formali di funzione, in alternativa allo scambio per riferimento.
• Il riferimento a locazioni specifiche della memoria, associate a dispositivi hardware (ad esempio per l'ingresso-uscita).

Per i puntatori sono previsti i seguenti operatori:

• L'operatore di assegnazione tra puntatori che puntano allo stesso tipo.
• Gli operatori unari di incremento e decremento.
• L'operatore di somma o differenza tra puntatori.

Puntatori e strutture

Il puntatore viene molto usato anche con strutture: array e record.

• Un puntatore ad array è una variabile che punta alla prima posizione dell'array.

Esempio:

int a[dim];
int *p;
p = a; // p è un puntatore alla prima posizione dell'array a.
for (int* p = a, int i=0; i<dim; i++, p++) // azzeramento di tutti gli elementi
  *p = 0;

Un puntatore a record è una variabile che punta all'indirizzo di memoria dove è allocato il record.

struct Ts {
  ...
};
Ts *p; // p è una variabile di tipo puntatore a Ts
p = &r1; // il puntatore p punta alla variabile r1

Per accedere ai campi della struttura tramite puntatori si usa l'istruzione:

• p -> r1.

Operazioni con puntatori

• L'operatore new alloca spazio in memoria atto a contenere una variabile di tipo T.
• L'operatore delete produce la deallocazione dell'area puntata da p.

Il puntatore il più delle volte viene passato con passaggio per valore, ma se necessario può essere passato anche per riferimento. Nel caso in cui il puntatore venga passato per riferimento, allora la variabile puntata potrà essere modificata tramite il puntatore. Quando una funzione ritorna un puntatore, può accadere che l'elemento puntato venga deallocato in quanto al momento della chiamata è stata fatta già una copia all'interno del programma chiamante.

Ricorsione

Un oggetto è ricorsivo se è possibile darne una definizione in termini di se stesso; il concetto della ricorsione si rifà all'induzione matematica. La ricorsione ritorna molto utile perché permette di risolvere un problema complesso in sottoproblemi più semplici fino ad arrivare al caso elementare. Per sfruttare la ricorsione dobbiamo prima individuare un caso base e poi trovare uno o più casi induttivi.

Un'induzione ben posta deve essere:

• Non circolare.
• Non ambigua.
• Completa.

Un programma ricorsivo è un sottoprogramma che invoca se stesso. Esistono vari tipi di ricorsione:

• Mutua ricorsione (una funzione invoca un'altra che a sua volta ne invoca ancora una).
• Ricorsione lineare (quando vi è solo una chiamata della funzione ricorsiva).
• Ricorsione di coda (quando la chiamata ricorsiva è l'ultima ad essere eseguita).

È possibile passare dalla forma ricorsiva alla forma iterativa, ma non è vero il viceversa.

typedef

Il typedef serve per definire dei tipi mediante un identificatore. Bisogna tenere presente che typedef NON DEFINISCE NUOVI TIPI! È molto comodo nell'implementazione perché permette di sostituire un tipo mediante poche operazioni, e quando si vuole definire un tipo con dichiarazione complessa attraverso un identificatore semplice.

Algoritmi di ordinamento

Gli algoritmi di ordinamento sono molto utili per effettuare una ricerca o per "ordinare" liste. Tra i vari tipi di ordinamento troviamo:

• Ordinamento per selezione (Selection sort).
• Ordinamento per scambi (Bubble sort).
• Ordinamento per inserzione (Insertion sort).
• Quick sort.

Selection Sort

Il Selection sort opera tramite spostamento fisico: cioè, prese due liste di interi, prende in esame una generica sottolista a[i]...a[n], si definisce l'elemento minimo (min) e la sua posizione (jmin), viene effettuato lo scambio tra a[i] e a[jmin] = min. Tale procedimento verrà poi eseguito per tutte le sottoliste ponendo i = 0, 2, ..., n-2.

Istruzione:

void SelSort(T* V, const int n) {
  int p;
  T min;
  for(int k = 0; k < n; k++) {
    V[p] = V[k];
    V[k] = min;
  }
}

Bubble Sort

Il Bubble Sort opera mediante spostamento fisico. Tale algoritmo fa un confronto tra coppie adiacenti e si scambiano gli elementi se essi non sono ordinati.

Istruzione:

void BubbleSort(Vettore V, int n) {
  int flag = 1;
  for(int i = 0; i < n && flag; i++) {
    flag = 0;
    for(int j = 0; j < n; j++)
      if (V[j] <= V[j+1])
        swap(V[j], V[j+1]);
  }
}

Insertion Sort

L'Insertion Sort opera effettuando i seguenti passi:

1. Ricerca del vettore i dove inserire elem.