[c++] implementacje lista/tablica/kopiec

#include "stdafx.h"
#include <iostream>
#include <cmath>
#include <stdlib.h>
#include <fstream>
#include <cstdlib>
#include <ctime>

#define MAX true
#define MIN false



using namespace std;



//-----------------------------LISTA-------------------------------------//
struct liczba
{
    signed int nbr;
    liczba * nastepna; //wskaźnik na nastepny elemnet
    liczba(); // konstruktor
};

liczba::liczba()
{
    nastepna = 0; // konstruktor
}

struct lista
{
    liczba * pierwszy; //wskaznik na poczatek
    void dodaj_element( signed int war );
    void usun_element( signed int nr );
    void wyswietl_elementy();
    void dodaj_poz( signed int war, signed int alt );
    void wyszukaj( signed int war );
    void zaladuj();
    lista();
};

lista::lista()
{
    pierwszy = 0; //konstruktor
}

void lista::wyszukaj( signed int war )
{
    liczba * temp = pierwszy;
    while( temp ) //przewijamy liste
    {
        if( temp->nbr == war )
        {
            cout << "liczba " << war << " wystepuje na liscie";
            break;
        }
        temp = temp->nastepna;
    }
    system( "PAUSE" );
}
void lista::dodaj_poz( signed int war, signed int alt )
{
   
    liczba * nowa = new liczba;
    liczba * temp = pierwszy;
    bool is = true;
   
    while( temp ) //przewijamy liste
    {
       
       
        if( temp->nbr == war )
        {
            is = false;
            break;
        }
       
        temp = temp->nastepna; //ustawiamy wksaźnik na nastepny element
    }
    if( is )
    {
        nowa->nbr = alt;
        nowa->nastepna = pierwszy;
        pierwszy = nowa;
    }
}
void lista::dodaj_element( signed int war )
{
    liczba * nowa = new liczba; //tworzymy nowy element
    nowa->nbr = war; //wypelniamy
    if( pierwszy == 0 ) //sprawdzamy czy pierwszy element jest poczatkiem listy
    {
        pierwszy = nowa; //jesli tak to nowy element jest teraz poczatkiem listy
    }
    else
    {
        liczba * temp = pierwszy; //jesli nie to idziemy na koniec listy
       
        while( temp->nastepna )
        {
            temp = temp->nastepna; //znajdujemy wskaźnik na ostatni element
        }
       
        temp->nastepna = nowa; //onstatni element wskazuje na nasz nowy
        nowa->nastepna = NULL; //ostatni element nie wskazyje na nic.
    }
}

void lista::wyswietl_elementy()
{
    liczba * temp = pierwszy; //wskaźnik na pierwszy element lisy
   
    while( temp ) //przewijamy liste
    {
        cout << temp->nbr << endl;
        temp = temp->nastepna; //ustawiamy wksaźnik na nastepny element
    }
   
}

void lista::usun_element( signed int nr )
{
    liczba * poprzednia = pierwszy;
    if( pierwszy->nbr == nr ) //jesli usuwamy pierwszy element
    {
        liczba * temp = pierwszy;
        pierwszy = temp->nastepna; //początek listy
    }
    else //jesli nie jest to pierwszy element
    {
        int j = 1;
        liczba * temp = pierwszy; //wskaźnik temp bedzie wskaźnikiem na liczbę poprzedzajacą liczbe usuwaną.
       
        while( temp )
        {
            poprzednia = temp;
            if( temp->nbr == nr ) //sprawdzamy czy wskźnik jest już na wymaganej pozycji.
            {
                break;
            }
           
            temp = temp->nastepna;
            ++j;
        }
        //wskaźnik temp wskazuje teraz na liczbe na pozycji n-1
        //nadpisujemy wskźnik liczby n na liczbę n+1
        //w wyniku czego tracimy dostem do elementu n
       
        if( temp->nastepna == 0 ) //sprawdzamy czy nie usuwamy ostatniego elementu listy
        { //wtedy należy wyzerować ostatni wskaźnik.
            poprzednia->nastepna = 0;
        }
        else
        {
            poprzednia->nastepna = temp->nastepna->nastepna;
        }
    }
}

void lista::zaladuj()
{
    ifstream liczby( "liczby.txt" );
    int war;
    if( !liczby )
    {
        cout << "Nie mozna otworzyc pliku";
       
    }
    else
    {
       
        while( !liczby.eof() )
        {
            liczby >> war;
            dodaj_element( war );
           
        }
       
    }
   
    liczby.close();
   
}

void obsluga_list() //funkcja sterująca listami, analogicznie jak w tablicach
{
    lista lis;
   
    ifstream liczby( "liczby.txt" );
    signed int buf;
    signed int war;
    int ch = 0;
    clock_t time;
    clock_t sr( 0 );
    int testy = 0;
    double czas = 0;
   
    while( ch != 6 )
    {
       
        system( "CLS" );
        cout << "wybierz opcje:" << endl;
        cout << "0. ustaw liczbe testów." << endl;
        cout << "1. wczytaj liste z pliku" << endl;
        cout << "2. dodaj element" << endl;
        cout << "3. usun element" << endl;
        cout << "4. wyswietl tablice" << endl;
        cout << "5. wyszukaj" << endl;
        cin >> ch;
       
        switch( ch )
        {
        case 0:
            cout << "ile testów chcesz wykonwac?";
            cin >> testy;
            break;
        case 1:
           
            lis.zaladuj();
            break;
           
        case 2:
            //cout << "podaj wartosc wyszukiwanego elementu:" << endl;
            //cin >>war;
            //cout << "podaj wartosc elementu do zapisu:" << endl;
            //cin >> buf;
           
            for( int i = 0; i < testy; i++ )
            {
                war = rand() % 9999 - 4998;
                buf = rand() % testy;
                lis.zaladuj();
                time = clock();
                lis.dodaj_poz( war, buf );
                time =( clock() - time );
               
                czas = czas + time;
               
            }
           
           
            cout << "czas wykonania:" << czas << " ms" << endl;
            system( "PAUSE" );
            break;
        case 3:
            //cout << "podaj wartosc usuwanego elementu:" << endl;
            //cin >> war;
           
            for( int i = 0; i < testy; i++ )
            {
                war = rand() % 9999 - 4998;
                lis.zaladuj();
                time = clock();
                lis.usun_element( war );
                time =( clock() - time );
               
                czas = czas + time;
            }
           
           
            cout << "czas wykonania:" << czas << " ms" << endl;
            system( "PAUSE" );
            break;
        case 4:
           
            for( int i = 0; i < testy; i++ )
            {
                time = clock();
                lis.wyswietl_elementy();
                time =( clock() - time );
               
                czas = czas + time;
            }
           
           
            cout << "czas wykonania:" << czas << " ms" << endl;
            system( "PAUSE" );
            break;
        case 5:
            //cout << "podaj wartosc elementu do wyszukajnia:" << endl;
            //cin >> buf;
           
            for( int i = 0; i < testy; i++ )
            {
                war = rand() % 9999 - 4998;
                time = clock();
                lis.wyszukaj( buf );
                time =( clock() - time );
               
                czas = czas + time;
               
            }
           
           
            cout << "czas wykonania:" << czas << " ms" << endl;
            system( "PAUSE" );
            break;
        case 6:
            break;
           
           
        }
    }
   
   
   
   
}


//--------------------------------KOPIEC------------------------------------//

struct kopiec
{
    signed int * dane;
    unsigned max_roz, rozmiar;
    bool k;
   
    void zamien( unsigned int index_a, unsigned int index_b )
    {
        unsigned int buff = dane[ index_a ];
        dane[ index_a ] = dane[ index_b ];
        dane[ index_b ] = buff;
    }
   
    bool porownaj( unsigned int index_a, unsigned int index_b )
    {
       
        return k ?( dane[ index_a ] < dane[ index_b ] ? true: false )
            :( dane[ index_a ] > dane[ index_b ] ? true
            : false );
       
    }
   
    bool wstaw( signed int wartosc );
   
    unsigned int usun();
   
    bool odbuduj( unsigned nowy_roz );
   
    void wyswietl();
   
    kopiec( unsigned int max_roz, bool max = true );
   
    void zaladuj( int roz );
};

kopiec::kopiec( unsigned int ssize, bool max )
    : max_roz( ssize )
    , dane( new signed int[ ssize + 2 ] )
    , rozmiar( 0 )
    , k( max )
{
    memset( dane,( max ? 0: 0xFFFFFFFF ), ssize + 2 ); // konstruktor kopca;
    // jako parametr max_size okreslamy poczatkowy maksymany rozmiar kopca,
    // w parametrze max okreslamy warunek kopca czyli czy ma byc max (normalny) czy min kopiec
}

bool kopiec::wstaw( signed int wartosc ) // wstawia element do kopca;
// jako parametr "wartosc" podajemy wartosc nowego elementu
// zwraca true jesli sie udalo i false jesli nie (np kopiec pelny)
{
    if( rozmiar == max_roz )
    {
        return false;
    }
    dane[ rozmiar++ ] = wartosc;
    for( unsigned int i = rozmiar; i != 1; i /= 2 )
    {
        if( porownaj(( i / 2 ) - 1, i - 1 ) )
        {
            zamien(( i / 2 ) - 1, i - 1 );
        }
        else
        {
            break;
        }
    }
    return true;
}

unsigned kopiec::usun() // usowa korzen kopca;
// zwraca wartosc usuwanego korzenia
{
    if( rozmiar == 0 ) return 0;
   
    signed wartosc = dane[ 0 ];
    dane[ 0 ] = dane[ --rozmiar ];
    unsigned i = 1;
    while( i * 2 <= rozmiar )
    {
        register unsigned temp = porownaj(( i * 2 ) - 1, i * 2 ) ?( i * 2 )
            :( i * 2 ) - 1;
       
        if( porownaj( i - 1, temp ) )
        {
            zamien( i - 1, temp );
            i = temp + 1;
        }
        else
        {
            break;
        }
    }
    return wartosc;
}

bool kopiec::odbuduj( unsigned nowy_roz ) // zmienia rozmiar kopca (nowa wartosc moze byc wieksza, moze byc mniejsza);
// jako parametr podajemy nowy maksymalny rozmiar kopca
// zwraca true jesli sie udalo i false jesli nie (np kopiec zajmuje za duzo i nie da sie zmniejszyc jego maksymalnego rozmiaru na podany)
{
    if( nowy_roz < rozmiar )
    {
        return false;
    }
   
    max_roz = nowy_roz;
    signed * temp = new signed[ nowy_roz ];
    memset( temp,( k ? 0: ~0 ), nowy_roz );
    memcpy( temp, dane, rozmiar );
    delete[] dane;
    dane = temp;
    return true;
}

void kopiec::wyswietl() // wyswietla kopiec poszczególne poziomy zostały od siebie odgrodzone.
{
    int cnt = 0;
    int j = 0;
    int sum = 0;
   
    for( unsigned i = 0; i < rozmiar; ++i )
    {
        cout << dane[ i ] << endl;
        if( i == 0 )
        {
            cout << "----------------------" << endl;
            ++j;
        }
        else
        {
           
            if( cnt == pow( 2, j ) )
            {
                cout << "----------------------" << endl;
                ++j;
                cnt = 0;
            }
        }
        ++cnt;
    }
}


void kopiec::zaladuj( int roz )
{
   
    ifstream liczby( "liczby.txt" );
    signed int war;
    delete[] dane;
    dane = new signed int[ roz ];
    if( !liczby )
    {
        cout << "Nie mozna otworzyc pliku";
       
    }
    else
    {
       
        while( !liczby.eof() )
        {
            liczby >> war;
           
            wstaw( war ); //ladujemy do kopca wszystkie liczby
        }
    }
   
    liczby.close();
}


void obsluga_kopca( int roz ) //obsluga kopca analogicznie jak w przypadku tablicy.
{
    srand( time( NULL ) );
   
    kopiec heap( roz );
   
    int ch = 0;
    clock_t time;
    clock_t sr( 0 );
    int testy = 0;
    double czas = 0;
    int war;
    system( "CLS" );
    cout << "wybierz opcje:" << endl;
    cout << "0. ustaw liczbe testów." << endl;
    cout << "1. wczytaj kopiec z pliku" << endl;
    cout << "2. dodaj element" << endl;
    cout << "3. usun element" << endl;
    cout << "4. wyswietl kopiec" << endl;
    cin >> ch;
   
    switch( ch )
    {
    case 0:
        cout << "ile testów chcesz wykonwac?";
        cin >> testy;
        break;
    case 1: //tworzymy/otwieramy plik w1ysciowy
       
        heap.zaladuj( roz );
        break;
       
    case 2:
       
        //cout << "podaj wartisc liczby:" << endl;
        //cin >> war;
       
        for( int i = 0; i < testy; i++ )
        {
           
            war = rand() % 9999 - 4998;
            heap.zaladuj( roz );
            time = clock();
            heap.wstaw( war );
            time =( clock() - time );
            czas = czas + time;
           
        }
       
       
       
       
        cout << "czas wykonania:" << czas << " ms" << endl;
        system( "PAUSE" );
       
        break;
       
    case 3:
       
        for( int i = 0; i < testy; i++ )
        {
            heap.zaladuj( roz );
            time = clock();
           
            heap.usun();
            time =( clock() - time );
           
            czas = czas + time;
        }
       
       
        cout << "czas wykonania:" << czas << " ms" << endl;
        system( "PAUSE" );
       
        break;
    case 4:
       
        for( int i = 0; i < testy; i++ )
        {
            heap.zaladuj( roz );
            time = clock();
            heap.wyswietl();
            time =( clock() - time );
           
            czas = czas + time;
           
        }
       
       
        cout << "czas wykonania:" << czas << " ms" << endl;
        system( "PAUSE" );
       
        break;
    case 5:
        cout << "powrót";
        break;
    }
}




//----------------------TABLICA----------------------//


struct tablica
{
    int roz; //rozmiar tablicy
    signed int * tab; //wskaźnik na tablice
    tablica( int roz ); //konstruktor
   
    void dodaj( int nr, signed int * tab, signed int wartosc );
    void wyswietl( int roz );
    void usun( int nr, signed int * tab );
    void zaladuj( int ilosc );
   
};

tablica::tablica( int roz2 )
{
    tab = new signed int[ roz2 ]; //tworymy tablice o rozmiarze roz2
    roz = roz2; //ustawiamy domyslny rozmiar tablicy na roz2
}
void tablica::dodaj( int nr, signed int * tab, signed int wartosc )
{
   
    signed int * buff = new signed int[ roz ]; //tworzymy bufor do tymczasowgo przechowania tablicy
   
    memcpy(( signed int * ) buff,( signed int * ) tab, roz * sizeof( signed int ) ); //kopiujemy zawartosc tablicy do bufora
   
    ++roz;
   
    delete[] tab; //usuwamy stara tablice
   
    tab = new signed int[ roz ]; //tworzymy nowa tablcie o powiekszonym rozmiarze
   
    int j = 0; //licznik tablicy
    int i = 0; //licznik bufora
    while( i <= roz ) //przewijamy tablice i bufor
    {
        if( i ==( nr - 1 ) ) //przy osiagnieciu zadanego indeksu wprowadzamy nowa wartosc
        {
            tab[ i ] = wartosc;
        }
        else
        {
            tab[ i ] = buff[ j ]; //w pozostalych przypadkach przepisujemy buffor do tablicy
            ++j;
        }
        ++i;
    }
   
    delete[] buff;
   
}

void tablica::usun( int nr, signed int * tab ) //usuwanie analogicznie do dodawania
{
    signed int * buff = new signed int[ roz ];
   
    memcpy(( signed int * ) buff,( signed int * ) tab, roz * sizeof( signed int ) );
   
    --roz;
   
    delete[] tab;
   
    tab = new signed int[ roz ];
   
    int j = 0;
    int i = 0;
    while( i <= roz )
    {
        if( i ==( nr - 1 ) ) //przy osiagnieciu zadanego indeksu pomijamy komórke bufora
        { //którą chcielismy usunąc z tablicy
           
        }
        else
        {
            tab[ j ] = buff[ i ];
            ++j;
        }
        ++i;
    }
   
    delete[] buff;
   
}

void tablica::wyswietl( int roz ) //przewijamy tablice i wyswietlamy
{
    for( int i = 0; i < roz; i++ )
         cout << tab[ i ] << endl;
   
}

void tablica::zaladuj( int ilosc )
{
    ifstream liczby;
    int tmp = 0;
    tab = new signed int[ ilosc ];
   
    liczby.open( "liczby.txt" );
    if( !liczby )
    {
        cout << "Nie mozna otworzyc pliku";
        system( "PAUSE" );
       
    }
    else
    {
       
       
        while( !liczby.eof() )
             liczby >> tab[ tmp++ ]; //ladujemy do tablicy wszystkie liczby
       
    }
   
    liczby.close();
}

void obsluga_tablic( int ilosc ) //funkcja sterująca tablicami
{
    int ch = 0;
    int spc = 0;
   
    tablica tab1( ilosc );
   
   
    double czas;
    clock_t time;
    clock_t sr( 0 );
    int testy = 0;
    int buf;
    signed int war;
    ifstream liczby;
   
   
   
    while( ch != 5 )
    {
       
        system( "CLS" );
        cout << "wybierz opcje:" << endl;
        cout << "0. ustaw liczbe testów." << endl;
        cout << "1. wczytaj tablice z pliku" << endl;
        cout << "2. dodaj element" << endl;
        cout << "3. usun element" << endl;
        cout << "4. wyswietl tablice" << endl;
        cin >> ch;
       
       
        switch( ch )
        {
        case 0:
            cout << "ile testów chcesz wykonwac?";
            cin >> testy;
            break;
           
        case 1: //tworzymy/otwieramy plik w1ysciowy
           
            tab1.zaladuj( ilosc );
            break;
           
        case 2: //losowa wartosc dodajemy w losowym miwjscu tablicy
           
           
            czas = 0;
           
            for( int i = 0; i < testy; i++ )
            {
                buf =( rand() % 9999 ) - 4998;
                war =( rand() % testy );
                tab1.zaladuj( ilosc );
                time = clock();
                tab1.dodaj( buf, tab1.tab, war );
                time =( clock() - time );
               
                czas = czas + time;
               
            }
           
           
            cout << "czas wykonania:" << czas << " ms" << endl;
            system( "PAUSE" );
           
           
           
            ++ilosc;
            break;
           
        case 3:
            //cout << "podaj ideks z którego ma byc usunieta liczba:" << endl;
            //cin >> buf;
           
            czas = 0;
            for( int i = 0; i < testy; i++ ) //usuwamy liczbe z losowo wybranego miejsca.
            {
               
                tab1.zaladuj( ilosc );
                buf =( rand() % 9999 ) - 4998;
                time = clock();
                tab1.usun( buf, tab1.tab );
                time =( clock() - time );
               
                czas = czas + time;
            }
           
           
            cout << "czas wykonania:" << czas / testy << " ms" << endl;
            system( "PAUSE" );
           
            break;
        case 4:
            czas = 0;
            for( int i = 0; i < testy; i++ ) //wyswietlamy tablice.
            {
                tab1.zaladuj( ilosc );
                time = clock();
                tab1.wyswietl( ilosc );
                time =( clock() - time );
               
                czas = czas + time;
            }
           
           
            cout << "czas wykonania:" << czas / testy << " ms" << endl;
            system( "PAUSE" );
           
           
           
            break;
        case 5:
            cout << "powrót";
            break;
        }
    }
   
   
   
}














int _tmain( int argc, _TCHAR * argv[] )
{
    int ilosc;
    int ch = 0;
    signed int liczba;
    ofstream nowyplik;
    srand( time( NULL ) );
    double czas = 0;
    while( ch != 5 )
    {
        cout << "wybierz opcje:" << endl;
        cout << "1. wygeneruj plik." << endl;
        cout << "2. tablica" << endl;
        cout << "3. kopiec" << endl;
        cout << "4. lista" << endl;
        cin >> ch;
       
        switch( ch )
        {
        case 1:
            nowyplik.open( "liczby.txt" ); //tworzymy nowy plik lub nadpisujemy juz istniejący
            cout << "ile liczb chcesz przetestowac?"; //zadaną ilośia losowych liczb/
            cin >> ilosc;
            if( nowyplik.is_open() == 1 )
            {
                cout << "otwarto plik" << endl;
                //nowyplik << ilosc << endl;
                for( int i = 0; i < ilosc; ++i )
                {
                    liczba =( rand() % 9999 ) - 4998;
                    nowyplik << liczba << endl;
                   
                }
            }
            nowyplik.close();
            break;
        case 2: //uruchamiamy operacje na tablicach/
           
            obsluga_tablic( ilosc );
            break;
        case 3: //uruchamiamy operacje na kopcu
            obsluga_kopca( ilosc );
            break;
        case 4: //uruchamiamy operacje na listach
            obsluga_list();
            break;
           
            default:
            break;
        }
    }
   
   
   
   
    system( "PAUSE" );
    return 0;
}