Lab2 sdmp

download Lab2 sdmp

of 11

  • date post

    11-Jul-2015
  • Category

    Internet

  • view

    47
  • download

    1

Embed Size (px)

Transcript of Lab2 sdmp

  • 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