Have this outline for a singly linked list program need to figure out how to wri
ID: 3748828 • Letter: H
Question
Have this outline for a singly linked list program need to figure out how to write the code for the InsertItem, FreeNodes and DisplayList functions in c++
#include
#include
#include
#include
using namespace std;
// linked list structure
struct LNode
{
int item;
LNode *next;
};
// function prototypes
int DisplayList(const LNode *head);
void DisplayMenu();
void FlushInstream(istream &inStream = cin);
int FreeNodes(LNode *head);
LNode* InsertItem(LNode *head, int index, int item, bool &bSuccess);
// ==== main ==================================================================
//
// ============================================================================
int main()
{
bool bLoop = true;
bool bResult;
char selection;
int index;
int intVal;
int numInts = 0;
LNode *headPtr = NULL;
// allow the user to manipulate the list
do {
// display the main menu
DisplayMenu();
// get the user selection
cout << " Please enter your selection: ";
cin >> selection;
// call the appropriate member function
switch (toupper(selection))
{
case 'A':
// get a new integer value to insert
cout << "Please enter a value to insert: ";
if (!(cin >> intVal))
{
cout << "Error reading int, please try again... ";
FlushInstream();
continue;
}
// get an index
cout << "Please enter a target index: ";
if (!(cin >> index))
{
cout << "Error reading int, please try again... ";
FlushInstream();
}
else if ((index > numInts) || (index < 0))
{
cout << "Index is out of range... ";
continue;
}
else
{
headPtr = InsertItem(headPtr, index, intVal, bResult);
if (false == bResult)
{
cout << "Sorry, insertion failed... ";
}
else
{
++numInts;
}
}
break;
case 'C':
// release all nodes in the list
if (NULL == headPtr)
{
cout << "List is currently empty." << endl;
}
else
{
numInts = FreeNodes(headPtr);
cout << numInts;
cout << " item";
cout << ((1 == numInts) ? " " : "s ");
cout << "released." << endl;
headPtr = NULL;
numInts = 0;
}
break;
case 'D':
// display the current contents of the list
if (NULL == headPtr)
{
cout << "List is currently empty." << endl;
}
else
{
cout << "Here is the list:" << endl;
DisplayList(headPtr);
cout << "There ";
cout << ((1 == numInts) ? "is " : "are ");
cout << numInts << " item";
cout << ((1 == numInts) ? "" : "s");
cout << " in the list" << endl;
}
break;
case 'Q':
bLoop = false;
numInts = FreeNodes(headPtr);
cout << numInts;
cout << " item";
cout << ((1 == numInts) ? " " : "s ");
cout << "released. Bye!" << endl;
break;
default:
cout << "Unrecognized response; try again... ";
break;
} // end of switch
} while (true == bLoop);
return 0;
} // end of "main"
// ==== DisplayMenu ===========================================================
//
// This function displays the menu selections to stdout.
//
// Input:
// Nothing.
//
// Output:
// Nothing.
//
// ============================================================================
void DisplayMenu()
{
cout << " Do you wish to: ";
cout << " A)dd a new item to the list ";
cout << " D)isplay the current contents of the list ";
cout << " C)lear the list ";
cout << " Q)uit the program ";
} // end of "DisplayMenu"
// ==== DisplayList ===========================================================
//
// This function displays the current contents of the list to stdout.
//
// Input:
// head [IN] -- a pointer to the head of the linked list
//
// Output:
// The number of items written to stdout.
//
// ============================================================================
int DisplayList(const LNode *head)
{
??
} // end of "DisplayList"
// Input:
// inStream -- a reference to the input stream to flush
//
// Output:
// Nothing.
//
// ============================================================================
void FlushInstream(istream &inStream)
{
char inChar;
inStream.clear();
while (false == inStream.eof())
{
inStream.get(inChar);
if (' ' == inChar)
{
break;
}
}
} // end of "FlushInstream"
// ==== FreeNodes =============================================================
//
// This function traverses the linked list and releases the memory allocated
// for each individual node.
//
// Input:
// head -- a pointer to the head of the linked list
//
// Output:
// The total number of nodes released is returned.
//
// ============================================================================
int FreeNodes(LNode *head)
{
???
} // end of "FreeNodes"
// ==== InsertItem ============================================================
//
// This function inserts a new item into the list. If the item is inserted
// successfully, the boolean parameter is set to true, otherwise it is set to
// false.
//
// Input:
// head [IN] -- a pointer to the first node in the linked list
//
// index [IN] -- the zero-based location index for the new item
//
// item [IN] -- the integer value to insert into the list
//
// bSuccess [OUT] -- the boolean result of the insert operation (true
// if successful, false if not)
//
// Output:
// A pointer to the (potentially new) head of the linked list.
//
// ============================================================================
LNode* InsertItem(LNode *head, int index, int item, bool &bSuccess)
{
??
} // end of "InsertItem"
Explanation / Answer
Please find the response to your question below. Let me know if you have any concerns.
LNode* InsertItem(LNode *head, int index, int item, bool &bSuccess)
{ if(bSuccess==false){//if bSuccess equals false,return null
return NULL; //gives an instant to the random null memory as insertion fails
}
else{
struct LNode *tmp;//tmp node to be added at position index
struct LNode *leftNode,*rightNode;//after node leftNode and before rightNode
rightNode=head;
for(int i=1;i<index;i++)//iterate the list until the index is found at which node is to be inserted
{
leftNode=rightNode;
rightNode=rightNode->next;
}
tmp= new LNode;//create a new Node tmp,insert it after at index,
tmp->data=item;//and initialize the next Node of leftNode to tmp,and
leftNode->next=tmp;//next node of temp to rightNode
leftNode=temp;
leftNode->next=rightNode;
return head;}//return the initial point (head) on node
} // end of "InsertItem"
int FreeNodes(LNode *head)
{
struct LNode *temp =head;//create a temp node which equals head
while(head != NULL){//iterate through the list until the list is empty
temp=head->next;//assign temp as next node of temp
free(head);//free head
head=temp;// make temp node as head
}
return 1;
} // end of "FreeNodes"
int DisplayList(const LNode *head){
while(head!=NULL){// iterate through the list until end is found.
cout<<head->item<<" ";//print the item value of head
head=head->next;
}
return 1;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.