fork(2) download
copy 
  1. #include <iostream>
  2. #include <cstdlib>
  3.  
  4. struct node {
  5. 	int   num;
  6. 	node* next;
  7. };
  8.  
  9. struct slist {
  10. 	node* head;
  11. 	node* tail;
  12. 	slist(void):head(NULL), tail(NULL){}
  13. };
  14.  
  15. bool slist_add(slist* lst, int num);
  16. void slist_clear(slist* lst);
  17.  
  18.  
  19. //сортировка односвязного списка слиянием
  20. void slist_sort(node*& head, node*& tail) {
  21. 	if((head == NULL) || (head->next == NULL))
  22. 		return;
  23.  
  24. 	node* ptr, *next, *end, *pos;
  25. 	node* iter = head;
  26. 	node* last = head;
  27.  
  28. 	ptr = next = end = NULL;
  29. 	pos = head;
  30. 	while((pos != NULL) && (pos->next != NULL)){
  31. 		last = iter;
  32. 		iter = iter->next;
  33. 		pos  = pos->next->next;
  34. 	}
  35. 	last->next = NULL;
  36.  
  37. 	slist_sort(head, tail);
  38. 	slist_sort(iter, tail);
  39.  
  40. 	while((head != NULL) || (iter != NULL)) {
  41. 		if(iter == NULL) {
  42. 			next = head;
  43. 			head = head->next;
  44. 		} else if(head == NULL) {
  45. 			next = iter;
  46. 			iter = iter->next;
  47. 		} else if(head->num < iter->num) {
  48. 			next = head;
  49. 			head = head->next;
  50. 		} else {
  51. 			next = iter;
  52. 			iter = iter->next;
  53. 		}
  54.  
  55. 		if(ptr == NULL) 
  56. 			ptr = next;
  57. 		else
  58. 			end->next = next;
  59. 		end = next;
  60. 	}
  61. 	head = ptr;
  62. 	tail = end;
  63. }
  64.  
  65.  
  66. //слияние списков
  67. void slist_union(slist* l3, slist* l1, slist* l2){
  68. 	node*  p1 = l1->head;
  69. 	node*  p2 = l2->head; 
  70. 	node** r3 = &l3->head;
  71.  
  72. 	while((p1 != NULL) && (p2 != NULL)){
  73. 		if(p1->num < p2->num){
  74. 			*r3 = p1;
  75. 			p1  = p1->next;
  76. 		} else {
  77. 			if(p1->num == p2->num){
  78. 				*r3 = p1;
  79. 				p1  = p1->next;
  80. 				r3  = &(*r3)->next;
  81. 			}
  82. 			*r3 = p2;
  83. 			p2  = p2->next;
  84. 		}
  85. 		r3 = &(*r3)->next;
  86. 	}
  87.  
  88. 	if(p1 != NULL){
  89. 		*r3      = p1;
  90. 		l3->tail = l1->tail; 
  91. 	} else {
  92. 		*r3      = p2;
  93. 		l3->tail = l2->tail;
  94. 	}
  95. 	l1->head = l1->tail =
  96. 	l2->head = l2->tail = NULL;
  97. }
  98.  
  99.  
  100. int main(void){
  101. 	slist l1;
  102. 	for(int i = 0; i < 10; ++i)
  103. 		slist_add(&l1, std::rand() % 10);
  104.  
  105. 	slist l2;
  106. 	for(int j = 0; j < 20; ++j)
  107. 		slist_add(&l2, std::rand() % 20);		
  108.  
  109. 	//сортируем списки
  110. 	slist_sort(l1.head, l1.tail);
  111. 	slist_sort(l2.head, l2.tail);
  112.  
  113. 	slist l3;
  114. 	slist_union(&l3, &l1, &l2);
  115.  
  116. 	const node* p = l3.head;
  117. 	while(p != NULL){
  118. 		std::cout << p->num << ' ';
  119. 		p = p->next;
  120. 	}
  121. 	slist_clear(&l3);
  122. 	return 0;
  123. }
  124.  
  125. //вставка в конец списка
  126. bool slist_add(slist* lst, int num){
  127. 	node* ptr = new (std::nothrow) node();
  128. 	if(ptr != NULL){
  129. 		ptr->num  = num;
  130. 		ptr->next = NULL;
  131. 		if(lst->head == NULL)
  132. 			lst->head = lst->tail = ptr;
  133. 		else {
  134. 			lst->tail->next = ptr;
  135. 			lst->tail = ptr;
  136. 		}
  137. 	}
  138. 	return (ptr != NULL);
  139. }
  140.  
  141. //удаление списка
  142. void slist_clear(slist* lst){
  143. 	node* tmp;
  144. 	while(lst->head != NULL){
  145. 		tmp       = lst->head;
  146. 		lst->head = lst->head->next;
  147. 		delete tmp;
  148. 	}
  149. 	lst->tail = NULL;
  150. }
Success #stdin #stdout 0s 3228KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 1 2 2 2 2 3 3 3 3 5 5 6 6 6 6 7 7 7 7 8 9 9 10 10 11 12 15 16 19
https://ideone.com/EdfoAu
language:
C++ (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!