fork download 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4. #include <assert.h>
  5.  
  6. struct TNode
  7. {
  8. 	int data;
  9. 	struct TNode *next;
  10. 	struct TNode *prev;
  11. };
  12.  
  13. struct TList
  14. {
  15. 	struct TNode *head;
  16. 	struct TNode *tail;
  17. };
  18.  
  19. void ListInit(struct TList *L)
  20. {
  21. 	assert(L);
  22. 	L->head = NULL;
  23. 	L->tail = NULL;
  24. }
  25.  
  26. int ListIsEmpty(struct TList *L)
  27. {
  28. 	assert(L);
  29. 	return L->head == NULL;
  30. }
  31.  
  32. void ListDisplayForward(struct TList* L)
  33. {
  34. 	assert(L);
  35. 	int counter = 0;
  36. 	struct TNode *curr = L->head;
  37. 	printf("List (head-->tail): ");
  38. 	while (curr != NULL)
  39. 	{
  40. 		printf("%d -> ", curr->data);
  41. 		curr = curr->next;
  42. 		counter++;
  43. 	}
  44. 	printf("NULL \n");
  45. 	printf("Liczba wezlow listy: %d \n", counter);
  46. }
  47.  
  48. void ListDisplayBackward(struct TList* L)
  49. {
  50. 	assert(L);
  51. 	int counter = 0;
  52. 	struct TNode *curr = L->tail;
  53. 	printf("List (tail-->head): ");
  54. 	while (curr != NULL)
  55. 	{
  56. 		printf("%d -> ", curr->data);
  57. 		curr = curr->prev;
  58. 		counter++;
  59. 	}
  60. 	printf("NULL \n");
  61. 	printf("Liczba wezlow listy: %d \n", counter);
  62. }
  63.  
  64. void ListInsertNodeTail(struct TList *L, struct TNode *p)
  65. {
  66. 	assert(L);
  67. 	assert(p);
  68. 	p->next = NULL;
  69. 	if (L->head == NULL)
  70. 	{
  71. 		p->prev = NULL;
  72. 		L->head = p;
  73. 	}
  74. 	else
  75. 	{
  76. 		L->tail->next = p;
  77. 		p->prev = L->tail;
  78. 	}
  79. 	L->tail = p;
  80. }
  81.  
  82. void ListInsertValueTail(struct TList *L, int k)
  83. {
  84. 	assert(L);
  85. 	struct TNode *node = (struct TNode *)malloc(sizeof(struct TNode));
  86. 	assert(node);
  87. 	node->data = k;
  88. 	ListInsertNodeTail(L, node);
  89. }
  90.  
  91. struct TNode *ListDetachHead(struct TList *L)
  92. {
  93. 	assert(L);
  94. 	struct TNode *temp = L->head;
  95. 	if (L->head)
  96. 	{
  97. 		if (L->head->next == NULL)
  98. 			L->tail = NULL;
  99. 		else
  100. 			L->head->next->prev = NULL;
  101. 		L->head = L->head->next;
  102. 	}
  103. 	return temp;
  104. }
  105.  
  106. void ListDeleteHead(struct TList *L)
  107. {
  108. 	assert(L);
  109. 	free(ListDetachHead(L));
  110. }
  111.  
  112. void ListDelete(struct TList *L)
  113. {
  114. 	assert(L);
  115. 	while (!ListIsEmpty(L))
  116. 		ListDeleteHead(L);
  117. }
  118.  
  119. void SwapNodePointers(struct TNode **A, struct TNode **B)
  120. {
  121. 	assert(A);
  122. 	assert(B);
  123. 	struct TNode *tmp = *A;
  124. 	*A = *B;
  125. 	*B = tmp;
  126. }
  127.  
  128. void SwapListPointers(struct TList **A, struct TList **B)
  129. {
  130. 	assert(A);
  131. 	assert(B);
  132. 	struct TList *tmp = *A;
  133. 	*A = *B;
  134. 	*B = tmp;
  135. }
  136.  
  137. int ListSplit(struct TList *L, struct TList *A, struct TList *B)
  138. {
  139. 	assert(L);
  140. 	assert(A);
  141. 	assert(B);
  142. 	// prevNode trzeba zainicjalizowac nullem, coby się nie wysypać na początku
  143. 	struct TNode *currNode, *prevNode = NULL;
  144. 	ListInit(A);
  145. 	ListInit(B);
  146. 	while (currNode = ListDetachHead(L)) // "odłączamy głowę", dopóki nie zwróci nulla
  147. 	{
  148. 		// jeśli mamy początek nowej serii, to zamieniamy ze sobą wskaźniki do list,
  149. 		// w ten sposób poniższy kod zapisujący do A będzie zapisywał naprzemiennie do list A, B
  150. 		//  (coby kod niżej był prostszy - jeden przypadek zamiast dwóch)
  151. 		if (prevNode && prevNode->data > currNode->data)
  152. 			SwapListPointers(&A, &B);
  153.  
  154. 		// zawsze zapisujemy do A, ale A nie zawsze wskazuje tę samą listę
  155. 		ListInsertNodeTail(A, currNode);
  156. 		// pamiętamy poprzednią wartość (węzeł z wartością), coby wykryć koniec aktualnej serii
  157. 		prevNode = currNode;
  158. 	}
  159. 	return ListIsEmpty(B);
  160. }
  161.  
  162. void ListMerge(struct TList* A, struct TList* B, struct TList *L)
  163. {
  164. 	assert(L);
  165. 	assert(A);
  166. 	assert(B);
  167. 	struct TNode *tmpA, *tmpB, *prevA, *prevB;
  168. 	tmpA = ListDetachHead(A); // akutalna wartość z A
  169. 	tmpB = ListDetachHead(B); // akutalna wartość z B
  170. 	ListInit(L);
  171. 	while (tmpA && tmpB) // obie serie niepuste
  172. 	{
  173. 		// zapewnienie, że w A mamy serię z aktualnie niewiększą wartością,
  174. 		// w razie potrzeby zamieniamy odpowiednie wskaźniki
  175. 		//  (coby kod niżej był prostszy - jeden przypadek zamiast dwóch)
  176. 		if (tmpA->data > tmpB->data)
  177. 		{
  178. 			SwapNodePointers(&tmpA, &tmpB);
  179. 			SwapNodePointers(&prevA, &prevB);
  180. 			SwapListPointers(&A, &B);
  181. 		}
  182.  
  183. 		// przepisanie aktualnej wartości z serii w A (czyli wartości niewiększej od tej z B)
  184. 		ListInsertNodeTail(L, tmpA);
  185. 		// i pobranie kolejnej
  186. 		prevA = tmpA;
  187. 		tmpA = ListDetachHead(A);
  188.  
  189. 		// sprawdzenie, czy była to ostatnia liczba z serii
  190. 		if (!tmpA || tmpA->data < prevA->data)
  191. 		{
  192. 			// jeśli tak, przenosimy do końca aktualną serię z B (na pewno jest niepusta)
  193. 			do
  194. 			{
  195. 				ListInsertNodeTail(L, tmpB);
  196. 				prevB = tmpB;
  197. 				tmpB = ListDetachHead(B);
  198. 			} while (tmpB && prevB->data <= tmpB->data);
  199. 		}
  200. 	}
  201. 	// w którejś z list (ale tylko jednej) mogły zostać jeszcze jakieś serie
  202. 	// upewniamy się, że ewentualne "resztki" są w A
  203. 	// (tu wskaźnik tmp można nadpisać, ale wskaźniki do list trzeba ewentualnie podmienić)
  204. 	if (!tmpA)
  205. 	{
  206. 		tmpA = tmpB;
  207. 		SwapListPointers(&A, &B);
  208. 	}
  209. 	// przenosimy ewentualne "resztki"
  210. 	while (tmpA)
  211. 	{
  212. 		ListInsertNodeTail(L, tmpA);
  213. 		tmpA = ListDetachHead(A);
  214. 	}
  215. }
  216.  
  217. int main()
  218. {
  219. 	int k, n, m;
  220. 	struct TList L, L1, L2;
  221. 	ListInit(&L);
  222. 	srand(time(NULL));
  223. 	n = 20; m = 50;
  224. 	//scanf("%d %d", &n, &m);
  225. 	for (k = 1; k <= n; k++)
  226. 		ListInsertValueTail(&L, rand() % m);
  227.  
  228. 	printf("List L \n");
  229. 	ListDisplayForward(&L);
  230. 	ListDisplayBackward(&L);
  231.  
  232. 	ListSplit(&L, &L1, &L2);
  233.  
  234. 	printf("\nList L1 \n");
  235. 	ListDisplayForward(&L1);
  236. 	ListDisplayBackward(&L1);
  237. 	printf("\nList L2 \n");
  238. 	ListDisplayForward(&L2);
  239. 	ListDisplayBackward(&L2);
  240.  
  241. 	ListMerge(&L1, &L2, &L);
  242.  
  243. 	printf("\nList L \n");
  244. 	ListDisplayForward(&L);
  245. 	ListDisplayBackward(&L);
  246.  
  247. 	ListDelete(&L);
  248.  
  249. 	system("PAUSE");
  250. 	return 0;
  251. }
Success #stdin #stdout #stderr 0s 9424KB
comments (?)
stdin 
20 50
stdout 
List L 
List (head-->tail): 22 -> 23 -> 36 -> 16 -> 29 -> 5 -> 10 -> 6 -> 16 -> 24 -> 27 -> 6 -> 34 -> 8 -> 44 -> 3 -> 41 -> 0 -> 4 -> 5 -> NULL 
Liczba wezlow listy: 20 
List (tail-->head): 5 -> 4 -> 0 -> 41 -> 3 -> 44 -> 8 -> 34 -> 6 -> 27 -> 24 -> 16 -> 6 -> 10 -> 5 -> 29 -> 16 -> 36 -> 23 -> 22 -> NULL 
Liczba wezlow listy: 20 

List L1 
List (head-->tail): 22 -> 23 -> 36 -> 5 -> 10 -> 6 -> 34 -> 3 -> 41 -> NULL 
Liczba wezlow listy: 9 
List (tail-->head): 41 -> 3 -> 34 -> 6 -> 10 -> 5 -> 36 -> 23 -> 22 -> NULL 
Liczba wezlow listy: 9 

List L2 
List (head-->tail): 16 -> 29 -> 6 -> 16 -> 24 -> 27 -> 8 -> 44 -> 0 -> 4 -> 5 -> NULL 
Liczba wezlow listy: 11 
List (tail-->head): 5 -> 4 -> 0 -> 44 -> 8 -> 27 -> 24 -> 16 -> 6 -> 29 -> 16 -> NULL 
Liczba wezlow listy: 11 

List L 
List (head-->tail): 16 -> 22 -> 23 -> 29 -> 36 -> 5 -> 6 -> 10 -> 16 -> 24 -> 27 -> 6 -> 8 -> 34 -> 44 -> 0 -> 3 -> 4 -> 5 -> 41 -> NULL 
Liczba wezlow listy: 20 
List (tail-->head): 41 -> 5 -> 4 -> 3 -> 0 -> 44 -> 34 -> 8 -> 6 -> 27 -> 24 -> 16 -> 10 -> 6 -> 5 -> 36 -> 29 -> 23 -> 22 -> 16 -> NULL 
Liczba wezlow listy: 20
stderr 
sh: 1: PAUSE: not found
https://ideone.com/5cSdal
language:
C (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!