Writing a Storable file from C does not sound like an easy solution to me. Here are alternate ways to solve this problem. I am assuming throughout that there is some C library you have that provides an interface into this data structure. If it doesn't exist yet, you should be able to build one fairly easily.
From your question I suspect that you're using Storable. Be warned that the direct C solutions will not necessarily play well with Storable if your Perl developers are using that. The solution to that is to build STORABLE_freeze and STORABLE_thaw hooks that serialize and deserialize your C data structures into a string that Storable can use.