ADT Symbol Tables Key-value pair abstraction. Insert a value with specified key. Given a key, search for the corresponding value. Example: DNS lookup. Insert URL with specified IP address. Given URL, find corresponding IP address anhtt-fit@mail.hut.edu.vn dungct@it-hut.edu.vn http://www.mediafire.com/?n2yzyjnnn10 Example applications Can interchange roles: given IP address find corresponding URL Elementary implementations Binary search implementation: maintaining two parallel arrays of keys and values, keeping them in key-sorted order. It uses binary search for get. Linked list implementation. Both put and get take linear time per operation: to search for a key, we need to traverse its links; to put a key-value pair, we need to search for the given key. Binary search trees. Performance depend on the shape of tree. 1 Implementation Define a structure to store key-value pairs Example: phonebook typedef struct { long number; char name[80] } PhoneEntry; Using array for implementation Key-value pairs are stored in an ordered array Example: #define MAX_PHONE_NUMBER 1000 typedef struct { PhoneEntry entries[MAX_PHONE_NUMBER]; int total; } PhoneBook; The key is phone number and the value is person name API Quiz 1 Add an entry in the phone book void addPhoneNumber(long number, char * name, PhoneBook* book); NB: If the entry exists, the value should be overwritten. Write a program to add and search phone numbers in a phone book using an array for implementation Find an entry in the phone book char * getPhoneNumber(long number, const PhoneBook* book); returns null if the entry does not exist 2 Using dynamic memory API The memory to store the entries should be allocated dynamically according to the size of the phone book. typedef struct { PhoneEn