Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma warning(disable:4996)
- #include <iostream>
- #include <iomanip>
- #include <cstdlib>
- #include <ctime>
- #include <time.h>
- #include <fstream>
- using namespace std;
- struct slistEl
- {
- slistEl * next;
- int data;
- double d;
- char c;
- };
- struct slist
- {
- slistEl * head;
- slist()
- {
- head = NULL;
- }
- ~slist()
- {
- while (head) pop_front();
- }
- void printl()
- {
- slistEl * p;
- int ilosc = 0;
- for (p = head; p; p = p->next)
- {
- cout << " " << p->data << " " << p->c << " " << p->d << endl;
- }
- cout << endl;
- }
- void push_front(int v)
- {
- slistEl * p;
- p = new slistEl;
- p->next = head;
- p->data = v;
- p->c = 'T';
- p->d = rand() % 1000;
- head = p;
- }
- void pop_front()
- {
- slistEl * p = head;
- if (p)
- {
- head = p->next;
- delete p;
- }
- }
- void split(slist & l1, slist & l2)
- {
- slistEl * p1, *p2;
- bool s = false;
- l1.push_front(0);
- l2.push_front(0);
- p1 = l1.head;
- p2 = l2.head;
- while (head)
- {
- if (s)
- {
- p2->next = head;
- p2 = p2->next;
- }
- else
- {
- p1->next = head;
- p1 = p1->next;
- }
- head = head->next;
- s = !s;
- }
- p1->next = p2->next = NULL;
- l1.pop_front();
- l2.pop_front();
- }
- void merge(slist & l1, slist & l2)
- {
- slistEl * p;
- push_front(0);
- p = head;
- while (l1.head && l2.head)
- {
- if (l1.head->data > l2.head->data)
- {
- p->next = l2.head;
- l2.head = l2.head->next;
- }
- else
- {
- p->next = l1.head;
- l1.head = l1.head->next;
- }
- p = p->next;
- }
- while (l1.head)
- {
- p->next = l1.head;
- l1.head = l1.head->next;
- p = p->next;
- }
- while (l2.head)
- {
- p->next = l2.head;
- l2.head = l2.head->next;
- p = p->next;
- }
- pop_front();
- }
- void merge_sort()
- {
- slist h1, h2;
- if (head && head->next)
- {
- split(h1, h2);
- h1.merge_sort();
- h2.merge_sort();
- merge(h1, h2);
- }
- }
- slistEl * find_first(int k, slistEl* &pomocniczy)
- {
- slistEl * p = head;
- pomocniczy = p;
- while (p && p->data != k)
- {
- p = p->next;
- }
- return p;
- }
- void printlj(int ilosc)
- {
- slistEl * p;
- int i = 0;
- for (p = head; p; p = p->next)
- {
- if (i > ilosc - 12)
- cout << p->data << endl;
- i++;
- }
- cout << endl;
- }
- void printld()
- {
- slistEl * p;
- int ilosc = 0;
- for (p = head; p && ilosc < 20; p = p->next)
- {
- cout << " " << p->data << " " << p->c << " " << p->d << endl;
- ilosc++;
- }
- cout << endl;
- }
- void pop_back(slistEl* &el)
- {
- slistEl* p = head;
- if (p)
- {
- if (p->next)
- {
- while (p->next->next) p = p->next;
- delete p->next;
- p->next = 0;
- }
- else
- {
- delete p;
- head = 0;
- }
- }
- }
- };
- void czytanie(int &X,int &k1,int &k2,int &k3,int &k4,int &k5)
- {
- fstream plik;
- plik.open("inlab02.txt", ios::in);
- if (plik.good()) {
- plik >> X >> k1 >> k2 >> k3 >> k4 >> k5;
- plik.close();
- }
- else exit;
- }
- int main()
- {
- float czas;
- int X,k1,k2,k3,k4,k5;
- czytanie(X,k1,k2,k3,k4,k5);
- clock_t begin, end;
- begin = clock();
- slist L;
- slistEl *p;
- slistEl *pomocniczy;
- int rozmiar = 0;
- int klucz1 = 0;
- int *wylosowane = new int[X];
- wylosowane[0] = 0;
- srand(time(NULL));
- int losowa;
- for (int i = 0; i < X; i++)
- {
- losowa = rand() % 99999 + 99;
- for (int j = 0; j < i; j++)
- {
- if (losowa == wylosowane[j])
- {
- losowa = rand() % 99999 + 99;
- j = -1;
- }
- }
- rozmiar++;
- if (losowa == k1) { klucz1++; }
- L.push_front(losowa);
- wylosowane[i] = losowa;
- }
- cout << "rozmiar " << rozmiar << endl;
- cout << endl;
- L.merge_sort();
- do
- {
- p = L.find_first(k1,pomocniczy);
- if (p)
- {
- cout << "wykryto k1" << endl;
- break;
- }
- } while (p);
- cout << "klucz 1 wystapil : " << klucz1 << " razy " << endl;
- L.printld(); //show 20
- L.push_front(k2);
- rozmiar++;
- L.merge_sort();
- L.printld(); //show 20
- L.push_front(k3);
- rozmiar++;
- L.merge_sort();
- L.printld(); //show 20
- L.push_front(k4);
- rozmiar++;
- L.merge_sort();
- L.printld(); //show 20
- L.push_front(k5);
- rozmiar++;
- //delete k3
- L.merge_sort();
- do
- {
- p = L.find_first(k3, pomocniczy);
- if (p)
- {
- if (p->next == 0) { L.pop_back(p); }
- else {
- pomocniczy->next = p->next;
- p->next = nullptr;
- delete p;
- }
- }
- } while (p);
- rozmiar--;
- L.printld(); //show 20
- //delete k2
- do
- {
- p = L.find_first(k2, pomocniczy);
- if (p)
- {
- if (p->next == 0) { L.pop_back(p); }
- else {
- pomocniczy->next = p->next;
- p->next = nullptr;
- delete p;
- }
- }
- } while (p);
- rozmiar--;
- L.printld(); //show 20
- //delete k5
- do
- {
- p = L.find_first(k5, pomocniczy);
- if (p)
- {
- if (p->next == 0) {L.pop_back(p);}
- else {
- pomocniczy->next = p->next;
- p->next = nullptr;
- delete p;
- }
- }
- } while (p);
- rozmiar--;
- cout << rozmiar << " elementy" << endl<<endl;//wielkosc listy
- do
- {
- p = L.find_first(k5, pomocniczy);
- if (p)
- {
- cout << "cos poszlo nie tak i nie usunieto klucza 5" << endl;
- }
- } while (p);
- L.printlj(rozmiar);//show wartosci 11
- //delete lista
- for (int i = 0; i < rozmiar; i++) { L.pop_front(); }
- L.printl(); //brak listy
- end = clock();
- czas = (float)(end - begin);
- cout << "czas wykonania: "<<czas / 1000<<"s"<<endl;
- system("pause");
- delete[]wylosowane;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement