Danh sách trong một mô hình dữ liệu

Ch ¬ng 3

d a n h s ¸ c h

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 = (a1, a2, ..., an)

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

phÇn tö ®Çu tiªn cña danh s¸ch, cßn an lµ 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ö ai "®i tríc" phÇn tö ai+1 hay "®i s©u" phÇn tö

ai víi i = 1,2, ..., n-1. Ta sÏ nãi ai (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 = (a1, a2, ..., an) lµ mét danh s¸ch vµ i, j lµ c¸c vÞ trÝ, 1 ≤ i ≤ j ≤ n

th× danh s¸ch L' = (b1, b2, ..., bj-i+1) trong ®ã b1 = ai , b2 = ai+1) ... bj-i+1=aj, Nh

vËy, danh s¸ch con L' gåm tÊt c¶ c¸c phÇn tö tõ ai ®Õn aj cñ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ú.

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

32

(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 ?

function Empty (L : List) : boolean ;

33

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Ï lu 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 lu 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 lu 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 lu 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 ;

1 phÇn tö thø nhÊt

34

2 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

OK : = false ;

35