1
Universitatea “Ştefan cel Mare” Suceava Facultatea de Inginerie Electrică şi Ştiinţa Calculatoarelor
ÎNDRUMAR DE LABORATOR
Programarea calculatoarelor şi limbaje de programare 2
prof. dr. ing. Ştefan-Gheorghe PENTIUC
asistent. drd. ing. Ovidiu-Andrei SCHIPOR
asistent. drd. ing. Felicia-Florentina GÎZĂ-BELCIUG
ş.l. dr. ing. Marius CERLINCĂ
Suceava, 2010
2
3
Cuprins 1. FIŞIERE TEXT 5
2. FIŞIERE BINARE 9
3. POINTERI LA FUNCŢII 13
4. STRUCTURI 15
5. CÂMPURI DE BIŢI 19
6. LISTE LINIARE 31
7. LISTE SIMPLU ÎNLĂNŢUITE 37
8. STIVA 43
9. COADA 47
10. MULŢIMI 51
11. ARBORI 57
12. METODA GREEDY 61
13. BACKTRACKING RECURSIV 65
14. BACKTRACKING ITERATIV 69
BIBLIOGRAFIE 71
4
5
1. Fişiere text 1.Obiective
� Utilizarea principalelor funcţii specifice fişierelor text; � Implementarea unei aplicaţii de salvare/citire a datelor matriceale în/din fişierele text; � Generarea fişierelor html şi a fişierelor istoric în cadrul aplicaţiei.
2.Aspecte teoretice Memoria internă este limitată atât din punctul de vedere al persistenţei datelor cât şi din
punctul de vedere al capacităţii. Posibilitatea de a stoca şi accesa cantităţi mari de date este oferită de dispozitivele de stocare externe (hard-disk, DVD, flash). Din punct de vedere logic, aceste dispozitive organizează datele sub forma fişierelor. Transferul datelor din memoria internă într-un fişier poartă denumirea de salvarea datelor. Transferul invers presupune citirea din fişier.
Funcţii noi
deschidere fopen
închidere fclose
caracter şir de caractere date formatate scriere fputc fgets fscanf
citire fgetc fputs fprintf
3.Exemple Exemplul 1 – salvarea/citirea unui vector în/din fişier text
Un program minimal ce operează cu şiruri de numere întregi trebuie să implementeze funcţiile de citire de la tastatură şi afişare pe ecran. Utilizând fişiere se pot implementa încă două funcţii, una care să realizeze salvarea unui vector într-un fişier iar alta citirea unui vector din fişier.
Trebuie respectat un anumit format al fişierului. Convenim ca să scriem pe prima linie a fişierului numărul de elemente ale şirului iar pe linia următoare elementele, separate prin spaţiu. De exemplu, după salvarea vectorului {2, -3, 0, 8}, fişierul trebuie să conţină:
4 2 -3 0 8
6
Funcţia de salvare a vectorului are ca argumente numărul de elemente - n, vectorul - v şi numele fişierului în care se doreşte salvarea vectorului - numeFisier. Această funcţie returnează valoarea 1 (unu) dacă nu au apărut erori la deschiderea fişierului şi 0 (zero) în caz contrar.
Funcţia de citire din fişier a vectorului are ca argumente un pointer la numărul de elemente - n, vectorul - v şi numele fişierului din care se doreşte citirea vectorului - numeFisier. Returnează valoarea 1 (unu) dacă nu au apărut erori la deschiderea fişierului şi 0 (zero) în caz contrar.
Exemplul 2 – copierea conţinutului unui fişier text în altul În cadrul acestui exemplu se va prezenta o funcţie care copie conţinutul unui fişier în altul.
Funcţia primeşte ca argument numele fişierelor sursă şi destinaţie (în această ordine). Returnează valoarea 0 (zero) dacă a apărut eroare la deschiderea fişierelor şi 1 (unu) în caz contrar.
int salvareVector(int n, int v[NMAX], char* numeFisier){ FILE *pf; //pf este o variabila de tip pointer catre un fisier int i;
//se deschide fisierul in mod scriere (write)
pf = fopen (numeFisier, "wt");
//daca fisierul nu poate fi deschis, se returneaza fals logic
if (pf == NULL) return 0;
//daca pf este un pointer valid atunci se pot scrie datele fprintf (pf, "%d\n",n); //se scrie numarul de elemente for (i=0;i<n;i++) //se scriu succesiv elementele fprintf (pf, "%d ",v[i]); fclose (pf); //inchidere fisier return 1; //salvarea datelor s-a incheiat cu succes
}
int copiereFisier1 (char* numeSursa, char* numeDest){ FILE *pfSursa, *pfDest; // pointeri la cele doua fisiere
char c; // variabila de "manevra" if ((pfSursa=fopen(numeSursa, "rt"))==NULL) //deschidere sursa return 0;
if ((pfDest=fopen(numeDest, "wt"))==NULL) //deschidere destinatie return 0;
/*se citesc caractere din fisierul sursa si se scriu in fisierul
destinatie pana cand functia fgetc() returneaza EOF*/
while ((c=fgetc(pfSursa))!=EOF)
fputc(c,pfDest); fclose (pfSursa); fclose (pfDest); return 1; }
int citireVectorFisier(int* pn, int v[NMAX], char* numeFisier){ FILE *pf; int i;
//se deschide fisierul in mod citire (read)
pf = fopen (numeFisier, "rt"); if (pf == NULL) return 0; fscanf (pf, "%d",pn); //se citeste numarul de elemente for (i=0;i<*pn;i++) //se citesc succesiv elementele
fscanf (pf, "%d",&v[i]); fclose (pf); //inchidere fisier return 1; //citirea datelor din fisier s-a incheiat cu succes }
7
Varianta prezentată realizează copierea caracter cu caracter. În cazul fişierelor text poate fi mai performantă o copiere linie cu linie. În continuare este prezentată secvenţa de copiere pentru acest mod de implementare. Pentru dimensiunea tabloului în care se memorează o linie s-a utilizat constanta MAX_LINIE. Cu alte cuvinte, presupunem că numărul maxim de caractere de pe o linie din fişierul sursă este MAX_LINIE – 1 (la sfârşitul şirului trebuie adăugat şi caracterul ‘\0’). Exemplul 3 – testarea existenţei unui fişier
Funcţia care testează existenţa unui fişier are ca argument numele acestuia. Se bazează pe faptul că fopen() returnează NULL dacă se încearcă deschiderea în citire a unui fişier inexistent.
4. Temă de realizat în timpul laboratorului Exerciţiul 1 – matrice şi fişiere text
Să se realizeze o aplicaţie care să afişeze un meniu cu următoarele opţiuni:
Referitor la formatul datelor în fişier, pe prima linie se vor scrie numărul de linii şi numărul de coloane separate prin spaţiu. Apoi se vor scrie pe linii succesive liniile matricei (elementele separate prin spaţiu). Conţinutul fişierului după salvarea matricei {{4,9,2},{0,6,1}} va fi: Exerciţiul 2 – generare fişier backup
Să se adauge o opțiune care să permită copierea unui fișier în altul (B – creare fisier backup pentru un fisier creat la optiunea S).
2 3
4 9 2
0 6 1
int copiereFisier2 (char* numeSursa, char* numeDest){ FILE *pfSursa, *pfDest; char buf[MAX_LINIE]; // variabila de manevra if ((pfSursa=fopen(numeSursa, "rt"))==NULL)
return 0; if ((pfDest=fopen(numeDest, "wt"))==NULL) return 0;
//cand ajunge la sfarsitul fisierului fgets() returneaza NULL
while (fgets(buf,MAX_LINIE-1,pfSursa)!=NULL)
fputs(buf,pfDest); fcloseall(); // se inchid toate fisierele deschise return 1; }
int existaFisier (char* numeFisier){
FILE *pf;
//daca fisierul poate fi deschis pentru scriere atunci el exista
return (pf=fopen (numeFisier, "r"))==NULL ? 0 : (fclose(pf),1); }
C – citire matrice de la tastatura A – afisare matrice pe ecran S – salvare matrice in fisier R – citire matrice din fisier
8
Exerciţiul 3 – generare fişiere HTML Din ce în ce mai multe aplicaţii îşi prezintă datele în format html. Fişierele html sunt în acest
caz generate pe baza unor date necunoscute iniţial. Ele se mai numesc fişiere generate ”on the fly” (din zbor). Aplicaţia anterioară poate fi extinsă în acest sens prin adăugarea unei opţiuni (H – generare html). Accesarea ei trebuie să determine generarea unui fişier html care, deschis cu ajutorul unui browser, să afişeze matricea sub forma unui tabel ca în exemplul următor:
<html> <head><title>Matrice</title></head>
<body>Matrice: 2 linii, 3 coloane.<br> <table border='1'> <tr><td>4</td><td>9</td><td>2</td></tr> <tr><td>0</td><td>6</td><td>1</td></tr> </table></body></html>
Matrice: 2 linii, 3 coloane
4 9 2
0 6 1
9
2. Fişiere binare 1. Obiective
� Identificarea diferenţelor între formatele text şi binar ale datelor; � Însuşirea lucrului cu principalele funcţii specifice fişierelor binare; � Extinderea unei aplicaţii de salvare/citire a datelor în/din fişiere binare.
2. Aspecte teoretice În cadrul laboratorului anterior, datele au fost salvate în format text, rezultând fişiere uşor de
citit/modificat cu ajutorul programelor editoare de text (Notepad). În memoria internă, datele au o altă reprezentare – formatul binar. Aşa de exemplu, în limbajul C, o variabilă de tip întreg va ocupa în memorie întotdeauna 2 octeţi, indiferent de valoarea ei. Acest lucru nu este valabil după conversia variabilei în formatul text când, un număr întreg poate ocupa de la 1 octet (de exemplu numărul 7) şi până la 6 octeţi (de exemplu numărul –12539). Pentru a evita conversia consumatoare de timp între cele două formate este necesară scrierea datelor din memorie în fişiere direct în formatul binar.
Funcţii noi
scriere citire poziţionare aflare poziţie fwrite fread fseek ftell
Tabelul următor ilustrează legătura dintre formatul text (linia valoare) şi formatul binar (liniile baza 2 şi baza 10) pentru variabile de diferite tipuri, adăugate succesiv într-un fişier binar. Linia ASCII se referă la conversia valorii numerice din fiecare octet la tipul caracter pe baza tabelei ASCII (aceste caractere se afişează dacă fişierul binar este deschis cu un editor de text obişnuit).
variabila char c1 char c2 int i1 int i2 int i3
valoare 'A' '0' 49 320 -49
nr octet 1 2 3 4 5 6 7 8
baza 2 01000001 00110000 00110001 00000000 01000000 00000001 11001111 11111111
baza 10 65 48 49 0 64 1 207 255
ASCII A 0 1 @
variabila long l char s[4]
valoare 6513249 "ana"
nr octet 9 10 11 12 13 14 15 16
baza 2 01100001 01100010 01100011 00000000 01100001 01101110 01100001 00000000
baza 10 97 98 99 0 97 110 97 0
ASCII a b c a n a
variabila int v[4]
valoare {65,66,51,52}
nr octet 17 18 19 20 21 22 23 24
baza 2 01000001 00000000 01000010 00000000 00110011 00000000 00110100 00000000
baza 10 65 0 66 0 51 0 52 0
ASCII A B 3 4
10
3. Exemple Exemplul 1 – program de test fişiere binare
Programul următor oferă posibilitatea citirii succesive de la tastatura a unor variabile şi adaugarii acestora într-un fişier binar. La fiecare iteraţie utilizatorul are posibilitatea să precizeze tipul şi valoarea variabilei. După fiecare adaugare în fişier, programul afişează conţinutul acestuia la nivel de octet, indicând numărul octetului si valoarea sa in formatele decimal şi ASCII. CONV.C
#include <stdio.h> #include <conio.h>
#include <string.h>
// numele fisierului in care se vor scrie datele
#define NUME_FISIER "fisier.dat"
// tipurile de date se considera:
// 1-char, 2-int
// 0-rezervat pentru terminarea programului
// vector de intregi cu numarul de octeti ale tipurilor de date
int lung[] ={0,sizeof(char),sizeof(int)};
// vector de siruri de caractere cu specificatori de format
char *format[] = {"","%c","%d"}; int citesteTipVariabila(); void citesteVariabila(int tip, char* var);
int adaugaVariabilaInFisier(char* numeFisier, int tip, char* zona); int afiseazaFisierBinar(char* numeFisier); char* convertesteInBaza2(char c);
//-------------------------------------------
// functia principala a programului
//-------------------------------------------
void main (){
// pentru memorarea unei variabile se aloca 2 octeti
char var[sizeof(int)];
// tipul variabilei (1-char, 2-int)
int tip;
// ciclul se repeta cat timp tip este diferit de 0
while(tip = citesteTipVariabila()){
// se citeste o variabila de la tastatura
citesteVariabila (tip,var);
// se adauga variabila in fisierul binar
adaugaVariabilaInFisier (NUME_FISIER,tip,var);
// se afiseaza fisierul binar
afiseazaFisierBinar (NUME_FISIER);
} }
//-------------------------------------------
// citeste si returneaza tipul unei variabile
//-------------------------------------------
int citesteTipVariabila(){ int tip;
// citeste un tip pana cand se incadreaza in intervalul [0,2]
do{
11
clrscr(); printf ("\nDa tipul (1-char, 2-int, 0-termina):"); scanf("%d",&tip);
}while (tip<0 || tip>2); return tip; }
//-----------------------------------------------------------------
// citeste o variabila de un anumit tip in zona primita ca argument
//-----------------------------------------------------------------
void citesteVariabila (int tip, char* var){ printf ("\nDa valoarea variabilei:"); flushall();
// se utilizeaza un format dependent de valoarea lui tip
// var este adresa unei zone in care se memoreaza variabila
scanf (format[tip],var); }
//----------------------------------------------------------------
// adauga in fisier valoarea de tipul tip din zona de memorie var
//----------------------------------------------------------------
int adaugaVariabilaInFisier (char* numeFisier, int tip, char* var){
// fisierul este deschis in modul append binar
FILE* pf = fopen(numeFisier,"ab"); if (!pf)
return 0;
// se scriu 1 x lung[tip] octeti
// de la adresa var in fisierul pf
fwrite (var,lung[tip],1,pf); fclose (pf);
return 1; }
//------------------------------------------------------------------
// afiseaza continutul fisierului in binar, decimal si ASCII
//------------------------------------------------------------------
int afiseazaFisierBinar (char* numeFisier){ char octet; int i=0; FILE *pf = fopen(numeFisier,"rb");
if (!pf) return 0;
// se afiseaza header-ul tabelului
printf ("nr. octet | decimal | ASCII "); printf ("\n---------------------------");
// se citeste cate un octet din fisier
// pana cand se ajunge la sfarsitul fisierului
while (fread (&octet,1,1,pf)==1){
// se afiseaza aliniat pe coloane informatiile
printf ("\n%9d | %7d | %5c "
,i++,octet,octet); } fclose (pf); printf ("\nApasa orice tasta pentru a continua..."); getch();
return 1; }
12
Exemplul 2 – salvarea/citirea unui vector în/din fişier binar Scrierea în fişier se realizează după următorul format: întâi este scris numărul de elemente n
(de tip int, va ocupa sizeof(int) bytes); în continuare este scris fiecare element din vectorul v. int salveazaVectorBinar(int n, int v[NMAX], char* numeFisier){ FILE* fp = fopen(numeFisier, "wb");
if (fp == NULL) return 0; // eroare deschidere
// scrie in fisierul fp numarul de elemente ale vectorului
// adica 1 x sizeof(int) octeti de la adresa &n
if (fwrite(&n, sizeof(int), 1, fp) == 1)
// scrie in fisierul fp elementele vectorului
// adica n x sizeof(int) octeti de la adresa v
if (fwrite(v, sizeof(int), n, fp) != n){
// daca datele au fost scrise cu succes
fclose(fp);
return 1; } fclose(fp); // au aparut probleme la scrierea datelor return 1; }
Funcţia de citire a vectorului din fișier va prelua mai întâi numărul de elemente și apoi va citi
elementele vectorului. int citesteVectorFisierBinar(int* pn, int v[NMAX], char* numeFisier){ FILE* fp = fopen(numeFisier, "rb");
if (fp == NULL) return 0; // eroare deschidere
// se citeste numarul de elemente
if (fread(pn, sizeof(int), 1, fp) == 1)
// se citesc elementele
if (fread(v, sizeof(int), *pn, fp) == *pn){
// daca datele au fost citite cu succes
fclose(fp); return 1;
} fclose(fp); // au aparut probleme la citirea datelor return 0; }
4. Temă de realizat în timpul laboratorului
Exerciţiul 1 Să se modifice aplicaţia prezentată în exemplul 1 pentru a permite adăugarea în fişier şi a
variabilelor de tipul long int. De asemenea să se afişeze pe ecran şi valorile în bazele 8 respectiv 16 ale octeţilor din fişier. Indicati cea mai simplă modalitate de a goli fişierul în care se salveză datele de fiecare dată când scrieţi în el câte o variabilă. Exerciţiul 2
Să se extindă aplicaţia realizată în laboratorul cu fişiere text prin adăugarea opţiunilor: M – salvare matrice in fisier binar N – citire matrice din fisier binar
13
3. Pointeri la funcţii 1. Obiective
� familiarizarea cu tablouri de pointeri la funcţii � utilizarea modului grafic
2. Aspecte teoretice Declararea unui parametru de tip pointer la funcţie se face astfel :
Acest pointer nu poate conţine decât adresa unei funcţii ce are un prototip identic cu cel al pointerului:
cu observaţia că numele funcţiei reprezintă adresa funcţiei. Apelul unei funcţii prin intermediul unui pointer la funcţie se face conform secvenţei de mai jos:
3. Exemplu Se consideră o aplicaţie care afişează 10 valori ale funcţiilor cosinus, sinus şi x+x/2 pe intervalele [-1,1] şi pentru funcţia radical pe intervalul [0.1,3.2].
#include <math.h>
#include <stdio.h>
#include <conio.h>
typedef double (*pFunctie)( double v );
void tabel( char*, pFunctie, double, double, int);
double functie( double );
void main( void )
p_functie( 23, 45.6 ) ;
int functie( int a, float b )
{
//corpul functiei
}
void main( void )
{
p_functie = functie;
}
int (*p_functie)( int , float ) ;
14
4. Temă de realizat în timpul laboratorului Observaţie. Odată cu afişarea graficului, într-un fişier text al cărui nume este dat in linia de comanda să se salveze valorile funcţiei alese in diferite puncte sub forma: x sin(x)
-1 -0.0174
-0.9 -0.0157
-0.8 -0.0139
. . . . .
x cos(x)
. . . . .
Ordinea funcţiilor trebuie sa fie cea aleasă corespunzător meniului.
void main( void )
{
clrscr();
tabel( "cos", cos, -1, 1, 10 );
tabel( "sin", sin, -1, 1, 10 );
tabel( "radical", sqrt, 0.1, 3.2, 10 );
tabel( "functie", functie, -1, 1, 10 );
}
void tabel( char *nume, pFunctie functie, double a, double b, int N)
{
printf("\n\n%s - [%.1lf, %.1lf] in %d pasi", nume, a, b, N );
for( double i=a, suma=0; i <= b; i += (b-a)/N )
printf("\n%5.1lf\t|%5.1lf", i, functie( i ));
}
double functie( double x )
{
return x + x/2;
}
Q - Citirea intervalului de reprezentare a funcŃiei
N - Citirea numărului de paşi S - Afişează grafic funcŃia sinus
C - Afişează grafic funcŃia cosinus
R - Afişează grafic funcŃia radical
P - Afişează grafic o funcŃie polinomiala a cărui grad
si coeficienŃi sunt citiŃi de la tastatura -
X - Ieşire
15
4. Structuri
1.Obiective � Insuşirea lucrului cu tipurile de date structurate; � Consolidarea cunoştinţelor privind fişierele binare; � Implementarea unei aplicaţii minimale de gestiune a stocurilor;
2.Aspecte teoretice În aplicaţiile de până acum s-au utilizat doar tipuri de date simple (char, int, float, etc…). Cel
mult aceste tipuri au fost extinse prin utilizarea operatorilor [] obţinându-se astfel tablouri de date de acelaşi tip (omogene).
De cele mai multe ori, realităţile modelate prin datele programului sunt complexe nereducându-se la un şir omogen de date. Pentru asemenea date trebuie create tipuri noi (compuse) specifice aplicaţiei. În continuare este prezentată o definiţie de tip de dată care să modeleze conceptul de calculator:
Pentru a defini în program o variabilă în care să se poată memora datele de identificare ale unui calculator trebuie să se utilizeze noul tip de dată creat şi anume struct calculator.
În acest moment se alocă memorie suficientă pentru a memora toate câmpurile specificate în definiţia de structură. Pentru a putea utiliza variabila unCalculator este necesară o modalitate de acces la membrii din care este formată. Accesul la membrii se realizează cu ajutorul operatorului . (punct).
În acest context, unCalculator.numeProcesor se comportă ca un şir de caractere obişnuit şi similar, unCalculator.frecventa se comportă ca un număr întreg. Avantajele tipurilor de date structurate sunt:
� crearea şi manipularea cu uşurinţă a tipurilor complexe de date specifice aplicaţiei; � copierea simplificată, printr-o singură atribuire a tuturor câmpurilor; � transmiterea ca parametrii la funcţii; � scrierea/citirea în bloc în/din fişiere binare.
struct calculator{ char numeProcesor[20];
float frecventa; //exprimata in GHz
int capacitateRAM; //exprimata in MB
int capacitateHDD; //exprimata in GB
char numeProducator[64];
float pret;
};
struct calculator unCalculator;
16
3.Exemple
Considerăm structura: Exemplul 1 – două variante de funcţii pentru citirea unui student
Pentru citirea unui student se poate utiliza fie o funcţie care returnează o variabilă de tip STUDENT fie o funcţie care primeşte adresa unei variabile de tip STUDENT.
Dacă în prima variantă se transferă prin stivă un număr de sizeof(STUDENT) octeţi (în acest caz 108), în a doua variantă se transferă doar octeţii necesari memorării unei adrese. Deşi prima variantă este mai intuitivă a doua variantă este mai eficientă. Exemplul 2 – funcţie pentru adăugarea într-un fişier binar
Se doreşte realizarea unei funcţii care să adauge o înregistrare (un student) într-un fişier. Numele fişierului se va primi ca argument. Funcţia va returna valoarea 0 (zero) dacă au apărut erori I/O şi 1 (unu) în caz contrar.
Transmiterea studentului în funcţie poate fi realizată fie prin valoare (argumentul este de tip STUDENT) fie prin referinţă (argumentul este de tip STUDENT*). Se preferă a doua variantă deoarece numărul de octeţi transferaţi prin stivă este considerabil mai mic.
struct student{
long nrMatricol;
char nume[100];
float media;
};
typedef struct student STUDENT; // typedef creaza sinonimul STUDENT
// pentru denumirea struct student
STUDENT citireStudent (){
STUDENT s;
printf (“\nIntroduceti pe rand nr. matricol, numele si media”);
scanf (“%ld”,&s.nrMatricol);
gets (s.nume);
scanf (“%f”,&s.media); return s; }
void citireStudent (STUDENT *p){
printf (“\nIntroduceti pe rand nr. matricol, numele si media”);
scanf (“%ld”,&p->nrMatricol);
gets (p->nume);
scanf (“%f”,&p->media); }
int adaugareStudent (char *numeFisier, STUDENT *p){
if ((f=fopen(numeFisier, “a”))==NULL) return 0;
fwrite (p,sizeof(STUDENT),1,f)
return 1;
}
17
4. Temă de realizat în timpul laboratorului Exerciţiul 1
Se va realiza o aplicaţie tip meniu care să permită gestionarea unei baze de date cu produsele dintr-o magazie. Un produs va fi reprezentat prin 3 informaţii: cod, nume, unitate (ex: 315,”mere”,”kg”).
Opţiunile necesare pentru a fi implementate sunt: Observaţii:
� fişierul de lucru (al cărui nume este preluat din linia de comandă) va fi accesat în mod binar; � dacă utilizatorul încearcă să adauge un produs cu un cod care se mai găseşte deja în fişierul
de lucru, va fi interogat dacă doreşte suprascrierea sau nu a înregistrării respective; În continuare este prezentat listing-ul fişierului header al aplicaţiei:
A – adaugare un produs in fisierul de lucru V – vizualizarea produselor din fisierul de lucru
U – cautarea unui produs dupa nume
I – informatii despre autor
X – iesire din program
#ifndef _PRODUSE_H_ // protectie împotriva includerii multiple
#define _PRODUSE_H_ // a acestui fişier header
typedef char LOGIC;
#define ADEVARAT 1
#define FALS 0
typedef struct produs{. . .}PRODUS; // utilizare rapida a lui typedef
void citireProdus (PRODUS *p); /* încarcă produsul indicat de
pointerul p cu informatiile specifice (cod, nume, unitate) */
LOGIC adaugareProdus (char *numeFisier, PRODUS *p);/*adauga in
fisierul cu numele numeFisier produsul indicat de pointerul p; daca a
aparut o eroare I/O returneaza FALS altfel returneaza ADEVARAT*/
LOGIC vizualizareProduse (char *numeFisier);/*afiseaza pe rand toate
inregistrarile din fisierul cu numele numeFisier; daca a aparut o
eroare I/O returneaza FALS altfel returneaza ADEVARAT*/
LOGIC gasitProdus (char *numeFisier, int codProdus,LOGIC *errFisier);
/*cauta produsul cu codul codProdus in fisierul cu numele numeFisier;
daca produsul este gasit returneaza ADEVARAT altfel returneaza FALS;
variabila pointata de errFisier va avea valoarea FALS daca a aparut o
eroare IO sau ADEVARAT in caz contrar */
#endif
18
Exerciţiul 2 Aplicaţia anterioară poate fi extinsă prin urmărirea fluxului produselor. În acest scop se vor
utiliza încă două fişiere: - intrari - memorează codul produsului intrat în magazie şi numărul de bucăţi
(ex: 315 40 -> au intrat 40 kg mere) - ieşiri - memorează codul produsului ieşit din magazie şi numarul de bucăţi
(ex: 315 10 -> s-au vând 10 kg mere) Pentru modelare înregistrările din aceste fişiere trebuie definită încă o structură:
Opţiuni adăugate la meniu:
5. Teme pentru studiu individual Exerciţiul 1 – ştergerea înregistrărilor
O aplicaţie “reală” trebuie să permit şi ştergerea anumitor înregistrări. Acest aspect va fi luat în considerare pentru dezvoltarea unei versiuni îmbunătăţite a aplicaţiei. Exerciţiul 2 – datarea intrărilor şi ieşirilor
Aplicaţia de la laborator se va extinde astfel încât să permită păstrarea coordonatelor temporale asociate înregistrărilor cu privire la intrări şi ieşiri.
typedef struct produsIO{
int cod;
int cantitate;
}PRODUS_IO,*pPRODUS_IO;
B – efectuează o intrare
C – afişează intrările
D – efectuează o ieşire
E – afişează ieşirile S – afişeaza stocurile din magazie
19
5. Câmpuri de biţi 1. Obiective
� însuşirea lucrului cu câmpuri de biţi si uniuni � programarea cu tipuri de date complexe definite de utilizator � dezvoltarea aptitudinilor de programare modulara si structurata (utilizarea de segmente
de date si cod, clase de memorare, fişier header, proiect);
2. Aspecte teoretice Sa se elaboreze un program pentru evidenta tuturor studenţilor si doctoranzilor Facultatii de
Inginerie Electrica, înscrişi la toate formele de invatamant aprobate de Minister: ingineri, masterat, studii aprofundate si doctorat. Persoanele care urmează studiile la aceste categorii vor fi denumite in continuare prin termenul 'inscrisi'. Programul va afişa următorul meniu:
F - precizare forma de invatamant R - citire date din fisier C - citire date de la tastatura despre inscrisi S - salvare date in fisier
A - afisare inscrisi M - modifica datele despre un inscris T - terminare program
Precizarea formei de invatamant va fi ceruta initial de program, apoi va fi afisata in meniu
pentru a permite utilizatorului sa lucreze si cu alta forma de invatamant. Toate celelalte optiuni se refera la inscrisii de la forma de invatamant precizata. Prin optiunea R, datele citite din fisier se vor adauga eventualelor date prezente in memorie. Optiunea C preia de la tastatura date despre inscrisii de la forma de invatamant precizata si le adauga in memorie. Optiunea S salveaza datele din memorie in fisierul indicat de utilizator. La optiunea M se afiseaza numele tuturor inscrisilor si un numar de ordine. Apoi se cere numarul de ordine al persoanei pentru care se vor modifica datele.
3.Fişiere puse la dispoziţie inscrisi.h - definire tipuri de date evidenta.c - programul principal evidenta
citdate.c - citire date despre inscrisi
afisare.c - afisare date despre inscrisi
inscrisi.c - segment de date cu inscrisi
denspec.c - denumire specializari
denspec.h - declaratii denumire specializari
citiri.c - functii de citire
citiri.h - prototipurile functiilor de citire
/* ========================================================
I N S C R I S I . H
Contine declararea tipurilor de date pentru diferitele
categorii de 'inscrisi', inclusiv tabloul buf[] de
inscis is dimensiunea sa maxima (NMAX).
(c)PSG2002
======================================================== */
#ifndef INSCRISI_H #define INSCRISI_H
20
#define NMAX 500 #define _ING 0 #define _MASTER 1
#define _DSA 2 #define _DOCTORAT 3 #define ADEVARAT 1 #define FALS (!ADEVARAT)
typedef unsigned char LOGIC,COD; typedef struct { COD spec; float medii[5];
float licenta; } STUD_ING; typedef struct { COD spec;
char fac[30]; float medii[2]; float disertatie; } MASTER;
typedef struct { COD spec; char fac[30]; float medie_an; float disertatie;
} DSA; typedef struct { COD domeniu; char fac[30];
unsigned ex1:2,ex2:2,ex3:2; // 0="A", 1="S" 2="B", 3="FB" unsigned rf1:2,rf2:2,rf3:2; // 0="A", 1="S" 2="B", 3="FB" char teza[15]; // 'foarte bine", "magna cumlaude" } DOCTORAND;
typedef union { STUD_ING stud; MASTER sm; DSA sdsa; DOCTORAND drd;
} INSCRIERE; typedef struct stcd { char nume[20]; unsigned an_admis:11; //...2047
unsigned sex:1; // 0=F, 1=M unsigned cat:3; //0 =ing, 1=cursant postuniv. 4 luni //1= DSA 2 = master, 3=doctorand unsigned an:3; INSCRIERE info;
} INSCRISI; extern INSCRISI buf[]; #endif
21
/* ========================================================
I N S C R I S I . C
Segment de date cu tabloul buf[] de 'inscrisi'
(c)PSG2002
======================================================== */
#include "inscrisi.h" INSCRISI buf[NMAX];
/* ======================================================== C I T I R I . C
Fisierul contine functii gnerale de citire a valorilor
unor variabile de tip int, double si sir de caractere.
(c)PSG2002
======================================================== */
#include <stdio.h> #include <conio.h> #include <string.h>
#include "citiri.h"
/* --------------------------------------------------------------
c i t _ t e x t
Functia realizeaza:
- afisarea mesajului de atentionare
- citirea unui sir de caractere de maxim
n_car_max caractere
- memoreaza caracterele citite la adresa dest
-------------------------------------------------------------- */
char * cit_text(char *atentionare, char *dest, int n_car_max)
{ char *dest_0=dest; printf("%s:", atentionare); flushall(); for(n_car_max --;n_car_max > 0; n_car_max --, dest ++)
if((*dest = getche())== ENTER)break; *dest = EOS; return dest_0; }
/* --------------------------------------------------------------
c i t _ d o u b l e
Citeste un real, dupa avertizarea utilizatorului
prin citirea unui mesaj de atentionare pe ecran.
Rezultatul returnat de functie este valoarea citita.
Citirea este programata pentru ca functia sa fie operationala
si pe versiunile de compilatoare C unde nu s-a implementat
si formatul real de citire a datelor
-------------------------------------------------------------- */
double cit_double(char *atentionare) {
double val; char cifre[25];
cit_text(atentionare, cifre,25);
sscanf(cifre, "%lf", &val); return val; }
22
/* -------------------------------------------------------------- c i t _ i n t
Citeste un intreg dupa afisarea prealabila a mesajului de
la adresa atentionare. Verifica daca valoarea
citita este cuprinsa in intervalul [a,b]
-------------------------------------------------------------- */
int cit_int(char *atentionare, int a, int b)
{int n; flushall(); do{ printf("%s (%d, %d)= ", atentionare, a, b); scanf("%d", &n);
} while(n<a||n>b); return n; }
/* --------------------------------------------------------------
c i t _ f l o a t
Citeste un float dupa afisarea prealabila a mesajului de
la adresa atentionare. Verifica daca valoarea
citita este cuprinsa in intervalul [a,b]
-------------------------------------------------------------- */
float cit_float(char *atentionare, float a, float b) {float x; do{ printf("%s (%f, %f)= ", atentionare, a, b); scanf("%f", &x);
} while(x<a||x>b); return x; }
/* --------------------------------------------------------------
f g e t _ s i r ( s, n, f)
Citeste un sir din fisierul f.
Are functionarea asemanatoare cu a lui fgets
Suplimentar elimina new-line de la sfirsitul
sirului.
Vezi si functia fput_sir din acest fisier sursa.
-------------------------------------------------------------- */
char *fget_sir( char *s , int n , FILE *f) { char *ret_fgets;
if( (ret_fgets= fgets(s , n , f)) != 0) { *(s + strlen(s) - 1) = '\0'; /* eliminare new-line */ } return ret_fgets; }
23
/* --------------------------------------------------------------
f p u t s i r
Scrie in fisierul f sirul de caractere s
urmat de un '\n'.
-------------------------------------------------------------- */
int fputsir(char *s,FILE *f) { fputs(s, f);
return fputc('\n', f); }
// Actualizata dupa functia din bc_Help
long unsigned LungimeFisier(FILE *fis)
{ long unsigned poz_crt, lung; poz_crt = ftell(fis); fseek(fis, 0L, SEEK_END); lung = ftell(fis);
fseek(fis, poz_crt, SEEK_SET); return lung; }
/* ======================================================== D E N S P E C . C
Fisierul contine denumirile specializarilor formelor de
invatamant si a domeniilor de doctorat, precum si durata
acestora (nr_ani[]).
(c)PSG2002
======================================================== */
#include <stdio.h>
char *spec_ing[] ={ "Calculatoare", "Automatica si informatica industriala",
"Electronica", "Electrotehnica", "Energetica", "Inginerie economica"}; char *spec_post[] = {"Informatica",
"Sisteme inteligente in controlul proceselor"}; char *domenii[] = {
"Electronica si telecomunicatii", "Inginerie electrica", "Stiinta calculatoarelor" };
int nr_ani[]={5,2,1,6};
#define NR_pCHAR(x) sizeof(x)/sizeof(char *) int nr_specializari[]= {NR_pCHAR(spec_ing), NR_pCHAR(spec_post), NR_pCHAR(spec_post), NR_pCHAR(domenii) };
char **adresa[] = { spec_ing, spec_post, spec_post, domenii};
void AfiseazaDenumiri(int forma_inv) { int i; char **den = adresa[forma_inv]; for(i=1; i<=nr_specializari[forma_inv]; i++)
printf("\n%d-%s",i, den[i-1]); }
24
/* ========================================================
E V I D E N T A . C
Programul realizeaza evidenta tuturor studentilor
si doctoranzilor Facultatii de Inginerie Electrica,
inscrisi la toate formele de invatamant aprobate:
ingineri, masterat, studii aprofundate si doctorat.
Persoanele care urmeaza studiile la aceste categorii
vor fi denumite prin termenul 'inscrisi'.
Fisierul contine functia main() si meniu().
(c)PSG2002
======================================================== */
#include <stdio.h>
#include <string.h> #include <conio.h> #include <ctype.h> #include <stdlib.h> #include "inscrisi.h"
#include "citiri.h" #define INFINIT 1 char meniu(); extern int CitireDateTastatura(int forma_inv, int nr_inscrisi);
extern void AfisareInscrisi(int nr_inscrisi); void main() { char *txt_forma_inv="\nForma de invatamant: 0=ing,1=master,2=DSA,3=doctorat";
int forma_inv, nr_inscrisi=0; forma_inv=cit_int(txt_forma_inv, 0,3); while(INFINIT) switch(meniu()) {
case 'F': forma_inv=cit_int(txt_forma_inv, 0,3); break; case 'C': nr_inscrisi=CitireDateTastatura(forma_inv,nr_inscrisi); break; case 'A': AfisareInscrisi(nr_inscrisi);
break; case 'T': return; default: printf("\n*** Optiune neimplementata"); break; }
} char meniu() { printf("\n\n" "\nF - precizare forma de invatamant" "\nR - citire date din fisier"
"\nC - citire date de la tastatura despre inscrisi" "\nS - salvare date in fisier" "\nA - afisare inscrisi" "\nM - modifica datele despre un inscris" "\nT - terminare program"
"\nOptiunea dv.:" ); return toupper(getche()); }
25
/* ========================================================
C I T D A T E . C
Contine functiile de citire a datelor pentru diferitele
categorii de 'inscrisi'.
(c)PSG2002
========================================================
*/
#include <stdio.h>
#include <string.h> #include <conio.h> #include <ctype.h> #include <stdlib.h> #include "inscrisi.h"
#include "citiri.h" #include "denspec.h"
LOGIC CitireDateComune (INSCRISI *p); void CitesteDateStudIng(int nr);
void CitesteDateMaster(int nr); void CitesteDateDSA(int nr); void CitesteDateDoctorand(int nr);
int CitireDateTastatura(int forma_inv, int nr_inscrisi) {
printf("\n\n*** Dati ENTER la 'Nume :' cand ati terminat!"); for (;nr_inscrisi<=NMAX; nr_inscrisi++) { // // Date comune tuturor categoriilor //
if(!CitireDateComune(&buf[nr_inscrisi])) break; buf[nr_inscrisi].cat = forma_inv; buf[nr_inscrisi].an = cit_int("Anul de studii",1,nr_ani[forma_inv]); // // Partea de informatii specifica fiecarei categorii
// switch (forma_inv) { case _ING: CitesteDateStudIng(nr_inscrisi); break;
case _MASTER: CitesteDateMaster(nr_inscrisi); break; case _DSA: CitesteDateDSA(nr_inscrisi);
break; case _DOCTORAT: CitesteDateDoctorand(nr_inscrisi); break; }
} return nr_inscrisi; }
26
static LOGIC CitireDateComune (INSCRISI *p) { if(*cit_text("\nNume ",p->nume,sizeof(p->nume))==EOS) return FALS;
p->an_admis = cit_int ("\nAn admis",2000,2047); p->sex = cit_int ("Sex <0=F, 1=M>",0,1); return ADEVARAT; }
COD CitesteSpecializare(int forma_inv); void CitesteMedii(float *med, int n); static void CitesteDateStudIng(int nr) { buf[nr].info.stud.spec=CitesteSpecializare(_ING);
CitesteMedii(buf[nr].info.stud.medii, buf[nr].an); if(buf[nr].an==5) buf[nr].info.stud.licenta = cit_float("Media licenta",1.,10.); }
static COD CitesteSpecializare(int forma_inv)
{ printf("\nAlegeti codul specializarii:"); AfiseazaDenumiri(forma_inv); return (COD)cit_int("\nCod specializare", 1, nr_specializari[forma_inv]); }
static void CitesteMedii(float *med, int an) { int j; char msg[20]; for(j=1;j<=an;j++) {
sprintf(msg,"Media anului %d",j); med[j-1]=cit_float(msg, j<an?5.:1., 10.); } } static void CitesteDateMaster(int nr)
{ buf[nr].info.sm.spec=CitesteSpecializare(_MASTER); cit_text("Faculatea absolvita",buf[nr].info.sm.fac, sizeof(buf[nr].info.sm.fac)); printf("\n");
CitesteMedii(buf[nr].info.sm.medii,buf[nr].an); if(buf[nr].an==2) buf[nr].info.sm.disertatie = cit_float("Media lucrare de disertatie",1.,10.); }
static void CitesteDateDSA(int nr) { } static void CitesteDateDoctorand(int nr) {
}
27
/* ========================================================
A F I S A R E . C
Contine functiile de afisare ale diferitelor
categorii de 'inscrisi'.
(c)PSG2002
========================================================
*/
#include <stdio.h> #include <string.h> #include <conio.h> #include <ctype.h> #include <stdlib.h>
#include "inscrisi.h" #include "denspec.h"
void AfisareDateComune (INSCRISI pers); void AfisareDateStudIng(int nr); void AfisareDateMaster(int nr);
void AfisareDateDSA(int nr); void AfisareDateDoctorand(int nr);
void AfisareInscrisi(int nr_inscrisi) { int nr;
for (nr=0;nr<nr_inscrisi; nr++) { // // Date comune tuturor categoriilor // AfisareDateComune(buf[nr]);
// // Afisare informatii specifice fiecarei categorii // switch (buf[nr].cat) { case _ING:
AfisareDateStudIng(nr); break; case _MASTER: AfisareDateMaster(nr); break;
case _DSA: AfisareDateDSA(nr); break; case _DOCTORAT: AfisareDateDoctorand(nr);
break; } } }
28
static void AfisareDateComune (INSCRISI p) { printf("\n\nNume: %s\nSex : %c",p.nume,p.sex?'M':'F');
printf("\nAn admis : %d",p.an_admis); printf("\nAn de studiu : %d",p.an);
} static void AfisareMedii(float *med, int n);
static void AfisareDateStudIng(int nr) { printf("\nSpecializare : %s", spec_ing[buf[nr].info.stud.spec-1]); AfisareMedii(buf[nr].info.stud.medii, buf[nr].an); if(buf[nr].an==5)
printf("\nMedia licenta : %.2f",buf[nr].info.stud.licenta); } static void AfisareMedii(float *med, int an) { int j;
for(j=1;j<=an;j++) printf("\nMedia anului %d: %.2f",j,med[j-1]); }
static void AfisareDateMaster(int nr) {
printf("\nSpecializare : %s", spec_post[buf[nr].info.sm.spec-1]); printf("\nFaculatea absolvita : %s",buf[nr].info.sm.fac); AfisareMedii(buf[nr].info.sm.medii, buf[nr].an); if(buf[nr].an==2) printf("\nMedia disertatie %.2f",buf[nr].info.sm.disertatie);
} static void AfisareDateDSA(int nr) { }
static void AfisareDateDoctorand(int nr) { }
29
/* ========================================================
C I T I R I . H
Fisierul contine prototipurile functiilor gnerale de
citire a valorilor unor variabile de tip int, double
si sir de caractere (definitiile sunt lor in citiri.c)
(c)PSG2002
========================================================
*/
#ifndef CITIRI_H #define CITIRI_H #define ENTER '\r' #define EOS '\0'
char * cit_text(char *, char *, int ); int cit_int(char *, int , int ); float cit_float(char *atentionare, float a, float b); double cit_double(char *);
char *fget_sir( char * , int , FILE *); int fputsir(char * , FILE *); long unsigned LungimeFisier(FILE *fis); #endif
/* ========================================================
D E N S P E C . H
Contine declaratiile corespunzatoarea datelor din
fisierul denspec.c (denumiri specializari si durata
acestora (nr_ani)
(c)PSG2002
========================================================
*/
#ifndef DENSPEC_H
#define DENSPEC_H
extern int nr_ani[]; extern int nr_specializari[];
extern char *spec_ing[], *spec_post[], *domenii[]; void AfiseazaDenumiri(int forma_inv); #endif
30
4. Temă de realizat în timpul laboratorului
De rezolvat (in cadrul lucrării de laborator si sub forma de tema de casa). Se vor programa toate opţiunile acestui program si se vor rezolva următoarele prin completarea si eventual modificarea surselor puse la dispoziţie.
1. La terminarea programului se pot pierde date nesalvate in fişier. De aceea, in cazul când in memorie se afla date nou introduse, utilizatorul va fi întrebat automat daca doreşte sa le salveze.
2. Configuraţi programul pentru cazul real al înscrişilor din Facultatea de Inginerie Electrica: ingineri (maxim 1500), master (maxim 250), DSA(maxim 150), doctoranzi (maxim 100).
3. Numele celor înscrişi este memorat pe lungimea maxima data in structura. Reprogramaţi luând in considerare stocarea numelui pe n+1 caractere, unde n este numărul de caractere al numelui persoanei înscrise.
4. Luaţi in considerare memorarea denumirilor specializărilor intr-un fişier. Folosiţi o tehnica similara cu cea utilizata in laboratorul trecut in cazul denumirilor de discipline.
5. Programaţi o validare a datelor introduse luând in consideraţie corespondenţa (an_admis, an de studii) pentru valoarea maxima a anului de studii cat si data curenta din calculator pentru valoarea maxima an_admis. La afişarea datelor in versiunea actuala afişarea înscrişilor are loc in ordinea in care sunt prezenţi aceştia in tabloul buf[]. Realizaţi afişarea lor grupat, pe forme de învăţământ.
6. Programaţi funcţiile de căutare înscris după nume si 'exmatriculare' (ştergere din buf[]). 7. *Programaţi toate funcţiile acestui program, inclusiv căutare si ştergere lucrând direct in
fişier.
31
6. Liste liniare 1.Obiective
� Dezvoltarea de tipuri de date abstracte în limbajul C; � Însuşirea lucrului cu tipul de dată abstractă lista; � Implementarea listelor liniare prin vector de dimensiune variabilă alocat dinamic; � Implementarea operaţiilor de salvare/citire a listelor în/din fişierele text;
2.Aspecte teoretice
O listă liniară este o secvenţă de elemente ce pot fi regăsite prin numărul de ordine (al locului pe care îl ocupă) în acea secvenţă. l=<e1,e2,…,en>
Trebuie subliniat faptul că numărul de ordine al fiecărui element, esenţial în definiţia listei, nu este neapărat legat de valoarea elementelor listei. De altfel acestea pot nici să nu fie date scalare, deci comparaţiile nu pot avea loc. Operaţii principale asupra listelor liniare:
• init() – iniţializează o listă; • insert_inc(l,e) – inserează în faţa primului element din lista l, elementul e; • insert_sfirsit(l,e) - inserează după ultimul element din lista l, elementul e; • insert_stinga(l,e,f) – inserează în faţa elementului e din lista l, elementul f; • insert_sfirsit(l,e,f) – inserează după elementul e din lista l, elementul f; • sterge_prim(l) – şterge primul element din lista l; • sterge_ultim(l) – şterge ultimul element din lista l; • sterge(l,e) - şterge elemental e din lista l; • distrugere(l) – încheie toate operaţiile cu lista l, eliberează eventual spaţiul ocupat de
listă; Alte operaţii:
• cauta(l,e) – caută în lista l, elementul e; • este_vida(l,e) –testează dacă lista l este vidă(nu conţine elemente); • este_plina(l,e) –testează dacă lista l este plină(nu mai pot fi adăugate elemente noi);
O implementare prin vector alocat dinamic a listelor liniare în limbajul C poate utiliza următoarea structură:
struct dlist { int liber; //poziŃia în care va fi inserat un nou element
int nmax; //numărul maxim de elemente
DATA *pv; //pointer la tipul DATA – pentru alocarea dinamică a
//vectorului ce conŃine elementele listei
};
32
Un avantaj major al listelor liniare implementate prin vector de dimensiune variabilă alocat dinamic este dat de faptul că listele îşi măresc capacitatea în mod dinamic. Se ajunge astfel, la o mai buna gestiune a memoriei, evitându-se pe de o parte alocarea un număr prea mare de elemente şi pe de altă parte a unui număr prea mic de elemente.
Membrul nmax al structurii dlist va conţine numărul maxim de elemente ce pot fi introduse în listă şi işi va schimba valoarea în mod dinamic (va creşte cu o constantă N_INIT), de fiecare dată când se ajunge la capacitatea maximă.
Unul din cele mai importante aspecte legate de această implementare se referă la creşterea în mod dinamic a capacităţii vectorului. Acest aspect este prezentat în funcţia de adăugare a unui nou element la sfârşitul listei.
LISTA ins_la_urma(LISTA l, DATA x) { DATA *w;
int i; if(este_plina(l)) {
//Alocarea unei noi zone de memorie pentru vectorul ce conŃine elementele
//listei. Noul vector va avea un număr de elemente egal cu numărul maxim
//de elemente (nmax) la care se adaugă valoarea N_INIT.
if((w=malloc( (l->nmax+N_INIT)*sizeof(DATA) ) )==NULL) return l;
//Copierea datelor din zona de memorie a cărei adresă de început este dată
//de pv în noua zonă de memorie (copierea elementelor listei)
for(i=0;i<l->nmax;i++) w[i]=l->pv[i];
//Creşterea numărului maxim de elemente
l->nmax = l->nmax+N_INIT;
//Eliberarea zonei de memorie spre care pointează pv
free(l->pv);
//Setarea pointerului pv la adresa de început a noii zone de memorie ce
//conŃine elementele listei
l->pv = w;
}
//Adăugarea noului element
l->pv[l->liber++]=x; return l;
}
În figurile următoare este prezentată modalitatea de creştere în mod dinamic a capacităţii vectorului ce conţine elementele listei şi de adăugare a unui nou element la sfârşitul listei.
33
3. Temă de realizat în timpul laboratorului Să se scrie un program C care implementează tipul de dată abstractă lista. Se vor putea
efectua operaţii cu liste liniare implementate prin vectori alocaţi dinamic, ale căror elemente conţin chei întregi. Programul va afişa meniul următor şi va efectua operaţiile corespunzătoare:
C - citeşte un număr întreg şi-l introduce în faţa listei L R - citeşte un fişier text ce conţine numere întregi separate prin spaţii şi le introduce în lista A - afişeaza lista L S - caută un element în lista L E - elimină primul element din lista L W - salvează lista L într-un fişier text D - din lista L se formează două noi liste, una ce conţine elementele negative şi una conţinând elementele pozitive P - afişeaza lista conţinând elementele pozitive N - afişează lista conţinând elementele negative I - informaţii despre autor T - terminare program
34
În cazul opţiunilor R şi W se va afişa conţinutul fişierului citit/scris, iar numele fişierului va fi
introdus de la tastatură. Veţi implementa tipul de dată abstractă lista în 3 fişiere: data.h, listdinv.h şi listdinv.c.
Programul demonstrativ va fi realizat sub forma unui fişier separat (demolist.c). Veţi introduce opţiuni suplimentare pentru testarea celorlalte metode ale TDA lista care au
prototipuri în listdinv.h (sterge_primul, ins_la_urma, sterge_ultim,şterge un element de cheie dată indiferent de poziţie).
4. Fişiere puse la dispoziţie • Fişierul data.h – conţine definiţia tipului informaţiei din elementele TDA lista • Fişierul listdinv.h – conţine prototipurile funcţiilor de lucru cu TDA lista • Fişierul listdinv.c – conţine definiţiile funcţiilor de lucru cu TDA lista
Fişierul data.h #ifndef _DATA_H_ #define _DATA_H_
#define ADEVARAT 1 #define FALS 0 typedef unsigned char LOGIC;
//
//-----------------------------------------
// Rezervat modificarilor utilizatorului
// care va preciza tipul informatiei din
// elementele TDA
//-----------------------------------------
//
typedef int DATA; #define FORMAT "%d" #define ABSENT 0
//
//-----------------------------------------
#endif
Fisierul ListDinv.h #ifndef _LISTDINV_H_ #define _LISTDINV_H_ #include "data.h"
//-----------------------------------
// Proprietatile TDA lista in reprez.
// cu vector alocat dinamic de dimensiune extensibila dinamic
//
#define N_INIT 10
struct dlist { int liber; int nmax; DATA *pv;
}; typedef struct dlist Lista, *LISTA;
35
//
//----------------------------------
// Metodele (operatiile) TDA
//
LISTA newl(); LISTA ins_la_urma(LISTA l, DATA x); LISTA sterge_ultim(LISTA l); DATA primul(LISTA l);
LOGIC este_vida(LISTA l); LOGIC este_plina(LISTA l); char *conv_lista_sir(LISTA l,char *s);
// ...
void destroyl(LISTA l);
#endif
Fisierul ListDinv.c
#include <stdio.h> #include <string.h> #include "listdinv.h" #include <stdlib.h>
//---------------------------------------------------
// Metodele TDA lista in implementarea
// cu vector de dimensiune extensibila alocat dinamic
//
// Elaborat: PSG, 08.04.03
//---------------------------------------------------
//
// Initializare lista
//
LISTA newl() { LISTA l; if((l=(LISTA)malloc(sizeof(Lista)))==NULL) return NULL; l->nmax=2;
l->liber=0; if((l->pv=malloc( N_INIT * sizeof(DATA) ) ) ==NULL) { free(l); l=NULL;} return l; }
//-------------------------------------
// Distruge lista
//
void destroyl(LISTA l) { free(l->pv);
free(l); }
//---------------------------------------
// Inserarea unui nou element
// la sfarsitul listei
// Daca lista este plina, extinde dimens.
//
LISTA ins_la_urma(LISTA l, DATA x) { DATA *w; int i;
36
if(este_plina(l)) { if((w=malloc( (l->nmax+N_INIT)*sizeof(DATA) ) )==NULL) return l; for(i=0;i<l->nmax;i++) w[i]=l->pv[i];
l->nmax = l->nmax+N_INIT; free(l->pv); l->pv = w; } l->pv[l->liber++]=x;
return l; }
//
//---------------------------------------
// Sterge ultimul element introdus
//
LISTA sterge_ultim(LISTA l) { if(!este_vida(l)) l->liber--; return l;
}
//
//-------------------------------------
// Returneaza valoarea primului element
// al listei
//
DATA primul(LISTA l) { return este_vida(l) ? ABSENT : l->pv[0]; }
//-------------------------------------
LOGIC este_vida(LISTA l) { return l->liber==0; }
//-------------------------------------
LOGIC este_plina(LISTA l) { return l->liber==l->nmax; }
//
//-------------------------------------
// Conversie lista -> sir
//
char *conv_lista_sir(LISTA l, char *s)
{ int i; char zona[10]; strcpy(s,"{");
if(este_vida(l)) strcat(s,"<vida>}"); else for(i=0;i<l->liber;i++) { sprintf(zona,FORMAT"%c",l->pv[i], i==l->liber-1?'}':','); strcat(s,zona);
} return s; }
37
7. Liste simplu înlănţuite 1.Obiective
� Familiarizarea cu tipul de dată abstract listă; � Implementarea TDA listă cu ajutorul pointerilor (lista simplu înlănţuită); � Implementarea unei aplicaţii care sa utilizeze liste simplu înlănţuite.
2.Aspecte teoretice Lista este, după cum s-a precizat in laboratorul precedent, o mulţime de elemente, a cărui
număr variază în timpul execuţiei unui program. Lista simplu înlănţuită vine in întâmpinarea acestui dinamism prin modul de implementare, si anume:
� un element (sau nod) al listei este un tip de data abstract ce conţine pe lângă informaţia (sau informaţiile) corespunzătoare elementului, adresa următorului element al listei:
struct nod{ int info;
struct nod * urm;
};
� lista consta intr-o singura variabila de tip pointer la struct nod care tine adresa primului element al listei:
struct nod * ListaElemente;
Lista simplu înlănţuită are următoarele avantaje faţă de lista implementată prin vectori:
- nu este necesară alocarea unei zone continue de memorie ( ca in cazul vectorilor) - operaţiile de adăugare si ştergere element se simplifică, nemaifiind necesară mutarea tuturor
elementelor Există şi un dezavantaj:
- spaţiul ocupat de o lista simplu înlănţuită este mai mare decât în cazul vectorilor, datorită pointerului care intră in componenţa fiecărui element al listei.
Pentru a utiliza o lista simplu înlănţuită sunt necesare următoarele metode:
• init() – iniţializează o listă; • adauga_inceput(l,e) – inserează în faţa primului element din lista l, elementul e; • adauga_sfirsit(l,e) - inserează după ultimul element din lista l, elementul e; • adauga_stinga(l,e,f) – inserează în faţa elementului e din lista l, elementul f; • adauga_dupa(l,e,f) – inserează după elementul e din lista l, elementul f; • sterge_prim(l) – şterge primul element din lista l; • sterge_ultim(l) – şterge ultimul element din lista l; • sterge(l,e) - şterge elementul e din lista l; • distrugere(l) – încheie toate operaţiile cu lista l, eliberează eventual spaţiul ocupat de listă; Alte metode: • cauta(l,e) – caută în lista l, elementul e; • este_vida(l,e) – testează dacă lista l este vidă(nu conţine elemente); • este_plina(l,e) – testează dacă lista l este plină(nu mai pot fi adăugate elemente noi);
38
Observaţii: � La iniţializarea listei se modifică valoarea pointerului din variabila ListaElemente la NULL,
pentru a arata ca nu exista nici un element (dacă nu se realizează această operaţie, variabila ListaElemente are o valoare diferită de NULL care poate fi confundată cu o adresă de element şi prin urmare, la o eventuala verificare a stării, lista apare ca având elemente).
� La inserarea unui element trebuie realizaţi următorii paşi în ordinea specificată: o alocare zona de memorie de dimensiune egala cu numărul de octeţi necesari pentru a
memora un element al listei, o memorarea in aceasta zona a informaţiilor noi o realizarea legăturii cu elementele deja existente in lista
� La ştergerea unui element din lista trebuie realizaţi următorii paşi în ordinea specificată: o păstrarea într-o variabilă temporară a adresei elementului ce urmează a fi şters o realizarea legăturilor astfel încât elementul de şters să nu mai apară în listă o eliberarea zonei de memorie ocupată de elementul ce trebuie şters
� Ştergerea unui element sau a întregii liste nu este echivalenta cu ştergerea efectiva a informaţiilor din memorie, ci vizează marcarea zonei de memorie ca fiind disponibilă pentru stocarea altor informaţii.
3. Temă de realizat în timpul laboratorului Sa se scrie un program C care implementează tipul de data abstracta lista. Se vor putea
efectua operaţii cu liste înlănţuite, ale căror elemente conţin chei întregi. Programul va afişa meniul următor:
C - citeşte un număr întreg şi îl introduce în faţa listei L R - citeşte un fişier text ce conţine numere întregi separate prin spaţii şi le introduce în lista L A - afişează lista L S - caută un element in lista L E - elimina primul element din lista L W - salvează lista L intr-un fişier text D - din lista L se formează doua noi liste, cu elementele negative şi respectiv pozitive P - afişează lista conţinând elementele pozitive N - afişează lista conţinând elementele negative I - informaţii despre autor T - terminare program In cazul opţiunilor R si W se va afişa conţinutul fişierului citit/scris, iar numele fişierului va fi
cerut utilizatorului. Se vor introduce opţiuni suplimentare pentru testarea celorlalte metode ale TDA lista care au prototipuri in Lista.h (sterge_primul, ins_la_urma, sterge_ultim, sterge - şterge un element de cheie dată, indiferent de poziţie).
4. Fişiere puse la dispoziţie Pentru realizarea aplicaţiei propuse la acest laborator se vor utiliza următoarele fişiere: � data.h – fişier header ce conţine definiţia tipului de informaţie continuta de elementele din
TDA lista simplu inlantuita; � lista.h - fişier header ce conţine prototipurile funcţiilor specifice TDA lista simplu inlantuita; � lista.c - fişier sursă C cu implementarea funcţiilor corespunzătoare TDA lista simplu inlantuita. Programul demonstrativ va fi realizat sub forma unui fisier separat (demolist.c).
39
Fişierul data.h
#ifndef _DATA_H_
#define _DATA_H_ #define FALS 0 #define ADEVARAT (!FALS) typedef unsigned char LOGIC;
//
//-----------------------------------------
// Rezervat modificarilor utilizatorului
// care va preciza tipul informatiei din
// elementele TDA
// PSG, 1.04.03
//-----------------------------------------
//
typedef int DATA; #define FORMAT "%d"
#define ABSENT 0
//
//-----------------------------------------
#endif
Fişierul lista.h
#ifndef _LISTA_H_ #define _LISTA_H_ #include "data.h"
//
// Elaborat: PSG, 11.04.03
//----------------------------------
// Proprietatile TDA
//
struct clist { DATA cheie; struct clist *urm; }; typedef struct clist Lista, *LISTA;
//
//----------------------------------
// Metodele (operatiile) TDA
//
LISTA newl(void);
LISTA ins_in_fata(LISTA l, DATA x); LISTA sterge_primul(LISTA l); LISTA ins_la_urma(LISTA l, DATA x); LISTA sterge_ultim(LISTA l); LISTA sterge(LISTA l, DATA x);
LISTA cauta(LISTA l, DATA x); DATA primul(LISTA l); LOGIC este_vida(LISTA l); LOGIC este_plina(LISTA l); char *conv_sir_lista(LISTA l,char *s);
// ...
void destroyl(LISTA l); #endif
40
Fişierul lista.c
#include <stdio.h>
#include <stdlib.h> #include <string.h> #include "lista.h"
// ----------------------------------------------------
// Metodele TDA lista in implementarea
// cu vector alocat static
// Elaborat: PSG, 11.04.03
// Modificat:PSG, 13.04.05
// ----------------------------------------------------
// Initializeaza o lista vida
//
LISTA newl() { return NULL;
}
//
// ----------------------------------------------------
// Distruge o lista vida
//
void destroyl(LISTA l) { LISTA p; for(;!este_vida(l); l=p) { p=l->urm; free(l);
} }
//
// ----------------------------------------------------
// Insereaza un element in fata listei
//
LISTA ins_in_fata(LISTA l, DATA x) { LISTA t; if((t = (LISTA)malloc(sizeof(Lista)))==NULL) {
printf("\n\a EROARE la alocarea memoriei"); return l; } // alocare reusita
t->cheie = x; t->urm = l; return t; }
//
// -----------------------------------------------------
//
// Cauta o cheie in lista si intoarce adresa elementului
//
LISTA cauta(LISTA l,DATA x)
{ for( ;!este_vida(l) ;l=l->urm) if(l->cheie==x) return l; return NULL; }
41
//
// ----------------------------------------------------
//
// Returneaza cheia primului element al listei
// sau ABSENT daca nu este in lista
//
DATA primul(LISTA l) {
return este_vida(l) ? ABSENT:l->cheie ; }
//
// ----------------------------------------------------
// Verifica daca lista este vida
//
LOGIC este_vida(LISTA l) { return l==NULL; }
//
// ----------------------------------------------------
// Verifica daca lista este plina
// Se poate rescrie aceasta functi
//
LOGIC este_plina(LISTA l) { return FALS; }
//
// ----------------------------------------------------
//
// Conversie lista in sir de caractere
//
char *conv_sir_lista(LISTA l,char *s)
{ char zona[20]; strcpy(s,"{"); if(este_vida(l)) strcat(s,"<vida>}");
else for(;!este_vida(l); l=l->urm) { sprintf(zona,FORMAT"%c",primul(l), este_vida(l->urm)?'}':','); strcat(s,zona); }
return s; }
// ----------------------------------------------------
//
// T E M A D E E F E C T U A T
// ----------------------------------------------------
LISTA sterge_primul(LISTA l) {} LISTA ins_la_urma(LISTA l, DATA x) {}
LISTA sterge_ultim(LISTA l) {} LISTA sterge(LISTA l, DATA x) {}
42
5. Temă pentru studiu individual La concertul de muzica clasica care are loc o data pe an in judeţul Suceava, se realizează anul
acesta un studiu despre oamenii care vin la acest spectacol, pentru a vedea daca se poate organiza de doua sau chiar trei ori pe an. Informaţiile reţinute despre fiecare persoana care îşi cumpără bilet sunt: adresa (nu cea exactă; cea din care să rezulte zona in care locuieşte), ocupaţia, vârsta, număr bilet. In cazul in care o persoana cumpără bilete pentru mai multe persoane se vor cere informaţii despre fiecare in parte. Sa se implementeze o aplicaţie care sa permită efectuarea următoarelor operaţii utilizând lista simplu înlănţuită:
A. Adăugare informaţii despre o persoana. L. Listare informaţii despre toate persoanele care si-au cumpărat bilet pana la un moment dat S. Ştergere informaţii despre o persoana in cazul in care aceasta renunţă la bilet D. Afişare bilete disponibile Z. Afişarea numărului de bilete vândute pe zone din oraş V. Sa se realizeze trei liste corespunzătoare fiecărui interval de vârsta in care se încadrează cumpărătorii (10-25, 25- 40, 40-65) si sa se determine intervalul cu număr maxim de persoane. O. Sa se afişeze toate persoanele care au o anumita ocupaţie si au cumpărat bilet pentru concert. T. Terminare program
Observaţii 1. Un element al listei în acest caz va arăta în modul următor:
struct persoana{
int nr_bilet;
char * adresa;
char * ocupatie;
int varsta;
};
2. La adăugarea unui element nou trebuie alocată memorie atât pentru structura in sine cât şi pentru cele două şiruri de caractere care vor tine adresa si ocupaţia. 3. La ştergerea unui element se va elibera mai întâi zona alocată şirurilor de caractere şi apoi cea alocată structurii.
nr_bilet varsta ocupatie adresa
\0
\0
43
8. Stiva
1.Obiective � Familiarizarea cu tipul de dată abstract stiva; � Implementarea TDA stivă prin moştenire din TDA lista; � Verificarea închiderii corecte a parantezelor în cazul unei expresii matematice.
2.Aspecte teoretice Stiva este un caz particular de structură de date liniară în care intrările şi ieşirile se fac la un
singur capăt al ei. Structura de stivă presupune, conform definiţiei, o anumită disciplină de acces. Se spune că accesul la o stiva este de tip LIFO (Last In - First Out):
� totdeauna se adaugă un obiect "deasupra" ultimului depus; � totdeauna se extrage ultimul obiect adăugat.
Această structură de date cunoaşte mai multe implementări (vectori alocaţi static sau dinamic, înlănţuire simplă). Toate implementările au în comun cunoaşterea în permanenţă a vârfului stivei. Operaţiile de inserare şi respectiv extragere ale elementelor sunt foarte rapide deoarece nu necesită parcurgerea stivei şi deci nu depind de numărul de elemente. Operaţiile cu stiva poartă următoarele denumiri consacrate:
� push – inserare în stivă � pop – îndepărtarea elementului din vârful stivei � top – afişarea elementului din vârful stivei � toppop – operaţia top urmată de pop
Se prezintă în continuare evoluţia unei stive implementată prin înlănţuire pentru următoarea succesiune de operaţii (push(7), push(2), push (9), pop(). Vârful stivei (începutul înlănţuirii) este indicat chiar de pointerul s (spre primul element).
7
push (7)
s este NULL – stiva este vidă
2
push (2)
7
9
push (9)
2 7
2
pop ()
7
s
s
s
s
44
3.Exemple Pentru realizarea aplicaţiei propuse la acest laborator se va porni de la următoarele fişiere:
� data.h – fişier header pentru implementarea tipului DATA; � lista.h - fişier header pentru implementarea TDA lista; � lista.c – fişier sursă C cu implementarea funcţiilor corespunzătoare TDA lista; � stiva.h - fişier header pentru implementarea TDA stiva; � stiva.c - fişier sursă C cu implementarea funcţiilor corespunzătoare TDA.
Primele trei fişiere au fost prezentate în laboratorul corespunzător listelor.
//--------------------------------------------------------
// F i s i e r u l s t i v a . h
//-------------------------------------------------------- #ifndef __STIVA_H_
#define __STIVA_H_
#include "lista.h"
typedef LISTA STIVA;
// initializare stiva
extern STIVA news();
// inserare element in stiva
extern STIVA push(STIVA,DATA);
// indepartare element din stiva
extern STIVA pop(STIVA);
// afisarea elementului din varful stivei
extern DATA top(STIVA);
// afisarea elementului din varful stivei si stergerea lui
extern STIVA toppop(STIVA ,DATA *);
// testare stiva vida
extern LOGIC is_emptys(STIVA);
// testare stiva plina
extern LOGIC is_fulls(STIVA);
// conversie stiva la sir
extern char * toString(STIVA s, char *zona);
// eliberare spatiu alocat de stiva
extern void destroys(STIVA);
#endif
45
//--------------------------------------------------------
// F i s i e r u l s t i v a . c
//-------------------------------------------------------- #include "stiva.h"
#include "lista.h"
STIVA news(){
return (STIVA)newl();
}
//--------------------------------------------------------
STIVA push(STIVA s,DATA x){
return ins_in_fata((LISTA)s,x); }
//---------------------------------------------------------
STIVA pop(STIVA s){
return (STIVA) sterge_prim((LISTA)s);
}
//---------------------------------------------------------
DATA top(STIVA s){
return is_empty(s)?ABSENT : primul(LISTA)s);
}
//---------------------------------------------------------
STIVA toppop(STIVA s, DATA *val){
*val=top(s); return pop(s);
}
//---------------------------------------------------------
LOGIC is_emptys( STIVA s){
return este_vida((LISTA)s);
}
//---------------------------------------------------------
LOGIC is_fulls(STIVA s){
return este_plina((LISTA)s);
}
// ---------------------------------------------------------
char * toString(STIVA s, char *zona){
// completati cu codul necesar conversiei stivei s la sir }
//---------------------------------------------------------
void destroys(STIVA s){
destroy((LISTA)s);
}
46
4. Temă de realizat în timpul laboratorului Exerciţiul 1
Să se realizeze o aplicaţie tip meniu care să permită testarea operaţiilor cu stive. Stiva va conţine elemente de tip caracter: Exerciţiul 2 – extindere verificare paranteze
În aplicaţia anterioară, la cazul v se presupune că şirul conţine numai paranteze rotunde. Problema validării închiderii corecte a parantezelor poate fi generalizată în sensul urmăririi unor perechi de simboluri definite anterior. În cazul unei expresii incorecte să se genereze un mesaj de eroare cât mai explicit. Secvenţa se consideră validă dacă:
� fiecare pereche conţine un simbol de tipul stânga şi un simbol de tipul dreapta; � fiecare simbol face parte din exact o pereche; � secvenţa de simboluri care apare între simbol_stânga şi simbolul_dreapta trebuie să
satisfacă cele două condiţii anterioare. De exemplu, fiind date perechile: ( - ), [ - ], { - }, S – D, următoarea secvenţă este validă:
( S [ { S D ( ) [ ] } ] D )
5. Temă pentru studiu individual Exerciţiul 1 – evaluarea unei expresii aritmetice postfixate
Pe lângă notaţia uzuală a expresiilor aritmetice (notaţia infixată) mai există notaţiile prefixate şi respective postfixate. Ambele au avantajul că nu necesită paranteze pentru indicarea priorităţilor.
infixat: (5 - 3) * 9 prefixat: * - 5 3 9 postfixat: 5 3 – 9 *
Expresiile scrise în notaţie postfixată pot fi uşor evaluate utilizând o stivă. Se citesc pe rând
cuvintele din şirul de caractere reprezentând expresia aritmetică. Dacă respectivul cuvânt este un număr atunci acea valoare este inserată în stivă. La întâlnirea unui operator se preiau şi se îndepărtează din stivă ultimele două valori iar rezultatul obţinut prin aplicarea operatorului la cele două valori se inserează în stivă. După parcurgerea tuturor cuvintelor, în stivă ar trebui să se găsească un singur element reprezentând rezultatul expresiei.
Aplicaţia de realizat trebuie să afişeze rezultatul unei expresii aritmetice postfixate (reprezentată sub forma unui şir de caractere). De asemenea va fi semnalizată o expresie greşită.
P – inserarea unui element in stiva
Q – indepartarea elementului din varful stivei
T – afisarea elementului din varful stivei
U – afisarea si ulterior stergerea elementului din varful stivei
S – afisarea starii stivei (plina, vida, contine elemente)
A – afisarea stivei prin folosirea functiei toString
V – verificarea inchiderii corecte a parantezelor rotunde
in cazul unui sir de caractere, ignorand operanzii sau operatorii
I – info autor
G – gata program
47
9. Coada 1.Obiective
� Familiarizarea cu tipul de dată abstract coadă; � Implementarea TDA coadă prin vectori circulari; � Implementarea unui simulator al serviciilor medicale oferite de un doctor de familie.
2.Aspecte teoretice Coada este o structură specială, care restricţionează accesul la elementele sale astfel:
� Adăugarea elementelor este permisă numai la sfârşitul structurii � ştergerea este permisă numai de la începutul ei.
O coadă este caracterizată de expresia First In First Out (FIFO) – Primul Venit Primul Servit. Cele mai uzuale implementări ale cozii sunt cu ajutorul:
� listelor simple înlănţuite � vectorilor circulari.
În laboratorul de faţă va fi abordată cea de-a doua implementare. Vectorii circulari se diferenţiază de vectorii liniari prin faptul că, după ocuparea tuturor celor NMAX poziţii din vector, se continuă cu ocuparea poziţiilor de la începutul vectorului ( 0, 1, etc.). Acest lucru este posibil numai în cazul TDA coadă la care, între timp, au fost eliminate elemente de la începutul vectorului.
Utilizarea vectorilor circulari permite refolosirea zonei de memorie eliberată de elementele ce părăsesc coada.
Pentru a reprezenta TDA coadă prin vectori circulari avem nevoie de o structură specială, care să conţină pe lângă vectorul corespunzător cozii:
� doi indicatori ce vor specifica începutului şi sfârşitului cozii. � F – începutul cozii (engl. Front) � R – sfârşitul cozii (engl. Rear)
� si o variabilă rotire care este necesară pentru a diferenţia cele 2 situaţii când indicatorii F şi R sunt egali (dacă F = R şi rotire = FALS, coada este vidă; dacă F = R şi rotire = ADEVĂRAT, coada este plină).
Principalele operaţii efectuate asupra acestei structuri de date se realizează prin intermediul metodelor:
� openq() – iniţializare coadă; � add(q,e) – adăugarea elementului e în coada q; � rem(q) – îndepărtează din coada q primul element; � front(q) – returnează valoarea primului element din coada q; � isemptyq(q) – returnează ADEVĂRAT când coada este vidă; � isfullq(q) – returnează ADEVĂRAT când coada este plină; � destroyq(q) – eliberează spaţiul alocat cozii.
struct coada{ unsigned F,R; unsigned char rotire; DATA v[NMAX];
};
48
3. Temă de realizat în timpul laboratorului Cele mai importante aplicaţii ale structurii de tip coadă sunt reprezentate de simularea unor
situaţii de aşteptare reale. Vom considera un simulator ce modelează serviciile medicale oferite de un doctor de familie.
Acesta soseşte la ora 9 şi doreşte să termine programul la ora 13, deoarece în a doua jumătate a zilei cabinetul este ocupat de un coleg de-al său. În acest scop se realizează o simulare pe calculator a situaţiei existente pentru a determina ora la care trebuie primit ultimul pacient astfel încât cabinetul să fie liber la ora 13 (se acceptă o eroare de 10 minute). Vom presupune că fiecare pacient cere un singur serviciu din următoarele tipuri:
� adeverinţă (scutire, concediu medical etc.) – 5 min. � consultaţie (implică consultarea pacientului şi scrierea unui bilet de trimitere la diverse
cabinete de analize medicale) – 10 min. � tratament (se consideră că pacientul are analizele efectuate şi pe baza lor doctorul scrie
tratamentul corespunzător) – 7 min. Se consideră că a sosit un nou pacient dacă a trecut un anume interval de timp de la sosirea
pacientului anterior. Acest interval este o valoare aleatoare între 0 si T_MAX (T_MAX = 20). Pacientul sosit va fi adăugat în coadă cu un tip de serviciu generat aleator numai dacă timpul total de servire al pacienţilor din coada nu depăşeşte durata maximă de şedere a doctorului.
Trecerea timpului va fi simulată de un contor ce va lua valori de la 0 la valoarea duratei totale de simulare (exp.: 4 ore în cazul de faţă). La fiecare cuantă de timp (1 min.) se vor efectua următoarele operaţii:
� se verifică dacă nu a sosit un pacient. � dacă a sosit şi timpul necesar servirii pacienţilor nu depăşeşte durata totală de simulare, se
introduce în coadă şi se actualizează timpul necesar servirii pacienţilor. Obs.: pentru fiecare pacient se va memora în coadă momentul sosirii şi tipul serviciului cerut de acesta.
� se actualizează situaţia doctorului: � Dacă este liber şi sunt pacienţi pe sală, primul dintre ei este eliminat din coadă şi se
începe servirea lui. � Dacă este un pacient în cabinet se scade o unitate din timpul necesar serviciului cerut de
acesta. Dacă timpul de servire devine 0, doctorul trece în starea „LIBER”.
Aplicaţia va simula trecerea timpului printr-o structură repetitivă şi la fiecare cuantă de timp ( 1 min) se vor efectua operaţiile corespunzătoare descrierii problemei, utilizând metodele specifice TDA Coadă. De asemenea, metodele corespunzătoare TDA Coadă care nu sunt implementate în fişierele puse la dispoziţie vor fi programate în cadrul laboratorului. La final aplicaţia va genera următoarele rezultate:
� un fişier text, cu antetul prezentat mai jos, în care trebuie înregistraţi pacienţii din ziua respectivă: Nr_ordine Timp_sosire Tip_serviciu Moment_servire
� pe ecran se va afişa momentul în care pacienţii nu au mai fost primiţi în sala de aşteptare.
49
4. Fişiere puse la dispoziţie Pentru realizarea aplicaţiei propuse la acest laborator se vor utiliza următoarele fişiere: � data.h – fişier header ce conţine definiţia tipului de informaţie din TDA coada; � coada.h - fişier header ce conţine prototipurile funcţiilor specifice TDA coada; � coada.c - fişier sursă C care conţine implementarea funcţiilor corespunzătoare TDA coadă
realizată cu vectori circulari.
//--------------------------------------------------------
// F i s i e r u l c o a d a . h
// (c)PSG2002, FG2005
//--------------------------------------------------------
#ifndef __COADA_H_ #define __COADA_H_ #include "data.h" #define NMAX 10
struct coada{ unsigned F,R; LOGIC rotire; DATA pacienti[NMAX][2]; };
typedef struct coada *QUEUE; QUEUE newq(void); LOGIC add(QUEUE,DATA,DATA); LOGIC rem(QUEUE);
LOGIC front(QUEUE,DATA*,DATA *); LOGIC isemptyq(QUEUE); LOGIC isfullq(QUEUE); char * toString(QUEUE,char *); void destroyq(QUEUE);
#endif
//--------------------------------------------------------
// F i s i e r u l d a t a . h
// (c)PSG2002
//--------------------------------------------------------
#ifndef _DATA_H_ #define _DATA_H_ #define FALS 0 #define ADEVARAT !FALS typedef unsigned char LOGIC;
//-----------------------------------------
// Rezervat modificarilor utilizatorului care va preciza tipul
// informatiei din elementele TDA
//-----------------------------------------
//
typedef int DATA; #define FORMAT "%d" #define ABSENT 0 #endif
50
//--------------------------------------------------------
// F i s i e r u l c o a d a . c
// (c)PSG2002, FG2005
//--------------------------------------------------------
#include <stdio.h> #include <stdlib.h> #include <string.h> #include "coada.h"
//---------------------------------------------------------
QUEUE newq(void){ QUEUE q; if((q=(QUEUE)malloc(sizeof(struct coada)))==NULL)
printf("\n alocare imposibila"); else{ q->F = q->R = 0; q->rotire = FALS; }
return q; }
//---------------------------------------------------------
LOGIC isfullq(QUEUE q){
return (q->F == q->R && q->rotire == ADEVARAT); }
//---------------------------------------------------------
LOGIC add(QUEUE q, DATA timp_sos, DATA tip_serv){
if ( isfullq(q) ) return FALS; q->pacienti[q->R][0] = timp_sos; q->pacienti[q->R][1] = tip_serv; if( ++ q->R == NMAX){
q->R = 0; q->rotire = ADEVARAT; } return ADEVARAT;
}
51
10. Mulţimi 1.Obiective
� Familiarizarea cu structura de dată mulţime reprezentată prin vectori caracteristici; � Prezentarea tehnicilor utilizate la implementarea TDA mulţime prin vectori de biţi; � Implementarea/testarea principalelor operaţii cu mulţimi.
2.Aspecte teoretice Structura de date mulţime cunoaşte mai multe implementări, cele mai utilizate fiind prin liste
respectiv prin vectori de biţi. A doua implementare este posibilă doar în cazul modelării în prealabil a mulţimilor prin vectori caracteristici.
Fie U un univers, E un vector care asociază bijectiv fiecărui element din U un număr cuprins între 0 şi |U|-1 numit poziţia elementului şi mulţimea A inclusă în U. Vectorul caracteristic al mulţimii A în raport cu universul U are dimensiunea |U| şi se notează cu CA. Dacă elementul E[i] din U aparţine mulţimii A atunci CA[i] are valoarea 1 altfel valoarea 0.
Pentru cazul general, este nevoie să fie stocat şi vectorul E care să ofere o poziţie fiecărui element din universul U. Dacă însă universul U conţine doar numerele întregi din intervalul [0,n-1] atunci nu mai este necesară o structură suplimentară, valorile elementelor fiind chiar indicii din vectorii caracteristici.Considerăm de exemplu:
U = {0,1,2,3,4,5,6,7,8,9,10,11}; A = {2,5,9}; B = {0,4,8,9,11}
Vectorii caracteristici ai celor două mulţimi sunt:
Datorită faptului că valorile pe care le poate lua un element oarecare al unui vector
caracteristic fac parte strict din mulţimea {0,1} este posibilă o importantă economie de memorie prin reprezentarea fiecărui element din vector prin câte un bit. Vectorii caracteristici din exemplul anterior au nevoie de câte doi octeţi pentru a putea fi memoraţi.
� Numărul de octeţi necesar a fi alocaţi este (|U|+7)/8; � Pentru simplitatea în programare în cadrul unui octet numerotarea este inversată;
� Indicele x se află în octetul x/8 la distanţa x%8 de capătul din dreapta; poziţionarea în cadrul octetului se realizează cu o mască obţinută din 1 deplasat la stânga cu x%8.
primul octet al doilea octet
0 1 2 3 4 5 6 7 8 9 10 11
0 0
1
0
0
1
0
0
1
0
0
0
1
0
0
0
CA
CB
0
1
1
0
0
1
0
1
11 10 9 8 7 6 5 4 3 2 1 0 15 14 13 12
0 0
1
0
0
1
0
0
0
0
0
1
0
0
0
1
CA
CB
indici
1
0
1
1
0
0
1
0
indici
52
3.Exemple Sunt puse la dispoziţie următoarele fişiere:
� data.h – fişier header pentru implementarea tipului DATA; � multime.h - fişier header pentru implementarea TDA mulţime; � multime.c – fişier sursă C cu implementarea funcţiilor corespunzătoare TDA mulţime; � main.c - fişier sursă C cu implementarea unui meniu ce testează operaţiile specifice.
4. Temă de realizat în timpul laboratorului 1. Să se studieze fişierele sursă puse la dispoziţie şi să se implementeze funcţiile corespunzătoare pentru opţiunile nefuncţionale:
� S – intersecţia mulţimilor A, B � T – diferenţa mulţimilor A, B
Prototipul celor două funcţii se află în fişierul multime.h. Este necesară definirea funcţiilor (în fişierul mulţime.c) şi apelarea corespunzătoare (în fişierul main.c). 2. Să se extindă aplicaţia pentru a permite trei opţiuni suplimentare:
� E – testarea egalităţii mulţimilor A, B � C – complementara mulţimii A � V – verificarea relaţiei lui de Morgan în forma C(A∩B) = C(A) U C(B)
Este necesară declararea şi definirea unei funcţii care să testeze egalitatea dintre două mulţimi precum şi definirea funcţiei de complementare a unei mulţimi.
//--------------------------------------------------------
// F i s i e r u l m u l t i m e . h
//-------------------------------------------------------- #ifndef _MULTIMI_H_ #define _MULTIMI_H_
#include "data.h"
// proprietati TDA
struct multime{
int n; // numarul de elemente
char *pv; // pointerul zonei de octeti
};
typedef struct multime Multime,*MULTIME;
// metode (operatii) TDA
MULTIME newSet(int n);
MULTIME insert(MULTIME e, DATA x);
MULTIME Delete(MULTIME e, DATA x); LOGIC member(MULTIME e, DATA x);
int cardinal(MULTIME e);
MULTIME Union(MULTIME A, MULTIME B);
MULTIME intersect(MULTIME A, MULTIME B);
MULTIME diff(MULTIME A, MULTIME B);
MULTIME complementara(MULTIME A);
char *conv_multime_sir(MULTIME e, char *zona);
LOGIC isEmptySet(MULTIME e);
LOGIC isUniverse(MULTIME e);
void destroySet(MULTIME e);
#endif
53
//--------------------------------------------------------
// F i s i e r u l m u l t i m e . c
//--------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "multime.h"
MULTIME newSet(int n) {
//alocarea spaŃiului necesar informatiilor despre multime
MULTIME e=(MULTIME) malloc(sizeof(Multime));
if (e!=NULL) {//daca alocarea a avut succes
char *q;
// se aloca spatiul pentru vectorul caracteristic
q=(char *) malloc((n+7)/8);
// daca alocarea nu poate fi realizata
if (q==NULL) {
free (e); // se elibereaza spatiul deja alocat
return NULL; // multimea nu poate fi initializata
}
// se completeaza campurile corespunzatoare e->n = n;
e->pv = q;
// se initializeaza vectorul caracteristic cu 0
for(n=(n+7)/8 -1;n>=0;n--)
q[n]=0; }
return e;
}
MULTIME insert(MULTIME e, DATA x) {
int ix=(int)x; // conversia de la tipul DATA la tipul int
if (ix>=0 && ix<e->n) // testarea nedepasirii limitelor
// setarea bitului ix din vect. caracteristic la valoarea 1
// prin operatia de SAU pe biti intre octetul ix/8
// si o masca ce contine 1 doar pe pozitia ix%8
// considerata de la dreapta spre stanga
e->pv[ix/8] |= 1<< ix%8;
return e; }
LOGIC member(MULTIME e, DATA x) {
// conversia de la tipul DATA la tipul int
int ix=(int)x;
// testarea nedepasirii limitelor
if (ix>=0 && ix<e->n)
// daca bitul ix din vectorul caracteristic are valoarea 1
// expresia de mai jos returneaza o valoare diferita de 0
// altfel returneaza valoarea 0
return e->pv[ix/8] & 1 << ix%8;
// in caz de depasire a limitelor corespunzatoare
// elementul x nu apartine multimii
return FALS; }
54
MULTIME Delete(MULTIME e, DATA x) {
int ix=(int)x;
e->pv[ix/8] &= ~( 1 << ix%8 );
return e;
}
int cardinal(MULTIME e) { return e->n;
}
MULTIME Union(MULTIME A,MULTIME B) { MULTIME R;
int i;
if(A==NULL || B==NULL) {
printf("\nErr: cel putin o multime este neinitiaizata.");
return NULL;
}
if(A->n != B->n) {
printf("\nEroare: universuri de cardinali diferiti");
return NULL;
}
if((R=newMultime(A->n))==NULL) return NULL;
for(i=0;i<(A->n+7)/8;i++)
R->pv[i] = A->pv[i] | B->pv[i]; return R;
}
void destroySet(MULTIME e) {
if(e!=NULL) {
free(e->pv);
free(e);
} }
LOGIC isEmptySet(MULTIME e) {
int i;
for(i=0;i<(e->n+7)/8;i++)
if(e->pv[i] !=0) return FALS;
return ADEVARAT;
} char *conv_multime_sir(MULTIME e, char *zona) {
int i,j;
char oct;
if(e==NULL) return "Multime neintializata";
if(isEmptySet(e)) return "vida";
else {
strcpy(zona,"{");
for(i=0;i<(e->n+7)/8;i++) {
oct=e->pv[i];
for(j=0;j<8;j++) {
if((oct & 1)!=0)
sprintf(zona+strlen(zona), FORMAT",",i*8+j); oct>>=1;
}
}
sprintf(zona+strlen(zona)-1,"}");
return zona;
}
}
55
//--------------------------------------------------------
// F i s i e r u l m a i n . c
//--------------------------------------------------------
#include <stdio.h>
#include <conio.h>
#include <ctype.h>
#include <process.h> #include "multime.h"
#define INSERT 0
#define DELETE 1
char menu(void);
void operatie(MULTIME a, char *denMultime, int tipOperatie);
void main() {
int n;
char zona[200];
MULTIME a=NULL,b=NULL,r=NULL; printf("\nNr. maxim de elemente:");
scanf("%d",&n);
while(1){
switch(menu()){
case 'A': if(a!=NULL) destroySet(a);
a=newMultime(n);
break;
case 'B': if(b!=NULL) destroySet(b);
b=newMultime(n);
break;
case 'I': operatie(a, "A", INSERT);
break;
case 'J': operatie(b, "B", INSERT); break;
case 'D': operatie(a, "A", DELETE);
break;
case 'F': operatie(b, "B", DELETE);
break;
case 'G': printf("\nA=%s",conv_multime_sir(a,zona));
break;
case 'H': printf("\nB=%s",conv_multime_sir(b,zona));
break;
case 'R': printf("\nA U B=%s",
conv_multime_sir( r=Union(a,b) , zona));
destroySet(r);
break; case 'X': destroySet(a);
destroySet(b);
return;
default:printf("\n Optiune inexistenta");
}
}
}
56
char menu() {
printf("\n A-Initializare multime A ");
printf("\n B-Initializare multima B ");
printf("\n I-Inserare A ");
printf("\n J-Inserare B ");
printf("\n D-Delete A ");
printf("\n F-Delete B ");
printf("\n G-Afiseaza A ");
printf("\n H-Afiseaza B ");
printf("\n R-Afiseaza A U B "); printf("\n S-Afiseaza A intersectat B ");
printf("\n T-Afiseaza A \\ B ");
printf("\n X-Exit ");
printf("\n");
printf("\n Introduceti optiunea: ");
return toupper(getche());
}
// -----------------------------------------------------------------
// Procedura operatie este scrisa pentru acest program demo
// fiind si o ilustrare a utilizarii tablourilor de pointeri
// la functii. Procedura are urmatoarele argumente:
// e - multimea cu care se va executa operatia (insert / delete)
// denMultime - numele multimii (necesar pt. ev. mesaje de err.)
// tipOperatie - tipul operatiei (0 = insert, 1 = delete)
// Procedura citeste de la tastatura elementul de inserat/sters.
// In cazul operatiei delete verifica apartenenta elementului.
// -----------------------------------------------------------------
void operatie(MULTIME e, char *denMultime, int tipOperatie)
{
char *denOperatii[]={"inserat","eliminat"};
MULTIME (*operatii[])(MULTIME e, DATA k)={insert,Delete};
DATA x;
if(e!=NULL){
printf("\nElementul de %s in %s:", denOperatii[tipOperatie], denMultime);
scanf(FORMAT,&x);
if(x<0 || x>= cardinal(e))
printf("\nElementul "FORMAT" nu poate apartine
lui %s:", x, denMultime);
else if (tipOperatie==DELETE && !member(e,x))
printf("\nElementul "FORMAT" nu apartine
lui %s:", x, denMultime);
else
e=operatii[tipOperatie](e,x);
} else
printf("\nNu ati initializat multimea %s:",denMultime);
}
57
11. Arbori 1.Obiectiv
� Familiarizarea cu tipul de data abstract Arbore
� Însuşirea lucrului cu TDA Arbore; � Parcurgerea arborilor binari � Evaluarea expresiilor aritmetice
2.Aspecte teoretice Un arbore este o structură de date ierarhizată în care elementele structurii, numite noduri, sunt
legate între ele prin relaţii de tip tata-fiu. Nodul fără nici un predecesor(tată) este numit rădăcină, iar nodul care nu are nici un succesor(fiu) este numit frunză.
Gradul unui nod este numărul de fii pe care îi are acel nod. Nodurile care au grad zero se numesc noduri frunză sau noduri terminale. Gradul unui arbore este valoarea maximă a gradelor nodurilor sale, sau, cu atte cuvinte, gradul unui arbore este egal cu numărul maxim de fii pe care îi are un nod. Un arbore binar este un arbore care are gradul 2.
Exemplu. În figura 1, arborele binar reprezintă expresia aritmetică (a+1)*(b-(a+c)*2).
Figura1. Reprezentarea unei expresii aritmetice prin arbore binar
Traversarea unui arbore reprezintă o metodă de examinare sistematică a nodurilor unui
arbore, astfel încât fiecare nod să fie vizitat o singură dată şi să nu rămână niciun nod nevizitat. Se remarcă patru strategii de traversare a unui arbore. În cazul arborilor binari, se utilizează o serie de prescurtări ale acestora, astfel:
Preordine – RSD (Rădăcină, Stânga, Dreapta) – se vizitează Rădăcina, apoi subarborele stâng, după care cel drept; la vizitarea fiecărui subarbore se aplică din nou aceeaşi regulă de vizitare, începând cu Rădăcina sa.
Inordine – SRD (Stânga, Rădăcină, Dreapta) - se vizitează subarborele stâng, apoi Rădăcina, după care subarborele drept.
Postordine – SDR (Stânga, Dreapta, ,Rădăcină) - se vizitează subarborele stâng, apoi cel drept şi la final Rădăcina.
58
3.Teme de realizat în timpul laboratorului 1. Se considera o aplicatie demonstrativă de utilizare a arborilor binari. Sa se implementeze urmatorul meniu:
C - constructie arbore R - afisare in format RSD (Radacina Stanga Dreapta)
S - afisare in format SRD (Stanga Radacina Dreapta)
D - afisare in format SDR (Stanga Dreapta Radacina)
H - afisarea inaltimii arborelui I - info autor
X - iesire din program (si eliberare memorie arbore)
Observatii:
• arborele se va reprezenta prin legaturi catre descendentii stanga si dreapta; • informatia utila va fi de tip DATA (char); • caracterul ‘.’ (punct) indica absenta descendentului • utilizarea comentariilor este obligatorie.
2. Exista numeroase aplicatii ale TDA arbore. Interesant se dovedeste a fi cazul in care arborele reprezinta o expresie aritmetica. Nodurile frunza constituie operanzii iar celelalte noduri constituie operatorii. Fiecare parcurgere prezentata anterior genereaza cate o modalitate de exprimare a expresiilor aritmetice:
♦ SRD – forma infixata (forma clasica in care operatorii ocupa o pozitie centrala); ♦ RSD – forma prefixata (operatorii preced operanzii); ♦ SDR – forma postfixata (operatorii se afla dupa (post) operanzi).
In contextul arborilor ce reprezinta expresii aritmetice sa se realizeze:
• modificarea optiunii ‘S’ astfel incat expresia sa fie afisata cu paranteze • adaugarea optiunii ‘E’ – evaluarea expresiei reprezentata de arborele binar (si afisarea
rezultatului)
4. Fişiere puse la dispoziţie Pentru realizarea aplicaţiei propuse la acest laborator se vor utiliza următoarele fişiere: � data.h - pentru informaţia utila; � arbori.h - pentru definiţiile si prototipurile specifice tipului arbore;
� arbori.cpp - pentru definiţiile funcţiilor specifice tipului arbore; � demo.cpp - pentru implementarea meniului prezentat anterior;
59
//--------------------------------------------------------
// F i s i e r u l a r b o r i . c
// (c)PSG2002
//--------------------------------------------------------
#include <stdio.h>
#include <alloc.h> #include <conio.h> #include "arbori.h" #define max(a,b) ((a>b)?a:b) #define frunza(x) ((x->stg==NULL) && (x->dr == NULL))
#define prior(x) (x == '*' || x == '/') ARB creare_arbore (DATA x){ ARB a;
if(x == '.') return NULL; a = (ARB)malloc(sizeof(Arbore)); if(a== NULL){ printf("\n Eroare la alocare");
return NULL; } a->nod = x; printf("\n Dati nodul stang pentru %c : ",x); a->stg = creare_arbore(getche());
printf("\n Dati nodul drept pentru %c : ",x); a->dr = creare_arbore(getche()); return a;
}
//--------------------------------------------------------
// F i s i e r u l d a t a . h
// (c)PSG2002
//--------------------------------------------------------
#ifndef _DATA_H_
#define _DATA_H_ typedef unsigned char DATA; #define FORMAT "%c"
#endif
60
5. Teme pentru studiu individual 1. Sa se modifice optiunea ‘S’ astfel incat sa se afiseze doar parantezele necesare 2. Sa se realizeze parcurgerea in latime (‘L’) a arborelui utilizand TDA coada (implementata
prin vectori circulari intr-un laborator anterior)
//--------------------------------------------------------
// F i s i e r u l a r b o r i . h
// (c)PSG2002
//--------------------------------------------------------
#ifndef _ARBORI_H_
#define _ARBORI_H_ #include "data.h" typedef struct arbore{ DATA nod;
struct arbore *stg, *dr; } Arbore, *ARB; ARB creare_arbore (DATA ); void SRD(ARB ,DATA );
void RSD(ARB ); void SDR(ARB ); int inaltime(ARB ); int eval(ARB a);
#endif
61
12. Metoda Greedy 1.Obiectiv
� Aprofundarea metodei Greedy
2.Aspecte teoretice Metoda Greedy se foloseşte în general în situaţia în care este dată o mulţime A şi se cere să se
găsească o submulţime B a sa care să îndeplinească anumite condiţii sau un anumit criteriu de optim. Această metodă nu îşi propune găsirea celor mai bune soluţii ale problemei date ci doar a uneia dintre ele care îndeplineşte criteriul de optimizare ales. Mecanismul general al metodei Greedy este următorul:
1. se iniţializează mulţimea soluţiilor cu mulţimea vidă (B=Φ) 2. se alege un element x din mulţimea A 3. se verifică dacă elementul ales poate fi adăugat la mulţimea soluţiilor , dacă da atunci va
fi adăugat: B=B∪{x} 4. se continuă repetitiv cu pasul 2 până când au fost determinate toate elementele din
mulţimea soluţiilor Există două variante de proceduri pemtru metoda Greedy[1]:
Unde:
• POSIBIL(B,x) este o funcţie booleană care întoarce adevărat dacă B∪{x} poate fi soluţie a problemei
• ADAUG(B,x) adaugă elementul x la mulţimea B • PREL(A,n) prelucrează mulţimea A funcţie de natura problemei ce se doreşte rezolvată
Problemă.
Se cere sa se gaseasca o dispunere optimă a n fişiere cu lungimile L1, L2, ... , Ln pe o bandă magnetică în ipoteza că timpul de citire al unui fişier este proporţional cu lungimea sa, iar pe bandă citirea fişierului k implică şi citirea celor k-1 fişiere precedente. Presupunem o distribuţie uniformă a frecvenţelor de citire a fişierelor.
procedura Greedy_1 (A, n, B) este
B=Φ
pentru i=1,n executa
x = ALEGE(A,n,i)
daca POSIBIL(B,x) atunci
ADAUG(B,X)
@
@
sfarsit
procedura Greedy_2 (A, n, B) este
PREL(A,n)
B=Φ
pentru i=1,n executa
daca POSIBIL(B,ai) atunci
ADAUG(B,ai)
@
@
sfarsit
62
Aranjarea optimă a fişierelor pe o bandă magnetică înseamnă obţinerea unui timp mediu de citire minim. Structura fişierelor pe bandă:
nume fis.1
informatii fis1
EOF nume fis.2
informatii fis2
EOF ..... .....
Date de intrare
L - lungimea benzii magnetice n - numărul de fişiere ce trebuie aranjate Nume_Fişier_1 - un şir de caractere ce conţine numele primului fişier Dimensiune_Fişier_1 - lungimea în octeţi a informaţiilor conţinute în Fişier1 Nume_Fişier_2
Dimensiune_Fişier_2
...
... Nume_Fişier_n
Dimensiune_Fişier_n
Date de ieşire:
Varianta 1: Şirul (N1 L1) (N2 L2) ... (Nm Lm), unde cuplul (Ni Li) reprezintă numele şi dimensiunea fişierului i. Varianta 2: Permutarea p=(p1, p2, ... , pn), a lui (1,2,...,n) pentru care se obţine minimul timpului mediu de citire, elementele pi reprezentând numerele de ordine ale fişierelor din introducerea datelor. Soluţie propusă Se poate demonstra [1] că soluţia optimă se obţine atunci când fişierele sunt sortate în ordinea crescătoare a lungimii lor (lungime nume fişier + lungime informaţie). Se va folosi funcţia Greedy_2 cu următoarele observaţii
1. funcţia PREL(A, n) va crea un vector V (cu Vi=Lungime_nume_fişier_i + Lungime_informaţie_i) şi va sorta crescător vectorul V
2. funcţia POSIBIL(B,ai) va determina dacă lungimea bandei magnetice nu este depăşită (∑Bi + ai ≤ L)
3.Temă de realizat în timpul laboratorului 1. Implementaţi metoda Greedy având în vedere formatul de intrare propus anterior precum şi
prima variantă pentru datele de ieşire. Meniul afişat de program va fi: • C - Citire date de la tastatură • F - Citirea datelor dintr-un fişier al cărui nume este dat de la tastatură • S - Sortarea datelor şi afişarea lor după modelul: Nume fişier, Lungime fişier • G - Aplicarea algoritmului Greedy şi afişarea rezultatelor după modelul propus. • I - Informaţii autor • E - Ieşire program
Se va afişa mesajul Fără soluţie atunci când nici un fişier nu poate fi scris pe banda magnetică.
63
4. Temă pentru studiu individual Implementaţi metoda Greedy şi afişaţi datele folosind cel de-al doilea format de ieşire. Pentru sortarea datelor se va folosi funcţia qsort oferită de mediul de programare Borland
C şi care are prototipul:
Unde: • base - este adresa vectorului de sortat • nelem - numărul de elemente din vector • width - lungimea în octeţi (sizeof) al fiecărui element din vector • fcmp - o funcţie utilizator ce compară două elemente ale vectorului
Exemple de utilizare ale funcţiei qsort:
1. Sortarea crescătoare a unui vector de numere intregi: 2.
#include <stdio.h>
#include <stdlib.h> #include <string.h>
int sortare_crescatoare(const void *a, const void *b)
{
return (*(int *)a - *(int *)b);
}
int v[] = {3,1,5,4,2};
int main(void)
{
int i;
qsort((void*)v,sizeof(v)/sizeof(v[0]),sizeof(v[0]),sortare_crescatoare); for (i = 0; i < 5; i++)
printf("%d\n", v[i]);
return 0;
}
void qsort(
void *base,
size_t nelem,
size_t width,
int (*fcmp)(const void *, const void *));
64
2. Sortarea unui masiv de structuri:
#include <stdio.h>
#include <stdlib.h> #include <string.h>
typedef struct Student{
char Nume[10];
int Nota;
} *STUDENT;
int sortare_descrescatoare(const void *a, const void *b)
{
return ( ((STUDENT)b)->Nota - ((STUDENT)a)->Nota);
}
Student s[] = {{"Marcel",9},{"George",5},{"Mihaela",8}};
int main(void) {
int i;
qsort((void*)s,sizeof(s)/sizeof(s[0]),sizeof(s[0]),sortare_descrescatoare);
for (i = 0; i < 3; i++)
printf("\nNume:%s Nota:%d",s[i].Nume, s[i].Nota);
return 0;
}
65
13. Backtracking recursiv 1.Obiectiv
� Aprofundarea metodei de căutare cu revenire
2.Aspecte teoretice Problemă.
Între insulele unui arhipelag se află n poduri. Un turist îşi propune să viziteze aceste poduri, o singură dată, pornind de la o anumită insulă. Să se afişeze toate posibilităţile de parcurgere a celor n poduri.
Rezolvare Se porneşte analiza problemei prin identificarea celor mai potrivite structuri de date care să
modeleze conţinutul problemei. Date de intrare
n - numărul de poduri ins_start – insula de la care se porneşte pod[n] – un vector de structuri de dimensiune n, care descrie fiecare pod şi are ca membri două numere întregi reprezentând cele două insule (ins1, ins2), pe care le leagă.
Date de ieşire Şirul x1, x2, ...xn, fiecare element xi reprezentând indicele unui pod [0,n-1].
Procedura propusă pentru rezolvarea problemei Pentru a mări viteza de execuţie a procedurii recursive, se va considera că variabila n şi
tablourile x[] şi pod[] sunt globale. La fiecare pas se testează dacă podul i , cu i=0,n-1 , se poate concatena soluţiei parţiale
determinate până în acel moment.
procedura Plimbare(insula_crt, k) este
daca n==k atunci
*) scrie x[0],...,x[n-1]
altfel
pentru i=0,n-1 execută
daca POSIBIL(i,k,insula_crt) atunci
x[k]=i
daca insula_crt==pod[i].ins1 atunci
ins=pod[i].ins2
altfel
ins=pod[i].ins1
@
Plimbare (ins, k+1)
@
@
@
sfarsit
66
După ce se include la pasul k un pod în soluţia parţială, se determină noua ins_crt pentru
pasul următor (acel capăt al podului ales la pasul k ce nu se află pe vechea ins_crt).
Predicatele de extindere a soluţiei la pasul k: POSIBIL (alfa, k, ins_crt)
Vor verifica dacă: - podul alfa nu a fost vizitat (alfa != x[i] pentru i=0,k-1)
- insula curentă este una din extremităţile podului alfa (pod[alfa].ins1 == ins_crt sau pod[alfa].ins2 == ins_crt )
În programul principal rezolvarea problemei va fi declanşată prin apelul:
3. Teme de realizat în timpul laboratorului În timpul lucrării de laborator veţi programa rezolvarea acestei probleme conform
algoritmului prezentat sau al unui alt algoritm la alegerea dumneavoastră. Veţi lua în considerare faptul că datele de intrare vor fi preluate dintr-un fişier text cu n+2 înregistrări, având următorul format:
Observaţie. Toate valorile din fişier sunt întregi.
1. Faceţi ca programul să afişeze mesajul fără soluţie, dacă nu este posibilă găsirea unei soluţii în condiţiile cerute.
2. Rescrieţi programul astfel încât să determine insula de pe care turistul să plece şi să revină pe aceeaşi insulă după ce a parcurs toate podurile o singură dată.
n
ins_start
ins_11 ins_12
ins_21 ins_22
...
ins_n1 ins_n2
execută Plimbare (ins_start, 0)
functie POSIBIL (alfa, k, ins_crt) este
pentru j=0,k-1 executa
daca x[j] == alfa atunci
intoarce FALS
@
@
intoarce pod[alfa].ins1 == ins_crt sau pod[alfa].ins2 == ins_crt
67
4. Teme pentru studiu individual Veţi rezolva cel puţin 2 probleme indicate de cadrul didactic.
1. La o Masă rotundă privind “Creşterea rolului întreprinderilor în finanţarea învăţământului superior” au fost invitate să trimită câte un reprezentant n firme. Este cunoscut faptul că fiecare firmă invitată are una sau mai multe firme concurente printre celelalte invitate. Scrieţi un program care să aşeze participanţii la o masa rotundă astfel încât reprezentanţii a două firme concurente să nu stea alături.
2. Între n oraşe exista o reţea de şosele care unesc două oraşe între ele. Să se determine toate
posibilităţile de alegere a şoselelor, astfel încât sa se ajungă din oraşul s în oraşul d.
3. Un student la filologie poseda n dicţionare bilingve care permit traducerea dintr-o limba i intr-o limba j cu 1<=i, j<=n. Sa se determine toate seturile de dicţionare care îi permit studentului să realizeze o traducere între limba s şi limba d.
4. Pe un deal, într-un punct oarecare, se află o minge. Să se determine toate drumurile pe care
poate coborî mingea astfel încât să ajungă la poalele dealului.
5. Sa se acopere un hol de lungime L cu un număr minim de bucăţi de mochete de lungime li existente în depozit.
6. Se consideră un labirint descris cu ajutorul unui tablou bidimensional. Să se redacteze
programul care determină toate drumurile de ieşire din labirint.
7. Într-un grup de persoane, fiecare persoana se cunoaşte pe sine si cunoaşte eventual alte persoane din grup. Sa se formeze si sa se afişeze toate echipele posibile de persoane astfel încât, pentru o echipă, fiecare din cele n persoane sa fie cunoscută de cel puţin un membru al acelei echipe.
8. Sa se realizeze parcurgerea tabelei de şah de către un cal care pleacă dintr-o poziţie
oarecare, astfel încât sa parcurgă fiecare câmp al tablei o singura dată, mai puţin câmpul de coordonate (i,j).
9. Un dresor trebuie sa scoată m lei si n tigri din arena, astfel încât sa nu scoată doi tigri unul
după altul. Sa se genereze toate posibilităţile de înşiruire a leilor si tigrilor.
10. O caravană formată din n cămile călătoreşte prin deşert, în şir indian. Pentru a sparge monotonia zilelor lungi de drum, beduinul sef se hotărăşte sa schimbe aşezarea cămilelor, astfel încât fiecare cămilă sa nu mai vadă in fata ei aceeaşi cămila de până atunci. Sa se genereze toate posibilităţile de aşezare a cămilelor, cunoscând modul de aşezare din prima zi.
11. Un soldat trebuie sa parcurgă un teren minat pentru a ajunge in propriile linii. Sa se
genereze toate drumurile posibile prin care soldatul ajunge nevătămat la camarazii săi.
68
12. Fie n persoane, n locuri de munca si C(i,j) salariul pretins de persoana i dacă este angajată la locul de munca j. Sa se determine modul optim de angajare a tuturor persoanelor.
13. Dintr-un grup de n persoane, dintre care p femei, trebuie formată o delegaţie de k persoane din care l femei.
Să se precizeze toate delegaţiile care se vor forma.
14. Se consideră un labirint de formă dreptunghiulară având pereţi verticali şi orizontali. Să se găsească drumul cel mai scurt dintre două puncte date.
15. Fiind dat un carosaj dreptunghiular cu m linii şi n coloane, în care anumite poziţii sunt ocupate (interzise), se
cere să se determine toate poziţiile în care poate ajunge un mobil ce pleacă din punctul iniţial (i0, j0), ştiind că el se poate deplasa doar astfel:
• cu o poziţie la dreapta pe aceiaşi linie; • cu o poziţie la stânga pe aceiaşi coloană; • cu o poziţie în sus pe aceiaşi coloană.
16. Care este numărul minim de regi care pot fi aşezaţi pe o tablă de şah, astfel încât să ţină sub ameninţare toate
pătratele neocupate de figuri ?
17. Care este numărul maxim de cai care pot fi aşezaţi pe tabla de şah cu n2 pătrate, astfel încât să nu se ameninţe?
18. Problema bilei. Un teren este reprezentat sub forma unei matrice cu n linii şi n coloane. Elementele (i, j) ce aparţin mulţimii numerelor reale reprezintă cotele diferitelor porţiuni din acest teren. Se presupune că o bilă se găseşte pe o porţiune având o anumită cotă. Se cere să se precizeze toate traseele posibile de a fi urmate de bilă spre a ieşi din teren învecinată cu o cotă strict inferioară cotei terenului pe care se găseşte bila.
19. Se consideră o mulţime formată din n persoane, în care fiecare se cunoaşte pe sine şi eventual, alte persoane.
Să se afişeze grupurile care se pot forma cu aceste persoane, fiecare persoană din grup trebuind să cunoască toate celelalte persoane ale grupului. Relaţia “persoana i cunoaşte persoana j” este dată printr-o matrice
( )C ij i, j = T în care:
C dacă persoana i cunoaş te persoana j
0, în caz contrar
1n
ij =
1,
Observaţii:
• relaţia nu este în mod normal simetrică şi nici tranzitivă, deci Cij=Cji în anumite cazuri, iar din Cij =1 şi Cjk =1 nu rezultă Cik =1
• o persoană nu poate aparţine decât unui singur grup.
20. Se consideră n fete care urmează să se căsătorească într-un mod optim cu n băieţi. Fetele şi băieţii îşi exprimă preferinţele unul faţă de altul prin numere reale din intervalul [0, 1]. Preferinţa fetei i pentru băiatul j este dată de fb[[[[i, j]]]], iar preferinţa băiatului i pentru fata j este dată de bf[[[[i, j]]]]; elementele matricilor fb şi bf sunt numere reale din intervalul [0, 1]. Băiatul ales de fata i are numărul x[[[[i]]]]. Bineînţeles, vectorul x va fi un vector de permutare. Costul căsătoriei fetei i cu băiatul x[[[[i]]]] este fb [[[[i, x[[[[i]]]]]]]] ∗∗∗∗ bf[[[[x [[[[i]]]], i]]]], iar costul general (care trebuie maximizat) este suma după i a acestor valori. Mai mult, se cere ca cele n căsătorii cu i≠j astfel încât fata i să prefere băiatul x[[[[j]]]] băiatului x[[[[i]]]], iar băiatul x[[[[j]]]] să prefere fata i fetei j.
(G. M. 7-8 /1993)
69
14. Backtracking iterativ 1.Obiectiv
� Aprofundarea metodei de cautare cu revenire
2.Aspecte teoretice Exista doua variante de proceduri care realizeaza metoda cautarii cu revenire. Una dintre ele
este cea recursiva, prezentata in laboratorul anterior. Cea de-a doua procedura este iterativa si va fi prezentata in laboratorul de fata. Problema: Daca doreste sa imprumute bani de la prietena sa, Radu trebuie sa ii faca cel putin un cadou. Ea nu face niciodata mai multe imprumuturi decat numarul de cadouri pe care le primeste. Pentru a imprumuta bani de la ea de n ori, trebuie sa ii ofere n cadouri. Sa se determine toate posibilitatile de a oferi cadouri pentru a obtine cele n imprumuturi. Date de intrare: n - numarul de imprumuturi
Date de iesire: toate posibilitatile de oferire a cadourilor si obtinere a imprumuturilor
Exemplu: Se considera notatia C pentru cadou si B pentru imprumut (in engl. borrow).
Pentru n = 2, ordinea poate fi : CBCB sau CCBB, deci in total 2 posibilitati.
Rezolvare: Se considera vectorul solutie organizat ca o structura de date de tip stiva, la care inaltimea maxima este 2*nr_de_imprumuturi_ce_trebuie_efectuate, iar inaltimea curenta a stivei, respectiv nivel, reprezinta indicele componentei care urmeaza sa primeasca o valoare.
procedura ordineCadouri() este
nivel = 1;
init_stiva( nivel );
cat timp ( nivel > 0 ) executa
repeta
areSuccesor = succesor( nivel );
daca areSuccesor == ADEVARAT atunci
esteElementValid = validare( nivel );
cat timp( areSuccesor si !esteElementValid )
daca ( areSuccesor == ADEVARAT) atunci daca ( esteSolutie ( nivel ) ) atunci
afiseazaSolutie();
altfel
nivel = nivel + 1;
init_stiva( nivel );
@
altfel
nivel = nivel - 1;
@
@
sfarsit
70
Functia succesor realizeaza completarea unui nivel al stivei cu toate valorile existente pentru acel nivel, iar functia validare verifica daca este posibila completarea unui nivel al stivei cu valoarea aleasa la un moment dat. Daca s-a completat cu succes un nivel al stivei, se afiseaza solutia (daca este ultimul nivel) sau se trece la completarea urmatorului nivel. In caz contrar, adica nu s-a gasit nici o valoare posibila pentru un anumit nivel al stivei, se revine la alegerea elementului de pe nivelul anterior. Acesti pasi se repeta cat timp nivelul se mentine la o valoare mai mare decat 0. Nivelul va ajunge la valoarea 0 atunci cand nu mai exista succesor pentru primul nivel si se executa nivel = nivel –1.
Functiile succesor si validare pot fi implementate sub forma:
Functia init_stiva (nivel) realizeaza initializarea elementului de pe un nivel al stivei cu un element neutru (care nu se gaseste in domeniul de valori posibile pentru nivelul respectiv) .
Functia esteSolutie verifica daca s-a ajuns la o solutie a problemei. In cazul problemei imprumutului, o solutie se obtine daca au fost completate 2 * n nivele ale stivei cu n imprumuturi si n cadouri.
Pentru marirea vitezei de executie, functiile init_stiva si esteSolutie pot fi realizate ca macrodefinitii.
3. Teme de realizat în timpul laboratorului 1. Rezolvati problema specificata la inceputul laboratorului prin metoda iterativa a cautarii cu
revenire. 2. Folosind metoda prezentata in acest laborator, rezolvati problema din cadrul laboratorului
de backtracking recursiv.
functie esteSolutie( nivel ) este
intoarce nivel == 2 * n
procedura init_stiva( nivel ) este
stiva[nivel] = 0;
sfarsit
functie validare ( nivel ) este
*) daca nr. cadouri este mai mare decat nr. total de cadouri de oferit
*) sau nr. de imprumuturi este mai mare decat nr. de cadouri
*) sau daca nr. de cadouri este egal cu cel de imprumuturi si ultimul
element din vectorul solutie este un cadou
intoarce FALS intoarce ADEVARAT
functie succesor ( nivel ) este daca stiva[nivel] < nr_maxim_de_valori atunci
stiva[ nivel] ++;
intoarce ADEVARAT;
@
intoarce FALS;
71
Bibliografie 1. PENTIUC Ştefan Gheorghe, Structuri de date şi algoritmi fundamentali, Curs, Universitatea “Ştefan cel Mare”, Suceava, 1993;
2. SORIN Tudor, Informatică, Tehnici de programare, Editura L&S, Bucureşti 2000;
3. PENTIUC Ştefan-Gheorghe, TURCU Elena-Cristina, TURCU Corneliu-Octavian, MAHALU George, PETRIŞOR Cristinel, Programarea calculatoarelor, Editura Suceava, 1995.
4. IORGA Valeriu, OPINCARU Cristian, STRATAN Corina, CHIRITA Alexandru, Structuri de
date şi algoritmi. Aplicaţii în C++ folosind STL. Editura Polirom, Bucureşti, 2005.