Interesting question - I hope it's not too late to answer.
When I taught programming at Boston College in the early 80s, my colleagues and I wrestled with these issues every year, and we kept tweaking our approach. C was a new language then, so our progression went through Basic to Pascal. I remember thinking at the time how hard it would be to teach C just because it was more loosey-goosey, there were more ways for students to mess up, and more really confusing things like the distinction between arrays and pointers that you had to teach.
What I found most useful was to try to be concrete, not abstract. For example, in the intro programming course I used an interpreter for a simple decimal computer that you would program in it's decimal "machine language". It had addresses going from 0 to 999, and opcodes like 1234, with the "1" meaning "add to the accumulator", and "234" being the address of where to find the number to add. Students would write really simple programs, like to add up a list of numbers, and they would single-step them, observing what happens at each step.
I would have them play with this for about 3 weeks, and then start into BASIC. In the second course, they would go into Pascal. What that little decimal "computer" accomplished was to convey some concrete concepts that make the "abstractions" in "real" languages a lot easier to understand, such as:
- What memory is, and what addresses are, and how both data and programs are just numbers at addresses in memory. That makes the concept of "variable" and "array" and "pointer" much easier to explain later.
- How the basic model of computation is that very simple steps are performed in sequence, and before each step can begin, the previous one has to finish. I know people will object that computers are highly parallelized and pipelined nowadays, but I have to explain that you need to start really simple, because when newbies see a program run, it looks for all the world like it does everything at once, and reads your mind in the process.
- How, by combining a very small vocabulary of instructions, including jumps and conditional jumps, you can get the computer to do almost anything you want it to.
Now, regarding C, I've heard it disparaged as just a cut above assembly language, but I think that's a good thing. It always struck me as a language by experts for experts. I think the ideas of arrays and pointers and structures are very easy to explain if you can just refer back to the underlying machine. Similarly for C++ and object-oriented programming.
So, to summarize, if students understand the underlying concept of how computers work, even if it's a really artificial computer, then explaining higher-level data structure concepts is a lot easier.