Are you sure you've completely understood the algorithm? If so, it should actually be no big deal to implement it in C++. Maybe you should first start out with Dijkstra's algorithm, since A* is just an extension of it.
The hard part about it is rather how to integrate the algorithm and the associated data structures properly into your game's environment.
