>Route 13, Route 13, Route 17 (With Dowsing Machine), Route 17 (With Dowsing Machine), Route 18, Route 18 (With Dowsing Machine), Desert Resort, Driftveil City, Cold Storage, Dragonspiral Tower (With Dowsing Machine), Undella Bay (With Dowsing Machine)
There are loads of places where you can find Heart Scales. Try using your Dowsing Machine on Routes.
They can be received by showing a woman in Driftveil City a Pokemon knowing a certain move. You can also find them on Wild Luvdisc (Found by Fishing). Spam Thief or Covet.
Source
