Programare modulara

7. Programare modulara

2019/03/01 in Programare in C

Un program poate fi format din mai multe module.

Numim modul sursa o parte a textului sursa al programului care se compileaza printr-o singura compilare si separat de restul textului sursa al programului respectiv. Rezultatul compilarii unui modul sursa este un modul obiect.

In cele ce urmeaza, prin modul vom intelege un modul sursa. Modulele obiect le vom mai numi si module de tip OBJ.

De obicei, programele simple se compun dintr-un singur modul sau un numar relativ mic de module (4-5).

In componenta unui modul intra proceduri "inrudite". Aceasta notiune nu este definita riguros. De obicei, spunem ca mai multe proceduri sunt inrudite daca utilizeza in comun diferite date. De exemplu, functiile zi_din_an si luna_si_ziua, definite la capitolul precedent, se considera ca sunt inrudite. Ele utilizeaza in comun tabloul global nrzile.

Un modul se compune din unul sau mai multe fisiere. In cazul in care se compune din mai multe fisiere, acestea se compileaza impreuna incluzandu-le unul in altul cu ajutorul constructiei #include.

Modulele de tip OBJ obtinute prin compilarile modulelor din compunerea unui program pot fi reunite intr-un fisier executabil (cu extensia EXE) cu ajutorul editorului de legaturi.

Modulele unui program se definesc ca rezultat al procesului de descompunere a unei probleme in subprobleme mai simple. Acest proces se poate continua, adica subproblemele pot fi si ele la randul lor descompuse in altele mai simple si asa mai departe, pana cand se ajunge ca toate subproblemele de la nivelurile inferioare sa fie relativ simple. Diferite componente ale unei astfel de descompuneri se realizeaza prin module. De obicei, aceste module se pot realiza in paralel si relativ independent de catre mai multi programatori, ceea ce conduce la cresterea eficientei in programare.

Un avantaj mare pe care il ofera modulele este asa numita posibilitate de ascundere a datelor. Aceasta inseamna ca la o parte sau chiar la toate datele unui modul au acces direct numai procedurile din compunerea modulului respectiv. Se spune ca datele respective sunt vizibile numai la nivel de modul. Ele pot fi utilizate in alte module numai prin intermediul procedurilor modulului in care sunt vizibile. Mai mult decat atat, pot exista cazuri in care este avantajos ca si anumite proceduri dintr-un modul sa fie ascunsa. La acestea nu se pot face apeluri din alte module. Ele pot fi apelate numai de procedurile modulului in care sunt definite si ascunse.

Facilitatea de ascundere a datelor si procedurilor in module constituie o protectie impotriva deteriorarii datelor prin accese neautorizate din alte module. Aceasta protectie devine importanta mai ales in cazul problemelor complexe, cand participa colective mari pentru programarea si implementarea lor.

Prin programare modulara se intelege stilul de programare care are la baza module in vederea "ascunderii" datelor si procedurilor pentru a realiza protectia datelor respective fata de accese neautorizate.

Limbajul C a fost proiectat in ideea de a permite utilizarea programarii modulare. In acest caz modulul contine functii "inrudite". Datele statice, declarate in afara functiilor modulului, pot fi utilizate in comun de catre aceste functii. Ele sunt ascunse in modul, deoarece functii din alte module nu pot face acces direct la ele.

De asemenea, se pot defini si functii statice, ceea ce conduce la ascunderea lor in modulul in care au fost definite.

O functie statica poate fi apelata numai de functii definite in acelasi modul cu ea.

Exercitii:

7.1. Sa se realizeze un modul care implementeaza o stiva ale carei elemente sunt de tip int.

Prin stiva intelegem o multime ordonata de elemenete la care se are acces in conformitate cu principiul LIFO (Last In First Out).

Cel mai simplu procedeu de implementare a unei stive este pastrarea elementelor ei intr-un tablou unidimensional. Ulterior, vom vedea si alte moduri de implementare a unei stive.

In zona de memorie alocata unei stive se pot pastra elemenetele ei, unul dupa altul. De asemenea, ele se pot scoate din zona de memorie respectiva, unul cate unul, in ordine inversa pastrarii lor.

Ultimul element pus pe stiva se spune ca este varful stivei. Primul element pus pe stiva se afla la baza stivei.

Varful stivei se modifica atunci cand se pune un element pe stiva sau cand se scoate de pe stiva. In primul caz lungimea (numarul elemnetelor) stivei creste, iar in cel de-al doilea caz descreste.

Intr-adevar, cand se pune un element pe stiva, atunci acesta se pune dupa cel aflat in varful stivei si prin aceasta varful stivei se modifica asa incat elementul nou pus pe stiva devine varful ei. Cand se ia un element de pe stiva, atunci acesta este cel aflat in varful stivei si apoi varful stivei se modifica asa incat elementul care a fost pus pe stiva inaintea celui scos sa fie varful ei.

Punerea unui element pe stiva

Inainte de a se pune un element pe stiva
n (varful stivei)
n-1
.
.
.
1 (baza stivei)

Dupa ce s-a pus un element pe stiva
n+1 (varful stivei)
n
n-1
.
.
.
1 (baza stivei)

Scoaterea unui element de pe stiva

Inainte de a scoate un element pe stiva
n+1 (varful stivei)
n
n-1
.
.
.
1 (baza stivei)

Dupa ce s-a scos un element pe stiva
n (varful stivei)
n-1
.
.
.
1 (baza stivei)

Se observa ca totdeauna, ultimul element pus pe stiva este primul care se scoate din stiva. De aici provine afirmatia ca o stiva se gestioneaza conform principiului LIFO.

Pentru a implementa o stiva vor fi necesare doua functii:

una care sa puna un element pe stiva;
una care sa scoata un element din stiva.

Aceste functii au denumiri deja consacrate in literatura de specialitate si anume, functia care pune un element pe stiva se numeste push, iar cealalta pop.

Asa cum am precizat, stiva se va implementa folosind un tablou unidimensional. In cazul de fata, acesta va fi de tip int. Numim stack acest tablou, iar stack[0] este elementul de la baza stivei.

Functiile push si pop gestioneaza varful stivei si de aceea ele au nevoie de o variabila care sa defineasca indicele elementului din varful stivei. De obicei, se pastreaza indicele primului element liber, adica indicele elementului tabloului stack care urmeaza imediat dupa elementul aflat in varful stivei.

Numim next variabila a carei valoare curenta este indicele primul element liber al tabloului stack.

Evident, initial next = 0, deoarece la inceput nefiind niciun element pe stiva, stack[0] este primul element liber.

Utilizatorul stivei nu trebuie sa aiba acces direct la elementele stivei si de aceea atat tabloul stack, cat si variabila next trebuie "ascunse" in modul. In felul acesta, utilizatorul are posibilitatea sa puna un element pe stiva in varful ei apeland functia push si sa scoata elementul din varful stivei apeland functia pop. Rezulta ca aceste doua functii nu se "ascund" in modul.

De obicei, se definesc si alte functii, cum ar fi:

clear	pentru a vida stiva;
empty	stabileste daca stiva este vida sau nu;
full	stabileste daca stiva este plina sau nu;
top	permite acces la elementul din varful stivei, fara a-l scoate din stiva.

Toate aceste functii trebuie sa aiba acces atat la stack, cat si la variabila next.

De aceea stack si next se vor declara statice in afara corpurilor lor.

Cele 6 functii amintite mai sus vor avea un caracter global, ele putand fi apelate din orice modul al programului.

Functia push are prototipul:

void push(int x);

In principiu, ea pune pe stiva valoarea lui x, deci trebuie sa faca atribuirea:

stack[next] = x

si apoi sa incrementeze pe next pentru ca acesta sa defineasca locul liber curent. De aceea, atribuirea de mai sus se poate realiza impreuna cu incrementarea lui next:

stack[next++] = x

Functia trebuie sa testeze, in prealabil, daca exista loc liber pentru a pastra pe x si numai in acest caz se va executa atribuirea de mai sus. In caz ca stiva este plina (depasita), se da un mesaj de eroare.

Functia pop are prototipul:

int pop(void);

Ea returneaza valoarea din varful stivei. In acest scop se va decrementa next si apoi se va returna valoarea elementului stack[next].

Aceste doua actiuni se pot realiza cu ajutorul instructiunii:

return stack[--next];

Se observa ca prin aceasta varful stivei coboara cu un element, deoarece next, care exprima primul element liber, este chiar indicele elementului eliminat de pe stiva.

Inainte de a executa instructiunea de mai sus, functia pop va testa daca stiva nu cumva este vida. In cazul in care stiva este vida, functia pop va afisa un mesaj de eroare si va returna valoarea zero.

Functia top este identica cu pop, cu deosebirea ca nu se elimina elementul din varful stivei, ci numai se returneaza valoarea lui.

Functia clear are prototipul:

void clear(void);

Ea videaza stiva, ceea ce se realizeaza simplu prin atribuirea valorii zero variabilei next. In felul acesta, tot tabloul devine liber.

Functia empty are prototipul:

int empty(void);

Ea returneaza valoarea 1 daca stiva este vida si 0 in caz contrar.

Functia full are prototipul:

int full(void);

Ea returneaza valoarea 1 daca stiva este plina si 0 in caz contrar.

Aceste functii, impreuna cu declaratiile lui stack si next se pastreaza intr-un fisier care formeaza modulul ce implementeaza stiva stack prin intermediul unui tablu de tip int.

MODULUL093.C - Functii implementare stiva

#define MAX 1000

static int stack[MAX];
static int next = 0;

void push(int x)
{
  if(next < MAX)
    stack[next++] = x;
  else
    printf("stiva este plina\n");
}

int pop()
{
  if(next > 0)
    return stack[--next];
  else
    printf("stiva vida\n");
}

int top()
{
  if(next > 0)
    return stack[next-1];
  else
    printf("stiva vida\n");
}

void clear()
{
  next = 0;
}

int empty()
{
  return !next;
}

int full()
{
  return next == MAX;
}

7.2. Sa se scrie un program care transcrie o expresie cu operanzi numere naturale in forma poloneza postfixata.

Prin expresie aritmetica intelegem o expresie in care pot fi utilizate numai cele 4 operatii binare:

adunare (+);
scadere (-);
inmultire (*);
impartire (/).

Se pot utiliza parantezele rotunde pentru a schimba prioritatea operatorilor.

Forma poloneza postfixata a unei expresii aritmetice se poate defini ca mai jos:

forma poloneza postfixata a unui operand coincide cu el insusi daca nu este inclus in paranteze rotunde;
forma poloneza postfixata a unui operand de forma (exp) coincide cu forma poloneza postfixata a lui exp;
daca operatorul binar op leaga expresiile fexp1 si fexp2 care sunt in forma poloneza postfixata:
```
fexp1 op fexp2
```
atunci forma poloneza postfixata a acestei expresii este:
```
fexp1 fexp2 op
```

Exemple:

Expresia aritmetica	Echivalentul ei in forma poloneza postfixata
1+2	1 2 +
1+2*3	1 2 3 * +
(1+2)*3	1 2 + 3 *

Un algoritm simplu pentru a transforma o expresie aritmetica in forma poloneza postfixata se bazeaza pe utilizarea unei stive in acre se pastreaza temporar operatorii expresiei. In acest scop se va folosi stiva implementata prin modulul din exemplul precedent.

Expresia aritmetica in forma poloneza postfixata, pe masura ce se construieste, se pastreaza intr-un tablou tefpp de tip char.

Algoritmul de traducere are urmatorii pasi:

un operand se pastreaza automat in tabloul tefpp. Acest lucru rezulta din faptul ca prin aceasta transformare operanzii isi pastreaza ordinea din expresia initiala. Apoi se continua cu urmatorul element al expresiei.
paranteza deschisa se introduce automat in stiva.
un operator se introduce in stiva daca in varful stivei se afla:
- paranteza deschisa;
- un operator de prioritate mai mica;
- stiva este vida.
Daca in varful stivei se afla un operator de prioritate mai mare sau egala cu cu a celui curent, atunci operatorul din varful stivei se scoate din stiva si se pastreaza in tabloul tefpp. Apoi se compara din nou operatorul din varful stivei cu cel curent si se reia pasul 3.
la intalnirea unei paranteze inchise, se scot pe rand operatorii din stiva si se introduc in tabloul tefpp, pana la intalnirea parantezei deschise din stiva. Apoi se continua cu urmatorul element al expresiei.
la terminarea parcurgerii expresiei se scot pe rand toti operatorii care se mai afla in stiva si se trec in tefpp.

Se presupune ca expresia se termina cu punct si virgula.

La baza stivei se va afla caracterul NUL ('\0').

Programul de fata poate transforma mai multe expresii, pana la tastarea sfarsitului de fisier.

Metoda de transcriere descrisa mai sus functioneaza numai daca expresia respectiva este corecta din punct de vedere sintactic.

In mod normal, acest program se compune din doua module, unul care a fost definit la exercitiul precedent (fisierul sursa MODULUL093.C) si prin care se implementeaza o stiva pe care se pun elementele de tip int, iar cel de-al doilea modul defineste functia principala.

Cele doua module se pot compila distinct obtinandu-se doua module de tip OBJ care urmeaza apoi sa fie link-editate impreuna pentru a obtine imaginea executabila a programului.

Cele doua fisiere sursa pot fi compilate si impreuna, incluzand MODULUL093.C in Programul 093.

Se mai poate folosi un fisier de tip Project in care cele doua fisiere sunt compilate si link-editate impreuna.

Programul 093, alaturi de functia principala mai contine o functie denumita sca. Aceasta are prototipul:

int sca(int c);

Ea realizeaza saltul peste caracterele albe.

Daca c are ca valoare codul ASCII al unui caracter alb, atunci se citesc caracterele care urmeaza, pana la intalnirea primului caracter care nu este alb. La revenire, se returneaza codul ultimului caracter citit. Daca c are ca valoare codul unui caracter ASCII care nu este alb, atunci se revine din functie cu codul caracterului respectiv.

Programul 093 - Expresie aritmetica in forma poloneza postfixata

#include <stdio.h>
#include "MODULUL093.C"

#define MAXTEFPP 1000

int sca(int); /* prototipul functiei sca */
/* prototipul functiilor push, pop si clear sunt in plus aici, /
ar fi necesar daca fisierele s-ar compila separat */
void push(int);
int pop(void);
void clear(void);

main() /* transforma expresii aritmetice in forma poloneza */
{
    int c, i, j;
    char tefpp[MAXTEFPP];

    for( c = getchar(); c != EOF; ) {
        i = 0; /* indice pentru tefpp */
        clear(); /* videaza stiva */
        push('\0'); /* zero la baza stivei */
        while( (c=sca(c)) != ';' && c != EOF ) {
            /* c nu este alb, punct si virgula sau sfarsitul de fisier */
            while( c >= '0' && c <= '9') {
                /* se pastreaza un operand */
                tefpp[i++] = c;
                c = getchar();
            }
            /* s-a terminat un operand; poate urma un caracter alb,
            un operator, punct si virgula sau EOF */
            c = sca(c); /* salt peste caracterele albe, daca exista */
            tefpp[i++] = ' '; /* spatiu dupa operand */
            switch(c) {
            case '(': /* paranteza deschisa se pune pe stiva */
                push(c);
                break;
            case(')'): /* paranteza inchisa: se scot operatorii din
                stiva pana la paranteza deschisa si se trec in tefpp */
                while( (c = pop()) != '(' )
                    tefpp[i++] = c;
                break;
            case '+':
            case '-': /* se scot operatorii de pe stiva si
                se trec in tabloul tefpp */
                while( (j=pop())=='+' || j=='-' || j=='*' || j=='/')
                    tefpp[i++] = j;
                /* ultimul element scos de pe stiva se repune */
                push(j);
                /* se pune pe stiva operatorul curent */
                push(c);
                break;
            case '*':
            case '/': /* se scot de pe stiva operatorii * si / */
                while( (j=pop())=='*' || j=='/' )
                    tefpp[i++] = j;
                /* ultimul element scos de pe stiva se repune */
                push(j);
                /* se pune pe stiva operatorul curent */
                push(c);
                break;
            case ';': /* sfarsit expresie */
                break;
            default: /* expresie eronata */
                printf("caracter eronat: %c\t%d\n", c, c);
                /* se cauta sfarsitul expresiei sau EOF */
                while( c != ';' && c != EOF )
                    c = getchar();
            }
            if( c != ';' && c != EOF )
                /* avans la caracterul urmator din expresie */
                c = getchar();
        }
        /* sfarsit expresie: se trec operatorii din stiva in tefpp, daca exista */
        while((j=pop()) != '\0' )
            tefpp[i++] = j;
        /* se afiseaza forma poloneza postfixata a expresiei curente */
        putchar('\n');
        for(j = 0; j < i; j++)
            putchar(tefpp[j]);
        putchar('\n');
        /* la EOF se termina executia; altfel, se citeste primul caracter al /
        expresiei urmatoare */
        if(c == EOF)
            break;
        c = getchar();
        c = sca(c); /* avans peste caractere albe */
    }
}

int sca(int x) /* salt peste caractere albe */
{
    while(x == ' ' || x == '\t' || x == '\n')
        x = getchar();
    return x;
}

8. Pointeri