Bài giảng Cấu trúc dữ liệu và giải thuật

Ch-¬ng 3

danh s¸ch

Trong ch-¬ng nµy, chóng ta sÏ nghiªn cøu danh s¸ch, mét trong c¸c

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. C¸c ph-¬ng ph¸p kh¸c nhau ®Ó cµi ®Æt danh s¸ch sÏ ®-îc xÐt. Chóng ta

sÏ ph©n tÝch hiÖu qu¶ cña c¸c phÐp to¸n trªn danh s¸ch trong mçi c¸ch cµi

®Æt. Hai kiÓu d÷ liÖu trõu t-îng ®Æc biÖt quan träng lµ stack (ng¨n xÕp) vµ

hµng (hµng ®îi) sÏ ®-îc nghiªn cøu. Chóng ta còng sÏ tr×nh bµy mét sè øng

dông cña danh s¸ch.

3.1. Danh s¸ch.

cïng mét líp c¸c ®èi t-îng nµo ®ã. Ch¼ng h¹n, ta cã thÓ VÒ mÆt to¸n häc,

danh s¸ch lµ mét d·y h÷u h¹n c¸c phÇn tö thuéc nãi ®Õn danh s¸ch c¸c sinh

viªn cña mét líp, danh s¸ch c¸c sè nguyªn nµo ®ã, danh s¸ch c¸c b¸o xuÊt

b¶n hµng ngµy ë thñ ®«, ...

Gi¶ sö L lµ danh s¸ch cã n (n  0) phÇn tö

L = (a₁, a₂, ..., a_n)

Ta gäi sè n lµ ®é dµi cña cña danh s¸ch. NÕu n 1 th× a₁®-îc gäi lµ

phÇn tö ®Çu tiªn cña danh s¸ch, cßn a_nlµ phÇn tö cuèi cïng cña danh s¸ch.

NÕu n = 0 tøc danh s¸ch kh«ng cã phÇn tö nµo, th× danh s¸ch ®-îc gäi lµ

rçng.

Mét tÝnh chÊt quan träng cña danh s¸ch lµ c¸c phÇn tö cña nã ®-îc s¾p

tuyÕn tÝnh : nÕu n > 1 th× phÇn tö a_i"®i tr-íc" phÇn tö a_i+1hay "®i s©u" phÇn

tö a_ivíi i = 1,2, ..., n-1. Ta sÏ nãi a_i(i = 1,2, ..., n) lµ phÇn tö ë vÞ trÝ thø i cña

danh s¸ch.

CÇn chó ý r»ng, mét ®èi t-îng cã thÓ xuÊt hiÖn nhiÒu lÇn trong mét

danh s¸ch. Ch¼ng h¹n nh- trong danh s¸ch c¸c sè ngµy cña c¸c th¸ng trong

mét n¨m

(31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31)

Danh s¸ch con.

NÕu L = (a₁, a₂, ..., a_n) lµ mét danh s¸ch vµ i, j lµ c¸c vÞ trÝ, 1  i  j  n

th× danh s¸ch L' = (b₁, b₂, ..., b_j-i+1) trong ®ã b₁= a_i, b₂= a_i+1) ... b_j-i+1=a_j, Nh-

vËy, danh s¸ch con L' gåm tÊt c¶ c¸c phÇn tö tõ a_i®Õn a_jcña danh s¸ch L.

Danh s¸ch rçng ®-îc xem lµ danh s¸ch con cña mét danh s¸ch bÊt kú.

32

Danh s¸ch con bÊt kú gåm c¸c phÇn tö b¾t ®Çu tõ phÇn tö ®Çu tiªn cña

danh s¸ch L ®-îc gäi lµ phÇn ®Çu (prefix) cña danh s¸ch L. PhÇn cuèi

(postfix) cña danh s¸ch L lµ mét danh s¸ch con bÊt kú kÕt thóc ë phÇn tö cuèi

cïng cña danh s¸ch L.

D·y con

Mét danh s¸ch ®-îc t¹o thµnh b»ng c¸ch lo¹i bá mét sè (cã thÓ b»ng

kh«ng) phÇn tö cña danh s¸ch L ®-îc gäi lµ d·y con cña danh s¸ch L.

VÝ dô. XÐt danh s¸ch

L = (black, blue, green, cyan, red, brown, yellow)

Khi ®ã danh s¸ch (blue, green, cyan, red) lµ danh s¸ch con cña L. Danh

s¸ch (black, green, brown) lµ d·y con cña L. Danh s¸ch (black, blue, green) lµ

phÇn ®Çu, cßn danh s¸ch (red, brown, yellow) lµ phÇn cuèi cña danh s¸ch L.

C¸c phÐp to¸n trªn danh s¸ch.

Chóng ta ®· tr×nh bµy kh¸i niÖm to¸n häc danh s¸ch. Khi m« t¶ mét

m« t¶ mét m« h×nh d÷ liÖu, chóng ta cÇn x¸c ®Þnh c¸c phÐp to¸n cã thÓ thùc

hiÖn trªn m« h×nh to¸n häc ®-îc dïng lµm c¬ së cho m« h×nh d÷ liÖu. Cã rÊt

nhiÒu phÐp to¸n trªn danh s¸ch. Trong c¸c øng dông, th«ng th-êng chóng ta

chØ sö dông mét nhãm c¸c phÐp to¸n nµo ®ã. Sau ®©y lµ mét sè phÐp to¸n

chÝnh trªn danh s¸ch.

Gi¶ sö L lµ mét danh s¸ch (List), c¸c phÇn tö cña nã cã kiÓu d÷ liÖu

Item nµo ®ã, p lµ mét vÞ trÝ (position) trong danh s¸ch. C¸c phÐp to¸n sÏ ®-îc

m« t¶ bëi c¸c thñ tôc hoÆc hµm.

1. Khëi t¹o danh s¸ch rçng

procedure Initialize (var L : List) ;

2. X¸c ®Þnh ®é dµi cña danh s¸ch.

function Length (L : List) : integer

3. Lo¹i phÇn tö ë vÞ trÝ thø p cña danh s¸ch

procedure Delete (p : position ; var L : List) ;

4. Xen phÇn tö x vµo danh s¸ch sau vÞ trÝ thø p

procedure Insert After (p : position ; x : Item ; var L: List) ;

5. Xen phÇn tö x vµo danh s¸ch tr-íc vÞ trÝ thø p

procedure Insert Before (p : position ; x : Item ; var L:List) ;

6. T×m xem trong danh s¸ch cã chøa phÇn tö x hay kh«ng ?

procedure Search (x : Item ; L : List : var found : boolean) ;

7. KiÓm tra danh s¸ch cã rçng kh«ng ?

33

function Empty (L : List) : boolean ;

8. KiÓm tra danh s¸ch cã ®Çy kh«ng ?

function Full (L : List) : boolean ;

9. §i qua dah s¸ch. Trong nhiÒu ¸p dông chóng ta cÇn ph¶i ®i qua danh

s¸ch, tõ ®Çu ®Õn hÕt danh s¸ch, vµ thùc hiÖn mét nhãm hµnh ®éng nµo ®ã víi

mçi phÇn tö cña danh s¸ch.

procedure Traverse (var L : List) ;

10. C¸c phÐp to¸n kh¸c. Cßn cã thÓ kÓ ra nhiÒu phÐp to¸n kh¸c. Ch¼ng

h¹n truy cËp ®Õn phÇn tö ë vÞ trÝ thø i cña danh s¸ch (®Ó tham kh¶o hoÆc thay

thÕ), kÕt hîp hai danh s¸ch thµnh mét danh s¸ch, ph©n tÝch mét danh s¸ch

thµnh nhiÒu danh s¸ch, ...

VÝ dô : Gi¶ sö L lµ danh s¸ch L = (3,2,1,5). Khi ®ã, thùc hiÖn Delete

(3,L) ta ®-îc danh s¸ch (3,2,5). KÕt qu¶ cña InsertBefor (1, 6, L) lµ danh s¸ch

(6, 3, 2, 1, 5).

3.2. Cµi ®Æt danh s¸ch bíi m¶ng.

Ph-¬ng ph¸p tù nhiªn nhÊt ®Ó cµi ®Æt mét danh s¸ch lµ sö dông m¶ng,

trong ®ã mçi thµnh phÇn cña m¶ng sÏ l-u gi÷ mét phÇn tö nµo ®ã cña danh

s¸ch, vµ c¸c phÇn tö kÕ nhau cña danh s¸ch ®-îc l-u gi÷ trong c¸c thµnh phÇn

kÕ nhau cña m¶ng.

Gi¶ sö ®é dµi tèi ®a cña danh s¸ch (maxlength) lµ mét sè N nµo ®ã, c¸c

phÇn tö cña danh s¸ch cã kiÓu d÷ liÖu lµ Item. Item cã thÓ lµ c¸c kiÓu d÷ liÖu

®¬n, hoÆc c¸c d÷ liÖu cã cÊu tróc, th«ng th-êng Item lµ b¶n ghi. Chóng ta

biÓu diÔn danh s¸ch (List) bëi b¶n ghi gåm hai tr-êng. Tr-êng thø nhÊt lµ

m¶ng c¸c Item phÇn tö thø i cña danh s¸ch ®-îc l-u gi÷ trong thµnh phÇn thø

i cña m¶ng. Tr-êng thø hai ghi chØ sè cña thµnh phÇn m¶ng l-u gi÷ phÇn tö

cuèi cïng cña danh s¸ch (xem h×nh 3.1). Chóng ta cã c¸c khai b¸o nh- sau :

const maxlength = N ;

type List = record

element : array [1 ... maxlength]

of Item ;

count : 0 ... maxlength ;

end ;

var L : List ;

34

1

2

phÇn tö thø nhÊt

phÇn tö thø hai

danh s¸ch

.

Count

phÇn tö cuèi cïng

.

rçng

maxlength

H×nh 3.1. M¶ng biÓu diÔn danh s¸ch

Trong c¸ch cµi ®Æt danh s¸ch bëi m¶ng, c¸c phÐp to¸n trªn danh s¸ch

®-îc thùc hiÖn rÊt dÔ dµng. §Ó khëi t¹o mét danh s¸ch rçng, chØ gÇn mét lÖnh

g¸n :

L.count : = 0 ;

§é dµi cña danh s¸ch lµ L.count. Danh s¸ch ®Çy, nÕu L.count =

maxlength.

Sau ®©y lµ c¸c thñ tôc thùc hiÖn c¸c phÐp to¸n xen mét phÇn tö míi vµo

danh s¸ch vµ lo¹i mét phÇn tö khái danh s¸ch.

Thñ tôc lo¹i bá.

procedure Delete (p : 1 ... maxlength ; var L : List ;

var OK : boolean) ;

var i : 1 ... maxlength ;

begin

35

OK : = false ;

with L do

if p < = count then

begin

i : = p;

while i < count do

begin

element [i] : = element [i + 1] ;

i: = i + 1

end ;

count : = count -1 ;

OK : = true ;

end ;

Thñ tôc trªn thùc hiÖn phÐp lo¹i bá phÇn tö ë vÞ trÝ p khái danh s¸ch.

PhÐp to¸n chØ ®-îc thùc hiÖn khi danh s¸ch kh«ng rçng vµ p chØ vµo mét phÇn

tö trong danh s¸ch. Tham biÕn OK ghi l¹i phÐp to¸n cã ®-îc thùc hiÖn thµnh

c«ng hay kh«ng. Khi lo¹i bá, chóng ta ph¶i dån c¸c phÇn tö c¸c vÞ trÝ p+1, p +

2, ... lªn trªn mét vÞ trÝ.

Thñ tôc xen vµo.

procedure InsertBefore (p : 1 ... maxlength ; x : Item ;

var L : List ; var OK : boolean) ;

var i : 1... maxlength ;

begin

OK: = false ;

with L do

if (count < maxlength) and ( p <= count) then

begin

i: = count + 1 ;

while i > p do

36

begin

element[i]:= element[i-1] ;

i:=i-1 ;

end ;

element [p] : = x ;

count : = count + 1 ;

OK : = true ;

end ;

Thñ tôc trªn thùc hiÖn viÖc xen phÇn tö míi x vµo tr-íc phÇn tö ë vÞ trÝ

p trong danh s¸ch. PhÐp to¸n nµy chØ ®-îc thùc hiÖn khi danh s¸ch ch-a ®Çy

(count < maxlength) vµ p chØ vµo mét phÇn tö trong danh s¸ch (p <= count).

Chóng ta ph¶i dån c¸c phÇn tö ë c¸c vÞ trÝ p, p+1, ... xuèng d-íi mét vÞ trÝ ®Ó

lÊy chç cho x.

NÕu n lµ ®é dµi cña danh s¸ch ; dÔ dµng thÊy r»ng, c¶ hai phÐp to¸n

lo¹i bá vµ xen vµo ®-îc thùc hiÖn trong thêi gian O(n).

ViÖc t×m kiÕm trong danh s¸ch lµ mét phÐp to¸n ®-îc sö dông th-êng

xuyªn trong c¸c øng dông. Chóng ta sÏ xÐt riªng phÐp to¸n nµy trong môc

sau.

NhËn xÐt vÒ ph-¬ng ph¸p biÓu diÔn danh s¸ch bíi m¶ng.

Chóng ta ®· cµi ®Æt danh s¸ch bíi m¶ng, tøc lµ dïng m¶ng ®Ó l-u gi÷

c¸c phÇn tö cña danh s¸ch. Do tÝnh chÊt cña m¶ng, ph-¬ng ph¸p nµy cho phÐp

ta truy cËp trùc tiÕp ®Õn phÇn tö ë vÞ trÝ bÊt kú trong danh s¸ch. C¸c phÐp to¸n

kh¸c ®Òu ®-îc thùc hiÖn rÊt dÔ dµng. Tuy nhiªn ph-¬ng ph¸p nµy kh«ng

thuËn tiÖn ®Ó thùc hiÖn phÐp to¸n xen vµo vµ lo¹i bá. Nh- ®· chØ ra ë trªn,

mçi lÇn cÇn xen phÇn tö míi vµo danh s¸ch ë vÞ trÝ p (hoÆc lo¹i bá phÇn tö ë

vÞ trÝ p) ta ph¶i ®Èy xuèng d-íi (hoÆc lªn trªn) mét vÞ trÝ tÊt c¶ c¸c phÇn tõ ®i

sau phÇn tö thø p. Nh-ng h¹n chÕ chñ yÕu cña c¸ch cµi ®Æt nµy lµ ë kh«ng

gian nhí cè ®Þnh giµnh ®Ó l-u gi÷ c¸c phÇn tö cña danh s¸ch. Kh«ng gian nhí

nµy bÞ quy ®Þnh bëi cì cña m¶ng. Do ®ã danh s¸ch kh«ng thÓ ph¸t triÓn qu¸

cì cña m¶ng, phÐp to¸n xen vµo sÏ kh«ng ®-îc thùc hiÖn khi m¶ng ®· ®Çy.

3.3. T×m kiÕm trªn danh s¸ch.

3.3.1. VÊn ®Ò t×m kiÕm.

37

T×m kiÕm th«ng tin lµ mét trong c¸c vÊn ®Ò quan träng nhÊt trong tin

häc. Cho tr-íc mét sè ®iÖn tho¹i, chóng ta cÇn t×m biÕt ng-êi cã sè ®iÖn tho¹i

®ã, ®Þa chØ cña anh ta, vµ nh÷ng th«ng tin kh¸c g¾n víi sè ®iÖn tho¹i ®ã.

Th«ng th-êng c¸c th«ng tin vÒ mét ®èi t-îng ®-îc biÓu diÔn d-íi d¹ng mét

b¶n ghi, c¸c thuéc tÝnh cña ®èi t-îng lµ c¸c tr-êng cña b¶n ghi. Trong bµi

to¸n t×m kiÕm, chóng ta sÏ tiÕn hµnh t×m kiÕm c¸c ®èi t-îng dùa trªn mét sè

thuéc tÝnh ®· biÕt vÒ ®èi t-îng, chóng ta sÏ gäi c¸c thuéc tÝnh nµy lµ kho¸.

Nh- vËy, kho¸ cña b¶n ghi ®-îc hiÓu lµ mét hoÆc mét sè tr-êng nµo ®ã cña

b¶n ghi. Víi mét gi¸ trÞ cho tr-íc cña kho¸, cã thÓ cã nhiÒu b¶n ghi cã kho¸

®ã. Còng cã thÓ x¶y ra, kh«ng cã b¶n ghi nµo cã gi¸ trÞ kho¸ ®· cho.

Thêi gian t×m kiÕm phô thuéc vµo c¸ch chóng ta tæ chøc th«ng tin vµ

ph-¬ng ph¸p t×m kiÕm ®-îc sö dông. Chóng ta cã thÓ tæ chøc c¸c ®èi t-îng

®Ó t×m kiÕm d-íi d¹ng danh s¸ch, hoÆc c©y t×m kiÕm nhÞ ph©n,...Víi mçi

c¸ch cµi ®Æt (Ch¼ng h¹n, cã thÓ cµi ®Æt danh s¸ch bëi m¶ng, hoÆc danh s¸ch

liªn kÕt), chóng ta sÏ cã ph-¬ng ph¸p t×m kiÕm thÝch hîp.

Ng-êi ta ph©n biÖt hai lo¹i t×m kiÕm : t×m kiÕm trong vµ t×m kiÕm

ngoµi. NÕu khèi l-îng th«ng tin lín cÇn l-u gi÷ d-íi d¹ng c¸c file ë bé nhí

ngoµi, nh- ®Üa tõ hoÆc b¨ng tõ, th× sù t×m kiÕm ®-îc gäi lµ t×m kiÕm ngoµi.

Trong tr-êng hîp th«ng tin ®-îc l-u gi÷ ë bé nhí trong, ta nãi ®Õn t×m kiÕm

trong. Trong ch-¬ng nµy vµ c¸c ch-¬ng sau, chóng ta chØ ®Ò cËp t×m kiÕm

trong.

Sau ®©y chóng ta sÏ nghiªn cøu c¸c ph-¬ng ph¸p t×m kiÕm trªn danh

s¸ch ®-îc biÓu diÔn bëi m¶ng.

3.3.2. T×m kiÕm tuÇn tù.

Gi¶ sö keytype lµ kiÓu kho¸. Trong nhiÒu tr-êng hîp keytype lµ

integer, real, hoÆc string. C¸c phÇn tö cña danh s¸ch cã kiÓu Item - b¶n ghi

cã chøa tr-êng key kiÓu keytype.

type keytype = .... ;

Item = record

key : keytype ;

c¸c tr-êng kh¸c

. . . . . .

end ;

List

= record

element : array 1...max of Item ;

count : 0 .. max ;

end ;

38

T×m kiÕm tuÇn tù (hay t×m kiÕm tuyÕn tÝnh) lµ ph-¬ng ph¸p t×m kiÕm

®¬n gi¶n nhÊt : xuÊt ph¸t tõ ®Çu danh s¸ch, chóng ta tuÇn tù ®i trªn danh s¸ch

cho tíi khi t×m ra phÇn tö cã kho¸ ®· cho th× dõng l¹i, hoÆc ®i ®Õn hÕt danh

s¸ch mµ kh«ng t×m thÊy. Ta cã thñ tôc t×m kiÕm sau.

procedure SeqSearch (var L : List ; x : keytype ;

var found : boolean ; var p : 1..max) ;

begin

found : = false ;

p : = 1 ;

with L do

while (not found) and ( p = count) do

if element p . key = x then found : = true

else p : = p + 1 ;

end ;

Thñ tôc trªn ®Ó t×m xem trong danh s¸ch L cã chøa phÇn tö víi kho¸ lµ

x hay kh«ng. NÕu cã th× gi¸ trÞ cña tham biÕn found lµ true. Trong tr-êng hîp

cã, biÕn p sÏ ghi l¹i vÞ trÝ cña phÇn tö ®Çu tiªn cã kho¸ lµ x.

Ph©n tÝch t×m kiÕm tuÇn tù.

Gi¶ sö ®é dµi cña danh s¸ch lµ n (count = n). DÔ dµng thÊy r»ng, thêi

gian thùc hiÖn t×m kiÕm tuÇn tù lµ thêi gian thùc hiÖn lÖnh while. Mçi lÇn lÆp

cÇn thùc hiÖn phÐp so s¸nh kho¸ x víi kho¸ cña mét phÇn tö trong danh s¸ch,

sè lín nhÊt c¸c lÇn lÆp lµ n, do ®ã thêi gian t×m kiÕm tuÇn tù lµ 0 (n).

3.3.3. T×m kiÕm nhÞ ph©n.

Gi¶ sö L lµ mét danh s¸ch cã ®é dµi n vµ ®-îc biÓu diÔn bëi m¶ng, c¸c

phÇn tö cña nã cã kiÓu Item ®-îc m« t¶ nh- trong môc 3.3.2. Gi¶ sö kiÓu cña

kho¸ keytype lµ kiÓu cã thø tù, tøc lµ víi hai gi¸ trÞ bÊt kú cña nã v₁vµ v₂, ta

lu«n lu«n cã v₁ v₂, hoÆc v₁ v₂; trong ®ã  lµ mét quan hÖ thø tù nµo ®ã

®-îc x¸c ®Þnh trªn keytype. Gi¶ sö c¸c phÇn tö cña danh s¸ch L ®-îc s¾p xÕp

theo thø tù kho¸ kh«ng gi¶m :

L. element 1. key  L. element 2.key  ...

 L. element n.key

39

Trong tr-êng hîp nµy, chóng ta cã thÓ ¸p dông ph-¬ng ph¸p t×m kiÕm

kh¸c, hiÖu qu¶ h¬n ph-¬ng ph¸p t×m kiÕm tuÇn tù. §ã lµ kü thuËt t×m kiÕm

nhÞ ph©n. T- t-ëng cña t×m kiÕm nhÞ ph©n nh- sau : §Çu tiªn ta so s¸nh kho¸

1

x víi khãa cña phÇn tö ë gi÷a danh s¸ch, tøc phÇn tö ë vÞ trÝ m=(1+n)/2  .

NÕu chóng b»ng nhau x = L.element [m].key, ta ®· t×m thÊy. NÕu x <

L.element [m].key, ta tiÕp tôc t×m kiÕm trong nöa ®Çu danh s¸ch tõ vÞ trÝ 1

®Õn vÞ trÞ m-1. Cßn nÕu x > L.element [m].key, ta tiÕp tôc t×m kiÕm trong nöa

cuèi danh s¸ch tõ vÞ trÞ m + 1 ®Õn vÞ trÝ n. NÕu ®Õn mét thêi ®iÓm nµo ®ã, ta

ph¶i t×m x trong mét danh s¸ch con rçng, th× ®iÒu ®ã cã nghÜa lµ trong danh

s¸ch kh«ng cã phÇn tö nµo víi kho¸ x.

Chóng ta cã thÓ m« t¶ ph-¬ng ph¸p t×m kiÕm nhÞ ph©n bëi thñ tôc sau :

procedure BinarySearch (var L : List ; x : key type ;

var found : boolean ; p : 1 ... max) ;

var mid , bottom, top : integer ;

begin

(1) found : = false ;

(2) bottom : = 1,

(3) top : = L.count ;

(4) while (not found) and (bottom <= top) do

begin

(5) mid : = (bottom + top) div 2 ;

(6) if x = L. element [mid].key then

found : = true

else if x < L.element [mid].

top : = mid - 1 key then

else

bottom : = mid + 1 ;

end ;

(7) p : = mid ;

end ;

1

. Ký hiÖu a  chØ phÇn nguyªn cña a, tøc lµ sè nguyªn lín nhÊt nhá h¬n hoÆc b»ng a ;

ch¼ng h¹n 5  = 5, 5.2  = 5 cßn  a  chØ sè nguyªn nhá nhÊt lín h¬n hoÆc b»ng ch¼ng

h¹n  6.3  = 7,  6  = 6.

40

Trong thñ tôc trªn, ta ®· ®-a vµo hai biÕn bottom vµ top ®Ó ghi l¹i vÞ trÝ

®Çu vµ vÞ trÝ cuèi cña danh s¸ch con mµ ta cÇn tiÕp tôc t×m kiÕm. BiÕn mid ghi

l¹i vÞ trÝ gi÷a cña mçi danh s¸ch con. Qu¸ tr×nh t×m kiÕm ®-îc thùc hiÖn bëi

vßng lÆp while. Mçi lÇn lÆp kho¸ x ®-îc so s¸nh víi kho¸ cña phÇn tö ë gi÷a

danh s¸ch. NÕu b»ng nhau, found : = true vµ dõng l¹i. NÕu x nhá h¬n, ta tiÕp

tôc t×m ë nöa ®Çu cña danh s¸ch con ®ang xÐt (®Æt l¹i top : = mid -1 ). NÕu x

lín h¬n, ta sÏ t×m tiÕp ë nöa cuèi danh s¸ch (®Æt l¹i bottom :=mid + 1).

Ph©n tÝch t×m kiÕm nhÞ ph©n.

Trùc quan, ta thÊy ngay t×m kiÕm nhÞ ph©n hiÖu qu¶ h¬n t×m kiÕm tuÇn

tù, bëi v× trong t×m kiÕm tuÇn tù ta ph¶i lÇn l-ît xÐt tõng phÇn tö cña danh

s¸ch, b¾t ®Çu tõ phÇn tö ®Çu tiªn cho tíi khi ph¸t hiÖn ra phÇn tö cÇn t×m hoÆc

kh«ng. Cßn trong t×m kiÕm nhÞ ph©n, mçi b-íc ta chØ cÇn xÐt phÇn tö ë gi÷a

danh s¸ch, nÕu ch-a ph¸t hiÖn ra ta l¹i xÐt tiÕp phÇn tö ë gi÷a nöa ®Çu hoÆc

nöa cuèi danh s¸ch. Sau ®©y, ta ®¸nh gi¸ thêi gian thùc hiÖn t×m kiÕm nhÞ

ph©n. Gi¶ sö ®é dµi danh s¸ch lµ n. Thêi gian thùc hiÖn c¸c lÖnh (1) - (3) vµ

(7) lµ 0(1). V× vËy thêi gian thùc hiÖn thñ tôc lµ thêi gian thùc hiÖn lÖnh while

(4). Th©n cña lÖnh lÆp nµy (c¸c lÖnh (4) vµ (5) cã thêi gian thùc hiÖn lµ 0(1).

Gäi t lµ sè lÇn lÆp tèi ®a cÇn thùc hiÖn. Sau mçi lÇn lÆp ®é dµi cña danh s¸ch

gi¶m ®i mét nöa, tõ ®iÒu kiÖn bottom  top, ta suy ra t lµ sè nguyªn d-¬ng lín

nhÊt sao cho 2t  n, tøc lµ t  log₂n. Nh- vËy, thêi gian t×m kiÕm nhÞ ph©n

trong mét danh s¸ch cã n phÇn tö lµ 0(log₂n), trong khi ®ã thêi gian t×m kiÕm

tuÇn tù lµ 0(n).

3.3. CÊu tróc d÷ liÖu danh s¸ch liªn kÕt.

3.3.1. Danh s¸ch liªn kÕt.

Trong môc nµy chóng ta sÏ biÓu diÔn danh s¸ch bëi cÊu tróc d÷ liÖu

kh¸c, ®ã lµ danh s¸ch liªn kÕt. Trong c¸ch cµi ®Æt nµy, danh s¸ch liªn kÕt

®-îc t¹o nªn tõ c¸c tÕ bµo mçi tÕ bµo lµ mét b¶n ghi gåm hai tr-êng, tr-êng

infor "chøa" phÇn tö cña danh s¸ch, tr-êng next lµ con trá trá ®Õn phÇn tö ®i

sau trong danh s¸ch. Chóng ta sÏ sö dông con trá head trá tíi ®Çu danh s¸ch.

Nh- vËy mét danh s¸ch (a₁, a₂, ...a_n) cã thÓ biÓu diÔn bëi cÊu tróc d÷ liÖu danh

s¸ch liªn kÕt ®-îc minh ho¹ trong h×nh 3.2.

head

a₁

a₂

...

a_n



H×nh 3.2. Danh s¸ch liªn kÕt biÓu diÔn danh s¸ch (a₁, a₂, ...a_n)

41

Mét danh s¸ch liªn kÕt ®-îc hoµn toµn x¸c ®Þnh bëi con trá head trá tíi

®Çu danh s¸ch, do ®ã, ta cã thÓ khai b¸o nh- sau.

type pointer = ^ cell

cell = record

infor : Item ;

next : pointer

end ;

var head : pointer ;

Chó ý : Kh«ng nªn nhÇm lÉn danh s¸ch vµ danh s¸ch liªn kÕt. Danh

s¸ch vµ danh s¸ch liªn kÕt lµ hai kh¸i niÖm hoµn toµn kh¸c nhau. Danh s¸ch

lµ mét m« h×nh d÷ liÖu, nã cã thÓ ®-îc cµi ®Æt bëi c¸c cÊu tróc d÷ liÖu kh¸c

nhau. Cßn danh s¸ch liªn kÕt lµ mét cÊu tróc d÷ liÖu, ë ®©y nã ®-îc sö dông

®Ó biÓu diÔn danh s¸ch.

3.3.2. C¸c phÐp to¸n trªn danh s¸ch liªn kÕt.

Sau ®©y chóng ta sÏ xÐt xem c¸c phÐp to¸n trªn danh s¸ch ®-îc thùc

hiÖn nh- thÕ nµo khi mµ danh s¸ch ®-îc cµi ®Æt bëi danh s¸ch liªn kÕt.

§iÒu kiÖn ®Ó mét danh s¸ch liªn kÕt rçng lµ

head = nil

Do ®ã, muèn kh¬i t¹o mét danh s¸ch rçng, ta chØ cÇn lÖnh g¸n :

head : = nil

Danh s¸ch liªn kÕt chØ ®Çy khi kh«ng cßn kh«ng gian nhí ®Ó cÊp ph¸t

cho c¸c thµnh phÇn míi cña danh s¸ch. Chóng ta sÏ gi¶ thiÕt ®iÒu nµy kh«ng

xÈy ra, tøc lµ danh s¸ch liªn kÕt kh«ng khi nµo ®Çy. Do ®ã phÐp to¸n xen mét

phÇn tö míi vµo danh s¸ch sÏ lu«n lu«n ®-îc thùc hiÖn.

PhÐp to¸n xen vµo.

Gi¶ sö Q lµ mét con trá trá vµo mét thµnh phÇn cña danh s¸ch liªn kÕt,

vµ trong tr-êng hîp danh s¸ch rçng (head = nil) th× Q = nil. Chóng ta cÇn xen

mét thµnh phÇn míi víi infor lµ x vµo sau thµnh phÇn cña danh s¸ch ®-îc trá

bëi Q. PhÐp to¸n nµy ®-îc thùc hiÖn bëi thñ tôc sau :

procedure InsertAfter (x : Item ; Q : pointer ; var head : pointer) ;

var P : pointer ;

begin

new (P) ;

42

P^ . infor : = x ;

if head = nil then

begin

P^. next : = nil ;

head : = P ;

end else

begin

P^. next : = Q^. next ;

Q^. next : = P ;

end ;

C¸c hµnh ®éng trong thñ tôc InsertAfter ®-îc minh ho¹ trong h×nh3.3

Gi¶ sö b©y giê ta cÇn xen thµnh phÇn míi víi infor lµ x vµo tr-íc thµnh

phÇn cña danh s¸ch ®-îc trá bëi Q. PhÐp to¸n nµy (InsertBefore) phøc t¹p

h¬n. Khã kh¨n ë ®©y lµ, nÕu Q kh«ng lµ thµnh phÇn ®Çu tiªn cña danh s¸ch

(tøc lµ Q  head) th× ta kh«ng ®Þnh vÞ ®-îc thµnh phÇn ®i tr-íc thµnh phÇn Q

®Ó kÕt nèi víi thµnh phÇn sÏ ®-îc xen vµo. Cã thÓ gi¶i quyÕt khã kh¨n nµy

b»ng c¸ch, ®Çu tiªn ta vÉn xen thµnh phÇn míi vµo sau thµnh phÇn Q, sau ®ã

trao ®æi gi¸ trÞ chøa trong phÇn infor gi÷a thµnh phÇn míi vµ thµnh phÇn Q.

procedure InsertBefore (x : Item l Q : pointer ; var head : pointer) ;

var P : pointer ;

begin

new (P) ;

if Q = head then

begin

P^. infor : = x ;

P^. next : = Q ;

head : = P

end else

begin

P^.next : = Q^. next ;

43

Q^.next : = P ;

P^.infor : = Q^.infor ;

Q^.infor : = x ;

end ;

Q

X

P

H×nh 3.3. Xen thµnh phÇn míi vµo danh s¸ch sau Q.

PhÐp to¸n lo¹i bá.

Gi¶ sö ta cã mét danh s¸ch liªn kÕt kh«ng rçng (head  nil) Q lµ mét

con trá trá vµo mét thµnh phÇn trong danh s¸ch. Gi¶ sö ta cÇn lo¹i bá thµnh

phÇn Q khái danh s¸ch. ë ®©y ta còng gÆp khã kh¨n nh- khi muèn xen mét

thµnh phÇn míi vµo tr-íc thµnh phÇn Q. Do ®ã, ta cÇn ®-a vµo mét con trá R

®i tr-íc con trá Q mét b-íc, tøc lµ nÕu Q kh«ng ph¶i lµ thµnh phÇn ®Çu tiªn,

th× Q = R^.next. Khi ®ã phÐp to¸n lo¹i bá thµnh phÇn Q khái danh s¸ch ®-îc

thùc hiÖn rÊt dÔ dµng. Ta cã thñ tôc sau :

procedure Delete (Q,R : pointer ; var head : pointer ; var x : Item),

begin

x : = Q^.Infor ;

if Q = head then head : = Q^.next

else R^.next : = Q^.next ;

end ;

44

H×nh 3.4. Minh ho¹ c¸c thao t¸c trong thñ tôc Delete.

R

X

Q

.....

X

......

H×nh 3.4. Xo¸ thµnh phÇn Q khái danh s¸ch.

PhÐp to¸n t×m kiÕm.

§èi víi danh s¸ch liªn kÕt, ta chØ cã thÓ ¸p dông ph-¬ng ph¸p t×m kiÕm

tuÇn tù. Cho dï danh s¸ch ®· ®-îc s¾p xÕp theo thø tù kh«ng t¨ng (hoÆc

kh«ng gi¶m) cña kho¸ t×m kiÕm, ta còng kh«ng thÓ ¸p dông ®-îc ph-¬ng

ph¸p t×m kiÕm nhÞ ph©n. Lý do lµ, ta kh«ng dÔ dµng x¸c ®Þnh ®-îc thµnh phÇn

ë gi÷a cña danh s¸ch liªn kÕt.

Gi¶ sö chóng ta cÇn t×m trong danh s¸ch thµnh phÇn víi infor lµ x cho

s¸ch, lÇn l-ît qua c¸c thµnh phÇn cña danh s¸ch vµ dõng l¹i ë thµnh phÇn víi

infor = x. BiÕn found ®-îc sö dông ®Ó ghi l¹i sù t×m kiÕm thµnh c«ng hay

kh«ng.

procedure Search (x : Item ; head : pointer ; var P : pointer

var found : boolean) ;

begin

P : = head ;

found : = false ;

while (P < > nil ) and (not found) do

if P^.infor = x then found : = true

else P : = P^.next

end ;

Th«ng th-êng ta cÇn t×m kiÕm ®Ó thùc hiÖn c¸c thao t¸c kh¸c víi danh

s¸ch. Ch¼ng h¹n, ta cÇn lo¹i bá khái danh s¸ch thµnh phÇn víi infor = x hoÆc

45

xen mét thµnh phÇn míi vµo tr-íc (hoÆc sau) thµnh phÇn víi infor = x. Muèn

thÕ, tr-íc hÕt ta ph¶i t×m trong danh s¸ch thµnh phÇn víi infor lµ x cho tr-íc.

§Ó cho phÐp lo¹i bá vµ xen vµo cã thÓ thùc hiÖn dÔ dµng, ta ®-a vµo thñ tôc

t×m kiÕm hai con trá ®i c¸ch nhau mét b-íc. Con trá Q trá vµo thµnh phÇn

cÇn t×m, cßn R trá vµo thµnh phÇn ®i tr-íc. Ta cã thñ tôc sau :

procedure Search (x : Item ; head : pointer ; var Q, R : pointer ;

var found : boolean) ;

begin

R : = nil ;

Q : = head ;

found : = false :

while (Q < > nil) and (not found) do

if Q^.infor = x then found : = true

else begin

R:=Q ;

Q : = Q^. next ;

end ;

PhÐp to¸n ®i qua danh s¸ch.

Trong nhiÒu ¸p dông, ta ph¶i ®i qua danh s¸ch, 'th¨m' tÊt c¶ c¸c thµnh

phÇn cña danh s¸ch. Víi mçi thµnh phÇn, ta cÇn thùc hiÖn mét sè phÐp to¸n

nµo ®ã víi c¸c d÷ liÖu chøa trong phÇn infor. C¸c phÐp to¸n nµy, gi¶ sö ®-îc

m« t¶ trong thñ tôc Visit. Ta cã thñ tôc sau.

procedure traverse (var head : pointer) ;

var P : pointer ;

begin

P : = head ;

while P < > nil do

begin

Visit (P^) ;

46

P : = P^. next

end ;

3.3.3. So s¸nh hai ph-¬ng ph¸p.

Chóng ta ®· tr×nh bÇy hai ph-¬ng ph¸p cµi ®Æt danh s¸ch : cµi ®Æt danh

lµ, ph-¬ng ph¸p nµo tèt h¬n ? Chóng ta chØ cã thÓ nãi r»ng, mçi ph-¬ng ph¸p

®Òu cã -u ®iÓm vµ h¹n chÕ, viÖc lùa chän ph-¬ng ph¸p nµo, m¶ng hay danh

c¸c nhËn xÐt so s¸nh hai ph-¬ng ph¸p.

1. Khi biÓu diÔn danh s¸ch bëi m¶ng, chóng ta ph¶i -íc l-îng ®é dµi

tèi ®a cña danh s¸ch ®Ó khai b¸o cì cña m¶ng. SÏ xÈy ra l·ng phÝ bé nhí khi

danh s¸ch cßn nhá. Nh-ng trong thêi gian ch¹y ch-¬ng tr×nh, nÕu phÐp to¸n

xen vµo ®-îc thùc hiÖn th-êng xuyªn, sÏ cã kh¶ n¨ng dÉn ®Õn danh s¸ch ®Çy.

Trong khi ®ã nÕu biÓu diÔn danh s¸ch bëi danh s¸ch liªn kÕt, ta chØ cÇn mét

l-îng kh«ng gian nhí cÇn thiÕt cho c¸c phÇn tö hiÖn cã cña danh s¸ch. Víi

c¸ch biÓu diÔn nµy, sÏ kh«ng xÈy ra t×nh tr¹ng danh s¸ch ®Çy, trõ khi kh«ng

gian nhí ®Ó cÊp ph¸t kh«ng cßn n÷a. Tuy nhiªn nã còng tiªu tèn bé nhí cho

c¸c con trá ë mçi tÕ bµo.

2. Trong c¸ch biÓu diÔn danh s¸ch bíi m¶ng, c¸c phÐp to¸n truy cËp

®Õn mçi phÇn tö cña danh s¸ch, x¸c ®Þnh ®é dµi cña danh s¸ch... ®-îc thùc

hiÖn trong thêi gian h»ng. Trong khi ®ã c¸c phÐp to¸n xen vµo vµ lo¹i bá ®ßi

hái thêi gian tØ lÖ víi ®é dµi cña danh s¸ch. §èi víi danh s¸ch liªn kÕt, c¸c

phÐp to¸n xen vµo vµ lo¹i bá l¹i ®-îc thùc hiÖn trong thêi gian h»ng, cßn c¸c

phÐp to¸n kh¸c l¹i cÇn thêi gian tuyÕn tÝnh. Do ®ã, trong ¸p dông cña m×nh, ta

cÇn xÐt xem phÐp to¸n nµo trªn danh s¸ch ®-îc sö dông nhiÒu nhÊt, ®Ó lùa

chän ph-¬ng ph¸p biÓu diÔn cho thÝch hîp.

3.4. C¸c d¹ng danh s¸ch liªn kÕt kh¸c.

3.4.1. Danh s¸ch vßng trßn.

Danh s¸ch liªn kÕt vßng trßn (gäi t¾t lµ danh s¸ch vßng trßn) lµ danh

s¸ch mµ con trá cña thµnh phÇn cuèi cïng cña danh s¸ch kh«ng b»ng nil mµ

trá ®Õn thµnh phÇn ®Çu tiªn cña danh s¸ch, t¹o thµnh mét vßng trßn (xem

47

h×nh 3.5). §Æc ®iÓm cña danh s¸ch vßng trßn lµ c¸c thµnh phÇn trong danh

s¸ch ®Òu b×nh ®¼ng, mçi thµnh phÇn ®Òu cã thµnh phÇn ®i sau. XuÊt ph¸t tõ

mét thµnh phÇn bÊt kú ta cã thÓ truy cËp ®Õn thµnh phÇn bÊt kú kh¸c trong

danh s¸ch.

basic

H×nh 3.5. Danh s¸ch vßng trßn

TÕ bµo t¹o nªn danh s¸ch vßng trßn cã cÊu tróc nh- trong danh s¸ch

liªn kÕt. Chóng ta sö dông mét con trá basic trá tíi mét thµnh phÇn bÊt kú

trong danh s¸ch.

type pointer = ^Cell ;

Cell = record

infor : Item ;

next : pointer ;

end ;

var basic : pointer ;

Trong c¸c ¸p dông, chóng ta th-êng sö dông danh s¸ch vßng trßn cã

basic^.next). §èi víi danh s¸ch vßng trßn, ta th-êng sö dông ba phÐp to¸n

1.Xen vµo bªn tr¸i danh s¸ch (Insertleft) mét thµnh phÇn míi

2. Xen vµo bªn ph¶i danh s¸ch (InsertRight) mét thµnh phÇn míi.

3. Lo¹i bá thµnh phÇn bªn tr¸i danh s¸ch (DeletLeft).

48

vµo bªn tr¸i danh s¸ch mét thµnh phÇn míi víi infor lµ x ®-îc thùc hiÖn bëi

thñ tôc sau :

procedure InsertLeft (var basic : pointer ; x : Item ) ;

var P : pointer ;

begin

new (P) :

P^. infor : =x ;

if basic = nil then

begin

basic : = P ;

basic^.next : = basic

end ;

else begin

P^.next : = basic^.next ;

basic^.next : = P

end ;

ViÖc xen vµo bªn ph¶i danh s¸ch ®-îc tiÕn hµnh nh- sau. Ta thªm

thµnh phÇn míi vµo bªn tr¸i, sau ®ã cho con trá basic trá vµo thµnh phÇn míi

®-îc thªm vµo nµy.

procedure InsertRight (var basic : pointer ; x : Item) ;

begin

InsertLeft (basic, x) ;

basic : = basic^.next ;

end ;

49

procedure DeleteLeft (var basic : pointer ; var x :Item) ;

var P : pointer ;

begin

if basic < > nil then

begin

P : = basic^.next ;

x : = P^.infor ;

if basic^. next = basic then basic : = nil

else basic^.next : = P^.next :

dispose (P)

end ;

Mét ®iÒu ®Æc biÖt n÷a cña danh s¸ch vßng trßn lµ ë chç, ta cã thÓ sö

dông nã nh- mét stack (víi c¸c phÐp to¸n InsertLeft vµ DeleteLeft), hoÆc cã

thÓ sù dông nã nh- mét hµng (víi c¸c phÐp to¸n InsertRight vµ DeleteLeft).

Stack vµ hµng sÏ ®-îc nghiªn cøu kü trong c¸c môc sau.

§èi víi danh s¸ch vßng trßn, mét sè phÐp to¸n kh¸c trªn danh s¸ch

®-îc thùc hiÖn rÊt dÔ dµng. Ch¼ng h¹n, ®Ó nèi hai danh s¸ch vßng trßn base1

vµ base2 thµnh mét danh s¸ch base1, ta chØ cÇn trao ®æi c¸c con trá

base1^.next vµ base2.next.

Trong nhiÒu ¸p dông, ®Ó thuËn tiÖn cho c¸c thao t¸c víi danh s¸ch vßng

trßn, ta ®-a thªm vµo danh s¸ch mét thµnh phÇn ®Æc biÖt (®-îc gäi lµ ®Çu cña

phÇn kh¸c cña danh s¸ch (xem h×nh 3.6). Mét -u ®iÓm cña danh s¸ch vßng

trßn cã ®Çu, lµ nã kh«ng bao giê rçng.

head

H×nh 3.6. Danh s¸ch vßng trßn cã ®Çu.

50

Trong môc 3.5, chóng ta sÏ ®-a ra mét øng dông cña danh s¸ch vßng

trßn cã ®Çu, ë ®ã nã ®-îc sö dông ®Ó biÓu diÔn c¸c ®a thøc.

3.4.2. Danh s¸ch hai liªn kÕt.

Khi lµm viÖc víi danh s¸ch, cã nh÷ng xö lý trªn mçi thµnh phÇn cña

danh s¸ch l¹i liªn quan ®Õn c¶ thµnh phÇn ®i tr-íc vµ thµnh phÇn ®i sau.

Trong c¸c tr-êng hîp nh- thÕ, ®Ó thuËn tiÖn, ng-êi ta ®-a vµo mçi thµnh phÇn

cña danh s¸ch hai con trá : nextleft trá ®Õn thµnh phÇn bªn tr¸i vµ nextright

trá ®Õn thµnh phÇn bªn ph¶i. Khi ®ã chóng ta cã mét danh s¸ch hai liªn kÕt.

Chóng ta cÇn ®Õn hai con trá : left trá ®Õn thµnh phÇn ngoµi cïng bªn tr¸i vµ

righ trá ®Õn thµnh phÇn ngoµi cïng bªn bªn ph¶i danh s¸ch (xem h×nh 3.7).

Ta cã thÓ khai b¸o cÊu tróc d÷ liÖu danh s¸ch hai liªn kÕt nh- sau :

type pointer = ^Cell ;

Cell = record

infor : Item ;

nextleft, nextright : pointer ;

end ;

List = record

left, right : pointer ;

end ;

left

right

. .

.

H×nh 3.7. Danh s¸ch hai liªn kÕt.

ViÖc cµi ®Æt danh s¸ch hai liªn kÕt, tÊt nhiªn tiªu tèn nhiÒu bé nhí h¬n

danh s¸ch mét liªn kÕt. Song bï l¹i, danh s¸ch hai liªn kÕt cã nh÷ng -u ®iÓm

mµ danh s¸ch mét liªn kÕt kh«ng cã: khi xem xÐt mét danh s¸ch hai liªn kÕt

ta cã thÓ tiÕn lªn tr-íc hoÆc lïi l¹i sau.

51

Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 3: Danh sách