Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdlib>
- #include <ctime>
- using namespace std;
- struct node{
- int val;
- node *next;
- };
- void add(node *&H, int value)
- {
- node *p = new node;
- p->val = value;
- p->next=H;
- H=p;
- }
- void addToEnd(node *&H, int value){
- if(H==NULL){
- add(H, value);
- }else{
- node *p = H;
- while(p->next!=NULL){
- p=p->next;
- }
- node *p2 = new node;
- p2->val = value;
- p->next=p2;
- p2->next=NULL;
- }
- }
- void show(node *&H){
- node *p = H;
- cout << "H->";
- while(p != NULL){
- cout << p->val << "->";
- p=p->next;
- }
- cout << "NULL" << endl;
- }
- void del(node *&H){
- node *p = H;
- H = p->next;
- delete p;
- }
- void copyRevert(node *&H){
- node *p = H;
- node *H2 = NULL;
- node *pointer = NULL;
- while(p !=NULL){
- add(H2, p->val);
- if(p->next == NULL)
- pointer = p;
- p=p->next;
- }
- pointer->next = H2;
- H2=NULL;
- }
- void copyInOrder(node *&H){
- node *p = H;
- node *H2 = NULL;
- node *pointer = NULL;
- while(p !=NULL){
- add(H2, p->val);
- if(p->next == NULL)
- pointer = p;
- p=p->next;
- }
- show(H2);
- p=H2;
- while(H2 != NULL){
- if(H2->next==NULL){
- pointer->next=H2;
- p->next=NULL;
- pointer = pointer->next;
- H2=NULL;
- }
- else if(H2->next->next == NULL){
- p=p->next;
- pointer->next=p;
- p->next = NULL;
- H2->next=NULL;
- pointer=pointer->next;
- p=H2;
- }
- else{
- while(p->next->next != NULL){
- p=p->next;
- }
- pointer->next=p->next;
- p->next=NULL;
- pointer = pointer->next;
- p=H2;
- }
- }
- }
- void delValue(node *&H, int value)
- {
- node *p = H;
- if(H != NULL)
- {
- if(H->val==value)
- {
- del(H);
- } else {
- while(p->next != NULL){
- if(p->next->val == value)
- {
- node *temp = p;
- p->next=p->next->next;
- delete temp;
- } else {
- p=p->next;
- }
- }
- }
- } else {
- cout << "Lista jest pusta (delValue)"<< endl;
- }
- }
- void swapWithNext(node *&H, int valToSwap)
- {
- node *x = H;
- node *y = H;
- node *z = H;
- if(H->next->next == NULL)
- {
- cout << "Lista ma mniej niz 2 elementy" << endl;
- } else {
- if(H->val == valToSwap)
- {
- {
- cout << "H " << H->val << endl;
- cout << "y " << y->val << endl;
- cout << "z " << z->val << endl;
- node *x = H-> next;
- H->next = x -> next;
- x->next = H;
- H=x;
- }
- } else {
- while (x->next != NULL) {
- if(x->next->val == valToSwap)
- {
- if (x->next->next == NULL)
- {
- cout << "Probujesz zamienic ostatni element" << endl;
- break;
- } else {
- y = x-> next;
- z = y-> next;
- y->next = z->next;
- z->next = x->next;
- x->next = z;
- break;}
- }
- else {
- x = x-> next;
- }
- }
- }
- }
- }
- void ssort(node *H){
- node *H2 = NULL;
- node *prev_max = NULL;
- node *p = H;
- node *max = H;
- while(H != NULL){
- prev_max = NULL;
- p=H;
- max = H;
- while(p->next != NULL){
- if(p->next->val > max->val)
- {
- prev_max = p;
- max = p->next;
- cout << "Max: " << max->val << endl;
- }
- p=p->next;
- }
- if(prev_max == NULL)
- {
- H=H->next;
- max->next = H2;
- H2 = max;
- }else{
- prev_max->next = max->next;
- max->next=H2;
- H2=max;
- }
- }
- H = H2;
- H2 = NULL;
- }
- void wiekszeNaKoniec(node *&H){
- double wartosc = 0;
- int liczbaElementow = 0;
- node *p = H;
- while(p!=NULL){
- wartosc += p->val;
- liczbaElementow++;
- p=p->next;
- }
- double srednia = wartosc/liczbaElementow;
- cout << "wartosc " << wartosc << endl;
- cout << "srednia " << srednia << endl;
- cout << "liczba " << liczbaElementow << endl;
- node *H2 = NULL;
- p=H;
- node *tail = NULL;
- while(p!=NULL){
- if (p->val>srednia) {
- addToEnd(H2, p->val);
- }
- if(p->next==NULL){
- tail=p;
- }
- p=p->next;
- }
- tail->next=H2;
- H2=NULL;
- }
- void usunCoDrugie(node *&H){
- node *p = H;
- node *d = NULL;
- if(H!=NULL){
- while(p->next!=NULL){
- d = p->next;
- p->next=p->next->next;
- p=p->next;
- delete d;
- }
- }
- }
- void usunParzystePary(node *H){
- node *p = H->next;
- node *d = NULL;
- if(H!=NULL){
- while(p->next->next != NULL && p->next->next->next!=NULL){
- if((p->next->val + p->next->next->val) %2 == 0){
- d = p->next;
- p->next = p->next->next->next;
- delete d->next;
- delete d;
- }else{
- p=p->next->next;
- }
- }
- if(p->next->next->next == NULL){
- if((p->next->val + p->next->next->val)%2 == 0){
- delete p->next->next;
- delete p->next;
- p->next = NULL;
- }
- }else if(p->next->next == NULL){
- if((p->val + p->next->val)%2 == 0){
- delete p->next;
- p=NULL;
- }
- }
- }
- }
- //void swapBubble(node *&H, node *&p){
- //
- //
- //
- // if(p == NULL)
- // {
- // node *temp = H;
- // H=H->next;
- // temp->next = H->next;
- // H->next = temp;
- // }else{
- //
- // node *d = p->next->next;
- // p->next->next = d->next;
- // d->next = p->next;
- // p->next = d;
- // }
- //
- //}
- //
- //void bubbleSort(node *&H){
- //
- // bool flag = 1; //ustawiam flage ktora sprawdza czy zamieniono jakikolwiek element przy przejsciu
- // node *p = H;
- //
- // while(flag == 1){
- // flag = 0;
- //
- // if(H->val > H->next->val){
- // swapBubble(H, p=NULL);
- // flag = 1;
- //
- // }else{
- //
- // p=H;
- // while (p->next->next != NULL) {
- //
- // if(p->next->val > p->next->next->val){
- // swapBubble(H, p);
- // flag = 1;
- // }
- // p=p->next;
- // }
- // }
- // }
- //}
- void swapBubble(node *&H, node *&p){
- if(p==NULL){
- node *temp = H;
- H=H->next;
- temp->next = H->next;
- H->next=temp;
- }else{
- node *temp = p->next->next;
- p->next->next = temp ->next;
- temp->next = p->next;
- p->next=temp;
- }
- }
- void bubbleSort(node *&H){
- node *p = H;
- int flag = 1;
- while(flag == 1){
- flag = 0;
- //if(H->next != NULL && H!=NULL)
- {
- if(H->val > H->next->val){
- swapBubble(H, p=NULL);
- flag = 1;
- }else{
- p=H;
- while(p->next->next != NULL){
- if(p->next->val>p->next->next->val){
- swapBubble(H, p);
- flag = 1;
- }
- p=p->next;
- }
- }}
- }
- }
- void splitList(node *&H, node *&H1, node *&H2){ //Przerobic to na funkcje zewnetrzna, wywolywanie dla kazdego elementu w petli while
- if(H!=NULL){
- node *p = NULL;
- node *t1 = NULL;
- node *t2 = NULL;
- while(H!=NULL){
- p=H;
- H=H->next;
- if(t1==NULL){
- t1 = p;
- H1=p;
- p->next = NULL;}
- else{
- t1->next = p;
- t1 = p;
- t1->next = NULL;
- }
- if(H!=NULL){
- p=H;
- H=H->next;
- if(t2==NULL){
- t2 = p;
- H2=p;
- p->next = NULL;}
- else{
- t2->next = p;
- t2 = p;
- t2->next = NULL;
- }
- }
- }
- }
- }
- void usunWiekszeOdSredniej(node *&H){
- double wartosc = 0;
- double liczbaElementow = 0;
- node *p = H;
- while(p!=NULL){
- wartosc += p->val;
- liczbaElementow++;
- p=p->next;
- }
- double srednia = wartosc/liczbaElementow;
- p=H;
- while(p->next != NULL){
- if(H->val > srednia){
- node *temp = H;
- H=H->next;
- delete temp;
- }
- if(p->next->val > srednia){
- node *temp = p->next;
- p->next=p->next->next;
- delete temp;
- }
- p=p->next;
- }
- }
- void insertToSortedList(node *&H, int x){
- node *p = H;
- if(H==NULL){
- add(H, x);
- }
- if (x < p->val) {
- add(H, x);
- }else{
- while (p->next->val < x) {
- p=p->next;
- }
- add(p->next, x);
- }
- }
- void showDB(node **DB, int size){
- for(int i = 0; i<size; i++)
- {
- cout << DB[i]->val << endl;
- }
- }
- void database(node *&H, int size){
- node **DB = new node*[size/100];
- for(int i = 0; i<size/100; i++){
- DB[i]=NULL;
- }
- cout << "kubelkowe start" << endl;
- std::chrono::time_point<std::chrono::system_clock> start, end;
- start = std::chrono::system_clock::now();
- srand( time( NULL ) );
- for(int i=0; i<size; i++){
- int temp = (( rand() % 50000 ) + 1 );
- add(DB[temp/100],temp);
- add(H, temp);
- }
- for(int i = 0; i < size/100; i++){
- if (DB[i]!=NULL && DB[i]->next != NULL) {
- bubbleSort(DB[i]);
- }
- }
- node *HF = DB[0];
- node *p = HF;
- for(int i = 1; i<size/100; i++){
- if(HF!=NULL){
- while (p->next != NULL) {
- p=p->next;}
- }
- p->next = DB[i];
- }
- end = std::chrono::system_clock::now();
- std::chrono::duration<double> elapsed_seconds = end-start;
- std::time_t end_time = std::chrono::system_clock::to_time_t(end);
- std::cout << "finished computation at " << std::ctime(&end_time)
- << "elapsed time: " << elapsed_seconds.count() << "s\n";
- cout << "babelkowe koniec" << endl;
- cout << "kubelkowe koniec" << endl;
- cout << "babelkowe start" << endl;
- start = std::chrono::system_clock::now();
- bubbleSort(H);
- //std::cout << "f(42) = " << fibonacci(42) << '\n';
- end = std::chrono::system_clock::now();
- elapsed_seconds = end-start;
- end_time = std::chrono::system_clock::to_time_t(end);
- std::cout << "finished computation at " << std::ctime(&end_time)
- << "elapsed time: " << elapsed_seconds.count() << "s\n";
- cout << "babelkowe koniec" << endl;
- }
- int main() {
- node *H = NULL;
- database(H, 50000);
- return 0;
- }
- // node *H1 = NULL;
- // node *H2 = NULL;
- //add(H, 2);
- //add(H, 18);
- //add(H, 2);
- //add(H, 6);
- //add(H, 33);
- //add(H, 8);
- //add(H, 1);
- //
- //show(H);
- //bubbleSort(H);
- //show(H);
- //insertToSortedList(H, 22);
- //show(H);
- //insertToSortedList(H, 4);
- //show(H);
- //insertToSortedList(H, -9);
- //show(H);
- //add(H, 6);
- //add(H, 14);
- //add(H, 1);
- //add(H, 12);
- //add(H, 17);
- //add(H, 65);
- //add(H, 157);
- //add(H, 13);
- // usunCoDrugie(H);
- // addToEnd(H, 666);
- // wiekszeNaKoniec(H);
- // copyRevert(H);
- // copyInOrder(H);
- // usunParzystePary(H);
- // splitList(H, H1, H2);
- // usunWiekszeOdSredniej(H);
- //if(H->next->next == NULL || H->next == NULL || H == NULL)
- //{
- // cout << "Tu tego nie zrobisz" << endl;
- //}else
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement