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
|
#include <iostream>
#include "d_node.h"
#include "d_nodel.h"
#include "d_random.h"
using namespace std;
// return a pointer to the maximum element in the linked list
template <typename T>
node<T> *getMax(node<T> *front);
// if target is in the linked list, remove its first
// occurrence; otherwise, do not modify the list
template <typename T>
void eraseValue(node<T> * & front, const T& target);
// outputs the nodes of a single linked list in reverse order.
template <typename T>
void outputReverse(node<T> *front);
int main()
{
node<int> *front = NULL, *p;
randomNumber rnd;
int listCount, i;
cout << "Enter the size of the list: ";
cin >> listCount;
for (i = 0; i < listCount; i++)
front = new node<int>(rnd.random(100), front);
cout << "Original List of Values: ";
writeLinkedList(front, " ");
cout << endl;
cout << "The list reversed is: ";
outputReverse(front);
cout << endl;
cout << "Output in Descending Order: ";
while (front != NULL)
{
p = getMax(front);
cout << p->nodeValue << " ";
eraseValue(front, p->nodeValue);
}
cout << endl;
system("PAUSE");
return 0;
}
template <typename T>
node<T> *getMax(node<T> *front)
{
node<T> *curr = front, *maxPtr = front;
while (curr != NULL)
{
if (maxPtr->nodeValue < curr->nodeValue)
maxPtr = curr;
curr = curr->next;
}
return maxPtr;
}
template <typename T>
void eraseValue(node<T> * & front, const T& target)
{
// curr moves through list, trailed by prev
node<T> *curr = front, *prev = NULL;
// becomes true if we locate target
bool foundItem = false;
// scan until locate item or come to end of list
while (curr != NULL && !foundItem)
{
if (curr->nodeValue == target) // have a match
{
if (prev == NULL) // remove the first node
front = front->next;
else
prev->next = curr->next; // erase intermediate node
delete curr;
foundItem = true;
}
else
{
// advance curr and prev
prev = curr;
curr = curr->next;
}
}
}
template <typename T>
void outputReverse(node<T> *front)
{
node<T> *temp, *newNode, *p;
while (front != NULL)
{
newNode = new node<T>(front, temp);
front = front->next;
temp = newNode;
}
writeLinkedList(temp, "<-");
while (temp != NULL)
{
if (temp != NULL)
{
p = temp;
temp = temp->next;
delete p;
}
}
}
|
