There are two parts to the question. Make sure you implement both Use the implem
ID: 3755061 • Letter: T
Question
There are two parts to the question. Make sure you implement both
Use the implementation of Sorted linked list we used in class(SortLinkLst.h) and make the following changes. When we implemented, the items were being included in ascending order.
Change the list to accommodate the items in descending order. Use string as the item under consideration. (15 points)
The Link list should be a list of strings. Strings should be included in the list in descending order of the alphabet.
So for example if you are inserting the following strings “cart “, “mart “, “dart “, “part”, “art”
The strings should be included in descending order of the alphabet which is the following order
part mart dart cart and art
where the listData or header should point to ‘part’ which is the highest string in descending order.
Add the following two functions besides the regular ones:
public boolean findWordEndIn(char endAlphabet) (15 points)
// checks for the first word in the list which ends with a particular alphabet. For example if char ‘w’ is passed in it should return true if there is any word in the list which ends in w like saw or slaw etc. If there are more than one word you can stop with the first one and return true. Don’t need to search anymore.
public void displayListBackwards() ( 20 points) // prints the list in ascending order of alphabets
// displays the words in the reverse alphabetic order. So for example if the list is
‘part mart dart cart art’
//it should print out the list in reverse order.
art, cart, dart, mart, part
You can add any other constructors or methods if needed to implement this.
A palindrome is a word, phrase, number, or other sequence of characters which reads the same backward as forward, such as madam or racecar. Sentence-length palindromes may be written when allowances are made for adjustments to capital letters, punctuation, and word dividers, such as "A man, a plan, a canal, Panama!", "Was it a car or a cat I saw?" or "No 'x' in Nixon".
Write a program using Stacks-Array and Queue-Array data structure we did in class to check whether a given string is a palindrome. (50 points)
This is an exercise in Stacks and Queues. So you need to use both datastructures to test :
In the main you can test whether a string is a palindrome using the method
bool palindromeTest( string test) and should include “QueArr.h” and “StackArr.h”
SortLinkLst.h:
#include <iostream>
using namespace std;
template<class ItemType>
struct NodeType
{
ItemType info;
NodeType<ItemType>* next;
};
template<class ItemType>
class SortedType
{
public:
SortedType();
void MakeEmpty();
bool IsFull() const;
int GetLength() const;
ItemType GetItem(ItemType item, bool& found);
void PutItem(ItemType item);
void DeleteItem(ItemType item);
void ResetList();
ItemType GetNextItem();
void PrintItem(SortedType u);
private:
NodeType<ItemType> * listData;
int length;
NodeType<ItemType>* currentPos;
};
template<class ItemType>
SortedType<ItemType>::SortedType() // Class constructor
{
length = 0;
listData = NULL;
}
template<class ItemType>
bool SortedType<ItemType>::IsFull() const
// Returns true if there is no room for another ItemType
// on the free store; false otherwise.
{
NodeType<ItemType>* location;
try
{
location = new NodeType;
delete location;
return false;
}
catch (std::bad_alloc exception)
{
return true;
}
}
template<class ItemType>
int SortedType<ItemType>::GetLength() const
// Post: Number of items in the list is returned.
{
return length;
}
template<class ItemType>
void SortedType<ItemType>::MakeEmpty()
// Post: List is empty; all items have been deallocated.
{
NodeType<ItemType>* tempPtr;
while (listData != NULL)
{
tempPtr = listData;
listData = listData->next;
delete tempPtr;
}
length = 0;
}
template<class ItemType>
void SortedType<ItemType>::PutItem(ItemType item)
// item is in the list; length has been incremented.
{
NodeType<ItemType> * newNode; //pointer to node being inserted
NodeType<ItemType> * predLoc; // Trailing Pointer
NodeType<ItemType> * location; // traveling pointer to a node
bool moreToSearch;
location = listData;
predLoc = NULL;
moreToSearch = (location != NULL);
while (moreToSearch)
{
if (item > location->info)
{
predLoc = location;
location = location->next;
moreToSearch = (location != NULL);
}
else if (item < location->info)
{
moreToSearch = false;
break;
}
}
newNode = new NodeType<ItemType>;
newNode->info = item;
if (predLoc == NULL) //Insert as first
{
newNode->next = listData;
listData = newNode;
}
else
{
newNode->next = location;
predLoc->next = newNode;
}
length++; // Increment length of the list
}
template<class ItemType>
ItemType SortedType<ItemType>::GetItem(ItemType item, bool& found)
// Pre: Key member(s) of item is initialized.
// Post: If found, item's key matches an element's key in the
// list and a copy of that element has been returned;
// otherwise, item is returned.
{
bool moreToSearch;
NodeType<ItemType> * location;
location = listData;
found = false;
moreToSearch = (location != NULL);
while (moreToSearch && !found)
{
if(item == location->info)
{
found = true;
item = location->info;
break;
}
else if (item > location->info)
{
location = location->next;
moreToSearch = (location != NULL);
}
else
{
moreToSearch = false;
break;
}
}
return item;
}
template<class ItemType>
void SortedType<ItemType>::DeleteItem(ItemType item)
// Pre: item's key has been initialized.
// An element in the list has a key that matches item's.
// Post: No element in the list has a key that matches item's.
{
NodeType<ItemType>* tempLocation = NULL;
NodeType<ItemType> * predLoc; // Trailing Pointer
NodeType<ItemType> * location; // traveling pointer to a node
bool moreToSearch;
location = listData;
predLoc = NULL;
moreToSearch = (location != NULL);
// Locate node to be deleted.
if (item == listData->info)
{
tempLocation = location;
listData = listData->next; // Delete first node.
}
else
{
while (moreToSearch)
{
if (item == location->info)
{
moreToSearch = false;
predLoc->next = location->next;
tempLocation = location;
}
else if (item > location->info)
{
predLoc = location;
location = location->next;
moreToSearch = (location != NULL);
}
else if (item < location->info)
{
moreToSearch = false;
break;
}
}
}
delete tempLocation;
length--;
}
template<class ItemType>
void SortedType<ItemType>::ResetList()
// Post: Current position has been initialized.
{
currentPos = NULL;
}
template<class ItemType>
ItemType SortedType<ItemType>::GetNextItem()
// Post: A copy of the next item in the list is returned.
// When the end of the list is reached, currentPos
// is reset to begin again.
{
ItemType item;
if (currentPos == NULL)
currentPos = listData;
item = currentPos->info;
currentPos = currentPos->next;
return item;
}
template<class ItemType>
void SortedType<ItemType>::PrintItem(SortedType list)
// Pre: list has been initialized.
// dataFile is open for writing.
// Post: Each component in list has been written to dataFile.
// dataFile is still open.
{
int length;
ItemType item;
list.ResetList();
length = list.GetLength();
if (length == 0)
cout << "List is Empty";
for (int counter = 1; counter <= length; counter++)
{
item = list.GetNextItem();
cout << item << " ";
}
cout << endl;
}
QueArr.h:
#include <iostream>
#include <string>
using namespace std;
typedef string ItemType;
class QueType
{
public:
QueType();
QueType(int max);
~QueType();
void MakeEmpty();
bool IsEmpty() const;
bool IsFull() const;
void Enqueue(ItemType newItem);
void Dequeue(ItemType& item);
void Print();
private:
int front;
int rear;
ItemType* items;
int maxQue;
int length;
};
QueArr.cpp:
#include "QueArr.h"
QueType::QueType() // Default class constructor.
// Post: maxQue, front, and rear have been initialized.
// The array to hold the queue elements has been dynamically
// allocated.
{
maxQue = 501;
front = maxQue - 1;
rear = maxQue - 1;
items = new ItemType[maxQue];
length = 0;
}
QueType::QueType(int max)
// Parameterized class constructor.
// Post: maxQue, front, and rear have been initialized.
// The array to hold the queue elements has been dynamically allocated.
{
maxQue = max + 1;
front = maxQue - 1;
rear = maxQue - 1;
items = new ItemType[maxQue];
length = 0;
}
QueType::~QueType() // Class destructor.
{
delete[] items;
}
void QueType::MakeEmpty()
// Post: front and rear have been reset to the empty state.
{
front = maxQue - 1;
rear = maxQue - 1;
}
bool QueType::IsEmpty() const
// Returns true if the queue is empty; false otherwise.
{
return (rear == front);
}
bool QueType::IsFull() const
// Returns true if the queue is full; false otherwise.
{
return ((rear + 1) % maxQue == front);
}
void QueType::Enqueue(ItemType newItem)
// Post: If (queue is not full) newItem is at the rear of the queue;
// otherwise, a FullQueue exception is thrown.
{
if (IsFull())
{
//throw error;
cout << "Array is Full" << endl;
}
else
{
rear = (rear + 1) % maxQue;
items[rear] = newItem;
length++;
}
}
void QueType::Dequeue(ItemType& item)
// Post: If (queue is not empty) the front of the queue has been
// removed and a copy returned in item;
// otherwise, an EmptyQueue exception is thrown.
{
if (IsEmpty())
cout << "Array is Empty" << endl;
else
{
front = (front + 1) % maxQue;
item = items[front];
length--;
}
}
void QueType::Print()
{
if (length == 0)
cout << "Que is empty" << endl;
else
{
cout << front << ", " << length << endl;
int temp = front;
for (int i = 0; i < length; i++)
{
temp = (temp + 1) % maxQue;
cout << items[temp] << " ";
}
cout << endl;
}
}
StackArr.h:
#include <iostream>
using namespace std;
template <class ItemType>
class StackArr
{
public:
StackArr(); //Empty constructor
StackArr(int max); //Constructor which takes a size
bool IsEmpty() const;
bool IsFull() const;
void Push(ItemType item);
void Pop();
ItemType Top() const;
void PrintStack();
private:
int top;
int maxStack;
ItemType* items;
int length;
};
template <class ItemType>
StackArr<ItemType>::StackArr()
{
maxStack = 100;
top = -1;
items = new ItemType[maxStack];
length = 0;
}
template <class ItemType>
StackArr<ItemType>::StackArr( int max)
{
maxStack = max;
top = -1;
items = new ItemType[maxStack];
length = 0;
}
template <class ItemType>
bool StackArr<ItemType>::IsEmpty() const
{
return (top == -1);
}
template <class ItemType>
bool StackArr<ItemType>::IsFull() const
{
return (top == maxStack - 1);
}
template <class ItemType>
void StackArr<ItemType>::Push(ItemType item)
{
if (IsFull())
{
cout << "The stack is full and item cannot be pushed";
}
else
{
top++;
items[top] = item;
length++;
}
}
template <class ItemType>
void StackArr<ItemType>::Pop()
{
if(IsEmpty())
{
cout << "The stack is empty and item cannot be popped";
}
else
{
top--;
length--;
}
}
template <class ItemType>
ItemType StackArr<ItemType>::Top() const
{
if (IsEmpty())
{
cout << "The stack is empty and no item on top";
}
else
return items[top];
}
template <class ItemType>
void StackArr<ItemType>::PrintStack()
{
if (length == 0)
cout << "Stack is empty" << endl;
else
{
for (int i = 0; i < length; i++)
cout << items[i] << ", ";
cout << endl;
}
}
Explanation / Answer
Find a String is Palindrome or Not using C++ Stacks and Queues
Pre-Conditions :
QueArr.h to be implemented -- PASSED
StackArr.h to be implemented -- PASSED
C++ Code to find Passed String is palindrome using Data Structures (Stack and Queues)
#include<iostream>
#include<string>
#include "QueArr.h"
#include "StackArr.h"
using namespace std;
int main()
{
// declare variables
std::string testStr;
cout<<"Please Enter the String to be tested for Palindrome: "; //Prompt User to Enter the String
std::getline( std::cin, testStr); //Move the User Entered String to testStr Variable
if (testStr.empty()) //Id testStr is Empty then return from Program
{
return 0;
}
//If testStr passed has value then pass the string to function palindromeTest
palindromeTest(testStr);
//Implementation of bool palindromeTest function
bool palindromeTest (string testStr)
{
StackArr<char> lifo; //StackArr object Declaration
QueArr<char> fifo; //QueArr Object Declaration
unsigned int loop; //loop variable to read the String Variable as Char
for(loop = 0; loop < testStr.length; ++loop)
{
fifo.EnQueue(testStr[loop]);
lifo.Push(testStr[loop]);
cout<<"Copy String to StackArr and to QueArr:";
}
bool isPalindrome = true; //Validation param
//Determine String is Palindrome or Not
while((!fifo.empty()) && (!lifo.empty()) && isPalindrome)
{
if(fifo.Front() != lifo.Top())
{
isPalindrome = false;
}
else
{
//Values are matched so remove the entered values in stack and queue
fifo.DeQueue();
lifo.Pop();
}
//Display the Reult in Screen
if(isPalindrome)
{
cout<<"Entered String is a Palindrome !"<<endl;
return true;
}
else
{
cout<<"Entered String is NOT a Palindrome !"<<endl;
return false;
}
}
}
}
Output For the Above Code as follows:
Success Case
Please Enter the String to be tested for Palindrome: Liril
Entered String is a Palindrome !
Failure Case
Please Enter the String to be tested for Palindrome: Mango
Entered String is NOT a Palindrome !
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.