Tema 9: Structuri de date. Tablouri unidimensionaleObiective: Studiind aceast tem vei deveni capabili: - s declarai tipuri de date tablou; - s accesai direct elemenele variabilelor de tip tablou; - s prelucrai secvenial toate elementele tabloului; - s elaborai algoritmi de formare a tablourilor; - s ntroducei de la tastatur elementele tabloului; - s afiai toate elementele tabloului; - s afiai numai elementele tabloului care posed o proprietate dat; - s numrai elementele tabloului care posed o proprietate dat; - s nsumai toate elementele unui tablou cu elemente numerice; - s nsumai elementele tabloului care posed o proprietate dat; - s determinai valoare minim(maxim) a tabloului; - s determinai poziia elementului maxim(minim) a tabloului; - s determinai existena n tablou a elementelor cu o proprietate dat cu o variabil logic; - s determinai existena n tablou a elementelor cu o proprietate dat fr o variabil logic; - s determinai existena n tablou a elementelor cu o proprietate dat folosind algoritmul cutrii cu baraj; - s determinai existena n tablou a elementelor cu o proprietate dat folosind algoritmul cutrii binare; - s determinai poziia primului element care posed o proprietate dat; - s determinai poziia ultimului element care posed o proprietate dat; - s implementai algoritmul cutrii cu baraj; - s deplasai elementele unui tablou la stnga; - s deplasai elementele unui tablou la dreapta; - s rotii elementele unui tablou la stnga; - s rotii elementele unui tablou la dreapta; - s sortai elementele unui tablou prin metoda seleciei; - s sortai elementele unui tablou prin metoda includerii directe; - s sortai elementele unui tablou prin metoda bulelor; - s sortai elementele unui tablou prin metoda ShakerSort; - s elaborai algoritmi de interclasare a tablourilor; - S elaborai algoritmi care utilizeaz date de tip tablou. Pentru a realiza aceste obiectivele este necesar cunoaterea urmtoarelor noiuni i elemente primare: tip de date char; structuri de date; structructura liniar; structura alternativ; structura repetitiv; proceduri; funcii. 1

Structurile de date, spre deosebire de cele simple, sunt combinaii de alte tipuri, definite prin descrierea tipurilor componentelor i prin indicarea unor metode de structurare. Componentele tipurilor structurate pot fi elementare sau structurate. Tablouri unidimensionale n multe probleme apare necesitatea de a lucra cu grupuri de variabile de acelai tip. De exempu, pentru a memora notele studentului de la sesiunea de iarn avem nevoie de un grup de numere naturale, iar pentru a memora temperaturile zilnice ale lunii noiemrie avem nevoie de un grup de numere ntregi. Un grup de elemente de acelai tip se mai numete i tablou unidimensional sau vector. Vectorul reprezint un tip de date structurat. S alctuim algoritmul rezolvrii urmtoarei probleme: s se calculeze suma a 5 numere ntregi. Rezolvare: numer ntregi. Algoritm suma Var N1: integer N2: integer N3: integer N4: integer N5: integer S : integer Begin Readint(n1) Readint(n2) Readint(n3) Readint(n4) Readint(n5) S:=n1+n2+n3+n4+n5 Writeint(s) End. S calculm suma a 30 numere ntregi. Dac rezolvm problema n mod analog, atunci avem nevoie de 30 variabile pentru pstrarea celor 30 numere i algoritmul ar fi mult mai lung. Vom declara 5 variabile de tip integer pentru a memora valorile celor 5

2

Ar fi mai bine ca cele 30 de variabile s nu le declarm separate, dar s declarm un grup format din 30 elemente. Tipul tablou unidimensional (vector) se declar n felul urmtor:

Type< Nume_tip> = array of , unde tip indice poate fi de orice tip scalar, iar tip element de orice tip de date. Exemple: Type vector = array[1..20] of integer numerotate de la 1 la 20. Fie urmtoarea declaraie: Var X: vector Pentru a accesa elementul cu indicele 7 vom specifica X[7], deci componenta cu indicele I se va specifica prin X[I]. Pentru a referi un element al vectorului se folosete urmtoarea specificare < Nume_variabila> [ ] Se pot defini i vectori cu elementele numerotate, de pild, de la 5 la 5: Type vector1=array[-5 ..5] of integer Var X1:vector n acest caz vectorul va avea 10 elemente, numerotate astfel: [-5][-4][-3][-2][-1][0][ 1][ 2][ 3][ 4][ 5] Primul element al acestui vector poate fi accesat astfel X1[-5], al 6-lea X1[0] Fie date urmtoarele declaraii: Type Lucratori=(Ivanov,Petrov,Sidorov) Vector2 = array[lucratori] of real Var Salar : vector2 Vectorul Salar are 3 elemente. Specificarea Salar[Ivanov] ar referi primul element, Salar[Petrov] al 2-lea, iar Salar[Sidorov] al 3-lea. 3 ar nsemna un grup de elemente numere nteregi,

Type Vector=array[a ..z] of real ar nsemna un ir de numere reale, numerotate de la a la z Pentru vectorul Var X: vector Componenta a 3-ia ar fi referit astfel X[c] Am putea defini chiar: Type Vector=array[char] of integer ceea ce ar nsemna un grup de elemente numere ntregi, numerotate de la caracterul cu codul ASCII 0 pn la caracterul cu codul ASCII 255, care este ultimul. Putem folosi i tipul Boolean pentru a defini vectori, de exemplu: Type Vector=array[Boolean] of integer Var Y:vector Vectorul Y are 2 elemente. Primul poate fi referit Y[false], iar ultimul Y[true]. O variabil de tip vector nu poate fi nici citit nici scris n ntregime. De obicei se lucreaz cu componentele vectorului. Cu componentele vectorului se pot face toate operaiile ce se pot face cu orice variabil de acel tip ( afiare, citire, atribuire etc.) Prelucrarea secvenial a elementelor vectorului Deoarece o structur de tip vector cuprinde un numr fixat de elemente de acelai tip, pentru a prelucra toate elementele lui se va folosi un ciclu care se va repeta de n ori, unde nnumrul de componente ale vectorului. For I := to step 1 < Prelucrarea elementului I> Endfor Acest algoritm parcurge elementele vectorului de la primul pn la ultimul. Pentru a parcurge elementele vectorului n ordine invers se va folosi urmtorul algoritm: For I := valoare finala indice to valoare initiala indice step -1 Prelucrarea elementului I

4

Endfor Metode de lucru cu elementele vectorilor Fie urmtoarea declaraie: Type Vector=array[1 .. 10] of integer Var A: Vector Formarea vectorului Citirea vectorului de la tastatur Trebuie s fie formate toate cele 10 componente ale vectorului. Deci folosim algoritmul de prelucrare consecutiv a elementelor, unde n fiecare iteraie se va citi valoarea care se va memoriza n elementul corespunztor. Pentru organizarea ciclului cu contor avem nevoie de variabila ciclului, fie I Var I: Natural Begin For I:=1 to 10 step 1 ReadInt(A[I]) End End Formarea vectorului 1. Sa se formeze un vector elementele cruia sunt primele n numere naturale Var I: Natural Begin For I:=1 to 10 step 1 A[I] := I End End 2. Sa se formeze un vector elementele cruia sunt primele n numere Fibonacci Primul numr Fibonacci este 1.deaceia vom atribui primului element al vectorului A[1] valoara 1. i cel de-al doilea numr Fibonacci este 1 i vom atribui celui de-al doilea element al vectorului valoarea 1. Celelalte numere Fibonacci, ncepnd cu al 3-lea sunt egale cu suma celor doi vecini din stnga, care vor fi referii A[I-1] i A[I-2] respectiv. Var 5

I: natural Begin A[1]:=1 A[2]:=1 For I:=3 to 10 step 1 A[I] := A[I-2}+A[I-1] End End Afiarea unui vector Afiarea poate fi fcut n dou feluri: fiecare element pe un rnd; toate elementele pe un rnd.

Afiarea vectorului - fiecare element pe un rnd Var I: natural Begin For I:=1 to 10 step 1 WriteInt(A[I] ) Writeln End End Afiarea vectorului - toate elementele pe un rnd Var I: natural Begin For I:=1 to 10 step 1 WriteInt(A[I] ) End End Afiarea vectorului - toate elementele pe un rnd n ordine invers Vom folosi algoritmul care parcurge elementele vectorului n ordine invers Var I: natural Begin 6

For I:=10 to 1 step -1 WriteInt(A[I] ) End End Afiarea elementelor pare ale vectorului Elementul current al vectorului A[I] va fi afiat numai dac conine un numr par (A[I] mod 2 =0) Var I: natural Begin For I:=1 to 10 step 1 If A[I] mod 2 =0 WriteInt(A[I] ) End End End Afiarea elementelor impare de pe poziii pare Poziia nseamn indicele I, iar elementul de pe poziia I va fi referit ca A[I]. Pentru a parcurge numai elementele de pe poziii pare vom ncepe cu primul element de pe poziie par al 2-lea, apoi cu pasul 2 var fi parcurse celelalte elemente. Var I: natural Begin For I:=2 to 10 step 2 If A[I] mod 2 #0 then WriteInt(A[I] ) End End End Modificarea valorilor elementelor vectorului 1. De exemplu: s se mreasc cu 5 ultimul element al tabloului Rezolvare: n acest caz vom accesa direct elementul 5 al vetorului folosind referirea A[10] A[10]:=A[10]+5 7

2. Toate elementele negative ale vectorului s fie micorate de 3 ori Rezolvare: Vom parcurge toate elementele vectorului, dar vor fi modificate numai cele negative(A[I]0 then WriteString(Exist) Else WriteString(Nu exist) End Acest algoritm ar putea fi optimizat. Parcurgerea vectorului se va face de la prima poziie, pn la sfrit sau pn s-a gsit primul element cutat. Aceast metod, de comparare succesiv a valorii cutate cu cele din vector, considerate n ordinea apariiei lor, este denumit cutare secvenial. Fie A vectorul cu n elemente n care este cutat valoarea X i Gasit o variabil de tip Boolean, a crei valoare precizeaz dac valoarea cutat a fost gsit sau nu. nainte de a ncepe cutarea, variabila Gsit trebuie iniializat cu valoarea false, deoarece nu s-a gsit valoarea cutat (X). Atunci cnd aceasta este gsit, variabilei Gasit i se atribuie valoarea True i cutarea se termin. Dac ns vectorul nu conine valoarea X, valoarea variabilei Gasit rmne neschimbat(False), cutarea terminndu-se dup analiza ultimului element din vector. Algoritmul care realizeaz cutarea,conform celor expuse anterior, este urmtoarea: 12

Gasit:=false I:=1 While (IX n poziia vecin din dreapta. Astfel, cutnd locul noului element, asigurm i eliberarea lui. Begin I:=n While (I >=1) and (A[I]>X) do A[I+1]:=A[I] I:=I-1 End A[I+1]:=X Operaii cu mulimi, memorate sub form de vectori Mulimile pot fi memorate sub forma unor vectori, fcnd, ns convenia de a nu se repeat elementele n cadrul vectorului. S presupunem c avem doi vectori A (cu n elemente distincte) i B ( cu m elemente distincte). S realizm reuniunea i respective intersecia lor. Reuniunea Pentru reuniune, vom copia n vectorul rezultat (reuniune) toate elementele din A, dup care vom aduga acele elemente din B care nu se gsesc n A. 33 ; contorul elementelor incluse

For I:=1 to n step 1 Reuniune[I]=A[I] End ; se adaug acele elemente di n B care nu sunt n A k:=0 for I:=1 to m step 1 j:=1 while (jn then k:=k+1 reuniune[n+k]:=B[I] end end Intersecie ; se parcurge A, i se pun n Intersec toate acele elemente ce se regsesc n B k:=0 for I:=1 to n step 1 j:=1 gasit:=false while j