514,196 views
6 votes
6 votes
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).

User Munsu
by
2.7k points

1 Answer

17 votes
17 votes

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!\\";

}

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:

Develop a program that will maintain an ordered linked list of positive whole numbers-example-1
User TietjeDK
by
2.9k points