Directions: The problems in this assignment are full programming problems. For e
ID: 3542499 • Letter: D
Question
Directions: The problems in this assignment are full programming problems. For each program, submit your source code and project files. When adding files to your zip file use folders to keep projects separate. Remember to keep a copy of your work.
Write recursive functions that perform insertion and retrieval operations on a pointer-based sorted linked list of integers. The insertion function should be void, taking a head pointer and the item to be inserted as parameters. The retrieval function should take a head pointer and the item to be retrieved as parameters, and should return the item's position, or -1 if the item is not found in the list. Use these procedures to write a program that inputs a series of integers, inserting them into a list until 0 is entered. Then a second series of integers is input, until 0 is entered, and the position of each integer in the list is displayed. Example:
Enter numbers to be inserted (0 to end): 34 23 1 45 7 0
The list is: 1 7 23 34 45
Enter numbers to be retrieved (0 to end): 23 8 45 0
23 is at position 3
8 is not in the list
45 is at position 5
Note that the program should be able to handle requests to retrieve items that are not in the list.
Explanation / Answer
#include <iostream>
using namespace std;
/* Recursive functions
insertion
retrieval
pointer based sorted linked list of integers
also if 0 is entered it keeps inserting until 0 is entered.
*/
struct node
{
int item;
node *next;
};
// takes in the head pointer
// item to be inserted
//building the list here
void insertion(node *&HeadPtr, int NumberToInsert) {
HeadPtr->item=NumberToInsert;
HeadPtr->next=new node;
node *tmp=HeadPtr;
tmp->next=new node;
do {
cout << "Please input the number to insert: 0 to quit ";
cin >> NumberToInsert;
tmp->item=NumberToInsert;
if (tmp->item==0)
{
tmp->next=NULL;
} //end if
else
{
tmp->next=new node;
tmp=tmp->next;
} // end else
}while (NumberToInsert!=0); //end do -while
node *tmp2=HeadPtr;
tmp2=HeadPtr;
//sort the list
while (tmp2!=NULL)
{
if (tmp2->item >tmp2->next->item)
{
int temp=tmp2->item;
tmp2->item=tmp2->next->item;
tmp2->next->item=temp;
}
else
{tmp2==NULL;}
}
tmp2=HeadPtr;
// traverse the list
while (tmp2!=NULL)
{
cout << tmp2->item << " ";
tmp2=tmp2->next;
} // end while
}
int main() {
int number=-1;
node *HeadPtr=new node;
insertion(HeadPtr, number);
system("pause");
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.