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
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
|
#include <iostream>
#include <iomanip>
#include <string>
using namespace std;
// Defines a structure employee
struct employee
{
// Data member to store data
string fname, lname;
int id;
// Default constructor
employee() {}
// Parameterized constructor
employee(string f, string l, int i)
{
fname = f;
lname = l;
id = i;
}// End of parameterized constructor
};// End of structure
// Structure mylist definition
struct mylist
{
// To store employee object
struct employee data;
// To point to next employee
mylist *next;
};// End of structure
// Function to create a node and return it
mylist* createnode(employee e)
{
// Declares a pointer object
mylist *n;
// Creates a the pointer object
n = new mylist;
// Assigns employee object
n->data = e;
// Assigns new node next to NULL
n->next = NULL;
}// End of function
// Function to add a node at the end of linked list
void add(mylist **n, employee e)
{
// Calls the function to create a node and stores the return object in temp
mylist *temp = createnode(e);
// Declares pointer
mylist *p;
// Checks if parameter pointer object is NULL then list is empty
if (*n == NULL) //list is empty
// Adds the newly created node to start
*n = temp;
// Otherwise nodes are available
else
{
// Assigns start node to pointer p
p = *n;
// Moves till end of the list
while (p->next) //move p to the last node
// Move to next node
p = p->next;
// Assigns the newly created node to currently pointing node
p->next = temp; //Add new employee(node) in the last
}// End of else
}// End of function
// Function to display the linked list
void printlist(mylist *n)
{
// Creates an object using default constructor
employee e;
// Loops till end of the linked list
while (n)
{
// Stores the current object in object e
e = n->data;
// Displays the first name, last name and id
cout << left << setw(8) << "Name:" << setw(10) << e.fname << setw(10) << e.lname
<< setw(6) << "ID = " << setw(6) << e.id << endl;
// Move to next nod
n = n->next;
}// End of while loop
}// End of function
/* Split the nodes of the given linked list into front and back parts,
* and return the two lists using the reference parameters.
* Checks if the length is odd, the extra node should go in the front list.
*/
void splitfrontback(mylist* sourceList, mylist** frontList, mylist** backList)
{
// Creates two pointer type object to refer to two and one node
mylist* first;
mylist* last;
// Assign the source node to last
last = sourceList;
// Assign source node next to first
first = sourceList->next;
// Advance 'first' two nodes, and advance 'last' one node
while (first != NULL)
{
// Move next
first = first->next;
// Checks if first is not NULL
if (first != NULL)
{
// Move first and last node to next node
last = last->next;
first = first->next;
}// End of if condition
}// End of while loop
// 'last' is before the midpoint in the list, so split it in two at that point.
*frontList = sourceList;
*backList = last->next;
last->next = NULL;
}// End of function
// Function to perform swapping with data
mylist* sortedmerge(mylist* first, mylist* second)
{
// Creates a pointer type object for swapping
mylist* result = NULL;
// Checks if first node is NULL then return second node
if (first == NULL)
return second;
// Otherwise checks if second node is NULL then return first node
else if (second == NULL)
return first;
// Picks either first or second, and recurse
// Checks if first node last name is greater than the second node last name
if (first->data.lname.compare(second->data.lname) > 0)
{
// Assigns the first node to result
result = first;
// Recursive calls the function with first parameter moving first node next
result->next = sortedmerge(first->next, second);
}// End of if condition
// Otherwise
else
{
// Assigns second node to result
result = second;
// Recursive calls the function with second parameter moving second node next
result->next = sortedmerge(first, second->next);
}
// Returns the result node
return result;
}// End of function
// Function to sort the linked list by changing next pointers
void mergesort(mylist** headNode)
{
mylist* head = *headNode;
mylist* first;
mylist* second;
// Base case -- length 0 or 1
if ((head == NULL) || (head->next == NULL))
return;
// Split head into 'first' and 'second' sublists
splitfrontback(head, &first, &second);
// Recursively calls the function to sort the sublists
mergesort(&first);
mergesort(&second);
// head node = merge the two sorted lists together
*headNode = sortedmerge(first, second);
}// End of function
// main function definition
int main()
{
mylist *start = NULL; //points to start of the list
// Created employee with given data
employee e1("Peter", "Schmidt", 3044);
add(&start, e1); //Add employee in the list
employee e2("Mary", "Alson", 1234);
add(&start, e2); //Add employee in the list
employee e3("Juan", "Lopez", 2334);
add(&start, e3); //Add employee in the list
employee e4("Xion", "Lee", 5556);
add(&start, e4); //Add employee in the list
employee e5("Adrian", "Boixua", 3443);
add(&start, e5); //Add employee in the list
// Calls the function to display list
cout << "\n Before sorting \n";
printlist(start);
// Calls the function to perform merge sort
mergesort(&start);
// Displays the list after merge sort
cout << "\n After sorting by Last Name \n";
printlist(start);
return 0;
}// End of main function
|
