Advertisement
Guest User

Untitled

a guest
Mar 24th, 2019
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.27 KB | None | 0 0
  1. #include <iostream>;
  2. using namespace std;
  3. struct Node {
  4.     int value;
  5.     Node *next;
  6.     Node *prev;
  7.   };
  8. void add(Node **first, int value) {  //2 звездочки так как изменяем
  9.     if (*first == NULL) {    //  если нет первого элемента,
  10.         *first = new Node; //выделение памяти
  11.         (*first)->value = value;    // то присваеваем новому значению
  12.         (*first)->next = (*first)->prev = *first; // присваиваем ссылки на предыдущий и следующий элементы списка
  13.     }
  14.     else { // если значение первого элемента задано,
  15.         Node *newItem = new Node, // создаем новый элемент
  16.             *lastItem = (*first)->prev; // и запоминаем указатель на последний
  17.         newItem->value = value; // присваиваем новому элементу его значение
  18.         newItem->prev = lastItem; // указываем на последний (теперь предпоследний) элемент списка
  19.         newItem->next = (*first); // и  на первый соответственно
  20.         lastItem->next = (*first)->prev = newItem; // теперь последний элемент знает, что после него идет новый элемент
  21.              // а первый эл-т знает, что перед ним новый
  22.     }
  23. }
  24.  
  25. void remove(Node **first, int index) {
  26.     if (index == 0 && ((*first)->next == (*first))) { // если index указывает на первый элемент и первый элемент ссылается на себя
  27.                                                 // то размер списка равен единице или нулю, а после удаления размер списка точно нулевой
  28.         (*first)->value = NULL;// пустое значение перовго элемента - признак пустого списка
  29.                             // менять сссылки не надо, они и так должны указывать на первый элемент
  30.     }
  31.     else {
  32.         Node * removedItem = *first; // создаем указатель на удаляемый элемент. Изначально указывает на первый
  33.         while (index != 0) { // пока index != 0
  34.             removedItem = removedItem->next; // смещаем указатель на следующий элемент списка
  35.             index--; // уменьшаем индекс
  36.         }
  37.         removedItem->next->prev = removedItem->prev;
  38.         removedItem->prev->next = removedItem->next;
  39.         delete removedItem;
  40.     }
  41. }
  42.  
  43. int value(Node *first, int index) {
  44.     Node * indItem = first; // создаем указатель на искомый элемент. Изначально указывает на первый
  45.     while (index != 0) { // пока index != 0
  46.         indItem = indItem->next; // смещаем указатель на следующий элемент списка
  47.         index--; // уменьшаем индекс
  48.     }
  49.  
  50.     return indItem->value; // возвращаем значение по индексу
  51.  
  52. }
  53.  
  54. int length(Node *first) {
  55.     if (first == NULL) // если в первом элементе не задано значение, то список пустой, возвращаем "0"
  56.         return 0;
  57.     Node * indItem = first;// создаем указатель на элемент. Изначально указывает на первый
  58.     int size = 1; // переменная для поиска размера
  59.     while (indItem->next != first) { // пока элемент не укажет на первый
  60.         indItem = indItem->next; // смещаем текущий указатель на следующий элемент в списке
  61.         size++; // увеличиваем размер на 1
  62.     }
  63.     return size;
  64. }
  65. void print(Node *first)
  66. {
  67.     int len = length(first);
  68.     for (int i = 0; i < len; i++)
  69.         cout << value(first, i) << " ";
  70.     cout << endl;
  71. }
  72. int main()
  73. {
  74.  
  75.     Node *first = NULL;
  76.      add(&first, 1);//добавление в конец списка
  77.      add(&first, 2);
  78.      add(&first, 3);
  79.      add(&first, 4);
  80.      remove(&first, 1);//удаление 1 элемента
  81.  
  82.     cout << value (first, 2) << endl;
  83.  
  84.     cout << length (first) << endl;
  85.  
  86.     system("pause");
  87.  
  88.     return 0;
  89.  
  90. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement