bueno
y como quieres comenzar?
que ideas tiens hasta el momento?
¿En C o C++? ¿Manejas algo de punteros o prefieres no usarlos?
Usa estructuras, los datos de un contacto los englobas en una estructura. Luego, puedes crear una lista de estructuras y hacer dinámico el número de estructuras que manejarás (necesitas manejar un poco de punteros y memoria dinámica), o simplemente creas un array de X estructuras y pones a X como el límite de estructuras que puedes manejar (si no manejas la memoria dinámica/punteros es más fácil así, pero es un detallito nadamás).
Bueno, si no conoces esos temas, pues repasa y verás que tendrás una mejor idea de cómo realizar el programa.
Saludos,
José Jorge (Geo).