Ấ
C U TRÚC D LI U VÀ I THU T GI
Ữ Ệ Ả
Ậ
Ch
ng 9: B ng
ươ
ả
Ma tr n 2 chi u vs. 1 chi u ề
ề
ậ
A[i, j]
B[ max_row*i + j]
C[i + max_col*j]
2 Ch ng 9: B ng ươ ả
B ng và ch m c
ỉ ụ
ả
3 Ch ng 9: B ng ươ ả
Radix sort B c 1 ướ
B c 2 ướ
B c 3 ướ
m o p
m a p
c a r
r a t
m a p
r a p
c a t
m o p
t o p
c a r
c o t
c a t
r a p
t a r
m a p
m a p
r a t
m o p
c a r
c a r
t a r
c a t
r a p
t o p
r a t
m o p
r a t
c o t
c a t
t o p
t a r
t a r
c o t
c o t
t o p
r a p
4 Ch ng 9: B ng ươ ả
Đánh giá Radix sort
Θ(n k), n là s ph n t
và
trên
ầ ử
ố
k là s ký t ố
ự
ố ầ khóa
ươ
ỏ
ớ ớ
n lg n: ng pháp khác là n là nh thì radix sort ch m ậ n là l n thì radix sort nhanh h n
ỏ
ớ
ơ
i lúc sau trên
DS liên t c gây ra vi c di chuy n nhi u ph n t
ụ
ể
ề
S l n so sánh là
ạ ầ ử t ố
ị
So sánh v i các ph N u ế k l n và N u ế k nh và B t ti n: ấ ệ Vi c tách thành 27 danh sách con và ghép l ệ ệ Khóa so sánh là chu i nh phân thì không t ỗ
5 Ch ng 9: B ng ươ ả
Radix sort trên DSLK
6 Ch ng 9: B ng ươ ả
Gi
i thu t Radix sort trên DSLK
ả
ậ
ầ
Algorithm radix_sort Input: danh sách c n s p th t ứ ự Output: danh sách đã s p th t ứ ự
ắ ắ
có ký t
ỗ
t ự ươ
ầ ử
ng ng ứ
//M i queue ch a các ph n t 1. queues là m t dãy có max_character hàng
ứ ộ
i v trí k
t
c, ki m tra các ký t
ự ạ ị
ể
ướ
v trí k trong khóa
ữ
//L p k b ặ 2. for position = size(khóa) to 0 2.1. while (danh sách còn) 2.1.1. L y ph n t ầ ử ầ ấ 2.1.2. Tính toán th t 2.1.3. Đ y ph n t
đ u tiên c a ch cái ứ ự ủ này vào queue t
ầ ử
ẩ
ở ị ươ
ng ng ứ
2.2. N i t
t c các queue l
i v i nhau thành danh sách
ố ấ ả
ạ ớ
End radix_sort
7 Ch ng 9: B ng ươ ả
Mã C++ Radix sort trên DSLK
const int max_chars = 28;
template
void Sortable_list :: radix_sort( ) {
Record data;
Queue queues[max_chars];
for (int position = key_size − 1; position >= 0; position−−) {
// Loop from the least to the most significant position.
while (remove(0, data) == success) {
int queue_number = alphabetic_order(data.key_letter(position));
queues[queue_number].append(data); // Queue operation.
}
rethread(queues); // Reassemble the list.
}
}
8 Ch ng 9: B ng ươ ả
N i các queue liên k t ế
ố
Dùng các CTDL queue Ph i dùng queue.retrieve và list.insert(list.size(),x)
ng trình
ả Cách 2: Vi t l ế ạ Ch c n tìm đ n cu i m i queue và n i con tr vào đ u ỉ ầ
i các CTDL ki u queue trong ch ươ ố
ầ
ỏ
ỗ
ế queue sau (ho c đ n NULL) ặ
ể ố ế
Cách 1:
9 Ch ng 9: B ng ươ ả
Tăng t c tra c u
ứ
ố
O (lg n)
ế
ộ O(1)
ụ
ế Ví d : Tra b ng v i key chính là position ớ Hàm đ i m t key thành position: hàm Hash
ả ộ
ổ
position
position
key
key
search 1
search 2
Magic
Tìm ki m: hàm f: key -> position => N u có hàm f: key -> position v i t c đ ớ ố
10 Ch ng 9: B ng ươ ả
B ng Hash
ả
đ
c tính b ng hàm hash
ầ ử ượ
ằ
ộ
ậ ả ề ộ ể
ộ ị
ề
B ng Hash ả B ngả V trí c a 1 ph n t ủ ị Hàm hash:
ể ả
ộ
O(1)
ữ ệ
ế
ầ
Nh n vào m t khóa Tr v m t ch s v trí ỉ ố ị (Có th chuy n vài khóa v cùng m t v trí) ụ N u v trí tìm ra đúng là d li u c n tìm: ị Không đúng: gi ả ả
ả
i quy t đ ng đ (ph i đ m b o ộ
ế ụ
ả O(1))
Đ ng đ trên b ng hash:
11 Ch ng 9: B ng ươ ả
Hàm Hash
ả O(1)
f(x) = x % m; f(‘abc’) = (char_index(‘a’)*base_number2 +
char_index(‘b’)*base_number1 + char_index(‘c’)*base_number0) % hash_size
Đ m b o ả Ví d :ụ
12 Ch ng 9: B ng ươ ả
Ví d dùng b ng Hash
ụ
ả
Các khóa: M, O, T, V, I, D, U
hash(x) = char_index(x) % 10
T U V M D O
Tìm V
Không có
0 1 2 3 4 5 6
7
Tìm F
8
I
9
char_index: Space=0, A=1, B=2, …, Z=27
M O T V I D U F
5 0 2 9 4 1 6 3
13 Ch ng 9: B ng ươ ả
ng pháp Đ a ch m (Open
ị
ươ
ỉ ở
ả
ng
Ph Addressing) B ng hash là m t array ộ Các v trí khi có đ ng đ s tìm v trí m i b ng các ph ộ ẽ
ớ ằ
ụ
ị
ươ
ế
ả
ị pháp gi Th tuy n tính (linear probing): ử
i quy t: ế
Tăng ch s lên m t: h = (h+i) % hash_size
ỉ ố
ộ
ử ậ
Th b c hai (quadratic probing): Tăng ch s lên theo bình ph
ng: h = (h + i
2)%
ỉ ố
ươ
Ph
hash_size ươ
Ng u nhiên
ng pháp khác ẫ
14 Ch ng 9: B ng ươ ả
Thi
t k b ng Hash dùng đ a ch m
ế ế ả
ỉ ở
ị
Đ m b o phép th tuy n tính không b l p vòng ế
ị ặ
ử
ả
ả
const int hash_size = 997; // a prime number of appropriate size
class Hash_table { public: Hash_table( ); void clear( ); Error_code insert(const Record &new entry); Error_code retrieve(const Key &target, Record &found) const; private: Record table[hash_size]; };
15 Ch ng 9: B ng ươ ả
i thu t thêm ph n t
ầ ử
dùng b ng Hash ả
ả
Gi ậ đ a ch m ỉ ở ị
Algorithm Hash_Insert
ả
Input: b ng Hash, m u tin c n thêm vào ẫ Output: b ng Hash đã có m u tin thêm vào
ầ ẫ
ả
ộ
//Có đ ng đ
1. probe = hash(input_key) 2. increment = 1 //Dùng khi đ ng đ 3. while (table[probe] không r ng) ỗ
ụ ộ
ụ
ế
ậ
ử ậ
//Dùng các phép th (tuy n tính, b c hai, …) ử 3.1. probe = (probe + increment) % hash_size 3.2. increment = increment + 2 //Th b c hai 4. table[probe] = new_data
End Hash_insert
16 Ch ng 9: B ng ươ ả
ầ ử
dùng b ng Hash ả
Mã C++ thêm ph n t đ a ch m
ỉ ở
ị
Error_code Hash_table :: insert(const Record &new entry) { Error_code result = success; int probe_count = 0, increment = 1, probe; Key null; probe = hash(new_entry); while (table[probe] != null && table[probe] != new_entry && probe_count < (hash size + 1)/2) { probe_count++; probe = (probe + increment)%hash_size; increment += 2; } if (table[probe] == null) table[probe] = new_entry; else if (table[probe] == new_entry) result = duplicate_error; else result = overflow;
return result; }
17 Ch ng 9: B ng ươ ả
ng pháp n i k t (chained hash
ố ế
Ph ươ table)
18 Ch ng 9: B ng ươ ả
L i ích c a ph
ủ
ợ
ươ
ng pháp n i k t ố ế
ố ượ
t ki m vùng nh . ớ
ế
ẫ
ớ
ệ i quy t đ ng đ : đ n gi n là đ y vào cùng m t danh sách
ng m u tin l n: ti ả ộ ơ
ế ụ
ẩ
ộ
ả
ề
ớ ố ượ
ng m u tin. ẫ là đ n gi n và nhanh chóng.
ầ ử
ả
N u s l ế Gi ả liên k t.ế
c m
ướ
ẫ
ả
ơ ế ộ N u có n m u tin, và b ng hash có kích th Đ dài trung bình c a DSLK là n/m ủ
ế ộ
B ng hash nh h n nhi u so v i s l ỏ ơ Xóa m t ph n t ộ Đ ph c t p khi tìm ki m: ứ ạ
19 Ch ng 9: B ng ươ ả
Thi
ế ế ả
t k b ng Hash n i k t ố ế
const int hash_size = 997; // a prime number of appropriate size
class Hash_table {
public:
//Specify methods here
private:
List table[hash_size];
};
20 Ch ng 9: B ng ươ ả
ươ
ng th c c a b ng ứ ủ ả
t k các ph Thi ế ế Hash n i k t ố ế Constructor:
G i constructor c a m i danh sách trong array. ỗ
ủ
ng th c clear cho m i danh sách trong array.
ươ
ứ
ỗ
ọ Clear: G i ph ọ Retrieval:
sequential_search(table[hash(target)], target, position);
Insertion:
table[hash(new_entry)].insert(0, new_entry);
Deletion:
remove(const Key type &target, Record &x); N u tìm th y trong danh sách t
ng ng thì xóa đi
ươ
ứ
ế
ấ
21 Ch ng 9: B ng ươ ả
Đánh giá ph
ng pháp dùng b ng Hash
ươ
ả
c b ng hash
ố ẫ
ướ
ả
ế
ớ ả
ử
1+(1/2)λ phép th khi tìm th y λ phép th khi không tìm th y.
ử
load factor λ = s m u tin/kích th Tìm ki m v i b ng hash n i k t: ố ế ấ ấ
ớ ả
ử
ỉ ở ử
ẫ ị (1/λ)ln (1/(1-λ)) phép th khi tìm th y ấ 1/(1-λ) phép th khi không tìm th y ấ ử
ớ ả
ử
Tìm v i b ng hash đ a ch m (th ng u nhiên):
ỉ ở ử ử
Tìm v i b ng hash đ a ch m (th tuy n tính): ị ế (1/2)(1 + 1/(1-λ)) phép th khi tìm th y ấ (1/2)(1 + 1/(1-λ)2) phép th khi không tìm th y ấ
22 Ch ng 9: B ng ươ ả
So sánh các ph
ng pháp
ươ
23 Ch ng 9: B ng ươ ả
So sánh các ph
ng pháp (tt.)
ươ
24 Ch ng 9: B ng ươ ả
