Homework SourseIn C Write a recursive function to determine whether or not
In C++
Write a recursive function to determine whether or not a Linked List is in sorted order (smallest value to largest value).
Add the following function prototypes to your List class under the section for access functions, then implement the functions below the class definition:
public:
/**Access Functions*/
bool isSorted();
//Wrapper function that calls the isSorted helper function to determine whether
//a list is sorted in ascending order.
//We will consider that a list is trivially sorted if it is empty.
//Therefore, no precondition is needed for this function
private:
bool isSorted(Nodeptr node);
//Helper function for the public isSorted() function.
//Recursively determines whether a list is sorted in ascending order.
#include //for NULL
#include
#include
using namespace std;
template //list stores generic list data, not any specific C++ type
class List
{
private:
struct Node
{
listdata data;
Node* next;
Node* previous;
Node(listdata data): data(data), next(NULL), previous(NULL){}
};
typedef struct Node* Nodeptr;
Nodeptr first;
Nodeptr last;
Nodeptr iterator;
int size;
public:
/**Constructors and Destructors*/
List();
//Default constructor; initializes and empty list
//Postcondition: numeric values equated to zero, or strings should be empty.
List(const List &list);
~List();
//Destructor. Frees memory allocated to the list
//Postcondition: position NodePtr at next Node
/**Accessors*/
listdata getFirst();
//Returns the first element in the list
//Precondition:NodePtr points to the first node on list
listdata getLast();
//Returns the last element in the list
//Precondition: make new node first on the list
listdata getIterator();
bool isEmpty();
//Determines whether a list is empty.
int getSize();
//Returns the size of the list
/**Manipulation Procedures*/
void startIterator();
void advanceIterator();
void removeLast();
//Removes the value of the last element in the list
//Precondition: list is not empty, not the first element.
//Postcondition: one remaining node
void removeIterator();
void removeFirst();
//Removes the value of the first element in the list
//Precondition: list is not empty
//Postcondition: no nodes left
void insertLast(listdata data);
//Inserts a new element at the end of the list
//If the list is empty, the new element becomes both first and last
//Postcondition: next equal to null
void insertFirst(listdata data);
//Inserts a new element at the start of the list
//If the list is empty, the new element becomes both first and last
//Postcondition:point nodePtr next node on list
/**Additional List Operations*/
bool offEnd();
void printList();
//Prints to the console the value of each element in the list sequentially
//and separated by a blank space
//Prints nothing if the list is empty
void insertIterator(listdata data);
bool operator==(const List &list);
};
// constructor definition
template
List::List(): first(NULL), last(NULL), iterator(NULL), size(0) {}
template
List::List(const List &list): size(list.size)
{
if(list.first == NULL) //If the original list is empty, make an empty list for this list
{
first = last = iterator = NULL;
}
else
{
first = new Node(list.first->data); //calling Node constructor
Nodeptr temp = list.first; //set a temporary node pointer to point at the first of the original list
iterator = first; //set iterator to point to first node of the new list
while(temp->next != NULL)
{
temp = temp->next; //advance up to the next node in the original list
iterator->next = new Node(temp->data); //using node constructor to create a new node with copy of data
iterator = iterator->next; //advance to this new node
}
last = iterator;
iterator = NULL;
}
}
template
List::~List()
{
Nodeptr cursor = first;
Nodeptr temp;
while(cursor != NULL)
{
temp = cursor->next;
delete cursor;
cursor = temp;
}
}
//inserts first node
template //Step 1: template the function
void List::insertFirst(listdata data)
{
if (size == 0) //Why is this necessary?
{
first = new Node(data);
last = first; //notice the order here. Assignment is right to left
}
else{
Nodeptr N = new Node(data);//create the new node by calling the node constructor
N->next = first;//set the new node\'s next field to point to the first node
first->previous = N;
first = N;}//point the first pointer to the new node
size++;
}
template
void List::printList()
{
iterator = first; //create a temporary iterator
while (iterator != NULL) {
cout<data< iterator = iterator->next; //Add two lines of code here
//Hint: One statement should contain a cout
}
cout << endl; //What does this do?
}
template
void List::insertLast(listdata data)
{
if (size == 0) //Why is this necessary?
{
Nodeptr n = new Node(data);
first = last = n; //notice the order here. Assignment is left to right
}
else
{
Nodeptr N = new Node(data);//create the new node by calling the node constructor
last->next = N;//set the new node\'s next field to point to the last node
last->previous = N;
last = N;//point the last pointer to the new node
}
size++;
}
template
void List::removeFirst()
{
if (size==0){
cout << \"removeFirst: List is empty. No data to remove.\" << endl;
} else if (size == 1) {
delete first;
first = last = NULL;
size = 0;
} else {
Nodeptr temp = first; //store pointer to first so we don\'t lose access to it
first = first->next; //advance the pointer
delete temp; //free the memory for the original first node
size--;
}
}
template
void List::removeLast()
{
if (size==0){
cout<<\"last is empty\";
} else if (size==1) {
delete last;
last = first = NULL;
size = 0;//fill in the missing lines here
} else {
last->previous->next=last->next;
delete last; //free the memory for the original last node
last->next = NULL; //so last->next is not pointing at freed memory
size--;
}
}
template
bool List::isEmpty()
{
return (size==0);
}
template
listdata List::getIterator()
{
assert(size != 0);
assert(iterator != NULL);
return iterator->data;
}
template
int List::getSize()
{
return size;
}
template
listdata List::getFirst()
{
assert(first != NULL);
return first->data;
}
template
listdata List::getLast()
{
assert(last != NULL);
return last->data;
}
template
void List::insertIterator(listdata data)
{
if(size==0)
cout<<\"list empty\"< else if(iterator == last)
{
insertLast(data);
}
else{
Nodeptr n = new Node(data);
n->next = iterator ->next;
n->previous = iterator;
iterator->next->previous=n;
iterator->next = n;
size++;
}
}
template
void List::startIterator()
{
iterator = first;
}
template
void List::advanceIterator()
{
iterator=iterator->next;
}
template
void List::removeIterator()
{
assert(iterator != NULL);
if (iterator == first) {
removeFirst();
} else if (iterator == last) {
removeLast();
} else {
iterator->previous->next = iterator->next;
iterator->next->previous = iterator->previous;
delete iterator;
iterator = NULL;
size--;
}
}
template
bool List::offEnd()
{
return iterator == NULL;
}
template
bool List::operator==(const List& list)
{
if(size != list.size)
return false;
Nodeptr temp1 = first;
Nodeptr temp2 = list.first;
while(temp1 != NULL)
{
if(temp1->data != temp2->data)
return false;
temp1 = temp1->next;
temp2 = temp2->next;
}
return true;
}
Solution
#include \"stdafx.h\" #include < iostream > #include < conio.h > #include < stdlib.h > using namespace std; struct node { int data; node *prev, *next; }*q, *temp, *start=NULL; int c1, c2 ; void create(); void display(); void insert(); void del(); void main() { system(\"cls\"); while(1) { system(\"cls\"); cout << \" \\t\\t ******* MAIN MENU ******\ \" ; cout << \" press 1 for adding data \ \" ; cout << \" press 2 for displaying data \ \" ; cout << \" press 3 for insertion \ \" ; cout << \" press 4 for deletion \ \" ; cout << \" press 0 for exit\ \" ; char ch; ch=getch(); switch(ch) { case \'1\': system(\"cls\"); create(); break; case \'2\': system(\"cls\"); display(); getch(); break; case \'3\': system(\"cls\"); insert(); break; case \'4\': system(\"cls\"); del(); break; case \'0\': exit(1); } } } void create() { temp = new node; temp -> next = NULL; cout << \"\ Enter data\ \" ; cin >> temp -> data ; if(start == NULL) { start = temp; temp -> prev = NULL; } else { q= start; while(q->next != NULL) { q = q->next; } q->next = temp; temp->prev = q; } } void display() { q=start; while(q!=NULL) { cout<
