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. Dont 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

using namespace std;

template

struct NodeType

{

ItemType info;

NodeType* next;

};

template

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 * listData;

int length;

NodeType* currentPos;

};

template

SortedType::SortedType() // Class constructor

{

length = 0;

listData = NULL;

}

template

bool SortedType::IsFull() const

// Returns true if there is no room for another ItemType

// on the free store; false otherwise.

{

NodeType* location;

try

{

location = new NodeType;

delete location;

return false;

}

catch (std::bad_alloc exception)

{

return true;

}

}

template

int SortedType::GetLength() const

// Post: Number of items in the list is returned.

{

return length;

}

template

void SortedType::MakeEmpty()

// Post: List is empty; all items have been deallocated.

{

NodeType* tempPtr;

while (listData != NULL)

{

tempPtr = listData;

listData = listData->next;

delete tempPtr;

}

length = 0;

}

template

void SortedType::PutItem(ItemType item)

// item is in the list; length has been incremented.

{

NodeType * newNode; //pointer to node being inserted

NodeType * predLoc; // Trailing Pointer

NodeType * 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;

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

ItemType SortedType::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 * 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

void SortedType::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* tempLocation = NULL;

NodeType * predLoc; // Trailing Pointer

NodeType * 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

void SortedType::ResetList()

// Post: Current position has been initialized.

{

currentPos = NULL;

}

template

ItemType SortedType::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

void SortedType::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

#include

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

using namespace std;

template

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

StackArr::StackArr()

{

maxStack = 100;

top = -1;

items = new ItemType[maxStack];

length = 0;

}

template

StackArr::StackArr( int max)

{

maxStack = max;

top = -1;

items = new ItemType[maxStack];

length = 0;

}

template

bool StackArr::IsEmpty() const

{

return (top == -1);

}

template

bool StackArr::IsFull() const

{

return (top == maxStack - 1);

}

template

void StackArr::Push(ItemType item)

{

if (IsFull())

{

cout << "The stack is full and item cannot be pushed";

}

else

{

top++;

items[top] = item;

length++;

}

}

template

void StackArr::Pop()

{

if(IsEmpty())

{

cout << "The stack is empty and item cannot be popped";

}

else

{

top--;

length--;

}

}

template

ItemType StackArr::Top() const

{

if (IsEmpty())

{

cout << "The stack is empty and no item on top";

}

else

return items[top];

}

template

void StackArr::PrintStack()

{

if (length == 0)

cout << "Stack is empty" << endl;

else

{

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

cout << items[i] << ", ";

cout << endl;

}

}