//sortowania lista jednokierunkowa i tablice
#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;

//int licznikjebany =0;

struct node{
node *next;
int val;
};
void delfirst(node*&head);

void usunwieksze(node*&head,int odczego)
{
    node*temp=head;
    node*temp2;
 while (temp != NULL && temp->val > odczego) {
        head = temp->next;
        delete temp;
        temp = head;
    }

    while(temp!=NULL)
        {

         while(temp!=NULL &&temp->val <=odczego)
    {
        temp2=temp;
        temp=temp->next;
    }



    if(temp==NULL)
    return;

    temp2->next=temp->next;
    delete temp;
    temp=temp2->next;


        }

}

void add(node *&head,int x)
{
    //licznikjebany++;
    node *temp=new node;
    temp->val=x;
    temp->next=head;
    head=temp;

}


node* split(node *&head)
{
  if(head==NULL)
        return NULL;
  node *temp=head;
  node *temp2=head->next;
  while(temp2!=NULL)
  {
      temp2=temp2->next;
      if(temp2==NULL)
        break;
      temp2=temp2->next;
      temp=temp->next;
  }
    node *dozwrocenia= temp->next;
    temp->next=NULL;
    return dozwrocenia;
}



void show(node *head)
{
    node *temp=head;
    while(temp!=NULL)
    {

        cout<<temp->val<<"-->";
         temp=temp->next;
    }

}
void maxi(node *head)
{
    node *temp=head;
    node *temp2=head;
    while(temp  !=NULL)
    {
        if(temp2->val < temp->val)
        {
         temp2=temp;
        }

        temp=temp->next;


    }
 cout<<temp2->val;
}

void delfirst(node*&head)
{
    if(head!=NULL)
    {
       // licznikjebany--;
        node *temp=head;
        head=temp->next;
        delete temp;


    }
}

void usunx2(node *&head)
{
    if(head!=NULL)
    {
        node *temp=head;
        node *temp2=head->next;
        while(temp!=NULL && temp2!=NULL)
        {
            temp->next=temp2->next;
            delete temp2;
            temp=temp->next;
            if(temp!=NULL)
            {
                temp2=temp->next;
            }


        }
    }

}

int srednia(node*head)
{
    int iloscob=0;
    int dodajemy=0;
    if(head==NULL)
       return 0;
    node *temp=head;
    while(temp)
    {
        dodajemy=dodajemy+temp->val;
        temp=temp->next;
        iloscob++;

    }
    return dodajemy/iloscob;

}
void addxx(node*&head)
{
    node *temp=new node;
    temp=head;
    while(temp!=NULL)
    {
        add(temp->next,temp->val);
        temp=temp->next->next;

    }


}
void addpoval(node*&head)
{
    node *temp=new node;
    temp=head;
    while(temp!=NULL)
    {
        for(int i=0;i<temp->val-1;i++)
        {
        add(temp->next,temp->val);
        temp=temp->next;

        }
        temp=temp->next;
    }


}

void bubblesort(node *&head)
{
    node *i,*j;
    int temp;
    i=head;


    for(i=head;i->next!=NULL;i=i->next)
    {
        for(j=i->next;j!=NULL;j=j->next)

            if(i->val>j->val)
        {
            temp=i->val;
            i->val=j->val;
            j->val=temp;
        }

    }
}

void selectsort(node *&head)
{
    node *i,*j,*dobry;
    int temp;
    i=head;

    for(i=head;i->next!=NULL;i=i->next)
    {
        dobry=i;
        // na poczatku zawsze ustawiamy wartosc minimalna na 1 element
        for(j=i->next;j!=NULL;j=j->next) // ta petla porownuje wartosc minimalna z kolejnymi elementami
        {                                 // jesli znajdzie mniejsza wartosc to ona zostaje nowym minimalem
            if(dobry->val>j->val)
            {
                dobry=j;
            }
        }
        if(dobry->val !=i->val)
        {
            temp=i->val;
            i->val=dobry->val; //jesli wartosc minimalna rozni sie od indeksu pierwszej robimy swapa
            dobry->val=temp;
        }

    }
}

void addtosorted(node *&head,int x)
{
//    licznikjebany++;
    add(head,NULL);
    node *temp2=head;
    while((temp2->next!=NULL) && (temp2->next->val<x))
          {
              temp2=temp2->next;
          } //temp 2 l¹duje zawsze przed wiekszym elementem
          //dodawanie nody
          node *temp = new node;
          temp->val=x;
          temp->next=temp2->next;
          temp2->next=temp;
          delfirst(head);

}
void insertionSort(node *&head)
{
    // Initialize sorted linked list
   node *sorted = NULL;

    // Traverse the given linked list and insert every
    // node to sorted
    node *current = head;
    while (current != NULL)
    {
        // Store next for next iteration
      node *next = current->next;

        // insert current in sorted linked list
        addtosorted(*&sorted, current->val);

        // Update current
        current = next;
    }

    // Update head_ref to point to sorted linked list
    head = sorted;
}
/* Rozbija node z podanej listy na przednie i tylnie po³owy,
	i zwraca je u¿ywaj¹c referencji.
	Jeœli d³ugoœæ jjest niecodzienna to dodatkowy node idzie na przód.
	U¿ywa fast/slow. */
	//source - head z funkcji MergeSort| front i back to a i b
void FrontBackSplit(node* source, node*& frontRef, node*& backRef)
{
	node* fast;
	node* slow;
	slow = source;
	fast = source->next;

	/* fast przechodzi o 2 node a slow o jeden dzieki czemu znajdujemy srodek listy w efektywnym czasie */
	while (fast != NULL) {
		fast = fast->next;
		if (fast != NULL) {
			slow = slow->next;
			fast = fast->next;
		}
	}

	/* Zwracamy wartoœci-slow jest zaraz przed œrodkiem
	wiec aby rozbic na pó³ potrzeba nam slow->next. */
	frontRef = source;
	backRef = slow->next;
	slow->next = NULL;
}

/* funkcja laczaca posorotowane podlsty(lista d³ugoœci 1 jest zawsze posortowana)  */
node* SortedMerge(node* a, node* b)
{
	node* result = NULL;

	/*Jeœli niema 2giego elemetu do scalenia to zwróæ ten jeden istniej¹cy */
	if (a == NULL)
		return (b);
	else if (b == NULL)
		return (a);

	/*Wybiera jeden z elementów i wywo³uje siê rekurencyjnie */
	if (a->val <= b->val) {
		result = a;
		result->next = SortedMerge(a->next, b);
	}
	else {
		result = b;
		result->next = SortedMerge(a, b->next);
	}
	return (result);
}

void MergeSort(node *& head)
{
	node* pom = head;
	node* a;
	node* b;

	/* Jeœli lista ma d³ugoœæ 0 lub 1 to nie ma czego sortowaæ */
	if ((head == NULL) || (head->next == NULL)) {
		return;
	}

	/*Rozbijamy head na 2 podlisty */
	FrontBackSplit(head, a, b);

	/* rozbite podlisty rozbijamy dalej tworz¹c coraz mniejsze listy */
	MergeSort(a);
	MergeSort(b);

	/* z³¹cza posortowane listy ze sob¹ */
	head = SortedMerge(a, b);
}



void wypelnij(int * tab, int rozmiar)
{
	for (int i = 0; i < rozmiar; i++)
	{
		tab[i] = (rand() % 100);
	}
}

void wypisz_tablice(int * tab ,int rozmiar)
{
	for (int i = 0; i < rozmiar; i++)
	{
		cout << "tab [" << i << "] = [" << tab[i] << "]" << endl;
	}
}

void swapp( int &x, int &y){
int tmp =x;
x=y;
y= tmp ;
}
void shiftdown (int*t, int i, int n) {
for ( int l =2* i; l <= n; i=l, l =2* i) {
if(l+1 <= n && t[l +1] > t[l]) ++l;
if(t[i] >= t[l]) return ;
swapp (t[i], t[l]);
}
}
void buildheapBU (int*t, int n) {
for ( long i=n /2; i; --i)
shiftdown (t, i, n);
}

void heap_sort (int*t, int n) {
--t; // teraz indeks 1 pokazuje na element 0 !
buildheapBU (t, n); // shiftdown / shifup
while (n > 1) {
// przenosimy max. elem . na koniec kopca
swapp (t[1] , t[n]);
// przywracamy w³asnosc kopca dla mniejszego kopca
shiftdown (t, 1, --n);
}
}

void sortowanie_grzebieniowe(int * tab,int rozmiar)
{
	int gap = rozmiar;
	int temp;
	bool czy_zamieniono = true;
	while (gap > 1 || czy_zamieniono)		//tak d³ugo a¿ nei dokonamy zamiany albo gap nie bêdzie mniejszy od 1 wykonuj
	{
		gap = (gap/(1.3));
		if (gap == 9 || gap == 10) gap = 11;//s¹ to niekorzystne wartosci ktore obni¿aja wydajnoœæ
		if (gap == 0)
		{
			gap = 1;						// jeœli gap jest równy 0 to ustawiamy go na 1 ¿eby nadal dokonywaæ zamian
		}
		czy_zamieniono = false;				//jesli nie dokonamy zamiany to wyjdziemy z petli
		for (int i = 0; i + gap < rozmiar; i++)
		{
			if (tab[i + gap] < tab[i])
			{
				temp = tab[i];
				tab[i] = tab[i + gap];
				tab[i + gap] = temp;
				czy_zamieniono = true;
			}
		}
	}
}


int main()
{

    node *head=NULL;

    //delfirst(head);
    show(head);
    cout<<endl<<"wywolanie"<<endl;
    add(head,3);
    add(head,1);
    add(head,3);
    add(head,-2);
    add(head,5);
    add(head,10);



   //addpoval(head);
  // usunx2(head);
   show(head);
   cout<<endl;
     //  cout<<"licznik:"<<licznikjebany<<endl;

   MergeSort(head);
   show(head);
   cout<<endl;


	srand(time(NULL));

    //addxx(head);

	int tab[10]={9,8,5,6,2,1,2,5,6,1};
	//wypelnij(tab, a);
    wypisz_tablice(tab, 10);
	//sortowanie_grzebieniowe(tab, a);
	cout<<"po sortowaniu"<<endl;
	heap_sort(tab,10);
	wypisz_tablice(tab, 10);



    return 0;
}
 

//drzewo BST
#include <iostream>

using namespace std;

struct node {
    int val;
    node *P;
    node *L;
    node *O;
};

void insertBST(node *& root, int val) {
    if (root == NULL) {
        root = new node;
        root->val = val;
        root->L = root->P = NULL;
    }
    else {
        if (val < root->val) {
            insertBST(root->L, val);
            root->L->O = root;
        }
        else {
            insertBST(root->P, val);
            root->P->O = root;
        }
    }
}

void inorder(node *root) {
    if (root != NULL) {
        inorder(root->L);
        cout << root->val << " ";
        inorder(root->P);
    }
}

void find_sek(node*root, int val) {
    while (root) {
        if (root->val == val) {
            cout << "element istnieje!" << endl;
            break;
        }
        else if (root->val > val) {
            root = root->L;
        }
        else {
            root = root->P;
        }
    }
}

void find_rek(node*root, int val) {
    if (root != NULL) {
        if (root->val == val) {
            cout << "element istnieje" << endl;
        }
        else if (root->val > val) {
            find_rek(root->L, val);
        }
        else {
            find_rek(root->P, val);
        }
    }
}

node* usun_liscie(node*root) {
    if (root != NULL)
    {
        if (root->L == NULL && root->P == NULL)
        {
            delete root;
            return NULL;
        }
        else
        {
            root->L = usun_liscie(root->L);
            root->P = usun_liscie(root->P);
        }
    }
    return root;
}

node* max(node*root) {
    while (root->P) root = root->P;
    return root;
}

void poprzednik(node*root, node*&pop, int x) {
    if (root == NULL) {
        pop = NULL;
        return;
    }
        if (root->val == x) {
            if (root->L) {
                pop = max(root->L);
            }
        }
        else if (x < root->val) {
            poprzednik(root->L, pop, x);
        }
        else {
            pop = root;
            poprzednik(root->P, pop, x);
        }

}

int main()
{
    node*root = NULL;
    insertBST(root, 15);
    insertBST(root, 6);
    insertBST(root, 18);
    insertBST(root, 17);
    insertBST(root, 20);
    insertBST(root, 3);
    insertBST(root, 7);
    insertBST(root, 2);
    insertBST(root, 4);
    insertBST(root, 13);
    insertBST(root, 9);

    inorder(root);
    cout << endl;
    //usun_liscie(root);
    inorder(root);
    cout << endl;
    node*pop = NULL;
    poprzednik(root, pop, 17);
    cout << "Poprzednik dla wartosci wprowadzonej w funkcji wyzej (17) to: " <<pop->val << endl;

   // system("PAUSE");
    return 0;
}

//kolejki + stos
#include <iostream>

using namespace std;

struct  node{
node*next;
int val;
};


void enqueue(node *&Q,node *&T,int x)
{
    node*p =new node;
    p->val=x;
    p->next=NULL;
    if(Q==NULL)
    Q=p;
    else
    T->next=p;

    T=p;
}

void dequeue(node*&Q,node *&T)
{
    if(Q!=NULL)
    {
        node *p=Q;
        Q=Q->next;
        delete p;
    }
    if(Q==NULL)
    T=NULL;

}
void showfirst(node* Q)
{
      if(Q!=NULL){
    node *p = Q;
    cout<<p->val;

    }
}

void showlast(node* T)
{
      if(T!=NULL){
    node *p = T;
    cout<<p->val;

    }
}

 bool is_Emptyx(node*Q)              //t-next=new node; t=t-next;  t-val=x; t-next=null;   -  to ->
 {
     if(Q==NULL)
     return true;
     else
     return false;
 }



bool is_Empty(node*stos)
{
    if(stos==NULL)
        return true;
    else
        return  false;

}

void push(node*&stos,int x)
{
node *temp=new node;
temp->val=x;
temp->next=stos;
stos=temp;
}

int pop(node*&stos)
{
    if(is_Empty(stos))
    {
        cout<<"stos jest pusty";
    }
    else
        {
   node*temp=stos;
   stos=stos->next;
   return (temp->val);
        }
}

void showtop(node*stos)
{
  if(is_Empty(stos))
    {
        cout<<endl<<"stos jest pusty";
    }
    else
  {
      node *temp=stos;
      cout<<"gora stosu :"<<temp->val;

  }
}

void stosnakolejke(node*&stos,node *&Q,node *&T)
{
    node *temp=stos;
    while(temp!=NULL)
    {
        int x=pop(temp);
        temp=temp->next;
        cout<<"wrzucam na kolejke: "<<x;
        enqueue(Q,T,x);
    }
}

int dequeuex(node*&Q,node *&T)
{
    if(Q!=NULL)
    {
        node *p=Q;
        Q=Q->next;
        return (p->val);
    }
    if(Q==NULL)
    T=NULL;

}

void stosnakolejkecaly(node*&stos,node *&Q,node *&T)
{

    while(stos!=NULL)
    {
        int x=pop(stos);
        //temp=temp->next;
        //cout<<"wrzucam na kolejke: "<<x;
        enqueue(Q,T,x);
    }
}

void kolejkanastoscala(node*&stos,node *&Q,node *&T)
{
    while(Q!=NULL)
    {
        int x=dequeuex(Q,T);
        push(stos,x);
    }

}

void kolejkanastos(node*&stos,node *&Q,node *&T)
{

    while(Q!=NULL)
    {
        int x=dequeuex(Q,T);
        push(stos,x);
        Q=Q->next;

    }


}

void show(node*stos)
{
    node *temp=stos;
    while(temp!=NULL)
    {

        cout<<temp->val<<"->"<<endl;
        temp=temp->next;
    }

}

void showxx(node*Q)
{
    node *temp=Q;
    while(temp!=NULL)
    {

        cout<<temp->val<<"->"<<endl;
        temp=temp->next;
    }

}


int main()
{

    node* Q = NULL;
    node* T=NULL;
    node*stos=NULL;
    push(stos,5);
    push(stos,2);
    push(stos,3);
    push(stos,6);
    push(stos,7);
    push(stos,1);
    show(stos);
    stosnakolejkecaly(stos,Q,T);
    cout<<endl;
    cout<<"1 element kolejki: ";
    showfirst(Q);
    cout<<endl;
    cout<<"ostatni element kolejki: ";
    showlast(T);
    cout<<endl;
    showxx(Q);
    cout<<endl;
    showtop(stos);
    cout<<endl<<"kolejka na stos";

    kolejkanastos(stos,Q,T);
    show(stos);


    return 0;
}