Below are some codes (8 Code Fragments). Put all of the code into a header file
ID: 3809928 • Letter: B
Question
Below are some codes (8 Code Fragments). Put all of the code into a header file (**.h).
Create a source.cpp to test (insert some elements into the list and using iterator, print out the elements of a list.)
Must have no compile error.
//Code Fragment: Begin-End
NodeList::Iterator NodeList::begin() const // begin position is first item
{
return Iterator(header->next);
}
NodeList::Iterator NodeList::end() const // end position is just beyond last
{
return Iterator(trailer);
}
//Code Fragment: Erase
void NodeList::erase(const Iterator& p) { // remove p
Node* v = p.v; // node to remove
Node* w = v->next; // successor
Node* u = v->prev; // predecessor
u->next = w; w->prev = u; // unlink p
delete v; // delete this node
n--; // one fewer element
}
void NodeList::eraseFront() // remove first
{
erase(begin());
}
//Code Fragment: Insert
// insert e before p
void NodeList::insert(const NodeList::Iterator& p, const Elem& e) {
Node* w = p.v; // p's node
Node* u = w->prev; // p's predecessor
Node* v = new Node; // new node to insert
v->elem = e;
v->next = w; w->prev = v; // link in v before w
v->prev = u; u->next = v; // link in v after u
n++;
}
void NodeList::insertFront(const Elem& e) // insert at front
{
insert(begin(), e);
}
//Code Fragment: Iterator-methods
NodeList::Iterator::Iterator(Node* u) // constructor from Node*
{
v = u;
}
Elem& NodeList::Iterator::operator*() // reference to the element
{
return v->elem;
}
// compare positions
bool NodeList::Iterator::operator==(const Iterator& p) const
{
return v == p.v;
}
bool NodeList::Iterator::operator!=(const Iterator& p) const
{
return v != p.v;
}
// move to next position
NodeList::Iterator& NodeList::Iterator::operator++()
{
v = v->next; return *this;
}
// move to previous position
NodeList::Iterator& NodeList::Iterator::operator--()
{
v = v->prev; return *this;
}
//Code Fragment: Simple
NodeList::NodeList() { // constructor
n = 0; // initially empty
header = new Node; // create sentinels
trailer = new Node;
header->next = trailer; // have them point to each other
trailer->prev = header;
}
int NodeList::size() const // list size
{
return n;
}
bool NodeList::empty() const // is the list empty?
{
return (n == 0);
}
//Code Fragment: Class
typedef int Elem; // list base element type
class NodeList { // node-based list
private:
// insert Node declaration here...
public:
// insert Iterator declaration here...
public:
NodeList(); // default constructor
int size() const; // list size
bool empty() const; // is the list empty?
Iterator begin() const; // beginning position
Iterator end() const; // (just beyond) last position
void insertFront(const Elem& e); // insert at front
void insertBack(const Elem& e); // insert at rear
void insert(const Iterator& p, const Elem& e); // insert e before p
void eraseFront(); // remove first
void eraseBack(); // remove last
void erase(const Iterator& p); // remove p
// housekeeping functions omitted...
private: // data members
int n; // number of items
Node* header; // head-of-list sentinel
Node* trailer; // tail-of-list sentinel
};
//Code Fragment: Iterator-class
class Iterator { // an iterator for the list
public:
Elem& operator*(); // reference to the element
bool operator==(const Iterator& p) const; // compare positions
bool operator!=(const Iterator& p) const;
Iterator& operator++(); // move to next position
Iterator& operator--(); // move to previous position
friend class NodeList; // give NodeList access
private:
Node* v; // pointer to the node
Iterator(Node* u); // create from node
};
//Code Fragment: Node-class
struct Node { // a node of the list
Elem elem; // element value
Node* prev; // previous in list
Node* next; // next in list
};
void NodeList::insertBack(const Elem& e) // insert at rear
{
insert(end(), e);
}
void NodeList::eraseBack() // remove last
{
erase(--end());
}
Explanation / Answer
PROGRAM CODE:
NodeList.h
/*
* NodeList.h
*
* Created on: 03-Apr-2017
* Author: kasturi
*/
#ifndef PROGRAMS_NODELIST_H_
#define PROGRAMS_NODELIST_H_
//Code Fragment: Class
typedef int Elem;
//Code Fragment: Node-class
struct Node { // a node of the list
Elem elem; // element value
Node* prev; // previous in list
Node* next; // next in list
};
//Code Fragment: Iterator-class
class Iterator { // an iterator for the list
public:
Elem& operator*(); // reference to the element
bool operator==(const Iterator& p) const; // compare positions
bool operator!=(const Iterator& p) const;
Iterator& operator++(); // move to next position
Iterator& operator--(); // move to previous position
friend class NodeList; // give NodeList access
private:
Node* v; // pointer to the node
Iterator(Node* u); // create from node
};
// list base element type
class NodeList { // node-based list
private:
// insert Node declaration here...
public:
// insert Iterator declaration here...
public:
NodeList(); // default constructor
int size() const; // list size
bool empty() const; // is the list empty?
Iterator begin() const; // beginning position
Iterator end() const; // (just beyond) last position
void insertFront(const Elem& e); // insert at front
void insertBack(const Elem& e); // insert at rear
void insert(const Iterator& p, const Elem& e); // insert e before p
void eraseFront(); // remove first
void eraseBack(); // remove last
void erase(const Iterator& p); // remove p
// housekeeping functions omitted...
private: // data members
int n; // number of items
Node* header; // head-of-list sentinel
Node* trailer; // tail-of-list sentinel
};
void NodeList::insertBack(const Elem& e) // insert at rear
{
insert(end(), e);
}
void NodeList::eraseBack() // remove last
{
erase(--end());
}
Iterator NodeList::begin() const // begin position is first item
{
return Iterator(header->next);
}
Iterator NodeList::end() const // end position is just beyond last
{
return Iterator(trailer);
}
//Code Fragment: Erase
void NodeList::erase(const Iterator& p) { // remove p
Node* v = p.v; // node to remove
Node* w = v->next; // successor
Node* u = v->prev; // predecessor
u->next = w; w->prev = u; // unlink p
delete v; // delete this node
n--; // one fewer element
}
void NodeList::eraseFront() // remove first
{
erase(begin());
}
//Code Fragment: Insert
// insert e before p
void NodeList::insert(const Iterator& p, const Elem& e) {
Node* w = p.v; // p's node
Node* u = w->prev; // p's predecessor
Node* v = new Node; // new node to insert
v->elem = e;
v->next = w; w->prev = v; // link in v before w
v->prev = u; u->next = v; // link in v after u
n++;
}
void NodeList::insertFront(const Elem& e) // insert at front
{
insert(begin(), e);
}
//Code Fragment: Iterator-methods
Iterator::Iterator(Node* u) // constructor from Node*
{
v = u;
}
Elem& Iterator::operator*() // reference to the element
{
return v->elem;
}
// compare positions
bool Iterator::operator==(const Iterator& p) const
{
return v == p.v;
}
bool Iterator::operator!=(const Iterator& p) const
{
return v != p.v;
}
// move to next position
Iterator& Iterator::operator++()
{
v = v->next; return *this;
}
// move to previous position
Iterator& Iterator::operator--()
{
v = v->prev; return *this;
}
//Code Fragment: Simple
NodeList::NodeList() { // constructor
n = 0; // initially empty
header = new Node; // create sentinels
trailer = new Node;
header->next = trailer; // have them point to each other
trailer->prev = header;
}
int NodeList::size() const // list size
{
return n;
}
bool NodeList::empty() const // is the list empty?
{
return (n == 0);
}
#endif /* PROGRAMS_NODELIST_H_ */
NodeList.cpp
/*
* NodeList.cpp
*
* Created on: 03-Apr-2017
* Author: kasturi
*/
#include "NodeList.h"
#include <iostream>
using namespace std;
int main()
{
NodeList list;
list.insertBack(4);
list.insertBack(5);
list.insertFront(3);
cout<<"[ ";
for(Iterator it = list.begin(); it!= list.end(); ++it)
{
cout<<*it<<" ";
}
cout<<"]";
}
OUTPUT:
[ 3 4 5 ]
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.