Page 1
goupee.vn goupee.com 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@mail.hut.edu.vn dungct@it-hut.edu.vn Can interchange roles: given IP address find corresponding URL http://www.mediafire.com/?n2yzyjnnn10 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. fb.com/goupee.vn 1 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 2
goupee.vn goupee.com 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 fb.com/goupee.vn 2 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 3
goupee.vn goupee.com 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 typedef struct { Create a phone book with an initial size 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 fb.com/goupee.vn 3 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 4
goupee.vn goupee.com 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; (*makeNode)(void*,void*),int(*compare)(void*,void*)) res.key = malloc(sizeof(int)); memcpy( res.key, phone, sizeof(int) ); { res.value = strdup( (char*)name ); SymbolTable a; return res; } a.Entries=(Entry*)malloc(Initial_size*sizeof(Entry)); int comparePhone(void * key1, void* key2) { a.total=0; int num1 = *( (int*) key1 ); int num2 = *( (int*) key2 ); a.size=Initial_size; if (num1==num2) return 0; a.makeNode=makeNode; else if (num1 < num2) return -1; a.compare=compare; else return 1; } return a; } SymbolTable phoneBook = createSymbolTable(makePhoneBook, comparePhone); fb.com/goupee.vn 4 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 5
goupee.vn goupee.com 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 ip.csv (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: http://www.4shared.com/file/36199066/b8d84c 41/ip_online.html Quiz 5 Spell checking http://www.4shared.com/file/36268661/9e4927 Write a program that takes as command-line 4a/lect02.html 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 words.utf-8.txt. Link to file: http://www.4shared.com/file/36199064/56d62d 6d/wordsutf-8.html fb.com/goupee.vn 5 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 6
goupee.vn goupee.com 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 ip-to-country.csv 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 (provided by lecturer: domain.txt) and then ending of IP address range two character country code reads strings from standard input and prints three character country code out only those websites that should not be and country name. filtered. The IP addresses are non-overlapping. Such a database tool can be used for: credit card Link to file: fraud detection, spam filtering, auto-selection of http://www.4shared.com/file/36199067/cfdf7cd language on a web site, and web server log analysis. Link to file: 7/domain.html http://www.4shared.com/file/36199063/c8b2b8ce/ip-to- country.html Homework Make a symbol table using a binary search http://www.4shared.com/file/80368156/dba90d tree and then use this data structure to write 66/_2__ip-to-country.html the phone book program. http://www.4shared.com/file/80368155/42a05c dc/elements.html http://www.4shared.com/file/80368153/abc3f9 e9/ip-to-country.html http://www.4shared.com/file/80368152/dcc4c9 7f/misspellings.html http://www.4shared.com/file/80368157/acae3d f0/wordsutf-8.html fb.com/goupee.vn 6 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Page 7
goupee.vn goupee.com http://www.4shared.com/file/80373759/a5fac2f 4/pi-1million.html http://www.4shared.com/file/80373764/f066ed 8a/domain.html http://www.4shared.com/file/80373765/8761dd 1c/GeoIPCountryWhois.html http://www.4shared.com/file/80373761/800c19 05/phonena.html http://www.4shared.com/file/80373768/f9d0a1 a1/toplevel-domain.html fb.com/goupee.vn 7 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Affichage des 7 premières pages. Téléchargez le document pour le voir en entier.
Commentaires (0)
Aucun commentaire pour le moment. Soyez le premier !