fork download
copy 
  1. // Main.cpp
  2.  
  3. #include <cstdlib>
  4. #include <ctime>
  5. #include <iostream>
  6. #include "mergClassM.h"
  7. //#include "DoublyLinkedList.hpp"
  8.  
  9. using namespace std;
  10.  
  11. int compare(const int& a, const int& b)
  12. {
  13. 	return a - b;
  14. }
  15.  
  16.  
  17. template<class T>
  18. class DoublyLinkedList;
  19.  
  20. // Link.hpp
  21.  
  22. template<class T>
  23. class Link
  24. {
  25. private:
  26. 	T data;
  27. 	Link<T> *next;
  28. 	Link<T> *previous;
  29. public:
  30. 	Link(T data);
  31. 	Link(T data, Link<T> * next, Link<T> * previous);
  32. 	void displayLink();
  33. 	T getData();
  34. 	void setData(T data);
  35. 	Link<T> *getNext();
  36. 	void setNext(Link<T> *next);
  37. 	Link<T> *getPrevious();
  38. 	void setPrevious(Link<T> *previous);	
  39. 	friend std::ostream& operator<< (std::ostream& print, Link<T>& obj);
  40. 	friend class DoublyLinkedList<T>;
  41. };
  42.  
  43. template<class T>
  44. Link<T>::Link(T data)
  45. 	: Link(data, nullptr, nullptr)
  46. {
  47. }
  48.  
  49. template<class T>
  50. Link<T>::Link(T data, Link<T> * next, Link<T> * previous)
  51. 	: data(data), next(next), previous(previous)
  52. {
  53. }
  54.  
  55. template<class T>
  56. void Link<T>::displayLink()
  57. {
  58. 	std::cout << getData() << " ";
  59. }
  60.  
  61. template<class T>
  62. T Link<T>::getData()
  63. {
  64. 	return data;
  65. }
  66.  
  67. template<class T>
  68. void Link<T>::setData(T data)
  69. {
  70. 	this->data = data;
  71. }
  72.  
  73. template<class T>
  74. Link<T> *Link<T>::getNext()
  75. {
  76. 	return next;
  77. }
  78.  
  79. template<class T>
  80. void Link<T>::setNext(Link<T> *next)
  81. {
  82. 	this->next = next;
  83. }
  84.  
  85. template<class T>
  86. Link<T> *Link<T>::getPrevious()
  87. {
  88. 	return previous;
  89. }
  90.  
  91. template<class T>
  92. void Link<T>::setPrevious(Link<T> *previous)
  93. {
  94. 	this->previous = previous;
  95. }
  96.  
  97.  
  98. template <class T>
  99. std::ostream& operator<<(std::ostream& print, Link<T> & L)
  100. {
  101. 	print << L.getData();
  102. 	return print;
  103. }
  104.  
  105. //DoublyLinkedList.hpp
  106.  
  107.  
  108. //#include "Link.hpp"
  109.  
  110. template<class T>
  111. class DoublyLinkedList
  112. {
  113. private:
  114. 	Link<T> *first;
  115. 	Link<T> *last;
  116. 	Link<T> *headdel();
  117. 	void tailins(Link<T> *p);
  118. public:
  119. 	DoublyLinkedList();
  120. 	~DoublyLinkedList();
  121. 	Link<T> *getFirst();
  122. 	void setFirst(Link<T> *first);
  123. 	Link<T> *getLast();
  124. 	void setLast(Link<T> *first);
  125. 	bool isEmpty();
  126. 	Link<T> *find(T key);
  127. 	void insertFirst(T dd);
  128. 	void insertLast(T dd);
  129. 	void deleteFirst();
  130. 	void deleteLast();
  131. 	void insert(T k, int(*compare)(const T&, const T&));
  132. 	bool insertAfter(T key, T dd);
  133. 	void deleteKey(T key);
  134. 	void displayForward();
  135. 	void displayBackward();
  136. 	bool Split(DoublyLinkedList<T> &A, DoublyLinkedList<T> &B, int(*compare)(const T&, const T&));
  137. 	void Merge(DoublyLinkedList<T> &A, DoublyLinkedList<T> &B, int(*compare)(const T&, const T&));
  138. 	void MergeSort(int(*compare)(const T&, const T&));
  139. };
  140.  
  141. //template<class T>
  142. //using Link = typename DoublyLinkedList<T>::Link;
  143.  
  144. template<class T>
  145. DoublyLinkedList<T>::DoublyLinkedList()
  146. 	: first(nullptr), last(nullptr)
  147. {
  148. }
  149.  
  150. template<class T>
  151. DoublyLinkedList<T>::~DoublyLinkedList()
  152. {
  153. 	while (!isEmpty())
  154. 	{
  155. 		deleteFirst();
  156. 	}
  157. }
  158.  
  159. template<class T>
  160. Link<T> *DoublyLinkedList<T>::getFirst()
  161. {
  162. 	return first;
  163. }
  164.  
  165. template<class T>
  166. void DoublyLinkedList<T>::setFirst(Link<T> *first)
  167. {
  168. 	this->first = first;
  169. }
  170.  
  171. template<class T>
  172. Link<T> *DoublyLinkedList<T>::getLast()
  173. {
  174. 	return last;
  175. }
  176.  
  177. template<class T>
  178. void DoublyLinkedList<T>::setLast(Link<T> *last)
  179. {
  180. 	this->last = last;
  181. }
  182.  
  183. template<class T>
  184. bool DoublyLinkedList<T>::isEmpty()
  185. {
  186. 	return getFirst() == nullptr;
  187. }
  188.  
  189. template<class T>
  190. Link<T> *DoublyLinkedList<T>::find(T key)
  191. {
  192. 	Link<T> *current = getFirst();
  193. 	while (current != nullptr && !(current->getData == key))
  194. 		current = current->getNext();
  195. 	return current;
  196. }
  197.  
  198. template<class T>
  199. void DoublyLinkedList<T>::insertFirst(T dd)
  200. {
  201. 	Link<T> *newLink = new Link<T>(dd);
  202. 	if (isEmpty())
  203. 		setLast(newLink);
  204. 	else
  205. 		getFirst()->setPrevious(newLink);
  206. 	newLink->setNext(getFirst());
  207. 	setFirst(newLink);
  208. }
  209.  
  210. template <class T>
  211. void DoublyLinkedList<T>::insert(T value, int(*compare)(const T&, const T&))
  212. {
  213. 	// wskazanie na wskaźnik wskazujący węzeł następujący po nowo dodawanym
  214. 	Link<T> **addrNextPtr = &first; // adres pola składowego klasy, nie kopii wskaźnika zwracanego przez getFirst()
  215. 	// znajdujemy odpowiednie miejsce do wstawienia wartości
  216. 	while (*addrNextPtr && compare(value, (*addrNextPtr)->data) > 0)
  217. 	{
  218. 		addrNextPtr = &(*addrNextPtr)->next; // adres pola składowego węzła, nie kopii wskaźnika zwracanego przez getNext();
  219. 	}
  220.  
  221. 	// wskazanie na wskaźnik wskazujący węzeł poprzedzający nowo dodawany
  222. 	Link<T> **addrPrevPtr =
  223. 		*addrNextPtr // jeśli wstawiamy przed jakiś węzeł (jeśli jest kolejny węzeł)
  224. 		? &(*addrNextPtr)->previous // to wskazujemy adres poprzednika następnego węzła
  225. 		: &last; // w przeciwnym razie wskazujemy na adres ostatniego elementu
  226. 	//
  227. 	// powyższa "linijka" bardziej rozwięźle:
  228. 	// Link<T> **addrPrevPtr;
  229. 	// if (*addrNextPtr)
  230. 	// {
  231. 	// 	addrPrevPtr = &(*addrNextPtr)->previous;
  232. 	// }
  233. 	// else
  234. 	// {
  235. 	// 	addrPrevPtr = &last;
  236. 	// }
  237.  
  238. 	// tworzymy węzeł z odpowiednimi wskazaniami oraz ustawiamy odpowiednie wskazania na nowy węzeł
  239. 	*addrNextPtr = *addrPrevPtr = new Link<T>(value, *addrNextPtr, *addrPrevPtr);
  240. 	// powyższa linijka bardziej rozwięźle:
  241. 	// Link<T> *newNode = new Link<T>(value, *addrNextPtr, *addrPrevPtr);
  242. 	// *addrNextPtr = *addrPrevPtr = newNode;
  243. 	//
  244. 	// jeszcze bardziej rozwięźle:
  245. 	// Link<T> *newNode = new Link<T>(value);
  246. 	// newNode-next = *addrNextPtr;
  247. 	// newNode->previous = *addrPrevPtr;
  248. 	// *addrNextPtr = newNode;
  249. 	// *addrPrevPtr = newNode;
  250. }
  251.  
  252. template<class T>
  253. void DoublyLinkedList<T>::insertLast(T dd)
  254. {
  255. 	Link<T> *newLink = new Link<T>(dd);
  256. 	if (isEmpty())
  257. 	{
  258. 		setFirst(newLink);
  259. 	}
  260. 	else
  261. 	{
  262. 		getLast()->setNext(newLink);
  263. 		newLink->setPrevious(getLast());
  264. 	}
  265. 	setLast(newLink);
  266. }
  267.  
  268. template<class T>
  269. void DoublyLinkedList<T>::deleteFirst()
  270. {
  271. 	if (isEmpty())
  272. 		return;
  273. 	Link<T> *temp = getFirst();
  274. 	if (getFirst()->getNext() == nullptr)
  275. 		setLast(nullptr);
  276. 	else
  277. 		getFirst()->getNext()->setPrevious(nullptr);
  278. 	setFirst(getFirst()->getNext());
  279. 	delete temp;
  280. }
  281.  
  282. template<class T>
  283. void DoublyLinkedList<T>::deleteLast()
  284. {
  285. 	if (isEmpty())
  286. 		return;
  287. 	Link<T> *temp = getLast();
  288. 	if (getFirst()->getNext() == nullptr)
  289. 		setFirst(nullptr);
  290. 	else
  291. 		getLast()->getPrevious()->setNext(nullptr);
  292. 	setLast(getLast()->getPrevious());
  293. 	delete temp;
  294. }
  295.  
  296. template<class T>
  297. bool DoublyLinkedList<T>::insertAfter(T key, T dd)
  298. {
  299. 	Link<T> *current = find(key);
  300. 	if (current == nullptr)
  301. 		return false;
  302. 	Link<T> *newLink = new Link<T>(dd);
  303. 	if (current->getNext() == nullptr)
  304. 	{
  305. 		newLink->setNext(nullptr);
  306. 		setLast(newLink);
  307. 	}
  308. 	else
  309. 	{
  310. 		newLink->setNext(current->getNext());
  311. 		current->getNext()->setPrevious(newLink);
  312. 	}
  313. 	newLink->setPrevious(current);
  314. 	current->setNext(newLink);
  315. 	return true;
  316. }
  317.  
  318. template<class T>
  319. void DoublyLinkedList<T>::deleteKey(T key)
  320. {
  321. 	Link<T> *current = find(key);
  322. 	if (current == nullptr)
  323. 		return;
  324. 	if (current->getPrevious() == nullptr)
  325. 		setFirst(current->getNext());
  326. 	else
  327. 		current->getPrevious()->setNext(current->getNext());
  328. 	if (current->getNext() == nullptr)
  329. 		setLast(current->getPrevious());
  330. 	else
  331. 		current->getNext()->setPrevious(current->getPrevious());
  332. 	delete current;
  333. }
  334.  
  335. template<class T>
  336. void DoublyLinkedList<T>::displayForward()
  337. {
  338. 	std::cout << "List (first-->last): ";
  339. 	Link<T> *current = getFirst();
  340. 	while (current != nullptr)
  341. 	{
  342. 		current->displayLink();
  343. 		current = current->getNext();
  344. 	}
  345. 	std::cout << "\n";
  346. }
  347.  
  348. template<class T>
  349. void DoublyLinkedList<T>::displayBackward()
  350. {
  351. 	std::cout << "List (last-->first): ";
  352. 	Link<T> *current = getLast();
  353. 	while (current != nullptr)
  354. 	{
  355. 		current->displayLink();
  356. 		current = current->getPrevious();
  357. 	}
  358. 	std::cout << "\n";
  359. }
  360.  
  361. template <class T>
  362. Link<T> *DoublyLinkedList<T>::headdel()
  363. {
  364. 	Link<T> *temp = getFirst();
  365. 	if (!isEmpty())
  366. 	{
  367. 		if (getFirst()->getNext() == nullptr)
  368. 			setLast(nullptr);
  369. 		else
  370. 			getFirst()->getNext()->setPrevious(nullptr);
  371. 		setFirst(getFirst()->getNext());
  372. 	}
  373. 	return temp;
  374. }
  375.  
  376. template <class T>
  377. void DoublyLinkedList<T>::tailins(Link<T> *p)
  378. {
  379. 	p->setNext(nullptr);
  380. 	if (isEmpty())
  381. 	{
  382. 		p->setPrevious(nullptr);
  383. 		setFirst(p);
  384. 	}
  385. 	else
  386. 	{
  387. 		getLast()->setNext(p);
  388. 		p->setPrevious(getLast());
  389. 	}
  390. 	setLast(p);
  391. }
  392.  
  393. template <class T>
  394. bool DoublyLinkedList<T>::Split(DoublyLinkedList<T> &A, DoublyLinkedList<T> &B, int(*compare)(const T&, const T&))
  395. {
  396. 	bool isEmptyB, swapLists;
  397. 	Link<T> *currNode = nullptr;
  398. 	Link<T> *prevNode = nullptr;
  399. 	isEmptyB = true;
  400. 	swapLists = true;
  401. 	if (!isEmpty())
  402. 	{
  403. 		currNode = headdel();
  404. 		A.tailins(currNode);
  405. 		prevNode = currNode;
  406. 	}
  407. 	while (!isEmpty())
  408. 	{
  409. 		currNode = headdel();
  410. 		if (compare(prevNode->getData(), currNode->getData()) > 0)
  411. 			swapLists = !swapLists;
  412. 		if (swapLists)
  413. 			A.tailins(currNode);
  414. 		else
  415. 		{
  416. 			B.tailins(currNode);
  417. 			isEmptyB = false;
  418. 		}
  419. 		prevNode = currNode;
  420. 	}
  421. 	return isEmptyB;
  422. }
  423.  
  424. template <class T>
  425. void DoublyLinkedList<T>::Merge(DoublyLinkedList<T> &A, DoublyLinkedList<T> &B, int(*compare)(const T&, const T&))
  426. {
  427. 	Link<T> *tmpA = nullptr;
  428. 	Link<T> *tmpB = nullptr;
  429. 	Link<T> *poprzedniZtmpA = nullptr;
  430. 	Link<T> *poprzedniZtmpB = nullptr;
  431. 	bool koniecSeriiWtmpA, koniecSeriiWtmpB;
  432. 	if (!A.isEmpty())
  433. 	{
  434. 		tmpA = A.headdel();
  435. 	}
  436. 	if (!B.isEmpty())
  437. 	{
  438. 		tmpB = B.headdel();
  439. 	}
  440. 	koniecSeriiWtmpA = (tmpA == nullptr);
  441. 	koniecSeriiWtmpB = (tmpB == nullptr);
  442. 	while (tmpA != nullptr || tmpB != nullptr)
  443. 	{
  444. 		while (!koniecSeriiWtmpA && !koniecSeriiWtmpB)
  445. 			if (compare(tmpA->getData(), tmpB->getData()) <= 0)
  446. 			{
  447. 				tailins(tmpA);
  448. 				poprzedniZtmpA = tmpA;
  449. 				tmpA = A.headdel();
  450. 				if (tmpA == nullptr || compare(poprzedniZtmpA->getData(), tmpA->getData()) > 0)
  451. 					koniecSeriiWtmpA = true;
  452. 			}
  453. 			else
  454. 			{
  455. 				tailins(tmpB);
  456. 				poprzedniZtmpB = tmpB;
  457. 				tmpB = B.headdel();
  458. 				if (tmpB == nullptr || compare(poprzedniZtmpB->getData(), tmpB->getData()) > 0)
  459. 					koniecSeriiWtmpB = true;
  460. 			}
  461. 		while (!koniecSeriiWtmpA)
  462. 		{
  463. 			tailins(tmpA);
  464. 			poprzedniZtmpA = tmpA;
  465. 			tmpA = A.headdel();
  466. 			if (tmpA == nullptr || compare(poprzedniZtmpA->getData(), tmpA->getData()) > 0)
  467. 				koniecSeriiWtmpA = true;
  468. 		}
  469. 		while (!koniecSeriiWtmpB)
  470. 		{
  471. 			tailins(tmpB);
  472. 			poprzedniZtmpB = tmpB;
  473. 			tmpB = B.headdel();
  474. 			if (tmpB == nullptr || compare(poprzedniZtmpB->getData(), tmpB->getData()) > 0)
  475. 				koniecSeriiWtmpB = true;
  476. 		}
  477. 		koniecSeriiWtmpA = (tmpA == nullptr);
  478. 		koniecSeriiWtmpB = (tmpB == nullptr);
  479. 		poprzedniZtmpA = nullptr;
  480. 		poprzedniZtmpB = nullptr;
  481. 	}
  482. }
  483.  
  484. template <class T>
  485. void DoublyLinkedList<T>::MergeSort(int(*compare)(const T&, const T&))
  486. {
  487. 	bool isEmptyB = false;
  488. 	DoublyLinkedList<T> L1, L2;
  489. 	while (!isEmptyB)
  490. 	{
  491. 		isEmptyB = Split(L1, L2, compare);
  492. 		if (!isEmptyB)
  493. 			Merge(L1, L2, compare);
  494. 	}
  495. 	setFirst(L1.getFirst());
  496. 	setLast(L1.getLast());
  497. 	L1.setFirst(nullptr);
  498. 	L1.setLast(nullptr);
  499. }
  500.  
  501. int main(int argc, char *argv[])
  502. {
  503. 	int k, n, m;
  504. 	DoublyLinkedList<int> L;
  505. 	srand(time(nullptr));
  506. 	cin >> n >> m;
  507. 	for (k = 1; k <= n; k++)
  508. 		L.insert(rand() % m, compare);
  509. 	L.displayForward();
  510. 	L.displayBackward();
  511. 	L.MergeSort(compare);
  512. 	L.displayForward();
  513. 	L.displayBackward();
  514. 	while (!L.isEmpty())
  515. 		L.deleteFirst();
  516. 	system("PAUSE");
  517. 	return EXIT_SUCCESS;
  518. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
20 50
compilation info 
prog.cpp:6:24: fatal error: mergClassM.h: No such file or directory
 #include "mergClassM.h"
                        ^
compilation terminated.
stdout
copy 
Standard output is empty
https://ideone.com/PbuWop
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!