Symbol Tables Key-value pair abstraction, Insert a value with specified key, Given a key, search for the corresponding value, Binary search implementation, Linked list implementation, Binary search trees. | 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@ dungct@ 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 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. Quiz 1 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 The memory to store the entries should be allocated dynamically according to the size of the phone book. typedef struct { PhoneEntry * entries; int total; int size; } PhoneBook; API #define INITIAL_SIZE 100 #define INCREMENTAL_SIZE 10 Create a phone book with an initial size PhoneBook createPhoneBook(); Drop a phone book void .
