API tools faq
paste
allekco

lab1 + lab0

allekco
Dec 22nd, 2019
145
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 14.36 KB | None | 0 0
raw download clone embed print report
  1. #include <iostream>
  2. #include <ostream>
  3. #include <fstream>
  4. #include <string>
  5. #include <cstdlib>
  6. #include <ctime>
  7.  
  8. using namespace std;
  9.  
  10. template <typename TElement> class Sequence {
  11. public:
  12.     virtual void Append(TElement item) = 0;
  13.     virtual void Prepend(TElement item) = 0;
  14.     virtual void InsertAt(int index, TElement item) = 0;
  15.     virtual int getLength() = 0;
  16.     virtual int getIsEmpty() = 0;
  17.     virtual TElement Get(int index) = 0;
  18.     virtual TElement GetFirst() = 0;
  19.     virtual TElement GetLast() = 0;
  20.     virtual void Remove(TElement item) = 0;
  21.     virtual void Swap(int i, int j) = 0;
  22.     virtual void Show() = 0;
  23.  
  24. };
  25.  
  26. template <typename TElement> struct Node //узел
  27. {
  28.     TElement value;
  29.     Node<TElement>* next;
  30.     Node<TElement>* prev;//Указатели на адреса следующего и предыдущего элементов списка
  31. };
  32.  
  33. template <typename TElement> class ListSequence: public Sequence<TElement> {
  34. private:
  35.     int Length;
  36.     Node<TElement>* head;
  37.     Node<TElement>* tail;
  38. public:
  39.  
  40.      ListSequence()
  41.      {
  42.         head = nullptr;
  43.         tail = nullptr;
  44.         Length = 0;
  45.      }
  46.  
  47.     virtual void Append(TElement item) override
  48.     {
  49.         struct Node<TElement>* temp;
  50.         temp = new Node<TElement>;
  51.         temp->value = item;
  52.         if (head == nullptr) { //если список пустой
  53.             head = temp;
  54.             tail = temp;
  55.             head->prev = nullptr;
  56.             tail->next = nullptr;
  57.             Length = 1;
  58.         }
  59.         else { //список не пустой
  60.             temp->prev = tail;
  61.             tail->next = temp;
  62.             tail = temp;
  63.             tail->next = nullptr;
  64.             Length += 1;
  65.         }
  66.     }
  67.  
  68.     virtual void Prepend(TElement item)override
  69.     {
  70.         struct Node<TElement>* temp;
  71.         struct Node<TElement>* p = head;
  72.         temp = new Node<TElement>;
  73.         temp->prev = nullptr;
  74.         temp->value = item;
  75.         if (head == nullptr) { //если список пустой
  76.             head = temp;
  77.             tail = temp;
  78.             temp->next = nullptr;
  79.             Length = 1;
  80.         }
  81.         else { //список не пустой
  82.             p->prev = temp;
  83.             temp->next = head;
  84.             head = temp;
  85.             Length += 1;
  86.            
  87.         }
  88.     }
  89.  
  90.     virtual void InsertAt(int index, TElement item) override
  91.     {
  92.         index = index + 1;
  93.         if (index == 1) return Prepend(item);
  94.         if (index == Length + 1) return Append(item);
  95.         if (index < 1 || index > Length + 1)
  96.             cout << "This index out of length" << endl;
  97.         else {
  98.             struct Node<TElement>* temp1;
  99.             struct Node<TElement>* p3;
  100.             temp1 = new Node<TElement>;
  101.             int i;
  102.             p3 = head;
  103.             for (i = 1; i < index; i++) {
  104.                 p3 = p3->next;
  105.             }
  106.             temp1->value = item;
  107.             temp1->prev = p3->prev;
  108.             temp1->next = p3;
  109.             p3=p3->prev;
  110.             p3->next = temp1;
  111.             p3 = temp1->next;
  112.             p3->prev = temp1;
  113.             Length ++;
  114.         }
  115.     }
  116.  
  117.     virtual int getLength() override
  118.     {
  119.         return Length;
  120.     }
  121.  
  122.     virtual int getIsEmpty() override
  123.     {
  124.         if (Length == 0) {
  125.             cout << "Sequence is empty" << endl;
  126.             return 1;
  127.         }
  128.         else {
  129.             cout << "Sequence isn't empty" << endl;
  130.             return -1;
  131.         }
  132.     }
  133.  
  134.     virtual TElement Get(int index) override
  135.     {
  136.         if ((Length <= index) || (index < 0)) {
  137.             cout << "Element with index " << index << " didn't find" << endl;
  138.             return -1;
  139.         }
  140.         else {
  141.             int i;
  142.             Node<TElement>* temp;
  143.             temp = head;
  144.             for (i = 0; i < index; i++) {
  145.                 temp = temp->next;
  146.             }
  147.             return temp->value;
  148.         }
  149.     }
  150.  
  151.     virtual TElement GetFirst() override
  152.     {
  153.         return Get(0);
  154.     }
  155.  
  156.     virtual TElement GetLast() override
  157.     {
  158.         return Get(Length - 1);
  159.     }
  160.  
  161.     virtual void Remove(TElement item) override //по значению
  162.     {
  163.         int i;
  164.         Node<TElement>* p = head;
  165.         Node<TElement>* p2 = head;
  166.         if (head->value == item) {
  167.             RemoveFirst();
  168.             Length -= 1;
  169.         }
  170.         else {
  171.             for (i = 1; i < Length; i++) {
  172.                 if ((p->next->value == item) && (p->next->next != nullptr)) {
  173.                     Length -= 1;
  174.                     p->next = p->next->next;
  175.                     p = p->next;
  176.                     p->prev = p2;
  177.                     break;
  178.                 }
  179.                 if ((p->next->value == item) && (p->next->next == nullptr)) {
  180.                     RemoveLast();
  181.                     break;
  182.                 }
  183.                 p = p->next;
  184.                 p2 = p2->next;
  185.             }
  186.         }
  187.     }
  188.  
  189.     void RemoveIndex(TElement index)
  190.     {
  191.         int i;
  192.         Node<TElement>* p = head;
  193.         Node<TElement>* p2 = head;
  194.         if (index >= Length || index < 0) {
  195.             cout << "Out of lenght" << endl;
  196.         }
  197.         else
  198.         {
  199.             if (index == 0) RemoveFirst();
  200.             else {
  201.                 if (index == Length - 1) RemoveLast();
  202.                 else
  203.                 {
  204.                     for (i = 0; i < index-1; i++)
  205.                     {
  206.                         p = p->next;
  207.                         p2 = p2->next;
  208.                     }
  209.                     p2 = p2->next->next;
  210.                     p->next = p2;
  211.                     p2->prev = p;
  212.                 }
  213.             }
  214.             Length -= 1;
  215.         }
  216.     }
  217.  
  218.     void RemoveFirst()
  219.     {
  220.         if (head == tail) {
  221.             head = nullptr;
  222.             tail = nullptr;
  223.         }
  224.         else {
  225.             Node<TElement>* q = head;
  226.             head = q->next;
  227.             q->next->prev = head;
  228.         }
  229.     }
  230.     void RemoveLast()
  231.     {
  232.         Node<TElement>* l = tail;
  233.         tail = l->prev;
  234.         l->prev->next = tail;
  235.         tail->next = nullptr;
  236.     }
  237.  
  238.     ListSequence GetSubsequence(int startIndex, int endIndex)
  239.     {
  240.         ListSequence B;
  241.         Node<TElement>* p = head;
  242.         if ((startIndex < 0) || (endIndex < 0) || (endIndex < startIndex) || (endIndex >= Length)) {
  243.             cout << "Error with index" << endl;
  244.         }
  245.         else {
  246.             for (int i = 0; i < startIndex; i++) {
  247.                 p = p->next;
  248.             }
  249.             for (int j = startIndex; j <= endIndex; j++) {
  250.                 B.Append(p->value);
  251.                 p = p->next;
  252.             }
  253.         }
  254.         return B;
  255.     }
  256.  
  257.     virtual void Swap(int i, int j) override
  258.     {
  259.         int a, b;
  260.         a = Get(i);
  261.         b = Get(j);
  262.         RemoveIndex(i);
  263.         RemoveIndex(j-1);
  264.         InsertAt(i, b);
  265.         InsertAt(j, a);
  266.     }
  267.  
  268.     virtual void Show() override
  269.     {
  270.         Node<TElement>* temp = head;
  271.         while (temp != nullptr) {
  272.             cout << temp->value << " ";
  273.             temp = temp->next;
  274.         }
  275.         cout << endl;
  276.     }
  277.  
  278.     ~ListSequence() {}
  279. };
  280.  
  281. template <typename TElement> class ArraySequence
  282.     : public Sequence<TElement>
  283. {
  284. private:
  285.     TElement* point; // указатель на массив
  286.     int Length; // размер массива
  287.  
  288. public:
  289.     ArraySequence()
  290.     {
  291.         Length = 0; // по умолчанию размер массива = 10 элементов
  292.         point = new TElement[Length]; // выделить место в памяти для массива
  293.     }
  294.    
  295.     virtual void Append(TElement item) override
  296.     {
  297.         int i;
  298.         TElement* tmp;
  299.         tmp = new TElement[Length]; // выделяем память
  300.         for (i = 0; i < Length; i++) {
  301.             tmp[i] = point[i];
  302.         }
  303.         Length = Length + 1; // увеличиваем размер массива на 1
  304.         point = new TElement[Length];
  305.         for (i = 0; i < Length - 1; i++) {
  306.             point[i] = tmp[i];
  307.         }
  308.         point[Length - 1] = item;
  309.         delete tmp;
  310.     }
  311.  
  312.     virtual void Prepend(TElement item) override
  313.     {
  314.         int i;
  315.         TElement* tmp;
  316.         tmp = new TElement[Length]; // выделяем память
  317.         for (i = 0; i < Length; i++) {
  318.             tmp[i] = point[i];
  319.         }
  320.         Length = Length + 1; // увеличиваем размер массива на 1
  321.         point = new TElement[Length];
  322.         point[0] = item;
  323.         for (i = 1; i < Length; i++) {
  324.             point[i] = tmp[i - 1];
  325.         }
  326.         delete tmp;
  327.     }
  328.  
  329.     virtual void InsertAt(int index, TElement item) override
  330.     {
  331.         if ((Length + 1 <= index) || (index < 0)) {
  332.             cout << "This index out of length" << endl;
  333.         }
  334.         else {
  335.             int i;
  336.             TElement* tmp;
  337.             tmp = new TElement[Length]; // выделяем память
  338.             for (i = 0; i < Length; i++) {
  339.                 tmp[i] = point[i];
  340.             }
  341.             Length = Length + 1; // увеличиваем размер массива на 1
  342.             point = new TElement[Length];
  343.             for (i = 0; i < index; i++)
  344.                 point[i] = tmp[i];
  345.             point[index] = item;
  346.             for (i = index + 1; i < Length; i++)
  347.                 point[i] = tmp[i - 1];
  348.             delete tmp;
  349.         }
  350.     }
  351.  
  352.     virtual int getLength() override
  353.     {
  354.         return Length;
  355.     }
  356.  
  357.     virtual int getIsEmpty() override
  358.     {
  359.         if (Length == 0) {
  360.             cout << "Sequence is empty" << endl;
  361.             return 1;
  362.         }
  363.         else {
  364.             cout << "Sequence isn't empty" << endl;
  365.             return -1;
  366.         }
  367.     }
  368.  
  369.     virtual TElement Get(int index) override
  370.     {
  371.         if ((Length <= index) || (index < 0)) {
  372.             cout << "Element with index " << index << " didn't find" << endl;
  373.             return -1;
  374.         }
  375.         else {
  376.             return point[index];
  377.         }
  378.     }
  379.  
  380.     virtual TElement GetFirst() override
  381.     {
  382.         if (Length != 0) {
  383.             return point[0];
  384.         }
  385.         else {
  386.             cout << "Sequance is empty" << endl;
  387.             return -1;
  388.         }
  389.     }
  390.     virtual TElement GetLast() override
  391.     {
  392.         if (Length != 0) {
  393.             return point[Length - 1];
  394.         }
  395.         else {
  396.             cout << "Sequance is empty" << endl;
  397.             return -1;
  398.         }
  399.     }
  400.     virtual void Remove(TElement item) override
  401.     {
  402.         int i = 0, index, key = 0;
  403.         while (i < Length) {
  404.             if (point[i] == item) {
  405.                 index = i;
  406.                 i = Length;
  407.                 key = 1;
  408.             }
  409.             i++;
  410.         }
  411.         if (key) { //удаляем
  412.             TElement* tmp;
  413.             tmp = new TElement[Length];
  414.             for (i = 0; i < Length; i++) {
  415.                 tmp[i] = point[i];
  416.             }
  417.             Length = Length - 1;
  418.             point = new TElement[Length];
  419.             for (i = 0; i < index; i++) {
  420.                 point[i] = tmp[i];
  421.             }
  422.             for (i = index; i < Length; i++) {
  423.                 point[i] = tmp[i + 1];
  424.             }
  425.         }
  426.     }
  427.  
  428.     void RemoveIndex(TElement index)
  429.     {
  430.         int i;
  431.         TElement* tmp;
  432.         tmp = new TElement[Length];
  433.         for (i = 0; i < Length; i++) {
  434.             tmp[i] = point[i];
  435.         }
  436.         Length = Length - 1;
  437.         point = new TElement[Length];
  438.         for (i = 0; i < index; i++) {
  439.             point[i] = tmp[i];
  440.         }
  441.         for (i = index; i < Length; i++) {
  442.             point[i] = tmp[i + 1];
  443.         }
  444.     }
  445.  
  446.     ArraySequence GetSubsequence(int startIndex, int endIndex)
  447.     {
  448.         ArraySequence B;
  449.         if ((startIndex < 0) || (endIndex < 0) || (endIndex < startIndex) || (endIndex >= Length)) {
  450.             cout << "Error with index" << endl;
  451.         }
  452.         else {
  453.             for (int i = startIndex; i <= endIndex; i++) {
  454.                 B.Append(point[i]);
  455.             }
  456.         }
  457.         return B;
  458.     }
  459.     virtual void Swap(int i, int j) override
  460.     {  
  461.         int a, b;
  462.         a = Get(i);
  463.         b = Get(j);
  464.         RemoveIndex(i);
  465.         RemoveIndex(j - 1);
  466.         InsertAt(i, b);
  467.         InsertAt(j, a);
  468.     }
  469.  
  470.     virtual void Show() override
  471.     {
  472.         int i;
  473.         for (i = 0; i < Length; i++) {
  474.             cout << point[i] << " ";
  475.         }
  476.         cout << endl;
  477.     }
  478.  
  479.     ~ArraySequence() {}
  480. };
  481.  
  482. template <typename TElement> class Sorter {
  483. public:
  484.     virtual void Sort(Sequence<TElement>&) = 0;
  485.  
  486. };
  487.  
  488. template <typename TElement, typename Cmp>
  489. class InsertionSort
  490.     : public Sorter<TElement>
  491. {
  492. private:
  493.     Cmp m_compare;
  494.  
  495. public:
  496.     InsertionSort() = delete;
  497.     InsertionSort(Cmp cmp) : m_compare(cmp)
  498.     {}; //конструктор
  499.     InsertionSort(const InsertionSort&) = default;
  500.     InsertionSort& operator=(const InsertionSort&) = default; //оператор копирования
  501.     void Sort(Sequence<TElement>& seq) override
  502.     {
  503.         int i, j;
  504.         for (i = 1; i < seq.getLength(); i++) //первый элемент не трогаем
  505.         {
  506.             for(j=i; j>0 && m_compare(seq.Get(j - 1), seq.Get(j))==1; j--) //ищем место для вставки
  507.             {
  508.                 seq.Swap(j - 1, j);
  509.             }
  510.         }
  511.     };
  512. };
  513.  
  514. int randomazer(int min, int max)
  515. {
  516.     float random;
  517.     random = rand();
  518.     random = (random / RAND_MAX) * (max - min) + min;
  519.     return((int)random);
  520. }
  521.  
  522. void test1(ArraySequence<int> A, ArraySequence<int> A2)
  523. {
  524.     A.getIsEmpty();
  525.     A.getLength();
  526.     cout << endl;
  527.     A.Append(23);
  528.     A.getLength();
  529.     A.GetFirst();
  530.     A.GetLast();
  531.     A.Get(0);
  532.     A.Get(-1);
  533.     A.Get(1);
  534.     cout << endl;
  535.     A.Append(43);
  536.     A.Show();
  537.     A.getLength();
  538.     A.GetFirst();
  539.     A.GetLast();
  540.     A.Get(0);
  541.     A.Get(1);
  542.     A.Get(-1);
  543.     A.Get(2);
  544.     cout << endl;
  545.     A.Prepend(53);
  546.     A.getLength();
  547.     A.GetFirst();
  548.     A.GetLast();
  549.     A.Get(0);
  550.     A.Get(1);
  551.     A.Get(-1);
  552.     A.Get(3);
  553.     cout << endl;
  554.     A2 = A.GetSubsequence(1, 1);
  555.     A2.getLength();
  556.     A2.GetFirst();
  557.     A2.GetLast();
  558.     cout << endl;
  559. }
  560.  
  561. void test2(ListSequence<int> A, ListSequence<int> A2)
  562. {
  563.     A.getIsEmpty();
  564.     A.getLength();
  565.     cout << endl;
  566.     A.Append(23);
  567.     A.getLength();
  568.     A.GetFirst();
  569.     A.GetLast();
  570.     A.Get(0);
  571.     A.Get(-1);
  572.     A.Get(1);
  573.     cout << endl;
  574.     A.Append(43);
  575.     A.Show();
  576.     A.getLength();
  577.     A.GetFirst();
  578.     A.GetLast();
  579.     A.Get(0);
  580.     A.Get(1);
  581.     A.Get(-1);
  582.     A.Get(2);
  583.     cout << endl;
  584.     A.Prepend(53);
  585.     A.getLength();
  586.     A.GetFirst();
  587.     A.GetLast();
  588.     A.Get(0);
  589.     A.Get(1);
  590.     A.Get(-1);
  591.     A.Get(3);
  592.     cout << endl;
  593.     A2 = A.GetSubsequence(1, 1);
  594.     A2.getLength();
  595.     A2.GetFirst();
  596.     A2.GetLast();
  597.     cout << endl;
  598. }
  599.  
  600. void lab0()
  601. {
  602.     int i = 1;
  603.     while (i) {
  604.         cout << "Which Sequence do you want?" << endl;
  605.         cout << "1 - Array Sequance" << endl;
  606.         cout << "2 - List Sequance" << endl;
  607.         cout << "0 - EXIT" << endl;
  608.         int n;
  609.         cin >> n;
  610.         cout << endl;
  611.         ArraySequence<int> A1;
  612.         ArraySequence<int> A2;
  613.         ListSequence<int> B1;
  614.         ListSequence<int> B2;
  615.         switch (n) {
  616.         case 1:
  617.             test1(A1, A2);
  618.             break;
  619.         case 2:
  620.             test2(B1, B2);
  621.             break;
  622.         case 0:
  623.             i = 0;
  624.             break;
  625.         default:
  626.             break;
  627.         }
  628.     }
  629. }
  630.  
  631.  
  632.  
  633. int main()
  634. {
  635.     auto cmp = [](int a, int b) { return (a < b) ? -1 : ((a > b) ? 1 : 0); };
  636.     InsertionSort<int, decltype(cmp)> InsSorter(cmp); //InsSorter - обьект сортировки
  637.     //ShellSorter<...> shSorter(...);
  638.     //shSorter.Sort(seq2);
  639.     ArraySequence<int> ArSeq;
  640.     ListSequence<int> ListSeq;
  641.  
  642.    
  643.     int k; //Заполнение списка рандомными числами
  644.     srand(time(nullptr));
  645.     for (int y = 0; y < 20; y++) {
  646.         k = randomazer(-20, 20);
  647.         ArSeq.Append(k);
  648.         ListSeq.Append(k);
  649.     }
  650.  
  651.     int i=1,j;
  652.     while (i)
  653.     {
  654.         cout << "Which sort do you want?" << endl;
  655.         cout << "1 - Intersection sort" << endl;
  656.         cout << "2 - Heapsort" << endl;
  657.         cout << "0 - EXIT" << endl;
  658.         int n;
  659.         cin >> n;
  660.         cout << endl;
  661.         switch (n)
  662.         {
  663.         case 1: //Intersection
  664.             j = 1;
  665.             while(j)
  666.             {
  667.                 cout << "Which sequance do you want?" << endl;
  668.                 cout << "1 - List" << endl;
  669.                 cout << "2 - Array" << endl;
  670.                 cout << "0 - BACK" << endl;
  671.                 cin >> n;
  672.                 cout << endl;
  673.                 switch (n)
  674.                 {
  675.                 case 1:
  676.                     cout << "Before: ";
  677.                     ListSeq.Show();
  678.                     InsSorter.Sort(ListSeq);
  679.                     cout << "After: ";
  680.                     ListSeq.Show();
  681.                     break;
  682.                 case 2:
  683.                     cout << "Before: ";
  684.                     ArSeq.Show();
  685.                     InsSorter.Sort(ArSeq);
  686.                     cout << "After: ";
  687.                     ArSeq.Show();
  688.                     break;
  689.                 case 0:
  690.                     j = 0;
  691.                     break;
  692.                 default:
  693.                     break;
  694.                 }
  695.                
  696.             }
  697.             break;
  698.         case 2: //Heap sort
  699.             j = 1;
  700.             while (j)
  701.             {
  702.                 cout << "Which sequance do you want?" << endl;
  703.                 cout << "1 - List" << endl;
  704.                 cout << "2 - Array" << endl;
  705.                 cout << "0 - BACK" << endl;
  706.                 cin >> n;
  707.                 cout << endl;
  708.                 switch (n)
  709.                 {
  710.                 case 1:
  711.                     break;
  712.                 case 2:
  713.                     break;
  714.                 case 0:
  715.                     j = 0;
  716.                     break;
  717.                 default:
  718.                     break;
  719.                 }
  720.  
  721.             }
  722.             break;
  723.         case 0:
  724.             i = 0;
  725.             break;
  726.         default:
  727.             break;
  728.         }
  729.     }
  730.  
  731.     return 0;
  732. }
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!