Question

C++ program
Complete the following functions for linked list. You are not allowed to alter the names or the function prototypes.

#ifndef _ULL
#define _ULL
#include <iostream>
#include "nodeType.h"
using namespace std;

void initializeList(nodeType *&head, nodeType *&tail, int&count);
//Initialize the list to an empty state.
//Postcondition: head = NULL, tail = NULL, count = 0;

bool isEmptyList(const nodeType *head) ;
//Function to determine whether the list is empty.
//Postcondition: Returns true if the list is empty,
// otherwise it returns false.

void print(const nodeType *head) ;
//Function to output the data contained in each node.
//Postcondition: none

int length(const nodeType *head) ;
//Function to return the number of nodes in the list.
//Postcondition: The value of count is returned.

void destroyList(nodeType *& head, nodeType *& tail, int&count);
//Function to delete all the nodes from the list.
//Postcondition: head= NULL, tail = NULL, count = 0;

 

void insertFirst(..... you figure this out);
//Function to insert newItem at the end of the list.
//Postcondition: first points to the new list, newItem
// is inserted at the end of the list,
// last points to the last node in the list,
// and count is incremented by 1.

 

void insertLast(nodeType *&head, nodeType *&tail, int&count, const int& newItem);
//Function to insert newItem at the beginning of the list.
//Postcondition: first points to the new list, newItem is
// inserted at the beginning of the list,
// last points to the last node in the list,
// and count is incremented by 1.

 

bool search(nodeType *srcHead, const int &searchItem) ;
//Function to determine whether searchItem is in the list.
//Postcondition: Returns true if searchItem is in the
// list, otherwise the value false is
// returned.

 

void deleteNode(nodeType *&srcHead, nodeType *&srcTail, const int & deleteItem);
//Function to delete deleteItem from the list.
//Postcondition: If found, the node containing
// deleteItem is deleted from the list.
// first points to the first node, last
// points to the last node of the updated
// list, and count is decremented by 1.

 

void copyList(nodeType *srcHead, nodeType *dstHead, nodeType *dstTail, int &dstCount);
//Function to make a copy of otherList (src).
//Postcondition: A copy of otherList(src) is created and
// assigned to this list (dst).

After completing the functions, write the following menu based program that performs the listed functions.

<0> initializeList
<1> isEmptyList
<2> print
<a> Print src
<b> Print dst
<3> length
<4> destroyList
<5> search
<6> insertFirst
<7> insertLast
<8> deleteNode
<9> copyList
<Q> QuitRun your code,
using your menu to create a list with the following  int values 8,9,6,12,133,12,18,8,0,1
- search for 133
- search for 28
- copyList (deep copy src to dst)
- deleteNode 12 in src list
- print src
- print dst

Ensure that you destroy both list prior to "Quitting" your program.

Turn in your code along with a screenshot printing your list.

 

nodeType.h contains the struct

struct nodeType{
int data;
struct nodeType *next;
};

Answer 1

#ifndef _ULL
#define _ULL
#include <iostream>
#include "nodeType.h"
using namespace std;

void initializeList(nodeType *&head, nodeType *&tail, int&count)
{
//Initialize the list to an empty state.
//Postcondition: head = NULL, tail = NULL, count = 0
head=NULL;
tail=NULL;
count=0;
}

bool isEmptyList(const nodeType *head)
{
//Function to determine whether the list is empty.
//Postcondition: Returns true if the list is empty,
// otherwise it returns false.
if(head==NULL) return false;
return true;
}

void print(const nodeType *head)
{
//Function to output the data contained in each node.
//Postcondition: none
while(head!=NULL)
{
cout<<head->data<<" ";
head=head->next;
}
}

int length(const nodeType *head)
{
//Function to return the number of nodes in the list.
//Postcondition: The value of count is returned.
int Count=0;
while(head!=NULL)
{
Count++;
head=head->next;
}
return Count;
}

void destroyList(nodeType *& head, nodeType *& tail, int&count)
{
//Function to delete all the nodes from the list.
//Postcondition: head= NULL, tail = NULL, count = 0;
struct nodeType* current = head;
struct nodeType* next;
while (current != NULL) {
next = current->next;
delete (current);
current = next;
}
head= NULL;
tail=NULL;
count=0;
}

void insertFirst(nodeType *&head,nodeType *&tail,const int& newItem, int& count)
{
//Function to insert newItem at the end of the list.
//Postcondition: first points to the new list, newItem
// is inserted at the end of the list,
// last points to the last node in the list,
// and count is incremented by 1.

nodeType *temp=new nodeType;
temp->data=newItem;
temp->next=NULL;
if(head==NULL && tail==NULL)
{
head=temp;
tail=temp;
}
else
{
tail->next=temp;
tail=temp;
}
count++;
}

void insertLast(nodeType *&head, nodeType *&tail, int&count, const int& newItem)
{
//Function to insert newItem at the beginning of the list.
//Postcondition: first points to the new list, newItem is
// inserted at the beginning of the list,
// last points to the last node in the list,
// and count is incremented by 1.
nodeType *temp=new nodeType;
temp->data=newItem;
temp->next=NULL;
if(head==NULL && tail==NULL)
{
head=temp;
tail=temp;
}
else
{
temp->next=head;
head=temp;
}
count++;
}

bool search(nodeType *srcHead, const int &searchItem)
{
//Function to determine whether searchItem is in the list.
//Postcondition: Returns true if searchItem is in the
// list, otherwise the value false is
// returned.
while(srcHead!=NULL)
{
if(srcHead->data==searchItem) return true;
srcHead=srcHead->next;
}
return false;
}

void deleteNode(nodeType *&srcHead, nodeType *&srcTail, const int & deleteItem,int& count)
{
//Function to delete deleteItem from the list.
//Postcondition: If found, the node containing
// deleteItem is deleted from the list.
// first points to the first node, last
// points to the last node of the updated
// list, and count is decremented by 1.
nodeType *prev=NULL;
nodeType *temp_head=srcHead;
if(temp_head!=NULL && temp_head->data==deleteItem)
{
srcHead=srcHead->next;
return;
}
while(temp_head!=NULL && temp_head->data!=deleteItem )
{
prev=temp_head;
temp_head=temp_head->next;
}
if(temp_head==NULL) return;
if(srcTail==temp_head)
{
srcTail=prev;
prev->next=NULL;
}

prev->next=temp_head->next;
count--;
}

void copyList(nodeType *srcHead, nodeType *&dstHead, nodeType *&dstTail, int &dstCount)
{
//Function to make a copy of otherList (src).
//Postcondition: A copy of otherList(src) is created and
// assigned to this list (dst)
nodeType *temp=srcHead;
dstHead=NULL;
dstTail=NULL;
while(temp!=NULL)
{
if(dstHead==NULL)
{
dstHead=new nodeType;
dstHead->data=temp->data;
dstHead->next=NULL;
dstTail=dstHead;
}
else
{
dstTail->next=new nodeType;
dstTail=dstTail->next;
dstTail->data=temp->data;
dstTail->next=NULL;
}
dstCount++;
temp=temp->next;
}
}

int main()
{
cout<<"Folllowing is the menu for operations on linked list:"<<endl;
cout<<"<0> initializeList"<<endl<<"<1> isEmptyList"<<endl<<"<2> print"<<endl<<" <a> Print src"<<endl<<" <b> Print dst"<<endl;
cout<<"<3> length"<<endl<<"<4> destroyList"<<endl<<"<5> search"<<endl<<"<6> insertFirstt"<<endl<<"<7> insertLast"<<endl;
cout<<"<8> deleteNode"<<endl<<"<9> copyList"<<endl<<"<Q> QuitRun your code,"<<endl;
char ch;
nodeType *head=new nodeType;
nodeType *tail=new nodeType;
int count;
nodeType *dest_head=new nodeType;
nodeType *dest_tail=new nodeType;
int dest_count;
while(true)
{
cout<<endl<<"Enter your choice: ";
cin>>ch;
if(ch=='0')
{
initializeList(head,tail,count);
initializeList(dest_head,dest_tail,dest_count);
}
else if(ch=='1')
{
isEmptyList(head);
}
else if(ch=='2')
{
char ch1;
cout<<"Enter choice -a or b: ";
cin>>ch1;
if(ch1=='a')
{
print(head);
}
else
{
print(dest_head);
}
}
else if(ch=='3')
{
cout<<length(head);
}
else if(ch=='4')
{
destroyList(head,tail,count);
}
else if(ch=='5')
{
cout<<"Enter item to be searched: ";
int item;
cin>>item;
if(search(head, item)) cout<<"Found!!"<<endl;
else cout<<"Not found!!"<<endl;
}
else if(ch=='6')
{
cout<<"Enter item to be insert: ";
int item;
cin>>item;
insertFirst(head,tail,item, count);
}
else if(ch=='7')
{
cout<<"Enter item to be insert: ";
int item;
cin>>item;
insertLast(head,tail,count,item);
}
else if(ch=='8')
{
cout<<"Enter item to be delete: ";
int item;
cin>>item;
deleteNode(head,tail,item,count);
}
else if(ch=='9')
{
copyList(head, dest_head, dest_tail, dest_count);
}
else if(ch=='Q' || ch=='q') break;
else
{
cout<<"Wrong choice!!"<<endl;
}
}

delete head;

delete tail;

delete dest_head;

delete dest_tail;
}

CODE;

CODE OUTPUT SNAPSHOT: