Designing data structures for an address book in C program?

Question

I want the number of address book items to be variable - not known in advance; I am thinking that using a linked list is the right choice?

"The user can enter new person data, or print the data for a given name, the asking data need not be a name but also an address on a telephone number, the program prints the whole information about a person, print the content of the book in alphabetical order. Store some data in a file; retrieve it and safe it after modification.

Program should write a file to the disk and retrieve the file from it. Program should be called with arguments."

I will use malloc but I don't know when and how.

Is there somebody who did a similar task or has an idea that can help me, please?

Answer 1

For a "toy" program, a linked list is enough. The problem with linked list is that if you have a lot of the records. In the worse case, you will have to search your whole list to find or not a entry. The best approach would be a hash or a combination of hash and tree. You will have to use malloc() for sure if you are using pointers. I recommend that you check the Wikipedia article about linked list implementation. They have even an example in C.

Answer 2

You could use a linked list, or a doubly-linked list, but one of the criteria is that you can present the data in a sorted order. Of course, it is not clear whether that will be alphabetical on surname (family name) or first name (given name), or town, or ...

You might need to use a structure more amenable to sorting than a list, especially if the sort criterion can be different at different times. In general, sorting an arbitrary singly-linked list is really hard is not particularly efficient, but efficiency is probably not relevant here. There are some ways of sorting a doubly-linked list is easier to sort that can be more efficient. You often end up with either an array or some sort of heap or tree structure, as these can be sorted more efficiently.

However, if you have a fixed sort criterion and can put the items in order as you build the list, then a singly-linked list is fine.

You will use malloc() when you create a new entry - possibly several times for each entry.

When you write to disk, you will probably generate a text file (because it is easier to see what needs fixing if the file is all text). You will need to mark the beginning and end of each entry.

Answer 3

After careful consideration, I offer you the following example (note the fact that you can turn the pages and sort the entries, hence my suggestion of a doubly linked list which you mistook as a char[] array ..)

My original answer is below (Yes, I would rather find screen shots of Microsoft Bob than give you the full source code needed to satisfy your homework):

Well, lets think about all of the stuff that is interesting about people:

typedef struct person {
    char *firstname;
    char *lastname;
    char *phone;
    struct person *prev;
    struct person *next;
    unsigned fname_hash;
    unsigned lname_hash;
    unsigned full_name_hash;
} person_t;

Note a hash for first, last and full name which is how people commonly search an address book.

Then take a look at a very, very basic hashing algorithm (pulled right out of an ini file parser (basically just a dictionary) that I maintain):

unsigned simple_hash(char *key)
{
 int len;
 unsigned hash;
 int i;

 len = strlen(key);
 for (hash = 0, i = 0; i < len; i++) {
  hash += (unsigned) key[i];
  hash += (hash << 10);
  hash ^= (hash >> 6);
 }
 hash += (hash << 3);
 hash ^= (hash >> 11);
 hash += (hash << 15);
 return hash;
}

The hashing function above is not collision proof. You will still need to compare strings when you think you have a match, just to be sure. However, employing that hash (or another) is the fastest way to search through a linked list. You will be comparing unsigned values, not strings (unless of course the hash matches, then you compare just to check to be sure its not a collision).

When you begin, allocate enough space for n entries in the list (3 - 4 should be fine). After that, you will need to re-allocate for each addition or removal.

Of course, most people would like their address book to appear alphabetically, so inserting and deleting nodes is just half of the battle. You will also want to sort the list. Its very difficult to help you there with what you provided.

What I can say is address books commonly contain company information, so you might encounter "1A Pest Control". In that case, you might want to have a look at a natural language string comparison.

Finally, If this has to work on wide character sets, you need to edit and re-tag your question.

Answer 4

Actually linked list will not stored your data into hard disk. You can utilize FILE to store data. You can look at the http://www.utas.edu.au/infosys/info/documentation/C/CStdLib.html link to get a small reference.