/
exp_2018-09-26_1.c
186 lines (177 loc) · 6.5 KB
/
exp_2018-09-26_1.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
//
// exp_2018-09-26_1.c
// External sorting for linked-lists.
// Created by cosh.cage#hotmail.com on 09/26/18.
// Licence: Public domain.
// Platform: Cross Platform.
//
#include <stdio.h>
#include <stdlib.h>
#include "../src/svstring.h"
#define LIST1_LEN (10) // Length of single pointer linked list.
#define LIST2_LEN (20) // Length of double pointer linked list.
// Function: cbftvs_print
// Desc: Print list contents.
// Param: pitem: pointer to each node in a list. param: value of enumeration NodeType.
// Return: Either CBF_CONTINUE or CBF_TERMINATE.
int cbftvs_print(void * pitem, size_t param)
{
if (ENT_SINGLE == param)
printf("%c ", (char)(size_t)((P_NODE_S)pitem)->pdata);
else if (ENT_DOUBLE == param)
printf("%2d ", *(int *)((P_NODE_D)pitem)->pdata);
else
return CBF_TERMINATE;
return CBF_CONTINUE;
}
// Function: cbftvs_copy_1
// Desc: Copy data between a single linked-list and an array.
// Param: pitem: pointer to each node in a list. param: a size_t[2] array.
// Return: CBF_CONTINUE only.
int cbftvs_copy_1(void * pitem, size_t param)
{
if (0[(size_t *)param]) /* Linked-list -> array. */
*((*(char **)1[(size_t *)param])++) = (char)(size_t)((P_NODE_S)pitem)->pdata;
else /* Array -> linked-list. */
((P_NODE_S)pitem)->pdata = (PUCHAR)(size_t)*((*(char **)1[(size_t *)param])++);
return CBF_CONTINUE;
}
// Function: cbftvs_copy_2
// Desc: Copy data between a doubly linked-list and an array.
// Param: pitem: pointer to each node in a list. param: a size_t[2] array.
// Return: CBF_CONTINUE only.
int cbftvs_copy_2(void * pitem, size_t param)
{
if (0[(size_t *)param]) /* Linked-list -> array. */
*((*(int **)1[(size_t *)param])++) = *(int *)((P_NODE_D)pitem)->pdata;
else /* Array -> linked-list. */
*(int *)((P_NODE_D)pitem)->pdata = *((*(int **)1[(size_t *)param])++);
return CBF_CONTINUE;
}
// Function: cbfcmp_1
// Desc: Compare values for characters.
// Param: px: a pointer to a char value. py: another pointer to a char value.
// Return: Either 1, -1 or 0 depends on comparison result.
int cbfcmp_1(const void * px, const void * py)
{
if (*(char *)px > *(char *)py) return 1;
if (*(char *)px < *(char *)py) return -1;
return 0;
}
// Function: cbfcmp_2
// Desc: Compare values for ints.
// Param: px: a pointer to an int value. py: another pointer to an int value.
// Return: Either 1, -1 or 0 depends on comparison result.
int cbfcmp_2(const void * px, const void * py)
{
if (*(int *)px > *(int *)py) return 1;
if (*(int *)px < *(int *)py) return -1;
return 0;
}
// Function: SortLinkedListSC
// Desc: Sort data in a single pointer linked list. This function takes pdata as value directly.
// Param: plist: pointer to a linked list. cbfcmp: pointer to a comparison function.
// Return: TRUE: sorting succeeded; FALSE: sorting failed.
BOOL SortLinkedListSC(P_NODE_S plist, CBF_COMPARE cbfcmp)
{
size_t a[2];
char * pstr;
P_ARRAY_Z parr;
// Move list 1's content to an array.
if (NULL == (parr = strCreateArrayZ(strLevelLinkedListSC(plist), sizeof(char))))
return FALSE; // Allocation failure.
pstr = (char *)parr->pdata;
a[0] = TRUE;
a[1] = (size_t)&pstr;
strTraverseLinkedListSC_A(plist, NULL, cbftvs_copy_1, (size_t)a);
strSortArrayZ(parr, sizeof(char), cbfcmp);
// Copy data back to list.
pstr = (char *)parr->pdata;
a[0] = FALSE;
a[1] = (size_t)&pstr;
strTraverseLinkedListSC_A(plist, NULL, cbftvs_copy_1, (size_t)a);
// Deallocate array.
strDeleteArrayZ(parr);
return TRUE;
}
// Function: SortLinkedListDC
// Desc: Sort data in a single pointer linked list.
// Param: plist: pointer to a linked list.
// cbfcmp: pointer to a comparison function.
// brev: TRUE, search list downward; FALSE, search list upward.
// Return: TRUE: sorting succeeded; FALSE: sorting failed.
BOOL SortLinkedListDC(P_NODE_D plist, CBF_COMPARE cbfcmp, BOOL brev)
{
size_t a[2];
int * pint;
P_ARRAY_Z parr;
// Move list 2's content to an array.
if (NULL == (parr = strCreateArrayZ(strLevelLinkedListDC(plist, brev), sizeof(int))))
return FALSE; // Allocation failure.
pint = (int *)parr->pdata;
a[0] = TRUE;
a[1] = (size_t)&pint;
strTraverseLinkedListDC_A(plist, NULL, cbftvs_copy_2, (size_t)a, brev);
strSortArrayZ(parr, sizeof(int), cbfcmp);
// Copy data back to list.
pint = (int *)parr->pdata;
a[0] = FALSE;
a[1] = (size_t)&pint;
strTraverseLinkedListDC_A(plist, NULL, cbftvs_copy_2, (size_t)a, brev);
// Deallocate array.
strDeleteArrayZ(parr);
return TRUE;
}
// Function: main
// Desc: Program entry.
// Param: N/A.
// Return: 0: no error; 1, 2: allocation failure.
int main(void)
{
int i, n;
NODE_S list1[LIST1_LEN];
LIST_D list2, pnoded;
char * pstr = "helloworld";
strInitLinkedListDC(&list2);
// Assemble single-linked list 1.
list1[0].pdata = (PUCHAR)(size_t)(*pstr++);
for (i = 1; i < LIST1_LEN; ++i)
{
/* To convert a size_t value to PUCHAR after converting char value to size_t
* to cheat compilers from warning me. Warning codes are shocking.
* I wish for compilers' forgiveness for my false conduct. :)
*/
list1[i].pdata = (PUCHAR)(size_t)(*pstr++);
list1[i - 1].pnode = &list1[i];
}
list1[9].pnode = NULL; // Close tail.
// Print list 1.
puts("Linked lists sorting\n\nList 1:"); strTraverseLinkedListSC_A(list1, NULL, cbftvs_print, ENT_SINGLE); printf("\n");
if (SortLinkedListSC(list1, cbfcmp_1))
puts("List 1 after sorting:"), strTraverseLinkedListSC_A(list1, NULL, cbftvs_print, ENT_SINGLE);
else
puts("Error occurred while sorting list 1.");
// Assemble doubly-pointer-linked list 2.
srand((unsigned int)&n);
n = rand() % 99 + 1;
list2 = strCreateNodeD(&n, sizeof(int));
for (i = 0, pnoded = list2; n = rand() % 99 + 1, i < (LIST2_LEN - 1); ++i)
{
if (NULL == (pnoded->ppnode[NEXT] = strCreateNodeD(&n, sizeof(int))))
{
strFreeLinkedListDC(&list2, FALSE);
puts("Error occurred while creating list 2.");
return 2; /* Allocation failure while creating doubly linked list. */
}
pnoded = pnoded->ppnode[NEXT];
}
// Print list 2.
puts("\n\nList 2:"); strTraverseLinkedListDC_A(list2, NULL, cbftvs_print, ENT_DOUBLE, FALSE); printf("\n");
if (SortLinkedListDC(list2, cbfcmp_2, FALSE))
puts("List 2 after sorting:"), strTraverseLinkedListDC_A(list2, NULL, cbftvs_print, ENT_DOUBLE, FALSE);
else
puts("Error occurred while sorting list 2.");
printf("\n");
strFreeLinkedListDC(&list2, FALSE);
return 0;
}