//
// project.cpp
// HW2
//
// Created by 栋 on 2019/9/23.
// Copyright © 2019 Dong. All rights reserved.
//
#include
/*
– Implement two member functions, merge and remove, of the DoublyLinkedList class of HW1.
The descriptions of the two member functions are given below.
– In the implementation of merge and remove, you are not allowed to modify values of nodes.
You only can modify pointers of nodes.
– Again, you are not allowed to create new nodes in your implementation. No external structures (such as arrays,
linked list, map, etc.) are allowed. You can use some temporary pointes or variables for your
implementation.
– In implementaing merge and remove, you are not allowed to call sort() in HW1
When you submit your code, do not modify main function.
Do not introduce new functions
In-place implementation is required. (This means all operations should directly performed on the list.)
*/
#include
using namespace std;
class Node {
public:
int value;
Node* next;
Node* previous;
Node(int i) { value = i; next = previous = nullptr; }
Node() { next = previous = nullptr; }
};
class DoublyLinkedList {
public:
Node* head;
Node* tail;
DoublyLinkedList() { head = tail = nullptr; }
void makeRandomList(int m, int n);
void printForward();
void printBackward();
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
void merge(DoublyLinkedList& L);
/*
Given an already sorted DoublyLinkedList (i.e., the result of HW1) , take
another unsorted list L as function argument, and merge L into the current
list to form a single sorted DoublyLinkedList. The result of merge is a sorted list.
You are not allowed to invoke sort() in HW1 in your implementation of merge.
*/
void remove(int m, int n);
/*
Given an already sorted DoublyLinkedList (i.e., the result of the HW1),
remove n times of value m from the DoublyLinkedList.
If n is more than the total number of m’s in the DoublyLinkedList,
then remove all m’s from the list.
If m does not exist in the list, then do nothing.
The result of remove will be a sorted list.
You are not allowed to invoke sort() in HW1 in your implementation of remove.
*/
};
void DoublyLinkedList::makeRandomList(int m, int n) {
for (int i = 0; i < m; i++) {
Node* p1 = new Node(rand() % n);
p1->previous = 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->previous;
}
}
int main() {
DoublyLinkedList d1, d2;
d1.makeRandomList(50, 20);
d1.printForward();
d1.printBackward();
d1.sort();
d1.printForward();
d1.printBackward();
d2.makeRandomList(50, 20);
d1.printForward();
d1.printBackward();
d1.merge(d2);
d1.printForward();
d1.printBackward();
d1.remove(13, 3);
d1.printForward();
d1.printBackward();
getchar();
getchar();
return 0;
}