計(jì)算機(jī)算法導(dǎo)論_第11章-wenkub
2023-04-07 00:04:59 本頁面
【正文】 is the minimum element. ? Modifying operations: change the set. ? INSERT(S, x), augments the set S with the element pointed to by x. ? DELETE(S, x), given a pointer x to an element in the set S, removes x from S. 5 Overview ? The time taken to execute a set operation is usually measured in terms of the size of the set. ? Next few lectures will focus on data structures rather than straight algorithms 1. Chapter 10 presents the essentials of working with simple data structures such as stacks, queues, linked lists, and rooted trees. 2. Chapter 11 introduces hash tables, which support the dictionary operations INSERT, DELETE, and SEARCH. 3. Chapter 12 Binary search trees 4. Chapter 13 Redblack trees, a variant of binary search trees 5. Chapter 14, augment redblack trees to support operations other than the basic ones 11 Hash Table 7 Hash Tables ? Motivation: symbol tables ? A piler uses a symbol table to relate symbols to associated data ? Symbols: variable names, procedure names, etc. ? Associated data: memory location, call graph, etc. ? For a symbol table (also called a dictionary), we care about search, insertion, and deletion ? Typically don’t care about sorted order 8 Symboltable problem ? The structure we will use is a hash table ? Supports all the above in O(1) expected time! 9 Hashing: Keys ? consider all keys to be (possibly large) natural numbers ? How can we convert floats to natural numbers for hashing purposes? ? How can we convert ASCII strings to natural numbers for hashing purposes? 10 Review ? Section discusses direct addressing ? Section presents the main ideas, focusing on chaining as a way to handle collisions ? Section describes how array indices can be puted from keys using hash functions ? Section looks at open addressing, which is another way to deal with collisions ? Section introduces perfect hashing Directaddress tables 12 Direct Addressing ? Suppose: ? The range of keys is 0..m1 ? Keys are distinct ? The idea: ? Set up an array T[0..m1] in which ? T[i] = x if x? T and key[x] = i ? T[i] = NULL otherwise ? This is called a directaddress table ? Operations take O(1) time! 13 Direct Addressing 14 Direct Addressing ? DIRECTADDRESSSEARCH(T, k) return T [k] ? DIRECTADDRESSINSERT(T, x) T[key[x]] ← x
研究報(bào)告相關(guān)推薦
鄂ICP備17016276號-1