Linked List Processing This program will define various functions to process a l

Question

Linked List Processing This program will define various functions to process a linked list. The main program will demonstrate that the functions work. Input: An input file contains an unknown number of integers. Use a createList function to create the list with the integers in the info component of each list node. output: Use a printList function to output the info component of each listnode. Other functions are 1. find Max This function returns a pointer to the node which has the maxmum info value 2. add Last This function asks the user to input an integer, and inserts a new node containing that integer at the end of the list. 3. addFirst This function asks the user to input an integer, and inserts a new node containing that integer at the beginning of the list. 4. deleteMina This function locates the node with the minimum info value, and deletes it from the list. 5. sortList Ascending This function sorts the list so the integers in the info components of the nodes are in ascending order. 6. addlnorder This function gets an integer from the user, and inserts a node containing that integer into its proper place in a list which is sorted in ascending order. This function is not allowed to call the sortListAscending function!)

Explanation / Answer

//Tested on linux,Ubuntu

/******************program******************/

#include <iostream>
#include <fstream>
#include <malloc.h>
using namespace std;
//structure declaration
struct Node
{
int number;
struct Node* next;
};

struct Node *head=NULL;
//This function is used to get Node which has maximum value
Node* findMax(struct Node *firstNode) {
   //variable declarations
   struct Node *temp=firstNode,*maxNode;
   int max=0;
   //run the loop until temp become NULL
   while(temp!=NULL) {
       if(temp->number>max) {
           max=temp->number;
           maxNode=temp;
       }
       temp=temp->next;
      
   }
   //returning max Node
   return maxNode;
  
}
//This function is used to delete a node which has minimum value in list
void deleteMin(struct Node **firstNode) {
   //variable declaration and initialization
   struct Node *temp=*firstNode,*smallest=*firstNode,*prev;
   while(temp!=NULL){
       //checking if temp has next node and next node value less then smallest node value
       if(temp->next!=NULL&&temp->next->number<smallest->number) {
           smallest=temp->next;
           prev=temp;
       }
       temp=temp->next;
   }
   //if it is not head Node
       if(smallest!=*firstNode) {
           prev->next=smallest->next;
       } else{
           (*firstNode)=(*firstNode)->next;
       }  
      
      
      
  
}
//This function is used to sort linked list
void sortListAscending(struct Node **firstNode) {
   //variable declaration
struct Node *q,*p;
int data;
q=*firstNode;
//sorting logic
while(q!=NULL)
{
p=q->next;
while(p!=NULL)
{
if(q->number>p->number)
{
data=q->number;
q->number=p->number;
p->number=data;
}
p=p->next;
}
q=q->next;
}
}
/*Adding Node at front*/
void addFirst(struct Node** head, int num)
{
    if ((*head) == NULL) { // checking if first node is NULL or not
        (*head) = (struct Node*)malloc(sizeof(struct Node));
        (*head)->number = num;
        (*head)->next = NULL;
    }
    else {
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); //dynamically allocation of memory
        newNode->number = num;
        newNode->next = *head;
        *head = newNode;
    }
}
//AddNodetoEnd Method Implementation
void addLast(struct Node **lastNode, int num){
    if((*lastNode)==NULL){// checking if first node is NULL or not
        (*lastNode)=(struct Node*)malloc(sizeof(struct Node));
        (*lastNode)->number=num;
        (*lastNode)->next=NULL;
    }else{
       struct Node *temp=*lastNode;
        while(temp->next!=NULL){
            temp=temp->next;
        }
        struct Node *newNode=(struct Node*)malloc(sizeof(struct Node));//dynamically allocation of memory
        newNode->number=num;
        newNode->next=NULL;
        temp->next=newNode;
    }

}
/*addInOrder method implementation */
Node * addInOrder(Node *currNode, int num){
if(currNode==NULL){// checking if first node is NULL or not
currNode=(struct Node*)malloc(sizeof(struct Node));//dynamically allocation of memory
currNode->number=num;
currNode->next=NULL;
}
else{
struct Node *prev=currNode,*temp=currNode;
while(temp!=NULL){
if(temp->number>num)
break;
else{
prev=temp;
temp=temp->next;
}
}
struct Node* newNode=(struct Node*)malloc(sizeof(struct Node));//dynamically allocation of memory
newNode->number=num;
newNode->next=temp;
prev->next=newNode;
}
}
/*Display List Method Implementation*/
void printList (struct Node* firstNode){
    while(firstNode!=NULL){
        cout<<firstNode->number<<" ";
        firstNode=firstNode->next;
    }
cout<<endl;
}

int main() {
   //variable declaration
   std::string filename;
   int data;
  
   cout<<"Please Enter file Name: ";
   cin>>filename;
  
std::ifstream file(filename.c_str());

// Make sure the file stream is good
if(!file) {
    cout << endl << "Failed to open file " << filename;
    return 1;
}

int i;
while (file >> i) {
      //initially adding node at front side
   addFirst(&head,i);
}
//printing list
printList(head);
//adding number at END of List
addLast(&head,10);
addLast(&head,11);
addLast(&head,12);
//printing list
cout<<"Printing List After calling AddLast function"<<endl;
printList(head);

cout<<"Calling finMax Function"<<endl;
struct Node *temp=findMax(head);
cout<<"Max Number is: "<<temp->number<<endl;
cout<<"Deleting minimum value from Node"<<endl;
deleteMin(&head);
printList(head);
cout<<"Sorting Linked List by sortListAscending function"<<endl;
sortListAscending(&head);
printList(head);
cout<<"Calling AddInOrder function"<<endl;
cout<<"Please Enter number which you wana insert"<<endl;
cin>>data;
addInOrder(head,data);
printList(head);

return 0;
}

/************************test.txt content****************/

1
2
3
4
5
6
7
8
14

/********************output************************/

lalchand@lalchand:~/Desktop/chegg$ g++ LinkedListOperation.cpp
lalchand@lalchand:~/Desktop/chegg$ ./a.out
Please Enter file Name: test.txt
14 8 7 6 5 4 3 2 1
Printing List After calling AddLast function
14 8 7 6 5 4 3 2 1 10 11 12
Calling finMax Function
Max Number is: 14
Deleting minimum value from Node
14 8 7 6 5 4 3 2 10 11 12
Sorting Linked List by sortListAscending function
2 3 4 5 6 7 8 10 11 12 14
Calling AddInOrder function
Please Enter number which you wana insert
13
2 3 4 5 6 7 8 10 11 12 13 14

Thanks a lot

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.