Follow instruction fill in the code. #ifndef OLIST_H #define OLIST_H #include <i
ID: 3770428 • Letter: F
Question
Follow instruction fill in the code.
#ifndef OLIST_H
#define OLIST_H
#include <iostream>
using namespace std;
template <class T>
class Node {
public:
Node(const T & inf = T()):info(inf) {
this->next = NULL;
}
T info;
Node * next;
};
template <class T>
class OList {
friend ostream & operator<< (ostream & out, const OList<T> & list) {
Node<T> * temp = list.head.next; // to walk through the list
out << "{ ";
while (temp != NULL) {
out << temp->info << (temp->next == NULL ? " " : ", ");
temp = temp->next;
}
out << "}";
return out;
}
public:
OList() {
lastPtr = &head; // head is a "dummy" anchor node
size = 0;
}
// constructor initialize the list with elements from array values
OList(T * values, int length) {
size = 0;
lastPtr = &head;
for (int i = 0; i < length; i++)
insert(values[i]);
}
OList(const OList<T> & other) {
// fill in code... (A one liner!)
}
~OList() {
// fill in code... (Another one liner.)
}
int getSize() const {
return size;
}
OList<T> & operator=(const OList<T> & other) {
if (&other == this) {
// self assignment ignored.
return *this;
}
else {
// fill in code ( call copy() ? )
}
}
// lists must have same length same sequence of values
bool operator==(const OList<T> & other) const {
// fill in code
}
bool operator!=(const OList<T> & other) const {
// fill in code (call operator==() ?)
}
OList<T> & operator+= (const OList<T> & other) {
Node<T> * pre = &head; // initial value for pre
for ( const Node<T> * temp = other.head.next;
temp != NULL;
temp = temp->next
)
{
// fill in code...
// call findInsertionPoint() to update pre
// create a newNodePtr with the same info as temp
// then call insertAfter(pre, newNodePtr)
}
// fill in code...
// update size
// return ?;
}
OList<T> operator+(const OList<T> & other) const {
// fill in code...
// declare an OList temp, initialized to *this
// call operator+=()
// return ?
}
void insert(const T & val) {
Node<T> * pre = findInsertionPoint(&head,val);
// fill in code...including a call to insertAfter()
}
bool remove(const T & val, bool removeAll = false) {
if (size == 0) return false;
bool foundIt = false;
Node<T> * pre = findInsertPoint(&head,val);
while (pre->next != NULL && pre->next->info == val) {
foundIt = true;
size--;
Node<T> * temp = pre->next;
if (temp == lastPtr)
lastPtr = pre;
pre->next = temp->next;
delete temp;
if (!removeAll) break; // only remove one instance of val
}
return foundIt; // true if val was removed
}
void clear() {
// fill in code using hints below.
// clear the list and set size to 0
// be sure to call delete on every Node after head (avoid memory leaks).
}
bool find(const T & val) {
// fill in code using hint below.
// return true if val is in the list and false otherwise. Ti determine if val is in the list, callfindInsertionPoint
}
const T getSmallest() const {
if (isEmpty()) {
cout << "Error: no smallest element for empty list." << endl;
return T();
}
// fill in code... (easy since he have a head node.)
}
const T getBiggest() const {
if (isEmpty()) {
cout << "Error: no biggest element for empty list." << endl;
return T();
}
// fill in code... (easy since we have a lastPtr )
}
bool isEmpty() const {
// fill in code... (easy since we have a size member variable)
}
void print(bool separateLines = false) const {
if (!separateLines)
cout << *this << endl; // We just use the stream insertion operator defined above
else {
Node<T> * temp = head.next;
while (temp!= NULL) {
cout << temp->info << endl; // put in an endl right after outputting the data
temp = temp->next;
}
}
}
void printBackwards() const {
// fill in code...
// print values in reverse order, enclosed in braces (e.g. {5, 3, 1}
// First output "{ " then call printBackwardsHelper() to print the values in reverse order. Then output "}"
}
private:
Node<T> head; // This is a "dummy" head node like we discussed in class.
Node<T> * lastPtr;
int size;
void printBackwardsHelper(Node<T> * n) const {
// fill in code... (use recursion)
}
Node<T> * findInsertionPoint(Node<T> * pre, const T & val) {
for (;pre->next != NULL && val > pre->next->info; pre = pre->next); // find position
return pre;
}
// precondition: pre != NULL
void insertAfter(Node<T> * pre, Node<T> * theNode) {
// fill in code...
// be sure to update lastPtr if necessary
}
// copy other list to *this
OList<T> & copy(const OList<T> & other) {
clear();
Node<T> * temp = other.head.next; // first real node of other
while (temp != NULL) {
// fill in code...
}
size = other.size;
return *this;
}
};
#endif
Explanation / Answer
Sample code:
// OrderedLinkedList.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
using namespace std;
template <class T>
class Node {
public:
Node(const T & inf = T()):info(inf) {
this->next = NULL;
}
T info;
Node * next;
};
template <class T>
class OList {
friend ostream & operator<< (ostream & out, const OList<T> & list) {
Node<T> * temp = list.head.next; // to walk through the list
out << "{ ";
while (temp != NULL) {
out << temp->info << (temp->next == NULL ? " " : ", ");
temp = temp->next;
}
out << "}";
return out;
}
public:
OList() {
lastPtr = &head; // head is a "dummy" anchor node
size = 0;
}
// constructor initialize the list with elements from array values
OList(T * values, int length) {
size = 0;
lastPtr = &head;
for (int i = 0; i < length; i++)
insert(values[i]);
}
OList(const OList<T> & other) {
lastPtr =other;// fill in code... (A one liner!)
}
~OList() {
lastPtr=NULL;// fill in code... (Another one liner.)
}
int getSize() const {
return size;
}
OList<T> & operator=(const OList<T> & other) {
if (&other == this) {
return *this;
}
else {
copy(const OList<T> & other) ;
}
}
bool operator==(const OList<T> & other) const {
return other.head==other.lastPtr;
}
bool operator!=(const OList<T> & other) const {
return !(other.head==other.lastPtr);
}
OList<T> & operator+= (const OList<T> & other) {
Node<T> * pre = &head; // initial value for pre
for ( const Node<T> * temp = other.head.next;
temp != NULL;
temp = temp->next
)
{
.
findInsertionPoint(pre, other); //to update pre
Node<T> *newNodePtr = new Node<T>(val);
temp->next=newNodePtr;
newNodePtr->info=temp->info;
insertAfter(pre, newNodePtr)
}
}
OList<T> operator+(const OList<T> & other) const {
OList<T> temp=*this;
temp+=temp.head;
return temp;
}
void insert(const T & val) {
Node<T> * pre = findInsertionPoint(&head,val);
Node<T> *theNode = new Node<T>(val);
insertAfter(pre, theNode);
}
bool remove(const T & val, bool removeAll = false) {
if (size == 0) return false;
bool foundIt = false;
Node<T> * pre = findInsertPoint(&head,val);
while (pre->next != NULL && pre->next->info == val) {
foundIt = true;
size--;
Node<T> * temp = pre->next;
if (temp == lastPtr)
lastPtr = pre;
pre->next = temp->next;
delete temp;
if (!removeAll) break; // only remove one instance of val
}
return foundIt;
}
void clear() {
// fill in code using hints below.
// clear the list and set size to 0
// be sure to call delete on every Node after head (avoid memory leaks).
}
bool find(const T & val) {
// fill in code using hint below.
// return true if val is in the list and false otherwise. Ti determine if val is in the list, callfindInsertionPoint
}
const T getSmallest() const {
if (isEmpty()) {
cout << "Error: no smallest element for empty list." << endl;
return T();
}
// fill in code... (easy since he have a head node.)
}
const T getBiggest() const {
if (isEmpty()) {
cout << "Error: no biggest element for empty list." << endl;
return T();
}
// fill in code... (easy since we have a lastPtr )
}
bool isEmpty() const {
// fill in code... (easy since we have a size member variable)
}
void print(bool separateLines = false) const {
if (!separateLines)
cout << *this << endl; // We just use the stream insertion operator defined above
else {
Node<T> * temp = head.next;
while (temp!= NULL) {
cout << temp->info << endl; // put in an endl right after outputting the data
temp = temp->next;
}
}
}
void printBackwards() const {
// fill in code...
// print values in reverse order, enclosed in braces (e.g. {5, 3, 1}
// First output "{ " then call printBackwardsHelper() to print the values in reverse order. Then output "}"
}
private:
Node<T> head; // This is a "dummy" head node like we discussed in class.
Node<T> * lastPtr;
int size;
void printBackwardsHelper(Node<T> * n) const {
// fill in code... (use recursion)
}
Node<T> * findInsertionPoint(Node<T> * pre, const T & val) {
for (;pre->next != NULL && val > pre->next->info; pre = pre->next); // find position
return pre;
}
// precondition: pre != NULL
void insertAfter(Node<T> * pre, Node<T> * theNode) {
theNode->next = pre->next;
pre->next = theNode;
if(theNode->next == NULL)
lastPtr = theNode;
}
// copy other list to *this
OList<T> & copy(const OList<T> & other) {
clear();
Node<T> * temp = other.head.next; // first real node of other
while (temp != NULL) {
// fill in code...
}
size = other.size;
return *this;
}
};
int main()
{
OList<int> list;
list.insert(5);
list.insert(1);
list.insert(6);
list.insert(3);
list.insert(4);
cout << list << endl;
system("pause");
return 0;
}
Sample output: