Question

Develop a program that will maintain an ordered linked list of positive whole numbers. Your program will provide for the following options: a. Add a number b. Delete a number c. Search for a number d. Display the whole list of numbers At all times, the program will keep the list ordered (the smallest number first and the largest number last).

Answer 1

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: