SHARE
TWEET

lab0 double_connected lists ver 4.0

allekco Dec 1st, 2019 84 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <ostream>
  3. #include <fstream>
  4. #include <string>
  5.  
  6. using namespace std;
  7.  
  8. template <typename TElement> struct Node //узел
  9. {
  10.     TElement value;
  11.     Node<TElement>* next;
  12.     Node<TElement>* prev;//Указатели на адреса следующего и предыдущего элементов списка
  13. };
  14.  
  15. template <typename TElement> class ListSequence {
  16. private:
  17.     int Length;
  18.     Node<TElement>* head;
  19.     Node<TElement>* tail;
  20. public:
  21.     void Init() {
  22.         head = NULL;
  23.         tail = NULL;
  24.         Length = 0;
  25.     }
  26.    
  27.     void Append(TElement item) {
  28.         struct Node<TElement>* temp;
  29.         temp = (struct Node<TElement>*)malloc(sizeof(Node<TElement>));
  30.         temp->value = item;
  31.         if (head == NULL) { //если список пустой
  32.             head = temp;
  33.             tail = temp;
  34.             head->prev = NULL;
  35.             tail->next = NULL;
  36.             Length = 1;
  37.         }
  38.         else { //список не пустой
  39.             temp->prev = tail;
  40.             tail->next = temp;
  41.             tail = temp;
  42.             tail->next = NULL;
  43.             Length += 1;
  44.         }
  45.     }
  46.  
  47.     void Prepend(TElement item) {
  48.         struct Node<TElement>* temp;
  49.         temp = (struct Node<TElement>*)malloc(sizeof(Node<TElement>));
  50.         temp->prev = NULL;
  51.         temp->value = item;
  52.         if (head == NULL) { //если список пустой
  53.             head = temp;
  54.             tail = temp;
  55.             temp->next = NULL;
  56.             Length = 1;
  57.         }
  58.         else { //список не пустой
  59.             temp->next = head;
  60.             head = temp;
  61.             Length += 1;
  62.         }
  63.     }
  64.  
  65.     void InsertAt(int index, TElement item) {
  66.         if (index == 1) return Prepend(item);
  67.         if (index == Length + 1) return Append(item);
  68.         if (index < 1 || index > Length + 1)
  69.             cout << "This index out of length" << endl;
  70.         else {
  71.             struct Node<TElement>* temp;
  72.             struct Node<TElement>* p;
  73.             temp = (struct Node<TElement>*)malloc(sizeof(Node));
  74.             int i;
  75.             p = head;
  76.             cout << p->value << endl;
  77.             for (i = 1; i < index; i++) {
  78.                 p = p->next;
  79.                 cout << p->value << endl;
  80.             }
  81.             temp->value = item;
  82.             temp->prev = p->prev;
  83.             temp->next = p;
  84.             p=p->prev;
  85.             p->next = temp;
  86.             p = temp->next;
  87.             p->prev = temp;
  88.             Length += 1;
  89.         }
  90.     }
  91.  
  92.     int getLength() {
  93.         cout << "Lenght of sequence: ";
  94.         cout << Length << endl;
  95.         return Length;
  96.     }
  97.  
  98.     int getIsEmpty() {
  99.         if (Length == 0) {
  100.             cout << "Sequence is empty" << endl;
  101.             return 1;
  102.         }
  103.         else {
  104.             cout << "Sequence isn't empty" << endl;
  105.             return -1;
  106.         }
  107.     }
  108.  
  109.     TElement Get(TElement index) {
  110.         if ((Length <= index) || (index < 0)) {
  111.             cout << "Element with index " << index << " didn't find" << endl;
  112.             return -1;
  113.         }
  114.         else {
  115.             int i;
  116.             Node<TElement>* temp;
  117.             temp = head;
  118.             for (i = 0; i < index; i++) {
  119.                 temp = temp->next;
  120.             }
  121.             cout << "Element with index " << index << ": ";
  122.             cout << temp->value << endl;
  123.             return temp->value;
  124.         }
  125.     }
  126.  
  127.     TElement GetFirst() {
  128.         cout << "First element. ";
  129.         return Get(0);
  130.     }
  131.  
  132.     TElement GetLast() {
  133.         cout << "Last element. ";
  134.         return Get(Length - 1);
  135.     }
  136.  
  137.     void Remove(TElement item) {
  138.         int i;
  139.         Node* p = head;
  140.         Node* p2 = head;
  141.         if (head->value == item) {
  142.             RemoveFirst();
  143.             Length -= 1;
  144.         }
  145.         else {
  146.             for (i = 1; i < Length; i++) {
  147.                 if ((p->next->value == item) && (p->next->next != NULL)) {
  148.                     Length -= 1;
  149.                     p->next = p->next->next;
  150.                     p = p->next;
  151.                     p->prev = p2;
  152.                     break;
  153.                 }
  154.                 if ((p->next->value == item) && (p->next->next == NULL)) {
  155.                     RemoveLast();
  156.                     break;
  157.                 }
  158.                 p = p->next;
  159.                 p2 = p2->next;
  160.             }
  161.         }
  162.     }
  163.  
  164.     void RemoveFirst() {
  165.         if (head == tail) {
  166.             head = NULL;
  167.             tail = NULL;
  168.         }
  169.         else {
  170.             Node* q = head;
  171.             head = q->next;
  172.             q->next->prev = head;
  173.         }
  174.     }
  175.  
  176.     void RemoveLast() {
  177.         Node* l = tail;
  178.         tail = l->prev;
  179.         l->prev->next = tail;
  180.         tail->next = NULL;
  181.     }
  182.  
  183.     ListSequence GetSubsequence(int startIndex, int endIndex) {
  184.         ListSequence B;
  185.         B.Init();
  186.         Node<TElement>* p = head;
  187.         if ((startIndex < 0) || (endIndex < 0) || (endIndex < startIndex) || (endIndex >= Length)) {
  188.             cout << "Error with index" << endl;
  189.         }
  190.         else {
  191.             for (int i = 0; i < startIndex; i++) {
  192.                 p = p->next;
  193.             }
  194.             for (int j = startIndex; j <= endIndex; j++) {
  195.                 B.Append(p->value);
  196.                 p = p->next;
  197.             }
  198.         }
  199.         return B;
  200.     }
  201.  
  202.     void Show() {
  203.         Node<TElement>* temp = head;
  204.         while (temp != NULL) {
  205.             cout << temp->value << " ";
  206.             temp = temp->next;
  207.         }
  208.         cout << endl;
  209.     }
  210. };
  211.  
  212.  
  213.  
  214. /*наследование
  215. виртуальный метод
  216. */
  217.  
  218. int main() {
  219.     ListSequence<char> A1;
  220.     A1.Init();
  221.     A1.Append('a');
  222.     A1.Append('b');
  223.     A1.Show();
  224.     A1.getLength();
  225.  
  226.     cout << endl;
  227.     cout << endl;
  228.     ListSequence<int> A;
  229.     A.Init();
  230.     A.getIsEmpty();
  231.     A.getLength();
  232.     cout << endl;
  233.     A.Append(23);
  234.     A.getLength();
  235.     A.GetFirst();
  236.     A.GetLast();
  237.     A.Get(0);
  238.     A.Get(-1);
  239.     A.Get(1);
  240.     cout << endl;
  241.     A.Append(43);
  242.     A.Show();
  243.     A.getLength();
  244.     A.GetFirst();
  245.     A.GetLast();
  246.     A.Get(0);
  247.     A.Get(1);
  248.     A.Get(-1);
  249.     A.Get(2);
  250.     cout << endl;
  251.     A.Prepend(53);
  252.     A.getLength();
  253.     A.GetFirst();
  254.     A.GetLast();
  255.     A.Get(0);
  256.     A.Get(1);
  257.     A.Get(-1);
  258.     A.Get(3);
  259.     cout << endl;
  260.     ListSequence<int> A2;
  261.     A2 = A.GetSubsequence(1, 1);
  262.     A2.getLength();
  263.     A2.GetFirst();
  264.     A2.GetLast();
  265.  
  266.     return 0;
  267. }
RAW Paste Data
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
 
Top