ADT
Key-value pair abstraction.
Insert a value with specified key.
Given a key, search for the corresponding value.
Symbol Tables
Example: DNS lookup.
Insert URL with specified IP address.
Given URL, find corresponding IP address
anhtt-fit@[Link]
dungct@[Link]
Can interchange roles: given IP address find corresponding URL
[Link]
Example applications 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
[Link] [Link]
Implementation Using array for implementation
Define a structure to store key-value pairs Key-value pairs are stored in an ordered array
Example: phonebook Example:
typedef struct { #define MAX_PHONE_NUMBER 1000
long number; typedef struct {
char name[80] PhoneEntry entries[MAX_PHONE_NUMBER];
} PhoneEntry; int total;
} PhoneBook;
The key is phone number and the value is
person name
API Quiz 1
Add an entry in the phone book Write a program to add and search phone
void addPhoneNumber(long number, char * numbers in a phone book using an array for
name, PhoneBook* book); implementation
NB: If the entry exists, the value should be
overwritten.
Find an entry in the phone book
char * getPhoneNumber(long number, const
PhoneBook* book);
returns null if the entry does not exist
2
[Link] [Link]
Using dynamic memory API
The memory to store the entries should be allocated #define INITIAL_SIZE 100
dynamically according to the size of the phone book.
#define INCREMENTAL_SIZE 10
Create a phone book with an initial size
typedef struct {
PhoneEntry * entries; PhoneBook createPhoneBook();
int total; Drop a phone book
int size; void dropPhoneBook(PhoneBook* book);
} PhoneBook;
When the total number of exceeds the size, the memory
entries have to be reallocated with a new size
Quiz 2 Homework K53
Rewrite the phone book program using Do Quiz 1, 2, 3, 6
dynamic memory
3
[Link] [Link]
Generic symbol tables API
Define a generic structure for entries #define INITIAL_SIZE 100
typedef struct { #define INCREMENTAL_SIZE 10
void * key;
SymbolTable createSymbolTable(
void * value;
} Entry; Entry (*makeNode)(void*, void*),
Define a generic structure for symbol tables int (*compare)(void*, void*)
typedef struct { );
Entry * entries; void dropSymbolTable(SymbolTable* tab);
int size, total;
int addEntry(void* key, void* value, SymbolTable* book);
Entry (*makeNode)(void*, void*);
int (*compare)(void*, void*); void * getEntryValue(void* key, const SymbolTable *
} SymbolTable; book);
makeNode is a function pointer to refer to a function to create a node
with a key and a value passed NB: Free the memory allocated for each entry when a
compare is a function to refer to a function to compare two keys table is dropped
Example Guide - creatSymbolTable function
Entry makePhoneBook(void* phone, void* name) { SymbolTable creatSymbolTable(Entry
Entry res;
[Link] = malloc(sizeof(int));
(*makeNode)(void*,void*),int(*compare)(void*,void*))
memcpy( [Link], phone, sizeof(int) ); {
[Link] = strdup( (char*)name ); SymbolTable a;
return res;
} [Link]=(Entry*)malloc(Initial_size*sizeof(Entry));
int comparePhone(void * key1, void* key2) { [Link]=0;
int num1 = *( (int*) key1 );
int num2 = *( (int*) key2 ); [Link]=Initial_size;
if (num1==num2) return 0; [Link]=makeNode;
else if (num1 < num2) return -1;
else return 1; [Link]=compare;
} return a;
}
SymbolTable phoneBook = createSymbolTable(makePhoneBook,
comparePhone);
4
[Link] [Link]
Quiz 3 Quiz 4 DNS Lookup
Rewrite the phone book program using a Write a DNS Lookup program that reads in a
generic symbol table file [Link] (provided by lecturer) and organize
data in file in a symbol table. The program
asks the IP address from input and return the
Domain name as output.
Add the functionality of DNS Reverse Lookup.
Users provide domain name
Program return IP address
Link to file:
[Link]
41/ip_online.html
Quiz 5 Spell checking
[Link] Write a program that takes as command-line
4a/[Link] argument the name of a file containing a
dictionary of words, and then reads strings
from standard input and prints out any string
that is not in the dictionary. Use the 600,000+
word dictionary [Link].
Link to file:
[Link]
6d/[Link]
5
[Link] [Link]
Quiz 6 Web filter Quiz 7 IP lookup by country
Write a program called WebBlocker that takes Write a program using BST that load the data in the
file [Link] to determine what country a given
as command-line argument the name of a file IP address is coming from. The data file has five fields
containing a list of objectionable websites beginning of IP address range
ending of IP address range
(provided by lecturer: [Link]) and then two character country code
reads strings from standard input and prints three character country code
and country name.
out only those websites that should not be
The IP addresses are non-overlapping.
filtered. Such a database tool can be used for: credit card
Link to file: fraud detection, spam filtering, auto-selection of
language on a web site, and web server log analysis.
[Link] Link to file:
7/[Link] [Link]
[Link]
Homework
Make a symbol table using a binary search [Link]
tree and then use this data structure to write 66/_2__ip-[Link]
the phone book program. [Link]
dc/[Link]
[Link]
e9/[Link]
[Link]
7f/[Link]
[Link]
f0/[Link]
6
[Link] [Link]
[Link]
4/[Link]
[Link]
8a/[Link]
[Link]
1c/[Link]
[Link]
05/[Link]
[Link]
a1/[Link]
7
[Link] [Link]
