Answered step by step
Verified Expert Solution
Question
1 Approved Answer
//LinkedList.h #ifndef LINKEDLIST_H_ #define LINKEDLIST_H_ #include using namespace std; template class LinkedList{ private: struct LinkedListNode{ T element; LinkedListNode* next; LinkedListNode(); LinkedListNode(T element); LinkedListNode(T element, LinkedListNode*
//LinkedList.h
#ifndef LINKEDLIST_H_
#define LINKEDLIST_H_
#include
using namespace std;
template
class LinkedList{
private:
struct LinkedListNode{
T element;
LinkedListNode* next;
LinkedListNode();
LinkedListNode(T element);
LinkedListNode(T element, LinkedListNode* next);
~LinkedListNode();
};
LinkedListNode *head;
LinkedListNode *tail;
public:
LinkedList();
~LinkedList();
void insertFront(T element);
void insertBack(T element);
T removeFront();
T removeBack();
void print();
void reverseList();
void clear();
const LinkedListNode* getHead() const {
return head;
}
const LinkedListNode* getTail() const {
return tail;
}
};
template
LinkedList::LinkedListNode::LinkedListNode() {
this->next = NULL;
}
template
LinkedList::LinkedListNode::LinkedListNode(T element) {
this->element = element;
this->next = NULL;
}
template
LinkedList::LinkedListNode::LinkedListNode(T element,
LinkedListNode* next) : element(element), next(next) {
}
template
LinkedList::LinkedListNode::~LinkedListNode() {}
template
LinkedList::LinkedList() {
head = NULL;
tail = NULL;
}
template
LinkedList::~LinkedList() {
clear();
}
template
void LinkedList::insertFront(T element) {
LinkedListNode * new_node = new LinkedListNode(element);
new_node->next = head;
head = new_node;
if(tail == NULL)
tail = new_node;
}
template
void LinkedList::insertBack(T element) {
LinkedListNode * new_node = new LinkedListNode(element);
if(tail == NULL){
head = new_node;
}
else{
tail->next = new_node;
}
tail = new_node;
}
template
T LinkedList::removeFront() {
if(head == NULL){
throw "Removing from empty linked list";
}
LinkedListNode *old_head = head;
T return_element = old_head->element;
head = head->next;
if(head == NULL)
tail = NULL;
delete old_head;
return return_element;
}
template
T LinkedList::removeBack() {
LinkedListNode *old_tail = tail;
T return_element = old_tail->element;
if(head == NULL){
throw "Removing from empty linked list";
}
LinkedListNode *temp = head;
if(head == tail){
head = NULL;
tail = NULL;
}
while(temp->next != tail){
temp = temp->next;
}
temp->next = NULL;
tail = temp;
delete old_tail;
return return_element;
}
template
void LinkedList::print() {
LinkedListNode *temp = head;
if(temp == NULL)
cout
while(temp){
cout element
temp = temp->next;
}
cout
}
template
void LinkedList::reverseList() {
if(!head)
return;
if(head == tail)
return;
LinkedListNode* temp;
LinkedListNode* next;
LinkedListNode* prev;
tail = head;
prev = NULL;
temp = head;
while(temp){
next = temp->next;
temp->next = prev;
prev = temp;
temp = next;
}
head = prev;
}
template
void LinkedList::clear() {
while(head){
removeFront();
}
}
#endif /* LINKEDLIST_H_ */
//recursiveReverseWords
#include
#include
#include "LinkedList.h"
using namespace std;
string reverseWords(LinkedList list);
int main() {
LinkedList list; //A quick brown fox jumps over the lazy dog
list.insertBack("A");
list.insertBack("quick");
list.insertBack("brown");
list.insertBack("fox");
list.insertBack("jumps");
list.insertBack("over");
list.insertBack("the");
list.insertBack("lazy");
list.insertBack("dog");
cout
list.print();
string s = reverseWords(list);
cout
cout
list.clear();
list.insertBack("Thursday"); //Thursday
cout
list.print();
s = reverseWords(list);
cout
cout
list.clear();
list.insertBack("Algorithms"); //Algorithms and Data Structure Design
list.insertBack("and");
list.insertBack("Data");
list.insertBack("Structure");
list.insertBack("Design");
cout
1. Write a pseudocode using recursion to reverse such a sentence word by word. E.g., if the input sentence is "A quick brown fox jumps over the lazy dog", the output needs to be "dog lazy the over jumps fox brown quick A". Put your pseudocode, including all your sources, in a file called recursiveReverseWords.pdf. You cannot make the linked list doubly linked 2. Implement your pseudocode. You are provided a file called recursiveReversewords.cpp with a main function and the function declaration. Do not change the function declaration. The input parameter and return types must be as specified. You will need to include your implementation in this file. The main function includes some test cases In a separate file called LinkedList.h, you will find the template declaration for a linked list with the basic functionalities implemented. For bonus points, implement a function that checks if the element you insert into the linked list is a word (i.e., does not contain special characters or white spaces) list.print();
s = reverseWords(list);
cout
cout
return 0;
}
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started