1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

bst and doubly linked list

Discussion in 'C' started by airmang, Jan 1, 2009.

  1. airmang

    airmang New Member

    Joined:
    Dec 5, 2008
    Messages:
    2
    Likes Received:
    0
    Trophy Points:
    0
    Happy New Year for all!!!

    I have a problem and I need your help. It is about image file manipulation in C.

    I have a BST (binary search tree) and a doubly linked list:
    Code:
    this is a part of my given definitions
    
    // Double-linked list node definition.
    // Multiple loaded images are stored in such lists
    typedef struct image_entry
    {
        IMAGE *image;
        char name[255];
        int changed;
        struct image_entry *next;
        struct image_entry *previous;
    } IMAGE_ENTRY;
    
    // A Binary Search Tree (BST) node, in order to index the images
    typedef struct node
    {
        IMAGE_ENTRY *image_entry;
        struct node *parent;
        struct node *left;
        struct node *right;
    } NODE;
    
    extern NODE *ROOT;  // Initially the BST is empty
    extern IMAGE_ENTRY *LIST;  // Initially no bmp file is loaded
    
    I have to write a function to close the image file, that is
    a) delete the image from the list
    b) delete the image from memory
    c) delete the node from tree

    I have implement the following:
    Code:
    int close_file(char name[])
    {
        IMAGE_ENTRY *image_entry;
        //Find the node in the linked-list using the BST index.
        NODE *n=(NODE*) bst_find(ROOT,name); //already constructed
        if (n==NULL) {
            printf("There is no file named %s.\n",name);
            return EXIT_FAILURE;
        }
        else
        {        image_entry=n->image_entry;    }
    
        if (LIST==NULL) {
            printf("list is empty\n");
            return EXIT_FAILURE;
        }
    
        //delete from list
        if(image_entry->previous==NULL)
            LIST->next=image_entry->next;
        else
            image_entry->previous->next = image_entry->next;
    
        if(image_entry->next==NULL)
            LIST->previous=image_entry->previous;
        else
            image_entry->next->previous = image_entry->previous;
        n->image_entry=image_entry;
    
        //delete from bst
        bst_delete(ROOT,n); //already constructed
    
        //delete from memory
        free(image_entry->image);
        free(image_entry);
       return EXIT_SUCCESS;
    }
    
    BUT it only works fine for a node that it's in the middle of the list...
    The problem appears when i try to delete from the begining or the end of the list....
    What am I doing wrong???
    Thanks in anvance!!!
     
  2. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,012
    Likes Received:
    203
    Trophy Points:
    0
    Occupation:
    Senior Support Engineer
    Location:
    England
    What I tend to do in situations like this is to work out on paper what should happen, then to try to figure out what the code should do from that. So I might get something like this:
    Code:
    +-+ A-> +-+ B-> NULL
    | |     |X|
    +-+ <-C +-+
    
    From this we can see that when we delete X, only pointer A needs modifying.

    Does LIST point to the top entry? If so you probably don't want to assign to LIST->previous.
     

Share This Page