If you have moved a lot of files and these are spread across a lot of directories, then you got a great deal of work on your hands!
I suggest just adding:
Code:
ErrorDocument 404 /
to your .htaccess. This will direct users to your homepage in case they land on a 404.
Alternatively, you can add
Code:
ErrorDocument 404 /404.html
Create a 404.html with instructions telling users that you restructured your site.
Also, add a google search box (if you have signed up with adsense) to your site to let users search it.