Go4Expert (http://www.go4expert.com/)
-   C (http://www.go4expert.com/forums/c/)
-   -   bst and doubly linked list (http://www.go4expert.com/forums/bst-doubly-linked-list-t15696/)

airmang 1Jan2009 17:41

bst and doubly linked list
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:

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;

// 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;

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:

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;
    {        image_entry=n->image_entry;    }

    if (LIST==NULL) {
        printf("list is empty\n");
        return EXIT_FAILURE;

    //delete from list
        image_entry->previous->next = image_entry->next;

        image_entry->next->previous = image_entry->previous;

    //delete from bst
    bst_delete(ROOT,n); //already constructed

    //delete from memory
  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!!!

xpi0t0s 5Jan2009 01:29

Re: bst and doubly linked list
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:

+-+ 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.

All times are GMT +5.5. The time now is 05:55.