Listy Sortowania Drzewka

LaborkiAiSD.cpp

#include <iostream>
#include <stdlib.h>
#include <time.h>

using namespace std;
int n = 0;
struct node {
	int val;
	node * next;
};
struct treesome{
	int val;
	treesome * up;
	treesome * left;
	treesome * right;
};

struct nodeGraph{
	int waga;
	int	to;
	nodeGraph * next;

};

void Add(node *&head, int val)
{
	node * tmp = new node;
	tmp->val = val;
	tmp->next = head;
	head = tmp;
}
void DeleteLast(node *& head)
{
	node * elementToDelete = head;
	head = elementToDelete->next;
	delete(elementToDelete);
}

void PokaSowe(node * p) {
	while (p) {
		cout << p->val << " -> ";
		p = p->next;
	}
	cout << endl;
}

node * Swap(node * head){
	node * p = head->next;
	head->next = p->next;
	p->next = head;

	return p;
}


//usuń pierwszy elemenet o wartości X z listy head1 i dodaj na koniec listy h2
void unplug(node *& head1, node *& head2, int X){
	node * p1 = head1;
	node * p2 = head2;
	node * bp1 = NULL;
	//bp1->next = head1;
	while (p1){		
		if (p1->val == X){		
			if (p1 == head1){
				head1 = head1->next;
			}
			else{
				bp1->next = p1->next;
			}
			p1->next = NULL;
			if (p2){
				while (p2->next)p2 = p2->next;
				p2->next = p1;
			}
			else{			
				p2 = p1;
			}
		}		
		bp1 = p1;
		p1 = p1->next;
	}
	
}





void BabelekKuwra(node * & head){
	node * p = head;		//wskaźnik do heada -jego zmieniami i wogole
	node * p2 = head;		//wskaźnik do zewnetrzego while - licznik
	node * beforep = NULL;

	while (p2->next){
		while (p->next){

			if (p->val > p->next->val){

				if (beforep == NULL){	//jezeli poprzednik jest null to specjalna zamiana gdzie ehad tez zmieniamy

					head = Swap(p);
					beforep = head;
					p = head->next;
				}
				else{
					//jak nie jest 1 element to to
					beforep->next = Swap(p);
					p = beforep->next->next;
					beforep = beforep->next;
				}
			}
			else{

				beforep = p;
				p = p->next;
			}
		}
		p2 = p2->next;
		p = head;
		beforep = NULL;
	}
}

int GetListSize(node * & head){
	node * p = head;
	int size = 0;
	while (p){
		size++;
		p = p->next;
	}
	return size;
}


void swapHeadVal(node*&list, int val) {
	// val = 3 // 1->2->3->4 => 3->2->1->4
	node *p = list;
	while (p->next) {
		if (p->next->val == val) {
			node* nextp = p->next->next; //
			node* firstel = p->next; //element

			p->next->next = list->next;
			list->next = nextp;
			p->next = list;
			list = firstel;
		}
		p = p->next;
	}
}

// pp -> head -> randomnode -> randomnode -> bp1 -> p1 -> randomnode -> randomnode -> randomnode-> randomnode -> bp2 -> p2 -> randomnode -> NULL
void ComboSort(node * & head){

	int gap = GetListSize(head);
	node * buffor = head;	//uzywany tylko do podmiany
	node * bp1 = NULL;	//before p1 czyli przed 1 elementem ktory zamieniami
	node * bp2 = head;	//before p2 czyli przed 2 elementem ktory zamieniamy
	node * pp = new node; //pomocniczy elemenet. ma wskazywac na head
	pp->next = head;	//wskauzje na heada

	while (gap > 1){
		//inicjalizacja zmiennych przy kazdym powtorzeniu while
		bp2 = head;				//przypisanie do elementu przed drugim 
		bp1 = pp;				//bp1 to element przed head. wskazuje na head
		gap = gap * 10 / 13;	//ustalenie odstepu
		if (gap == 1){			//jak jest juz 1 odstepu to dopierdolic bubblesort
			BabelekKuwra(head);
			return;
		}

		//ustalanie p2 o jeden raz mniej niz gap bo zawsze ma byc conajmniej 2 drugim elementem.

		for (int i = 0; i < gap-1; i++){
			bp2 = bp2->next;
		}
		while (bp2->next){
			//cout << "iteracja: " ;
			//PokaSowe(bp1);

			if (bp1->next->val > bp2->next->val){

				if (bp1->next== head){
					//Zamiana ->next elementow ktore zmieniamy
					buffor = head->next;		//p1 to next po p1
					head->next = bp2->next->next;
					bp2->next->next = buffor;
					
					//zamiana p1 z p2
					buffor = bp2->next;
					bp2->next = head;
					head = buffor; //next po bp1 to p2
					
					//ustawienie pp na heada bo pokazuje na starego heada
					pp->next = head;
				}
				else{
					//zamiana nextow po p1 i p2
					buffor = bp1->next->next;		//p1 to next po p1
					bp1->next->next = bp2->next->next;
					bp2->next->next = buffor;

					//zamiana p1 z p2
					buffor = bp2->next;
					bp2->next = bp1->next;
					bp1->next = buffor; //next po 1 to p2
				}
			}
			//przesuniecie bp1 i bp2 o 1 dalej
			bp2 = bp2->next;
			bp1 = bp1->next;
		
		}
	}
}


// 10 8 4 24 2 4 2 5 1 5
// 10 8 4 24 2
// 10 8
// 10
// 10  8
// 8 10

void Merge(int * & tab, int l, int m, int r){
	int lsize = m - l + 1;
	int rsize = r - (m+1) +1;	//zaczynamy o jeden dalej dlatego m+1. mozna zapisac r-m

	int * ltab = new int[lsize];
	int * rtab = new int[rsize];


	for (int i = 0; i < lsize; i++){
		ltab[i] = tab[l + i];
	}
	for (int i = 0; i < rsize; i++){
		rtab[i] = tab[m + 1 + i];
	}

	int i = 0;
	int j = 0;

	while (i < lsize && j < rsize){
		if (ltab[i] <= rtab[j]){
			tab[l] = ltab[i];
			i++;
		}
		else{
			tab[l] = rtab[j];
			j++;
		}
		l++;
	}
	while (i < lsize){
		tab[l] = ltab[i];
		i++;
		l++;
	}

	
	while (j < rsize){
		tab[l] = rtab[j];
		j++;
		l++;
	}

}

void MergeSort(int *& tab,int l, int r){
	if (l < r){
		int m = (l + r) / 2;
		MergeSort(tab, l, m);
		MergeSort(tab, m+1, r);
		Merge(tab, l ,m, r);
	}
}


int partition(int *& tab, int l, int r){
	int tmp;
	int i = l;							//inicjalizacja połozenia pivota
	for (int j = l+1; j <= r; j++){		//zaczynamy przechodzenie po j po tablicy od elementu po pivocie do ostatniego elementu
		if (tab[j] < tab[l]){			//jeżeli element po ktorym przechodizmy(j) jest mniejszy od pivota to zamienimy porównywany(j) z (i)elementem pod ktorym ma byc potem pivot. Zaarniamy od pierwszej tablicy elementy poprostu. 
			i++;						//jak znajdziemy element mniejszy od pivota to pivot musi iśc dalej w tablicy bo jest wiecej elementow ktore są mniejsze od niego..
			tmp = tab[i];				//podmiana
			tab[i]=tab[j];
			tab[j] = tmp;
		}
	}
	tmp = tab[l];						//jak sie skończy to podmiana pivota za element i
	tab[l] = tab[i];
	tab[i] = tmp;
	return i;
}

void quicksortLomuto(int *& tab, int l, int r){
	if (l < r){								//jezeli sa 2 elementy
		int q = partition(tab, l, r);		//zwrata pivota i wczesniej ustawia tablice tak zeby były mniejsze liczby przed pivotem a wieksze pi piwocie czyli q.
		quicksortLomuto(tab, l, q-1);				//QS na tab mniejszej od q
		quicksortLomuto(tab , q+1,r);				//QS na tab od q do konca	
	}
}

int partitionHoare(int * & tab,int l,int r){
	int p = tab[l];
	int i = l - 1;
	int j = r + 1;
	while (true){
		do{
			i++;
		} while (tab[i]< p);
		do{
			j--;
		} while (tab[j] > p);
	
		if (i >= j){
			return j;
		}
		swap(tab[i], tab[j]);
		n++;
		
	}

}
void quickSortHoare(int *& tab, int l, int r){
	if (l < r){
	
		int pivot = partitionHoare(tab, l, r);
		quickSortHoare(tab, l, pivot);
		quickSortHoare(tab, pivot + 1, r);
	}
}

//dwie funkcje funkcjonalne dla picu
void PokaSoweTable(int * & tab, int size){
	cout << endl;
	for (int i = 0; i < size; i++){
		cout << tab[i] << " ";
	}
	cout << endl;
}

void FillTableRand(int * & tab, int size){
	for (int i = 0; i < size; i++){
		int value = rand() % 100;
		tab[i] = value;
	}

} 
//SORTOWANIE PRZEZ KUPCOWANIE

//Bąbelek gówna leci do góry. Sprawdzamy czy syn < ojciec. Jak syn większy to źle: czyli trzeba zamienić. Jak zaminimy to przchodzimy wyżej i sprawdzamy czy moze synalek może zajśc jeszcze wyżej. 
void srajWGore(int * & tab, int i){
	while (i>1){				//ma sie juz nie wykonać dla porównania korzenia z rodzicem korzenia - czyli dla i = 1
		int stary = i / 2;
		if (tab[stary] > tab[i])return;
		swap(tab[stary], tab[i]);
		i = stary;
	}
	return;
}
//robienie kupca od góry W DÓŁ czyli od drugiego elementu w tablicy w dół. Od pierwszego elementu po korzeniu. Od i = 2. Zacznamy od pierwszego rodzica i tak sobie schodzimy w dół. 
void zrobKupePodSiebie(int *& tab, int size){
	for (int i = 2; i <= size; i++){
		srajWGore(tab, i);
	}
}

//Sortowanie przez kupcowanie
void zrobKupe(int * & tab, int size){
	zrobKupePodSiebie(tab, size);
	PokaSoweTable(tab,size+1);
	int i =0;
	while (i <size){
		swap(tab[1], tab[size-i]);
		i++;
		zrobKupePodSiebie(tab, size-i);
	}
}

//szuka odpowiedniego meijsca i dodaje
void SearchAdd(treesome *& root, treesome *& leaf){

	if (root==NULL){
		//cout << "root";
		root = leaf;
		return;
	}
	if (leaf->val < root->val){
		//cout << "left";
		if (root->left)SearchAdd(root->left, leaf);
		else{
			root->left = leaf;
			leaf->up = root;
		}
	}
	else{
		//cout << "right";
		if (root->right)SearchAdd(root->right, leaf);
		else{
			root->right = leaf;
			leaf->up = root;
		}
	}
}
//dodawanie liscia
void AddLeaf(treesome *& root, int nval){
	treesome * leaf = new treesome;
	leaf->left = leaf->right = leaf->up = NULL;
	leaf->val = nval;

	SearchAdd(root, leaf);
}
//moje.. chujowe ale działa. 
treesome * findSmallest(treesome * drzeffko){
	if (drzeffko){
		if (drzeffko->left) return findSmallest(drzeffko->left);
		else if (drzeffko->right) return findSmallest(drzeffko->right);
		else return drzeffko;
	}
	else return NULL;
}
//featuring Tomasz Walas Proste i genialne
treesome * GetMinValue(treesome *node){
	while (node->left != NULL)
		node = node->left;

	return node;
}

//okazalo sie ze to sie profesjonalnie nazywa przechodzenie po drzewie IN kurwa ORDER; poprzeczne przejscie po polskiemu
void PokaSoweSTB(treesome *& drzeffko){	//small to big
	if (drzeffko){
		PokaSoweSTB(drzeffko->left);
		cout << drzeffko->val << " ";
		PokaSoweSTB(drzeffko->right);
	}
}
//pre order wzdluzne
void preOrder(treesome *& drzeffko){	
	if (drzeffko){
		cout << drzeffko->val << " ";
		PokaSoweSTB(drzeffko->left);
		PokaSoweSTB(drzeffko->right);
	}

}

//post-order wsteczne
void PostOrder(treesome *& drzeffko){	
	if (drzeffko){
		
		PokaSoweSTB(drzeffko->left);
		PokaSoweSTB(drzeffko->right);
		cout << drzeffko->val << " ";
	}

}
//usuwanie lisci
void ANaDrzewachZamiastLisciBedaWisiecKomunisci(treesome *& drzeffko){
	treesome * p = drzeffko;
	if (p){															//jak wogole istnieje
		if (p->left == NULL && p->right == NULL){					//jak badany element nie ma L i R
			treesome * stary = p->up;								//znajdujemy rodzica
			if (stary) {											//jezeli istnieje rodzic
				if (p->val < stary->val)stary->left = NULL;			//ba
				else stary->right = NULL;							
			}
			delete(p);												//usuwanie elementu
			return;
		}						
		else{
			if (p->left){
				ANaDrzewachZamiastLisciBedaWisiecKomunisci(p->left);
			}
			if (p->right){
				ANaDrzewachZamiastLisciBedaWisiecKomunisci(p->right);
			}
		}
	}

}




void krecMiDupaWPrawo(treesome * & root, treesome * & A){
	treesome * B = A->left, *p = A->up;

	if (B)
	{
		A->left = B->right;
		if (A->left) A->left->up = A;

		B->right = A;
		B->up = p;
		A->up = B;

		if (p)
		{
			if (p->left == A) p->left = B; else p->right = B;
		}
		else root = B;
	}

}

void krecMiDupaWLewo(treesome * & root, treesome * & A){
	treesome * B = A->right, *p = A->up;

	if (B)
	{
		A->right = B->left;
		if (A->right) A->right->up = A;

		B->left = A;
		B->up = p;
		A->up = B;

		if (p)
		{
			if (p->left == A) p->left = B; else p->right = B;
		}
		else root = B;
	}

}

void cutDatTreeDSW(treesome * & beniz){

	int n = 0;						// W n zliczamy węzły
	int s, i;
	treesome * listek = beniz;		// Rozpoczynamy tworzenie listy liniowej
	while (listek)                  // Dopóki jesteśmy w drzewie
		if (listek->left)           // Jeśli przetwarzany węzeł ma lewego syna,
		{
		krecMiDupaWPrawo(beniz, listek);             // to obracamy wokół niego drzewo w prawo
		listek = listek->up;
		}
		else
		{
			n++;                        // Inaczej zwiększamy licznik węzłów
			listek = listek->right;               // i przesuwamy się do prawego syna
		}
	// Teraz z listy tworzymy drzewo BST
	s = n + 1 - log2(n + 1);        // Wyznaczamy początkową liczbę obrotów

	listek = beniz;                       // Rozpoczynamy od początku drzewa
	for (i = 0; i < s; i++)          // Zadaną liczbę razy
	{
		krecMiDupaWLewo(beniz, listek);                // co drugi węzeł obracamy w lewo
		listek = listek->up->right;
	}

	n = n - s;                      // Wyznaczamy kolejne liczby obrotów

	while (n > 1)                    // Powtarzamy procedurę obrotów węzłów
	{
		n >>= 1;                      // Jednakże wyznaczając za każdym razem
		listek = beniz;                     // odpowiednio mniejszą liczbę obrotów, która
		for (i = 0; i < n; i++)        // maleje z potęgami 2.
		{
			krecMiDupaWLewo(beniz, listek);
			listek = listek->up->right;
		}
	}
}

//Obrót w prawo. Obracamy element podany i jego lewackiego syna.
void krecMiDupaWPrawo2(treesome * Daneczko){
	cout << "obracam" << Daneczko->val;
	treesome * gowniak = Daneczko->left;	// *Głosem dr Danuty Szeligi* lewy syn
	treesome * stary = Daneczko->up;		// parent - poliglota tak bardzo
	if (stary)stary->right = gowniak;
	gowniak->up = stary;
	Daneczko->up = gowniak;
	Daneczko->left = gowniak->right;
	if (gowniak->right)gowniak->right->up = Daneczko;
	gowniak->right = Daneczko;


}
//poczatek balansowania drzewa rozklad tylko na liste tak jakby
void cutDatTreeDSW2(treesome * & root){
	if (root){
		treesome * p = root;
		while (p){
			while (p->left){
				krecMiDupaWPrawo2(p);
				p = p->up;
			}
			p = p->right;
		}
	}
}

//Wysokość drzewa
int rozmiar(treesome* beniz){
	int rl=0, rr=0;
	if (!beniz) return 0;	//jak puste to 0
	if (beniz){				//jak istnieje to zwróc 1 + rozmiar ewentualnych podrzew
		if (beniz->left)	rl = rozmiar(beniz->left);	//badamy podrzewo lewe
		if (beniz->right)rr = rozmiar(beniz->right);	//badamy prawe
		if (rl > rr)return 1 + rl;						//jak lewy wiekszy to zwroć 1 + lewy
		else return 1 + rr;
	}
}

///////////////////////////////////////////////////////////////////////
//Grafy
void AddNeighbour(nodeGraph * &start , int id , int w){
	nodeGraph * p = start;
	nodeGraph * n = new nodeGraph;
	n->to = id;
	n->waga = w;
	n->next = NULL;
	if (p){
		while (p->next){
			p = p->next;
		}
		p->next = n;
	}
	else{
		start = n;
	}

}

int main(){
	srand(time(NULL));
	node * head = NULL;

	for (int i = 0; i < 100; i++)
	{
		int value = rand() % 20;
		Add(head, value);
	}

	//cout << "Poczatek: "<<endl;
	//PokaSowe(head);
//	cout << "Zbabelkowane:" << endl;
//	BabelekKuwra(head);
//	PokaSowe(head);
// int dupa = GetListSize(head);
//	cout <<endl<< "Ilosc nodeow: "<< dupa<<endl;



	//testowa
	node * head2 = NULL;
	Add(head2, 10);
	Add(head2, 3);
	Add(head2, 2);
	Add(head2, 1);
	Add(head2, 8);
	Add(head2, 7);
	Add(head2, 5);
	Add(head2, 4);
	Add(head2, 9);
	Add(head2, 6);
	ComboSort(head2);
	
	node * head10 = NULL;
	node * head11 = NULL;
	for (int i = 0; i < 10; i++)
	{
		Add(head10, i);
	}
	for (int i = 0; i < 10; i++)
	{
		Add(head11, i);
	}
	cout << endl << "lista nr 1: ";
	PokaSowe(head10);
	cout << endl << "lista nr 2: ";
	PokaSowe(head11);
	unplug(head10, head11, 5);
	cout << endl << "lista nr 1: ";
	PokaSowe(head10);
	cout << endl << "lista nr 2: ";
	PokaSowe(head11);


	
	
	
	
//TABLICE
	PokaSowe(head2);
	int size = 11;
	int * tab = new int[size];
	tab[0] = 6;
	tab[1] = 9;
	tab[2] = 4;
	tab[3] = 5;
	tab[4] = 7;
	tab[5] = 8;
	tab[6] = 1;
	tab[7] = 2;
	tab[8] = 3;
	tab[9] = 10;
	tab[10] = 9;

	//MergeSort (tab, 0, 9);
	//quicksortLomuto(tab, 0, 9);


	tab[0] = NULL;//dla kupcowania
	PokaSoweTable(tab, size);
	zrobKupe(tab, size - 1);
	PokaSoweTable(tab, size);



//Tablica numer 2
	size = 10;
	int * tab2 = new int[size];


	FillTableRand(tab2, size);

	//PokaSoweTable(tab2, size);
	//quicksortLomuto(tab2, 0, size - 1);
	//quickSortHoare(tab2, 0, size - 1);
	
	//zrobKupe(tab2, size-1);

	//PokaSoweTable(tab2, size);


	cout << "zamiana: " << n;

//Drzewa BST
	treesome * choinka = NULL;
	
	
	AddLeaf(choinka, 5);
	AddLeaf(choinka, 1);
	AddLeaf(choinka, 7);
	AddLeaf(choinka, 4);
	AddLeaf(choinka, 6);
	AddLeaf(choinka, 3);
	AddLeaf(choinka, 2);
	AddLeaf(choinka, 8);
	AddLeaf(choinka, 4);
	AddLeaf(choinka, 9);
	/*
	AddLeaf(choinka, 1);
	AddLeaf(choinka, 2);
	AddLeaf(choinka, 3);
	AddLeaf(choinka, 4);
	AddLeaf(choinka, 5);
	AddLeaf(choinka, 6);
	*/
	//cout << rozmiar(choinka);
//	cout << findSmallest(choinka)->val;
//	cout << GetMinValue(choinka)->val;
	/*for (int i = 0; i < 10; i++)
	{
		int value = rand() % 20;
		AddLeaf(choinka, value);
	}
	*/
	cout << endl;
	PokaSoweSTB(choinka);
	cout << endl;
	ANaDrzewachZamiastLisciBedaWisiecKomunisci(choinka);
	PokaSoweSTB(choinka);
	//cutDatTreeDSW2(choinka);
	//cout << rozmiar(choinka);
	
	/*
	int sizegraph = 11;
	nodeGraph ** NList = new nodeGraph * [sizegraph];


	for (int i = 0; i < 11; i++){
		NList[i] = NULL;
	}

	//brzydkie dodawane do tablicy list.. index w tablicy to numer OD a 2 argument to DO. trzeci to waga tego połączenia;
	AddNeighbour(NList[1], 2, 1);
	AddNeighbour(NList[1], 5, 6);
	AddNeighbour(NList[2], 3, 2);
	AddNeighbour(NList[2], 5, 5);
	AddNeighbour(NList[3], 2, 2);
	AddNeighbour(NList[4], 3, 3);
	AddNeighbour(NList[4], 5, 4);
	AddNeighbour(NList[5], 4, 4);
	AddNeighbour(NList[5], 2, 5);
	AddNeighbour(NList[5], 1, 6);
	//brzydkie wypisanie wag połaczeń wychodzących z wierzchołka nr 5;
	nodeGraph * p = NList[5];
	cout << endl; cout << endl;
	while(p){
		cout << p->waga;
		p = p->next;
	}
	*/


	system("Pause");
}