Wednesday, May 25, 2011

CS ADTs and fun fun fun!

Of utmost importance to a C/C++ programmer are (you guessed it) pointers!  Pointers enable programmers to create interesting (and useful) data structures that are likely more commonplace in performance applications.

A list of data structures is available on Wikipedia, http://en.wikipedia.org/wiki/List_of_data_structures  for now this post will is concerned with the abstract data types.

To name a few, there exists the stack, queue, deque, list, vector, set, map, and tree.

Perhaps the simplest, can be the "list", aka the "Linked List."

Typically the linked list will feature a node type commonly represented by a structure, in which each structure contains a pointer to the next (and in the case of a doubly linked list, the previous).

http://en.wikipedia.org/wiki/Linked_list

For reference a simple node type can be in C++ as follows:


[code]
template<class NodeData>
struct Node
{
NodeData data;
Node *next;
Node() : next(nullptr) {}
};
[/code]

When creating the linked list, the first node is created with it's "next" member pointing to nothing.  Appending a node to the end will cause the first node's next pointer to point to the second node.

With this structure, one may only have a pointer to the first node and be able to access the entire list's content by "traversing" the list.

Diagram of a linked list:
[Node] -> [Node] -> [Node] -> NULL

to traverse the list is pretty simple,
Node *current = firstNode;
while( current->next != NULL )
{
current = current->next;
}
the loop ends with current pointing to the last node in the list, commonly one will see traversing the list in this manner in the destructor or a clear() member function of the class.

For now, the implementation of many of these Computer Science data structures is left to you, there is a whole "list" of them.

43 comments:

  1. Interesting stuff. I gave up on C++ too soon - never got my head around pointers (but then, I didn't try very hard). All about the C# nowadays (yes, I am a trained monkey :D)

    ReplyDelete
  2. Never really looked into c++ much, done a lot more web based stuff. This is very interesting though, thanks

    ReplyDelete
  3. @Oivvad,

    Interesting, do you think you could hook me up with an internship? I'm a college student off for the summer. I have an associate's degree.

    ReplyDelete
  4. interesting post and blog ^^

    ReplyDelete
  5. I'm really excited to start reading your blog. I'm a game developer so things like this are always useful.

    ReplyDelete
  6. very useful to someone who is just starting to learn coding

    ReplyDelete
  7. Great tips.
    Can you post some documents on Perl? I really love to learn it.

    ReplyDelete
  8. Starting pointers soon, this should help

    ReplyDelete
  9. Like the monospace font, easier to read for programmers eh?

    ReplyDelete
  10. I've never programmed, but plan to begin learning Java this week.

    ReplyDelete
  11. You know how on the first line you say "you guessed it".... I didnt guess it

    ReplyDelete
  12. Great explanation. Can't wait to learn more from you.

    ReplyDelete
  13. Great! Easily explained, thank you for sharing, take care! :) Following also.

    ReplyDelete
  14. i'm no programmer so idk if this is a good example or not but i did write java and that made my head hurt so i applaud you for doing this

    ReplyDelete
  15. I'm not sure how much I actually understood. It's not you, it's me.

    ReplyDelete
  16. @Fermium Death,

    I'm not really the Perl go-to guy, but there are plenty of Perl docs: http://perldoc.perl.org/perlintro.html

    I think a quick intro could be done though. ;)

    ReplyDelete
  17. Great post, thanks mate, keep going :)

    ReplyDelete
  18. bahaha nice rebecca black reference

    ReplyDelete
  19. I always forget how important pointers are

    ReplyDelete
  20. could you separate different parts of code by fonts colors ?

    ReplyDelete
  21. Thanks for the help. Might try it out tomorrow.

    ReplyDelete
  22. Lovely! I just got back into coding and to say the least I'm a bit rusty, you're blog is sure to help.

    ReplyDelete
  23. This is my place to be. you will be seeing me again!!!!

    ReplyDelete
  24. Hey. A question for you, since you seem to be an expert - could you tell me what books do I need to reak to transition into programming in C? A long time ago I used to do some Visual Basic programming, and then I got into web development (php, javascript, etc...). I'm looking for a book that's not gonna assume that I have any knowledge about C, but at the same time won't have whole chapters devoted to explaining what's a loop.

    ReplyDelete
  25. @Zoidberg,

    well... I didn't really learn C first, I learned C++ and then C from web resources and experience.

    The book that was most helpful for me, which taught the basics was by Ivor Horton. It was named "Beginning Visual C++ 6.0". Since then he has written many more books, I think the latest is "Beginning Visual C++ 2010". His latest edition covers C++ as well as C++/CLI and is geared toward users of Visual Studio 2010 (either express or Pro.)

    I have also read "Programming and Problem solving with C++" by Nell Dale and Chip Weems.

    You shouldn't really be restricted to learning from a paper book though, web resources are paramount to learning to program.

    If you're using Windows you can get a good compiler here:
    Visual Studio 2010 Express (free to all)
    http://www.microsoft.com/express/Downloads/

    Also, "learning" a language is kind of an off idea, imo very few know everything about a programming language.

    ReplyDelete
  26. Oh, and C++ compilers also compile C. You might also want to check out C#, it's kind of butter-knifey but still pretty useful.

    ReplyDelete
  27. Hmmm I used to try and "program" whatever you want to call what I did. But I gave up :(

    ReplyDelete