l would not recommend an fixed sized array for your implementation, as
deleting a member from the middle will involve shuffle shiffting of elements
(assuming you are keeping the list sorted to enable a binary search to take
place).
Why not use something like a binary tree: You can then include some extra
code to enable your tree to perform rotations ie res-balck tree. this will
enable your tree to use a binary search method and guarantee O(logN) search
& insert times.
l have only included the code for an ordinary BST tree, to convert it to a
balanced BST tree is not that difficult. You need to see if the data you are
entering is sufficently random order that perhaps a fully balanced tree will
not be warrented as on the average a random input of data will enable a
reasonably balanced tree.
#define FAILURE 0
#define SUCCESS 1
typedef struct bstnode *BSTNodePtr;
typedef struct bstnode{
int key;
BSTNodePtr left, right;
}BSTNode;
typedef struct bstree{
BSTNodePtr root;
unsigned size
)BSTree;
/*inserting an element*/
int insertBST(BSTree *ps, int data)
{
BSTNodePtr current, previous, new;
assert(ps);
previous = NULL;
current = ps->root;
while(current != NULL)
{
previous = current;
if(data < current->key)
current = current->left;
else
current = current->right;
}
new = malloc(sizeof(BSTNode));
if(new == NULL)
{
/*error*/
return(FAILURE);
}
new->key = data;
new->left=new->right=NULL;
(ps->size)++;
if(previous==NULL)
{
ps->root = new;
return(SUCCESS);
}
if(data < previous->key)
previous->left = new;
else
previous->right = new;
return(SUCCESS);
}
Kind Regards
Renato Parletta........
To reply send mail to: [EMAIL PROTECTED]
ICQ No: 13078952
"l can only assume that a "Do Not File" document
is filed in a "Do Not File" file."
Senator Frank Church
Senate Intelligence Subcommittee Hearing, 1975
