What is the difference between these two structure declarations?

With the first you can use either the type-alias COMPLEX or struct complex.

With the second you have an anonymous structure which can only be used with the type-alias COMPLEX.

With that said, in C++ any structure name is also a type-name and can be used as a type directly:

struct complex { ... };
complex c1;