Thread: algorithm for this fucntion ?

  1. #1
    Temporal Apparition qubit67's Avatar
    Join Date
    Jan 2007
    Posts
    85

    algorithm for this fucntion ?

    the function list_t *matches(btree_t tree, char *prefix) takes a BST and searches it for phrases that begin with the same prefix, then inserts the phrases that match into a linked list in lexicographical order.

    I am having trouble with an algorithm to this function.
    In pseudo code I have thus far:

    a recursive approach

    compare = strncmp (phrase, prefix, strlen(prefix))

    1. if (compare == o) base case, create linked list of all entries in subtree
    First node of BST found matching prefix, node = root node of subtree
    traverse subtree tree inorder inserting at foot into linked list.
    When subtree == NULL, is processed
    return list;

    2. else
    Traverse main tree to find the first matching (root)node.

    can I use matches to recurse through the base case to build the linked list or am i forced to iterate?

    Is there a better way than the above to do this?

  2. #2
    Temporal Apparition qubit67's Avatar
    Join Date
    Jan 2007
    Posts
    85

    any one?

    I have this so far, but I'm getting a segfault...
    Please help me!
    Code:
    list_t *insert_at_foot (list_t *list, char *value) 
    {
       node_t *new;
    
       assert(list != NULL); 
       new = (node_t *) safe_malloc (sizeof (node_t));
       new->data = value;
       new->next = NULL;
       if (list->foot == NULL) 
       {
          /* this is the first insertion into the list */
          list->head = list->foot = new;
       } 
       else 
       {
          list->foot->next = new;
          list->foot = new;
       }
       return list;
    }
    
    list_t *insert_into_list (bstree_t *sub_tree, list_t *list)
    {
    	if (sub_tree == NULL)
    	{
    		return list;
    	}
    	else
    	{
    		insert_into_list (sub_tree->left, list);
    		list = insert_at_foot (list, sub_tree->phrase);
    		insert_into_list (sub_tree->right, list);
    	}
    }
    
    list_t *matches (bstree_t *index_tree, char *prefix)
    {
    	int len, compare;
       	list_t *list;
       	bstree_t *sub_tree;
       	
       
       	len = strlen (prefix);
       	
       	compare = strncmp (prefix, index_tree->phrase, len);
       
       	if (compare == 0 || len == 0)
    	{
    		list = make_empty_list ();
       		
       		sub_tree = index_tree;
       		
       		list = insert_into_list (sub_tree, list);
       		
       		return list;
       	}
       	else if (compare < 0)
        {
        	matches (index_tree->left, prefix);
        }
        else
        {
            matches (index_tree->right, prefix);
       	}
       	return list;
    }
    
    list_t *make_empty_list (void) 
    {
       list_t *list;
       list = (list_t *) safe_malloc (sizeof (list_t));
       list->head = list->foot = NULL;
       return list;
    }
    what am i doing wrong?

    len == 0 is for when the prefix is zero bytes, the function returns a list of the whole tree.

    I aim to search the BST for the first node of matching prefix.

    this node becomes the new root for a subtree, which i travers in order,
    inserting each data value into the list..

    Is this the right alogorithm?

    insert_into_list
    Last edited by qubit67; 09-21-2007 at 11:35 PM.

  3. #3
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    You're (still) casting your malloc calls.

    You ignore several return results of recursive calls to matches()

    I can't figure out why insert_into_list() calls itself recursively.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  4. #4
    Temporal Apparition qubit67's Avatar
    Join Date
    Jan 2007
    Posts
    85
    The generic functions are from my lecturer and his style was to cast just to make the code easier to understand for noobiez like me, I have removerd them now.

    I dont understand what you mean I ignore several return results from matches?
    I removed the return list at the end of matches and now the compiler is warning: control reaches end of non-void function.

    I made insert_into_list() because I have to traverse the sub_tree BST in order and I thought I needed a recursive funciton. Should I just use an iterative approach? please, your suggestions..

    Code:
    list_t *insert_at_foot (list_t *list, char *value) 
    {
       node_t *new;
    
       assert(list != NULL); 
       new = safe_malloc (sizeof (node_t));
       new->data = value;
       new->next = NULL;
       if (list->foot == NULL) 
       {
          /* this is the first insertion into the list */
          list->head = list->foot = new;
       } 
       else 
       {
          list->foot->next = new;
          list->foot = new;
       }
       return list;
    }
    
    list_t *insert_into_list (bstree_t *sub_tree, list_t *list)
    {
    	if (sub_tree == NULL)
    	{
    		return list;
    	}
    	else
    	{
    		insert_into_list (sub_tree->left, list);
    		list = insert_at_foot (list, sub_tree->phrase);
    		insert_into_list (sub_tree->right, list);
    	}
    }
    
    list_t *matches (bstree_t *index_tree, char *prefix)
    {
    	int len, compare;
       	list_t *list;
       	bstree_t *sub_tree;
       
       	len = strlen (prefix);
       	
       	compare = strncmp (prefix, index_tree->phrase, len);
       
       	if (compare == 0 || len == 0)
    	{
    		list = make_empty_list ();
       		
       		sub_tree = index_tree;
       		
       		list = insert_into_list (sub_tree, list);
       		
       		return list;
       	}
       	else if (compare < 0)
        {
        	matches (index_tree->left, prefix);
        }
        else
        {
            matches (index_tree->right, prefix);
       	}
    }
    
    list_t *make_empty_list (void) 
    {
       list_t *list;
       list = safe_malloc (sizeof (list_t));
       list->head = list->foot = NULL;
       return list;
    }

  5. #5
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    I dont understand what you mean I ignore several return results from matches?
    The calls in red execute matches() but then discard the value that matches() returns.

    Code:
    list_t *matches (bstree_t *index_tree, char *prefix)
    {
    	int len, compare;
       	list_t *list;
       	bstree_t *sub_tree;
       
       	len = strlen (prefix);
       	
       	compare = strncmp (prefix, index_tree->phrase, len);
       
       	if (compare == 0 || len == 0)
    	{
    		list = make_empty_list ();
       		
       		sub_tree = index_tree;
       		
       		list = insert_into_list (sub_tree, list);
       		
       		return list;
       	}
       	else if (compare < 0)
        {
        	matches (index_tree->left, prefix);
        }
        else
        {
            matches (index_tree->right, prefix);
       	}
    }
    Not to mention that you don't always return a value from several of your functions, including matches() and insert_into_list().
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  6. #6
    Temporal Apparition qubit67's Avatar
    Join Date
    Jan 2007
    Posts
    85
    thanks for the suggestions. I have re-written the function and it is a semi working function :
    Code:
    list_t *insert_into_list (list_t *list, bstree_t *sub_tree)
    {
    	if (sub_tree == NULL)
    	{
    		return list;
    	}
    	else
    	{
    		insert_into_list (list, sub_tree->left);
    		list = insert_at_foot (list, sub_tree->phrase);
    		insert_into_list (list, sub_tree->right);
    	}
    
    list_t *matches (bstree_t *index_tree, char *prefix)
    {
    	int len, compare;
    	bstree_t *sub_tree;
    	list_t *list;
    	list = make_empty_list ();
    	
    	len = strlen (prefix);
    	
    	if (sub_tree == NULL)
    	{
    		return list;
    	}
    	else
    	{
    		compare = strncmp (prefix, index_tree->phrase, len);
    		if (compare == 0)
    		{
    			sub_tree = index_tree;
    			list = insert_into_list (list, sub_tree);
    		}
    		else if (compare < 0)
    		{
    			matches (index_tree->left, prefix);
    		}
    		else
    		{
    			matches (index_tree->right, prefix);
    		}
    	}
    }
    from the index file :
    VAT;def19821
    xae;def20672
    garchiver;def8868
    modlogan;def13048
    neqn;def13695
    ISEE;def10826
    printfilters-ppd;def15639
    kdelibs;def11254
    .RAO;def2306
    ESAXC;def7989
    netn;def39400
    neps;def39059

    when I run my search for phrases beginning with "ne", I recieve :

    neps
    neqn
    netn
    printfilters-ppd

    this is kind of what I am looking to do. I dont understand why printfilters-ppd is in the output.

    I developed this function from the code :
    Code:
    list_t *matches (bstree_t *index_tree, char *prefix)
    {
    	int len, compare;
    	bstree_t *sub_tree;
    	list_t *list;
    	list = make_empty_list ();
    	
    	len = strlen (prefix);
    	
    	if (index_tree == NULL)
    	{
    		return list;
    	}
    	else
    	{
    		compare = strncmp (prefix, index_tree->phrase, len);
    		if (compare == 0)
    		{
    		                 list = insert_at_foot (list, index_tree->phrase);
    		}
    		else if (compare < 0)
    		{
    			matches (index_tree->left, prefix);
    		}
    		else
    		{
    			matches (index_tree->right, prefix);
    		}
    	}
    }
    The last function would return a list with the single entry of "neqn", which is the root if the subtree I want to insert in order into the list.

    Clearly and simply, what am i doing wrong?, how do I write this function? Is it ok to have a recursion function embedded in another recursion function.

    Can anyone see a better way to do this?

  7. #7
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Well the recursive calls don't return a list.

    How is the ultimate caller of this function ever going to find out all the stuff this function found in it's search?

    Code:
    list_t *matches (bstree_t *index_tree, char *prefix)
    {
    	int len, compare;
    	bstree_t *sub_tree;
    	list_t *list;
    	list = make_empty_list ();
    	
    	len = strlen (prefix);
    	
    	if (index_tree == NULL)
    	{
    		return list;
    	}
    	else
    	{
    		compare = strncmp (prefix, index_tree->phrase, len);
    		if (compare == 0)
    		{
    			list = insert_at_foot (list, index_tree->phrase);
    		}
    		else if (compare < 0)
    		{
    			sublist = matches (index_tree->left, prefix);
    			// now append sublist to list
    		}
    		else
    		{
    			matches (index_tree->right, prefix);
    			// dittos here
    		}
    	}
    	return list;
    }
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  8. #8
    Temporal Apparition qubit67's Avatar
    Join Date
    Jan 2007
    Posts
    85
    how to append sublist to list?
    thanks Salem

  9. #9
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Oh come on...
    Spend more than 15 minutes thinking about it.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  10. #10
    Temporal Apparition qubit67's Avatar
    Join Date
    Jan 2007
    Posts
    85
    I dont have a variable called sublist, I guess I need to create a new list_t pointer called sublist,

    sublist = make_empty_list ();

    to append list to sublist:

    list->foot->next = sublist->head

  11. #11
    Temporal Apparition qubit67's Avatar
    Join Date
    Jan 2007
    Posts
    85
    I dont think I understand what you mean by append. If you mean at the end, I would have to make a new list called sublist and dereference the right pointers to their coeerct positions:

    list->foot->next = sublist->head;
    list->foot = sublist->head;

    I changed few things and this seems to work, but looks really clunky and confusing to me:
    Code:
    list_t *matches (bstree_t *index_tree, char *prefix)
    {
    	int len, compare;
    	list_t *list, *sublist;
    	list = make_empty_list ();
    	
    	len = strlen (prefix);
    	
    	if (index_tree == NULL)
    	{
    		return list;
    	}
    	else
    	{
    		compare = strncmp (prefix, index_tree->phrase, len);
    		if (compare == 0)
    		{
    			list = insert_into_list (list, index_tree, prefix);
    		}
    		else if (compare < 0)
    		{
    			sublist = matches (index_tree->left, prefix);
    			list = sublist;
    		}
    		else
    		{
    			sublist = matches (index_tree->right, prefix);
    			list = sublist;
    		}
    	}
    	return list;
    }
    
    list_t *insert_into_list (list_t *list, bstree_t *tree, char *prefix)
    {
    	int len, compare;
    	len = strlen (prefix);
    	
    	if (tree == NULL)
    	{
    		return list;
    	}
    	else
    	{
    		insert_into_list (list, tree->left,prefix);
    		if ((compare = strncmp (prefix, tree->phrase, len)) == 0)
    		{
    		             list = insert_at_foot (list, tree->phrase);
    		}
    		insert_into_list (list, tree->right, prefix);
    	}
    }

  12. #12
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Perhaps if you could illustrate an example of a tree, and given a prefix, what result you expect from it.

    I'm puzzled why both functions recurse through the tree.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  13. #13
    Temporal Apparition qubit67's Avatar
    Join Date
    Jan 2007
    Posts
    85
    For example :
    Code:
    Enter phrases to input to the tree: 
    
    alpha
    beta
    cappa
    nequ
    neqi
    neqd
    neqx
    neqp
    neqy
    neqb
    neqc
    neql
    neqt
    peqy
    petq
    
    Enter a prefix to find all phrases in the tree that start with it : ne
    
    neqb
    neqc
    neqd
    neqi
    neql
    neqp
    neqt
    nequ
    neqx
    neqy
    
                                                            petq
                                                    peqy
                                            neqy
                                    neqx
                            nequ
                                                    neqt
                                            neqp
                                                    neql
                                    neqi
                                            neqd
                                                            neqc
                                                    neqb
                    cappa
            beta
    alpha
    The first recursion takes place to find the first node matching the prefix "ne", this I consider as the root of a new tree, a tree containing mostly phrases that match the prefix.

    The second recursion is an inorder traversal of the subtree to insert the phrases that match the prefix into a list

    The idea behind the algorithm is to isolate the part of the entire tree containing phrases with the same prefix, and then move inorder through the sub_tree inserting only the matches into a list.

    The only time matches needs to return a value is when the list has been filled with phrases that have the smae prefix from the sub_tree

    The base case for recursion is when I search and find the first node in the tree with a similar prefix. This as far as I see is the root of a subtree with phrases of similar prefix.

    I then move to recurse though the subtree inserting only the phrases that match the prefix into the list.
    The insert into list function returns the complete list, the matches function then returns the list to the caller.

    Code:
    list_t *matches (bstree_t *index_tree, char *prefix)
    {
    	int len, compare;
    	bstree_t *sub_tree;
    	list_t *list, *sublist;
    	
    	list = make_empty_list ();
    	
    	len = strlen (prefix);
    	
    	if (index_tree == NULL)
    	{
    		return list;
    	}
    	else
    	{
    		compare = strncmp (prefix, index_tree->phrase, len);
    		if (compare == 0)
    		{
    			sub_tree = index_tree;
    			list = insert_into_list (list, sub_tree, prefix);
    			return list;
    		}
    		else if (compare < 0)
    		{
    			sublist = matches (index_tree->left, prefix);
    			list = sublist;
    		}
    		else
    		{
    			sublist = matches (index_tree->right, prefix);
    			list = sublist;
    		}
    	}
    	return list;
    }
    
    
    list_t *insert_into_list (list_t *list, bstree_t *tree, char *prefix)
    {
    	int len, compare;
    	len = strlen (prefix);
    	
    	if (tree == NULL)
    	{
    		return list;
    	}
    	else
    	{
    		insert_into_list (list, tree->left,prefix);
    		if ((compare = strncmp (prefix, tree->phrase, len)) == 0)
    		{
    			list = insert_at_foot (list, tree->phrase);
    		}
    		insert_into_list (list, tree->right, prefix);
    	}
    	return list;
    }
    Make sense, or sensless?

  14. #14
    Temporal Apparition qubit67's Avatar
    Join Date
    Jan 2007
    Posts
    85
    hello?

  15. #15
    Technical Lead QuantumPete's Avatar
    Join Date
    Aug 2007
    Location
    London, UK
    Posts
    894
    Don't bump threads.
    "No-one else has reported this problem, you're either crazy or a liar" - Dogbert Technical Support
    "Have you tried turning it off and on again?" - The IT Crowd

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Implement of a Fast Time Series Evaluation Algorithm
    By BiGreat in forum C Programming
    Replies: 7
    Last Post: 12-04-2007, 02:30 AM
  2. Replies: 4
    Last Post: 12-10-2006, 07:08 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM