anonymous
  • anonymous
How do we do huffman coding and decoding in C++? It must implement a binary tree, binary search, scanning of Input stream, generation of Code.
Computer Science
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
chestercat
  • chestercat
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
anonymous
  • anonymous
Good luck with that :-D I can't even implement a binary search correctly :(
anonymous
  • anonymous
Oh :( i guess i will have to find some advanced books to do all that.
anonymous
  • anonymous
There's probably no need for an advanced book; try google :-D

Looking for something else?

Not the answer you are looking for? Search for more explanations.

More answers

anonymous
  • anonymous
Its too complicated, the part i'm not getting is converting those simple data structure algorithms to real time code. I have some idea overall on how this project will finally work, but need to join the pieces together through a bit of copy pasting and some research :P
anonymous
  • anonymous
this is my first project :D
anonymous
  • anonymous
Ah, good ol' Huffman. Once you've got the binary tree internalized, it becomes more clear how to do the rest of it. As for the binary tree, it's all about the data structure. A binary tree by definition means every non-leaf node has two children: N / \ N N / \ N N So that means your data structure for each node needs to contain the node data itself, and then pointers to two child nodes. You can use NULL child pointers to identify a leaf node. The tree itself then actually only needs to contain the root node, from there you can traverse with a recursive function to all other nodes. The trick about this is that it's O(logN) to find a particular piece of data in the tree if you structure it properly. Imagine you've got pointers to objects associated with an integer value between 1-10. The node data in this case should be a range of numbers, and in leaf nodes, a pointer to an object associated with that number. The root node R could contain the range 1-10, and children halve the range of the parent (with a special condition where the number isn't divisible by 2): 0-10 / \ 0-5 6-10 ... / \ 6-8 9-10 / \ / \ 6 7-8 9 10 / \ 7 8 I've only shown one branch from the root node here, but you get the idea. Now imagine you're searching for the pointer to the object associated with the value 7. You start at the root node. 0-10 contains 7, so check both children. The range of the left child 0-5 doesn't contain 7, so stop there. The right child is 6-10, which contains 7, so again check both children. Continue until you've reached the leaf node with the value 7, and you've found your object - in O(logN) time. Searching through an array would have O(N) complexity.
anonymous
  • anonymous
Yeah, as i was telling you, i have been taught only these concepts in the last semester, implementing all that in real time has driven me nuts. I understood Hoffman from this video http://www.youtube.com/watch?v=0PahtaFK640 But i guess first i need to code sorting and searching and implementation of binary tree properly in order to make that project.
anonymous
  • anonymous
To implement this, you'll need a node data structure that contains your data and simply pointers to two child nodes (and in the example case, an integer range and a pointer to the object): class BinaryTreeNode { .... private: Node *m_child1, *m_child2; int m_min, m_max; MyObject *m_pData; }; To traverse, you'll need recursion. You can implement the traversal function into the node class itself. That would look something like this: MyObject * BinaryTreeNode::Traverse(int value) { MyObject *pObj = 0; if(m_min<=value && value<=m_max) { // we have reached a leaf node if both children are 0, so check // if we've found the value we're looking for if(m_pChild1==0 && m_pChild2==0 && m_min==m_max && value==m_min) { pObj = m_pData; } else { // otherwise, traverse down the left side of the tree, and if // we don't find the object there, go down the right side pObj = m_pChild1->Traverse(value); if(!pObj) { pObj = m_pChild1->Traverse(value); } } } return pObj; } Now, this will probably not just work or even compile, but hopefully it helps to illustrate the idea.
anonymous
  • anonymous
You traverse down the tree until you've found the object, and if you've found it, it is passed back up the call chain by returning it, and the initial Traverse() call will return the found object. If it's not found, a null pointer will be passed back up by the successive return statements, so your initial call to Traverse() will return 0.
anonymous
  • anonymous
No matter i will need the whole day to digest that code, but i still understood the working of the tree and how you used the search, let me work the whole code and successfully run a traverse on the binary tree and then tackle the Huffman coding. Btw, the book i was using before for c++ was very theory ish so i have switched to Problem Solving with C++, WALTER SAVITCH.
anonymous
  • anonymous
The problem also is, some of my basic concepts about pointers arent very clear, i still need to get a feel for them.
anonymous
  • anonymous
I haven't read that one. I've got Numerical Recipes In C++, and can highly recommend it. Yeah, you'll have to get pointers down ;) Technically, they're memory addresses. If you allocate an object with new, malloc will be called to allocate a block of memory for that object. The result of that is a memory address, at which the object (the block of memory allocated for it) resides. A pointer is simply a representation of that memory address. By having a pointer to an object (a pointer of type Node, or Node *ptr, for example), you can use the -> operator to access that object. Conceptually, it's like an arrow that points to another object. Follow the arrow with -> and you can access the object it points to ;)
anonymous
  • anonymous
Yeah i have heard that expression "The sign to the restroom is a pointer not the toilet itself" :D And downloading that book right away!
anonymous
  • anonymous
btw isnt it around 3am at yours O.o?
anonymous
  • anonymous
Yeah, it is. I'm debugging an oriented box intersection routine and can't let go until it works. What can I say, I'm a nerd :P
anonymous
  • anonymous
It's a bit cumbersome code - using the Separating Axis Theorem to find out if two oriented boxes are intersecting or not ;) I'm getting a 404 for that link. What is it?
anonymous
  • anonymous
Oh ok, Its an e-book library, but that strange, its working for me.
anonymous
  • anonymous
they may not allow access from the US ;)
anonymous
  • anonymous
shall i delete its link? people who own this site might get into trouble lol
anonymous
  • anonymous
that's quite a collection for most books these days i try to get them on iPad to make them accessible everywhere ;)
anonymous
  • anonymous
yeah, probably a good idea
anonymous
  • anonymous
Yeah, but pdf to epub is sometimes messy for me, so i just read them on the laptop.
anonymous
  • anonymous
OK, I'm off to bed - night!
anonymous
  • anonymous
Good Night! And Thanks a lot!

Looking for something else?

Not the answer you are looking for? Search for more explanations.