fork download
copy 
  1. #include <iostream>
  2. #include <cstdlib>
  3.  
  4. struct Node {
  5. 	int x;
  6. 	Node* Next, *Prev;
  7. };
  8.  
  9. class List {
  10. 	Node* Head, *Tail;
  11. public:
  12. 	List();
  13. 	~List();
  14. 	void  Show(void);
  15. 	void  Add(int x);
  16. 	Node* Partition(bool (pcmp)(int));
  17. 	void  Clear(void);
  18. 	void  Swap(Node* p1, Node* p2);
  19. };
  20.  
  21. List::List(void):Head(nullptr), Tail(nullptr){}
  22. List::~List(){
  23. 	this->Clear();
  24. }
  25.  
  26. void List::Show(void){
  27. 	for(auto p = Head; p != nullptr; p = p->Next)
  28. 		std::cout << p->x << ' ';
  29. 	std::cout << std::endl;
  30. }
  31.  
  32. void List::Add(int x){
  33. 	Node* p;
  34. 	try {
  35. 		p = new Node();
  36. 	} catch(...){
  37. 		return;
  38. 	}
  39. 	p->x    = x;
  40. 	p->Next = p->Prev = nullptr;
  41.  
  42. 	if(Head == nullptr)
  43. 		Head = Tail = p;
  44. 	else {
  45. 		p->Prev = Tail;
  46. 		Tail    = Tail->Next = p;
  47. 	}
  48. }
  49.  
  50. //перестановка
  51. Node* List::Partition(bool (pcmp)(int)){
  52. 	Node* p = Head;
  53. 	while((p != nullptr) && pcmp(p->x))
  54. 		p = p->Next;
  55.  
  56. 	for(Node* i = p; i != nullptr; i = i->Next){
  57. 		if(pcmp(i->x)){
  58. 			if(i != p){
  59. 				this->Swap(i, p);
  60. 				std::swap(i, p);
  61. 			}
  62. 			p = p->Next;
  63. 		}
  64. 	}
  65. 	return p;
  66. }
  67.  
  68. // обмен узлов
  69. void List::Swap(Node* p1, Node* p2) {
  70. 	if((p1 == nullptr) || (p2 == nullptr))
  71. 		return;
  72.  
  73. 	Node* prev1 = p1->Prev;
  74. 	Node* prev2 = p2->Prev;
  75.  
  76. 	if(prev1 != nullptr)
  77. 		prev1->Next = p2;
  78. 	p2->Prev = prev1;
  79.  
  80. 	if(prev2 != nullptr)
  81. 		prev2->Next = p1;
  82. 	p1->Prev = prev2;
  83.  
  84. 	Node* t1 = p1->Next;
  85. 	Node* t2 = p2->Next;
  86.  
  87. 	p1->Next = p2->Next;
  88. 	if(t2 != nullptr)
  89. 		t2->Prev = p1;
  90.  
  91. 	p2->Next = t1;
  92. 	if(t1 != nullptr)
  93. 		t1->Prev = p2;
  94.  
  95. 	if(Head == p1)
  96. 		Head = p2;
  97. 	else if(Head == p2)
  98. 		Head = p1;
  99.  
  100. 	if(Tail == p1)
  101. 		Tail = p2;
  102. 	else if(Tail == p2)
  103. 		Tail = p1;
  104. }
  105.  
  106. //удаление всех
  107. void List::Clear(void){
  108. 	Node* tmp;
  109. 	while(Head != nullptr){
  110. 		tmp  = Head;
  111. 		Head = Head->Next;
  112. 		delete tmp;
  113. 	}
  114. 	Tail = nullptr;
  115. }
  116.  
  117.  
  118. int main(void){
  119. 	List lst;
  120. 	lst.Add(100);
  121. 	for(int i = 0; i < 10; ++i)
  122. 		lst.Add(-9 + std::rand() % 19);
  123.  
  124. 	lst.Add(-200);
  125. 	lst.Show();
  126. 	lst.Partition([] (int x) { return (x < 0); });
  127. 	lst.Show();
  128. 	return 0;
  129. }
Success #stdin #stdout 0s 3460KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
100 -7 6 -6 -6 1 -1 1 2 -7 -2 -200 
-7 -6 -6 -1 -7 -2 -200 1 2 6 1 100
https://ideone.com/YQeaA3
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!