curs 10 - profs.info.uaic.rodlucanu/cursuri/ap/resurse/curs10.pdf · studiu de caz: evaluarea...
Post on 05-Feb-2018
226 Views
Preview:
TRANSCRIPT
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
Algoritmi si Programare 2005 - 2006 2
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
Algoritmi si Programare 2005 - 2006 3
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
Algoritmi si Programare 2005 - 2006 4
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
Algoritmi si Programare 2005 - 2006 5
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 */
}
Algoritmi si Programare 2005 - 2006 6
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
Algoritmi si Programare 2005 - 2006 7
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
Algoritmi si Programare 2005 - 2006 8
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);
Algoritmi si Programare 2005 - 2006 9
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);
}
Algoritmi si Programare 2005 - 2006 10
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ţă
Algoritmi si Programare 2005 - 2006 11
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.*/
Algoritmi si Programare 2005 - 2006 12
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.
Algoritmi si Programare 2005 - 2006 13
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 */
Algoritmi si Programare 2005 - 2006 14
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 */
Algoritmi si Programare 2005 - 2006 15
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.
Algoritmi si Programare 2005 - 2006 16
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
Algoritmi si Programare 2005 - 2006 17
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))
Algoritmi si Programare 2005 - 2006 18
#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*/
Algoritmi si Programare 2005 - 2006 19
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);
Algoritmi si Programare 2005 - 2006 20
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)
Algoritmi si Programare 2005 - 2006 21
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 */
Algoritmi si Programare 2005 - 2006 22
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*/
Algoritmi si Programare 2005 - 2006 23
Directive pentru compilarecondiţionată
#if expr_const_intreagă
#else
#elif /* pentru else if */
#ifdef identificator
#ifndef identificator
#undef identificator
#endif
Algoritmi si Programare 2005 - 2006 24
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
Algoritmi si Programare 2005 - 2006 25
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
Algoritmi si Programare 2005 - 2006 26
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 */
};
Algoritmi si Programare 2005 - 2006 27
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);
Algoritmi si Programare 2005 - 2006 28
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;
}
Algoritmi si Programare 2005 - 2006 29
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;
}
Algoritmi si Programare 2005 - 2006 30
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');
Algoritmi si Programare 2005 - 2006 31
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 */}
}
Algoritmi si Programare 2005 - 2006 32
Demo
Algoritmi si Programare 2005 - 2006 33
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
Algoritmi si Programare 2005 - 2006 34
Operatorii bit cu bit - precedenţa
~ are aceeasi precedenţă cu !, asociativitate dreapta
<< şi >> după +, - şi înainte de <, <=, >, >=
&, ^, | în această ordine după == şi !=, înainte de &&
Algoritmi si Programare 2005 - 2006 35
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
Algoritmi si Programare 2005 - 2006 36
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");
}
Algoritmi si Programare 2005 - 2006 37
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= ");
}
Algoritmi si Programare 2005 - 2006 38
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*/
Algoritmi si Programare 2005 - 2006 39
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;
}
Algoritmi si Programare 2005 - 2006 40
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;
}
Algoritmi si Programare 2005 - 2006 41
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;
}
Algoritmi si Programare 2005 - 2006 42
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;}
Algoritmi si Programare 2005 - 2006 43
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;
Algoritmi si Programare 2005 - 2006 44
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;
}
top related