Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "stdafx.h"
- #include <iostream>
- #include <time.h>
- #include <string>
- #include <vector>
- #include <math.h>
- #include <fstream>
- #include <windows.h>
- using namespace std;
- char *t;
- #define N 2000
- LARGE_INTEGER startTimer()
- {
- LARGE_INTEGER start;
- DWORD_PTR oldmask = SetThreadAffinityMask(GetCurrentThread(), 0);
- QueryPerformanceCounter(&start);
- SetThreadAffinityMask(GetCurrentThread(), oldmask);
- return start;
- }
- LARGE_INTEGER endTimer()
- {
- LARGE_INTEGER stop;
- DWORD_PTR oldmask = SetThreadAffinityMask(GetCurrentThread(), 0);
- QueryPerformanceCounter(&stop);
- SetThreadAffinityMask(GetCurrentThread(), oldmask);
- return stop;
- }
- LARGE_INTEGER performanceCountStart, performanceCountEnd;
- //TABLICA
- void usun(int n, int * tab, int rozm)
- {
- performanceCountStart = startTimer();
- for (int i = n; i < rozm; i++) //zaczynamy wykonywanie pętli od elementu ktory chcemy usunac
- {
- tab[i] = tab[i + 1]; //każda wartosc przesuwany na nastepne miejsce - usuwany n-ty element, zsuwamy nastepne
- }
- performanceCountEnd = endTimer();
- LONGLONG tm = performanceCountEnd.QuadPart - performanceCountStart.QuadPart;
- cout << "Usunieto" << endl;
- for (int i = 0; i<rozm -1; i++) //wyswietlamy od tab[i+1] bo w pierwszej linii jest podana ilosc liczb
- printf("tab[%2d]=%4ld\n", i, tab[i+1]); //do rozm-1 bo usunelismy jeden element
- cout << "Czas dzialania: " << tm << " mikrosekund" << endl;
- }
- void dodaj(int m, int * tab, int rozm, int wart)
- {
- int temp, temp2;
- performanceCountStart = startTimer();
- temp2 = wart; //temp2 to element ktory dodajemy
- for (int i = m; i<rozm+1; i++) //pętla od m-miejsce w ktorym dodajemy element, do rozm+1 - zwiekszamy o 1 bo zwiekszamy tablice o 1 element
- {
- temp = temp2; //nadpisujemy kazdy element dalej rozsuwajac tablice od i=m - miejsca w ktorym dodajemy
- temp2 = tab[i];
- tab[i] = temp;
- }
- performanceCountEnd = endTimer();
- LONGLONG tm = performanceCountEnd.QuadPart - performanceCountStart.QuadPart;
- for (int i = 0; i<rozm; i++) //wyswietlanie
- printf("tab[%2d]=%4ld\n", i, tab[i+1]);
- cout << "Czas dzialania: " << tm << " mikrosekund" << endl;
- }
- void wyszukaj(int *tab, int rozm, int wart1)
- {
- int i;
- performanceCountStart = startTimer();
- for (i = 0; i < rozm; i++) //pętla przechodzaca po calej tablicy
- {
- if (tab[i + 1] == wart1) break; //jesli i+1 element tablicy jest rowny szukanej wartosci to wychodzimy z pętli
- //(i+1 bo pierwszy element to ilość elementow w pliku)
- }
- performanceCountEnd = endTimer();
- if (i < rozm) cout << "Znalazles element!\n"; //jesli nie doszlismy do konca to oznacza to tyle ze wczesniej wyszlismy z pętli czyli znalezlismy element
- if (i >= rozm) cout << "Nie znaleziono elementu!\n"; //jesli doszlismy do konca to znaczy ze nie znalezlismy elementu bo wczesniej nie wyszlismy z pętli
- LONGLONG tm = performanceCountEnd.QuadPart - performanceCountStart.QuadPart;
- cout << "Czas dzialania: " << tm << " mikrosekund" << endl;
- }
- //LISTA
- class lista{
- public:
- class ogniwo{
- public:
- ogniwo * next;
- ogniwo * prev;
- int value;
- };
- class inter{
- public:
- ogniwo * wsk;
- inter next(inter it);
- };
- lista (int v); //Konstruktor parametryczny
- void wyswietl(); //Wyswietlanie od przodu
- void wyswietl1(); //Wyswietlanie od tyłu
- inter poczatek; //Konstruktor domyślny ustawiający początek listy
- inter koniec; //Konstruktor domyślny ustawiający koniec listy
- inter begin(); //Metoda zwracająca początek
- inter end(); //Metoda zrwacająca koniec
- inter get(int v); //Metoda zwracająca miejsce, w które chcemy dodać element
- inter szukajl(int v); //Metoda klasy intera szukająca elementu
- inter stworz(inter it, int m); //Metoda klasy intera tworząca liste
- inter usunl(int y); //Metoda klasy intera usuwająca element
- inter dodajl(inter it, int v); //Metoda klasy intera dodająca element
- int size; //Rozmiar listy
- };
- lista::lista(int v) //Konstruktor parametryczny
- { //odczytuje wartosci z pliku tekstowego
- FILE* plik = fopen(t, "rt");
- ogniwo * a = new ogniwo;
- int k;
- for (int ilosc_wczytanych = 0; ilosc_wczytanych<v; ilosc_wczytanych++){
- fscanf(plik, "%ld", &k); //przechodzimy po kazdym elemencie listy ustawiając wskaźniki na niego
- a->next = a; //nadając mu wartosc
- a->prev = a;
- a->value = k;
- poczatek.wsk = a;
- koniec.wsk = a;
- size = 1;
- }
- fclose(plik);
- }
- lista::inter lista::begin(){
- return poczatek;
- }
- void lista::wyswietl(){
- inter it = poczatek; //Wyswietla zwartosc listy dwukierunkowej od przodu
- it.wsk = it.wsk->prev; //pomijamy pierwszą liczbe - ilosc elementow
- for (int i = 0; i < size; i++){
- it.wsk = it.wsk->prev;
- cout << it.wsk->value << " ";
- }
- cout << endl;
- }
- void lista::wyswietl1(){
- inter it = poczatek; //Wyswietla zwartosc listy dwukierunkowej od tylu
- for (int i = 0; i < size; i++){
- cout << it.wsk->value << " ";
- it.wsk = it.wsk->next;
- }
- cout << endl;
- }
- lista::inter lista::get(int v){
- inter it = poczatek; //metoda ustawia wskaźnik w miejsce, w ktore chcemy dodac element
- it.wsk = it.wsk->prev; //pomijamy pierwszą liczbe - ilosc elementow
- for (int i = 0; i <= v; i++){
- it.wsk = it.wsk->prev;
- }
- return it;
- }
- lista::inter lista::dodajl(inter it, int v){
- ogniwo * a = it.wsk; //Wstawia nowy element do listy dwukierunkowej
- ogniwo * b = new ogniwo; //Element ma wartosc v i jest wstawiany za elementem wskazywanym przez wskaźnik it
- ogniwo * c = a->next;
- performanceCountStart = startTimer();
- b->next = c; //wstawia c po b
- b->prev = a; //wstawia a przed b
- b->value = v; //ustawia wartosc dla b
- c->prev = b; //ustawia b przed c
- a->next = b; //ustawia b po a
- if (b->next == b)koniec.wsk = b; //poprawia koniec listy, jezeli dodajemy za ostatnim elementem
- performanceCountEnd = endTimer();
- size++; //dodajemy element wiec zwiekszamy rozmiar
- LONGLONG tm = performanceCountEnd.QuadPart - performanceCountStart.QuadPart;
- cout << "Czas dzialania: " << tm << " mikrosekund" << endl;
- return it;
- }
- lista::inter lista::stworz(inter it, int v){
- int k; //towrzymy liste
- FILE* plik = fopen(t, "rt");
- for (int ilosc_wczytanych = 0; ilosc_wczytanych < v; ilosc_wczytanych++){ //petla od 0 do podanego przez nas rozmiaru
- fscanf(plik, "%ld", &k); //skanujemy plik
- ogniwo * a = it.wsk; //i ustawiamy poszczegolne wartosci w odpowiednie miejsca
- ogniwo * b = new ogniwo;
- ogniwo * c = a->next;
- b->next = c;
- b->prev = a;
- b->value = k;
- c->prev = b;
- a->next = b;
- if (b->next == b)koniec.wsk = b; //poprawia koniec listy, jezeli dodajemy za ostatnim elementem
- }
- size = v; //rozmiar ustawiamy na taki jaki podalismy przy tworzeniu
- return it;
- }
- lista::inter lista::szukajl(int v){
- inter it = poczatek;
- int i = 0;
- performanceCountStart = startTimer();
- for (i = 0; i < size; i++){ //szukamy od poczatku do rozmiaru jaki podalismy wczesniej
- int x = it.wsk->value; //x to wartosc jaka wskazuje wskaźnik
- if (x == v) break; //jesli x rowna sie szukanej wartosci to wychodzimy z pętli
- else { //jesli nie to ustawiamy wskaźnik na nastepny element
- it.wsk = it.wsk->next;
- }
- }
- performanceCountEnd = endTimer();
- if (i < size) cout << "Jest taka liczba" << endl; //jesli h nie jest taki jak rozmiar to oznacza ze wyszlismy wczesniej z petli czyli znalezlismy element
- if (i >= size) cout << "Brak liczby" << endl; //jesli h jest taki jak rozmiar to znaczy ze przeszlismy przez całą pętle - nie znalezlismy elementu
- LONGLONG tm = performanceCountEnd.QuadPart - performanceCountStart.QuadPart;
- cout << "Czas dzialania: " << tm << " mikrosekund" << endl;
- return it;
- }
- lista::inter lista::usunl(int y){
- int i = 0;
- inter it = poczatek; //ustawiamy wskaźnik w miejsce, w ktorym jest element, ktory chcemy usunac
- it.wsk = it.wsk->prev; //pomijamy pierwszą liczbe - ilosc elementow
- for (i = 0; i <= size; i++){
- it.wsk = it.wsk->prev;
- if (it.wsk->value == y) break; //jesli wartosci na ktory wskazuje wskaznik jest taka jaka chcemy usunac to konczy sie dzialanie petli
- }
- if (i < size) {
- ogniwo * b = it.wsk; //b jest elementem ktory chcemy usunac
- ogniwo * a = b->prev; //a jest przed b
- ogniwo * c = b->next; //c jest po a
- performanceCountStart = startTimer();
- a->next = c; //ustawia c po a ---\ USUNIĘCIE B /---
- c->prev = a; //ustawia a przed c ---/ *********** \---
- if (poczatek.wsk == b) poczatek.wsk = c; //popraw poczatek listy, jezeli usuwamy pierwszy element
- if (koniec.wsk == b) koniec.wsk = a; //popraw koniec listy, jezeli usuwamy ostatni element
- delete b; //usunięcie b
- it.wsk = a;
- performanceCountEnd = endTimer();
- size--;
- LONGLONG tm = performanceCountEnd.QuadPart - performanceCountStart.QuadPart;
- cout << "Czas dzialania: " << tm << " mikrosekund" << endl;
- return it;
- }
- else
- cout << "Nie ma takiej liczby!\n";
- }
- //KOPIEC
- class kopiec{
- public:
- int tab[N]; //Tablica
- int size; //Rozmiar
- kopiec(); //Konstruktor bezparametrowy
- void insert_into(int v); //Metoda wstawiająca element o wartosci v do kopca
- void stworz_kopiec(int wielkosc, int tmptab[]); //Metoda tworząca kopiec z elementow pliku
- void usun_korzen(); //Metoda usuwająca korzeń
- void wyswietl(); //Metoda wyświetlająca kopiec
- void szukaj(int poczatek, int liczba); //Metoda wyszukująca element
- };
- kopiec::kopiec(){
- size = 0;
- }
- void kopiec::insert_into(int v){ //Wstawia element o wartosci v do kopca
- performanceCountStart = startTimer();
- tab[size + 1] = v; //zwiekszamy rozmiar o 1 i na ostatnie miejsce wstawiamy podana przez nas wartosc
- int s = size + 1;
- while (s != 1) { //kiedy rozmiar jest rozny (wiekszy) od 1 to sortujemy wszystkie elementy
- if (tab[s / 2] < tab[s]) {
- swap(tab[s / 2], tab[s]);
- s /= 2; //rozmiar dzielimy na 2 - zaczynamy od nowa tylko na innych pozycjach do czasu az s=1
- }
- else
- break;
- }
- size++;
- performanceCountEnd = endTimer();
- LONGLONG tm = performanceCountEnd.QuadPart - performanceCountStart.QuadPart;
- cout << "Czas dzialania: " << tm << " mikrosekund" << endl;
- }
- void kopiec::stworz_kopiec(int wielkosc, int tmptab[]){ //wstawia do tmptab wartosci z pliku
- performanceCountStart = startTimer();
- for (int i = 1; i<wielkosc + 1; i++){ //zaczyna od 1 bo 0 to ilosc elementow
- tab[size + 1] = tmptab[i]; //kazdy element tablicy w klasie kopiec jest teraz równy elementom z tablicy wczytanej z pliku
- int s = size + 1; //zwiekszamy rozmiar
- while (s != 1) { //tak jak wczesniej po kolei zamieniamy kazdy element jezeli poprzedni jest wiekszy od nastepnego -
- if (tab[s / 2] < tab[s]) { //aby spelniac zasade kopca - potomek ma niższa wartosc niz rodzic
- swap(tab[s / 2], tab[s]);
- s /= 2; //dzielimy s przez 2 i zaczynamy jeszcze raz - idziemy ku korzeniowi
- }
- else
- break;
- }
- size++;
- }
- performanceCountEnd = endTimer();
- LONGLONG tm = performanceCountEnd.QuadPart - performanceCountStart.QuadPart;
- cout << "Czas dzialania: " << tm << " mikrosekund" << endl;
- }
- void kopiec::usun_korzen() { //usuwamy korzen
- performanceCountStart = startTimer();
- tab[1] = tab[size]; //ostatni element jest teraz pierwszym - nowym korzeniem
- size--; //zmniejszamy rozmiar - cały proces usuwania korzenia
- int tmp = 1; //dalej sortowanie w dół
- while (tmp * 2 <= size){
- if (tab[tmp] < tab[tmp * 2] || tab[tmp] < tab[tmp * 2 + 1]) { //jesli tab[2] jest mniejszy od tab[4] lub tab[2] jest mniejszy od tab[5]
- if (tab[tmp * 2] > tab[tmp * 2 + 1] || tmp * 2 + 1 > size) { // i jesli tab[4] jest wiekszy od tab[5] lub 5 jest wiekszy od rozmiaru
- swap(tab[tmp], tab[tmp * 2]); //to zamieniamy tab[2] z tab[4]
- tmp = tmp * 2; //i tmp zwiekszyamy dwukrotnie - przechodzimy dalej (niżej)
- }
- else { //jesli tab[4] jest mniejszy od tab[5] i 5 jest mniejszy od rozmiwaru
- swap(tab[tmp], tab[tmp * 2 + 1]); //to zamieniamy tab[2] z tab[5]
- tmp = tmp * 2 + 1; //zwiekszamy tmp
- }
- }
- else
- break;
- }
- performanceCountEnd = endTimer();
- LONGLONG tm = performanceCountEnd.QuadPart - performanceCountStart.QuadPart;
- cout << "\nCzas dzialania: " << tm << " mikrosekund" << endl;
- }
- void kopiec::wyswietl() {
- int h = 1;
- for (int i = 1; i <= size; i++) {
- cout << tab[i] << " ";
- if (i == (pow(2, h) - 1)) { //warunek ktory sprawia ze mozna zobaczyć jak formuje sie drzewo
- cout << endl;
- h++; }
- }
- cout << endl;
- }
- void kopiec::szukaj(int poczatek, int liczba){
- int i;
- performanceCountStart = startTimer();
- if (poczatek <= size){
- for ( i = 1; i <= size; i++) //pętla od pierwszego do ostatniego podanego przez nas elementu
- {
- if (tab[i] == liczba) //jesli ktoryś element jest równy szukanej liczbie to wychodzimy z pętli
- break;
- }
- }
- performanceCountEnd = endTimer();
- if ( i < size + 1) cout << "Znalazles " << liczba << "! " << endl; //jesli przed dojściem pętli do końca wyszliśmy z niej to
- //oznacza wywołanie break'a czyli znalezlismy element
- if ( i >= size + 1) cout << "Nie znalazles " << liczba << "! " << endl; //jesli przeszlismy przez cala petle to oznacza ze nie znalezlismy
- //szukanego elementu - nie wywołał się break
- LONGLONG tm = performanceCountEnd.QuadPart - performanceCountStart.QuadPart;
- cout << "Czas dzialania: " << tm << " mikrosekund" << endl;
- }
- void main()
- {
- MENU:
- system("CLS");
- string nazwa_pliku;
- char a,x;
- cout << "*------------------- MENU -----------------*\n"
- "| Na czym chcesz dzialac? |\n"
- "|------------------------------------------|\n"
- "| |\n"
- "| 1. Tablica - wcisnij 1 |\n"
- "| 2. Lista - wcisnij 2 |\n"
- "| 3. Kopiec - wcisnij 3 |\n"
- "| 4. Zakoncz - wcisnij 4 |\n"
- "| |\n"
- "*------------------------------------------*\n";
- TUTAJ:
- cin >> a;
- switch (a)
- {
- case '1': {
- int rozm, n, m, wart, wart1;
- cout << "Z jakiego pliku chcesz wczytac liczby?\n"
- "Podstawowe pliki: kolejne.txt, losowe.txt\n";
- cin >> nazwa_pliku;
- t = new char[nazwa_pliku.size() + 1];
- strcpy(t, nazwa_pliku.c_str()); //zamieniamy string na char
- cout << "Podaj rozmiar tablicy:" << endl;
- cin >> rozm;
- int * tablica = new int[rozm]; //uzupelniamy tablice tyloma elementami ile chcemy
- printf("Odczyt z pliku i wyswietlenie zawartosci tablicy");
- FILE* plik = fopen(t, "rt"); //otwarcie pliku
- int ilosc_wczytanych = 0; //zmienna ktora pozniej wyswietli nam ile jest liczb w pliku
- while (ilosc_wczytanych - 1 < rozm && fscanf(plik, "%ld", &tablica[ilosc_wczytanych]) == 1) //wczytanie po kolei kazdej liczby
- ilosc_wczytanych++; //zwiększamy zmienna dopoki nie dojdzie do konca
- fclose(plik); //bezpiecznie zamykamy plik
- printf("\nIlosc liczb w pliku = %d\n", tablica[0] );
- for (int i = 0; i < rozm; i++) //wypisanie liczb na ekran
- printf("tab[%2d]=%4ld\n", i, tablica[i + 1]);
- cout << "\nKtory element chcesz usunac? (pierwszy element - tab[ 0]) ";
- cin >> n;
- usun(n, tablica, rozm);
- cout << "\nW ktorym miejscu chcesz dodac element? (pierwszy element - tab[ 0]) ";
- cin >> m;
- cout << "Podaj wartosc elementu: ";
- cin >> wart;
- dodaj(m, tablica, rozm, wart);
- cout << "\nJaka wartosc chcesz wyszukac? ";
- cin >> wart1;
- wyszukaj(tablica, rozm, wart1);
- cout << "\nChcesz wrocic do menu? t/n ";
- cin >> x;
- if (x == 't')
- goto MENU;
- else break;
- }
- case '2': {
- char a;
- int liczba, liczba2, liczba3, liczba4, liczba5;
- cout << "Z jakiego pliku chcesz wczytac liczby?\n"
- "Podstawowe pliki: kolejne.txt, losowe.txt\n";
- cin >> nazwa_pliku;
- t = new char[nazwa_pliku.size() + 1];
- strcpy(t, nazwa_pliku.c_str()); //zamieniamy string na char
- cout << "Wyswietlac od przodu (p) czy od tylu (t) ? ";
- cin >> a;
- cout << "Ile elementow chcesz wczytac: " << endl;
- cin >> liczba;
- lista L(liczba + 1); //tworzymy liste - odczytujemy wartosci z pliku
- lista::inter it = L.begin(); //zwracamy początek listy
- L.stworz(it, liczba); //tworzymy liste - przypisujemy wartości kazdemu elementowi
- if (a == 'p') L.wyswietl(); //wyswietlanie
- else L.wyswietl1();
- cout << "\nPodaj gdzie chcesz wstawic liczbe" << endl;
- cin >> liczba3;
- cout << "Podaj jaka liczbe chcesz wstawic" << endl;
- cin >> liczba4;
- it = L.get(liczba3); //ustawiamy miejsce (liczba3) w ktore chcemy wstawic liczba4
- L.dodajl(it, liczba4); //wstawiamy liczba4
- if (a == 'p') L.wyswietl(); //wyswietlanie
- else L.wyswietl1();
- cout << "\nPodaj jaka liczbe chcesz usunac" << endl;
- cin >> liczba2;
- L.usunl(liczba2); //usuwamy element
- if (a == 'p') L.wyswietl(); //wyswietlanie
- else L.wyswietl1();
- cout << "\nPodaj co chcesz znalezc" << endl;
- cin >> liczba5;
- L.szukajl(liczba5); //metoda wyszukująca element
- cout << "\nChcesz wrocic do menu? t/n ";
- cin >> x;
- if (x == 't')
- goto MENU;
- else break;
- }
- case '3':
- {
- kopiec K; //tworzymy kopiec
- int wielkosc, one, q;
- cout << "Z jakiego pliku chcesz wczytac liczby?\n"
- "Podstawowe pliki: kolejne.txt, losowe.txt\n";
- cin >> nazwa_pliku;
- t = new char[nazwa_pliku.size() + 1];
- strcpy(t, nazwa_pliku.c_str()); //zamieniamy string na char
- cout << "Podaj ile elementow chcesz wprowadzic do kopca: \n";
- cin >> wielkosc;
- int * tmptab = new int[wielkosc + 1]; //tworzymy tymczasową tablice
- FILE* plik = fopen(t, "rt"); //otwarcie pliku
- int ilosc_wczytanych = 0; //zmienna ktora pozniej wyswietli nam ile jest liczb w pliku
- while (ilosc_wczytanych - 1<wielkosc && fscanf(plik, "%ld", &tmptab[ilosc_wczytanych]) == 1)//wczytanie po kolei kazdej liczby
- ilosc_wczytanych++; //zwiększamy zmienna dopoki nie dojdzie do konca
- fclose(plik); //bezpieczne zamknięcie pliku
- printf("\nIlosc odczytanych liczb = %d\n", tmptab[0]);
- K.stworz_kopiec(wielkosc, tmptab); //tworzymy kopiec z elementow odczytanych z pliku
- K.wyswietl(); //wyswietlamy jego zawartosc
- cout << "\nJaka liczbe chcesz dodac? ";
- cin >> one;
- K.insert_into(one);
- K.wyswietl();
- cout << "\nJaka liczbe chcesz wyszukac? ";
- cin >> q;
- K.szukaj(1, q);
- system("pause");
- cout << "\nUsuwa korzen";
- K.usun_korzen();
- K.wyswietl();
- cout << "\nChcesz wrocic do menu? t/n ";
- cin >> x;
- if (x == 't')
- goto MENU;
- else break;
- }
- case '4': cout << "Zakonczyles prace!\n"; break;
- default: cout << "Nie ma takiej opcji! Wpisz jeszcze raz...\n";
- goto TUTAJ;
- }
- system("pause");
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement