Lab2 sdmp
date post
11-Jul-2015Category
Internet
view
48download
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