Programmi C / C++ - prof. Claudio Maccherani - Perugia - 2008
CODA (F.I.F.O.)
/* Adt, dato astratto CODA - F.I.F.O. realizzata tramite lista semplice: inserimento in fondo, estrazione in testa Dev-C++ - prof. Claudio Maccherani - Perugia - 2008/09 */ #include
#include
#include
#include
struct elem // definisce il tipo dell'elemento della coda (lista) { int info; // "info" = informazine elem *pun; // "pun" = puntatore prossimo elemento }; elem *p; // definisce un generico elemento della coda (lista) elem *pini; // definisce l'elemento iniziale della coda PINI=pun.inizio elem *pfin; // definisce l'elemento finale della coda PFIN=pun.fine int n; // numero elementi della pila int x; // valore dell'elemento da inserire / estrarre const int col=10; // colonna per menu int creaCoda(char flag); // crazione coda int elencoCoda(bool tit); // elenco elementi della coda int inserimentoElem(); // inserimento di un elemento nella coda int InCoda(int x); // inserimento di un elemento (in fondo) int estrazioneElem(); // estrazione di un elemento dalla coda int OutCoda(); // estrazione di un elemento (dalla testa) int eliminaCoda(char flag); // eliminazione coda e recupero memoria int gotorc(int r, int c); // posiziona il cusore a riga 'r' e colonna 'c' int main() { // programma principale ----------------------------------------- int scelta; do { system("cls"); scelta = -1; gotorc( 1,col); printf("Gestione dato astratto 'CODA' mediante lista semplice'
"); if (n > 0){ gotorc( 2,col); printf(" [ coda corrente di %d elementi ]",n); } gotorc( 4,col); printf("1 - Creazione AUTOMATICA della coda"); gotorc( 6,col); printf("2 - Creazione MANUALE della coda"); gotorc( 8,col); printf("3 - Elenco degli elementi della coda"); gotorc(10,col); printf("4 - Inserimento di un elemento (InCoda)"); gotorc(12,col); printf("5 - Estrazione di un elemento (OutCoda)"); gotorc(14,col); printf("6 - Cancellazione della coda"); gotorc(17,col); printf(" scegli (0=fine) ... "); cin>>scelta; switch (scelta) { case 1: { creaCoda('a'); break; } case 2: { creaCoda('m'); break; } case 3: { elencoCoda(true); break; } case 4: { inserimentoElem(); break; } case 5: { estrazioneElem(); break; } case 6: { eliminaCoda('i'); break; } } } while (scelta!= 0); eliminaCoda(' '); // elimina l'eventuale coda e libera la memoria return 0; } int creaCoda(char flag){ // crazione coda ('a'=automatica, 'm'=manuale)------- system("cls"); gotorc( 1,col); printf("Creazione della coda (a partire dall'ultimo)"); gotorc( 3,col); printf("Numero elementi della coda: "); cin>>n; cout <<"\n"; pini = NULL; // inizializza la testa della coda a NULL for (int i = 1; i <= n; i++) { p = new elem; // alloca un nuovo elemento if (flag == 'a') // se pila 'automatica' { p->info = (n - i + 1) * 10; // imposta il suo valore printf("%d^ elemento: %d\n",(n-i+1),p->info); } else { printf("%d^ elemento: ",i); // richiede il suo valore scanf("%d",&p->info); } p->pun = pini; // pun = indirizzo elemento precedente pini = p; // PIL = indirizzo dell'elemento inserito if (i == 1) pfin = p; } // se è l'ultimo, imposta il pun. all'ultimo getchar(); return 0; } int elencoCoda(bool tit){ // elenco elementi della coda ---------------------- if (tit) { system("cls"); gotorc( 1,col); printf("Elenco elementi della coda\n\n"); } p = pini; // imposta 'p' con il primo elemento while (p != NULL) { // fin quando non si raggiunge il puntatore NULL if (p == pini) cout<<"INIZIO:"; cout<<" <- "<< p->info; // visualizza l'infortmazione dell'elem.corrente p = p->pun; } // p = pun.elem. corrente, passa al successivo if (tit) getchar(); return 0; } int inserimentoElem(){ // inserimento di un elemento nella coda -------------- system("cls"); gotorc( 1,col); printf("Inserimento di un elemento\n\n"); elencoCoda(false); gotorc( 5,col); gotorc( 6,col); printf("Elemento da inserire: "); scanf("%d",&x); InCoda(x); n = n + 1; cout<<"\n"; elencoCoda(false); getchar(); getchar(); return 0; } int InCoda(int x){ // inserimento di un elemento (in fondo) elem *pp; // 'appoggio' per inserimento pp = pfin; // salva l'ultimo attuale pfin = new elem; // crea il nuovo ultimo (l'elemento da inserire) pfin->info = x; // gli assegna il valore pfin->pun = NULL; pp->pun = pfin; // lo collega alla coda (fine lista) return 0; } int estrazioneElem(){ // estrazione di un elemento dalla coda ---------------- system("cls"); gotorc( 1,col); printf("Estrazione di un elemento\n\n"); if (n > 0) // la coda non è vuota { elencoCoda(false); x = OutCoda(); n = n - 1; cout<<"\n\nL'elemento estratto e': "<
info; // estrae il primo elemento pp = pini; // salva primo (puntatore al primo, da eliminare) pini = pini->pun; // il primo assume il valore del pun.del primo elemento // (che ora punta al secondo) free(pp); // libera la memoria dell'elemento estratto return x; } int eliminaCoda(char flag){ // eliminazione coda e recupero memoria ---------- // (se 'flag'='i' interattivo) if (flag == 'i') {system("cls"); gotorc( 1,col); printf("Eliminazione coda e recupero memoria\n\n"); } int j=0; elem *pp; if (n > 0) { p = pini; // imposta 'p' con il puntatore inizo coda while (p != NULL) { // fin quando non si raggiunge il puntatore a NULL pini->pun = p->pun; free(p); p = pini->pun; } // 'p'=pun.elem.corrente, passa all'elem.successivo pini = NULL; pfin = NULL; } if (flag == 'i') { gotorc( 3,col); printf("Coda ELIMINATA e memoria recuperata ! "); getchar(); } n = 0; return 0; } int gotorc(int r, int c) { // posiziona il cusore a riga 'r' e colonna 'c' HANDLE Hout; CONSOLE_SCREEN_BUFFER_INFO ConsoleInfo; Hout = GetStdHandle(STD_OUTPUT_HANDLE); ConsoleInfo.dwCursorPosition.Y = r; ConsoleInfo.dwCursorPosition.X = c; SetConsoleCursorPosition(Hout,ConsoleInfo.dwCursorPosition); }