How do you make diagrams of memory and data structures?

Question

I have to create a short program in C that manipulates strings, but I always run into some weird pointer errors. While K&R is a great reference on the language, and I often look at it when I am puzzled it already assumes you are an adequate programmer.

The lecturer that teaches us programming said that good programmers make nice diagrams on these stuff but I have no idea how to do it. Can you recommend a good book or lectures on this?

Thanks, I will appreciate every answer I get.

Answer 1

Are you asking for tools to help draw diagrams, or what the diagrams should represent? I would recommend just using a piece of paper and pencil for anything that you are doing to try and understand this yourself; you don't need any fancy tools.

If you want to know about how pointers work, and what the diagrams mean, I found this handout after Googling that looks like it might be a decent tutorial.

Answer 2

Good programmers don't make "nice" diagrams - they make scruffy, illegible ones that serve their purposes. Just scribble what you need on any available surface. And don't wory about drawing the "correct" shapes - an ex colleague of mine once said that a diagramming methodology wasn't worth sh*t if you couldn't draw the diagrams on the back of a fag (cigarette for non-UK folks) packet.

Answer 3

You may want to see Gustave Duartes' blog for this. In his posts he often draws diagrams of memory and such. He uses Visio for this and I, for one, find the results pretty neat.

Answer 4

There aren't many tools that will draw the style of memory maps that your professor is referring to.

The idea he is trying to convey is that when you are a beginner developer in C, the use of pointers and arrays confuses the hell out of you. What aims at what? Are these two pointers pointing at the same thing? What cells of the array of string is each index referring to, etc. ?

Experienced programmers have a mental image of this. With experience, so will you. Until then, the idea is that you could physically draw something on a paper to understand those things rather than having it all in your head.

I agree that K&R is not meant as a textbook, and therefore doesn't have those visuals.

You can see an example of these diagrams in slides that I've made for a C tutorial

Answer 5

The typical memory model for C is that memory is a set of boxes; each box is 1 byte wide. Each box has an address in hexadecimal. A pointer is a variable that has an address in it.

Regarding books/lectures, you're looking for a basic computer organization and architecture book.

I've used these 3 books; I order them by "decreasing understandability". The classic is the last one by Patterson and Hennessy, but I find it the least readable. YMMV.

http://www.amazon.com/Introduction-Computing-Systems-gates-beyond/dp/0072467509/ref=sr_1_1?ie=UTF8&s=books&qid=1238345302&sr=1-1

http://www.amazon.com/Digital-Design-Computer-Architecture-Harris/dp/0123704979/ref=sr_1_6?ie=UTF8&s=books&qid=1238345245&sr=1-6

http://www.amazon.com/Computer-Organization-Design-Fourth-Architecture/dp/0123744938/ref=sr_1_3?ie=UTF8&s=books&qid=1238345245&sr=1-3

Answer 6

One of the most useful things I once have done was my application draw the graphs ...

In an application that had a complicated data structure specialized to the job (standard hashtable didn't do in that case ;-) I had my application output a ".dot" script that dot tool of graphviz could parse.

It did this by having a dump routine (okay, method, it was C++) that output the .dot header

 digraph g {

then walked my data structure and then wrote the footer

 }

In the structure walk it wrote every pointer with

 SOURCE -> DESTINATION

where Source was the memory address of the referencing object preprened with O (O213435354) and Destination was the object pointed to in the same format.

At the start of every object it also wrote

SOURCE [ .... ]

with ... being the object data.

Whenever the application was at an "intersting" state I dumped the graph and then used the dot-tool from graphviz to visualize it. I have found a lot of pointer error quite easily that way, the eye is built to see regular structures in lines ...

By the way I still regularily use graphviz as it is quite nice to write & edit graphs with the text editor and let the tool vizualize them afterward. If I need to dress up .dot graphs for a powerpoint-spoiled audience, I load them into OmniGraffle on my mac. (And my PC-using coworkers think I have some diagramming superhero powers because with that combination I produce graphs 10 times faster than them when they use Visio)

Answer 7

Use a block of squared (quadrille rather than graph) paper and a decent pencil* if you want your diagrams to look nice. Also useful for representing memory cells, letters in strings, and so on. You can even get quadrille moleskines, if you want to be hip and square at the same time.

*** I like uni shalaku dx 0.5 as it has the feeder button at the side so you don't have to shift your grip to get more lead.

Answer 8

An easy way is to draw the memory as one huge "ladder". Each box in the ladder represents one adress in memory. In the box you type the data and next to it you type the adress. Something like this:

http://cosketch.com/Saved/pe6sHGD0

Also learn how the debugger works, it can often show you the contents of pointers, variables etc.

Answer 9

I echo the suggestion of drawing them on paper first and then, if you feel the need, you can include an ascii version of them into the code.

I normally use these three formats:

---

to reason about memory:

      +--------+
   0  |        |  <- start
      +--------+
   1  |        |  <- q  scans from start to end
      +--------+
      ~  ..... ~
      +--------+
      |        |  <- end
      +--------+  \
      |        |  |
      +--------+  |__ rest of the
      ~  ..... ~  |   allocated memory
  n   |        |  |
      +--------+ /

---

to reason about strings:

    0               n
   +--+-- --+--+--+--+
   |  | ... |  |  |\0|
   +--+-  --+--+--+--+
     ^        ^__ q moves from the
     |            end to the start
     p moves from
       start to the end

---

to reason about bits in a word:

   xxxx yyzz 00tt 11ss
   \    \ \  \ \  \ \__ storage registry
    \    \ \  \ \  \___ always set to 1
     \    \ \  \ \_____ temp value
      \    \ \  \______ always zeroed 
       \    \ \________ zero flag value
        \    \_________ y register
         \_____________ x address            

---

I used to do something similar for finite state machines too but they tended to be too complex (and time consuming to do) so I now directly embed the graphviz code into a comment. Even not knowing about GraphViz it should be easy to guess how to draw the FSM diagram.

digraph G {
  mode = hier

  LIMBO [style= filled];
    node [shape = ellipse];

    LIMBO   -> HEADER  ;
    HEADER  -> LIMBO;
    HEADER  -> TUNE ;
    TUNE    -> LYRICS ;
    TUNE    -> CHORD [style=dashed ];
    TUNE    -> LIMBO ;
    GRACE   -> TUNE ;
    GRACE   -> CHORD  [style=dashed ] ;
    SYMBOLS -> TUNE ;
    SYMBOLS -> LIMBO ;

    overlap=false
  sep = 1.5
}

---

These cover the vast majority of diagrams I need. For more complex ones I use GraphViz or OpenOffice Draw.

Answer 10

This will only apply to those familiar with the insides of the machine, but a trick I use is to write a "fake" memory address in my diagrams to make it look realistic. What I mean is this:

    .------.
 A  | 3FFC |
    '------'
    .------.
 B  |    7 |
    '------'

Guess which variable has the pointer, and which has the value? Actually, I'll usually write the address under (or over) B's box to show where it is. And then, I'll make up another (very different) fake number to show that A is also located somewhere. This is helpful when you are just starting out. Later, you get used to all this pointer stuff.

Answer 11

the best way to visualize your problem is to debug your code. and focus on your variable. it will not only give you insight view of your code but also enable you to draw exact diagram of the code, which your lecturer said to you.