vadimk772336

Untitled

Oct 27th, 2021
955
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <list>
  4. using namespace std;
  5.  
  6. struct heap_elements;
  7.  
  8. struct list_segments
  9. { //Структура отрезка - элемента списка отрезок
  10.    
  11.     int l;
  12.     int r;
  13.     int status; // Но лучше просто считать это элементов класса и делать del по указателю
  14.     struct list_segments* next;
  15.     struct list_segments* prev;
  16.     int to_heap; //Указатель на себя в куче (элемент структуры heap_elements)
  17. };
  18.  
  19. struct heap_elements {
  20.     int l;
  21.     int r;
  22.     int position;
  23.     list_segments *to_list; //Указатель на себя в списке отрезков.
  24. };
  25.  
  26.  
  27. bool operator<(const heap_elements& a, const heap_elements& b)
  28. {
  29.     int len_a = a.r-a.l;
  30.     int len_b = b.r-b.l;
  31.    
  32.     if ( (a.r-a.l < b.r-b.l) )
  33.         return true;
  34.     if ( (a.r-a.l == b.r-b.l) & (a.l > b.l))
  35.         return true;
  36.  
  37.     return false;
  38. }
  39.  
  40.  
  41. class Heap
  42. {
  43.     static const int SIZE = 100; // максимальный размер кучи
  44.     struct heap_elements* h; // указатель на массив кучи
  45.     int HeapSize; // размер кучи
  46. public:
  47.     Heap(); // конструктор кучи
  48.     void add(heap_elements); // добавление элемента кучи
  49.     void outHeap(); // вывод элементов кучи в форме кучи
  50.     void out(); // вывод элементов кучи в форме массива
  51.     void siftup();
  52.     void siftdown(int);
  53.     void delete_vertex(int);
  54. };
  55.  
  56. Heap::Heap()
  57. {
  58.     h = new heap_elements[SIZE];
  59.     HeapSize = 0;
  60. }
  61.  
  62. void Heap::siftup()
  63. {
  64.     int i, parent;
  65.     i = HeapSize - 1;
  66.     parent = (i - 1) / 2;
  67.     while (parent >= 0 && i > 0)
  68.     {
  69.         if (h[parent] < h[i])
  70.         {
  71.             heap_elements temp = h[i];
  72.             h[i] = h[parent];
  73.             h[parent] = temp;
  74.             h[i].position = i;
  75.             h[parent].position = parent;
  76.         }
  77.         i = parent;
  78.         parent = (i - 1) / 2;
  79.     }
  80. }
  81.  
  82. void Heap::add(heap_elements elem)
  83. {
  84.  
  85.     h[HeapSize] = elem;
  86.     //h[HeapSize].r = elem.r;
  87.     //h[HeapSize].to_list=elem.to_list;
  88.     h[HeapSize].position = HeapSize;
  89.     HeapSize++;
  90.     siftup();
  91.     /*
  92.   parent = (i-1)/2;
  93.   while(parent >= 0 && i > 0)  {
  94.     if(h[i] > h[parent]) {
  95.       int temp = h[i];
  96.       h[i] = h[parent];
  97.       h[parent] = temp;
  98.     }
  99.     i = parent;
  100.     parent = (i-1)/2;
  101.   }
  102.   */
  103. }
  104.  
  105. void Heap::siftdown(int position)
  106. {
  107.     int i, parent;
  108.     int max_child;
  109.     i = position;
  110.     int child1 = 2 * i + 1;
  111.     int child2 = 2 * i + 2;
  112.     if (h[child2] < h[child1])
  113.         max_child = child1;
  114.     else
  115.         max_child = child2;
  116.  
  117.     while (child1 < HeapSize)
  118.     {
  119.         if (child1 == HeapSize - 1)
  120.         {
  121.             max_child = child1;
  122.         }
  123.         else if (h[child2] < h[child1])
  124.             max_child = child1;
  125.         else
  126.             max_child = child2;
  127.  
  128.         if (h[i] < h[max_child])
  129.         {
  130.             heap_elements temp = h[i];
  131.             h[i] = h[max_child];
  132.             h[max_child] = temp;
  133.             h[i].position = i;
  134.             h[max_child].position = max_child;
  135.         }
  136.         i = max_child;
  137.         child1 = 2 * i + 1;
  138.         child2 = 2 * i + 2;
  139.     }
  140. }
  141.  
  142. void Heap::delete_vertex (int position)
  143. {
  144.  
  145.     h[position] = h[HeapSize - 1];
  146.     h[HeapSize - 1].l = 0;
  147.     h[HeapSize - 1].r = 0;
  148.     HeapSize--;
  149.     siftdown(position);
  150. }
  151.  
  152. void Heap::out(void)
  153. {
  154.     for (int i = 0; i < HeapSize; i++)
  155.     {
  156.         cout << h[i].l << " "<<h[i].r<<" ";
  157.     }
  158.     cout << endl;
  159. }
  160.  
  161.  
  162. // LIST SEGMENT BEGIN -----------------------------------------
  163. class LIST_SEGMENTS
  164. {
  165.     struct list_segments * Head, * Tail;
  166.     struct list_segments* element;
  167.     int Count;
  168.  
  169. public:
  170.     LIST_SEGMENTS(); // конструктор кучи
  171.     //LIST_SEGMENTS(int, int, int, struct list_segments*, struct list_segments*,int); // конструктор кучи
  172.     void add(int, int, int, list_segments*, int);
  173.     void delete_segment(list_segments*);
  174.     void Print();
  175.     void add_head(int,int,int,int);
  176.     list_segments* get_head();
  177.     // void out(); // вывод элементов кучи в форме массива
  178. };
  179.  
  180. LIST_SEGMENTS::LIST_SEGMENTS()
  181. {
  182.    // Изначально список пуст
  183.    Head = Tail = NULL;
  184.    Count = 0;
  185. }
  186. void LIST_SEGMENTS::add_head(int l,int r,int status,int to_heap)
  187. {
  188.    // новый элемент
  189.    list_segments * temp = new list_segments;
  190.  
  191.    // Предыдущего нет
  192.    temp->prev = 0;
  193.    // Заполняем данные
  194.    temp->l = l;
  195.    temp->r = r;
  196.    temp->status = status;
  197.    // Следующий - бывшая голова
  198.    temp->next = Head;
  199.  
  200.    // Если элементы есть?
  201.    if(Head != 0)
  202.       Head->prev = temp;
  203.  
  204.    // Если элемент первый, то он одновременно и голова и хвост
  205.    if(Count == 0)
  206.       Head = Tail = temp;
  207.    else
  208.       // иначе новый элемент - головной
  209.       Head = temp;
  210.  
  211.    Count++;
  212. }
  213.  
  214. /*
  215. LIST_SEGMENTS::LIST_SEGMENTS(struct list_segments* segment,int l, int r, int status, struct list_segments* next, struct list_segments* prev,
  216.     int to_heap)
  217. {
  218.     segment = new list_segments;
  219.     segment.l = l;
  220.     segment.r = r;
  221.     segment.status = status;
  222.     segment.next = next;
  223.     segment.prev = prev;
  224.     segment.to_heap = to_heap;
  225. }
  226. */
  227.  
  228. void LIST_SEGMENTS::add(int l, int r, int status, list_segments* segment, int to_heap)
  229. {
  230.     //struct list_segments* next;
  231.     //struct list_segments* prev;
  232.     //prev = segment;
  233.     //*next = &(segment->next);
  234.     list_segments* segment2 = new list_segments;
  235.     //LIST_SEGMENTS(elem,l, r, status, &(segment->next), &segment, to_heap);
  236.     segment2->l = l;
  237.     segment2->r = r;
  238.     segment2->status = status;
  239.     segment2->next = segment->next;
  240.     segment2->prev = segment;
  241.     segment2->to_heap = to_heap;
  242.     if (segment->next!=NULL)
  243.         segment->next->prev = segment2;
  244.     segment->next = segment2;
  245.     Count++;
  246.  
  247. }
  248. void LIST_SEGMENTS::delete_segment(list_segments* segment)
  249. {
  250.     if (segment->next!=NULL)
  251.         segment->next->prev = segment->prev;
  252.     if (segment->prev!=NULL)
  253.         segment->prev->next = segment->next;
  254.     else Head = segment->next;    
  255.     delete segment; // или free или любое другое удаление хзхзхз
  256. }
  257. void LIST_SEGMENTS::Print()
  258. {
  259.    // Если в списке присутствуют элементы, то пробегаем по нему
  260.    // и печатаем элементы, начиная с головного
  261.     list_segments * temp = Head;
  262.     cout << "( ";
  263.     while(temp->next != NULL)
  264.     {
  265.         cout << temp->l << ", " << temp->r << ";";
  266.         temp = temp->next;
  267.     }
  268.  
  269.     cout << temp->l <<"," << temp->r <<  " )\n";
  270. }
  271. list_segments* LIST_SEGMENTS::get_head(){
  272.     return Head;
  273. }
  274.  
  275. // LIST SEGMENT END
  276.  
  277. int main()
  278. {
  279.  
  280.     //-------------------------------------------------------- REAL ЗАГАТОВКА
  281.     //Массив указателей на отрезки (list_segments)
  282.     vector<list_segments*> requests;
  283.    
  284.     Heap heap;
  285.    
  286.     int N,M,K;
  287.  
  288.    
  289.     cin >> N;
  290.     // Узнали N, можно добавить весь массив в структуры данных
  291.    
  292.     //Создание вершины и добавление в кучу
  293.     heap_elements vertex;
  294.     vertex.l = 1;
  295.     vertex.r = N;
  296.     vertex.to_list = NULL;
  297.     vertex.position = 0;
  298.     heap.add(vertex);
  299.  
  300.     //Cоздание списка отрезков
  301.     list_segments segment; //Создаем отрезок-структуру, заполняем
  302.     segment.l = 1;
  303.     segment.r = N;
  304.     segment.status = 1;
  305.     //segment.position = 0; //Не надо, можно просто удалять
  306.     segment.next = NULL;
  307.     segment.prev = NULL;
  308.     segment.to_heap  = 0; //?????????????
  309.    
  310.     LIST_SEGMENTS List; //Создаём пустой двусязный список
  311.     List.add_head(1,N,1,0);
  312.     vertex.to_list = List.get_head(); //Записываем в вершину запись её копии в списке отрезков (можно ли это сделать просто &segment?)
  313.    
  314.     heap.out();
  315.     List.Print();
  316.    
  317.     return 0;
  318. }
  319.  
RAW Paste Data