curs 10 - profs.info.uaic.rodlucanu/cursuri/ap/resurse/curs10.pdf · studiu de caz: evaluarea...

Algoritmi si Programare 2005 - 2006 1

Curs 10

Domeniu de vizibilitateClase de alocareDirective preprocesorStudiu de caz: evaluarea expresiilor aritmeticeOperaţii la nivel de bitCâmpuri de biţi în structuri


Domeniul de vizibilitate – “scope”Un nume (variabilă, funcţie) poate fi utilizat numai dupăce a fost declarat. Declaraţia descrie proprietăţile numelui

Domeniul de vizibilitate (scope) al unui nume este mulţimea instrucţiunilor (liniilor de cod) în care poate fi utilizat acel nume(numele este vizibil)

Regula de bază: identificatorii sunt accesibili doar în blocul în care au fost declaraţi; ei sunt necunoscuţi în afara acestor blocuri.

variabile globale – variabile ce sunt declarate în afara oricărui bloc

variabile locale sunt cele declarate:în funcţiiîn blocuri ca parametri


Domeniul de vizibilitate – “scope”

Blocuri paralele: {…}…{…}. În acest caz cel de-al doilea bloc “nu ştie” nimic de variabilele declarate în primul bloc.

Funcţiile sunt declarate “în paralel”

Blocuri cuibărite: {…{…}…}. Un nume declarat în blocul exterior este vizibil în cel interior dacănu este redefinit aici; în acest din urmă caz,numele din blocul exterior este “ascuns” sau “mascat”. Spunem că fiecare bloc are “propria nomenclatură” pentru numele variabilelor


Domeniul de vizibilitate#include <stdio.h>int a;int f(int x){

int y;y = x + a;{double a;a = (double)y * 2.0;y += (int) a;

}a = y – x;

}

variabila locala

variabila globala

parametru


Exemplu

{int a = 1, b = 2, c = 3;printf(“%2d%2d%2d\n”, a, b, c); /* 1 2 3 */{

int b = 4; float c = 5.0f; printf(“%2d%2d%4.1f\n”, a, b, c); /* 1 4 5.0 */a = b;{

int c; c = b; printf(“%2d%2d%2d\n”, a, b, c); /* 4 4 4 */

}printf(“%2d%2d%4.1f\n”, a, b, c); /* 4 4 5.0 */

}printf(“%2d%2d%2d\n”, a, b, c); /* 4 2 3 */

}


Clase de alocare a memoriei

Zona de memorie utilizată de un program C cuprinde 4 subzone:

Zona text: codul programuluiZona de date: variabilele globaleZona stivă: date temporare (variabilele locale)Zona heap: memoria dinamică

Clasele de alocare a variabilelor:Statică: variabile implementate în zona de dateAuto: variabile implementate în stivăDinamică: variabile implementate în heap , alocate dinamicRegister: variabile implementate într-un registru de memorie


Alocarea implicităDurata de viaţă vs. domeniu de vizibilitate

nucu zeroIniţializare

cea a blocului în care e declarată

cea a întregului program

Durata de viaţă

autola execuţie bloc

staticăla compilareAlocare

Variabile locale

Variabile globale


Clase de alocare

Se poate utiliza cuvântul cheie auto în declararea variabileor locale:

auto int a, b, c;auto double f;

Clasa de alocare extern: o variabilă (globală) sau o funcţie declarată extern este vizibilă şi în alt fişier decât cel în care a fost declarată

Funcţiile au clasa de alocare extern; cuvântul cheie extern poate fi utilizat la declararea/definirea funcţiilor:

extern double sinus(double);


Clase de alocare - exemplu

/* fisierul main.c */int a = 1, b = 2, c = 3; /* variabile globale */int f(void); /* prototip */int main(void){printf(“a = %d, b = %d, c = %d, f() = %d\n”);

}

/* fisierul f.c */int f(void){extern int a; /* cauta a in afara fisierului */int b, c; /* b, c locale */a = b = c = 22;return (a + b + c);

}


Clasa de alocare static - local

O variabilă locală declarată static are durata de viaţă egală cu cea a programului: la intrarea în bloc valoarea sa este cea care a avut-o la ieşire:

int f(void){static int contor = 0;return contor++;

}f(); f(); f();

Domeniu de vizibilitate vs. Durata de viaţă


Exemplu#include <stdio.h>int f(void);int main(void) {

int i;for (i=0; i<10; i++){

if(!(i%3))printf("\nFunctia f() este apelata a %d-a oara.", f());

}return 0;

}int f(void) {

static int nr_apeluri=0;nr_apeluri++; return nr_apeluri;

}/*Functia f() este apelata a 1-a oara.Functia f() este apelata a 2-a oara.Functia f() este apelata a 3-a oara.Functia f() este apelata a 4-a oara.*/


Clasa de alocare static - externO variabilă globală declarată static are domeniul de vizibilitate redus la fişierul sursăîn care este declarată, doar după declaraţia sa:

int f(void){/*variabila v nu este vizibila*/}static int v; void g(void){/* v este vizibila aici */}

O funcţie definită/declarată static este vizibilădoar în fişierul în care apare definiţia sa.


Clasa de alocare static - extern

static int g(void); /* prototip */void f(int a){…/* g este vizibila aici */

}static int g(void){…}/* g nu este vizibila in alt fisier */


Clasa de alocare registerO variabilă declarată register solicită sistemului alocarea ei într-un registru maşină, dacă este posibilSe utilizează pentru variabile “foarte solicitate”, pentru mărirea vitezei de execuţie:

{register int i;for(i = 0; i < N; ++i){

/*… */}

} /* se elibereaza registrul */


Domeniul de vizibilitate - rezumatÎntr-un fişier (resp. bloc) un identificator este vizibil dupădeclararea sa până la sfârşitul fişierului (resp. blocului) cu excepţia blocurilor(resp. subblocurilor) în care este redeclarat

Definiţia unui identificator mascheaza pe cea a aceluiaşi identificator declarat într-un suprabloc sau în fişier (global)

Apariţia unui identificator face referinţă la declararea sa în cel mai mic bloc (sau fişier) care conţine această apariţie

Funcţiile şi variabilele globale ale unei unităţi de program (fişier) sunt implicit publice: sunt accesibile din alte unităţi de program.extern indică o declaraţie fără definire: permite referirea unei variabile globale definită în afara unităţii de program.

static face ca o variabilă globală sau o funcţie să fie privată(proprie) unităţii unde a fost definită: ea devine inaccesibilă altei unităţi, chiar prin folosirea lui extern.


PreprocesorulDirectivele #include si #define#include <nume_fisier>#include “nume_fisier”

#define nume_macrodef#define nume_macrodef macrodef#define nume_macrodef(lista_arg)#define nume_macrodef(lista_arg) macrodefnume_macrodef ::= identificatorarg ::= identificator |(identificator)lista_arg ::= arg |lista_arg, argmacrodef ::= sir_unitati_lexicale_si_arg


Directivele #include si #define

#define pi 3.14159#define egal ==#define citeste scanf#define patrat(x) ((x)*(x))#define cub(x) (patrat(x)*(x))#define min(x,y) (((x)<(y))?(x):(y))#define printTablou(a, n, sirControl) \

for (i = 0; i < n; i++) \printf(sirControl, a[i]); \putchar(‘\n’)

#define new(X) (X*)malloc(sizeof(X))


#define Exemplu

#include <stdio.h>#define swap(t,a,b) {t temp=a;a=b;b=temp;}int main(){

int i=10, j=20;float x=1.23,y=3.21;printf("\ni=%d, j=%d, x=%f, y=%f",i,j,x,y);swap(int,i,j);swap(float,x,y);printf("\ni=%d, j=%d, x=%f, y=%f",i,j,x,y);return 0;

}/*i=10, j=20, x=1.230000, y=3.210000i=20, j=10, x=3.210000, y=1.230000*/


Macroul assert() din assert.h

Se utilizează în programe pentru a ne asigura că valoarea unei expresii este cea pe care o anticipăm

Dacă o aserţiune eşueaza – “ condiţia nu este îndeplinită “se va afişa un mesaj şi programul încetează a se executa

#include <assert.h>void f(char *p, int n){

assert( p != NULL):assert(n > 0 && n < 10);/*…*/

}

assert(b*b-4.*a*c >= 0);


Macrouri în stdio.h şi ctype.h

#define getchar() getc(stdin)#define putchar(c) putc((c), stdout)

#define NULL ((void*)0)

toupper(c) /* întoarce valoarea “upercase” corespunzătoare lui c */tolower(c) /* întoarce valoarea “lowercase” corespunzătoare lui c */toascii(c) /* întoarce valoarea ASCII corespunzătoare lui c */

isalpha(c) /* întoarce nonzero dacă c este literă */ isdigit(c) /* întoarce nonzero dacă c este cifră */isalnum(c) /* întoarce nonzero dacă c este litera sau cifră*/islower(c) /* întoarce nonzero dacă c este litera mică */isupper(c) /* întoarce nonzero dacă c este litera mare */isgraph(c) /* întoarce nonzero dacă c este printabil, nu spaţiu */isprint(c) /* întoarce nonzero dacă c este caracter printabil*/isxdigit(c) isspace(c) ispunct(c) iscntrl(c) isascii(c)


Macrouri predefinite

__DATE_ _ /* şir care conţine data curentă */

_ _FILE_ _ /* şir care conţine numele fişierului */

_ _LINE_ _ /* conţine numărul liniei curente */

_ _STDC_ _ /* are valoarea nonzero dacăimplementarea este ANSI standard C */

_ _TIME_ _ /* şir care conţine timpul curent */


Macrouri predefinite

#include <stdio.h>int main(void){

printf("Macrourile predefinite: \n");printf("__DATE__ = %s\n", __DATE__);printf("__FILE__ = %s\n", __FILE__);printf("__LINE__ = %d\n", __LINE__);printf("__STDC__ = %d\n", __STDC__);printf("__TIME__ = %s\n", __TIME__);return 0;

}/*Macrourile predefinite:__DATE__ = Dec 8 2003__FILE__ = ../Surse/Macro.c__LINE__ = 6__STDC__ = 1__TIME__ = 17:43:24*/


Directive pentru compilarecondiţionată

#if expr_const_intreagă

#else

#elif /* pentru else if */

#ifdef identificator

#ifndef identificator

#undef identificator

#endif


Directive pentru compilarecondiţionată#define DEBUG 1/*. . .*/#if DEBUG /* sau: #ifdef DEBUG */printf(“debug: a = %d\n”, a);#endif

#if VERSIUNE == 1#define FISIERINCLUS “fis1.h”#elif VERSIUNE == 2#define FISIERINCLUS “fis2.h”#else#define FISIERINCLUS “fis.h”#endif#include FISIERINCLUS


Studiu de caz: Evaluarea expresiilor

24 + 10/5 - 4*3 Forma poloneză postfixată o considerăm reprezentată ca un şir:

"24, 10, 5, /, +, 4, 3, *, -";

Prelucrarea şirului presupune a şti dacă un element(diferit de virgulă) este operator sau operand


Fişierul polish.h

/* Un element de tip data este operator sau operand (val) */struct data {

enum {operator, value} kind;union {

char op;int val;

} u;};typedef struct data data;typedef enum {false, true} boolean;/* Un element al stivei este o structura ce contine d si next */struct elem {

data d;struct elem *next;

};

typedef struct elem elem;/* Stiva este pointer la elem (top) si un contor*/struct stack {

int cnt; /* un contor al elementelor */elem *top; /* pointer la elementul din top */

};


Fişierul polish.h

boolean empty(const stack *stk); // este stiva stk vida?boolean full(const stack *stk); // este stiva stk plina?void initialize(stack *stk); // initializeaza stiva stkdata pop(stack *stk); // popvoid push(data d, stack *stk); // pushdata top(stack *stk); // top

// pune str in stiva stkvoid fill(stack *stk, const char *str);

// tipareste un element al tipului datavoid prn_data(data *dp);// tipareste continutul stivei stkvoid prn_stack(stack *stk);// evalueaza expresia poloneza din stiva polishint evaluate(stack *polish);


Fişierul stack.c

/* adaugarea datei d in stiva */void push(data d, stack *stk){

elem *p;p = malloc(sizeof(elem));p -> d = d;p -> next = stk -> top;stk -> top = p;stk -> cnt++;

}/* eliminarea unei datei din stiva stk */data pop(stack *stk){

data d;elem *p;

d = stk -> top -> d;p = stk -> top;stk -> top = stk -> top -> next;stk -> cnt--;free(p);return d;

}


Fişierul fill.c

#include "polish.h"/* In stiva stk se pune expresia memorata in str */void fill(stack *stk, const char *str){

const char *p = str;char c1, c2;boolean b1, b2;data d;stack tmp;

initialize(stk);initialize(&tmp);/*// Se proceseaza str si se pun datele in stiva tmp.*/while (*p != '\0') {

while (isspace(*p) || *p == ',') ++p;b1 = (boolean) ((c1 = *p) == '+' || c1 == '-' || c1 == '*' || c1 == '/' );b2 = (boolean) ((c2 = *(p + 1)) == ',' || c2 == '\0');


Fişierul fill.c

if (b1 && b2) {d.kind = operator;d.u.op = c1;

}else {

d.kind = value;assert(sscanf(p, "%d", &d.u.val) == 1);

}if (!full(&tmp))

push(d, &tmp); /* push data on tmp */while (*p != ',' && *p != '\0') ++p;

}/*// Se extrag (pop) datele din tmp si se pun in stk.*/while (!empty(&tmp)) {

d = pop(&tmp); /* pop data from tmp */if (!full(stk))

push(d, stk); /* push data on stk */}

}


Demo


Operaţii bit cu bit

Se aplică expresiilor întregiComplement ~ b = ~a;Conjuncţie & c = a & b;Disjuncţie | c = a | b;Sau exclusiv ^ c = a ^ b;Deplasare stânga <<

b = a << 5; x <<= 3; Deplasare dreapta >>

b = a >> 5; x >>= 3; Mască: constantă ce se utilizează pentru a extrage biţii convenabili: 1, 255=28-1


Operatorii bit cu bit - precedenţa

~ are aceeasi precedenţă cu !, asociativitate dreapta

<< şi >> după +, - şi înainte de <, <=, >, >=

&, ^, | în această ordine după == şi !=, înainte de &&


Precedenţa operatorilor

stânga|

stânga^

stânga&

stânga<< >>

stânga, (operatorul virgula)

dreapta= += -= *= /= %= >>= <<= &= ^= |=

dreapta?:

stânga||

stânga&&

stânga== !=

stânga< <= > >=

stânga+ -

stânga* / %

dreapta ++ -- (prefix) ! ~ & (adresa)* (dereferentiere ) + - (unari) sizeof(tip)

stânga () [] . -> ++ -- (postfix)

ASOCIERE OPERATORI


Operaţii bit cu bit – Exemplul 1#include <stdio.h>#include <limits.h>void print_bit_cu_bit(int x, const char* s){int i;int n = sizeof(int)*CHAR_BIT; int mask = 1 << (n-1);printf("%s", s);for (i=1; i <= n; i++) {putchar(((x & mask) == 0)? '0' : '1');x <<= 1;if (i%CHAR_BIT == 0 && i<n)putchar(' ');

}printf("\n");

}


Operaţii bit cu bit – Exemplul 1

void main(int x){int a = 0xA5b73, b = 0Xb0c8722;int c = ~a, d = a&b, e = a|b, f =a^b;print_bit_cu_bit(a, " a = ");print_bit_cu_bit(b, " b = ");print_bit_cu_bit(c, " ~a = ");print_bit_cu_bit(d, "a&b = ");print_bit_cu_bit(e, "a|b = ");print_bit_cu_bit(f, "a^b = ");print_bit_cu_bit(a<<3, "a<<3= ");print_bit_cu_bit(b>>6, "b>>6= ");

}


Operaţii bit cu bit – Exemplul 1

/*a = 00000000 00001010 01011011 01110011b = 00001011 00001100 10000111 00100010

~a = 11111111 11110101 10100100 10001100a&b = 00000000 00001000 00000011 00100010a|b = 00001011 00001110 11011111 01110011a^b = 00001011 00000110 11011100 01010001a<<3= 00000000 01010010 11011011 10011000b>>6= 00000000 00101100 00110010 00011100*/


Exemplul 2 - Împachetare

unsgn pack(unsgn an, unsgn ln, unsgn zi, unsgn *id)

{*id = an;*id = (*id << 4) | ln;*id = (*id << 5) | zi;return *id;

}


Exemplul 2 - Despachetare

void unpack(unsgn *an, unsgn *ln, unsgn *zi, unsgn id){/**an = (id & (127 << 9)) >> 9;*ln = (id & (15 << 5)) >> 5;*zi = id & 31;*/ *zi = id & 31; id >>= 5; *ln = id & 15;id >>= 4; *an = id;

}


Câmpuri de biţi în structuri

O declaratie, intr-o structura, de forma:

tip var:n; tip ∈ {int, unsigned}

stabileste reprezentarea lui var pe n biti:

typedef struct {unsigned oct0: 8, oct1: 8, oct2: 8, oct3: 8;

} cuv_oct; /* un cuvant = 4 octeti */typedef struct {unsigned b0 : 1, b1 : 1, ..., b31 : 1;

} cuv_bit; /* un cuvant = 32 biti */typedef union {unsigned i;cuv_oct oct;cuv_bit bit;

}


Câmpuri de biţi

Mărimea cămpului de biţi nu trebuie sa depăşeascănumărul de biţi într-un cuvânt (32)Câmpurile de biţi se declară ca membri consecutivi într-o structură; compilatorul îi împachetează într-un număr minim de cuvinteNu este posibilă declararea de tablouri de câmpuri de biţiNu se poate folosi operatorul adresă & pentru câmpuri de biţiSe pot folosi câmpuri de biţi, fără nume, pentru aliniere:

struct small_int{unsigned i1 : 7, i2 : 7, i3 :7,

:11, // aliniere la cuv urmatori4 : 7, i5 : 7, i6: 7;

};struct abc{

unsigned a : 1, :0, b : 1, :0, c : 1;}


Aplicaţie – operaţii cu mulţimi//Multimile reprezentate ca biti

#include <stdio.h>

typedef struct word {unsigned w0:1, w1:1, w2:1, w3:1, w4:1, w5:1, w6:1, w7:1,

w8:1, w9:1,w10:1,w11:1, w12:1, w13:1, w14:1, w15:1,w16:1,w17:1,w18:1,w19:1, w20:1, w21:1, w22:1, w23:1,w24:1,w25:1,w26:1,w27:1, w28:1, w29:1, w30:1, w31:1;

}word;

typedef union set {word m;unsigned u;

}set;


Aplicaţie – operaţii cu mulţimi

int main(){set x, y;

x.u = 0x0f100f10;printf("elementul 9 din x = %s\n" ,

((x.m.w9)? "true" : "false"));y.u = 0x01a1a0a1;printf("elementul 9 din y = %s\n" ,

((y.m.w9)? "true" : "false"));x.u |= y.u; /* reuniune de multimi */printf("elementul 9 din x reunit y = %s" ,

((x.m.w9)? "true" : "false"));return 0;

}

curs 10 - profs.info.uaic.rodlucanu/cursuri/ap/resurse/curs10.pdf · studiu de caz: evaluarea...

Documents