Problem with structures, where to put them and how to reference them in headers?

Question

OK, I'm in a dilemma right now, and neither my knowledge of C (which isn't the biggest one anyways) nor the almighty Google seem to be able to help me with this:

I have some structures for a game prototype:

• Map (Uhhm... the Map..)
• Chara (A base for Enemies the Players)
• Player (The Player)

Now the problem is: Map needs a reference to the Player that's on it, Player is being constructed giving it a Map and a Chara, and Chara needs the Map too.

If I declare the structs in the header files and wrap them with #ifndef I run into a cyclic dependency loop when I include headers from within other headers.

When I declare the structs in the .c files, I use extern struct Map map etc. but then I run into problem like invalid use of incomplete declaration or forward declaration of struct XXX.

It's 4 o'clock in the morning here and I would like to spend my time more on rewriting the engine stuff (which already exists both in Python AND JavaScript...yes I've got too much time!) rather then trying every feasible combination of search terms for the rest of the night.

I'm aware that this might be a REALLY easy thing, but it has 30°C in here, so please have mercy with my C "skills" ^^

EDIT
Since my problem used typedefs and caf's answer didn't include them, I had to fiddle a bit more with it in order to get it all working. So to help the people which might find this answer via a SE I'll add the code below:

map.h

typedef struct _Player Player;

typedef struct _Map {
    ...
    Player *player;
    ...
} Map;

map.c

// include both player.h and chara.h

player.h

typedef struct _Map Map;
typedef struct _Chara Chara;

typedef struct _Player {
    Chara *chara;
    ...
} Player;

Player *player_create(Map *map, int x, int y);

player.c

// include player.h, chara.h and map.h

Answer 1

Make sure your references are pointers rather than actual copies of the objects, and you should be able to forward-declare them just fine.

Answer 2

This works if your structures only contain pointers to the other structures:

map.h

#ifndef _MAP_H
#define _MAP_H

struct player;

struct map {
    struct player *player;
    ...
};

#endif /* _MAP_H */

chara.h

#ifndef _CHARA_H
#define _CHARA_H

struct map;

struct chara {
    struct map *map;
    ...
};

#endif /* _CHARA_H */

player.h

#ifndef _PLAYER_H
#define _PLAYER_H

struct map;
struct chara;

struct player {
    struct map *map;
    struct chara *chara;
    ...
};

#endif /* _PLAYER_H */

If one of your structures contain actual instances of the other structures (including arrays), then that one would need to #include the other header too. Eg if map contains an array of players:

map.h

#ifndef _MAP_H
#define _MAP_H

#include "player.h"

struct map {
    struct player p[10];
    ...
};

#endif /* _MAP_H */

You do have to be careful about circular includes though. If you included map.h in player.h, then you couldn't include player.h in another source file before map.h - so you wouldn't do that.