Implementarea căutării de date pe diferite structuri de date în C++

1. INTRODUCERE

Obiectivul problemei este de a implementa căutarea de date numerice pe diferite structuri de date: arbore binar de căutare şi coada, vector. Se doreşte minimizarea timpului de lucru.

Aplicaţia a fost realizată în Microsoft Visual Studio 2005. Pentru realizarea proiectului a fost consultată o bibliografie formată din două cărţi şi două siteuri.

2. STRUCTURA PROGRAMULUI

Aplicaţia conţine un meniu care permite utilizatorului să insereze date din fişier sau manual. Pentru teste se pot introduce date de la tastatură sau dintr-un fişier (pe prima linie numărul de elemente iar în continuare elementele).

3. STRUCTURI DE DATE UTILIZATE

Structurile de date utilizate sunt: cozi, vectori, fişiere şi arbori binari de căutare.Sunt declarate structurile de date „nod” şi „nod_coada”.

struct nod_coada{

int val;

nod_coada *prev;

};

struct nod

{int nr_o;

nod *st,*dr; };

Se foloseşte un fişier binar: numere.txt .

S-au utilizat arbori binari de căutare pentru identificarea mai uşoară a informaţiilor despre date. Un arbore binar de căutare este o structură de date numită arbore şi care deţine următoarele proprietăţi:

- Fiecare nod are o valoare

- Ordinea totală este definită pe aceste valori

- Sub-arborele stâng al unui nod oarecare conţine numai valori mai mici decât valoarea nodului respectiv

- Sub-arborele drept al unui nod oarecare deţine numai valorile mai mari sau egale cu nodul respectiv

Avantajul major al arborilor binari de căutare constă în relatarea algoritmilor de sortare şi algoritmilor de căutare care folosesc metoda traversării arborilor în ordine, poate fi foarte eficientă.

Coada este un tip special de listă în care elementele sunt inserate la un capăt şi sunt suprimate la celălalt , se mai numesc liste FIFO ( First In First Out ), adică de tip primul venit, primul servit. Conceptul de coadă apare în orice sistem în care obiectele sunt servite în ordinea sosirii.

Un şir de elemente de acelaşi tip, în care contează ordinea elementelor, se numeşte vector sau tablou unidimensional. Numărul de componente este determinat de numărul de valori ale indicilor, care sunt obligatoriu tipuri ordinale. Poziţia unui element se mai numeşte şi indicele sau rangul elementului, iar elementele se mai numesc şi componente ale vectorului. In vector, elementele sunt accesate direct.