Symbol Tables

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 .

Không thể tạo bản xem trước, hãy bấm tải xuống
TÀI LIỆU MỚI ĐĂNG
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.