PROGRAMARE MODULARA

PROGRAMARE MODULARA

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 sint inrudite daca utilizeaza in comun diferite date. De exemplu, functiile zi_din_an si luna_si_ziua, definite in capitolul precedent, se considera ca sint inrudite. Ele utilizeaza in comun tabloul global nrzile.

Un modul se compune din unul sau mai multe fisiere, in cazul in care el se compune din mai multe fisiere, acestea se compileaza impreuna incluzindu-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 de descompunere se poate continua, adica subproblemele obtinute la o prima descompunere pot fi si ele la rindul lor descompuse in altele mai simple si asa mai departe, pina cind 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. Adesea se spune ca datele respective sint vizibile numai la nivel de modul. Ele pot fi utilizate in alte module numai prin intermediul procedurilor modulului in care sint vizibile. Mai mult decit atit, pot exista cazuri in care este avantajos ca si anumite proceduri dintr-un modul sa fie ascunse. La acestea nu se pot face apeluri din alte module. Ele pot fi apelate numai de procedurile modulului in care sint 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, cind participa colective mari pentru programarea si implementarea lor.

Prin programarea modulara intelegem stilul de programare care are la baza utilizarea de 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 sint 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:

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

Prin stiva intelegem o multime ordonata de elemente 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 stivei se pot pastra elementele ei, unul dupa altul. De asemenea, ele se pot scoate din zona de memorie respectiva, unul cite unul, in ordine inversa pastrarii lor.

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

Virful stivei se modifica arunci cind se pune un element pe stiva sau cind se scoate de pe stiva. In primul caz lungimea stivei (numarul elementelor din stiva) creste, iar in cel de al doilea caz descreste.

intr-adevar, cind se pune un element pe stiva, atunci acesta se pune dupa cel aflat in virful stivei si prin aceasta virful stivei se modifica asa incit elementul nou pus pe stiva sa fie in virful ei. Cind se ia un element de pe stiva, atunci acesta este cel aflat in virful stivei si apoi virful stivei se modifica asa incit, elementul care a fost pus pe stiva inaintea celui scos, sa fie in virful ei.

<figura>Punerea unui element pe stiva

inainte de a pune un element pe stiva

Dupa ce s-a pus un element pe stiva

<figura>Scoaterea unui element de pe stiva

inainte de a scoate un element de pe stiva

Dupa ce s-a scos un element de pe stiva

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

si

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.

Vom pastra si noi aceste denumiri.

Am spus mai sus ca vom implementa stiva folosind un tablou unidimen­sional. Acesta va fi in cazul de fata de tip int. Numim stack acest tablou.

stack[0] este elementul de la baza stivei.

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

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

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

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

De obicei, se definesc si alte functii (vezi[5]) 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 virful stivei, fara a-1 scoate din stiva.

Toate aceste functii trebuie sa aiba acces atit la stack, cit 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 putind 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 aceasta 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 virful 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 virful 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 ca si pop, cu deosebirea ca nu se elimina elementul din virful 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 l daca stiva este vida si zero in caz contrar.

Functia full are prototipul:

int full(void);

Ea returneaza valoarea l daca stiva este plina si zero 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 tablou de tip int.

<titlu>MODULUL BVII1

#define MAX

static int stack[MAX] ;

static int next

void push( int x) /* pune x pe stiva */

int pop ( ) /* scoate din stiva elementul din virful ei */

int top /* returneaza elementul din virful stivei */

void clear /* videaza stiva */

int empty /* returneaza 1 daca stiva este vida si 0 altfel */

int full /* returneaza 1 daca stiva este plina si 0 altfel */

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 (*) si 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 sint in forma poloneza postfixata:

fexp1 op fexp2

atunci forma poloneza postfixata a acestei expresii este

fexp1 fexp2 op

Exemple:

<tabel>

*Expresie aritmetica

*Echivalentul ei in forma poloneza postfixata

</tabel>

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

Expresia aritmetica in forma poloneza postfixata, pe masura ce se con­struieste, se pastreaza intr-un tablou tefpp de tip caracter.

Algoritmul de traducere are urmatorii pasi:

a.  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.

b.  Paranteza deschisa se introduce automat in stiva.

c.  Un operator se introduce in stiva daca in virful stivei se afla:

- paranteza deschisa;

- un operator de prioritate mai mica; sau

- stiva este vida.

Daca in virful stivei se afla un operator de prioritate mai mare sau egalaxu a celui curent, atunci operatorul din virful stivei se scoate din stiva si se pastreaza in tabloul tefpp. Apoi se compara din nou operatorul din virful stivei cu cel curent si se reia pasul

d.  La intilnirea unei paranteze inchise, se scot pe rind operatorii din stiva si se introduc in tabloul tefpp, pina la intilnirea parantezei deschise din stiva. Aceasta pur si simplu se elimina din stiva. Apoi se continua cu urmatorul element al expresiei.

e.  La terminarea parcurgerii expresiei, se scot pe rind 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, pina la tastarea sfirsitului de fisier.

Mentionam ca metoda de transcriere a expresiilor descrisa mai sus, functioneaza exact 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 in exercitiul precedent (fisierul sursa BVII1.CPP) 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 obtinindu-se doua module de tip OBJ care urmeaza apoi a fi link-editate impreuna pentru a obtine imaginea executabila a programului.

Cele doua fisiere de tip sursa pot fi compilate si impreuna, procedind ca pina acum, adica incluzind fiserul BVH l .CPP in fisierul BVII2.CPP.

De asemenea, fisierele respective pot fi compilate si link- editate folosind un fisier de tip Project. Acesta se editeaza utilizind meniul Project al mediului integrat de dezvoltare Turbo C++.

Mai jos s-a adoptat varianta cu includerea fisierului B VII l .CPP.

Fisierul BVII2.CPP, 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, pina la intilnirea 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.

<titlu>PROGRAMUL BVII

#include <stdio.h>

#include 'bviil.cpp'

#define MAXTEFPP 1000

int sca (int); /* prototipul fiinctiei sca */

/* prototipul functiilor push, pop si clear sint necesare cind cele doua

fisiere se compileaza separat; in cazul de fata sint in plus */

void push(int);

int pop(void);

void clear(void);

main /* transforma expresii aritmetice in forma poloneza postfixata */

/* sfirsit while

/* 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)  /* sfirsit switch

if ( c!=';' && c != EOF )

/* avans la caracterul urmator din expresie */

c = getchar();

} /* sfirsit while l */

/* sfirsit 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 */

} /* sfirsit for neimbricat */

} /* sfirsit main */

int scaiint x) /* salt peste caractere albe */