Universitatea de Stat din Republica Moldova

Facultatea de Matematica si Informatica

Specialitatea Informatica(E)

Laboratorul 1

la SDMP.

Tema: Algoritmi de cutare.

Scris de:Moraru Igor,grupa I21

Verificat de: VERIF. LECTOR,MAGISTRU IN INFORM BITCOVSCHI LUCIA

Chiinu 2014

Considerai teoretice

Prin structura de date abstract (SDA), sau pur i simplu structura de date

(SD), vom nelege o totalitate de reguli i restricii ce reflect

legturile existente ntre prile separate de date i prin care prile

acestea se unesc ntr-un singur tot.

Sortarea este operaia de aranjare a elementelor unui vector dup valoarea

cheilor, pentru care este definit relaia de ordine i datorit careea se

poate efectua mai rapid cautarea unui element.

Varianta 4.

S se implementeze cteva metode de sortare i s se efectueze sortarea

dup cmpul

cheie din fiierul textual, iar pentru fiecare metod de sortare s se

efectueze

urmtoarele:

- S se analizeze complexitatea teoretic i complexitatea practic a

metodelor de sortare

- De descris algoritmul metodei de sortare pe pai.

LISTINGUL

#include

#include

#include

#include

#include

#include

#include

#include

//*********************abstract class ELEM

using namespace std;

class elem {

public:

virtual int fscanf_el(FILE * f)=0;

virtual int show(const char * opening, const char * ending)=0;

virtual int free()=0;

int operator >(elem &) {

error("Error should overide operator \">\"!\n");

return 0;

}

int operator =\"!\n");

return 0;

}

int operator

id=0;

Nume_A[0]='\0';

Prenume[0]='\0';

Titlu_C[0]='\0';

pret=0.0;

};

void setFirma(char* f) {

strcpy(firma,f);

}

void setModel(char* n) {

strcpy(model, n);

}

void setRam(int a) {

ram=a;

}

void setHdd(int i) {

hdd = i;

}

void setOs(char* i) {

strcpy(os,i);

}

char* getFirma() {

return firma;

}

char* getModel() {

return model;

}

int getRam() {

return ram;

}

int getHdd() {

return hdd;

}

char* getOs() {

return os;

}

int fscanf_el(FILE * f) {

return fscanf(f,"%s%s %i %i %s

%f",firma,model,&ram,&hdd,os,&pret);

}

void virtual show() {

cout

void shell_sort();

void quickSort(int l, int r);

void selectsort(int l, int r);

void insertsort(int i, int j);

void downheap(long k, long n);

void heapsort(int l, int r);

void show();

protected:

void error(char *message) {

cout 0) {

cout

el aux;

for (int i = 0; i < n - 1; i++)

for (j = i; j < n; j++) {

if (strcmp(t[i].getModel(),t[j].getModel())>0)

{

aux = t[i];

t[i] = t[j];

t[j] = aux;

count++;

}

}

cout

}

template

void tabel::insertsort(int l, int r) {

el temp;

for (int i = 1, j; i < r; ++i) //cikl prohodov, i - nomer prohoda

{

temp = t[i];

for (j = i - 1; j >= 0 && t[j] > temp; --j) // poisk mesta elementa

v gotovoy posledovatel'nosti

t[j + 1] = t[j]; // sdvigaem element napravo, poka ne doshli

t[j + 1] = temp; // mesto naydeno, vstavit' element

}

cout 0)

{ j--;}

if (i

quickSort(i, r);

if (l < j)

quickSort(l, j);

}

template

void tabel::downheap(long k, long n) {

// procedura proseivaniya sleduyuschego elementa

// Do procedury: a[k+1]...a[n] - piramida

// Posle: a[k]...a[n] - piramida

el new_elem;

long child;

new_elem = t[k];

while (k t[child])

break;

// inache

t[k] = t[child]; // perenosim syna naverh

k = child;

}

t[k] = new_elem;

}

template

void tabel::heapsort(int l, int r) {

long i;

el temp;

// stroim piramidu

for (i = r / 2 - 1; i >= 0; --i)

downheap(i, r - 1);

// teper' a[0]...a[size-1] piramida

for (i = r - 1; i > 0; --i) {

// menyaem pervyy s poslednim

temp = t[i];

t[i] = t[0];

t[0] = temp;

// vosstanavlivaem piramidal'nost' a[0]...a[i-1]

downheap(0, i - 1);

}

cout

// cout