Invalid Node Structure and Not Starting Up

Last night I was using my MacBook (OS X 10.4.11 (I think it's 11, I can't remember for sure, the latest one)) when all the programs that were running froze. I shut down the computer and went to reboot however when it rebooted all the got was the chime and not apple or pinwheel. In the end, I ran the Hardware Test and it came back clean so I went into Disk Utility and checked that, it came back with "Invalid Node Structure" etc so I tried to repair it and that failed.

Now I read this thread and understood most of it except for how actually do a repartition.

I don't have Disk Warrior so that's out, but I don't care about losing files or data or anything, I have an external hard-drive and luckily I actually copied everything that was important onto it a couple hours before this happened while I was cleaning the MacBook out.

So basically my question(s) is/are; how do I do a repartition, why did this happen and is there anything I can do to stop it from happening again?

Thanks.

 

I tried that and now I'm getting this:

"This drive has reported a fatal hardware error to Disk Utility. If the drive has not failed completely, back up as much data as you can and then replace it with a working drive."

I re-ran the Hardware Test and it's still coming back with no problems. I'm at a lose as to what to do, should I reformat or something?