#include
using namespace std;
class Node {
public:
int value;
Node* next;
Node* prior;
Node(int i) { value = i; next = prior = nullptr; }
Node() { next = prior = nullptr; }
};
class DoublyLinkedList {
public:
Node* head;
Node* tail;
DoublyLinkedList() { head = tail = nullptr; }
void makeRandomList(int m, int n);
void printForward();
void printBackward();
//inplement the following member functions:
void sort();//sort all values based on frequency in ascending order.
//In case of ties, the smaller values will appear earlier
//Example: for list with values 7 6 12 4 33 12 6 6 7
//sorted results: 4 33 7 7 12 12 6 6 6
//If your algorithm is inefficient, you might lose points.
//You will not modify L.
};
void DoublyLinkedList::sort()
{
int num[100]; //count element
int i;
for (i = 0; i < 100; i++)
{
num[i] = 0;
}
Node* p1 = head,*e;
Node* t = head;
while (p1 != nullptr) {
num[p1->value]++;
p1 = p1->next;
}
int min_num; //count lower frequency
int flag;
//int total_num = 0;
do
{
min_num = 0;
flag = -1;
for (i = 0; i < 100; i++)
{
if (num[i] != 0 && min_num == 0)
{
min_num = num[i];
flag = i;
}
else if (num[i] != 0 && min_num > num[i])
{
flag = i;
min_num = num[i];
}
}
if (flag == -1)
break;
num[flag] = 0;
e = t;
while (e != nullptr)
{
if (e->value == flag)
{
if (e == t)
{
e = e->next;
t = t->next;
continue;
}
if (e->next != nullptr)
{
e->next->prior = e->prior;
}
e->prior->next = e->next;
//e becomes tail
if (e->next == nullptr)
{
tail = e->prior;
}
e->prior = t->prior;
e->next = t;
if (t->prior != nullptr)
t->prior->next = e;
t->prior = e;
if (t == head)
{
head = e;
}
}
e = e->next;
}
} while (min_num != 0);
}
void DoublyLinkedList::makeRandomList(int m, int n) {
for (int i = 0; i < m; i++) {
Node* p1 = new Node(rand() % n);
p1->prior = tail;
if (tail != nullptr) tail->next = p1;
tail = p1;
if (head == nullptr) head = p1;
}
}
void DoublyLinkedList::printForward() {
cout << endl;
Node* p1 = head;
while (p1 != nullptr) {
cout << p1->value << " ";
p1 = p1->next;
}
}
void DoublyLinkedList::printBackward() {
cout << endl;
Node* p1 = tail;
while (p1 != nullptr) {
cout << p1->value << " ";
p1 = p1->prior;
}
}
int main() {
DoublyLinkedList d1;
d1.makeRandomList(50, 20);
d1.printForward();
d1.printBackward();
d1.sort();
d1.printForward();
d1.printBackward();
getchar();
getchar();
return 0;
}