SHARE
TWEET

lab0 double_connected lists ver 2.0

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