This what I have // SLinkedList.h // Code from: // Data Structures and Algorithm

Question

This what I have

// SLinkedList.h
// Code from:
// Data Structures and Algorithms in C++, Goodrich, Tamassia, and Mount, 2nd Ed., 2011.
//
// #pragma once
#include <stdexcept>
#include <iostream>
using namespace std;
template <typename E>
class SLinkedList; // forward declaration to be used when declaring SNode
template <typename E>
class SNode
{ // singly linked list node
private:
E elem; // linked list element value
SNode<E> *next; // next item in the list
friend class SLinkedList<E>; // provide SLinkedList access
};
template <typename E>
class SLinkedList
{ // a singly linked list
public:
SLinkedList(); // empty list constructor
~SLinkedList(); // destructor
bool empty() const; // is list empty?
E &front(); // return front element
void addFront(const E &e); // add to front of list
void addBack(const E &e); // add to end of list
void removeFront(); // remove front item list

int size() const; // list size
void reverse();
private:
SNode<E> *head; // head of the list
int n; // number of items
};
template <typename E>
SLinkedList<E>::SLinkedList() // constructor
: head(NULL), n(0)
{
}
template <typename E>
bool SLinkedList<E>::empty() const // is list empty?
{
return head == NULL; // can also use return (n == 0);
}
template <typename E>
E &SLinkedList<E>::front() // return front element
{
if (empty())
  throw length_error("empty list");
return head->elem;
}
template <typename E>
SLinkedList<E>::~SLinkedList() // destructor
{
while (!empty())
  removeFront();
}
template <typename E>
void SLinkedList<E>::addFront(const E &e)
{ // add to front of list
SNode<E> *v = new SNode<E>; // create new node
v->elem = e; // store data
v->next = head; // head now follows v
head = v; // v is now the head
n++;
}
template <typename E>
void SLinkedList<E>::addBack(const E &e)
{ // add to front of list
SNode<E> *v = new SNode<E>; // create new node
v->elem = e; // store data
v->next = NULL; // head now follows v
if (head == NULL)
{
  head = v;
}
else
{
  SNode<E> *old = head; // save current head
  while (old->next != NULL)
  {
   old = old->next;
  }
  old->next = v;
}
n++;
}
template <typename E>
void SLinkedList<E>::removeFront()
{ // remove front item
if (empty())
  throw length_error("empty list");
SNode<E> *old = head; // save current head
head = old->next; // skip over old head
delete old; // delete the old head
n--;
}
template <typename E>
int SLinkedList<E>::size() const
{ // list size
return n;
}

template<typename E>
void SLinkedList<E>::reverse()
{


}

//SLinkedList.cpp

#include <stdexcept>
#include <iostream>
#include <cstring>
#include <string>
#include "SLinkedList.h"
using namespace std;
int main()
{
SLinkedList<char>s;
string inp;
cout << "Enter input: ";
getline(cin, inp);
for (int i=0; i<inp.length(); i++)
{
  s.addBack(inp[i]);
}
s.reverse();
system("pause");

}

#3 [4 points] Given a singly linked list as in Problem 2, write a public member function void SLinkedList::reverse() to re-orient the next pointers of all the nodes in a list to each point to the previous element. Add a helper function as needed. Use the code available from SLinkedList.h on our Github https://github.com/apanangadan/CSUF-CPSC 131 with modification to illustrate your approach. For the example given in Problem 2, the linked list will look like: 6

Explanation / Answer

// SLinkedList.h

// Code from:

// Data Structures and Algorithms in C++, Goodrich, Tamassia, and Mount, 2nd Ed., 2011.

//

// #pragma once

#include <stdexcept>

#include <iostream>

using namespace std;

template <typename E>

class SLinkedList; // forward declaration to be used when declaring SNode

template <typename E>

class SNode

{ // singly linked list node

private:

E elem; // linked list element value

SNode<E> *next; // next item in the list

friend class SLinkedList<E>; // provide SLinkedList access

};

template <typename E>

class SLinkedList

{ // a singly linked list

public:

SLinkedList(); // empty list constructor

~SLinkedList(); // destructor

bool empty() const; // is list empty?

E &front(); // return front element

void addFront(const E &e); // add to front of list

void addBack(const E &e); // add to end of list

void removeFront(); // remove front item list

int size() const; // list size

void reverse();

void print();

private:

SNode<E> *head; // head of the list

int n; // number of items

};

template <typename E>

SLinkedList<E>::SLinkedList() // constructor

: head(NULL), n(0)

{

}

template <typename E>

bool SLinkedList<E>::empty() const // is list empty?

{

return head == NULL; // can also use return (n == 0);

}

template <typename E>

E &SLinkedList<E>::front() // return front element

{

if (empty())

throw length_error("empty list");

return head->elem;

}

template <typename E>

SLinkedList<E>::~SLinkedList() // destructor

{

while (!empty())

removeFront();

}

template <typename E>

void SLinkedList<E>::addFront(const E &e)

{ // add to front of list

SNode<E> *v = new SNode<E>; // create new node

v->elem = e; // store data

v->next = head; // head now follows v

head = v; // v is now the head

n++;

}

template <typename E>

void SLinkedList<E>::addBack(const E &e)

{ // add to front of list

SNode<E> *v = new SNode<E>; // create new node

v->elem = e; // store data

v->next = NULL; // head now follows v

if (head == NULL)

{

head = v;

}

else

{

SNode<E> *old = head; // save current head

while (old->next != NULL)

{

old = old->next;

}

old->next = v;

}

n++;

}

template <typename E>

void SLinkedList<E>::removeFront()

{ // remove front item

if (empty())

throw length_error("empty list");

SNode<E> *old = head; // save current head

head = old->next; // skip over old head

delete old; // delete the old head

n--;

}

template <typename E>

int SLinkedList<E>::size() const

{ // list size

return n;

}

template <typename E>

void SLinkedList<E>::reverse()

{

SNode<E> *prev = NULL, *current = head, *next;

while (current != NULL)

{

next = current->next;

current->next = prev;

prev = current;

current = next;

}

head = prev;

}

template <typename E>

void SLinkedList<E>::print()

{

SNode<E> *temp = head;

while (temp != NULL)

{

cout << temp->elem;

temp = temp->next;

}

cout << endl;

}

//SLinkedList.cpp

#include <stdexcept>

#include <iostream>

#include <cstring>

#include <string>

#include "SLinkedList.h"

using namespace std;

int main()

{

SLinkedList<char> s;

string inp;

cout << "Enter input: ";

getline(cin, inp);

for (int i = 0; i < inp.length(); i++)

{

s.addBack(inp[i]);

}

cout<<"Current List is: "<<endl;

s.print();

s.reverse();

cout<<"Reverse of List is:"<<endl;

s.print();

system("pause");

}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.