10.-Lista-stiva-coada-alocare-statica.pdf

Tipuri

structurate

de date

LISTE

STIVE

COZI

Sumar

1. Competene . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2. Prezentare general . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

3. Structura de date de tip list . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

4. Structura de date de tip stiv . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

5. Structura de date de tip coad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

6. Aplicaii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

7. Bibliografie i webografie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

2

1. Competene

Competene generale

identificarea datelor care intervin ntr-o problem i a relaiilor dintre

acestea

elaborarea algoritmilor de rezolvare a problemelor

aplicarea algoritmilor fundamentali n prelucrarea datelor

identificarea conexiunilor dintre informatic i societate

Competene specifice

evidenierea necesitii structurrii datelor

prelucrarea datelor structurate

alegerea structurii de date adecvat rezolvrii unei probleme

elaborarea unui algoritm de rezolvare a unei probleme din aria

currcicular a specialitii

alegerea unui algoritm eficient de rezolvare a unei probleme

identificarea aplicaiilor informaticii n viaa social

elaborarea i implementarea unor algoritmi de rezolvare a unor

probleme cotidiene

3

4

O structur de date este o colecie de elemente asupra creia se pot efectua

anumite operaii.

2. Prezentare general

5

Clasificarea structurilor de date:

1. n funcie de tipul datelor memorate n cadrul structurii, structurile de date se

pot clasifica n:

structuri de date omogene toate datele componente sunt de acelai tip

(de exemplu tabloul);

structuri de date neomogene pot conine date de tipuri diferite (de

exemplu nregistrarea).

2. n funcie de modul de alocare a memoriei interne, structurile de date sunt

de dou tipuri:

structuri de date statice ocup o zon de memorie de dimensiune fix,

alocat pe ntreaga durat a execuiei blocului n care este declarat (de

exemplu tabloul, fiierul, lista, stiva, coada);

structuri de date dinamice ocup o zon de memorie de dimensiune

variabil, alocat pe parcursul execuiei programului, la cererea explicit a

programatorului (de exemplu lista, stiva, coada).

Prezentare general

6

- utilizarea listelor se impune ori de cte ori este necesar organizarea ntr-

o form secvenial a unui ansamblu de informaii;

3. Structura de date de tip list

Lista este o structur de date de tip secvenial, constituit dintr-o

succesiune de elemente de acelai tip. Fiecare element din list are un

succesor (cu excepia ultimului element al listei) i un predecesor (cu

excepia primului element din list).

7

Operaii elementare care se pot efectua asupra unei liste:

crearea unei liste vide;

inserarea unui element n list;

eliminarea unui element din list;

accesarea unui element din list;

afiarea elementelor unei liste.

Exemplu

14, 2, 6, 77

LISTA

Structura de date de tip list

14 2 6 77

8

Reprezentarea listelor

Cel mai siplu mod de a implementa o list const n memorarea

elementelor sale ntr-un vector.

Declararea listei: [];

Exemplu

int LISTA[11];


9

1. Crearea unei liste vide - se iniializeaz numrul de elemente din list cu 0;

Exemplu

int n=0;


10

2. Inserarea unui element n list

- se deplaseaz cu o poziie la dreapta toate elementele din list;

- se insereaz elementul;

- crete cu o unitate numrul de elemente ale listei;

Exemplu

for(i=n;i>=poz;i--)

LISTA[i+1]=LISTA[i];

LISTA[poz]=e;

n++;

Exerciiu

- inserarea unui element la nceputul listei;

- inserarea unui element la sfritul listei.


11

3. Eliminarea unui element din list

- se deplaseaz cu o poziie la stnga toate elementele din list, ncepnd

cu poziia elementului care se elimin;

- scade cu o unitate numrul de elemente ale listei;

Exemplu

e=LISTA[poz];

for(i=poz;i

12

4. Accesarea unui element din list

- se memoreaz un element al listei ntr-o variabil;

Exemplu

e=LISTA[poz];


13

5. Afiarea elementelor din list

- se parcurge lista element cu element;

Exemplu

for(i=1;i

14

- singurul element din stiv la care avem acces direct este cel de la vrful

stivei;

- trebuie cunoscut n permanen vrful stivei;

- stiva este utilizat atunci cnd programul trebuie s amne execuia unor

operaii, pentru a le executa ulterior, n ordinea invers apariiei lor; - stiva funcioneaz dup principiul LIFO (Last In First Out);

4. Structura de date de tip stiv

Stiva este un tip particular de list, pentru care att operaia de inserare

a unui element n structur, ct i operaia de extragere a unui element

se realizeaz la un singur capt, denumit vrful stivei.

15

Operaii elementare care se pot efectua asupra unei stive:

crearea unei stive vide; nserarea unui element n stiv (PUSH);

extragerea unui element din stiv (POP);

accesarea elementului de la vrful stivei (TOP).

Exemplu

14, 2, 6, 77

Structura de date de tip stiv

77

6

2

14

vrful

stivei

(TOP)

PUSH POP

STIVA

16

Reprezentarea stivelor

Cel mai siplu mod de a implementa o stiv const n memorarea


Declararea stivei: [];

Exemplu

int STIVA[11];


17

1. Crearea unei stive vide - se iniializeaz numrul de elemente din stiv cu 0;

Exemplu

int vrf=0;


18

2. Inserarea unui element n stiv

- se verific dac stiva nu este plin;

- se mrete vrful stivei;

- se plaseaz la vrf noul element;

Exemplu

if(varf==10)

cout

19

3. Extragerea unui element din stiv

- se verific dac stiva nu este vid;

- se reine elementul din vrful stivei ntr-o variabil;

- se micoreaz cu o unitate vrful stivei;

Exemplu

if(varf==0)

cout

20

4. Accesarea elementului din vrful stivei

- se memoreaz elementul din vrful stivei ntr-o variabil;

Exemplu

e=STIVA[varf];


21

- singurul element din coad la care avem acces direct este cel de la

nceput;

- trebuie cunoscut n permanen nceputul cozii i sfritul cozii;

- coada este utilizat atunci cnd informaiile trebuie prelucrate exact n

ordinea n care au sosit i ele sunt reinute n coad pn cnd pot fi

prelucrate; - coada funcioneaz dup principiul FIFO (First In First Out);

5. Structura de date de tip coad

Coada este un tip particular de list, pentru care operaia de inserare a

unui element se realizeaz la un capt, iar operaia de extragere a unui

element se realizeaz la cellalt capt.

22

Operaii elementare care se pot efectua asupra unei cozi:

crearea unei cozi vide;

nserarea unui element n coad;

eliminarea unui element din coad;

accesarea unui element din coad.

Exemplu 14, 2, 6, 77

Structura de date de tip coad

14 2 6 14 77 out in

COADA

23

Reprezentarea cozilor

Cel mai simplu mod de a implementa o coad const n memorarea


Declararea cozii: [];

Exemplu

int COADA[11];


24

1. Crearea unei cozi vide - se iniializeaz numrul de elemente din coad cu 0, pentru aceasta se

iniializeaz variabilele nceput i sfrit;

Exemplu

int nceput=1, sfarsit=0;


25

2. Inserarea unui element n coad

- se verific dac coada nu este plin;

- se mrete sfritul cozii cu o unitate;

- se plaseaz la sfrit noul element;

Exemplu

if(sfarsit==10)

cout

26

3. Eliminarea unui element din coad

- se verific dac coada nu este vid;

- se reine elementul de la nceputul cozii ntr-o variabil;

- se mrete cu o unitate nceputul cozii;

Exemplu

if(inceptu>sfarsit)

cout

27

4. Accesarea unui element din coad

- se memoreaz elementul de la nceputul cozii ntr-o variabil;

Exemplu

e=COADA[inceptu];


28

Fi de lucru

ntrebri liste, stive, cozi

Aplicaii liste, stive, cozi

6. Aplicaii

29

1. Cerchez E., erban M., Informatic. Manual pentru clasa a X-a, Editura

Polirom, Iai, 2000

2. Mateescu G, Moraru P., Informatica. Manual pentru calsa a X, Editura

Donaris, Sibiu, 2006

3. Popescu C., Culegere de probleme de informatic, Editura Donaris-

Info, Sibiu, 2002

4. Ministerul Educaiei, Cercetrii i Tineretului, Centrul Naional pentru

Curriculum i Evaluare n nvmntul Preuniversitar, Proba scris la

informatic. Examenul de bacalaureat Variante (1-100) , Bucureti

2008

5. http://ro.wikipedia.org/wiki/Lista_(structur%C4%83_de_date)

6. http://ro.wikipedia.org/wiki/Stiv%C4%83_(structur%C4%83_de_date)

7. http://en.wikipedia.org/wiki/Stack_(abstract_data_type)

7. Bibliografie i webografie

http://ro.wikipedia.org/wiki/Lista_(structur%C4%83_de_date)http://ro.wikipedia.org/wiki/Lista_(structur%C4%83_de_date)http://ro.wikipedia.org/wiki/Lista_(structur%C4%83_de_date)http://ro.wikipedia.org/wiki/Lista_(structur%C4%83_de_date)http://ro.wikipedia.org/wiki/Lista_(structur%C4%83_de_date)http://ro.wikipedia.org/wiki/Lista_(structur%C4%83_de_date)http://ro.wikipedia.org/wiki/Lista_(structur%C4%83_de_date)http://ro.wikipedia.org/wiki/Lista_(structur%C4%83_de_date)http://ro.wikipedia.org/wiki/Lista_(structur%C4%83_de_date)http://ro.wikipedia.org/wiki/Lista_(structur%C4%83_de_date)http://ro.wikipedia.org/wiki/Lista_(structur%C4%83_de_date)http://ro.wikipedia.org/wiki/Lista_(structur%C4%83_de_date)http://ro.wikipedia.org/wiki/Lista_(structur%C4%83_de_date)http://ro.wikipedia.org/wiki/Stiv%C4%83_(structur%C4%83_de_date)http://ro.wikipedia.org/wiki/Stiv%C4%83_(structur%C4%83_de_date)http://ro.wikipedia.org/wiki/Stiv%C4%83_(structur%C4%83_de_date)http://ro.wikipedia.org/wiki/Stiv%C4%83_(structur%C4%83_de_date)http://ro.wikipedia.org/wiki/Stiv%C4%83_(structur%C4%83_de_date)http://ro.wikipedia.org/wiki/Stiv%C4%83_(structur%C4%83_de_date)http://ro.wikipedia.org/wiki/Stiv%C4%83_(structur%C4%83_de_date)http://ro.wikipedia.org/wiki/Stiv%C4%83_(structur%C4%83_de_date)http://ro.wikipedia.org/wiki/Stiv%C4%83_(structur%C4%83_de_date)http://ro.wikipedia.org/wiki/Stiv%C4%83_(structur%C4%83_de_date)http://ro.wikipedia.org/wiki/Stiv%C4%83_(structur%C4%83_de_date)http://ro.wikipedia.org/wiki/Stiv%C4%83_(structur%C4%83_de_date)http://ro.wikipedia.org/wiki/Stiv%C4%83_(structur%C4%83_de_date)http://ro.wikipedia.org/wiki/Stiv%C4%83_(structur%C4%83_de_date)http://ro.wikipedia.org/wiki/Stiv%C4%83_(structur%C4%83_de_date)http://ro.wikipedia.org/wiki/Stiv%C4%83_(structur%C4%83_de_date)http://ro.wikipedia.org/wiki/Stiv%C4%83_(structur%C4%83_de_date)http://ro.wikipedia.org/wiki/Stiv%C4%83_(structur%C4%83_de_date)http://ro.wikipedia.org/wiki/Stiv%C4%83_(structur%C4%83_de_date)http://en.wikipedia.org/wiki/Stack_(abstract_data_type)http://en.wikipedia.org/wiki/Stack_(abstract_data_type)http://en.wikipedia.org/wiki/Stack_(abstract_data_type)http://en.wikipedia.org/wiki/Stack_(abstract_data_type)http://en.wikipedia.org/wiki/Stack_(abstract_data_type)http://en.wikipedia.org/wiki/Stack_(abstract_data_type)http://en.wikipedia.org/wiki/Stack_(abstract_data_type)

10.-Lista-stiva-coada-alocare-statica.pdf

Documents

Transcript of 10.-Lista-stiva-coada-alocare-statica.pdf