Aplicatie La Liste Inlantuite

5/17/2018 Aplicatie La Liste Inlantuite - slidepdf.com

http://slidepdf.com/reader/full/aplicatie-la-liste-inlantuite 1/14

Aplicatie la liste inlantuiteAplicatie la liste inlantuiteReprezentarea polinoamelor si operatii cupolinoame



ReprezentareaReprezentareapolinoamelorpolinoamelor

123)( 2 ++= X X X P

5100)( 210002010 +++= X X X X Q

Cum sa le reprezentam daca deexemplu dorim sa scriem unprogram care aduna doua

polinoame?



ReprezentareaReprezentareapolinoamelorpolinoamelorFiecare polinom se poate scrie ca

o suma de termeni.Fiecare termen este bine definit

prin coeficient si gradultermenului3 2P: 2 1 1 0

100 2010 0 2009 0 2008Q: ...

1 1000 0 999 0 3...

1 2 0 1 5 0

123)( 2 ++= X X X P

5100)( 210002010 +++= X X X X Q



ReprezentareaReprezentareapolinoamelorpolinoamelorFiecare termen nenul se va reprezenta

ca un nod cu componentele:Coef GradLink (legatura la urmatorul termen nenul)

Numai termenii nuli vor fi reprezentati. Termenii se vor aseza in lista in ordinea

crescatoare a gradelor.

coef grad link



ReprezentareaReprezentareapolinoamelorpolinoamelor

3 2P: 2 1 1 0 NULL

123)( 2++= X X X P

5100)( 210002010 +++= X X X X Q

Q: 1 10001 25 0 100 2010 NULL



Adunarea polinoamelorAdunarea polinoamelor

53)( X X X X P −+=5432

28)( X X X X X Q ++++=

432

228))(( X X X X X Q P ++++=+



Adunarea polinoamelorAdunarea polinoamelor

n

n X a X a X aa X P ++++= ...)( 2

210

m

m X b X b X bb X Q++++=

...)(

2

210

0≠na

0≠mb

p

p X c X cc X Q P +++=+ ...))(( 10

≤<>

≤<>≤≤+

=

minnmb

nimmna

nmiba

c

i

i

ii

i

sidaca

sidaca

),min(0daca



Algoritmul de adunareAlgoritmul de adunareP, Q date => P = P + QP, Q date => P = P + Q

Plecand de la lista polinomului P,daca va fi necesar,

- vom adauga in lista noduri,- vom sterge noduri si

- vom modifica coeficienti,

astfel incat lista polinomului P vadeveni

lista polinomului P+Q.

In final, lista polinomului Q va



Algoritmul de adunareAlgoritmul de adunareVariabileVariabileFolosim variabilele:

- HEADP pointer la lista lui P

şi

- HEADQ pointer la lista lui Q

Folosim variabilele suplimentare:

- iterP şi iterQ, pointeri ceparcurg listele celor douapolinoame

- preced puncteaza la nodul



Algoritmul de adunare-Algoritmul de adunare-DescriereDescriere

// InitializareiterQ = HEADQ, iterP = HEADP, preced=NULL

while (iterQ ≠NULL and iterP ≠ NULL) // Atat timpcat nici una din liste nu s-a epuizat

i = iterP -> grad, j = iterQ -> grada= iterP -> coef, b= iterQ -> coef

if i = j then // termeni de acelasi grad

if a+b ≠ 0 then // coeficientul sumei

termenilor estenenul

iterP -> coef = a + b

// avanseaz in lista lui Pă

preced= iterP

= -



else // sterge din lista luiP

//termenul curentpreced ->link = iterP ->

linktemp = iterP

iterP= iterP -> link

delete temp.

endif iterQ=iterQ->link //avanseaz in listaă

Q else if j < i then //insereaza un nou nod in

lista P inaintea nodului

curent in P ca o copie a

nodului curent în Q.

Aloca memorie pentru un nodnou.



if temp = NULL then OVERFLOW

STOP

endif

if preced ≠ NULL then

preced ->link=temp

else // se insereaza lainceputul

listei lui P

HEADP=temp

endif preced = temp

temp ->link = iterP

temp ->coef = b

temp ->grad =j



else // avanseaz in lista lui Pă

preced= iterP

iterP = iterP ->link

endif endif Endwhile// Daca lista lui Q nu s-a terminat, dar a lui P s-aterminat se adauga la lista lui P ceea ce a mai

ramasdin lista lui Qwhile (iterQ ≠ NULL )

Aloca memorie pentru un nod nou.temp = pointer la noul nod.

if temp = NULL then OVERLOW; STOPendif



Algoritmul de adunare-Algoritmul de adunare-ultima parteultima parte

preced ->link =temp

temp ->link = NULL

temp ->coef = iterQ -> coef

temp ->grad = iterQ -> grad

// avanseaz ină lista lui Q

iterQ= iterQ->link

preced= temp endwhile

Aplicatie La Liste Inlantuite

Documents

Transcript of Aplicatie La Liste Inlantuite