I'm not sure why you are having probs. I've installed Mandrake on 3 different machines with no prob. I'm not near one now, sorry.
gcc is on disk 1 of your Mandrake install cd's. I just looked at mine. That is Mandrake 10.0 official.
Here you can get all of the .rpms for mandrake that you could ever use.
Are you using an old machine with limited HD space? Installing everything on the Mandrake distro only takes up about 3 GB or so.
Let me give you some more links that might help.
I think that I installed the C development enviroment and got all the tools needed for writing and compiling C.