Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 2: Kiểu dữ liệu, cấu trúc dữ liệu và mô hình dữ liệu
Ch-¬ng II
kiÓu d÷ liÖu, cÊu tróc d÷ liÖu vµ
m« h×nh d÷ liÖu
2.1. BiÓu diÔn d÷ liÖu.
Trong m¸y tÝnh ®iÖn tö (MT§T), c¸c d÷ liÖu dï cã b¶n chÊt kh¸c nhau
nh- thÕ nµo (sè nguyªn, sè thùc, hay x©u ký tù, ...), ®Òu ®-îc biÓu diÔn d-íi
d¹ng nhÞ ph©n. Mçi d÷ liÖu ®-îc biÓu diÔn d-íi d¹ng mét d·y c¸c sè nhÞ ph©n
0 hoÆc 1. VÒ mÆt kü thuËt ®©y lµ c¸ch biÓu diÔn thÝch hîp nhÊt, v× c¸c gi¸ trÞ 0
vµ 1 dÔ dµng ®-îc m· ho¸ bëi c¸c phÇn tö vËt lý chØ cã hai tr¹ng th¸i. Chóng
ta sÏ kh«ng quan t©m ®Õn c¸ch biÓu diÔn nµy cña d÷ liÖu, còng nh- c¸c c¸ch
tiÕn hµnh c¸c thao t¸c, c¸c phÐp to¸n trªn c¸c d÷ liÖu ®-îc biÓu diÔn d-íi
d¹ng nhÞ ph©n.
C¸ch biÓu diÔn nhÞ ph©n cña d÷ liÖu rÊt kh«ng thuËn tiÖn ®èi víi con
ng-êi. ViÖc xuÊt hiÖn c¸c ng«n ng÷ lËp tr×nh bËc cao (FORTRAN, BASIC,
PASSCAL, C ...) ®· gi¶i phãng con ng-êi khái nh÷ng khã kh¨n khi lµm viÖc
víi c¸ch biÓu diÔn trong m¸y cña d÷ liÖu. Trong c¸c ng«n ng÷ lËp tr×nh bËc
cao, c¸c d÷ liÖu, hiÓu theo mét nghÜa nµo ®ã, lµ sù tr×u t-îng ho¸ c¸c tÝnh chÊt
cña c¸c ®èi t-îng trong thÕ giíi hiÖn thùc. Nãi d÷ liÖu lµ sù tr×u t-îng ho¸ tõ
thÕ giíi hiÖn thùc, v× ta ®· bá qua nh÷ng nh©n tè, tÝnh chÊt mµ ta cho lµ kh«ng
c¬ b¶n, chØ gi÷ l¹i nh÷ng tÝnh chÊt ®Æc tr-ng cho c¸c ®èi t-îng thuéc ph¹m vi
bµi to¸n ®ang xÐt. Ch¼ng h¹n, vÞ trÝ cña mét ®èi t-îng trong thùc tiÔn, ®-îc
®Æc tr-ng bëi cÆp sè thùc (x,y) (®ã lµ to¹ ®o¹ ®ª-c¸c cña mét ®iÓm trong mÆt
ph¼ng). Do ®ã, trong ng«n ng÷ Pascal, vÞ trÝ mét ®èi t-îng ®-îc biÓu diÔn bëi
b¶n ghi gåm hai tr-êng t-¬ng øng víi hoµnh ®é vµ tung ®é cña mét ®iÓm.
Trong to¸n häc cã c¸c kh¸i niÖm biÓu diÔn ®Æc tr-ng vÒ mÆt sè l-îng vµ c¸c
quan hÖ cña c¸c ®èi t-îng trong thÕ giíi hiÖn thùc, ®ã lµ c¸c kh¸i niÖm sè
nguyªn, sè thùc, sè phøc, d·y, ma trËn, ... Trªn c¬ së c¸c kh¸i niÖm to¸n häc
nµy, ng-êi ta ®· ®-a vµo trong c¸c ng«n ng÷ lËp tr×nh bËc cao c¸c d÷ liÖu kiÓu
nguyªn, thùc, phøc, m¶ng, b¶n ghi, ... Tuy nhiªn do tÝnh ®a d¹ng cña c¸c bµi
to¸n cÇn xö lý b»ng MT§T, chØ sö dông c¸c kiÓu d÷ liÖu cã s½n trong c¸c
ng«n ng÷ lËp tr×nh bËc cao lµ ch-a ®ñ ®Ó m« t¶ c¸c bµi to¸n. Chóng ta ph¶i
cÇn ®Õn c¸c cÊu tróc d÷ liÖu. §ã lµ c¸c d÷ liÖu phøc t¹p, ®-îc x©y dùng nªn
tõ c¸c d÷ liÖu ®· cã, ®¬n gi¶n h¬n b»ng c¸c ph-¬ng ph¸p liªn kÕt nµo ®ã.
§Ó gi¶i quyÕt mét bµi to¸n b»ng MT§T, ta cÇn x©y dùng m« h×nh d÷
liÖu m« t¶ bµi to¸n. §ã lµ sù tr×u t-îng ho¸ c¸c ®Æc tr-ng cña c¸c ®èi t-îng
thuéc ph¹m vi vÊn ®Ò mµ ta quan t©m, c¸c mèi quan hÖ gi÷a c¸c ®èi t-îng ®ã.
Dïng lµm c¸c m« h×nh d÷ liÖu trong tin häc, chóng ta sÏ sö dông c¸c m« h×nh
to¸n häc nh- danh s¸ch, c©y, tËp hîp, ¸nh x¹, quan hÖ, ®å thÞ, ... M« h×nh d÷
liÖu sÏ ®-îc biÓu diÔn bëi c¸c cÊu tróc d÷ liÖu. Th«ng th-êng mét m« h×nh d÷
liÖu cã thÓ ®-îc biÓu hiÖn bëi nhiÒu cÊu tróc d÷ liÖu kh¸c nhau. Tuú tõng øng
0
dông, ta sÏ chän cÊu tróc d÷ liÖu nµo mµ c¸c thao t¸c cÇn thùc hiÖn lµ hiÖu
qu¶ nhÊt cã thÓ ®-îc.
2.2. KiÓu d÷ liÖu vµ cÊu tróc d÷ liÖu.
Trong c¸c ng«n ng÷ lËp tr×nh bËc cao, c¸c d÷ liÖu ®-îc ph©n líp thµnh
c¸c líp d÷ liÖu dùa vµo b¶n chÊt cña d÷ liÖu. Mçi mét líp d÷ liÖu ®-îc gäi lµ
mét kiÓu d÷ liÖu. Nh- vËy, mét kiÓu T lµ mét tËp hîp nµo ®ã, c¸c phÇn tö cña
tËp ®-îc gäi lµ c¸c gi¸ trÞ cña kiÓu. Ch¼ng h¹n, kiÓu integer lµ tËp hîp c¸c sè
nguyªn, kiÓu char lµ mét tËp h÷u h¹n c¸c ký hiÖu. C¸c ng«n ng÷ lËp tr×nh
kh¸c nhau cã thÓ cã c¸c kiÓu d÷ liÖu kh¸c nhau. Fortran cã c¸c kiÓu d÷ liÖu lµ
integer, real, logical, complex vµ double complex. C¸c kiÓu d÷ liÖu trong
ng«n ng÷ C lµ int, float, char, con trá, struct..., KiÓu d÷ liÖu trong ng«n ng÷
Lisp l¹i lµ c¸c S-biÓu thøc. Mét c¸ch tæng qu¸t, mçi ng«n ng÷ lËp tr×nh cã
mét hÖ kiÓu cña riªng m×nh. HÖ kiÓu cña mét ng«n ng÷ bao gåm c¸c kiÓu d÷
liÖu c¬ së vµ c¸c ph-¬ng ph¸p cho phÐp ta tõ c¸c kiÓu d÷ liÖu ®· cã x©y dùng
nªn c¸c kiÓu d÷ liÖu míi.
Khi nãi ®Õn mét kiÓu d÷ liÖu, chóng ta cÇn ph¶i ®Ò cËp ®Õn hai ®Æc
tr-ng sau ®©y :
1. TËp hîp c¸c gi¸ trÞ thuéc kiÓu. Ch¼ng h¹n, kiÓu integer trong ng«n
ng÷ Pascal gåm tÊt c¶ c¸c sè nguyªn ®-îc biÓu diÔn bëi hai byte, tøc lµ gåm
c¸c sè nguyªn tõ -32768 ®Õn + 32767. Trong c¸c ng«n ng÷ lËp tr×nh bËc cao
mçi h»ng, biÕn, biÓu thøc hoÆc hµm cÇn ph¶i ®-îc g¾n víi mét kiÓu d÷ liÖu
x¸c ®Þnh. Khi ®ã, mçi biÕn (biÓu thøc, hµm) chØ cã thÓ nhËn c¸c gi¸ trÞ thuéc
kiÓu cña biÕn (biÓu thøc, hµm) ®ã.
VÝ dô , nÕu X lµ biÕn cã kiÓu boolean trong Pascal (var X : boolean)
th× X chØ cã thÓ nhËn mét trong hai gi¸ trÞ true, false.
2. Víi mçi kiÓu d÷ liÖu, cÇn ph¶i x¸c ®Þnh mét tËp hîp nµo ®ã c¸c phÐp
to¸n cã thÓ thùc hiÖn ®-îc trªn c¸c d÷ liÖu cña kiÓu. Ch¼ng h¹n, víi kiÓu real,
c¸c phÐp to¸n cã thÓ thùc hiÖn ®-îc lµ c¸c phÐp to¸n sè häc th«ng th-êng +, -
, *, / , vµ c¸c phÐp to¸n so s¸nh = , < >, < , < =, >, > =.
Th«ng th-êng trong mét hÖ kiÓu cña mét ng«n ng÷ lËp tr×nh sÏ cã mét
sè kiÓu d÷ liÖu ®-îc gäi lµ kiÓu d÷ liÖu ®¬n hay kiÓu d÷ liÖu ph©n tö (atomic).
Ch¼ng h¹n, trong ng«n ng÷ Pascal, c¸c kiÓu d÷ liÖu integer, real,
boolean , char vµ c¸c kiÓu liÖt kª ®-îc gäi lµ c¸c kiÓu d÷ liÖu ®¬n. Së dÜ gäi
lµ ®¬n, v× c¸c gi¸ trÞ cña c¸c kiÓu nµy ®-îc xem lµ c¸c ®¬n thÓ ®¬n gi¶n nhÊt
kh«ng thÓ ph©n tÝch thµnh c¸c thµnh phÇn ®¬n gi¶n h¬n ®-îc n÷a.
Nh- ®· nãi, khi gi¶i quyÕt c¸c bµi to¸n phøc t¹p, chØ sö dông c¸c d÷
liÖu ®¬n lµ kh«ng ®ñ, ta ph¶i cÇn ®Õn c¸c cÊu tróc d÷ liÖu. Mét cÊu tróc d÷
liÖu bao gåm mét tËp hîp nµo ®ã c¸c d÷ liÖu thµnh phÇn, c¸c d÷ liÖu thµnh
1
phÇn nµy ®-îc liªn kÕt víi nhau bëi mét ph-¬ng ph¸p nµo ®ã. C¸c d÷ liÖu
thµnh phÇn cã thÓ lµ d÷ liÖu ®¬n, hoÆc còng cã thÓ lµ mét cÊu tróc d÷ liÖu ®·
®-îc x©y dùng. Cã thÓ h×nh dung mét cÊu tróc d÷ liÖu ®-îc t¹o nªn tõ c¸c tÕ
bµo (khèi x©y dùng), mçi tÕ bµo cã thÓ xem nh- mét c¸i hép chøa d÷ liÖu
thµnh phÇn.
Trong Pascal vµ trong nhiÒu ng«n ng÷ th«ng dông kh¸c cã mét c¸ch
®¬n gi¶n nhÊt ®Ó liªn kÕt c¸c tÕ bµo, ®ã lµ s¾p xÕp c¸c tÕ bµo chøa c¸c d÷ liÖu
cïng mét kiÓu thµnh mét d·y. Khi ®ã ta cã mét cÊu tróc d÷ liÖu ®-îc gäi lµ
m¶ng (array). Nh- vËy, cã thÓ nãi, mét m¶ng lµ mét cÊu tróc d÷ liÖu gåm mét
d·y x¸c ®Þnh c¸c d÷ liÖu thµnh phÇn cïng mét kiÓu. Ta vÉn th-êng nãi ®Õn
m¶ng c¸c sè nguyªn, m¶ng c¸c sè thùc, m¶ng c¸c b¶n ghi, ... Mçi mét d÷ liÖu
thµnh phÇn cña m¶ng ®-îc g¾n víi mét chØ sè tõ mét tËp chØ sè nµo ®ã. Ta cã
thÓ truy cËp ®Õn mét thµnh phÇn nµo ®ã cña m¶ng b»ng c¸ch chØ ra tªn m¶ng
vµ chØ sè cña thµnh phÇn ®ã.
Mét ph-¬ng ph¸p kh¸c ®Ó t¹o nªn c¸c cÊu tróc d÷ liÖu míi, lµ kÕt hîp
mét sè tÕ bµo (cã thÓ chøa c¸c d÷ liÖu cã kiÓu kh¸c nhau) thµnh mét b¶n ghi
(record). C¸c tÕ bµo thµnh phÇn cña b¶n ghi ®-îc gäi lµ c¸c tr-êng cña b¶n
ghi. C¸c b¶n ghi ®Õn l-ît l¹i ®-îc sö dông lµm c¸c tÕ bµo ®Ó t¹o nªn c¸c cÊu
tróc d÷ liÖu kh¸c. Ch¼ng h¹n, mét trong c¸c cÊu tróc d÷ liÖu hay ®-îc sö
dông nhÊt lµ m¶ng c¸c b¶n ghi.
Cßn mét ph-¬ng ph¸p quan träng n÷a ®Ó kiÕn t¹o c¸c cÊu tróc d÷ liÖu,
®ã lµ sö dông con trá. Trong ph-¬ng ph¸p nµy, mçi tÕ bµo lµ mét b¶n ghi gåm
hai phÇn INFOR vµ LINK, phÇn INFOR cã thÓ cã mét hay nhiÒu tr-êng d÷
liÖu, cßn phÇn LINK cã thÓ chøa mét hay nhiÒu con trá trá ®Õn c¸c tÕ bµo
kh¸c cã quan hÖ víi tÕ bµo ®ã. Ch¼ng h¹n, ta cã thÓ cµi ®Æt mét danh s¸ch bëi
cÊu tróc d÷ liÖu danh s¸ch liªn kÕt, trong ®ã mçi thµnh phÇn cña danh s¸ch
liªn kÕt lµ b¶n ghi gåm hai tr-êng
type Cell = record
element : Item ;
next : Cell ;
end ;
ë ®©y, tr-êng element cã kiÓu d÷ liÖu Item, mét kiÓu d÷ liÖu nµo ®ã
cña c¸c phÇn tö cña danh s¸ch. Tr-êng next lµ con trá trá tíi phÇn tö tiÕp theo
trong danh s¸ch. CÊu tróc d÷ liÖu danh s¸ch liªn kÕt biÓu diÔn danh s¸ch (a1,
a2,...., an) cã thÓ ®-îc biÓu diÔn nh- trong h×nh 2.1
2
H×nh 2.1 : cÊu tróc d÷ liÖu danh s¸ch liªn kÕt.
Sö dông con trá ®Ó liªn kÕt c¸c tÕ bµo lµ mét trong c¸c ph-¬ng ph¸p
kiÕn t¹o c¸c cÊu tróc d÷ liÖu ®-îc ¸p dông nhiÒu nhÊt. Ngoµi danh s¸ch liªn
kÕt, ng-êi ta cßn dïng c¸c con trá ®Ó t¹o ra c¸c cÊu tróc d÷ liÖu biÓu diÔn c©y,
mét m« h×nh d÷ liÖu quan träng bËc nhÊt.
Trªn ®©y chóng ta ®· nªu ba ph-¬ng ph¸p chÝnh ®Ó kiÕn t¹o c¸c cÊu
tróc d÷ liÖu. (ë ®©y chóng ta chØ nãi ®Õn c¸c cÊu tróc d÷ liÖu trong bé nhí
trong, c¸c cÊu tróc d÷ liÖu ë bé nhí ngoµi nh- file chØ sè, B-c©y sÏ ®-îc ®Ò
cËp riªng.)
Mét kiÓu d÷ liÖu mµ c¸c gi¸ trÞ thuéc kiÓu kh«ng ph¶i lµ c¸c d÷ liÖu
®¬n mµ lµ c¸c cÊu tróc d÷ liÖu ®-îc gäi lµ kiÓu d÷ liÖu cã cÊu tróc. Trong
ng«n ng÷ Pascal, c¸c kiÓu d÷ liÖu m¶ng, b¶n ghi, tËp hîp, file ®Òu lµ c¸c kiÓu
d÷ liÖu cã cÊu tróc.
2.3 HÖ kiÓu cña ng«n ng÷ Pascal.
Pascal lµ mét trong c¸c ng«n ng÷ cã hÖ kiÓu phong phó nhÊt. HÖ kiÓu
cña Pascal chøa c¸c kiÓu c¬ së, integer, real, boolean, char vµ c¸c quy t¾c,
dùa vµo ®ã ta cã thÓ x©y dùng nªn c¸c kiÓu phøc t¹p h¬n tõ c¸c kiÓu ®· cã. Tõ
c¸c kiÓu c¬ së vµ ¸p dông c¸c quy t¾c, ta cã thÓ x©y dùng nªn mét tËp hîp v«
h¹n c¸c kiÓu. HÖ kiÓu cña Pascal cã thÓ ®-îc ®Þnh nghÜa ®Þnh quy nh- sau :
A. C¸c kiÓu c¬ së
1. KiÓu integer
2. KiÓu real
3. KiÓu boolean
4. KiÓu char
5. KiÓu liÖt kª
Gi¶ sö obj1, obj2,.... objn lµ c¸c ®èi t-îng nµo ®ã. khi ®ã ta cã thÓ t¹o
nªn kiÓu liÖt kª T b»ng c¸ch liÖt kª ra tÊt c¶ c¸c ®ãi t-îng ®ã.
Chó ý. TÊt c¶ c¸c kiÓu ®¬n ®Òu lµ c¸c kiÓu cã thø tù, tøc lµ víi hai gi¸
trÞ bÊt kú a vµ b thuéc cïng mét kiÓu, ta lu«n cã a b hoÆc a b. trõ kiÓu
real, c¸c kiÓu cßn l¹i ®Òu lµ kiÓu cã thø tù ®Õm ®-îc.
6. KiÓu ®o¹n con
3
Trong ®ã min vµ max lµ cËn d-íi vµ cËn trªn cña kho¶ng ; min vµ max
lµ c¸c gi¸ trÞ thuéc cïng mét kiÓu integer, char, hoÆc c¸c kiÓu liÖt kª, ®ång
thêi min max. KiÓu T gåm tÊt c¶ c¸c gi¸ trÞ tõ min ®Õn max.
B. C¸c quy t¾c ®Ö quy.
Trong Pascal, chóng ta cã thÓ t¹o ra c¸c kiÓu míi b»ng c¸ch sö dông
c¸c quy t¾c sau.
7. KiÓu array (m¶ng)
Gi¶ sö T0 lµ mét kiÓu ®· cho, ta sÏ gäi T0 lµ kiÓu thµnh phÇn m¶ng.
Gi¶ sö I lµ kiÓu ®o¹n con hoÆc kiÓu liÖt kª, ta sÏ gäi I lµ kiÓu chØ sè m¶ng.
Khi ®ã ta cã thÓ t¹o nªn kiÓu m¶ng T víi c¸c thµnh phÇn cña m¶ng lµ c¸c gi¸
trÞ thuéc T0 vµ ®-îc chØ sè ho¸ bëi tËp h÷u h¹n, cã thø tù I.
8. KiÓu record (b¶n ghi)
Gi¶ sö T1, T2,... .Tn lµ c¸c kiÓu ®· cho, vµ F1, F2, ....Fn lµ c¸c tªn (tªn
tr-êng). Khi ®ã ta cã thÓ thµnh lËp mét kiÓu b¶n ghi T víi n tr-êng, tr-êng
thø i cã tªn lµ Fi vµ c¸c gi¸ trÞ cña nã cã kiÓu Ti víi i = 1, 2,...n.
Mçi gi¸ trÞ cña kiÓu b¶n ghi T lµ mét bé n gi¸ trÞ (t1, t2, ....tn), trong ®ã
ti thuéc Ti víi i = 1, 2,..., n.
9. KiÓu con trá
Gi¶ sö T lµ mét kiÓu ®· cho. Khi ®ã ta cã thÓ t¹o nªn kiÓu con trá Tp.
4
C¸c gi¸ trÞ cña Tp lµ ®Þa chØ (vÞ trÝ) trong bé nhí cña m¸y tÝnh ®Ó l-u
gi÷ c¸c ®èi t-îng thuéc kiÓu T. Chóng ta sÏ biÓu diÔn mét con trá p (var p:^T)
bëi vßng trßn nhá cã mòi tªn chØ ®Õn ®èi t-îng thuéc kiÓu T (h×nh 2.2)
p
H×nh 2.2 : BiÓu diÔn con trá.
10. KiÓu set (tËp hîp)
Gi¶ sö T0 lµ mét kiÓu ®· cho. T0 ph¶i lµ kiÓu cã thø tù ®Õm ®-îc "®ñ
nhá", ch¼ng h¹n kiÓu ®o¹n con (giíi h¹n phô thuéc vµo ch-¬ng tr×nh dÞch).
Khi dã, ta cã thÓ x¸c ®Þnh kiÓu tËp T
Mçi ®èi t-îng cña kiÓu T sÏ lµ mét tËp con cña t©p T0.
11. KiÓu file (tÖp)
Gi¶ sö T0lµ mét kiÓu nµo ®ã (trõ kiÓu file).
Khi ®ã,
sÏ x¸c ®Þnh mét kiÓu file víi c¸c phÇn tö lµ c¸c ®èi t-îng thuéc kiÓu T0
VÝ dô. Sau ®©y lµ ®Þnh nghÜa mét sè kiÓu d÷ liÖu
type Color = (white, red, blue, yellow, green) ;
Intarr = array [1 ...10] of integer,
Rec = record
Infor : color
ptr : Intarr ;
end ;
Recarr = array [1 ... 5] of Rec ;
5
BiÓu diÔn h×nh häc cña mét ®èi t-îng thuéc kiÓu Recarr ®-îc cho
trong h×nh 2.3.
1
9
2
0
3
9
10
13
1
red
.
.
.
.
.
.
.
.
.
2 yellow
1
5
2
3
9
10
37
3
red
21
4 blue
5 blue
1
.
2
.
3
.
10
H×nh 2.3 : CÊu tróc d÷ liÖu Recarr.
C¸c phÐp to¸n trong hÖ kiÓu Pascal
Nh- ®· nãi víi mçi kiÓu d÷ liÖu ta chØ cã thÓ thùc hiÖn mét sè phÐp
to¸n nhÊt ®Þnh trªn c¸c d÷ liÖu cña kiÓu. Ta kh«ng thÓ ¸p dông mét phÐp to¸n
trªn c¸c d÷ liÖu thuéc kiÓu nµy cho c¸c d÷ liÖu cã kiÓu kh¸c. Ta cã thÓ ph©n
tËp hîp c¸c phÐp to¸n trªn c¸c kiÓu d÷ liÖu cña Pascal thµnh hai líp sau :
A. C¸c phÐp to¸n truy cËp ®Õn c¸c thµnh phÇn cña mét ®èi t-îng d÷
liÖu, ch¼ng h¹n truy cËp ®Õn c¸c thµnh phÇn cña mét m¶ng, ®Õn c¸c tr-êng
cña mét b¶n ghi.
Gi¶ sö A lµ mét m¶ng víi tËp chØ sè I, khi ®ã A[i] cho phÐp ta truy cËp
®Õn thµnh phÇn thø i cña m¶ng. Cßn nÕu X lµ mét b¶n ghi th× viÖc truy cËp
®Õn tr-êng F cña nã ®-îc thùc hiÖn bëi phÐp to¸n X.F.
B. C¸c phÐp to¸n kÕt hîp d÷ liÖu.
Pascal cã mét tËp hîp phong phó c¸c phÐp to¸n kÕt hîp mét hoÆc nhiÒu
d÷ liÖu ®· cho thµnh mét d÷ liÖu míi. Sau ®©y lµ mét sè nhãm c¸c phÐp to¸n
chÝnh.
6
1. C¸c phÐp to¸n sè häc. §ã lµ c¸c phÐp to¸n + , -, * , / trªn c¸c sè thùc
; c¸c phÐp to¸n +, - *, /, div, mod trªn c¸c sè nguyªn.
2. C¸c phÐp to¸n so s¸nh. Trªn c¸c ®èi t-îng thuéc c¸c kiÓu cã thø tù
(®ã lµ c¸c kiÓu c¬ së vµ kiÓu tËp), ta cã thÓ thùc hiÖn c¸c phÐp to¸n so s¸nh =,
< >, <, <=, >, >=. CÇn l-u ý r»ng, kÕt qu¶ cña c¸c phÐp to¸n nµy lµ mét gi¸ trÞ
kiÓu boolaen (tøc lµ true hoÆc false).
3. C¸c phÐp to¸n logic. §ã lµ c¸c phÐp to¸n and, or, not ®-îc thùc hiÖn
trªn hai gi¸ trÞ false vµ truc cña kiÓu boolean.
4. C¸c phÐp to¸n tËp hîp. C¸c phÐp to¸n hîp, giao, hiÖu cña c¸c tËp
hîp trong pascal ®-îc biÓu diÔn bëi +, *, - t-¬ng øng. ViÖc kiÓm tra mét ®èi
t-îng x cã lµ phÇn tö cña tËp A hay kh«ng ®-îc thùc hiÖn bëi phÐp to¸n x in
A. KÕt qu¶ cña phÐp to¸n nµy lµ mét gi¸ boolean.
2.4. M« h×nh d÷ liÖu vµ kiÓu d÷ liÖu trõu t-îng.
§Ó gi¶i quyÕt mét vÊn ®Ò trªn MT§T th«ng th-êng chóng ta cÇn ph¶i
qua mét sè giai ®o¹n chÝnh sau ®©y :
1. §Æt bµi to¸n
2. X©y dùng m« h×nh
3. ThiÕt kÕ thuËt to¸n vµ ph©n tÝch thuËt to¸n
4. ViÕt ch-¬ng tr×nh
5. Thö nghiÖm.
Chóng ta sÏ kh«ng ®i s©u ph©n tÝch tõng giai ®o¹n. Chóng ta chØ muèn
lµm s¸ng tá vai trß cña m« h×nh d÷ liÖu trong viÖc thiÕt kÕ ch-¬ng tr×nh. XÐt
vÝ dô sau.
VÝ dô. Mét ng-êi giao hµng, hµng ngµy anh ta ph¶i chuyÓn hµng tõ mét
thµnh phè ®Õn mét sè thµnh phè kh¸c råi l¹i quay vÒ thµnh phè xuÊt ph¸t.
VÊn ®Ò cña anh ta lµ lµm thÕ nµo cã ®-îc mét hµnh tr×nh chØ qua mçi thµnh
phè mét lÇn víi ®-êng ®i ng¾n nhÊt cã thÓ ®-îc.
Chóng ta thö gióp ng-êi giao hµng m« t¶ chÝnh x¸c bµi to¸n. Tr-íc hÕt,
ta cÇn tr¶ lêi c©u hái, nh÷ng th«ng tin ®· biÕt trong bµi to¸n ng-êi giao hµng
lµ g× ? §ã lµ tªn cña c¸c thµnh phè anh ta ph¶i ghÐ qua vµ ®é dµi c¸c con
®-êng cã thÓ cã gi÷a hai thµnh phè. Chóng ta cÇn t×m c¸i g× ? Mét hµnh tr×nh
mµ ng-êi giao hµng mong muèn lµ mét danh s¸ch c¸c thµnh phè A1,A2...An+1
(gi¶ sö cã n thµnh phè), trong ®ã c¸c A1 (i=1,2,...,n+1) ®Òu kh¸c nhau, trõ
An+1 = A1.
Víi mét vÊn ®Ò ®Æt ra tõ thùc tiÔn, ta cã thÓ m« t¶ chÝnh x¸c vÊn ®Ò ®ã
hoÆc c¸c bé phËn cña nã (vÊn ®Ò con) bëi mét m« h×nh to¸n häc nµo ®ã.
7
Ch¼ng h¹n, m« h×nh to¸n häc thÝch hîp nhÊt ®Ó m« t¶ bµi to¸n ng-êi giao
hµng lµ ®å thÞ. C¸c ®Ønh cña ®å thÞ lµ c¸c thµnh phè, c¸c c¹nh cña ®å thÞ lµ
c¸c ®-êng nèi hai thµnh phè. Träng sè cña c¸c c¹nh lµ ®é dµi c¸c ®-êng nèi
hai thµnh phè. Trong thuËt ng÷ cña lý thuyÕt ®å thÞ, danh s¸ch c¸c thµnh phè
biÓu diÔn hµnh tr×nh cña ng-êi giao hµng, lµ mét chu tr×nh qua tÊt c¶ c¸c ®Ønh
cña ®å thÞ. Nh- vËy, bµi to¸n ng-êi giao hµng ®-îc qui vÒ bµi to¸n trong lý
thuyÕt ®å thÞ. T×m mét chu tr×nh xuÊt ph¸t tõ mét ®Ønh qua tÊt c¶ c¸c ®Ønh cßn
l¹i víi ®é dµi ng¾n nhÊt.
Bµi to¸n ng-êi giao hµng lµ mét trong c¸c bµi to¸n ®· trë thµnh kinh
®iÓn. Nã dÔ m« h×nh ho¸, song còng rÊt khã gi¶i. Chóng ta sÏ quay l¹i bµi
to¸n nµy.
CÇn l-u ý r»ng, ®Ó t×m ra cÊu tróc to¸n häc thÝch hîp víi mét bµi to¸n
®· cho, chóng ta ph¶i ph©n tÝch kü bµi to¸n ®Ó t×m ra c©u tr¶ lêi cho c¸c c©u
hái sau.
C¸c th«ng tin quan träng cña bµi to¸n cã thÓ biÓu diÔn bëi c¸c ®èi
t-îng to¸n häc nµo ?
Cã c¸c mèi quan hÖ nµo gi÷a c¸c ®èi t-îng ?
C¸c kÕt qu¶ ph¶i t×m cña bµi to¸n cã thÓ biÓu diÔn bëi c¸c kh¸i niÖm
to¸n häc nµo.
Sau khi ®· cã m« h×nh to¸n häc m« t¶ bµi to¸n, mét c©u hái ®Æt ra lµ, ta
ph¶i lµm viÖc víi m« h×nh nh- thÕ nµo ®Ó t×m ra lêi gi¶i cña bµi to¸n ? Chóng
ta sÏ thiÕt kÕ thuËt to¸n th«ng qua c¸c hµnh ®éng, c¸c phÐp to¸n thùc hiÖn
trªn c¸c ®èi t-îng cña m« h×nh.
Mét m« h×nh to¸n häc cïng víi c¸c phÐp to¸n cã thÓ thùc hiÖn trªn c¸c
®èi t-îng cña m« h×nh ®-îc gäi lµ m« h×nh d÷ liÖu. Ch¼ng h¹n, trong m« h×nh
d÷ liÖu ®å thÞ, trong sè rÊt nhiÒu c¸c phÐp to¸n, ta cã thÓ kÓ ra mét sè phÐp
to¸n sau : t×m c¸c ®Ønh kÒ cña mçi ®Ønh, x¸c ®Þnh ®-êng ®i ng¾n nhÊt nèi hai
®Ønh bÊt kú, t×m c¸c thµnh phÇn liªn th«ng, t×m c¸c ®Ønh treo,.. VÒ mÆt to¸n
häc, danh s¸ch lµ mét d·y h÷u h¹n n phÇn tö (a1, a2, ..., an). Trong m« h×nh d÷
liÖu danh s¸ch, chóng ta còng cã thÓ thùc hiÖn mét tËp hîp rÊt ®a d¹ng c¸c
phÐp to¸n, ch¼ng h¹n nh-, x¸c ®Þnh ®é dµi cña danh s¸ch, xen mét phÇn tö
míi vµo danh s¸ch, lo¹i mét phÇn tõ nµo ®ã khái danh s¸ch, s¾p xÕp l¹i danh
s¸ch theo mét trËt tù nµo ®ã, gép hai danh s¸ch thµnh mét danh s¸ch.
Trë l¹i bµi to¸n ng-êi giao hµng. Cã nhiÒu thuËt to¸n gi¶i bµi to¸n nµy.
Ch¼ng h¹n, ta cã thÓ gi¶i b»ng ph-¬ng ph¸p vÐt c¹n : gi¶ sö cã n thµnh phè,
khi ®ã mçi hµnh tr×nh lµ mét ho¸n vÞ cña n-1 thµnh phè (trõ thµnh phè xuÊt
ph¸t), thµnh lËp (n-1)! ho¸n vÞ, tÝnh ®é dµi cña hµnh tr×nh øng víi mçi ho¸n vÞ
vµ so s¸nh, ta sÏ t×m ®-îc hµnh tr×nh ng¾n nhÊt. Ta còng cã thÓ gi¶i bµi to¸n
b»ng ph-¬ng ph¸p qui ho¹ch ®éng (Ph-¬ng ph¸p nµy sÏ ®-îc tr×nh bµy ë tËp
2 cña s¸ch nµy). Sau ®©y ta ®-a ra mét thuËt to¸n ®¬n gi¶n. ThuËt to¸n nµy
8
t×m ra rÊt nhanh nghiÖm "gÇn ®óng", trong tr-êng hîp cã ®-êng ®i nèi hai
thµnh phè bÊt kú. Gi¶ sö G lµ mét ®å thÞ (Graph), V lµ tËp hîp c¸c ®Ønh
(Node), E lµ tËp hîp c¸c c¹nh cña nã. Gi¶ sö c(u,v) lµ ®é dµi (nguyªn d-¬ng)
cña c¹nh (u,v). Hµnh tr×nh (Tour) cña ng-êi giao hµng cã thÓ xem nh- mét
tËp hîp nµo ®ã c¸c c¹nh. Cost lµ ®é dµi cña hµnh tr×nh. ThuËt to¸n ®-îc biÓu
diÔn bëi thñ tôc Salesperson.
procedure Salespersen (G : Graph ; var Tour : set of E ;
var cost : integer) ;
var v, w : Node
U : set of V ;
begin
Tour : = [ ] ;
Cost : = 0 ;
v : = vo ; {vo - ®Ønh xuÊt ph¸t}
U : = V - [vo] ;
while
begin
U < > [ ] do
Chän (v, w) lµ c¹nh ng¾n nhÊt víi w thuéc U ;
Tour : = Tour + [(v, w)] ;
Cost : = Cost + c (v,w) ;
v : = w ;
U : = U - [w] ;
end ;
Tour : = Tour + [(v,vo)] ;
Cost : = Cost + c(v,vo) ;
end;
ThuËt to¸n Salesperson ®-îc x©y dùng trªn c¬ së m« h×nh d÷ liÖu ®å
thÞ vµ m« h×nh d÷ liÖu tËp hîp. Nã chøa c¸c thao t¸c trªn ®å thÞ, c¸c phÐp to¸n
tËp hîp. T- t-ëng cña thuËt to¸n nh- sau. XuÊt ph¸t tõ Tour lµ tËp rçng. Gi¶
sö ta x©y dùng ®-îc ®-êng ®i tõ ®Ønh xuÊt ph¸t v0 tíi ®Ønh v. B-íc tiÕp theo,
ta sÏ thªm vµo Tour c¹nh (v,w), ®ã lµ c¹nh ng¾n nhÊt tõ v tíi c¸c ®Ønh w
kh«ng n»m trªn ®-êng ®i tõ v0 tíi v. §Ó cã ®-îc ch-¬ng tr×nh, chóng ta ph¶i
biÓu diÔn ®å thÞ, tËp hîp bëi c¸c cÊu tróc d÷ liÖu. Sau ®ã viÕt c¸c thñ tôc
9
(hoÆc hµm) thùc hiÖn c¸c thao t¸c, c¸c phÐp to¸n trªn ®å thÞ, tËp hîp cã trong
thuËt to¸n.
Tãm l¹i, qu¸ tr×nh gi¶i mét bµi to¸n cã thÓ quy vÒ hai giai ®o¹n kÕ tiÕp
nh- sau
1. X©y dùng c¸c m« h×nh d÷ liÖu m« t¶ bµi to¸n. ThiÕt kÕ thuËt to¸n
b»ng c¸ch sö dông c¸c thao t¸c, c¸c phÐp to¸n trªn c¸c m« h×nh d÷ liÖu.
2. BiÓu diÔn c¸c m« h×nh d÷ liÖu bëi c¸c cÊu tróc d÷ liÖu. Víi c¸c cÊu
tróc d÷ liÖu ®· lùa chän, c¸c phÐp to¸n trªn c¸c m« h×nh d÷ liÖu ®-îc thÓ hiÖn
bëi c¸c thñ tôc (hµm) trong ng«n ng÷ lËp tr×nh nµo ®ã.
To¸n häc ®· cung cÊp cho Tin häc rÊt nhiÒu cÊu tróc to¸n häc cã thÓ
dïng lµm m« h×nh d÷ liÖu. Ch¼ng h¹n, c¸c kh¸i niÖm to¸n häc nh- d·y, tËp
hîp, ¸nh x¹, c©y, ®å thÞ, quan hÖ, nöa nhãm, nhãm, otomat,...Trong c¸c
ch-¬ng sau chóng ta sÏ lÇn l-ît nghiªn cøu mét sè m« h×nh d÷ liÖu quan
träng nhÊt, ®-îc sö dông th-êng xuyªn trong c¸c thuËt to¸n. §ã lµ c¸c m«
h×nh d÷ liÖu danh s¸ch, c©y, tËp hîp. Víi mçi m« h×nh d÷ liÖu chóng ta
nghiªn cøu c¸c c¸ch cµi ®Æt nã bëi c¸c cÊu tróc d÷ liÖu kh¸c nhau. Trong mçi
c¸ch cµi ®Æt, mét sè phÐp to¸n trªn m« h×nh cã thÓ ®-îc thùc hiÖn dÔ dµng,
nh-ng c¸c phÐp to¸n kh¸c cã thÓ l¹i kh«ng thuËn tiÖn. ViÖc lùa chän cÊu tróc
d÷ liÖu nµo ®Ó biÓu diÔn m« h×nh phô thuéc vµo tõng ¸p dông.
Nh- ®· nãi, víi mçi m« h×nh d÷ liÖu, chóng ta cã thÓ thùc hiÖn mét tËp
hîp c¸c phÐp to¸n rÊt ®a d¹ng, phong phó. Song trong nhiÒu ¸p dông, chóng
ta chØ sö dông m« h×nh víi mét sè x¸c ®Þnh c¸c phÐp to¸n nµo ®ã. Khi ®ã
chóng ta sÏ cã mét kiÓu d÷ liÖu trõu t-îng.
Nh- vËy, mét kiÓu d÷ liÖu trõu t-îng (abstract data type) lµ mét m«
h×nh d÷ liÖu ®-îc xÐt cïng víi mét sè x¸c ®Þnh c¸c phÐp to¸n nµo ®ã. Ch¼ng
h¹n, c¸c tËp hîp chØ xÐt víi c¸c phÐp to¸n : thªm mét phÇn tö vµo mét tËp ®·
cho, lo¹i mét phÇn tö khái mét tËp hîp ®· cho, t×m xem mét phÇn tö ®· cho
cã n»m trong mét tËp hîp hay kh«ng, lËp thµnh kiÓu d÷ liÖu trõu t-îng
(KDLTT) tõ ®iÓn (dictionnaire).
Cßn KDLTT hµng (hµng ®îi) lµ m« h×nh d÷ liÖu danh s¸ch cïng víi
hai phÐp to¸n chÝnh lµ : thªm mét phÇn tö míi vµo mét ®Çu danh s¸ch, vµ lo¹i
mét phÇn tö ë mét ®Çu kh¸c cña danh s¸ch. Chóng ta sÏ nghiªn cøu kü mét sè
kiÓu d÷ liÖu trõu t-îng quan träng nhÊt : hµng, ng¨n xÕp (stack), tõ ®iÓn, hµng
-u tiªn. Víi mçi KDLTT, c¸c cÊu tróc d÷ liÖu ®Ó biÓu diÔn nã sÏ ®-îc nghiªn
cøu. Chóng ta còng sÏ ®¸nh gi¸ hiÖu qu¶ cña c¸c phÐp to¸n trong tõng c¸ch
cµi ®Æt.
10
11 trang
22180
Free
Bạn đang xem tài liệu "Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 2: Kiểu dữ liệu, cấu trúc dữ liệu và mô hình dữ liệu", để 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:
- bai_giang_cau_truc_du_lieu_va_giai_thuat_chuong_2_kieu_du_li.doc
