[c++] lista inserimento ordinato

[Oo.Stud.ssa.oO]

Ciao a tutti, devo fare la funzione "AssegnaPrenotazione" che mi assegni le prenotazioni.
Gli elementi vanno inseriti in base alla seguente regola:
1) scorrere la lista della Stanza1 ed inserire la PrenotazioneDaAssegnare solo se in un punto della lista è verificata la seguente condizione:
DataInizio(PrenotazioneDaAssegnare)>DataFine(PrenotazionePrecedente)
DataFine (PrenotazioneDaAssegnare) Modiifcare il campo Stanza della Prenotazione inserendo il numero della stanza a cui è stata assegnata.
2) in caso di risposta negativa passare alla lista della Stanza2, e così via.
3) se non è possibile assegnare la prenotazione ad una stanza stampare messaggio di errore.
Cos ha che non va la mia funzione?

STRUTTURA DATI

typedef struct TipoPrenotazione{
        int IDPrenotazione;
        char NomeCliente[MAX];
        int DataInizio;
        int DataFine;
        int Stanza;
        //C default
        TipoPrenotazione(){
                           IDPrenotazione=0;
                           NomeCliente[0]='\0';
                           DataInizio=0;
                           DataFine = 1;
        }
        //c specifico
        TipoPrenotazione(int _IDPrenotazione, int _DataInizio, int _DataFine){
                           IDPrenotazione=_IDPrenotazione;
                           DataInizio=_DataInizio;
                           DataFine=_DataFine;
        }
        //stampa
void Stampa(){
      printf("ID: -- Nome cliente: -- Data inizio: -- Data fine: --Stanza:",IDPrenotazione, NomeCliente, DataInizio,   DataFine, Stanza);
        }
};

typedef struct TipoStanza{
        TipoPrenotazione Prenotazione;
        struct TipoStanza *next;
        TipoStanza(TipoPrenotazione _p, TipoStanza *_next){
                                    Prenotazione = _p;
                                    next = _next;                                   
        }
        TipoStanza(){
                     TipoPrenotazione p;
                     Prenotazione=p;
                     next=NULL;
        }

};
typedef struct TipoStanza Stanza;
typedef TipoStanza *StanzaPtr;

FUNZIONI:

int ID=0;
int random(int min, int max){
    int x= rand()%(max-min+1)+min;
    return x;
}
TipoPrenotazione CreaPrenotazione(){
                 TipoPrenotazione p(ID++,random(1,30), random(2,31));
                 return p;
}
StanzaPtr Inserisci(StanzaPtr pt, TipoPrenotazione p){
          int cont=0;
          StanzaPtr s;
          if (pt==NULL || pt->Prenotazione.DataInizio>p.DataFine){
                        StanzaPtr n=new Stanza (p,NULL);
                        pt=n;
                        cout<<"inserito"<<endl;
                        return pt;
          }else{
                s=pt;
                while (s!=NULL || (s->Prenotazione.DataFine<p.DataInizio && s->next->Prenotazione.DataInizio>p.DataFine )){
                      s=s->next;}
                if(s->Prenotazione.DataFine<p.DataInizio && s->next->Prenotazione.DataInizio>p.DataFine){
                                           StanzaPtr n=new Stanza (p,NULL);
                                           n->next= s->next;
                                           s->next=n; 
                                           cout<<"inserito"<<endl;
                                           return  pt;            
                }else{
                      cout<<"errore"<<endl;
                      return pt;}
                

}
}

MAIN:

StanzaPtr pt;
    TipoPrenotazione p1(1,3,6),p2(2,7,10);
    pt=Inserisci(pt,p1);
    pt=Inserisci(pt,p2);

Finchè inserisco un solo elemento funziona....

[Oo.Stud.ssa.oO]

Mi rispondo da sola... manca la condizione che ammette che nella lista c'è un solo elemento giusto?
Ma cosa posso fare al posto di mettere centinaia di if annidati?

[Vitalluni]

be intanto mi viene da farti notare che tu hai
"1 stanza con una lista di prenotazioni".
Quindi trovo un po strano che chiami "StanzaPtr" quello che effettivamente non è una stanza, ma è un nodo della lista.
E' importante separare le responsabilità, rende il programma più facile da leggere comprendere e modificare. Iniziare con il scegliere i nomi giusti è importantissimo (quindi non sono regole di "bellezza" ti aiutano e ti semplificano la vita;) ):
-Una stanza ha la lista di prenotazioni

struct Stanza{
    PrenotazListNode * first;
    //... bla bla 
};

-Ogni nodo della lista può puntare al nodo dopo e contiene una prenotazione

struct PrenotazListNode{
    TipoPrenotazione Prenotazione;
    PrenotazListNode * next;
    //...bla bla
};

-TipoPrenotazione (io l'avrei chiamata DatiPrenotazione o anche solo Prenotazione): contiene 2 date inizio e fine (e fine deve essere dopo inizio!)

struct TipoPrenotazione{
    int DataInizio;
    int DataFine;
    //.. bla bla
};

Direi che mancano 2 funzioni. Una ti dice se puoi aggiugere una prenotazione dopo l'altra. L'altra ti dice se una singola prenotazione è valida

// ritona "0" se la prenotazione è valida. Altrimenti ritorna -1
int PrenotazioneValida(PrenotazListNode * p){
    if(p->Prenotazione.DataInizio > p->Prenotazione.DataFine)
        return -1;
    return 0;
}
// ritorna "0" se puoi inserire "B" dopo "A". Altrimenti ritorna "-1".
int PrenotazioneAggiungibile(PrenotazListNode * A, PrenotazListNode * B){
    if(prenotazioneValida(A)==-1 || prenotazioneValida(B) ==-1)
        return -1;
    if (B->Prenotazione.DataInizio > A->Prenotazione.DataFine)
        return 0; 
    return -1;
}

Ora ti rimangono da gestire 3 casi

1) la lista è vuota. Devi controllare se la prenotazione è valida, dopodichè il primo nodo (first) è proprio il tuo PrenotazListNode.

Puoi iniziare a scorrere la lista

PrenotazListNode * p = StanzaParametro->first;
while(p!=NULL){  
   //tuo codice
    p = p->next;
}

ora mentre scorri la lista hai 2 casi possibili

PrenotazListNode * p = StanzaParametro->first;
while(p!=NULL){  
    if(p->next==NULL){ // il prossimo nodo sarà NULL (2° caso)
        //ti basta controllare che la prenotazione che vuoi aggiungere sia aggiungibile dopo p
        if(prenotazioneAggiungibile(p,tuaPrenotaz)==0){
            //... aggiungi tuaPrenotaz dopo p
            return; // non devi più fare nulla
        }
    }
    else { // il prossimo nodo non sarà NULL (3° caso)
        //controlli che tuaPrenotaz "stia in mezzo a "p" e "p->next"
        if( prenotazioneAggiungibile(p, tuaPrenotaz)==0 &&
            prenotazioneAggiungibile(tuaPrenotaz, p->next)==0 ){ 
            //.. aggiunti tua Prenotaz tra "p" e "pnext"
             return; // non devi più fare nulla
        }
    }
    p = p->next;
}

Nota bene ti ho anche mostrato un possibile approccio per risolvere il problema. Prima crei qualcosa che funziona solo con le cose "essenziali". E ti assicuri che funzioni bene etc (importante mettere a NULL i puntatori che puntano da nessuna parte). Poi il resto dei dettagli lo puoi sempre aggiugere dopo (nome stanza etc..)

Se puoi fatti sempre uno schemino su carta perchè aiuta.
Il fatto di confrontare "intervalli temporali" puoi benissimo farlo in un altra funzione così non devi più stare a mettere "tanti if annidati". (in generale quando inizano ad esserci più di 2/3 if annidati è un segnale che devi semplificare il codice, altrimenti poi diventa difficile trovare cosa non funziona)

[Oo.Stud.ssa.oO]

Ciao
Premetto che questo programma è un appello d'esame, e che il 90% dei nomi che ho usato sono proprio quelli del testo e sono quelli che bisogna usare!

Ma nel mio programma StanzaPtr è puntatore a una stanza.. no? è corretto, no?
Ho delle domande riguardo al tuo codice:
1- in pratica il tuo

first

è uguale al mio StackPtr pt; ma perchè per scorrere la lista hai messo

PrenotazListNode * p = StanzaParametro->first

?
Per scorrere la lista non devo usare il puntatore alla lista? In questo casoio avrei fatto così:

//Magari nell'header della funzione passo come parametro il puntatore alla lista che voglio scorrere es PrenotazListNode *p
poi all'interno della funzione 
while p!=NULL .....
...
p=p->next;

2- nel 2° caso, quello in cui il prossimo elemento è NULL, quindi ho un solo elemento, tu controlli se puoi aggiungere la prenotazione dopo p. Ma se invece la devo aggiungere prima?

3- E se volessi che il programma generasse errore nel caso in cui l'elemento non venga inserito, per esempio se nella stanza non c'è posto , come devo fare?

Grazie per la pazienza

[Vitalluni]

1-> l'importante è che "p" sia il primo nodo della lista. Be se quello è proprio il testo di esame non puoi fare altro che attenertici altrimenti poi rischi che non ti venga contato un esercizio giusto solo perchè hai cambiato i nomi. Nella realtà (purtroppo) se il tuo capo dice che devi chiamare una cosa in un certo modo devi farlo e se poi cambia idea ti ci devi attenere ugualmente. XD

2-> hai ovviamente ragione ho dimenticato un caso . In tal caso potresti semplicemente fare il test prima di iniziare il ciclo while (così tieni il ciclo while più semplice possibile,)

3-> Per i codici di errore c'è una semplice strategia(WHITELIST): se ho appena fatto quello che dovevo fare (inserire il nodo) ritorno un codice di "OK" (ad esempio 0). Altrimenti in fondo alla funzione metto "return -1;". In questo modo se non capita quello che doveva capitare sai già che ritorna errore.
In alcuni casi conviene ritornare invece sempre "OK" tranne in rare occasioni in cui si ritorna "NO" (BLACKLIST).

//TUA FUNZIONE CHE INSERISCE PRENOTAZIONE
// Se lista vuota crea nuovo nodo
if(prenotazioneAggiungibile(tuaPrenotaz , p){
    p=tuaPrenotaz;
    p->next = tuaPrenotaz;
    return 0;
}
while (p!=NULL){
//...
p=p->next
}
return -1; //se non siamo riusciti ad inserire il nodo allora errore.

quando io faccio così

PrenotazListNode * p = StanzaParametro->first

sto semplicemente prendendo il primo nodo della lista. Visto che c'è solo una lista di prenotazioni per ogni stanza, ho fatto in modo che ogni stanza punti al primo nodo della lista. Poi quel nodo li punterà a tutti quelli successivi.

[Oo.Stud.ssa.oO]

Si infatti nel testo è scritto anche:" I nomi dei campi e delle strutture devono essere rispettati rigorosamente.":)

Ok, però allora tutte le funzioni in cui voglio generare un codice d'errore numerico ( ok--->0; no--->-1) devono essere di tipo int, giusto?

[Vitalluni]

eh si allora devi rispettare i nomi personalmente non mi piacciono i nomi che ti hanno dato

Se vuoi ritornare 0/-1 "int" è conveniente. Se preferisci usare "bool" e ritornare true/false, oppure usare "char" e ritornare 'y'/'n' nessuno te lo impedisce. L'importante è che sia chiaro a chi legge il programma qual'è il codice di errore e qual'è il codice di OK. (se in qualche esempio che vi ha fatto il prof usa dei codici di errore magari ti conviene usare quelli li)

[Oo.Stud.ssa.oO]

Ok grazie 1000 per l'aiuto!!