Ccleaner is a great program in my opinion. Don't forget to defragment your hardrive. First thing I do is scan for viruses then run ccleaner, Disk cleanup, defrag, chkdsk. I don't know if it matters but that is the way I do things. I third what hamluis and keyboardninja said about backing up your hardrive. In my opinion an external hard drive is vital incase you delete something important.
before anything, you should have uninstalled any unnecesarry programs and/or unused windows components in control panel> add/reemove programs. then you should remove all old restore points if you use windows restore, and only leave the most recent one. then run several virus scanners, as not every scanner catches every virus. malwarebytes catches a lot of infections that standard anti-virus suites may miss, and so does avast.
after these steps, you should run disk cleanup, then check disk and then defrag, in that order. you dont want to defrag before you use check disk to repair errors and bad sectors, and you dont want to do either before you have used disk cleanup to get rid of your temp files, internet cache and such. after all this, running a reg scanner like ccleaner is a good idea. i never use registry cleaners personally, i perfer to go through the registry manually, but thats not something the average user should attempt.
you ALWAYS need to back up your drive before running a registry cleaner, no question about it. if you do not wish to invest in an external hard drive, then its all on you. dont say you have not been warned. there are services like mosy and carbonite which allow you to back up your hard drive to their web server for a monthly fee, but i dont know any sites that provide this service for free- so your best to make a one time investment in an external drive rather than pick up a new monthly bill.
you can also run hijack this to disable unnecesarry start-up items and malware, when you are doing your virus scans. you can use msconfig to remove unnecesarry start-up items, but hijack this does this AND allows you to remove malware all at once, but it takes a lot of work to use it, or the advise of an expert. there are experts that frequent this site, and may be able to help you with hijack this, but ive heard the wait is like 10 days. hijack this scans your computer, and lists EVREY SINGLE running process, and its up to you to google EACH unrecognized item to determine if it is legitimate/needed, or malware/unnecessary, unless you just want to post the log on this site and wait the 10 days for a review of the log.