›
›

Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 5: Tập hợp

Download
Ch-¬ng 5  
TËp hîp  
TËp hîp lµ mét cÊu tróc c¬ b¶n cña to¸n häc. Trong thiÕt kÕ thuËt to¸n,  
chóng ta th-êng xuyªn ph¶i sö dông ®Õn m« h×nh d÷ liÖu tËp hîp. Trong  
ch-¬ng nµy chóng ta sÏ nghiªn cøu m« h×nh d÷ liÖu tËp hîp, c¸c ph-¬ng ph¸p  
cµi ®Æt tËp hîp. Sau ®ã chóng ta sÏ nghiªn cøu mét sè kiÓu d÷ liÖu trõu t-îng,  
®ã lµ tõ ®iÓn vµ hµng -u tiªn, ®-îc x©y dùng dùa trªn kh¸i niÖm tËp hîp,  
nh-ng chØ quan t©m ®Õn mét sè phÐp to¸n nµo ®ã.  
5.1. TËp hîp vµ c¸c phÐp to¸n trªn tËp hîp.  
Chóng ta xem r»ng, ®éc gi¶ ®· lµm quen víi tËp hîp. Do ®ã chóng ta  
chØ tr×nh bµy ng¾n gän mét sè kh¸i niÖm ®-îc sö dông ®Õn sau nµy.  
Trong to¸n häc, cã hai ph-¬ng ph¸p ®Ó x¸c ®Þnh mét tËp hîp A. §¬n  
gi¶n nhÊt lµ liÖt kª tÊt c¶ c¸c phÇn tö cña tËp A (nÕu tËp A h÷u h¹n). Ch¼ng  
h¹n, A = {1, 2, 3} cã nghÜa lµ A tËp hîp chØ gåm 3 phÇn tö 1, 2, 3. C¸ch kh¸c,  
ta còng cã thÓ x¸c ®Þnh mét tËp A b»ng c¸ch nªu lªn c¸c ®Æc tr-ng cho ta biÕt  
chÝnh x¸c mét ®èi t-îng bÊt kú cã lµ mét phÇn tö cña tËp A hay kh«ng. VÝ dô,  
A = {xx lµ sè nguyªn ch½n}. Ta cÇn quan t©m ®Õn mét tËp ®Æc biÖt : tËp  
trèng , ®ã lµ tËp hîp kh«ng chøa phÇn tö nµo c¶.  
Víi hai tËp bÊt kú A, B vµ mét ®èi t-îng x bÊt kú, ta cã c¸c quan hÖ  
sau ®©y:  
x A (x thuéc A), quan hÖ nµy ®óng nÕu vµ chØ nÕu x lµ phÇn tö  
cña tËp A.  
A B (A lµ tËp con cña B), quan hÖ nµy ®óng nÕu vµ chØ nÕu  
mäi phÇn tö cña tËp A lµ phÇn tö cña tËp B.  
A = B nÕu vµ chØ nÕu A B vµ B A.  
C¸c phÐp to¸n c¬ b¶n trªn tËp hîp  
C¸c phÐp to¸n c¬ b¶n trªn tËp hîp lµ hîp, giao, hiÖu. Cho hai tËp A vµ  
B, khi ®ã hîp cña A vµ B, A B , lµ tËp hîp gåm tÊt c¶ c¸c phÇn tö thuéc A  
hoÆc thuéc B. Cßn giao cña A vµ B lµ tËp A B gåm tÊt c¶ c¸c phÇn tö võa  
thuéc A, võa thuéc B. HiÖu A-B lµ tËp hîp gåm tÊt c¶ c¸c phÇn tö thuéc A  
nh-ng kh«ng thuéc B. Ch¼ng h¹n, nÕu A = {1, 2, 3, 4} vµ B = { 3, 4, 5} th× A  
B = {1, 2, 3, 4, 5}, cßn A B = {3, 4} vµ A-B = {1, 2}.  
0
TÝch ®ª-cac cña hai tËp hîp A vµ B lµ tËp hîp A x B gåm tÊt c¶ c¸c cÆp  
phÇn tö (a, b), trong ®ã a A vµ b B. Ch¼ng h¹n, nÕu A = {1, 2}, B = {a, b,  
c} th× A x B = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}.  
Quan hÖ nhÞ nguyªn trªn tËp hîp  
Khi xÐt mét tËp hîp, trong nhiÒu tr-êng hîp ta cÇn quan t©m ®Õn quan  
hÖ gi÷a c¸c phÇn tö cña tËp hîp. Mét quan hÖ nhÞ nguyªn (gäi t¾t lµ quan hÖ)  
R trªn tËp A lµ mét tËp con nµo ®ã cña tÝch ®ª-cac A x A, tøc lµ R A x A.  
NÕu a, b lµ c¸c phÇn tö cña tËp A vµ (a, b) R th× ta nãi a cã quan hÖ  
R víi b vµ ký hiÖu lµ aRb. VÝ dô : A = {a, b, c} vµ R = {(a, a), (a, c), (b, a),  
(c, b)}, khi ®ã a cã quan hÖ R víi c v× (a,c) R cßn b kh«ng cã quan hÖ R víi  
c v× cÆp (b, c) R.  
Mét quan hÖ R cã thÓ cã c¸c tÝnh chÊt sau :  
- Quan hÖ R trªn tËp A cã tÝnh ph¶n x¹, nÕu aRa, víi mäi a A.  
- Quan hÖ R cã tÝnh ®èi xøng, nÕu mçi khi cã aRb th× còng cã bRa.  
- Quan hÖ R cã tÝnh b¾c cÇu, nÕu mçi khi cã aRb vµ bRc th× còng cã  
aRc.  
- Quan hÖ R cã tÝnh ph¶n ®èi xøng, nÕu mçi khi cã aRb vµ a b th×  
kh«ng cã bRa.  
VÝ dô nÕu A lµ tËp c¸c sè nguyªn Z vµ R lµ quan hÖ nhá h¬n () trªn  
c¸c sè, tøc lµ víi c¸c sè nguyªn n vµ m bÊt kú, nRm nÕu vµ chØ nÕu n m, th×  
dÔ dµng thÊy r»ng, lµ quan hÖ cã tÝnh b¾c cÇu vµ ph¶n ®èi xøng, nh-ng  
kh«ng cã tÝnh ph¶n x¹ vµ ®èi xøng.  
Hai d¹ng ®Æc biÖt quan träng lµ quan hÖ t-¬ng ®-¬ng vµ quan hÖ thø tù  
bé phËn. Mét quan hÖ R trªn tËp A ®-îc gäi lµ quan hÖ t-¬ng ®-¬ng, nÕu nã  
tho¶ m·n c¸c tÝnh chÊt ph¶n x¹, ®èi xøng vµ b¾c cÇu. Khi trªn tËp A ®-îc x¸c  
®Þnh mét quan hÖ t-¬ng ®-¬ng R, ta cã thÓ ph©n ho¹ch tËp A thµnh c¸c líp  
t-¬ng ®-¬ng sao cho hai phÇn tö bÊt kú thuéc cïng mét líp nÕu vµ chØ nÕu  
chóng t-¬ng ®-¬ng víi nhau.  
Ch¼ng h¹n, trªn tËp c¸c sè nguyªn Z ta x¸c ®Þnh quan hÖ R nh- sau :  
nRm nÕu vµ chØ nÕu n-m chia hÕt cho 3. DÔ dµng thÊy r»ng, quan hÖ ®ã tho¶  
m·n c¶ ba tÝnh chÊt ph¶n x¹, ®èi xøng vµ b¾c cÇu. TËp Z ®-îc ph©n thµnh 3  
líp t-¬ng ®-¬ng, ®ã lµ c¸c tËp sè nguyªn cã d¹ng 3k, 3k+1 vµ 3k+2.  
Mét quan hÖ R trªn tËp A ®-îc gäi lµ quan hÖ thø tù bé phËn, nÕu nã  
tho¶ m·n c¸c tÝnh chÊt ph¶n x¹, ph¶n ®èi xøng vµ b¾c cÇu. Khi trªn tËp A  
®-îc x¸c ®Þnh quan hÖ thø tù bé phËn, ta nãi A lµ tËp ®-îc s¾p thø tù bé phËn.  
Ch¼ng h¹n, A lµ tËp c¸c sè nguyªn d-¬ng, quan hÖ R ®-îc x¸c ®Þnh nh- sau :  
nRm nÕu vµ chØ nÕu n lµ -íc cña m. Khi ®ã R cã c¶ ba tÝnh chÊt ph¶n x¹,  
1
ph¶n ®èi xøng vµ b¾c cÇu, do ®ã nã lµ quan hÖ thø tù bé phËn. Quan hÖ thø tù  
bé phËn R sÏ ®-îc ký hiÖu lµ , do ®ã aRb sÏ ®-îc viÕt lµ a b. TËp ®-îc  
s½p thø tù bé phËn A ®-îc gäi lµ tËp ®-îc s¾p thø tù hoµn toµn, hay tËp ®-îc  
s¾p thø tù tuyÕn tÝnh, nÕu víi mäi cÆp phÇn tö a, b thuéc A ta lu«n lu«n cã a  
b hoÆc b a. Ch¼ng h¹n, tËp c¸c sè nguyªn, tËp c¸c sè thùc ®Òu lµ c¸c tËp  
®-îc s¾p thø tù tuyÕn tÝnh víi quan hÖ th«ng th-êng.  
M« h×nh d÷ liÖu tËp hîp  
Trong thiÕt kÕ thuËt to¸n, khi sö dông tËp hîp nh- mét m« h×nh d÷ liÖu,  
ngoµi c¸c phÐp to¸n hîp, giao, hiÖu, chóng ta ph¶i cÇn ®Õn nhiÒu phÐp to¸n  
kh¸c. Sau ®©y chóng ta sÏ ®-a ra mét sè phÐp to¸n quan träng nhÊt, c¸c phÐp  
to¸n nµy sÏ ®-îc m« t¶ bëi c¸c thñ tôc hoÆc hµm.  
1. PhÐp hîp :  
Procedure Union (A, B : set; var C : set);  
Thñ tôc t×m hîp cña tËp A vµ tËp B, kÕt qu¶ lµ tËp C.  
2. PhÐp giao :  
Procedure Intersection (A, B : set; var C : set);  
Thñ tôc t×m giao cña tËp A vµ tËp B, kÕt qu¶ lµ tËp C.  
3. PhÐp trõ :  
Procedure Difference ( A,B: set ; var C: set);  
Thñ tôc t×m hiÖu cña tËp A vµ tËp B, kÕt qu¶ lµ C.  
4. X¸c ®Þnh mét phÇn tö cã thuéc tËp hîp hay kh«ng :  
Function Member ( x: element ; A: set) : boolean ;  
Hµm Member nhËn gi¸ trÞ true nÕu xA vµ false nÕu kh«ng.  
5. PhÐp xen vµo :  
Procedure Insert ( x: element ; var A: set);  
Thñ tôc nµy thªm phÇn tö x vµo tËp A, do ®ã sau khi thùc hiÖn thñ tôc,  
gi¸ trÞ míi cña A lµ A x.  
6. PhÐp lo¹i bá :  
Procedure Delete ( x : element ; var A: set);  
Thñ tôc nµy lo¹i bá x khái tËp A . Sau thñ tôc nµy ,tham biÕn A nhËn  
gi¸ trÞ míi lµ A-x.  
7. T×m phÇn tö nhá nhÊt ( phÇn tö lín nhÊt ).  
Procedure Min ( A: set ; var x: element );  
2
PhÐp to¸n nµy chØ ¸p dông trªn c¸c tËp hîp s¾p thø tù tuyÕn tÝnh . Sau  
khi thùc hiÖn thñ tôc, x lµ phÇn tö nhá nhÊt cña tËp A .  
VÊn ®Ò ®-îc ®Æt ra b©y giê lµ , ta cÇn biÓu diÔn tËp hîp nh- thÕ nµo ®Ó  
c¸c phÐp to¸n ®-îc thùc hiÖn víi hiÖu qu¶ cao .  
5.2.Cµi ®Æt tËp hîp.  
Cã nhiÒu ph-¬ng ph¸p biÓu diÔn tËp hîp. Trong tõng ¸p dông, tuú  
thuéc vµo c¸c phÐp to¸n cÇn thùc hiÖn vµ cì ( sè phÇn tö ) cña tËp hîp mµ ta  
lùa chän c¸ch cµi ®Æt sao cho c¸c phÐp to¸n thùc hiÖn cã hiÖu qu¶ .  
Tr-íc hÕt, chóng ta cÇn biÕt r»ng, c¸c phÇn tö cña tËp hîp cã thÓ lµ ®èi  
t-îng phøc t¹p (kh«ng ph¶i lµ c¸c sè nguyªn, sè thùc hoÆc c¸c kÝ tù ). C¸c ®èi  
t-îng nµy cã thÓ ®-îc biÓu diÔn bëi b¶n ghi mµ c¸c tr-êng lµ c¸c thuéc tÝnh  
cña ®èi t-îng. Mçi phÇn tö ®-îc hoµn toµn x¸c ®Þnh bëi c¸c gi¸ trÞ cña mét sè  
tr-êng nµo ®ã (kho¸). Trong tr-êng hîp nµy, ta cã thÓ m« t¶ kiÓu d÷ liÖu cña  
c¸c phÇn tö cña tËp hîp nh- sau.  
type elementtype = record  
key : keytype;  
[C¸c tr-êng kh¸c]  
end;  
5.2.1.Cµi ®Æt tËp hîp bëi vect¬ bit.  
Gi¶ sö c¸c tËp hîp mµ ta quan t©m ®Òu lµ tËp con cña mét tËp "vò trô"  
nµo ®ã . Gi¶ sö cì cña tËp vò trô t-¬ng ®èi nhá vµ c¸c phÇn tö cña nã lµ c¸c  
sè nguyªn tõ 1 ®Õn n ( hoÆc ®-îc m· ho¸ bëi c¸c sè nguyªn 1..n ). Khi ®ã ta  
cã thÓ dïng vect¬ bit (m¶ng boolean) ®Ó biÓu diÔn tËp hîp. Mét tËp A ®-îc  
biÓu diÔn bëi vect¬ bit (A[1] , A[2] ,..., A[i] ,..., A[n] ), trong ®ã thµnh phÇn thø  
i , A[i] lµ true nÕu vµ chØ nÕu i lµ phÇn tö cña tËp A.  
const n = ...;  
type Set = array[1..n] of boolean;  
var A,B,C : set;  
x : 1..n;  
DÔ dµng thÊy r»ng, víi c¸ch cµi ®Æt nµy, tÊt c¶ c¸c phÐp to¸n c¬ b¶n  
trªn tËp hîp ®Òu ®-îc thùc hiÖn rÊt dÔ dµng, vµ víi thêi gian thùc hiÖn cïng  
l¾m lµ tû lÖ víi cì cña tËp vò trô, tøc lµ O(n). Ch¼ng h¹n, ®Ó thªm x vµo tËp  
3
A, ta chØ cÇn thùc hiÖn lÖnh  
A[x]: = true  
Cßn ®Ó x¸c ®Þnh x cã lµ tËp con cña tËp A hay kh«ng ta chØ cÇn biÕt  
A[x] lµ true hay false.  
C¸c phÐp hîp, giao, hiÖu cña hai tËp hîp còng ®-îc thùc hiÖn rÊt ®¬n  
gi¶n. Sau ®©y lµ hµm Union thùc hiÖn phÐp lÊy hîp cña hai tËp A vµ B.  
procedure Union (A, B : Set; var C: Set ) ;  
var i: integer;  
begin  
for i : = 1 to n do C[i] : = A[i] or B[i]  
end;  
5.2.2.Cµi ®Æt tËp hîp bëi danh s¸ch  
Chóng ta còng cã thÓ biÓu diÔn tËp hîp bëi danh s¸ch L=(a1, a2,..., an),  
trong ®ã c¸c thµnh phÇn ai cña danh s¸ch lµ c¸c phÇn tö cña tËp hîp. Nhí l¹i  
r»ng, mét danh s¸ch cã thÓ ®-îc cµi ®Æt bëi m¶ng, hoÆc bëi danh s¸ch liªn  
kÕt. Do ®ã chóng ta cã thÓ cµi ®Æt tËp hîp bëi m¶ng hoÆc bëi danh s¸ch liªn  
kÕt.  
1. Cµi ®Æt tËp hîp bëi m¶ng :  
Gi¶ sö sè phÇn tö cña tËp hîp kh«ng v-ît qu¸ mét h»ng nµo ®ã  
maxsize. Khi ®ã ta cã thÓ biÓu diÔn tËp hîp bëi mét m¶ng. C¸c thµnh phÇn  
cña m¶ng b¾t ®Çu tõ thµnh phÇn ®Çu tiªn sÏ l-u gi÷ c¸c phÇn tö cña tËp hîp. ta  
sÏ ®-a vµo mét biÕn last ghi l¹i chØ sè cña thµnh phÇn cuèi cïng cña m¶ng cã  
chøa phÇn tö cña tËp hîp.  
const maxsize = ...;  
type Set = record  
last : integer;  
element : array [1..maxsize] of elementtype;  
end;  
Trong c¸ch cµi ®Æt nµy, mét kh«ng gian nhí cè ®Þnh (do cì cña m¶ng  
qui ®Þnh) ®-îc dïng ®Ó l-u gi÷ c¸c phÇn tö cña tËp hîp. ViÖc thùc hiÖn c¸c  
phÐp hîp, xen vµo cã thÓ dÉn ®Õn c¸c tËp hîp cã sè phÇn tö v-ît qu¸ cì cña  
m¶ng. Do ®ã khi sö dông c¸ch cµi ®Æt nµy chóng ta ph¶i chän maxsize thÝch  
hîp ®Ó tiÕt kiÖm bé nhí vµ tr¸nh tr-êng hîp bÞ trµn.  
Chóng t«i ®Ó l¹i cho ®éc gi¶ tù viÕt c¸c thñ tôc vµ hµm thùc hiÖn c¸c  
4
phÐp to¸n tËp hîp trong c¸ch cµi ®Æt nµy.  
2. Cµi ®Æt tËp hîp bëi danh s¸ch liªn kÕt  
ViÖc biÓu diÔn tËp hîp bëi danh s¸ch liªn kÕt sÏ kh¾c phôc ®-îc h¹n  
chÕ vÒ kh«ng gian khi dïng m¶ng. ta cã thÓ sö dông ph-¬ng ph¸p nµy ®Ó biÓu  
diÔn tËp hîp cã sè phÇn tö nhiÒu Ýt tuú ý, miÔn lµ bé nhí cña m¸y cho phÐp.  
Tuy nhiªn trong c¸ch cµi ®Æt nµy, viÖc thùc hiÖn c¸c phÐp to¸n tËp hîp sÏ  
phøc t¹p h¬n. Mçi thµnh phÇn trong danh s¸ch liªn kÕt biÓu diÔn tËp hîp lµ  
mét tÕ bµo cã khai b¸o nh- sau :  
type pointer = ^ Cell;  
Cell = record  
elementtype;  
next : pointer;  
end;  
C¸c tËp hîp A, B, C sÏ ®-îc biÓu diÔn bëi c¸c danh s¸ch liªn kÕt, trong  
®ã c¸c con trá A, B, C sÏ trá tíi ®Çu cña c¸c danh s¸ch ®ã.  
var A, B, C : pointer;  
Sau ®©y chóng ta sÏ tr×nh bµy sù thùc hiÖn c¸c phÐp to¸n khi tËp hîp  
®-îc cµi ®Æt bëi danh s¸ch liªn kÕt. PhÐp to¸n Member (x,A) chÝnh lµ phÐp  
t×m kiÕm phÇn tö x trong danh s¸ch liªn kÕt A.  
Cho hai tËp hîp A vµ B ®-îc biÓu diÔn bëi c¸c danh s¸ch liªn kÕt. ViÖc  
t×m danh s¸ch C biÓu diÔn hîp, giao hoÆc hiÖu cña A vµ B ®-îc tiÕn hµnh bëi  
cïng mét ph-¬ng ph¸p. Ch¼ng h¹n, muèn t×m giao cña A vµ B, ta ph¶i so  
s¸nh mçi phÇn tö e cña danh s¸ch A víi lÇn l-ît tõng phÇn tö cña danh s¸ch  
B. NÕu trong danh s¸ch B cã mét phÇn tö cïng lµ e th× phÇn tö e ®-îc ®-a vµo  
danh s¸ch C.  
Sau ®©y lµ thñ tôc thùc hiÖn phÐp giao :  
procedure Intersection (A, B : pointer; var C : pointer);  
var Ap, Bp, Cp : pointer;  
found : boolean;  
begin  
C : = nil;  
Ap : = A;  
while Ap   nil do  
begin  
Bp : = B;  
5
found : = false;  
while (Bp   nil) and (not found) do  
if Bp ^. element + Ap ^. element then  
found : = true else Bp : = Bp^.next;  
if found then  
begin  
new (Cp);  
Cp ^. element : = Ap ^. element;  
Cp ^. next : = C;  
C : = Cp  
end;  
Ap : = Ap ^. next  
end  
end;  
§Ó t×m hîp cña A vµ B, ®Çu tiªn ta sao chÐp danh s¸ch B ®Ó cã danh  
s¸ch C lµ b¶n sao cña B. Sau ®ã ta so s¸nh mçi phÇn tö e cña danh s¸ch A víi  
tõng phÇn tö cña danh s¸ch B. NÕu kh«ng cã phÇn tö nµo cña B lµ e th× ta  
thªm e vµo danh s¸ch C. Mét c¸ch t-¬ng tù ®èi víi phÐp to¸n A-B.  
Trong c¸ch cµi ®Æt tËp hîp bëi danh s¸ch (kh«ng ®-îc s¾p) nh- trªn,  
khi thùc hiÖn c¸c phÐp to¸n hîp, giao, trõ, ta ph¶i so s¸nh mçi phÇn tö cña  
danh s¸ch A víi tõng phÇn tö cña danh s¸ch B. Do ®ã thêi gian thùc hiÖn c¸c  
phÐp to¸n ®ã lµ 0(n2), trong ®ã n = max (A, B), ë ®©y Aký hiÖu sè phÇn  
tö cña tËp A.  
C. Cµi ®Æt tËp hîp bëi danh s¸ch ®-îc s¾p :  
Trong tr-êng hîp c¸c tËp hîp lµ c¸c tËp con cña tËp vò trô ®-îc s¾p  
tuyÕn tÝnh bëi quan hÖ thø tù nµo ®ã, th× c¸c phÐp to¸n tËp hîp sÏ ®-îc thùc  
hiÖn nhanh h¬n nÕu ta cµi ®Æt c¸c tËp bëi c¸c danh s¸ch ®-îc s¾p. Mét tËp  
®-îc biÓu diÔn bëi danh s¸ch ®-îc s¾p, nÕu c¸c thµnh phÇn cña danh s¸ch  
®-îc s¾p xÕp theo thø tù t¨ng dÇn (hoÆc gi¶m dÇn) : a1 < a2 < ... < an. Chó ý :  
thay cho viÖc xÐt chÝnh c¸c phÇn tö cña tËp hîp, ta cã thÓ xÐt c¸c kho¸ cña  
chóng. NÕu tËp c¸c kho¸ lµ tËp ®-îc s¾p tuyÕn tÝnh th× ta còng cã thÓ cµi ®Æt  
tËp hîp bëi danh s¸ch ®-îc s¾p theo kho¸.  
Víi c¸c danh s¸ch ®-îc s¾p A vµ B, ®Ó t×m danh s¸ch ®-îc s¾p C biÓu  
diÔn hîp, giao, hiÖu cña chóng, ta chØ cÇn so s¸nh mçi phÇn tö a cña danh  
s¸ch A víi c¸c phÇn tö cña danh s¸ch B cho tíi khi hoÆc t×m ®-îc trong danh  
s¸ch B mét phÇn tö b»ng a, hoÆc t×m ®-îc mét phÇn tö b > a. H¬n n÷a, nÕu  
®èi víi mét phÇn tö ai trong danh s¸ch A, ta ®· t×m ®-îc mét phÇn tö bk trong  
danh s¸ch B sao cho ai bk, th× ®èi víi phÇn tö tiÕp theo ai+1 trong danh s¸ch  
A ta chØ cÇn b¾t ®Çu sù t×m kiÕm trong danh s¸ch B kÓ tõ thµnh phÇn bk. Do  
6
®ã thêi gian thùc hiÖn c¸c phÐp to¸n hîp, giao, trõ sÏ tû lÖ víi sè phÇn tö cña  
tËp hîp, O(n), trong ®ã n = max (A, B).  
Sau ®©y chóng ta sÏ viÕt c¸c thñ tôc thùc hiÖn c¸c phÐp hîp vµ giao cña  
c¸c tËp hîp ®-îc biÓu diÔn bëi c¸c danh s¸ch ®-îc s¾p A vµ B. Danh s¸ch  
®-îc s¾p C biÓu diÔn hîp (hoÆc giao) lµ danh s¸ch vßng trßn, con trá C trá tíi  
cuèi danh s¸ch, cßn C^.next trá tíi ®Çu danh s¸ch .  
procedure Union (A,B : pointer ; var C: pointer );  
var Ap , Bp , Cp : pointer ;  
procedure Add ( Cp : pointer ; var C: pointer);  
Thªm Cp vµo cuèi danh s¸ch C   
begin  
if C=nil then  
begin  
C:=Cp;  
C^.next :=C  
end else  
begin  
Cp^.next :=C^.next;  
C^.next := Cp;  
C:=Cp  
end  
end;  
begin  
C:= nil;  
Ap:=A;  
Bp:=B;  
while ( Ap<>nil) and (Bp<> nil)  
if Ap^.element < = Bp^.element then  
begin  
new(Cp);  
Cp^.element:=Ap^.element  
Add(Cp,C);  
if Ap^.element=Bp^.element then  
begin  
Ap := Ap^.next ;  
Bp := Bp^.next  
end else Ap:=Ap^.next  
end else  
7
begin  
end;  
new(Cp);  
Cp^.element:=Bp^.element  
Add(Cp,C);  
Bp:=Bp^.next  
while Ap < > nil do  
begin  
new(Cp);  
Cp^.element:=Ap^.element;  
Add (Cp,C);  
while Bp < > nil do  
begin  
new (Cp);  
C ^. element : Bp ^. element ;  
Add (Cp, C)  
end;  
end;  
procedure Intersection(A,B : pointer; var C: pointer);  
var Ap, Bp, Cp : pointer;  
begin  
C:=nil;  
Ap:=A;  
Bp:=B;  
while ( Ap< > nil ) and (Bp< > nil) do  
if Ap^.element= Bp^.element then  
begin  
new(Cp);  
Cp^.element := Ap^.element;  
Add(Cp,C);  
Ap:= Ap^.next;  
Bp := Bp^.next;  
end else  
if Ap^.element < Bp^.element then Ap := Ap^.next  
else Bp := Bp^.next  
end;  
8
5.3.Tõ ®iÓn  
5.3.1.Tõ ®iÓn  
Trong nhiÒu ¸p dông, khi sö dông m« h×nh d÷ liÖu tËp hîp ®Ó thiÕt kÕ  
thuËt to¸n, ta kh«ng cÇn ®Õn c¸c phÐp to¸n lÊy hîp, giao, hiÖu cña c¸c tËp .  
Th«ng th-êng khi ®· l-u gi÷ mét tËp hîp th«ng tin nµo ®ã, ta chØ cÇn ®Õn  
phÐp to¸n thªm mét phÇn tö míi n÷a vµo tËp hîp, lo¹i khái tËp hîp mét phÇn  
tö vµ t×m xem trong tËp hîp cã chøa mét phÇn tö nµo ®ã hay kh«ng.  
M« h×nh gi÷ liÖu tËp hîp, nh-ng chØ xÐt ®Õn nh÷ng phÐp to¸n Insert,  
Delete vµ Member ®-îc gäi lµ kiÓu gi÷ liÖu trõu t-îng tõ ®iÓn ( Dictionary )  
Sau ®©y chóng ta sÏ nªu ra c¸c ph-¬ng ph¸p ®¬n gi¶n mµ chóng ta ®·  
biÕt trong c¸c ch-¬ng tr-íc ®Ó cµi ®Æt tõ ®iÓn. Trong môc 5. 4 chóng ta sÏ  
tr×nh bµy mét kü thuËt míi ®Ó cµi ®Æt tõ ®iÓn.  
5.3.2.C¸c ph-¬ng ph¸p ®¬n gi¶n cµi ®Æt tõ ®iÓn  
Tõ ®iÓn lµ mét tËp hîp, do ®ã ®-¬ng nhiªn ta cã thÓ sö dông c¸c  
ph-¬ng ph¸p cµi ®Æt tËp hîp ®Ó cµi ®Æt tõ ®iÓn .  
Chóng ta cã thÓ biÓu diÔn tõ ®iÓn bëi vect¬ bit. Khi ®ã c¸c phÐp to¸n  
trong tõ ®iÓn ®-îc thùc hiÖn rÊt ®¬n gi¶n víi thêi gian h»ng. Tuy nhiªn, ta chØ  
cã thÓ ¸p dông ®-îc ph-¬ng ph¸p nµy nÕu tõ ®iÓn lµ tËp hîp cã thÓ dïng lµm  
tËp chØ sè cho m¶ng .  
Chóng ta cã thÓ biÓu diÔn tõ ®iÓn bëi danh s¸ch. §Õn l-ît m×nh, danh  
s¸ch cã thÓ ®-îc cµi ®Æt bëi m¶ng hoÆc bëi danh s¸ch liªn kÕt. Khi cµi ®Æt tõ  
®iÓn bëi m¶ng hoÆc bëi danh s¸ch liªn kÕt , mçi ph-¬ng ph¸p ®Òu cã -u ®iÎm  
vµ nh-îc ®iÓm mµ chóng ta ®· ph©n tÝch ë ch-¬ng 3. Thêi gian ®Ó thùc hiÖn  
c¸c phÐp to¸n Insert, Delete, Member nãi chung lµ O(n) víi tõ ®iÓn cã n phÇn  
tö.  
Gi¶ sö tõ ®iÓn lµ mét tËp ®-îc s¾p thø tù tuyÕn tÝnh . Trong tr-êng hîp  
nµy, ta cã thÓ biÓu diÔn tõ ®iÓn bëi c©y t×m kiÕm nhÞ ph©n. Víi c¸ch cµi ®Æt  
nµy c¸c phÐp to¸n Member, Insert vµ Delete lµ c¸c phÐp to¸n t×m kiÕm, xen  
vµo vµ lo¹i bá trªn c©y t×m kiÕm nhÞ ph©n ®-îc xÐt trong ch-¬ng 4. Thêi gian  
trung b×nh ®Ó thùc hiÖn c¸c phÐp to¸n trªn c©y t×m kiÕm nhÞ ph©n lµ O(logn),  
trong tr-êng hîp xÊu nhÊt khi c©y suy biÕn thµnh danh s¸ch lµ O(n). NÕu ta  
biÓu diÔn tõ ®iÓn bëi c©y c©n b»ng, th× thêi gian thùc hiÖn c¸c phÐp to¸n, ngay  
c¶ trong tr-êng hîp xÊu nhÊt cïng lµ 0(logn). Tuy nhiªn nh- chóng ta ®· biÕt,  
viÖc thùc hiÖn c¸c phÐp to¸n xen vµo vµ lo¹i bá trªn c©y c©n b»ng kh¸ phøc  
t¹p.  
5. 4. CÊu tróc d÷ liÖu b¶ng b¨m.  
Cµi ®Æt tõ ®iÓn bëi b¶ng b¨m.  
Trong môc nµy chóng ta sÏ tr×nh bµy mét kü thuËt quan träng, ®-îc gäi  
9
lµ ph-¬ng ph¸p b¨m (hashing). Chóng ta sÏ ¸p dông ph-¬ng ph¸p b¨m ®Ó cµi  
®Æt tõ ®iÓn. B¨m lµ ph-¬ng ph¸p rÊt thÝch hîp ®Ó cµi ®Æt tËp hîp cã sè phÇn tö  
lín vµ thêi gian cÇn thiÕt ®Ó thùc hiÖn c¸c phÐp to¸n tõ ®iÓn, ngay c¶ trong  
tr-êng hîp xÊu nhÊt, lµ tû lÖ víi cì cña tËp hîp.  
Chóng ta sÏ ®Ò cËp ®Õn hai ph-¬ng ph¸p b¨m kh¸c nhau. Mét gäi lµ  
b¨m më (open hasing) cho phÐp sö dông mét kh«ng gian kh«ng h¹n chÕ ®Ó  
l-u gi÷ c¸c phÇn tö cña tËp hîp. Ph-¬ng ph¸p b¨m kh¸c ®-îc gäi lµ b¨m ®ãng  
(closed hashing) sö dông mét kh«ng gian cè ®Þnh vµ do ®ã tËp hîp ®-îc cµi  
®Æt ph¶i cã cì kh«ng v-ît qu¸ kh«ng gian cho phÐp.  
5.4.1. B¶ng b¨m më :  
T- t-ëng c¬ b¶n cña b¨m më lµ ph©n chia tËp hîp ®· cho thµnh mét sè  
cè ®Þnh c¸c líp. Ch¼ng h¹n, ta muèn ph©n thµnh N líp ®-îc ®¸nh sè 0, 1, ...,  
N-1. Ta sö dông m¶ng T víi chØ sè ch¹y tõ 0 ®Õn N-1. Mçi thµnh phÇn T [i]  
cña m¶ng ®-îc nãi ®Õn nh- mét "ræ" ®ùng c¸c phÇn tö cña tËp hîp thuéc líp  
thø i. C¸c phÇn tö cña tËp hîp thuéc mçi líp ®-îc tæ chøc d-íi d¹ng mét  
danh s¸ch liªn kÕt. Do ®ã T [i] sÏ chøa con trá trá ®Õn danh s¸ch cña líp i. Ta  
sÏ gäi m¶ng T lµ b¶ng b¨m (hash table).  
ViÖc ph©n chia c¸c phÇn tö cña tËp hîp vµo c¸c líp ®-îc thùc hiÖn bëi  
hµm b¨m (hash function) h. NÕu x lµ mét gi¸ trÞ kho¸ cña phÇn tö nµo ®ã cña  
tËp hîp th× h(x) lµ chØ sè nµo ®ã cña m¶ng T vµ ta gäi h(x) lµ gi¸ trÞ b¨m  
(hash value) cña x. Nh- vËy h lµ ¸nh x¹ tõ tËp hîp c¸c kho¸ K vµo tËp hîp {0,  
1, ..., N-1}.  
Hµm b¨m  
Cã hai tiªu chuÈn chÝnh ®Ó lùa chän mét hµm b¨m. Tr-íc hÕt nã ph¶i  
cho phÐp tÝnh ®-îc dÔ dµng vµ nhanh chãng gi¸ trÞ b¨m cña mçi kho¸. Thø  
hai nã ph¶i ph©n bè ®Òu c¸c kho¸ vµo c¸c ræ. Trªn thùc tÕ tiªu chuÈn thø hai  
rÊt khã ®-îc thùc hiÖn. Sau ®©y chóng ta ®-a ra mét sè ph-¬ng ph¸p thiÕt kÕ  
hµm b¨m :  
1. Ph-¬ng ph¸p c¾t bá : gi¶ sö kho¸ lµ sè nguyªn (nÕu kho¸ kh«ng ph¶i lµ sè  
nguyªn, ta xÐt ®Õn c¸c m· sè cña chóng). Ta sÏ bá ®i mét phÇn nµo ®ã cña  
kho¸, vµ lÊy phÇn cßn l¹i lµm gi¸ trÞ b¨m cña kho¸. Ch¼ng h¹n, nÕu kho¸ lµ  
c¸c sè nguyªn 10 ch÷ sè vµ b¶ng b¨m gåm 1000 thµnh phÇn, khi ®ã ta cã thÓ  
lÊy ch÷ sè thø nhÊt, thø ba vµ thø bÈy tõ bªn tr¸i lµm gi¸ trÞ b¨m. VÝ dô : h  
(7103592810) = 702. Ph-¬ng ph¸p c¾t bá rÊt ®¬n gi¶n, nh-ng nã th-êng  
kh«ng ph©n bè ®Òu c¸c kho¸.  
2. Ph-¬ng ph¸p gÊp : gi¶ sö kho¸ lµ sè nguyªn. Ta ph©n chia kho¸ thµnh mét  
sè phÇn, sau ®ã kÕt hîp c¸c phÇn l¹i b»ng mét c¸ch nµo ®ã (ch¼ng h¹n, dïng  
phÐp céng hoÆc phÐp nh©n) ®Ó nhËn gi¸ trÞ b¨m. Ch¼ng h¹n, nÕu kho¸ lµ sè  
nguyªn 10 ch÷ sè, ta ph©n thµnh c¸c nhãm ba, ba, hai vµ hai ch÷ sè tõ bªn  
10  
tr¸i, céng c¸c nhãm víi nhau, sau ®ã c¾t côt nÕu cÇn thiÕt, ta sÏ nhËn ®-îc gi¸  
trÞ cña hµm b¨m. VÝ dô 7103592810 ®-îc biÕn ®æi thµnh 710+359+28+10 =  
1107, do ®ã ta cã gi¸ trÞ b¨m lµ 107. V× mäi th«ng tin trong kho¸ ®Òu ®-îc  
ph¶n ¸nh vµo gi¸ trÞ b¨m, nªn ph-¬ng ph¸p gÊp cho ph©n bè ®Òu c¸c kho¸ tèt  
h¬n ph-¬ng ph¸p c¾t bá.  
3. Ph-¬ng ph¸p sö dông phÐp to¸n lÊy phÇn d- : gi¶ sö kho¸ lµ sè nguyªn, vµ  
gi¶ sö ta muèn chia tËp hîp c¸c kho¸ thµnh N líp. Chia sè nguyªn cho N råi  
lÊy phÇn d- lµm gi¸ trÞ b¨m. §iÒu nµy trong Pascal ®-îc thùc hiÖn b»ng phÐp  
to¸n MOD. TÝnh ph©n bè ®Òu c¸c kho¸ cña hµm b¨m ®-îc x¸c ®Þnh b»ng  
ph-¬ng ph¸p nµy phô thuéc nhiÒu vµo viÖc chän N. Tèt nhÊt chän N lµ sè  
nguyªn tè. Ch¼ng h¹n thay cho chän N = 1000, ta lÊy N= 997 hoÆc N = 1009.  
Sau ®©y ta sÏ viÕt mét hµm b¨m trong Pascal ®Ó b¨m c¸c kho¸ lµ c¸c  
x©u kÝ tù cã ®é dµi 10 thµnh c¸c gi¸ trÞ tõ 0 ®Õn N-1  
type  
keytype = string [10]  
function  
h (x : keytupe) : 0..N-1;  
var I, Sum : integer;  
begin  
Sum : = 0;  
for i = 1 to 10 do  
Sum : = Sum + ord(x[i]);  
h : = Sum mod N  
end;  
Trong hµm b¨m trªn, ta ®· chuyÓn ®æi c¸c x©u kÝ tù thµnh c¸c sè  
nguyªn b»ng c¸ch lÊy tæng sè cña c¸c m· sè cña tõng kÝ tù trong x©u (ord (c)  
lµ m· sè cña kÝ tù c).  
CÊu tróc d÷ liÖu b¶ng b¨m më ®-îc minh ho¹ trong h×nh 5.1  
0
11  
1
2
N-1  
T
H×nh 5.1 B¶ng b¨m më.  
Chóng ta cã thÓ khai b¸o cÊu tróc d÷ liÖu b¶ng b¨m më biÓu diÔn tõ  
®iÓn nh- sau :  
const  
type  
N = ...;  
pointer = ^ element;  
element = record  
key : keytype;  
next : pointer  
end;  
Dictionary = array [0 .. N-1] of pointer;  
var T : Dictionary;  
ViÖc khëi t¹o mét tõ ®iÓn rçng ®-îc thùc hiÖn b»ng lÖnh sau  
for i : = 0 to N-1 do T [i] : = nil;  
C¸c phÐp to¸n tõ ®iÓn trªn b¶ng b¨m më  
Sau ®©y chóng ta sÏ ®-a ra c¸c thñ tôc thùc hiÖn c¸c phÐp to¸n tõ ®iÓn.  
12  
function  
var  
begin  
Member (x : keytype; var T : Dictionary) : boolean;  
P : pointer; found : boolean;  
P : = T [h(x)];  
found : = false;  
while (P < > nil) and (not found) do  
if P ^. key = x then found : = true  
else P : = P ^. next;  
Member : = found  
end;  
procedure Insert (x : keytype; var T : Dictionary);  
var i : 1 .. N-1;  
P : pointer;  
begin  
if not Member (x, T) then  
begin  
i : = h (x);  
new (P);  
P ^. key : = x;  
P ^. next : = T [i];  
T[i] : = P  
end  
end;  
procedure Delete (x : keytype; var T : dictionary);  
var i : 0 .. N-1;  
P, Q : pointer; found : boolean;  
begin  
i : = h (x);  
13  
found : = false;  
if T[i] < > nil then  
if T [i] ^. key = x then  
begin { lo¹i x khái danh s¸ch}  
T [i] : = T [i] ^. next;  
found : = true  
end else  
begin {xem xÐt c¸c thµnh phÇn tiÕp theo trong danh s¸ch}  
Q : = T [i];  
P : = Q ^. next;  
while (P < > nil) and (not found) do  
if P ^. key = x then  
begin { lo¹i x khái danh s¸ch }  
Q ^. next : = P ^. next;  
found : = true  
end else  
begin  
Q : = P;  
P : = Q ^. next;  
end;  
end;  
end;  
5.4.2. B¶ng b¨m ®ãng :  
Trong b¶ng b¨m më, mçi thµnh phÇn T [i] cña b¶ng l-u gi÷ con trá trá  
tíi danh s¸ch c¸c phÇn tö cña tËp hîp ®-îc ®-a vµo líp thø i (i = 0, ..., N-1).  
Kh¸c víi b¶ng b¨m më, trong b¶ng b¨m ®ãng, mçi phÇn tö cña tËp ®-îc l-u  
gi÷ trong chÝnh c¸c thµnh phÇn T [i] cña m¶ng. Do ®ã ta cã thÓ khai b¸o kiÓu  
d÷ liÖu tõ ®iÓn ®-îc cµi ®Æt bëi b¶ng b¨m ®ãng nh- sau :  
type Dictionary = array [o .. N-1] of keytype  
ë ®©y KeyType lµ kiÓu d÷ liÖu cña kho¸ cña c¸c phÇn tö trong tõ ®iÓn.  
Nhí l¹i r»ng, hµm b¨m  
14  
h : K {0, 1, ..., N-1}  
lµ ¸nh x¹ tõ tËp hîp c¸c kho¸ K vµo tËp hîp c¸c chØ sè 0, 1, ..., N-1 cña m¶ng.  
§©y lµ ¸nh x¹ nhiÒu-vµo-mét, nªn cã thÓ xÈy ra mét sè khãa kh¸c nhau ®-îc  
¸nh x¹ vµo cïng mét chØ sè. Do ®ã cã thÓ cã tr-êng hîp, ta muèn ®Æt kho¸ x  
vµo thµnh phÇn i = h (x) cña m¶ng, nh-ng ë ®ã ®· l-u gi÷ mét kho¸ kh¸c.  
Hoµn c¶nh nµy ®-îc gäi lµ sù va ch¹m (collision). VÊn ®Ò ®Æt ra lµ gi¶i quyÕt  
sù va ch¹m nh- thÕ nµo.  
Sù va ch¹m ®-îc gi¶i quyÕt b»ng c¸ch b¨m l¹i (rehashing). ChiÕn l-îc  
b¨m l¹i lµ nh- sau. ta sÏ lÇn l-ît xÐt c¸c vÞ trÝ h1 (x), h2 (x), ... cho tíi khi t×m  
®-îc mét vÞ trÝ nµo trèng ®Ó ®Æt x vµo ®ã. NÕu kh«ng t×m ®-îc vÞ trÝ nµo trèng  
th× b¶ng ®· ®Çy vµ ta kh«ng thÓ ®-a x vµo b¶ng ®-îc n÷a. ë ®©y hi (x) (i = 1,  
2, ...) lµ c¸c gi¸ trÞ b¨m l¹i lÇn thø i, nã chØ phô thuéc vµo kho¸ x. Sau ®©y  
chóng ta sÏ xÐt mét sè ph-¬ng ph¸p b¨m l¹i.  
C¸c ph-¬ng ph¸p b¨m l¹i.  
1. B¨m l¹i tuyÕn tÝnh  
§©y lµ ph-¬ng ph¸p b¨m l¹i ®¬n gi¶n nhÊt. C¸c hµm hi (x) ®-îc x¸c  
®Þnh nh- sau :  
hi (x) = (h (x) + i) mod N.  
Tøc lµ, ta xem m¶ng lµ m¶ng vßng trßn vµ lÇn l-ît xem xÐt c¸c vÞ trÝ h  
(x) + 1, h (x) + 2, ...  
Ch¼ng h¹n, N = 10 vµ c¸c kho¸ a, b, c, d, e cã c¸c gi¸ trÞ b¨m nh- sau h  
(a) = 7, h(b) = 1, h (c) = 4, h (d) = 3, h (e) = 3.  
b
d
c
e
a
0
1
2 3  
4
5
6
7
8
9
H×nh 5.2  
Gi¶ sö ban ®Çu b¶ng rçng, tøc lµ tÊt c¶ c¸c thµnh phÇn cña b¶ng ®Òu  
chøa mét gi¸ trÞ empty nµo ®ã kh¸c víi tÊt c¶ c¸c gi¸ trÞ kho¸. Gi¶ sö ta muèn  
®-a vµo b¶ng rçng lÇn l-ît c¸c gi¸ trÞ kho¸ a, b, c, d, e. Khi ®ã a, b, c, d lÇn  
l-ît ®-îc ®Æt vµo c¸c vÞ trÝ 7, 1, 4, 3 vµo b¶ng. V× h(e) = 3, ta t×m ®Õn thµnh  
phÇn thø 3 cña m¶ng vµ thÊy nã ®· chøa d. T×m ®Õn thµnh phÇn h1 (e) = h (e)  
+ 1 = 4, l¹i thÊy nã ®· chøa c. T×m ®Õn thµnh phÇn h2 (e) = 5, vÞ trÝ nµy rçng,  
ta ®-a e vµo ®ã. KÕt qu¶ lµ ta cã b¶ng b¨m ®ãng ®-îc minh ho¹ trong h×nh  
5.2.  
H¹n chÕ c¬ b¶n cña ph-¬ng ph¸p b¨m l¹i tuyÕn tÝnh lµ c¸c gi¸ trÞ kho¸  
sÏ ®-îc xÕp liÒn vµo sau c¸c gi¸ trÞ kho¸ ban ®Çu ®· ®-a vµo b¶ng mµ kh«ng  
15  
gÆp va ch¹m. Do ®ã cµng ngµy c¸c gi¸ trÞ khãa trong b¶ng cµng tô l¹i thµnh  
c¸c ®o¹n dµi bÞ lÊp ®Çy vµ gi÷a c¸c ®o¹n bÞ lÊp ®Çy lµ c¸c kho¶ng trèng. Vµ v×  
vËy, viÖc t×m ra mét vÞ trÝ trèng trong b¶ng ®Ó ®-a gi¸ trÞ míi vµo, cµng vÒ sau  
cµng chËm.  
2. B¨m l¹i b×nh ph-¬ng  
Ph-¬ng ph¸p b¨m l¹i tèt h¬n, cho phÐp ta tr¸nh ®-îc sù tÝch tô trong  
b¶ng c¸c gi¸ trÞ xung quanh c¸c gi¸ trÞ ®-a vµo b¶ng ban ®Çu, lµ sö dông c¸c  
hµm b¨m l¹i ®-îc x¸c ®Þnh nh- sau :  
h i (x) = (h (x) + i2) mod N;  
H¹n chÕ cña ph-¬ng ph¸p nµy lµ ë chç, c¸c gi¸ trÞ b¨m l¹i kh«ng lÊy  
®Çy tÊt c¶ c¸c chØ sè cña m¶ng. Do ®ã khi cÇn ®-a vµo b¶ng mét gi¸ trÞ míi,  
cã thÓ ta kh«ng t×m ®-îc vÞ trÝ rçng, mÆc dÇu trong b¶ng h·y cßn c¸c vÞ trÝ  
rçng.  
XÐt tr-êng hîp chiÒu cña m¶ng N lµ sè nguyªn tè. Gi¶ sö víi i j ta cã  
h i (x) = h j (x)  
hay  
h (x) + i2 h (x) + j2 (mod N)  
Do ®ã  
(i - j) (i +j) 0 (mod N)  
V× N lµ sè nguyªn tè, ta suy ra, mét trong hai nh©n thøc i -j vµ i + j  
ph¶i chia hÕt cho N. Do ®ã hoÆc i N/2 hoÆc j N/2. Tõ ®ã ta suy ra, víi i ®i  
tõ 1 ®Õn N div 2 tÊt c¶ c¸c gi¸ trÞ b¨m l¹i ®Òu kh¸c nhau. Nh- vËy cã tÊt c¶ N  
div 2 gi¸ trÞ b¨m l¹i kh¸c nhau. Tøc lµ, khi gÆp va ch¹m, ph-¬ng ph¸p b¨m l¹i  
b×nh ph-¬ng sÏ cho phÐp t×m ®Õn mét nöa sè vÞ trÝ trong b¶ng. ViÖc t×m ®Õn  
mét nöa sè vÞ trÝ cña b¶ng ®Ó t×m ra mét vÞ trÝ trèng, trªn thùc tÕ, lµ Ýt khi cÇn  
®Õn, trõ tr-êng hîp b¶ng ®· gÇn ®Çy.  
Trong c¸c ph-¬ng ph¸p b¨m l¹i trªn, thùc chÊt ta ®· thªm vµo gi¸ trÞ  
b¨m ban ®Çu h (x) mét gia sè (i) ®Ó nhËn ®-îc gi¸ trÞ b¨m l¹i ë lÇn thø i.  
h i (x) = (h (x) + (i)) mod N  
Trong tr-êng hîp b¨m l¹i tuyÕn tÝnh (i) = i, cßn trong tr-êng hîp  
b¨m l¹i b×nh ph-¬ng (i) = i2.  
Cßn cã thÓ sö dông c¸c hµm gia sè kh¸c ®Ó nhËn ®-îc c¸c gi¸ trÞ b¨m  
l¹i. Ch¼ng h¹n, (i) = c i, trong ®ã c h»ng sè > 1.  
h i (x) = (h (x) + c i) mod N.  
VÝ dô, víi N = 8, c= 3 vµ h (x) = 4, c¸c vÞ trÝ trong b¶ng ®-îc t×m ®Õn  
lµ 4, 7, 2, 5, 0, 3, 6 vµ 1. TÊt nhiªn, nÕu N vµ c cã -íc chung lín h¬n 1, th×  
16  
ph-¬ng ph¸p b¨m l¹i nµy kh«ng cho ta t×m ®Õn tÊt c¶ c¸c vÞ trÝ trong b¶ng;  
ch¼ng h¹n víi N = 8 vµ c = 2.  
Mét c¸ch tiÕp cËn kh¸c lµ sö dông c¸c gia sè lµ c¸c sè ngÉu nhiªn :  
h i (x) = (h (x) + di) mod N  
trong ®ã, d1, d2, ... d  
lµ mét ho¸n vÞ ngÉu nhiªn cña c¸c sè 1, 2, ... N-1.  
N-1  
CÇn l-u ý r»ng, khi ®· chän mét d·y ngÉu nhiªn d1, d2, ..... d N-1, th× trong mäi  
phÐp to¸n t×m kiÕm, xen vµo vµ lo¹i bá, nÕu gÆp va ch¹m, ta ph¶i sö dông  
cïng mét d·y ngÉu nhiªn ®· chän ®Ó tÝnh c¸c gi¸ trÞ b¨m l¹i.  
C¸c phÐp to¸n tõ ®iÓn trªn b¶ng b¨m ®ãng.  
Sau ®©y chóng ta sÏ xÐt c¸c phÐp to¸n tõ ®iÓn (Insert, Delete, Member)  
khi tõ ®iÓn ®-îc cµi ®Æt bëi b¶ng b¨m ®ãng.  
§Ó biÕt trong b¶ng cã chøa kho¸ x hay kh«ng, ta ph¶i " th¨m dß" lÇn  
l-ît c¸c vÞ trÝ h (x), h1 (x), h2 (x)... Gi¶ sö ta ch-a thùc hiÖn phÐp lo¹i bá nµo  
®èi víi b¶ng. Khi ®ã cã hai kh¶ n¨ng. HoÆc lµ t×m ®-îc mét vÞ trÝ cña b¶ng  
chøa x, hoÆc lµ t×m ®-îc mét vÞ trÝ trèng ®Çu tiªn hk (x). Trong tr-êng hîp thø  
hai, ta cã thÓ kÕt luËn r»ng, b¶ng kh«ng chøa x, v× x kh«ng thÓ ®-îc ®Æt vµo  
mét trong c¸c vÞ trÝ hk+1 (x), hk+2 (x), tuy nhiªn t×nh h×nh sÏ kh¸c, nÕu trong  
b¶ng ®· thùc hiÖn mét sè lÇn lo¹i bá. Trong tr-êng hîp ®· cã sù lo¹i bá trong  
b¶ng, nÕu t×m ra vÞ trÝ trèng ®Çu tiªn hk (x) ta kh«ng thÓ ®¶m b¶o r»ng x  
kh«ng ë ®©u ®ã trong c¸c vÞ trÝ h k+1 (x), h k+2 (x), ... V× r»ng cã thÓ lóc ®-a x  
vµ b¶ng, vÞ trÝ hk (x) ®· ®Çy, nh-ng sau ®ã nã trë thµnh trèng bëi mét phÐp  
lo¹i bá nµo ®ã.  
§Ó ®¶m b¶o r»ng, khi t×m ra vÞ trÝ trèng ®Çu tiªn hk (x), ta cã thÓ tin  
ch¾c r»ng b¶ng kh«ng chøa x, ta ®-a vµo mét h»ng míi "bÞ lo¹i bá" (deleted)  
kh¸c víi h»ng "trèng" (empty). Víi viÖc ®-a vµo h»ng deleted, mçi khi cÇn  
lo¹i bá mét gi¸ trÞ khái mét vÞ trÝ nµo ®ã trong b¶ng, ta chØ cÇn thay gi¸ trÞ  
cña b¶ng t¹i vÞ trÝ ®ã bëi h»ng deleted. Khi cÇn ®-a mét gi¸ trÞ míi vµo b¶ng,  
ta cã thÓ ®Æt nã vµo vÞ trÝ ®· lo¹i bá.  
Ta cã thÓ khai b¸o cÊu tróc d÷ liÖu b¶ng b¨m ®ãng biÓu diÔn tõ ®iÓn  
nh- sau :  
const  
N
= . . . ;  
empty = . . . ;  
deleted = . . . ;  
{empty vµ deleted lµ hai h»ng kh¸c víi tÊt c¶ c¸c gi¸ trÞ kho¸ cña c¸c  
phÇn tö cña tõ ®iÓn}.  
type Dictionary = array [ 0 .. N-1] of keytype;  
17  
var  
T : Dictionary;  
Víi mçi gi¸ trÞ kho¸ x, ®Ó thùc hiÖn c¸c phÐp to¸n Insert, Delete,  
Member, ta ®Òu ph¶i x¸c ®Þnh vÞ trÝ trong b¶ng cã chøa x, hoÆc vÞ trÝ trong  
b¶ng cÇn ®Æt x vµo. T- t-ëng ®Ó t×m ra c¸c vÞ trÝ ®ã lµ th¨m dß lÇn l-ît c¸c vÞ  
trÝ h (x), h1 (x), h2 (x), .... §iÒu ®ã ®-îc thùc hiÖn bëi thñ tôc Location.  
Sau ®©y ta sÏ m« t¶ thñ tôc Location trong tr-êng hîp sö dông ph-¬ng  
ph¸p b¨m l¹i tuyÕn tÝnh.  
Víi mçi gi¸ trÞ kho¸ x, thñ tôc nµy cho phÐp th¨m dß c¸c vÞ trÝ trong  
b¶ng, xuÊt ph¸t tõ vÞ trÝ ®-îc x¸c ®Þnh bëi gi¸ trÞ b¨m h (x), råi lÇn l-ît qua  
c¸c vÞ trÝ h1 (x), h2 (x), ... cho tíi khi hoÆc t×m ®-îc vÞ trÝ cã chøa x, hoÆc t×m  
ra vÞ trÝ trèng ®Çu tiªn.  
Qu¸ tr×nh th¨m dß còng sÏ dõng l¹i nÕu ®i qua toµn bé b¶ng mµ kh«ng  
thµnh c«ng (kh«ng t×m thÊy vÞ trÝ chøa x còng kh«ng t×m thÊy vÞ trÝ trèng). VÞ  
trÝ mµ t¹i ®ã qu¸ tr×nh th¨m dß dõng l¹i ®-îc ghi vµo tham biÕn k. Ta ®-a vµo  
thñ tôc tham biÕn j ®Ó ghi l¹i vÞ trÝ lo¹i bá (deleted) ®Çu tiªn hoÆc vÞ trÝ trèng  
®Çu tiªn mµ qu¸ tr×nh th¨m dß ph¸t hiÖn ra, nÕu trong b¶ng cßn cã c¸c vÞ trÝ  
nh- thÕ.  
procedure Location (x : keytype; var k, j : integer);  
var  
i
: integer;  
{biÕn i ghi l¹i gi¸ trÞ b¨m ®Çu tiªn h (x)}  
begin  
i
j
: = h (x);  
: = i;  
if (T [i] = x) or (T [i] = empty) then  
k : = i else  
begin  
k = (i + 1) mod N;  
while (k < > i) and ( T [k] < > x) and  
(T [k] < > empty) do  
begin  
if (T [k] = deleted) and (T [j] < > deleted)  
then j : = k;  
k : = (k +1) mod N  
end;  
if (T [k] = empty) and (T [j] < > deleted)  
18  
then j : = k  
end;  
end;  
Sau ®©y ta sÏ m« t¶ c¸c thñ tôc vµ hµm thùc hiÖn c¸c phÐp to¸n tõ ®iÓn  
function Member (x : keytype; var T : Dictionary) : boolean;  
var k, j : integer;  
begin  
Location (x, k, j)  
if T [k] = x then Member : = true  
else Member : = false  
end;  
procedure Insert (x : keytype; var T : Dictionary);  
var k, j : integer;  
begin  
Location (x, k, j);  
if T [k] < > x then  
if (T [j] = deleted) or (T[j] = empty) then T [j] := x  
else writeln (' b¶ng ®Çy')  
else writeln (' b¶ng ®· cã x')  
end;  
procedure  
Delete (x : keytype; var T : Dictionary);  
var k, j : integer;  
begin  
Location (x, k, j);  
if T [k] = x then T [k] : = deleted;  
19  
Tải về để xem bản đầy đủ
doc 33 trang baolam 15780 Free
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 5: Tập hợp", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

  • docbai_giang_cau_truc_du_lieu_va_giai_thuat_chuong_5_tap_hop.doc