A good C library implementing common data structures (lists, trees, hash tables, etc) is GLib:

http://library.gnome.org/devel/glib/

It does many other things, provides abstractions for threads, files, etc. It is a general-purpose utility library originally written for GTK+. I never really understood why GLib is not more often used.