bst and doubly linked list

airmang's Avatar, Join Date: Dec 2008
Newbie Member
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!!!
0
xpi0t0s's Avatar, Join Date: Aug 2004
Mentor
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.