Develop a program that will maintain an ordered linked list of positive whole numbers. Your program will provide for the followi
1 answer:
Answer:
#include <iostream>
using namespace std;
struct entry
{
int number;
entry* next;
};
void orderedInsert(entry** head_ref,entry* new_node);
void init_node(entry *head,int n)
{
head->number = n;
head->next =NULL;
}
void insert(struct entry **head, int n)
{
entry *nNode = new entry;
nNode->number = n;
nNode->next = *head;
*head = nNode;
}
entry *searchNode(entry *head, int n)
{
entry *curr = head;
while(curr)
{
if(curr->number == n)
return curr;
curr = curr->next;
}
}
bool delNode(entry **head, entry *ptrDel)
{
entry *curr = *head;
if(ptrDel == *head)
{
*head = curr->next;
delete ptrDel;
return true;
}
while(curr)
{
if(curr->next == ptrDel)
{
curr->next = ptrDel->next;
delete ptrDel;
return true;
}
curr = curr->next;
}
return false;
}
void display(struct entry *head)
{
entry *list = head;
while(list!=NULL)
{
cout << list->number << " ";
list = list->next;
}
cout << endl;
cout << endl;
}
//Define the function to sort the list.
void insertionSort(struct entry **h_ref)
{
// Initialize the list
struct entry *ordered = NULL;
// Insert node to sorted list.
struct entry *current = *h_ref;
while (current != NULL)
{
struct entry *next = current->next;
// insert current in the ordered list
orderedInsert(&ordered, current);
// Update current
current = next;
}
// Update the list.
*h_ref = ordered;
}
//Define the function to insert and traverse the ordered list
void orderedInsert(struct entry** h_ref, struct entry* n_node)
{
struct entry* current;
/* Check for the head end */
if (*h_ref == NULL || (*h_ref)->number >= n_node->number)
{
n_node->next = *h_ref;
*h_ref = n_node;
}
else
{
//search the node before insertion
current = *h_ref;
while (current->next!=NULL &&
current->next->number < n_node->number)
{
current = current->next;
}
//Adjust the next node.
n_node->next = current->next;
current->next = n_node;
}
}
int main()
{
//Define the structure and variables.
char ch;int i=0;
entry *newHead;
entry *head = new entry;
entry *ptr;
entry *ptrDelete;
//Use do while loop to countinue in program.
do
{
//Define the variables
int n;
int s;
int item;
char choice;
//Accept the user choice
cout<<"Enter your choice:"<<endl;
cout<<"a. Add a number"<<endl
<<"b. Delete a number"<<endl
<<"c. Search for a number"<<endl
<<"d. Display the whole list of numbers"<<endl;
cin>>choice;
//Check the choice.
switch(choice)
{
//Insert an item in the list.
case 'a' :
// cin>>item;
cout<<"Enter the element:"<<endl;
cin>>item;
//To insert the first element
if(i==0)
init_node(head,item);
//To insert remaining element.
else
{
ptr = searchNode(head,item);
//Check for Duplicate data item.
if(ptr==NULL)
{
insert(&head,item);
}
else
{
cout<<"Duplicate data items not allowed";
cout<<endl<<"EnterAgain"<<endl;
cin>>item;
insert(&head,item);
}
}
insertionSort(&head);
i=i+1;
break;
//Delete the item from the list
case 'b' :
int numDel;
cout<<"Enter the number to be deleted :"<<endl;
cin>>numDel;
//Locate the node.
ptrDelete = searchNode(head,numDel);
if(ptrDelete==NULL)
cout<<"Element not found";
else
{
if(delNode(&head,ptrDelete))
cout << "Node "<< numDel << " deleted!\n";
}
break;
//Serach the item in the list.
case 'c' :
cout<<"Enter the element to be searched :";
cout<<endl;
cin>>s;
ptr = searchNode(head,s);
if(ptr==NULL)
cout<<"Element not found";
else
cout<<"Element found";
break;
//Display the list.
case 'd' :
display(head);
break;
default :
cout << "Invalid choice" << endl;
break;
}
//Ask user to run the program again
cout<<endl<<"Enter y to countinue: ";
cin>>ch;
}while(ch=='y'||ch=='Y');
return 0;
}
output:
You might be interested in