File contenente l'intero programma. More...

#include <iostream>
#include <fstream>
#include <cstring>
#include <stdlib.h>

Classes
struct	elem
	Struttura del singolo elemento. More...
struct	desc_sequenza
	Descrittore di una sequenza. More...
Typedefs
typedef elem *	elem_p
Enumerations
enum	tipo_chiave_t { CHIAVE_NUMERICA, CHIAVE_STRINGA, CHIAVE_NUMERICA, CHIAVE_STRINGA }
	Tipo chiave per una sequenza. More...
enum	ins_modo { in_testa, in_coda, in_ordine, in_testa, in_coda, in_ordine }
	Posizione in cui inserire l'elemento: in testa, in coda, in ordine. More...
Functions
void	inizializza (desc_sequenza &s, const tipo_chiave_t t)
	Inizializzazione di una sequenza.
void	dealloca_elem (elem *p)
	Dealloca un elemento e le parole a cui punta.
void	distruggi (desc_sequenza &s)
	Distruzione di una sequenza.
int	diff (const desc_sequenza &s, const char c1[], const char c2[])
	Ritorna la differenza tra la chiave c1 e la chiave c2.
void	inserisci (desc_sequenza &s, elem *el, ins_modo modo)
	Inserimento di un elemento nella sequenza.
int	ric_sequenziale (const desc_sequenza &s, const char c[])
	Effettua una ricerca sequenziale di un elemento.
int	ric_binaria (const desc_sequenza &s, const char c[])
	Effettua una ricerca binaria di un elemento.
int	cerca (const desc_sequenza &s, const char c[])
	Cerca l'elemento con la chiave richiesta nella sequenza.
bool	elimina (desc_sequenza &s, const char c[])
	Elimina elemento dalla sequenza per valore.
void	stampa_elem (const elem &el, ostream &os)
	Stampa del contenuto di un elemento.
void	stampa (const desc_sequenza &s)
	Stampa del contenuto della sequenza.
void	salva (const desc_sequenza &s, const char nome[])
	Salva il contenuto della sequenza su un file di testo.
int	main ()
	Funzione principale.
Variables
const int	MAXLUN = 100
	Lunghezza massima stringhe.
const int	DIM_BASE = 100
	Dimensione minima dell'array in cui � memorizzata una sequenza.

Detailed Description

File contenente l'intero programma.

Typedef Documentation

typedef elem* elem_p

Enumeration Type Documentation

enum ins_modo

Posizione in cui inserire l'elemento: in testa, in coda, in ordine.

Enumerator:

in_testa
in_coda
in_ordine
in_testa
in_coda
in_ordine

{in_testa, in_coda, in_ordine} ;

enum tipo_chiave_t

Tipo chiave per una sequenza.

La chiave degli elementi di una sequenza pu� essere un numero intero positivo oppure una parola.

Si poteva utilizzare un tipo booleano per il tipo della chiave, ma, siccome il tipo della chiave � un parametro di ingresso della funzione che inizializza la sequenza, usare gli enumeratori aumenta la leggibilit� (dal nome dell'enumeratore passato alla funzione di inizializzazione si deduce immediatamente il tipo della chiave).

Enumerator:

CHIAVE_NUMERICA
CHIAVE_STRINGA
CHIAVE_NUMERICA
CHIAVE_STRINGA

{CHIAVE_NUMERICA, CHIAVE_STRINGA} ;

Function Documentation

int cerca	(	const desc_sequenza &	s,
		const char	c[]
	)

Cerca l'elemento con la chiave richiesta nella sequenza.

Parameters:

[in]	s	Sequenza in cui cercare l'elemento
[in]	c	Chiave da cercare. La chiave � rappresentata mediante una stringa, che, nel caso di chiave numerica, � uguale alla rappresentazione in base 10 della chiave da cercare.

Returns:: Indice dell'elemento contenente la chiave cercata in caso di successo, o -1 in caso di fallimento.

{
    return s.ordinata ? ric_binaria(s, c) : ric_sequenziale(s, c) ;
}

void dealloca_elem ( elem * p )

Dealloca un elemento e le parole a cui punta.

Parameters:

[in] p Puntatore all'elemento da deallocare.

{
    if (p->parole != 0)
        delete [] p->parole ;
    delete p ;
}

int diff	(	const desc_sequenza &	s,
		const char	c1[],
		const char	c2[]
	)		`[inline]`

Ritorna la differenza tra la chiave c1 e la chiave c2.

Parameters:

[in]	s	Sequenza sui cui elementi effettuare la differenza
[in]	c1	Prima chiave
[in]	c2	Seconda chiave

Returns:: Risultato della sottrazione tra la prima e la seconda chiave se le chiavi sono di tipo numerico, altrimenti valore di ritorno di strcmp(c1, c2)

{
    return s.tipo_chiave == CHIAVE_NUMERICA ? 
        atoi(c1) - atoi(c2) : strcmp(c1, c2) ;
}

void distruggi ( desc_sequenza & s )

Distruzione di una sequenza.

Libera la memoria utilizzata dalla sequenza.

Parameters:

[in] s Descrittore della sequenza da distruggere

{
    for (int i = 0 ; i < s.num_elem ; i++)
        dealloca_elem(s.elementi[i]) ;

    delete [] s.elementi ;
}

bool elimina	(	desc_sequenza &	s,
		const char	c[]
	)

Elimina elemento dalla sequenza per valore.

Cerca l'elemento con chiave uguale a quella passata in ingresso e, se lo trova, lo elimina.

Parameters:

[in]	s	Sequenza in cui cercare ed eliminare l'elemento
[in]	c	Chiave dell'elemento da cercare.

Returns:: Vero in caso di successo dell'eliminazione

{
    int pos = cerca(s, c) ;
    if (pos == -1)
        return false ;
    dealloca_elem(s.elementi[pos]) ;

    for (int i = pos ; i < s.num_elem - 1 ; i++)
        s.elementi[i] = s.elementi[i+1] ;

    s.num_elem-- ;
    return true ;
}

void inizializza	(	desc_sequenza &	s,
		const tipo_chiave_t	t
	)

Inizializzazione di una sequenza.

Da invocarsi prima di utilizzare la sequenza.

Parameters:

[in]	s	Descrittore della sequenza da distruggere
[in]	t	Tipo della chiave, di tipo tipo_chiave_t

{
    s.elementi = new elem_p[DIM_BASE] ;
    s.dim = DIM_BASE ;
    s.num_elem = 0 ;
    s.ordinata = true ;
    s.tipo_chiave = t ;
}

void inserisci	(	desc_sequenza &	s,
		elem *	el,
		ins_modo	modo
	)

Inserimento di un elemento nella sequenza.

E' possibile inserire l'elemento in testa, in coda o in ordine crescente, in base al valore del parametro modo. Attenzione: nella sequenza viene memorizzato l'indirizzo dell'elemento, per cui chi invoca la funzione inserisci deve assicurarsi che tale elemento non sia poi deallocato. Saranno le funzioni elimina e distruggi ad occuparsi della deallocazione dell'elemento.

Parameters:

[in]	s	Sequenza in cui inserire l'elemento
[in]	el	Elemento (pre-inizializzato) da inserire
[in]	modo	modalit� di inserimento (vedi ins_modo)

{
    int pos = 0 ;

    if (modo == in_coda)
        pos = s.num_elem ;
    else if (modo == in_ordine) {
        if (!s.ordinata) {
            cout<<"Inserimento in ordine non effettuato, "
                <<"perch� la sequenza non � ordinata"<<endl ;
            return ;
        }
        for ( ; pos < s.num_elem && 
                  diff(s, s.elementi[pos]->chiave, el->chiave) < 0 ;
              pos++)
            ;
    }

    // se non c'e' piu' spazio riallochiamo l'array
    if (s.num_elem == s.dim) {
        elem_p *nuovo = new elem_p[s.dim + DIM_BASE] ;
        for (int i = 0 ; i < s.num_elem ; i++)
            nuovo[i] = s.elementi[i] ;
        delete [] s.elementi ;
        s.elementi = nuovo ;
    }

    for (int i = s.num_elem ; i > pos ; i--)
        s.elementi[i] = s.elementi[i - 1] ;
    
    s.elementi[pos] = el ;
    s.num_elem++ ;

    if (modo != in_ordine && s.num_elem > 1)

        s.ordinata = diff(s, s.elementi[0]->chiave, s.elementi[1]->chiave) < 0 
            && 
            diff(s, s.elementi[s.num_elem-2]->chiave, 
                 s.elementi[s.num_elem - 1]->chiave) < 0 ;
}

int main ( )

Funzione principale.

Stampa un men� con tutte le funzionalit� disponibili. Tali funzionalit� sono:

inserimento, implementato mediante la funzione inserisci
ricerca, implementata mediante la funzione cerca
eliminazione, implementata mediante la funzione elimina
stampa, implementata mediante la funzione stampa
caricamento da file, per ora non implementata
salvataggio su file, implementata mediante la funzione salva

{
    desc_sequenza sequenza ;

    int scelta ;
    do {
        cout<<"Tipo di chiave: "<<endl ;
        cout<<"\t1) Numerica"<<endl ;
        cout<<"\t2) Stringa"<<endl ;
        cin>>scelta ; 
    } while(scelta < 1 || scelta > 2) ;

    tipo_chiave_t tipo_chiave ;
    switch(scelta) {
    case 1: tipo_chiave = CHIAVE_NUMERICA ; break ;
    case 2: tipo_chiave = CHIAVE_STRINGA ; break ;
    default: cout<<"Errore inatteso"<<endl ; return 1 ;
    }

    inizializza(sequenza, tipo_chiave) ;

    char menu[] =
        "\nOpzioni disponibili:\n\n"
        "\t1) Inserisci elemento\n"
        "\t2) Cerca elemento\n"
        "\t3) Elimina elemento\n"
        "\t4) Stampa sequenza\n"
        "\t5) Salva su file\n"
        "\t6) Carica da file\n"
        "\t0) Esci\n"
        "Scelta: " ;

    cout<<"Gestione sequenze."<<endl ;
    while(true) {
        cout<<menu ;

        int scelta ;
        cin>>scelta ;
        if (!cin) {
            cin.clear() ;
            cin.ignore() ;
            continue ;
        }

        switch(scelta) {
        case 0:
            return 0 ;
        case 1:{
            do { 
                cout<<"Modalita' di inserimento:"<<endl ;
                cout<<"\t1) In testa"<<endl ;
                cout<<"\t2) In coda"<<endl ;
                if (sequenza.ordinata)
                    cout<<"\t3) In ordine"<<endl ;
                cin>>scelta ; 
            } while(scelta < 1 || scelta > 3 || 
                    (!sequenza.ordinata && scelta > 2)) ;

            ins_modo modo ;
            switch(scelta) {
            case 1: modo = in_testa ; break ;
            case 2: modo = in_coda ; break ;
            case 3: modo = in_ordine; break ;
            default: cout<<"Errore inatteso"<<endl ; return 1 ;
            }
            elem *el = new elem ;
            el->parole = 0 ;
            cout<<"Dati elemento:"<<endl ;
            cout<<"Chiave: " ;
            cin>>el->chiave ;
            cout<<"Numero di parole: " ;
            cin>>el->num_parole ;
            if (el->num_parole > 0) {
                el->parole = new char[el->num_parole][MAXLUN] ;
                for (int i = 0 ; i < el->num_parole ; i++) {
                    cout<<"Parola: " ;
                    cin>>el->parole[i] ;
                }
            }
            inserisci(sequenza, el, modo) ; }
            break ;
        case 2: {
            char c[MAXLUN] ;
            cout<<"Chiave: " ;
            cin>>c ;
            int pos = cerca(sequenza, c) ;
            if (pos == -1)
                cout<<"Elemento non trovato"<<endl ;
            else {
                cout<<"Elemento trovato: "<<endl ;
                stampa_elem(*sequenza.elementi[pos], cout) ;
            } }
            break ;
        case 3: {
            char c[MAXLUN] ;
            cout<<"Chiave: " ;
            cin>>c ;
            if (!elimina(sequenza, c))
                cout<<"Elemento non trovato"<<endl ;
            else 
                cout<<"Elemento eliminato"<<endl ; }
            break ;
        case 4:
            stampa(sequenza) ;
            break ;
        case 5:
            salva(sequenza, "sequenza.txt") ;
            break ;
        default:
            cout<<"Scelta non valida"<<endl ;
        }
    }

    return 0 ;
}

int ric_binaria	(	const desc_sequenza &	s,
		const char	c[]
	)

Effettua una ricerca binaria di un elemento.

Parameters:

[in]	s	Sequenza in cui cercare l'elemento
[in]	c	Chiave da cercare. La chiave � rappresentata mediante una stringa, che, nel caso di chiave numerica, � uguale alla rappresentazione in base 10 della chiave da cercare.

Returns:: Indice dell'elemento contenente la chiave cercata in caso di successo, o -1 in caso di fallimento.

{
    if (s.num_elem == 0)
        return -1 ;
    int a = 0, b = s.num_elem - 1, m = (a+b) / 2 ;
    int d ;
    while ((d = diff(s, c, s.elementi[m]->chiave)) != 0) {
        if (d < 0) 
            b = m - 1 ;
        else 
            a = m + 1 ;
        if (a>b) 
            return -1 ;
        m = (a+b) / 2;
    }
    return m ;
}

int ric_sequenziale	(	const desc_sequenza &	s,
		const char	c[]
	)

Effettua una ricerca sequenziale di un elemento.

Parameters:

[in]	s	Sequenza in cui cercare l'elemento
[in]	c	Chiave da cercare. La chiave � rappresentata mediante una stringa, che, nel caso di chiave numerica, � uguale alla rappresentazione in base 10 della chiave da cercare.

Returns:: Indice dell'elemento contenente la chiave cercata in caso di successo, o -1 in caso di fallimento.

{
    int pos ;
    for (pos = 0 ; pos < s.num_elem ; pos++)
        if (diff(s, s.elementi[pos]->chiave, c) == 0)
            return pos ;
    return -1 ;
}

void salva	(	const desc_sequenza &	s,
		const char	nome[]
	)

Salva il contenuto della sequenza su un file di testo.

Parameters:

[in]	s	Sequenza da salvare
[in]	nome	Nome del file in cui salvare la sequenza

{
    ofstream f(nome) ;
    for (int i = 0 ; i < s.num_elem ; i++)
        stampa_elem(*s.elementi[i], f);
}

void stampa ( const desc_sequenza & s )

Stampa del contenuto della sequenza.

Parameters:

[in] s Sequenza da stampare

{
    for (int i = 0 ; i < s.num_elem ; i++) {
        cout<<"Elemento "<<i<<":"<<endl<<'\t' ;
        stampa_elem(*s.elementi[i], cout);
    }
    
    cout<<endl<<"Numero di elementi: "<<s.num_elem<<endl ;
    cout<<"Dimensione array: "<<s.dim<<endl ;
    cout<<(s.ordinata ? "Sequenza ordinata" : "Sequenza non ordinata")<<endl ;
}

void stampa_elem	(	const elem &	el,
		ostream &	os
	)

Stampa del contenuto di un elemento.

Parameters:

[in]	el	Elemento da stampare
[in]	os	Output stream su cui effettuare l'uscita

{
    os<<el.chiave ;
    for (int i = 0 ; i < el.num_parole ; i++)
        os<<" "<<el.parole[i] ;
    os<<endl ;
}

Variable Documentation

const int DIM_BASE = 100

Dimensione minima dell'array in cui � memorizzata una sequenza.

const int MAXLUN = 100

Lunghezza massima stringhe.

Classes

Typedefs

Enumerations

Functions

Variables

Detailed Description

Typedef Documentation

Enumeration Type Documentation

Function Documentation

Variable Documentation