Well it does give you the option to either delete the whole harddisk, or to shrink the windows partition, and create a new partition, and set up dual-boot with windows during the installation. However it does ask you twice if you are sure you want to delete the harddisk.
If you don't get an option to start windows on startup now, you have very likely deleted it all.
You can check once again in linux - go to: Applications - Accessoires - Terminal (or hit alt-f2 and type: gnome-terminal)
In the terminal you enter
It will ask you for the password. You will not get any feedback while you type it, this is normal.
Just copy and paste the code here (strg-c strg-v).
Your computer might have come with a "recovery" cd... That's basically an install cd. I can't believe you didn't get anything. That would mean in case of data loss you have to buy the Operating system again?
Anyway - don't panic. You might still have the registration code, and that's all you need. You can get someone elses XP cd, and use your registration code.
And if all else fails, you're stuck with the better Operating System! :P