Programmi C / C++ - prof. Claudio Maccherani - Perugia - 2008
PILA (L.I.F.O.)
/* Adt, dato astratto PILA o STACK - L.I.F.O. realizzata tramite lista semplice: inserimento in testa, estrazione in testa Dev-C++ - prof. Claudio Maccherani - Perugia - 2008/09 */ #include
#include
#include
#include
struct elem // definisce il tipo dell'elemento della pila (lista) { int info; // "info" = informazine elem *pun; // "pun" = puntatore prossimo elemento }; elem *p; // definisce un generico elemento della pila (lista) elem *top; // definisce l'elemento iniziale (TOP) int n; // numero elementi della pila int x; // valore dell'elemento da inserire / estrarre const int col=10; // colonna per menu int creaPila(char flag); // crazione pila int elencoPila(bool tit); // elenco elementi della pila int inserimentoElem(); // inserimento di un elemento in pila int Push(int x); // inserimento elemento (in testa alla lista) int estrazioneElem(); // estrazione di un elemento int Pop(); // estrazione elemento (dalla testa della lista) int eliminaPila(char flag); // eliminazione pila 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 'PILA/STACK' con lista semplice'
"); if (n > 0){ gotorc( 2,col); printf(" [ pila corrente di %d elementi ]",n); } gotorc( 4,col); printf("1 - Creazione AUTOMATICA della pila"); gotorc( 6,col); printf("2 - Creazione MANUALE della pila"); gotorc( 8,col); printf("3 - Elenco degli elementi della pila"); gotorc(10,col); printf("4 - Inserimento di un elemento (PUSH)"); gotorc(12,col); printf("5 - Estrazione di un elemento (POP)"); gotorc(14,col); printf("6 - Cancellazione della pila"); gotorc(17,col); printf(" scegli (0=fine) ... "); cin>>scelta; switch (scelta) { case 1: { creaPila('a'); break; } case 2: { creaPila('m'); break; } case 3: { elencoPila(true); break; } case 4: { inserimentoElem(); break; } case 5: { estrazioneElem(); break; } case 6: { eliminaPila('i'); break; } } } while (scelta!= 0); eliminaPila(' '); // elimina l'eventuale pila e libera la memoria return 0; } int creaPila(char flag){ // crazione pila ('a'=automatica, 'm'=manuale)------- system("cls"); gotorc( 1,col); printf("Creazione della pila (a partire dall'ultimo)"); gotorc( 3,col); printf("Numero elementi della pila: "); cin>>n; cout <<"\n"; top = NULL; // inizializza 'top' 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 = top; // da al puntatore l'indirizzo del precedente top = p; } // da al puntatore inizio lista l'indirizzo dell'inserito getchar(); return 0; } int elencoPila(bool tit){ // elenco elementi della pila ---------------------- if (tit) { system("cls"); gotorc( 1,col); printf("Elenco elementi della lista\n\n"); } p = top; // imposta 'p' con il TOP while (p != NULL) { // fin quando non si raggiunge il puntatore NULL if (p == top) cout<<"TOP:"; cout<<"-> "<< p->info<<" "; // visualizza l'informaz. dell'elem.corrente p = p->pun; } // 'p'=pun.elemento corrente, passa al successivo if (tit) getchar(); return 0; } int inserimentoElem(){ // inserimento di un elemento ------------------------- system("cls"); gotorc( 1,col); printf("Inserimento di un elemento\n\n"); elencoPila(false); gotorc( 5,col); gotorc( 6,col); printf("Elemento da inserire: "); scanf("%d",&x); Push(x); n = n + 1; cout<<"\n"; elencoPila(false); getchar(); getchar(); return 0; } int Push(int x){ // inserimento di un elemento (in testa alla lista)---------- elem *pp; // 'appoggio' per inserimento pp = top; // salva il TOP attuale top = new elem; // crea il nuovo TOP (l'elemento da inserire) top->info = x; // gli assegna il valore top->pun = pp; // lo collega alla pila assegnandogli il TOP return 0; } int estrazioneElem(){ // estrazione di un elemento --------------------------- system("cls"); gotorc( 1,col); printf("Estrazione di un elemento\n\n"); if (n > 0) // la pila non è vuota { elencoPila(false); x = Pop(); n = n - 1; cout<<"\n\nL'elemento estratto e': "<
info; // estrae l'elemento (top) pp = top; // salva il TOP (puntatore al primo, da eliminare) top = top->pun; // il TOP assume il valore del puntatore del 1° elemento // (che ora punta al secondo) free(pp); // libera la memoria dell'elemento estratto return x; } int eliminaPila(char flag){ // eliminazione pila e recupero memoria ---------- // (se 'flag'='i' inteattivo) if (flag == 'i') {system("cls"); gotorc( 1,col); printf("Eliminazione pila e recupero memoria\n\n"); } int j=0; elem *pp; if (n > 0) { p = top; // imposta 'p' con il puntatore inizo pila (TOP) while (p != NULL) { // fin quando non si raggiunge il puntatore NULL top->pun = p->pun; free(p); p = top->pun; } // 'p'=pun.elem.corrente, passa al successivo top = NULL; } if (flag == 'i') { gotorc( 3,col); printf("Pila 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); }