fork download
copy 
  1. #include <iostream>
  2. #include <cstring>
  3.  
  4. template<typename T>
  5. struct node {
  6. 	T val;
  7. 	node<T>* next;
  8. };
  9.  
  10. template<typename T>
  11. class single_list {
  12. private:
  13. 	node<T>* head;
  14. 	node<T>* tail;
  15. 	size_t   cnt;
  16. public:
  17. 	single_list(void):head(NULL),
  18. 	                  tail(NULL), 
  19. 	                  cnt(0){}
  20. 	~single_list(){
  21. 		this->clear();
  22. 	}
  23. 	single_list(const single_list&);
  24. 	single_list& operator = (const single_list&);
  25. public:
  26. 	//добавление элемента в конец
  27. 	bool add_back(const T& val){
  28. 		node<T>* p = new_node(val);
  29. 		if(p != NULL){
  30. 			if(head == NULL)
  31. 				head = tail = p;
  32. 			else {
  33. 				tail->next = p;
  34. 				tail = p;
  35. 			}
  36. 		}
  37. 		return (p != NULL);
  38. 	}
  39.  
  40. 	//сортировка
  41. 	template<typename Cmp>
  42. 	void sort(Cmp cmp){
  43. 		head = _merge_sort(head, &tail, cmp);
  44. 	}
  45.  
  46. 	//удаление всех элементов
  47. 	void clear(void){
  48. 		node<T>* tmp;
  49. 		while(head != NULL){
  50. 			tmp  = head;
  51. 			head = head->next;
  52. 			delete tmp;
  53. 		}
  54. 		tail = NULL;
  55. 		cnt  = 0;
  56. 	}	
  57.  
  58. 	size_t   size(void) const { return cnt; }
  59. 	node<T>* begin(void){ return head; }
  60. 	node<T>* begin(void) const { return head; }
  61. private:
  62. 	node<T>* new_node(const T& val){
  63. 		node<T>* p = new (std::nothrow) node<T>();
  64. 		if(p != NULL){
  65. 			p->val  = val;
  66. 			p->next = NULL;
  67. 			++cnt;
  68. 		}
  69. 		return p;
  70. 	}
  71.  
  72. 	//сортировкa слиянием
  73. 	template<typename Cmp>
  74. 	node<T>* _merge_sort(node<T>* lst, node<T>** ptail, Cmp cmp) {
  75. 		if((lst == NULL) || (lst->next == NULL))
  76. 			return lst;
  77. 		node<T>* ptr, *next, *end;
  78. 		node<T>* first = lst;
  79. 		node<T>* last  = lst;
  80.  
  81. 		ptr = next = end = NULL;
  82. 		for(node<T>* p = lst; (p != NULL) && (p->next != NULL); p = p->next->next) {
  83. 			last  = first;
  84. 			first = first->next;
  85. 		}
  86. 		last->next = NULL;
  87.  
  88. 		lst   = _merge_sort(lst,   ptail, cmp);
  89. 		first = _merge_sort(first, ptail, cmp);
  90.  
  91. 		while((lst != NULL) || (first != NULL)){ 
  92. 			if(first == NULL) {
  93. 				next = lst;
  94. 				lst  = lst->next;
  95. 			} else if(lst == NULL){
  96. 				next  = first;
  97. 				first = first->next;
  98. 			} else if(cmp(lst->val, first->val)){
  99. 				next = lst;
  100. 				lst  = lst->next;
  101. 			} else {
  102. 				next  = first;
  103. 				first = first->next;
  104. 			}
  105.  
  106. 			if(ptr == NULL)
  107. 				ptr = next;
  108. 			else
  109. 				end->next = next;
  110. 			end = next;
  111. 		}
  112. 		*ptail = end;
  113. 		return ptr;
  114. 	}
  115. };
  116.  
  117. //----------------------------------------------------------------------------
  118.  
  119. typedef struct {
  120. 	char l_name[16];
  121. 	int  year;
  122. } book;
  123.  
  124. struct book_cmp {
  125. 	bool operator () (const book& a, const book& b)const{
  126. 		int res = strcmp(a.l_name, b.l_name);
  127. 		return ((res < 0) || (! res && (a.year < b.year)));
  128. 	}
  129. };
  130.  
  131.  
  132. int main(void){
  133. 	const size_t N = 8;
  134. 	const book arr[N] = {
  135. 		{"wwww", 1997}, {"aaaa", 2000}, {"aaaa", 1997}, {"wwww", 1965},
  136. 		{"wwww", 1993}, {"cccc", 1997}, {"cccc", 1993}, {"aaaa", 1999}
  137. 	};
  138.  
  139. 	single_list<book> lst;
  140. 	for(size_t i = 0; i < N; ++i)
  141. 		lst.add_back(arr[i]);
  142.  
  143. 	lst.sort(book_cmp());
  144. 	for(const node<book>* p = lst.begin(); p != NULL; p = p->next)
  145. 		std::cout << p->val.l_name << ' ' << p->val.year << std::endl;
  146. 	lst.clear();
  147. 	return 0;
  148. }
Success #stdin #stdout 0s 3276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
aaaa 1997
aaaa 1999
aaaa 2000
cccc 1993
cccc 1997
wwww 1965
wwww 1993
wwww 1997
https://ideone.com/9QX2hn
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!