Allocazione dinamica della memoria in C++. Esercitazione “Interi in ordine crescente”

Descrizione del problema

Si supponga di avere un file di testo come quello mostrato in figura, in cui sono memorizzati un numero non noto a priori di numeri interi, uno per riga, che termina con un carattere di nuova riga. Si richiede di scrivere un programma in C++ che visualizzi a video in ordine crescente tutti gli interi memorizzati nel file.

Soluzione proposta

I numeri presenti nel file devono essere letti e, prima che possano essere visualizzati a video, devono essere ordinati. Essi pertanto dovranno essere memorizzati in una struttura dati, in modo da permettere di eseguire le operazioni di ordinamento. Nelle soluzioni qui proposte si sceglierà di lavorare solo con strutture dati memorizzate in memoria centrale e si sottolinea che tali strutture dovranno essere allocate in memoria RAM in maniera dinamica, visto che quanti siano i numeri contenuti nel file non è noto a priori e né si ha alcuna indicazione per poterlo stimare. Tra le strutture dati che potrebbero essere utili potremmo considerare, per esempio, un vettore a lunghezza variabile o una lista ordinata. Di seguito vengono sviluppate entrambe le proposte di soluzione.

Soluzione n. 1 con vettore dinamico a lunghezza variabile

Nel programma seguente i numeri contenuti nel file vengono letti e man mano memorizzati in un vettore dinamico la cui dimensione viene aumentata ogni volta di un’unità. I numeri interi così caricati nel vettore vengono ordinati utilizzando l’algoritmo di ordinamento per sostituzione e, infine, visualizzati a video.

#include <iostream>
#include <fstream>
using namespace std;

/*Ordina un vettore utilizzando l'algoritmo di
ordinamento per sostituzione*/
void ordinaVettore(int v[], int dim) {
    int temp;
    for(int i=0; i<dim-1; i++) {
        for(int j=i+1; j<dim; j++) {
            if(v[i]>v[j]) {
                temp = v[i];
                v[i] = v[j];
                v[j] = temp;
            }
        }
    }
}

int main() {
    int n, dim=0;
    int* p = NULL;
    int* temp;
    fstream f("numeri.txt", ios::in);
    f >> n; //legge un intero dal file
    while(!f.eof()) { //finché non si arriva alla fine del file
        dim++; //aumenta di un'unità la dimensione del vettore
        temp = (int*) realloc(p, dim*sizeof(int)); //aggiunge un elemento al vettore
        if(temp!=NULL) { //se la riallocazione è andata a buon fine
            p = temp;
            p[dim-1] = n; //carica l'intero letto nel vettore
            f >> n; //legge un intero nel file
        }
        else {
            cout <<"Attenzione, memoria insufficiente!";
            break;
        }
    }
    f.close();
    ordinaVettore(p, dim);
    cout <<"Numeri letti, visualizzati in ordine crescente:"<<endl;
    //Visualizza a video gli interi letti e ordinati
    for(int i=0; i<dim; i++) {
        cout << p[i]<<" ";
    }
    cout <<endl;
    delete [] p;
    return 0;
}

#include <iostream>

#include <fstream>

using namespace std;

/*Ordina un vettore utilizzando l'algoritmo di

ordinamento per sostituzione*/

void ordinaVettore(int v[], int dim) {

int temp;

for(int i=0; i<dim-1; i++) {

for(int j=i+1; j<dim; j++) {

if(v[i]>v[j]) {

temp = v[i];

v[i] = v[j];

v[j] = temp;

}

int main() {

int n, dim=0;

int* p = NULL;

int* temp;

fstream f("numeri.txt", ios::in);

f >> n; //legge un intero dal file

while(!f.eof()) { //finché non si arriva alla fine del file

dim++; //aumenta di un'unità la dimensione del vettore

temp = (int*) realloc(p, dim*sizeof(int)); //aggiunge un elemento al vettore

if(temp!=NULL) { //se la riallocazione è andata a buon fine

p = temp;

p[dim-1] = n; //carica l'intero letto nel vettore

f >> n; //legge un intero nel file

}

else {

cout <<"Attenzione, memoria insufficiente!";

break;

}

f.close();

ordinaVettore(p, dim);

cout <<"Numeri letti, visualizzati in ordine crescente:"<<endl;

//Visualizza a video gli interi letti e ordinati

for(int i=0; i<dim; i++) {

cout << p[i]<<" ";

}

cout <<endl;

delete [] p;

return 0;

}

Soluzione n. 2 con lista ordinata

In questa seconda proposta di soluzione gli interi contenuti nel file vengono letti e man mano aggiunti ad una struttura dati a lista ordinata creata dinamicamente nell’heap. Quando tutti i numeri sono stati letti e caricati nella lista, risultano già ordinati e, quindi, possono essere stampati a video.

#include "mio_header.h"
#include "mie_funzioni.h"

int main() {
    int n;
    t_nodo* pNodo;
    inizializzaLista();
    fstream f("numeri.txt", ios::in);
    f >> n; //legge il primo intero dal file
    while(!f.eof()) { //finché non arriva alla fine del file
        pNodo = creaNodo(n); //crea un nuovo nodo con l'intero letto
        inserisciNodo(pNodo); //aggiunge il nodo creato alla lista ordinata
        f >> n; //legge l'intero successivo dal file
    }
    f.close();
    cout <<"Numeri letti, visualizzati in ordine crescente:"<<endl;
    visualizzaLista();
    svuotaLista();
    cout <<endl;
    return 0;
}

#include "mio_header.h"

#include "mie_funzioni.h"

int main() {

int n;

t_nodo* pNodo;

inizializzaLista();

fstream f("numeri.txt", ios::in);

f >> n; //legge il primo intero dal file

while(!f.eof()) { //finché non arriva alla fine del file

pNodo = creaNodo(n); //crea un nuovo nodo con l'intero letto

inserisciNodo(pNodo); //aggiunge il nodo creato alla lista ordinata

f >> n; //legge l'intero successivo dal file

}

f.close();

cout <<"Numeri letti, visualizzati in ordine crescente:"<<endl;

visualizzaLista();

svuotaLista();

cout <<endl;

return 0;

}

#ifndef MIO_HEADER_H_INCLUDED
#define MIO_HEADER_H_INCLUDED

#include <iostream>
#include <fstream>
using namespace std;

struct t_nodo {
    int num;
    t_nodo* succ;
};

t_nodo* testa = NULL;

#endif // MIO_HEADER_H_INCLUDED

#ifndef MIO_HEADER_H_INCLUDED

#define MIO_HEADER_H_INCLUDED

#include <iostream>

#include <fstream>

using namespace std;

struct t_nodo {

int num;

t_nodo* succ;

};

t_nodo* testa = NULL;

#endif // MIO_HEADER_H_INCLUDED

#ifndef MIE_FUNZIONI_H_INCLUDED
#define MIE_FUNZIONI_H_INCLUDED

/*Inizializza la lista*/
void inizializzaLista() {
    testa = NULL;
}
/*Crea un nuovo nodo*/
t_nodo* creaNodo(int n) {
    t_nodo* nuovo = new t_nodo;
    nuovo->num = n;
    nuovo->succ = NULL;
    return nuovo;
}
/*Inserisci un nodo nella lista in ordine crescente
rispetto al campo 'num' del nodo*/
void inserisciNodo(t_nodo* p) {
    t_nodo* attuale;
    t_nodo* precedente;
    if(testa == NULL) testa=p;
    else if(testa->num > p->num) {
        p->succ = testa;
        testa = p;
    }
    else {
        attuale = testa;
        while(attuale!=NULL && p->num > attuale->num) {
            precedente = attuale;
            attuale = attuale->succ;
        }
        p->succ = attuale;
        precedente->succ = p;
    }
}
/*Visualizza i numeri caricati nella lista*/
void visualizzaLista() {
    t_nodo* p = testa;
    while(p!=NULL){
        cout << p->num << " ";
        p = p->succ;
    }
}
/*Dealloca i nodi della lista dall'heap*/
void svuotaLista(){
    t_nodo* p;
    while(testa!=NULL) {
        p = testa;
        testa = testa->succ;
        free(p);
    }
}

#endif // MIE_FUNZIONI_H_INCLUDED

#ifndef MIE_FUNZIONI_H_INCLUDED

#define MIE_FUNZIONI_H_INCLUDED

/*Inizializza la lista*/

void inizializzaLista() {

testa = NULL;

}

/*Crea un nuovo nodo*/

t_nodo* creaNodo(int n) {

t_nodo* nuovo = new t_nodo;

nuovo->num = n;

nuovo->succ = NULL;

return nuovo;

}

/*Inserisci un nodo nella lista in ordine crescente

rispetto al campo 'num' del nodo*/

void inserisciNodo(t_nodo* p) {

t_nodo* attuale;

t_nodo* precedente;

if(testa == NULL) testa=p;

else if(testa->num > p->num) {

p->succ = testa;

testa = p;

}

else {

attuale = testa;

while(attuale!=NULL && p->num > attuale->num) {

precedente = attuale;

attuale = attuale->succ;

}

p->succ = attuale;

precedente->succ = p;

}

/*Visualizza i numeri caricati nella lista*/

void visualizzaLista() {

t_nodo* p = testa;

while(p!=NULL){

cout << p->num << " ";

p = p->succ;

}

/*Dealloca i nodi della lista dall'heap*/

void svuotaLista(){

t_nodo* p;

while(testa!=NULL) {

p = testa;

testa = testa->succ;

free(p);

}

#endif // MIE_FUNZIONI_H_INCLUDED

Articoli che ti potrebbero interessare