Danh sách tuyến tính

Danh s¸ch TuyÕn tÝnh

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 trong c¸c thuËt to¸n. C¸c ph­¬ng ph¸p cµi ®Æt danh s¸ch kh¸c nhau sÏ ®­îc xÐt. Hai kiÓu d÷ liÖu trõu t­îng ®Æc biÖt quan träng lµ ng¨n xÕp (STACK) vµ hµng ®îi (QUEUE) 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.

I. Kh¸i niÖm vÒ danh s¸ch.

1. §Þnh nghÜa

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 cïng mét líp c¸c ®èi t­îng nµo ®ã. Ch¼ng h¹n, danh s¸ch sinh viªn cña mét líp, danh s¸ch c¸c sè nguyªn, danh s¸ch c¸c b¸o xuÊt b¶n hµng ngµy ë thñ ®« v.v...

Gi¶ sö L lµ mét danh s¸ch cã n phÇn tö (n>=0).

L = (a1, a2, ..., an)

Ta gäi n lµ ®é dµi cña danh s¸ch. nÕu n>=1 th× a1 ®­îc gäi lµ phÇn tö ®Çu tiªn, an ®­îc gäi lµ phÇn tö cuèi cïng cña danh s¸ch L. NÕu n=0 th× danh s¸ch L ®­îc gäi lµ danh s¸ch 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+1. Ta gäi a_i (i=1, 2, ..., n) lµ phÇn tö ë vÞ trÝ thø i cña danh s¸ch.

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

Khi 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 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(X : Item; p : position; Var L : List);

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

Procedure Insert_Before(X : Item; p : position; Var L : List);

6. T×m phÇn X trong danh danh s¸ch.

Function Search(X : Item; L : List) : Boolean;

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

Function Empty(L : List) : Boolean;

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

Function Full(L : List) : Boolean;

9. DuyÖt danh s¸ch.

Trong nhiÒu øng dông chóng ta ph¶i ®i qua danh s¸ch, tõ ®Çu ®Õn cuèi danh s¸ch vµ thùc hiÖn mét nhãm c¸c thao t¸c nµo ®ã ®èi 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ö 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, t¸ch mét danh s¸ch thµnh nhiÒu danh s¸ch v.v...

VÝ dô: Gi¶ sö cã 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 Insert_Before(1, 6, L) ta ®­îc danh s¸ch (6, 3, 2, 1, 5).

Sau ®©y ta sÏ xÐt mét sè lo¹i danh s¸ch vµ øng dông cña chóng.

II. Danh s¸ch tuyÕn tÝnh.

1. Kh¸i niÖm.

Mét danh s¸ch mµ quan hÖ l©n cËn gi÷a c¸c phÇn tö ®­îc hiÓn thÞ ra th× ®­îc lµ danh s¸ch tuyÕn tÝnh.

Nh­ vËy, danh s¸ch tuyÕn tÝnh lµ mét danh s¸ch hoÆc rçng, hoÆc cã d¹ng (a1, a2, ..., an). Trong danh s¸ch tuyÕn tÝnh lu«n tån t¹i mét phÇn tö ®Çu a1 vµ mét phÇn tö cuèi an.

§Ó l­u tr÷ danh s¸ch tuyÕn tÝnh trong bé nhí m¸y tÝnh ng­êi ta sö dông m¶ng mét chiÒu. Tuy nhiªn viÖc sö dông m¶ng mét chiÒu còng cã nh÷ng ­u ®iÓm vµ nh­îc ®iÓm nhÊt ®Þnh cña nã.

V× m¶ng ®­îc ®­îc l­u tr÷ kÕ tiÕp nªn viÖc truy nhËp viÖc truy nhËp vµo phÇn tö cña m¶ng ®­îc thùc hiÖn trùc tiÕp dùa vµo ®Þa chØ tÝnh ®­îc (chØ sè), nªn tèc ®é nhanh vµ ®ång ®Òu ®èi víi mäi phÇn tö.

Khi khai b¸o mét m¶ng ta ph¶i x¸c ®Þnh sè l­îng phÇn tö cña m¶ng, ®iÒu nµy sÏ tuú thuéc vµo sè l­îng ®èi t­îng cña danh s¸ch mµ m¶ng l­u tr÷, nh­ng ®iÒu nµy rÊt khã thùc hiÖn v× sè l­îng ®èi t­îng cña danh s¸ch lu«n lu«n biÕn ®éng. Do ®ã dÉn ®Õn viÖc l·ng phÝ bé nhí (cã nh÷ng phÇn tö m¶ng kh«ng ®­îc sö dông) hoÆc thiÕu bé nhí (do tÊt c¶ c¸c phÇn tö m¶ng ®· ®­îc sö dông trong khi ta cÇn thªm mét sè ®èi t­îng nµo ®ã vµo danh s¸ch).

2. L­u tr÷ kÕ tiÕp cña danh s¸ch tuyÕn tÝnh.

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 l­u tr÷ 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 tr÷ trong c¸c thµnh phÇn kÕ nhau cña m¶ng. Sau ®©y sÏ tr×nh bµy hai lo¹i danh s¸ch s¸ch tuyÕn tÝnh lµ ng¨n xÕp (Stack) vµ hµng ®îi (Queue) cïng víi c¸c phÐp to¸n c¬ b¶n cña nã.