Experts please find the bug in this sorting list program

This is a discussion on Experts please find the bug in this sorting list program within the C Programming forums, part of the General Programming Boards category; Hi i have a bug in my program that i have been trying to find but i cant find it.I ...

  1. #1
    Registered User
    Join Date
    Nov 2011
    Posts
    118

    Experts please find the bug in this sorting list program

    Hi i have a bug in my program that i have been trying to find but i cant find it.I am trying to sort my data as i pass it in into a double linked list.My test data is 7,5,1. it works when there are only two numbers but when i increased it to three nodes this is what happens
    1,7. my five gets overwritten.
    Code:
    struct node{
        char key;
        struct node *next;
        struct node *previous;
    
    
    };
    
    
    struct listset{
        int length;
        struct node *head;
        struct node * tail;
        struct node *iterator;
    };
    struct listset * listset_new(){
        struct listset *p =(struct listset*) malloc(sizeof(*p));
        p->head=NULL;
        p->tail=NULL;
        p->iterator=NULL;
        p->iterator=NULL;
        return p;
    
    
    }
    /* add new item before current item. if the iterator ia at end of the
       list then add item to end of list */
    void list_add_before_current(struct listset * p,char item){
        
    
    
      struct node * temp = (struct node*)malloc(sizeof (*temp));
     
        if(list_at_end(p)){
        //at end of list
       // if(p->iterator->previous!=NULL&& p->iterator->next==NULL){
            temp->next=NULL;
            p->tail->next=temp;
    
    
            temp->key=item;
            temp->previous=p->tail;
            p->tail=temp;
    
    
    
    
      //  }
        }
        //if only one element in the list
        else if(p->iterator->previous==NULL&&p->iterator!=NULL){
            p->head=temp;
            temp->key=item;
            temp->next=p->iterator;
        }
        
        //anywhere in the list
        else
        {
            
            temp->key=item;
            p->iterator->previous->next=temp;  //pointing my former previous node next  to my new node
            p->iterator->previous=temp; //iterator previous now points to my new node
            temp->previous=p->iterator->previous; // new node previous  points tom my currents iterator previous
            temp->next=p->iterator; //new node next points to my iterator
    
    
        }
    
    
    }
    
    
    void list_move_to_start(struct listset *p){
     
      
    
    
        while(p->iterator->previous!=NULL){
            p->iterator=p->iterator->previous;
          
    
    
        }
      
    
    
    }
    
    
    
    
    void listset_add(struct listset * t, char item){
        struct listset *a=t;
        int found=0;
        struct node *temp= (struct node*)malloc(sizeof(*temp));
        if(t->head==NULL)
        {
        
        a->head=temp;
        a->tail=temp;
        temp->key=item;
        temp->previous=NULL;
        temp->next=NULL;
        a->iterator=temp; //when first element is added .iterator becomes my temp
       
        }
        else {
            while(a->iterator!=NULL && found!=1){
     
                
                if(item<a->iterator->key){
                    list_add_before_current(a, item);
                found=1;
                 list_move_to_start(a);}
                
                else
                    a->iterator=a->iterator->next;
       
            }//iner while
           
            if(a->iterator==NULL){
                 list_add_before_current(a, item);
           list_move_to_start(a);
            }
           
        }//else
        
    }
    //checking if a list is empty
    int isEmpty(struct listset *p){
    
    
        if(p->head==NULL)
            return 1;
    
    
        else
            return 0;
    }
    //removing an item from the end of the list
    void list_popBack(struct listset *p){
        if(p->tail->previous==NULL)
    {
        free(p->tail);
        p->head=NULL;
    }
    else {
        p->tail->previous->next=NULL;
        free(p->tail);
          }
    
    
    }
    
    
    void list_write_out(struct listset *p){
         struct node *current=p->head;
          while(current!=NULL){
              printf("%d ",current->key);
              current=current->next;
    
    
          }
    
    
    }
    
    
    /* move the iterator to the next item in the list */
    void list_move_to_next(struct listset * p){
        p->iterator=p->iterator->next;
    
    
    }
    
    
    int list_get_current(struct listset * p){
        int c=0;
    
    
        c= p->iterator->key;
        return c;
    
    
    
    
    }
    
    
    /* set the value of the current value of the list */
    void list_set_current(struct listset * p, char item){
    
    
        p->iterator->key=item;
    
    
    }
    
    
    /* delete the current item in the list */
    void list_delete_current(struct listset * p){
        if(p->iterator->previous==NULL)
       {
        free(p->iterator);
        p->head=NULL;
       }
       else {
        p->iterator->previous->next=p->iterator->next;
        free(p->iterator);
          }
    
    
     
    }
    /* check has the iterator moved past last item in list;
       always true if list is empty */
    int list_at_end(struct listset * p){
        if( (p->iterator==NULL &&  !isEmpty(p) )){
            return 1;
        //printf("at end of list");
        }
        else {
          //  printf(" notat end of list");
            return 0;}
        
    }
    
    
    
    
    
    
    
    
    int main(int argc, char** argv) {
        struct listset  *src1;
        struct listset  *src2;
        struct listset  *destination;
         src1=listset_new();
         src2=listset_new();
         destination=listset_new();
         char buffer[100];
         char x;
         int  choice;
    
    
     listset_add(src1, 7);
     listset_add(src1, 5);
     listset_add(src1, 1);

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,855
    > listset_add(src1, 7);
    The problem here, if add creates a new head node, then your pointer here is NOT updated.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User
    Join Date
    Nov 2011
    Posts
    118
    Quote Originally Posted by Salem View Post
    > listset_add(src1, 7);
    The problem here, if add creates a new head node, then your pointer here is NOT updated.
    a new node is created everytime the add function is called.When 7 is beeing added the list is empty so it performs the firstpart of myy add method

  4. #4
    Registered User
    Join Date
    Jun 2005
    Posts
    6,677
    Quote Originally Posted by sigur47 View Post
    a new node is created everytime the add function is called.When 7 is beeing added the list is empty so it performs the firstpart of myy add method
    That may be true, but Salem's point is valid.

    You are losing track of the head of your list.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Sunshine, and read this, this, and this before posting again.

  5. #5
    Registered User
    Join Date
    Nov 2011
    Posts
    118
    Quote Originally Posted by grumpy View Post
    That may be true, but Salem's point is valid.

    You are losing track of the head of your list.
    When the first node is put in , the head points to the first node so when the new node which the iterator and tail point to .When the second node is put in ,it gets linked withe the previous node in the list so its head(contains firstnode)->secondnode->null

  6. #6
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,855
    > Experts please find the bug in this sorting list program
    Are you even listening to what anyone says?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  7. #7
    Registered User
    Join Date
    Nov 2011
    Posts
    118
    Quote Originally Posted by Salem View Post
    > Experts please find the bug in this sorting list program
    Are you even listening to what anyone says?
    i am listening but i honestly cant find where am loosing track of my head

  8. #8
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,855
    Code:
     listset_add(src1, 7);
     printf("Head is %p\n", (void*)src1);
     listset_add(src1, 5);
     printf("Head is %p\n", (void*)src1);
     listset_add(src1, 1);
     printf("Head is %p\n", (void*)src1);
    If your goal is a list containing 1 5 7, then src1 should change with each call - it will not (as written).

    This you need to fix.

    Mostly, I do something like this, to cater for the possibility that the list will end up with a new head.
    head = insert(head,node);
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  9. #9
    Registered User
    Join Date
    Nov 2011
    Posts
    118
    Quote Originally Posted by Salem View Post
    Code:
     listset_add(src1, 7);
     printf("Head is %p\n", (void*)src1);
     listset_add(src1, 5);
     printf("Head is %p\n", (void*)src1);
     listset_add(src1, 1);
     printf("Head is %p\n", (void*)src1);
    If your goal is a list containing 1 5 7, then src1 should change with each call - it will not (as written).

    This you need to fix.

    Mostly, I do something like this, to cater for the possibility that the list will end up with a new head.
    head = insert(head,node);
    src1 is a listset that adds a new node whenever an item is added

  10. #10
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,855
    Yes, that's what you want.

    But the question is, did you add the print statements to see that this isn't happening?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. sorting columns in 2d array and find avgse
    By newbc in forum C Programming
    Replies: 4
    Last Post: 11-23-2010, 12:00 PM
  2. Replies: 16
    Last Post: 08-26-2008, 12:08 AM
  3. stl list find
    By l2u in forum C++ Programming
    Replies: 8
    Last Post: 09-06-2006, 03:53 PM
  4. std::list<*> sorting
    By ziruz in forum C++ Programming
    Replies: 18
    Last Post: 06-25-2003, 04:23 PM
  5. sorting array efficiently...can't find the error
    By Unregistered in forum C++ Programming
    Replies: 4
    Last Post: 04-09-2002, 03:32 PM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21