Câu 1:
template <class T>
void DLinkedList<T>::add(const T& e) {
/* Insert an element into the end of the list. */
Node* newNode = new Node(e);
if (count == 0) {
head = tail = newNode;
} else {
tail->next = newNode;
newNode->previous = tail;
tail = newNode;
}
count++;
template<class T>
void DLinkedList<T>::add(int index, const T& e) {
/* Insert an element into the list at given index. */
if (index < 0 || index > count) {
throw "Index out of bounds!";
}
Node* newNode = new Node(e);
if (index == 0) {
if (count == 0) {
head = tail = newNode;
} else {
newNode->next = head;
head->previous = newNode;
head = newNode;
}
} else if (index == count) {
tail->next = newNode;
newNode->previous = tail;
tail = newNode;
} else {
Node* prevNode = head;
for (int i = 0; i < index - 1; i++) {
prevNode = prevNode->next;
}
newNode->next = prevNode->next;
newNode->previous = prevNode;
prevNode->next->previous = newNode;
prevNode->next = newNode;
}
count++;
template<class T>
int DLinkedList<T>::size() {
/* Return the length (size) of list */
return count ;
}
Câu 2:
template<class T>
T DLinkedList<T>::get(int index) {
/* Give the data of the element at given index in the list. */
if (index < 0 || index >= count) {
throw "Index out of bounds!";
}
Node* currentNode = head;
for (int i = 0; i < index; i++) {
currentNode = currentNode->next;
}
return currentNode->data;
}
template <class T>
void DLinkedList<T>::set(int index, const T& e) {
/* Assign new value for element at given index in the list */
if (index < 0 || index >= count) {
throw "Index out of bounds!";
}
Node* currentNode = head;
for (int i = 0; i < index; i++) {
currentNode = currentNode->next;
}
currentNode->data = e;
}
template<class T>
bool DLinkedList<T>::empty() {
/* Check if the list is empty or not. */
return count == 0 ;
}
template<class T>
int DLinkedList<T>::indexOf(const T& item) {
/* Return the first index wheter item appears in list, otherwise return -1 */
Node* currentNode = head;
for (int i = 0; i < count; i++) {
if (currentNode->data == item) {
return i;
}
currentNode = currentNode->next;
}
return -1;
}
template<class T>
bool DLinkedList<T>::contains(const T& item) {
/* Check if item appears in the list */
return indexOf(item) != -1;
}
Câu 3:
/*
* TODO: Implement class Iterator's method
* Note: method remove is different from SLinkedList, which is the advantage of
DLinkedList
*/
template <class T>
DLinkedList<T>::Iterator::Iterator(DLinkedList<T> *pList, bool begin)
{
this->pList = pList;
if (begin) {
this->current = pList->head;
this->index = 0;
} else {
this->current = NULL;
this->index = pList->count;
}
template <class T>
typename DLinkedList<T>::Iterator& DLinkedList<T>::Iterator::operator=(const
DLinkedList<T>::Iterator &iterator)
{
this->current = iterator.current;
this->index = iterator.index;
return *this;
template <class T>
void DLinkedList<T>::Iterator::set(const T &e)
{
if (this->current != NULL) {
this->current->data = e;
}
}
template<class T>
T& DLinkedList<T>::Iterator::operator*()
{
return this->current->data;
}
template<class T>
void DLinkedList<T>::Iterator::remove()
{
/*
* TODO: delete Node in pList which Node* current point to.
* After that, Node* current point to the node before the node just deleted.
* If we remove first node of pList, Node* current point to nullptr.
* Then we use operator ++, Node* current will point to the head of pList.
*/
if (this->current != NULL && this->pList != NULL) {
Node* nodeToRemove = this->current;
if (nodeToRemove == this->pList->head) {
this->pList->head = nodeToRemove->next;
}
if (nodeToRemove == this->pList->tail) {
this->pList->tail = nodeToRemove->previous;
}
if (nodeToRemove->next != NULL) {
nodeToRemove->next->previous = nodeToRemove->previous;
}
if (nodeToRemove->previous != NULL) {
nodeToRemove->previous->next = nodeToRemove->next;
this->current = nodeToRemove->previous;
} else {
this->current = NULL;
}
delete nodeToRemove;
this->pList->count--;
}
template<class T>
bool DLinkedList<T>::Iterator::operator!=(const DLinkedList::Iterator &iterator)
{
return this->current != iterator.current;
}
template<class T>
typename DLinkedList<T>::Iterator& DLinkedList<T>::Iterator::operator++()
{
if (this->current != NULL) {
this->current = this->current->next;
} else if (this->pList != NULL) {
this->current = this->pList->head;
}
return *this;
template<class T>
typename DLinkedList<T>::Iterator DLinkedList<T>::Iterator::operator++(int)
{
Iterator iteratorBeforeIncrementation(*this);
++*this;
return iteratorBeforeIncrementation;
}
Câu 4:
template <class T>
T DLinkedList<T>::removeAt(int index)
{
if (index < 0 || index >= count)
throw out_of_range("Index out of range");
Node *currentNode = head;
T removedData;
if (index == 0)
{
head = currentNode->next;
if (head != nullptr)
head->previous = nullptr;
else
tail = nullptr;
removedData = currentNode->data;
delete currentNode;
}
else
{
for (int i = 0; i < index - 1; i++)
{
currentNode = currentNode->next;
}
Node *nodeToRemove = currentNode->next;
Node *nextNode = nodeToRemove->next;
currentNode->next = nextNode;
if (nextNode != nullptr)
nextNode->previous = currentNode;
else
tail = currentNode;
removedData = nodeToRemove->data;
delete nodeToRemove;
}
count--;
return removedData;
}
template <class T>
bool DLinkedList<T>::removeItem(const T &item)
{
Node *currentNode = head;
Node *prevNode = nullptr;
while (currentNode != nullptr)
{
if (currentNode->data == item)
{
if (prevNode == nullptr)
{
head = currentNode->next;
if (head != nullptr)
head->previous = nullptr;
else
tail = nullptr;
}
else
{
prevNode->next = currentNode->next;
if (currentNode->next != nullptr)
currentNode->next->previous = prevNode;
else
tail = prevNode;
}
delete currentNode;
count--;
return true;
}
prevNode = currentNode;
currentNode = currentNode->next;
}
return false;
}
template <class T>
void DLinkedList<T>::clear()
{
Node *currentNode = head;
while (currentNode != nullptr)
{
Node *nextNode = currentNode->next;
delete currentNode;
currentNode = nextNode;
}
head = nullptr;
tail = nullptr;
count = 0;
}
Câu 5:
DataLog::DataLog()
{
/*
* TODO: add the first state with 0
*/
logList.push_back(0); // Initialize with state 0
currentState = logList.begin();
}
DataLog::DataLog(const int &data)
{
/*
* TODO: add the first state with data
*/
logList.push_back(data); // Initialize with given state
currentState = logList.begin();
}
void DataLog::addCurrentState(int number)
{
/*
* TODO: Increase the value of current state by number
*/
*currentState += number;
}
void DataLog::subtractCurrentState(int number)
{
/*
* TODO: Decrease the value of current state by number
*/
*currentState -= number;
}
void DataLog::save()
{
/*
* TODO: This function will create a new state, copy the data of the currentState
* and move the currentState Iterator to this new state. If there are other
states behind the
* currentState Iterator, we delete them all before creating a new state.
*/
// Remove states after current state
auto it = currentState;
++it;
while (it != logList.end()) {
it = logList.erase(it);
}
// Add current state to the end
logList.push_back(*currentState);
currentState = --logList.end(); // Point to the last element
}
void DataLog::undo()
{
/*
* TODO: Switch to the previous state of the data
* If this is the oldest state in the log, nothing changes
*/
if (currentState != logList.begin()) {
--currentState; // Move to the previous state
}
}
void DataLog::redo()
{
/*
* TODO: Switch to the latter state of the data
* If this is the latest state in the log, nothing changes
*/
auto next = currentState;
++next;
if (next != logList.end()) {
++currentState; // Move to the next state
}
}
Câu 6:
ListNode* reverse(ListNode* head, int a, int b) {
ListNode dummy;
dummy.right = head;
ListNode *pre = &dummy;
for (int i = 1; i < a; ++i) pre = pre->right;
ListNode *cur = pre->right;
for (int i = a; i < b; ++i) {
ListNode *temp = cur->right;
cur->right = temp->right;
temp->right = pre->right;
pre->right = temp;
if (cur->right) cur->right->left = cur;
if (temp->right) temp->right->left = temp;
}
return dummy.right;
}
Yeu em!
