Thread: Sorting singly linked list using insertion sort and deleting certin nodes

  1. #1
    Registered User
    Join Date
    May 2016
    Posts
    3

    Sorting singly linked list using insertion sort and deleting certin nodes

    So the whole concept is to sort a singly linked list using insertion sort and deleting the nodes in order. The other codes are given, so all I have to do is fill in the "void InsertNode(int v)" and "void DeleteNode(int v)" and I am having trouble with it.

    The result should be something like:
    50 30 20 10 70 80 60 90 100 40
    50 is inserted
    30 is inserted
    20 is inserted
    ...
    100 is inserted
    10 20 30 40 50 60 70 80 90 100
    Good Job!
    50 is deleted
    10 20 30 40 60 70 80 90 100
    30 is deleted
    10 20 40 60 70 80 90 100
    20 is deleted
    10 40 60 70 80 90 100
    10 is deleted
    40 60 70 80 90 100
    70 is deleted
    40 60 80 90 100
    80 is deleted
    40 60 90 100
    60 is deleted
    40 90 100
    90 is deleted
    40 100
    100 is deleted
    40
    40 is deleted
    But mine would be like:
    50 30 20 10 70 80 60 90 100 40
    50 is inserted
    30 is inserted
    20 is inserted
    ...
    100 is inserted
    0
    Good Job!
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    Code:
    #include <iostream>
    #include <cstdlib>
    #include <ctime>  
    using namespace std;
    class Node{
       public:
          int value;
          Node *next;
    }; 
    class LinkedList{ //Singly Linked List
    public:
       LinkedList(){
       head=NULL;
       } 
       void SubMain(){
          bool result;   
          UniqueRandomData(10);
          CallInsertNode();
          PrintNode();
          result=CheckNode();
          CallDeleteNode(); 
       }
       void UniqueRandomData(int n){
          int i, j, k, temp;
          this->n=n;   
          x=new int[n]; 
       
       for(i=0; i<n; i++)
       x[i]=(i+1)*10; 
       
       for(i=0; i<n; i++){
          j=rand()%n;
          k=rand()%n;
          
          temp=x[j];
          x[j]=x[k];
          x[k]=temp;
       } 
       
       for(i=0; i<n; i++)
       cout<<x[i]<<" ";
       cout<<endl;
       }
    
       void InsertNode(int v){
          cout<<v<<" is inserted."<<endl;
    
          if (head == NULL) {
             head =  new Node();
           }
           else
           {
            head->next = new Node();
            head = head->next;
           }
                }
       }
       void PrintNode(){
          Node *cur=head; 
          while(cur!=0){
          cout<<cur->value<<" "; 
          cur=cur->next; 
          } 
       cout<<endl;
       }
       void CallInsertNode(){
          int i;
          for(i=0; i<n; i++)      
             InsertNode(x[i]);   
       }
       
       bool CheckNode(){
          Node *cur=head;
          while(cur !=NULL && cur->next !=NULL)
          if(cur->value > cur->next->value){
          cout<<"Error!"<<endl;
          cout<<cur->value<<", "<<cur->next->value<<endl;
          return false;
       }
       else 
       cur=cur->next;
       
       cout<<"Good job!"<<endl;
       return true;
       } 
       
       void CallDeleteNode(){
          int i;
       for(i=0; i<n; i++){  
          DeleteNode(x[i]); 
          this->PrintNode(); 
       }
       }
    
       void DeleteNode(int v){
           Node* prev = this->head;
            Node* current = this->head->next;
            while(current->value != v)
            {
                    current = current->next;
                    prev = prev->next;
            }
            if(current->value == v)
            {
                    prev->next = current->next;
                    delete current;
            }
          
          cout<<v<<" is deleted.";
          }
       
       private:
          Node *head;
          int *x;
          int n;
       
    }; 
    int main(){
       LinkedList a; 
       a.SubMain(); 
    }

  2. #2
    Tweaking master Aslaville's Avatar
    Join Date
    Sep 2012
    Location
    Rogueport
    Posts
    528
    I was going to look at your code only, it doesn't even compile.

  3. #3
    Registered User
    Join Date
    May 2016
    Posts
    3
    Quote Originally Posted by Aslaville View Post
    I was going to look at your code only, it doesn't even compile.
    strange 'cause it does in my dev c++

  4. #4
    Tweaking master Aslaville's Avatar
    Join Date
    Sep 2012
    Location
    Rogueport
    Posts
    528
    Quote Originally Posted by maria32 View Post
    strange 'cause it does in my dev c++
    May be you made a mistake when pasting ? Well, I can see for instance you have a class definition which is not followed by a semi-colon - that should not compile anywhere.

  5. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,863
    Quote Originally Posted by Aslaville
    Well, I can see for instance you have a class definition which is not followed by a semi-colon - that should not compile anywhere.
    It is not that there is a class definition which is not followed by a semi-colon: both class definitions are terminated with semi-colons. The problem is that there is an extra closing brace on line 56 (or 57, if you prefer), causing the compiler to mistake it as a class definition that is not terminated with a semi-colon when parsing the code.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #6
    Registered User
    Join Date
    May 2016
    Posts
    3
    okay so I corrected the code
    Code:
    #include <iostream>
    #include <cstdlib>
    #include <ctime>  
    using namespace std;
    class Node{
       public:
          int value;
          Node *next;
    }; 
    class LinkedList{ //Singly Linked List
    public:
       LinkedList(){
       head=NULL;
       } 
       void SubMain(){
          bool result;   
          UniqueRandomData(10);
          CallInsertNode();
          PrintNode();
          result=CheckNode();
          CallDeleteNode(); 
       }
       void UniqueRandomData(int n){
          int i, j, k, temp;
          this->n=n;   
          x=new int[n]; 
       
       for(i=0; i<n; i++)
       x[i]=(i+1)*10; 
       
       for(i=0; i<n; i++){
          j=rand()%n;
          k=rand()%n;
          
          temp=x[j];
          x[j]=x[k];
          x[k]=temp;
       } 
       
       for(i=0; i<n; i++)
       cout<<x[i]<<" ";
       cout<<endl;
       }
       void InsertNode(int v){
         cout<<v<<" is inserted"<<endl;
          
        Node *cur=head;//cur=head
     Node* node=new Node();//new Node
     
        while(cur!=NULL){
            Node *prev=cur;
         cur=cur->next;
            if(node>prev && node<cur)
       cur=prev->next;
      else if(node<prev){
       prev=node;
       cur=prev;
      }
        }
       }
       void PrintNode(){
          Node *cur=head; 
          while(cur!=0){
          cout<<cur->value<<" "; 
          cur=cur->next; 
          } 
       cout<<endl;
       }
       void CallInsertNode(){
          int i;
          for(i=0; i<n; i++)      
             InsertNode(x[i]);   
       }
       
       bool CheckNode(){
          Node *cur=head;
          while(cur !=NULL && cur->next !=NULL)
          if(cur->value > cur->next->value){
          cout<<"Error!"<<endl;
          cout<<cur->value<<", "<<cur->next->value<<endl;
          return false;
       }
       else 
       cur=cur->next;
       
       cout<<"Good job!"<<endl;
       return true;
       } 
       
       void CallDeleteNode(){
          int i;
       for(i=0; i<n; i++){  
          DeleteNode(x[i]); 
          this->PrintNode(); 
       }
       }
       void DeleteNode(int v){
            cout<<v<<" is deleted."<<endl;
      
     Node *cur=head; 
     Node *delNode=cur;
     
     while(cur!=NULL) 
     find(cur, delNode, );
     
     cur=cur->next;
     delete delNode;
         
       }
       
       private:
          Node *head;
          int *x;
          int n;
       
    }; 
    int main(){
       LinkedList a; 
       a.SubMain(); 
       return 0; 
       system("pause");
    }
    I fixed the codes for void InsertNode(int v) and void DeleteNode(int v) since these are the ones I have to solve and I don't know what to do with the find() in the void deleteNode(int v) btw.

  7. #7
    Tweaking master Aslaville's Avatar
    Join Date
    Sep 2012
    Location
    Rogueport
    Posts
    528
    Quote Originally Posted by maria32 View Post

    I don't know what to do with the find() in the void deleteNode(int v) btw.
    Do you need the function 'find', I guess not. Myself I could have had.

    Code:
    
       void DeleteNode(int v){
            cout<<v<<" is deleted."<<endl;
    
             Node *cur=head;
             Node *previous = head; //you will need to keep track of both the previous and current node.
             Node *delNode=cur;
    
              while(cur!=NULL) 
              if(cur->value == v)
                {
                  previous->next = delNode->next; //link previous node to next node skipping the one that matched.
                  delete delNode;
                  return;
                }
             previous = cur; //move one node next
             cur=cur->next;
       }
    And of course, I just wrote this out on the browser so I could have missed something.

    You should probably also return something as an indicator of either successful deletion or failure( none of the nodes contain the value v)
    Last edited by Aslaville; 05-16-2016 at 01:19 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 11
    Last Post: 02-20-2012, 10:38 PM
  2. deleting from a linked list if there are just 2 nodes
    By Nooby in forum C++ Programming
    Replies: 2
    Last Post: 04-10-2010, 11:55 PM
  3. Problems with deleting a node in a singly linked list
    By omishompi in forum C++ Programming
    Replies: 7
    Last Post: 02-23-2006, 06:27 PM
  4. Deleting node from singly linked list
    By Happy Man in forum C Programming
    Replies: 2
    Last Post: 04-16-2004, 06:56 AM
  5. singly linked list insertion
    By Unregistered in forum C++ Programming
    Replies: 4
    Last Post: 11-26-2001, 03:25 PM

Tags for this Thread