//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;
}
