Ask your programming questions

Discussion in 'The Common Room' started by Elf, May 16, 2015.

  1. Elf

    Elf Immortal Staff Member

    Messages:
    105
    Likes Received:
    6
    Location:
    Clark County, WA
    Any programming questions? Ask! Anyone can answer.
     
  2. Krystal

    Krystal NPC

    Messages:
    9
    Likes Received:
    0
    Long story short, im taking a Algorithms in C class. I've taken a C class before so I sorta know my way around coding in C, but its been like 3 years, and it's a bit different than python so i'm a little foggy on some stuff.

    My current thing task is "... to implement the BinaryTree_insert and BinaryTree_delete functions. Note that the version of BinaryTree that you are working with is generalized to support trees containing any data type."

    BinaryTree.ccp: http://pastebin.com/kgnzLUAF
    BinaryTree.h http://pastebin.com/Te3JQXxt
    Str.h http://pastebin.com/5bNKLLQ2

    I think I've managed to get most of it done in a way that works but i'm not sure on two parts.

    Line 129: I know I want to progress down this tree to the left till I catch the first If in insert
    Code:
    BinaryTree_insert(object/*->left ?*/, item); //-> left? 
    I thought about
    Code:
    object->root=object->root->left; BinaryTree_insert(object, item);
    but I'm not sure if this changes object to what I want.


    So for delete (line 155) ; the first step I need to do is find the node I need to delete. There is a function that you give it the item you want to find and it searches the tree for it.
    BinaryTree_lookup calls BinaryTree_lookup_node; which when it finds the value it wants, returns node->data to I assume BinaryTree_lookup. that returns object->root, object->comes_before, item to I assume BinaryTree_delete.
    I guess I could do something like
    Code:
        BinaryTreeNode *rnode;
        SWO_t rcomes_before;
        const void *ritem;
    //then
       rnode, rcomes_before, ritem=BinaryTree_lookup(object, item);
       object->root = rnode;
    
    but I'm not sure any of this will actually do what I expect it to.
     
  3. Elf

    Elf Immortal Staff Member

    Messages:
    105
    Likes Received:
    6
    Location:
    Clark County, WA
    Binary trees are trees where each node has up to two child nodes. There are a variety of binary tree arrangements; based on your BinaryTree_lookup(const BinaryTree*, const void *) function it looks like your binary tree is implemented as an unbalanced sorted set (a data item can be present only once in the entire tree), with data less than the current node on the 'left' branch and data more than the current node on the 'right' branch. If the data is equal to that of the current node, it can only be present at the current node, thus the "set" property.

    Inserting data
    For a binary tree like this, inserting data is as follows:
    1. Start with a pointer to the 'current node' at the root of the tree, and a double pointer to the 'previous branch' to the address of the tree root pointer.
    2. At the current node:
      1. If the current node is NULL (non-existent):
        1. Create a new node containing the data to be inserted.
        2. Set pointer at the previous branch to point to the node created.
        3. Stop.
      2. Otherwise if the current node does exist:
        1. If the data to be inserted is equal to the data at the current node, stop. The data is already in the tree.
        2. If the data to be inserted is less than the value of the current node:
          1. Set the current node pointer to the left branch.
          2. Set the previous branch pointer to the address of the left branch pointer.
          3. Start over from #2 ("At the current node: [...]").
        3. If the data to be inserted is greater than the value of the current node:
          1. Set the current node pointer to the right branch.
          2. Set the previous branch pointer to the address of the right branch pointer.
          3. Start over from #2 ("At the current node [...]").
    Removing data
    Deleting data from the tree is a bit more troublesome as parts of the tree will potentially need to be reconstructed. Whenever you remove a node from the tree, its children need to remain in the tree, but it may have up to two child branches. Theoretically:
    1. If there are no child branches, the node can just be removed.
    2. If there is only one child branch, the node can be removed and replaced with the child branch.
    3. If there are two child branches, the node can be removed but you will have to do something else to retain the contents of the two child branches.
    What "something else" (in case #3) is, is up to you and how efficient or balanced you want your tree and code to be.

    Here is a simple method of removing data from the tree. There are lots of alternative ways to do this that could result in a more balanced tree, but perhaps this can start you thinking about it:
    1. Start with a pointer to the 'current node' at the root of the tree, and a double pointer to the 'previous branch' to the address of the tree root pointer.
    2. Locate the node to be removed:
      1. At the current node:
        1. If the current node is NULL (does not exist), then stop. The data you are looking for is not in the tree.
        2. If the the data to be removed is equal to the current node's data, then you have located the node to be removed.
        3. If the data to be removed is less than the current node's data, follow the left branch:
          1. Set your current node pointer to the node at the left branch.
          2. Set your previous branch pointer to the address of the left branch pointer.
        4. If the data to be removed is greater than the current node's data, follow the right branch:
          1. Set your current node pointer to the node at the right branch.
          2. Set your previous branch pointer to the address of the right branch pointer.
    3. If there are no child branches, set the pointer at the previous branch to NULL and destroy the current node. Stop.
    4. If there is one child branch (left is NULL or right is NULL but not both), set the pointer at the previous branch to the one existing (non-NULL) branch, and destroy the current node. Stop.
    5. If there are two child branches:
      1. Keep the left branch around as a new 'orphan branch' pointer.
      2. Set the previous branch pointer to the right branch node.
      3. Destroy the current node.
      4. Set the current node to the right branch and set the pointer at the previous branch to the address of the right branch node.
      5. Grab the data at the orphaned branch's top node ('orphan data').
      6. Locate a place to attach the orphaned branch:
        1. If the current node is NULL, then we have found a place to attach the orphaned branch. Set the pointer at the previous branch to the orphaned branch. Stop.
        2. If the orphan data is equal to the data at the current node, something is wrong with the tree. Stop.
        3. If the orphan data is less than the data at the current node:
          1. Set the current node pointer to the node at the left branch.
          2. Set the previous branch pointer to the address of the left branch pointer.
        4. If the orphan data is greater than the data at the current node:
          1. Set the current node pointer to the node at the right branch.
          2. Set the previous branch pointer to the address of the right branch pointer.
        5. Start over from #5.6 ("Locate a place to insert [...]").
    In the third case, rather than replacing the removed node with the left branch and finding a place to graft the right branch, one could also just remove the node and then run all the data in the left and right orphaned branches back through insertion into the tree. This would result in more compact code and a different tree balance, but would usually result in more execution time if the orphaned branches are large.
     
  4. Bemoliph

    Bemoliph High Priest Staff Member

    Messages:
    35
    Likes Received:
    14
    Let's back up a second and steal a picture from Wikipedia for context.

    [​IMG]

    So you're trying to implement some functions of a binary tree, presumably a binary search tree based on your existing less-than/greater-than logic. This means we have a tree where each node contains some value and up to two children, with the "left" child node containing a lesser value and the "right" child node containing a greater value.

    Your instructor's code provides you with two distinct structures representing the nodes (holds data and points to child nodes) and the overall tree (tracks node count and points to root node). You'll want to keep these two types straight so things work out ok.
    Code:
    struct BinaryTreeNode {
        const void *data;
        struct BinaryTreeNode *left;
        struct BinaryTreeNode *right;
    };
    
    [...]
    
    typedef struct {
        struct BinaryTreeNode *root;
        size_t count;
        SWO_t  comes_before;
    } BinaryTree;

    Now back to your own code, starting with BinaryTree_insert():
    Code:
    void BinaryTree_insert(BinaryTree *object, const void *item) {
        if (object->root == NULL) { //Tree is empty, put it here. | Or free spot on nested tree.
            object->root->data = item;
            object->root->left = NULL;
            object->root->right = NULL;
        }
        else { //find where to put this
            //item value less than node: fork left
            if (item < object->root->data ) {
                BinaryTree_insert(object/*->left ?*/, item); //-> left? but how
            }
            //if its more: fork right
            else if (item > object->root->data) {
                BinaryTree_insert(object/*->right ?*/, item); //-> right? but how
            }
            else { //incase of falcon
                //If code gets here then object==data
                // we dont actually need this but if we decide we want dupes later its here
                printf("duplicate: %s\n",item);
            }
        }
    }
    You seem to have the right idea, but you're trying to do some "impossible" things and generally mixing up your types. For example, you establish that object->root == NULL but immediately assign values to attributes of object->root despite it still being NULL. In your recursive calls to BinaryTree_insert(), you pass object->left/right even though object is a BinaryTree with no left or right attributes, and they'd be of type BinaryTreeNode instead of the BinaryTree expected by void BinaryTree_insert(BinaryTree *object, const void *item) anyway.

    So what can you do?

    The NULL thing is easy to fix - just assign a new BinaryTreeNode to object->root before trying to store data in it.

    Doing insertions involving children is a little more complicated. Using recursive calls and comparing the actual value of the node with item is a good way to go, but we need to ensure we go deeper than just the root node. Since you only have one BinaryTree that only points to the root node, BinaryTree_insert() only takes a BinaryTree and is geared more towards starting from root, and you want to work with the child nodes anyway (of type BinaryTreeNode), you should do the recursion with a separate function that accepts a BinaryTreeNode. Don't forget to increment the node count in the BinaryTree!

    Moving on to BinaryTree_delete(), try applying some of the same logic. Are there places where the types don't make sense? Are you hard coding relative to the root node, cutting yourself off from the rest of the tree? Do the children of deleted items get lost, or are you keeping them in check?
     
  5. Krystal

    Krystal NPC

    Messages:
    9
    Likes Received:
    0
    Thanks for the help. I'm gonna work on this more and give an update later.

    Edit: Yep, I got it now.
     
    Last edited: Oct 30, 2015
  6. Krystal

    Krystal NPC

    Messages:
    9
    Likes Received:
    0
    what i'm working on now is: you give the program strings, it hashes to something and puts it into a array.
    if say two items hash to the same thing, keep going down to the next slot until its free or hits the end of the array and loops back.
    HashTableOpen.cpp: http://pastebin.com/eUmCt0Ms HashTableOpen.h http://pastebin.com/TduVmxXm main http://pastebin.com/nMmZUNUz
    now im getting
    Code:
     (debug mess start)
    HashtableOpen created sucessfully.
    a 1 h: 1
    hi 2 h: 2
    tee 3 h: 3
    test 4 h: 4
    same 4 h: 4
    elephant 8 h: 8
    (debug mess end)
    array[0]:
    array[1]: ☺
    array[2]: ☻
    array[3]: ♥
    array[4]: ♦
    array[5]:
    array[6]:
    array[7]:
    array[8]:
    ...
    
    I mean for this assignment it doesn't matter what it hashes to, so ☺ or 1 would be fine but it should at least look like below and I have no clue what I broke.
    Code:
     (debug mess start)
    HashtableOpen created successfully.
    a 1 h: 1
    hi 2 h: 2
    tee 3 h: 3
    test 4 h: 4
    same 4 h: 4
    elephant 8 h: 8
    (debug mess end)
    array[0]:
    array[1]: ☺
    array[2]: ☻
    array[3]: ♥
    array[4]: ♦
    array[5]: ♦
    array[6]:
    array[7]:
    array[8]: (whatever 8is )
    ...
    
     
    Last edited: Nov 14, 2015
  7. Elf

    Elf Immortal Staff Member

    Messages:
    105
    Likes Received:
    6
    Location:
    Clark County, WA
    Hello again!

    This is certainly something we can help out with; implementing a hash table is generally not very complex. However I am not sure what you need help with. Can you restate what you are trying to achieve and what problems you are encountering?
     
  8. Krystal

    Krystal NPC

    Messages:
    9
    Likes Received:
    0
    Sort of a problem is even though the hash for hi is reported as 2. It show up in the array as ☻. But I guess since every two letter word comes out as☻it is technically fine. (either way I would be interested in knowing why this is happening)

    The real problem is it doesn't finish running building the array in main; stopping after array[4]:. I just finished going over it again and I saw
    Code:
    if (!HashtableOpen[0].empty()) { 
    0 is supposed to be h.
    This causes it to crash. The crash was
    Code:
     printf("Notify: new slot is %s", nslot);
    in findslot() instead of %i. Guess it actually wants the types to match.
    It still won't process anything over 8 letters but I bet its something simple like the last thing.


    basically the output i'm trying to get (using the temp insert items in main) is
    upload_2015-11-13_18-49-54.png
    I would rather it print out digits than symbols but either would be acceptable for this specific program.

    --Edit found the cause of the crash in findslot()
     
    Last edited: Nov 14, 2015
  9. Elf

    Elf Immortal Staff Member

    Messages:
    105
    Likes Received:
    6
    Location:
    Clark County, WA
    You are likely seeing a happy face character (and others) because you are trying to print the character value of an integer. What you are seeing is the character representation of the 8-bit number 1 (white happy face) and 2 (black happy face), in DOS code page 437. If you want to print an integer as its textual representation, you should use a formatted printing call to convert the number to a string (e.g. printf("%d [...]", number)).

    But rather than showing the output and code, it would be good to leave that behind for a minute and (without referencing the code or output text) just state in general terms what you are trying to achieve with your program and what isn't going the way you expected. Just showing the code and output will make us reverse engineer the problem statement and we may misinterpret what you are trying to do.
     
  10. Krystal

    Krystal NPC

    Messages:
    9
    Likes Received:
    0
    ah ok.

    no requirement or function was given for the hash but the professor says "suppose they hash to single digit numbers" using the next open address on collisions.
    1. construct makes a empty table
    2. a word goes into the program
    3. insert: some hash stuff happens (I decided to go with it being the length)
      1. If nothing else has hashed to this yet it goes into that slot(bucket) (ex a[3]=3)
      2. If something is already hashed to it, it moves down one till it finds an empty one (ex a[4]=3)
      3. If it reaches the end of the array without finding one it loops back to the beginning.
      4. If it still can't find a slot by the time it comes back around to what it would originally be, (ex 3) it Returns FALSE and gives up
      5. if it manages to find a spot it Returns TRUE
    4. The array prints out.
    5. Lookup finds hashes that match the hatch of the item you want to find and returns those locations.
    6. Destroy: destroys the whole table.
     
  11. Elf

    Elf Immortal Staff Member

    Messages:
    105
    Likes Received:
    6
    Location:
    Clark County, WA
    Thanks! Also let us know what is not working as expected for you.

    However, based on what you have said, some advice:
    1. Hashing based on length is certainly a type of hash you can implement. However, the general "simple hash" is often to iterate over all the characters in a string and add them up, then to wrap the number to the maximum hash value (number of buckets). For example, with a null terminated string s:
      Code:
      int hash(char *s, int buckets){
        int sum = 0;
        for(;*s; ++s)
          sum += (int)*s;
        return(sum % buckets);
      }
      The process being to iterate over each character, accumulating as you go, and then using the modulus function (%) to restrict the result to the number of buckets you have available in your hash table.

      It is a cheap and not very good hash, but depending on your dataset it will likely result in better distribution than using the length of the string.
    2. Generally speaking, a hash table doesn't skip rows on collision. This makes lookups an odd exercise, makes insertion non-deterministic (time wise), and will result in your table becoming full.

      A common implementation is to have a table with each row being a linked list. When there is a collision, the list is simply expanded by adding the new value. Lookups consist of navigating to the row that corresponds to the hash value, and then iterating over the list at that row. There are other schemes as well.
    3. If you still want to stick with the table implementation as you have described, iterating over the table should be easy. The logic being:
      1. Start with an index (i) set to your hash value (h).
      2. Test the table (t) at that location (t) to see if it is empty.
        1. If it is empty, insert the data there.
        2. If it is not empty, increment i and modulus it against the number of rows in the table (sz), e.g. i = (i + 1) % sz. This will make sure that it wraps around to the beginning of the table if you try to go past the end.
      3. If i equals h then you are back to where you started. You can stop trying; the table is full.
      4. Go back to (3.2 -- "Test the table [...]") to retry the insert.
    4. In this crazy table scheme that was cooked up, assuming you still want to use it, if you want to retrieve the data by hash value, you will need to store the hash value alongside your data. You will also essentially have to query the entire table to find the data, as there is no guarantee that it will be at the row corresponding to the hash value, depending on what was inserted before it. You can try to eke some optimization out of it using the following logic:
      1. Start with an index (i) set to your hash value (h).
      2. If the data at row i has a stored hash value of h, then add that data to a set of data to be returned (you could use a linked list).
      3. If the table is empty at row i, you have found everything that could possibly correspond to your hash value, so you can return your accumulated data set.
      4. Increment i and start the test over again at (4.2 -- "If the data at row [...]").
     
  12. Krystal

    Krystal NPC

    Messages:
    9
    Likes Received:
    0
    That helped and now everything is working right, thanks Elf.
     
  13. Elf

    Elf Immortal Staff Member

    Messages:
    105
    Likes Received:
    6
    Location:
    Clark County, WA
    Glad I could help!
     
  14. Krystal

    Krystal NPC

    Messages:
    9
    Likes Received:
    0
    Hi again, this time the assignment has to do with graphs and the Bellman-Ford algorithm. The book actually doesn't have this in it but kinda covered it in lecture. Looking at the visualalgo and other references for it, it does a few passes and calculates all the paths from the origin to vertices. If it finds one that is shorter than the one it has previously stored, it updates the predecessor of that vertex. I still feel kinda lost about this whole thing though.
     
    Last edited: Dec 8, 2015
  15. Elf

    Elf Immortal Staff Member

    Messages:
    105
    Likes Received:
    6
    Location:
    Clark County, WA
    Hello @Krystal !

    Let us know what the question is and we would be glad to help.
     
  16. Krystal

    Krystal NPC

    Messages:
    9
    Likes Received:
    0
    I don't really get how graph works in this. I have this but it feels like I am missing something else.
    Code:
     void Graph_add_vertex( Graph *object, int vertex_id )
    {
        object->vertex_count += 1;
        object->vertices[vertex_id];
        //add vertex to graph some how
    }
    so maybe I forgot something but I have no clue how to put the the vertexes also weight into the adjacency_list each vertex has.
    Code:
    void Graph_add_edge( Graph *object, int start_vertex, int end_vertex, double weight )
    {
        //make sure they exist first.
        //Shouldnt break anything if it exists.
        Graph_add_vertex(object, start_vertex);
        Graph_add_vertex(object, end_vertex);
    
        //since they are all bi directional, add both vertexes to each others adjacency list somehow.
     
        object->vertices[start_vertex].adjacency_list; //some other magic here to finish the code
     
        //or maybe this but it has to be a pointer but its not
        object->vertices[start_vertex].adjacency_list->EdgeInfo->vertex_id=end_vertex;
    
        //maybe this
        object->vertices[start_vertex].adjacency_list.count += 1;
            //someother stuff somehow
    
        //then
        //also add the weight somewhere to the edge's info somehow, probably EdgeInfo from AdjacencyList. somehow
    
        //should be done after that.
    }
    
    The last thing i'm really having problems with is bellman_ford. Im pretty sure I get how its supposed to work mechanically but i'm not sure how that kinda works into C code.
    Code:
    int bellman_ford( Graph *object, int start_vertex )
    {
        // Step 1: initialize graph
        for (int i = 0; i < object->vertex_count; ++i) {
            object->vertices[i].distance = DBL_MAX;
            object->vertices[i].predecessor = -1; // -1 is no predecessor
        }
        object->vertices[start_vertex].distance = 0.0;
    
        // Step 2: relax edges repeatedly //44.40
        for (int i = 0; i < object->vertex_count; ++i) {
            //for each edge figure out weight
                //if new weight cost < current weight cost
                    //current weight cost = new weight cost
                    //predecessor = the cheaper vertex from the new weight cost
        }
        // Step 3: check for negative-weight cycles
        //to do later, stop loops going to negative infinity.
    
        return 0;
    }
    
    Full code In case its needed or anything
     
    Last edited: Dec 9, 2015
  17. Elf

    Elf Immortal Staff Member

    Messages:
    105
    Likes Received:
    6
    Location:
    Clark County, WA
    Thanks for posting some more detail. I think @Bemoliph is going to take a first try at this one! : )
     
  18. Krystal

    Krystal NPC

    Messages:
    9
    Likes Received:
    0
    Don't worry about it, I managed to program something that did about what it was supposed to do.
     
  19. Elf

    Elf Immortal Staff Member

    Messages:
    105
    Likes Received:
    6
    Location:
    Clark County, WA
    Ok, good to hear!