laborator 2-3 SDA Kulev

7/23/2019 laborator 2-3 SDA Kulev

http://slidepdf.com/reader/full/laborator-2-3-sda-kulev 1/18

Ministerul Educaţiei al Republicii Moldova

Universitatea Tehnică a Moldovei

Catedra Informatică Aplicată

RAPORTLucrarea de laborator nr.!"

la disciplina Structuri de date i Algoritmiș

A efectuat#st. $r. %I!&'& E. Cucu

A verificat#dr.( conf.univ.( catedra IA M. )ulev

Chi*inău + ,&-



Lucrare de laborator 2-3

Tema: Implementarea tipului de date abstract Lista simplu inlantuita/ in C

Scopul lucrarii: obtinerea deprinderilor practice de implementare a unui tip de

date abstract 0T1A2 in limba3ul C si anume a T1A Lista simplu inlantuita/

Sarcina de lucru: 1e scris trei fisiere in limba3ul C pentru implementarea 0fisiere2 si utili4area 0& fisier + pro$ram cu functia main 2 a T1A Lista simpluinlantuita/#

&. 5i ierul antet cu e6tensia .h care descrie structura de date a elementuluiș

listei simplu inlantuite 0conform variantei din lucrare precedenta2 iș

prototipurile func iilor care asi$ură opera iunile de prelucrare a listei simpluț ț

inlantuite.

. 5i ier cu e6tensia .cpp 0sau .c2 care contine codurile 0implementarile2ș

tuturor functiilor declarate 7n fi ierul antet.ș

". 5i ierul utili4atorului ! pro$ramul cu func ia main 02 pentru prelucrarea listeiș ț

simplu inlantuite cu afisarea meniului de optiuni pe ecran( si anume#

pentru lucrare de laborator ! crearea listei simplu inlantuite in memoria

dinamica( introducerea informatiei despre elementele listei de la tastatura(

afisarea informatiei despre elementele listei pe ecran( cautarea elementului listeidupa unui cimp informational( modificarea cimpurilor elementului listei(

interschimbarea a elemente listei( determinarea lun$imei listei( sortarea

elementelor listei dupa unui cimp( eliberarea memoriei dinamice alocate pntru

lista( ie ire din pro$ram8ș

pentru lucrare de laborator "! adau$area unui element nou la sfirsitul listei(

adau$area unui element nou la 7nceputul listei( inserarea unui element nou in lista

dupa elementul indicat( inserarea unui element nou in lista inainte elementul

indicat( ster$erea unui element al listei( divi4area listei simplu inlantuite in doualiste separate( unirea a liste simlu inlantuite intr!o sin$ura lista( scrierea

informatiei despre elementele listei in fisier( citirea informatiei despre elementele

listei din fi ier( ie ire din pro$ram.ș ș



Mersul lucrării:

Noţiuni principale din teorie i metode !olosite:

9 listă simplu 7nlănţuită este o colecţie de noduri a*e4ate 7ntr!o ordine liniară 0dar

:U 7n locaţii succesive din memorie ! a*a cum se 7nt;mplă la vectori2. 5iecare nodare cel puţin un pointer către următorul nod( pe care 7l vom numi next . <rimul nodse nume*te head (. Lista se nume*te simplu înlănţuită deoarece fiecare nodmemorea4ă un sin$ur pointer către următorul nod. %pre deosebire de vectori( listanu are o mărime fixă. <oate fi redimensionată prin adău$area sau *ter$ereanodurilor. Un nod este ca un obiect 0item2 care conţine at;t informaţia pe care vreţis!o stocaţi c;t *i legătura către următorul obiect .

1atorită faptului ca elementele listei sunt stocate 7n diferite păr i ale memorieiț

calculatorului sunt u urate anumite opera ii cu lista( de e6emplu inserarea sauș țter$erea unui element al listei nu necesită mi carea celorlalte elemente pentru aș ș

face loc sau pentru a str7n$e lista( a a cum se 7nt7mplă la vectori de e6emplu.ș

E6emplu de ba4ă de date 7n formă de listă simplu 7nlăn uită#ț

t=pedef struct masina>char marca?',@8char model?',@8char ori$ine?',@8int anu8float pret8struct masina ne6t8Bmasina8masina head:ULL8



"isierul masina#$typedef struct masina{char marca[40];char model[40];char origine[40];

int anu;float pret;struct masina *next;}masina;

masina* head=NU;

int create(int n);!unctia de creare a listei simplu inlantuita necirculara"primenste caparamentru #n$ care este numarul de elemente care urmea%a a fialocate&

void read();!uncita de introducere a elementelor in lista simplu inlantuitanecirculara& masina* search(char* s);!unctia de cautare in lista simplu inlantuita necirculara dupaun cimp al structurii&'rimeste ca parametru adresa la string(ulintrodus de utili%ator si returnea%a elementele gasite&void show_search();!uncita de afisare a elementelor cautate cu a)utorul functieisearchchar*+;void show(masina* head);

!untia de afisarea tuturor elemente din lista simplu inlantuitanecirculara a,ind ca paramentru capul listei&void swap(masina* a,masina* b);!unctia de interschim-are a a doua elemente intre ele in listasimplu inlantuita necirculara a,ind . parametri fiind elemente alistei&void sort();!unctia de sortare dupa pretcimp al structurii+&int length();!unctia care determina lungimea listei simplu inlantuitenecirculare returnea%a o ,aloare de tip int care repre%inta

lungimea listei& masina* end();!untia care determina care este ultimul elemente din listasimplu inlantuita necirculara returnind adresa acestui element&void add_after_id(int id);!unctia de adaugare a elementelor dupa indicele indicat deutili%ator in lista simplu inlantuita necirculara"are caparamentru indicele tastat de utili%ator&void add_before_id(int id);!unctia de adaugare a elementelor inainte de indicele indicat deutili%ator in lista simplu inlantuita necirculara"are ca

paramentru indicele tastat de utili%ator&



void add_to_end();!unctia de adaugare a elementelor la sfirsit de lista simpluinlantuita necirculara&void delete_id(int id);!uncita de stergere a unui element din lista simplu inlantuita

necirculara&void devide(int id,masina** head2);!unctia care de,i%ea%a lista in doua liste"are .parametri"primul ste o ,aria-ila de tip int care repre%intaindicile deunde lista ,(a fi de,i%ata"ia al doilea este adresaelementului care urmea%a sa fie capul listei .*/void join(masina** head2);!unctia de unire a listei in doua"are ca parametru adresaelementului care este capul listei .&void modif(int id);!uncita de modificare a unui element din lista simplu inlantuita

necirculara"a,ind ca parametru o ,aria-ila de tip int care esteindicile elementului care urmea%a a fi modificat&void save(char* s);!uncitia de sal,are a informatiei din lista simplu inlantuitanecirculara in fisier"are ca paramentru adresa la string(ulintrodus de utili%ator care repre%inta numele fisierului&void load(char* s);!uncitia de incarcare a informatiei din fisier in lista simpluinltantuita necirculare"are ca paramentru adresa la string(ulintrodus de utili%ator care repre%inta numele fisierului&void freem();

!uncita de eli-erearea memoriei"distrugerea listei simpluinlantuite necirculare&



"isierul !unctii#cppinclude 1stdio&h2include 1stdli-&h2include 1string&h2include 3masina&h3

int createint n+{int i;masina *c"*p;fori=0;i1n;i+{

c=masina*+mallocsi%eofmasina++;ifc == NU+ return 0;ifi == 0+{

head=c;p=c;

}else{

p(2next=c;p=c;

}}p(2next=NU;return 5;

}

,oid read+{

masina *c=head;int i=0;6hilec+{

printf37n****************************************7n7n3+;printf38ntrodu datele masinii 9d7n3"i5+;printf3:arca 3+;scanf39s3"<c(2marca+;printf3:odel 3+;scanf39s3"<c(2model+;printf3riginea 3+;scanf39s3"<c(2origine+;printf3>nul de productie 3+;scanf39d3"<c(2anu+;printf3'retul?+ 3+;scanf39f3"<c(2pret+;c=c(2next;i;

}

}

,oid sho6masina* head+{

masina* c=head;int i=0;6hilec+{

printf3****************************************7n7n3+;printf3@atele masinii 9d7n3"i5+;printf3:arca 9s7n3"c(2marca+;printf3:odel 9s7n3"c(2model+;printf3riginea 9s7n3"c(2origine+;printf3>nul de productie 9d7n3"c(2anu+;printf3'retul?+ 9&.f7n7n3"c(2pret+;printf3>dresa curenta 9p7n3"c+;printf3>dresa elementului urmator 9p7n3"c(2next+;c=c(2next;i;



}}

,oid sho6Asearchchar* s+{

masina *c=head;int i=0"B=0;6hilec+{

ifstrcmps"c(2marca+==0+ CC strcmps"c(2model+==0 + CC strcmps"c(2origine+==0++

{printf3****************************************7n7n3+;printf3@atele masinii 9d7n3"i5+;printf3:arca 9s7n3"c(2marca+;printf3:odel 9s7n3"c(2model+;printf3riginea 9s7n3"c(2origine+;printf3>nul de productie 9d7n3"c(2anu+;printf3'retul?+ 9&.f7n7n3"c(2pret+;B;

}c=c(2next;i;

}ifB==0+

printf3Dlementul nu a fost gasitE7n3+;}

masina* searchchar* s+{

masina* c=head;int B=0;6hilec+{

ifstrcmps"c(2marca+==0 CC strcmps"c(2model+==0 CC strcmps"c(2origine+==0+

{return c;B;

}c=c(2next;

}ifB==0+{

printf3Nu exista asa masiniE7n3+;}return NU;

}

,oid s6apmasina *a"masina *-+{

masina t"*na"*n-;

na=a(2next;n-=-(2next;t=*a;*a=*-;*-=t;a(2next=na;-(2next=n-;

}

int lenght+{


i;c=c(2next;

}return i;



}

,oid sort+{

masina *a"*-;int i"B"l;l=lenght+;fori=0;i1l(5;i+{

a=head;-=a(2next;forB=0;B1l(5(i;B+{

ifa(2pret 1 -(2pret+{

s6apa"-+;}a=a(2next;-=-(2next;

}}

}

masina* end+{

masina* c;c=head;6hilec(2next+{

c=c(2next;}return c;

}

,oid modifint id+{

masina* c=head;int i=0;6hilec+{

ifi5 == id+{

printf3@atele masinii 9d pentru modificare7n3"i5+;printf3:arca 3+;scanf39s3"<c(2marca+;printf3:odel 3+;scanf39s3"<c(2model+;printf3riginea 3+;scanf39s3"<c(2origine+;printf3>nul de productie 3+;scanf39d3"<c(2anu+;printf3'retul?+ 3+;

scanf39f3"<c(2pret+; }c=c(2next;i;

}}

,oid addAafterAidint id+{

masina *c=head"*p;int i=0;6hilec+{

ifi == id(5+{p=c;c=masina*+mallocsi%eofmasina++;

printf37n****************************************7n7n3+;printf38ntrodu datele masinii 9d7n3"i.+;printf3:arca 3+;scanf39s3"<c(2marca+;



printf3:odel 3+;scanf39s3"<c(2model+;printf3riginea 3+;scanf39s3"<c(2origine+;printf3>nul de productie 3+;scanf39d3"<c(2anu+;printf3'retul?+ 3+;scanf39f3"<c(2pret+;c(2next=p(2next;p(2next=c;-reaB;

}i;c=c(2next;

}}

,oid addA-eforeAidint id+{masina *c=head"*p;int i=0;6hilec+{

ifi == id(5+{p=c;

c=masina*+mallocsi%eofmasina++;printf37n****************************************7n7n3+;printf38ntrodu datele masinii 9d7n3"i(.+;printf3:arca 3+;scanf39s3"<c(2marca+;printf3:odel 3+;scanf39s3"<c(2model+;printf3riginea 3+;scanf39s3"<c(2origine+;printf3>nul de productie 3+;scanf39d3"<c(2anu+;printf3'retul?+ 3+;scanf39f3"<c(2pret+;ifp == head+{

c(2next=head;head=c;-reaB;

}else {

c(2next=p;i=0;p=head;6hilep+{

ifi == id(.+{p(2next=c;

}i;p=p(2next;

}

-reaB;}

}i;c=c(2next;

}}

,oid addAtoAend+{masina *c=head"*p;6hilec+{

ifc(2next == NU+{p=c;c=masina*+mallocsi%eofmasina++;printf37n****************************************7n7n3+;

printf38ntrodu datele masinii7n3+;printf3:arca 3+;scanf39s3"<c(2marca+;printf3:odel 3+;



scanf39s3"<c(2model+;printf3riginea 3+;scanf39s3"<c(2origine+;printf3>nul de productie 3+;scanf39d3"<c(2anu+;printf3'retul?+ 3+;scanf39f3"<c(2pret+;p(2next=c;c(2next=NU;-reaB;

}c=c(2next;

}}

,oid deleteAidint id+{masina *c=head"*p;int i=0;6hilec+{

ifi == id(5+{ifc == head+{

head=c(2next;freec+;

-reaB;} else ifc(2next == NU+{

p=head;6hilep+{

ifp(2next == c+{freec+;p(2next=NU;-reaB;

}p=p(2next;

}} else {

p=head;6hilep+{

ifp(2next == c+{p(2next=c(2next;freec+;-reaB;

}p=p(2next;

}}

}i;c=c(2next;

}}

,oid de,ideint id"masina** head.+{


ifi == id(5+{*head.=c(2next;c(2next=NU;-reaB;

}i;c=c(2next;

}}

,oid )oinmasina** head.+{masina *c=head;

6hilec+{ifc(2next == NU+{

c(2next=*head.;-reaB;



}c=c(2next;

}*head.=NU;

}

,oid freem+{

masina *c=head"*p;6hilec+{

p=c;c=c(2next;freep+;ifc == NU+{

-reaB;}

}head=NU;

}

,oid sa,echar* fname+

{masina*c=head;!8D *txt=fopenfname"36t3+;6hilec+{

fprintftxt"39s 9s 9s 9d 9&.f 9p 9p3"c(2marca"c(2model"c(2origine"c(2anu"c(2pret"c"c(2next+;

ifc(2next E= NU+{

fprintftxt" 37n3+;}c=c(2next;

}fclosetxt+;

}

,oid loadchar* fname+{

masina* c"*p;int i=0;!8D *txt=fopenfname"3r3+;ifEtxt+{

printf3!isierul nu existaE7a7n3+;}6hileEfeoftxt++{

c=masina*+mallocsi%eofmasina++;ifc == NU+

{printf37a:emoria nu a fost alocata7n3+;

}ifi == 0+{

head=c;p=c;

}else{

p(2next=c;p=c;

}fscanftxt"39s9s9s9d9f3"<c(2marca"<c(2model"<c(2origine"<c(2anu"<c(

2pret+;

i;}p(2next=NU;fclosetxt+;



}

"isierul main#cppinclude 3functii&cpp3int main+{

masina *a=NU;/*element pentru sortare/interschim-are*/masina *-=NU;/*element pentru sortare/interschim-are*/masina *head.=NU;;/*element cap pentru di,i%are*/

char a5[500];/*string 5 pentru interschim-are*/char -5[500];/*string . pentru interschim-are*/char srch[500];/*string pentru cautare*/char sa,ef[500];/*string pentru sal,are*/char loadf[500];/*string pentru incarcare*/int n;/*numarul de elemente in lista*/int m;/*ciclu infinit meniu principal*/int com5;/*indice pentru meniu pricipal*/int mod;/*indice pentru modificare*/int idAde,ide;/*indice pentru de,i%are*/int idA-efore;/*indice pentru adaugare inaintea indicelui*/int idAafter;/*indice pentru adaugare dupa indice*/int idAdelete;/*indice pentru stergere a elemenentului*/6hile5+{

6hilem+{

m=0;system3cls3+;printf3(((((((((((((((((((((((Freare(((((((((((((((((((((((7n3+;printf35&Frearea listei si introducerea datelor manual7n3+;printf3.&Frearea listei si introduucerea datelor din

fisier7n7n3+;printf3((((((((((((((((((((('reaucrare(((((((((((((((((((((7n3+;printf3G&>fisarea listei7n3+;printf34&Hortarea listei dupa pret7n3+;printf3I&:odificarea unui element7n3+;printf3J&8nterschim-area elementelor7n3+;printf3K&Fautarea unui element7n3+;

printf3L&@e,i%area elementelor in doua liste7n3+;printf3M&Unirea a doua liste cu elemente7n7n3+;printf3(((((((((((((((((>daugare77Htergere((((((((((((((((((7n3+;printf350&>daugarea elementuui inaintea indicelui7n3+;printf355&>daugarea elementului dupa indice7n3+;printf35.&>daugarea elementului la sfirsitul listei7n3+;printf35G&Htergea unui element7n7n3+;printf3((((((((((((((((((((Hal,are778esire((((((((((((((((((7n3+;printf354&Hal,area in fisier7n3+;printf35I&Hal,are si 8esire7n3+;printf3((((((((((((((((((((((((((((((((((((((((((((((((((((7n3+;printf37n@ati comanda7n23+;scanf39d3"<com5+;s6itchcom5+{

case 5system3cls3+;ifhead+{

printf3:emoria este de)a alocata7n3+;system3pause3+;m=5;-reaB;

}system3cls3+;printf3@ati numarul de elemente in lista7n23+;scanf39d3"<n+;createn+;read+;

ifhead+{system3cls3+;printf3ista a fost creata cu

succesE7a7n3+;



system3pause3+;m=5;-reaB;

}case .

system3cls3+; ifhead+

{printf3:emoria este de)a alocata7n3+;system3pause3+;m=5;-reaB;

}printf3@ati numele fisierului7n23+;fflushstdin+;getsloadf+;strcatloadf"3&txt3+;loadloadf+;printf37a8ntroducerea a fost efectuata cu

succesE7n3+;m=5;system3pause3+;-reaB;

case Gsystem3cls3+;ifEhead+{

printf3ista nu existaE7a7n3+;m=5;system3pause3+;-reaB;

}sho6head+;system3pause3+;m=5;-reaB;

case 4system3cls3+;ifEhead+{


}sort+;printf3ista a fost sortata cu succesE7a7n3+;system3pause3+;m=5;-reaB;

case Isystem3cls3+;

ifEhead+{


}sho6head+;printf37n@ati indicile elementului pentru

modificare7n23+;scanf39d3"<mod+;system3cls3+;modifmod+;printf3:odificara a a,ut loc cu succesE7a7n3+;m=5;

system3pause3+;-reaB;

case Jsystem3cls3+;



ifEhead+{


}sho6head+;printf3@ati numele primului element pentru

interschim-are7n23+;fflushstdin+;getsa5+;a=searcha5+;printf3@ati numele primului element pentru

interschim-are7n23+;fflushstdin+;gets-5+;-=search-5+;system3cls3+;s6apa"-+;printf38nterschim-area a a,ut loc cu

succesE7a7n3+;m=5;


case Ksystem3cls3+;ifEhead+{


}printf3@ati denumirea77modelul77originea

pentru cautare7n23+;fflushstdin+;getssrch+;sho6Asearchsrch+;m=5;system3pause3+;-reaB;

case Lsystem3cls3+;ifEhead+{


}sho6head+;

printf37n8ntrodu indicile de unde lista ,(a fidespartita7n3+;

scanf39d3"<idAde,ide+;iflenght+ 2 5 << idAde,ide20 << idAde,ide 1

lenght++{de,ideidAde,ide"<head.+;

}printf3@e,i%area a fost efectuata cu

succesE7a7n3+;sho6head+;sho6head.+;m=5;system3pause3+;-reaB;

case M

system3cls3+;ifEhead+{

printf3ista nu existaE7a7n3+;m=5;




}ifhead.+{)oin<head.+;printf3Unirea a a,ut loc cu succes7n3+;}else {

printf37a:ai intii lista tre-uiedespartitaE7n3+;

}m=5;system3pause3+;-reaB;



}sho6head+;

printf37n8ntrodu numarul de ordine7n3+;scanf39d3"<idA-efore+;ifidA-efore 2 0 << idA-efore 1= lenght+ +{ system3cls3+; addA-eforeAididA-efore+;}else { printf37a>ti introdus un numar iesit din

inter,alul existent7n3+;}system3cls3+;printf3>daugarea s(a efectuat cu

succesE7a7n3+;m=5;system3pause3+;-reaB;



}sho6head+;printf37n8ntrodu numarul de ordine7n3+;scanf39d3"<idAafter+;ifidAafter 2 0 << idAafter 1= lenght+ +{ system3cls3+;

addAafterAididAafter+;}else { printf37a>ti introdus un numar iesit din

inter,alul existent7n3+;}system3cls3+;printf3>daugarea s(a efectuat cu


case 5.system3cls3+;ifEhead+{




}addAtoAend+;system3cls3+;printf3>daugarea s(a efectuat cu


case 5Gsystem3cls3+;ifEhead+{


}sho6head+;printf3@ati indicele elementului pentru

stergere7n3+;scanf39d3"<idAdelete+;deleteAididAdelete+;system3cls3+;printf3Htergerea a fost efectuata cu


case 54system3cls3+;printf3@ati numele fisierului7n23+;fflushstdin+;getssa,ef+;sa,esa,ef+;printf37aHal,area a fost efectuata cu

succesE7n3+;m=5;system3pause3+;-reaB;

case 5Isystem3cls3+;ifhead+{

printf3@ati numele fisierului7n23+;fflushstdin+;getssa,ef+;sa,esa,ef+;printf37aHal,area a fost efectuata cu

succesE7n3+;puts3@ OPD3+;system3pause3+;freem+;exit5+;

}-reaB;

defaultsystem3cls3+;printf3>ti introdus o tasta incorectaE7a7n3+;m=5;system3pause3+;-reaB;

}}

} return 0;}



%onclu&ii:&. Au fost ob inute deprinderi de creare a unei ba4e de date abstracti4ate utili47ndț

lista simplu 7nlăn uită 7n limba3ul C.ț. Au fost ob inute deprinderi de prelucrare a listei simplu 7nlăn uite( adau$areaț ț

elementelor( ster$erea( afisarea( sortarea( cautarea( interschimbarea etc.". Au fost ob inute deprinderi de salvare a datelor 7n fi iere i citirea datelor dinț ș ș

ele.'. Au fost ob inute deprinderi de creare a fi ierelor antet cu e6tensia .h( fi ierelor ț ș ș

cu func ii cu e6tensia .c i includerea lor 7n proiect.ț ș

'iblio(ra!ie:

& Conspectul prele$erilor cursului %tructuri de date i Al$oritmi. Lector dr.(șconf. univ. M. )ulev. Chi inău# UTM( ,&'.ș

https#DDen.iFipedia.or$DiFiDLinFedGlist accesat la ,H.,".,&-

laborator 2-3 SDA Kulev

Documents

Transcript of laborator 2-3 SDA Kulev