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