sorting a double linked list using an iterator

This is a discussion on sorting a double linked list using an iterator within the C Programming forums, part of the General Programming Boards category; Hi i am having problems sorting my linked list using my iterator.Its meant to get an item to add to ...

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

    sorting a double linked list using an iterator

    Hi i am having problems sorting my linked list using my iterator.Its meant to get an item to add to a linked list and check if its less than any of the items already in the list.
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    
    /*
     *
     */
    
    
    
    
    
    
    struct node{
        int 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;
    
    
    }
    
    
    //checking if a list is empty
    int isEmpty(struct listset *p){
    
    
        if(p->head==NULL)
            return 1;
    
    
        else
            return 0;
    }
    /* 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;}
    
    
    }
    /* add new item before current iterator 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));
          //at end of list
        if(list_at_end(p)){
    
    
       // 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 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;
                }
    
    
                else
                    a->iterator=a->iterator->next;
    
    
      
            }//iner while
    
    
            if(list_at_end(a))
                 list_add_before_current(a, item);
        }//else
    }
    
    
    //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);
          }
    
    
    }

  2. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,444
    You should find a good debugger tutorial and run your program through a debugger.
    Code:
    while (a->iterator != NULL || found != 1)
    This line is a problem. If a->iterator is NULL, the first half of the OR evaluates to false, meaning it checks the second half. found != 1 is true, so the while loop does another iteration. That means when you get to this line:
    Code:
    if (item < (a->iterator->key))
    The a->iterator is NULL, and a->iterator->key causes your program to crash. You should use && instead of ||.

  3. #3
    Registered User
    Join Date
    Nov 2011
    Posts
    118
    Quote Originally Posted by anduril462 View Post
    You should find a good debugger tutorial and run your program through a debugger.
    Code:
    while (a->iterator != NULL || found != 1)
    This line is a problem. If a->iterator is NULL, the first half of the OR evaluates to false, meaning it checks the second half. found != 1 is true, so the while loop does another iteration. That means when you get to this line:
    Code:
    if (item < (a->iterator->key))
    The a->iterator is NULL, and a->iterator->key causes your program to crash. You should use && instead of ||.
    i used a || so that if the item is found it can exist the while loop without waiting for the iterator to become null

  4. #4
    Registered User
    Join Date
    Mar 2010
    Posts
    535
    Quote Originally Posted by sigur47 View Post
    i used a || so that if the item is found it can exist the while loop without waiting for the iterator to become null
    It doesn't do that though.

    Code:
    while (a->iterator != NULL || found != 1)
    Suppose found==1, and a->iterator is not NULL.

    It's then:
    Code:
    while (<notnullvalue> != NULL || 1 != 1)
    so

    Code:
    while (true || false)
    Because the iterator is NULL, that part evaluates to true, so the loop continues to execute, which isn't what you wanted.

    You really do want &&. You only want to loop if *both* iterator isn't NULL and found isn't 1.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. single linked list to double linked list (help)
    By Countfog in forum C Programming
    Replies: 8
    Last Post: 04-29-2008, 08:04 PM
  2. Double Linked List Sorting
    By algatt in forum C Programming
    Replies: 5
    Last Post: 09-15-2007, 12:41 PM
  3. Linked List Iterator
    By gflores in forum C++ Programming
    Replies: 9
    Last Post: 11-16-2004, 05:06 PM
  4. linked list iterator class inheritience
    By neandrake in forum C++ Programming
    Replies: 2
    Last Post: 11-14-2004, 09:03 AM
  5. sorting a double linked list
    By Strut in forum Linux Programming
    Replies: 5
    Last Post: 10-19-2002, 04:30 AM

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