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

Ch-¬ng 6

B¶ng

Trong ch-¬ng tr-íc chóng ta ®· nghiªn cøu m« h×nh d÷ liÖu tËp hîp vµ

mét sè kiÓu d÷ liÖu trõu t-îng (tõ ®iÓn, hµng -u tiªn) ®-îc x©y dùng trªn c¬ së

kh¸i niÖm tËp hîp. Trong ch-¬ng nµy chóng ta sÏ nghiªn cøu kiÓu d÷ liÖu trõu

t-îng b¶ng ®-îc x©y dùng trªn cë së kh¸i niÖm hµm (¸nh x¹). Chóng ta còng

sÏ xÐt viÖc cµi ®Æt mét tr-êng hîp ®Æc biÖt cña b¶ng, ®ã lµ c¸c b¶ng ch÷ nhËt.

6.1. KiÓu d÷ liÖu trõu t-îng b¶ng :

Tr-íc hÕt chóng ta nh¾c l¹i kh¸i niÖm hµm trong to¸n häc. Nhí l¹i r»ng,

mét quan hÖ R tõ tËp A ®Õn tËp B lµ mét tËp con nµo ®ã cña tÝch ®ªcac A x B,

tøc lµ R lµ mét tËp hîp nµo ®ã c¸c cÆp (a, b) víi a  A, b  B. Mét hµm f : A

 B (f lµ hµm tõ A ®Õn B) lµ mét quan hÖ f tõ A ®Õn B sao cho nÕu (a, b)  f

vµ (a, c)  f th× b = c. Tøc lµ, quan hÖ f lµ mét hµm, nÕu nã kh«ng chøa c¸c

cÆp (a, b), (a, c) víi b  c. NÕu (a, b)  f, th× ta nãi b lµ gi¸ trÞ cña hµm f t¹i a

vµ ký hiÖu lµ f (a), b = f (a). TËp hîp tÊt c¶ c¸c a  A, sao cho tån t¹i cÆp (a, b)

 f, ®-îc gäi lµ miÒn x¸c ®Þnh cña hµm f vµ ký hiÖu lµ Dom (f).

Cã nh÷ng hµm, ch¼ng h¹n hµm f(x) = e^x, ta cã thuËt to¸n ®Ó x¸c ®Þnh gi¸

trÞ cña hµm f(x) víi mçi x. Víi nh÷ng hµm nh- thÕ ta cã thÓ cµi ®Æt bëi c¸c

hµm trong Pascal hoÆc C. Tuy nhiªn cã rÊt nhiÒu hµm. Ch¼ng h¹n hµm cho

t-¬ng øng mçi nh©n viªn lµm viÖc trong mét c¬ quan víi l-¬ng hiÖn t¹i cña

ng-êi ®ã, ta chØ cã thÓ m« t¶ bëi b¶ng l-¬ng. Trong c¸c tr-êng hîp nh- thÕ, ®Ó

m« t¶ mét hµm f : A  B, ta ph¶i l-u gi÷ mét b¶ng m« t¶ c¸c th«ng tin vÒ c¸c

®èi t-îng a  A vµ c¸c th«ng tin vÒ c¸c ®èi t-îng b  B t-¬ng øng víi mçi a.

Mét b¶ng víi tËp chØ sè A vµ tËp gi¸ trÞ B lµ mét hµm f nµo ®ã tõ A ®Õn

B cïng víi c¸c phÐp to¸n sau ®©y :

1. Truy xuÊt : víi chØ sè cho tr-íc a thuéc miÒn x¸c ®Þnh cña hµm, t×m

ra gi¸ trÞ cña hµm t¹i a.

2. Söa ®æi : víi chØ sè cho tr-íc a thuéc miÒn x¸c ®Þnh cña hµm, thay gi¸

trÞ cña hµm t¹i a bëi mét gi¸ trÞ kh¸c cho tr-íc.

3. Xen vµo : thªm vµo miÒn x¸c ®Þnh cña hµm mét chØ sè míi vµ x¸c

®Þnh gi¸ trÞ cña hµm t¹i ®ã.

4. Lo¹i bá : lo¹i mét chØ sè nµo ®ã khái miÒn x¸c ®Þnh cña hµm cïng víi

gi¸ trÞ cña hµm t¹i ®ã.

§èi víi b¶ng, c¸c phÐp to¸n truy xuÊt vµ söa ®æi lµ quan träng nhÊt.

Th«ng th-êng trong c¸c ¸p dông, khi ®· l-u gi÷ mét b¶ng, ta chØ cÇn ®Õn viÖc

0

truy xuÊt th«ng tin tõ b¶ng vµ söa ®æi th«ng tin trong b¶ng. Tuy nhiªn trong

mét sè ¸p dông ta ph¶i cÇn ®Õn c¸c phÐp to¸n xen vµo vµ lo¹i bá.

Sau ®©y chóng ta ®-a ra mét vÝ dô vÒ b¶ng. Mét ma trËn m hµng, n cét B

= [b_ij] cã thÓ xem nh- mét b¶ng. TËp chØ sè A ë ®©y lµ tËp c¸c cÆp (i, j) víi i =

1, 2, ..... , M vµ j = 1, 2, ....., N. NÕu ma trËn lµ ma trËn c¸c sè nguyªn, ta cã

thÓ xÐt ma trËn nh- mét hµm f tõ tËp chØ sè ®Õn tËp c¸c sè nguyªn, trong ®ã F

(i, j) = b_ij. sau nµy chóng ta sÏ gäi c¸c b¶ng mµ tËp chØ sè lµ tËp c¸c cÆp (i, j)

víi i = 1, 2, ..., M vµ j = 1, 2, ...., N lµ c¸c b¶ng ch÷ nhËt cã M hµng vµ N cét.

6.2. Cµi ®Æt b¶ng :

6.2.1 Cµi ®Æt b¶ng bëi m¶ng :

Gi¶ sö tËp chØ sè cña b¶ng lµ mét kiÓu ®¬n cã thÓ dïng lµm kiÓu chØ sè

cña mét m¶ng. Trong Pascal kiÓu chØ sè cña m¶ng cã thÓ lµ miÒn con cña c¸c

sè nguyªn, ch¼ng h¹n 1 . . 1000; cã thÓ lµ kiÓu ký tù hoÆc miÒn con cña kiÓu

ký tù, ch¼ng h¹n 'A' . . 'Z', cã thÓ lµ mét kiÓu liÖt kª ho¨ch miÒn con cña kiÓu

liÖt kª nµo ®ã. Trong tr-êng hîp nµy, ta cã thÓ biÓu diÔn b¶ng bëi m¶ng. §Ó

chØ r»ng, t¹i mét chØ sè nµo ®ã hµm kh«ng x¸c ®Þnh, ta ®-a thªm vµo mét gi¸

trÞ míi undefined (kh«ng x¸c ®Þnh) kh¸c víi tÊt c¶ c¸c gi¸ trÞ thuéc tËp gi¸ trÞ

cña b¶ng. T¹i c¸c chØ sè mµ hµm kh«ng x¸c ®Þnh, ta sÏ g¸n cho c¸c thµnh phÇn

cña m¶ng t¹i c¸c chØ sè ®ã gi¸ trÞ undefined.

Ta cã thÓ khai b¸o kiÓu b¶ng nh- sau :

type table = array [indextype] of valuetype;

{indextype lµ kiÓu chØ sè, valuetupe lµ kiÓu gi¸ trÞ cña b¶ng bao

gåm gi¸ trÞ undefine}.

var T : table;

i : indextype;

Gi¶ sö value1, value2 lµ chØ sè ®Çu tiªn vµ cuèi cïng, khi ®ã viÖc khëi

t¹o mét b¶ng rçng (¸nh x¹ kh«ng x¸c ®Þnh kh¾p n¬i) ®-îc thùc hiÖn bëi lÖnh

For i : = value1 to value2 do

T [i] : = undefined;

ViÖc cµi ®Æt b¶ng bëi m¶ng cho phÐp ta truy cËp trùc tiÕp ®Õn mçi thµnh

phÇn cña b¶ng. c¸c phÐp to¸n ®èi víi b¶ng ®-îc thùc hiÖn rÊt dÔ dµng (b¹n ®äc

cã thÓ thÊy ngay cÇn ph¶i lµm g×) vµ chØ ®ßi hái mét thêi gian 0 (1). CÇn chó ý

r»ng, nÕu tËp chØ sè cña b¶ng kh«ng thÓ dïng lµm kiÓu chØ sè cña m¶ng, nh-ng

cã thÓ m· ho¸ bëi mét kiÓu chØ sè nµo ®ã cña m¶ng, th× ta còng cã thÓ cµi ®Æt

b¶ng bëi m¶ng. Qu¸ tr×nh cµi ®Æt gåm hai giai ®o¹n, ®Çu tiªn lµ m· ho¸ tËp chØ

sè ®Ó cã mét kiÓu chØ sè cña m¶ng, sau ®ã míi dïng m¶ng.

6.2.2. Cµi ®Æt b¶ng bëi danh s¸ch

1

V× mét b¶ng víi tËp chØ sè A vµ tËp gi¸ trÞ B cã thÓ xem nh- mét tËp nµo

®ã c¸c cÆp (a, b), trong ®ã a  A vµ b  B lµ gi¸ trÞ t-¬ng øng víi a. Do ®ã, ta

cã thÓ biÓu diÔn b¶ng bëi danh s¸ch c¸c cÆp (a, b).

Nãi cô thÓ h¬n, ta cã thÓ cµi ®Æt b¶ng bëi danh s¸ch c¸c phÇn tö, mçi

phÇn tö lµ mét b¶n ghi cã d¹ng :

type

element = record

index : indextype;

value : valuetype

end;

ë ®©y danh s¸ch cã thÓ ®-îc cµi ®Æt bëi mét trong c¸c c¸ch mµ ta ®· xÐt

trong ch-¬ng 3. Tøc lµ ta cã thÓ cµi ®Æt bëi danh s¸ch kÕ cËn (dïng m¶ng)

hoÆc danh s¸ch liªn kÕt. C¸c phÐp to¸n ®èi víi b¶ng ®-îc qui vÒ c¸c phÐp to¸n

t×m kiÕm, xen vµo vµ lo¹i bá trªn danh s¸ch. Râ rµng lµ, víi c¸ch cµi ®Æt ®Æt

nµy, c¸c phÐp to¸n ®èi víi b¶ng ®-îc thùc hiÖn kÐm hiÖu qu¶, v× chóng ®ßi hái

thêi gian trung b×nh tØ lÖ víi sè thµnh phÇn cña b¶ng.

NÕu cã mét thø tù tuyÕn tÝnh x¸c ®Þnh trªn tËp chØ sè cña b¶ng, ta nªn

cµi ®Æt b¶ng bëi danh s¸ch ®-îc s¾p theo thø tù ®· x¸c ®Þnh trªn tËp chØ sè.

6.2.3. Cµi ®Æt b¶ng bëi b¶ng b¨m.

Trong nhiÒu c¶nh huèng, b¶ng b¨m lµ cÊu tróc d÷ liÖu thÝch hîp nhÊt ®Ó

cµi ®Æt mét b¶ng.

ViÖc x©y dùng c¸c b¶ng b¨m (më hoÆc ®ãng) ®Ó biÓu diÔn mét b¶ng

hoµn toµn gièng nh- viÖc x©y dùng b¶ng b¨m cho tõ ®iÓn. Chóng ta chØ cÇn

l-u ý mét sè ®iÓm kh¸c sau ®©y.

C¸c hµm b¨m sÏ "b¨m" c¸c phÇn tö cña tËp chØ sè A cña b¶ng vµo c¸c

'ræ'. Tøc lµ nÕu b¶ng b¨m gåm N ræ th× hµm b¨m lµ hµm h tõ tËp chØ sè A vµo

tËp {0, 1 . . . . N-1}.

Trong b¶ng b¨m më, ®èi víi tõ ®iÓn ta cã mçi ræ lµ mét danh s¸ch c¸c

phÇn tö cña tõ ®iÓn; Cßn ®èi víi b¶ng, víi tËp chØ sè A vµ tËp gi¸ trÞ B th× mçi

ræ lµ mét danh s¸ch nµo ®ã, c¸c cÆp (a, b) trong ®ã a  A, b  B. ChÝnh x¸c

h¬n, cÊu tróc d÷ liÖu b¶ng b¨m më biÓu diÔn b¶ng ®-îc khai b¸o nh- sau :

type

pointer = ^cell;

type cell

= record

index : indextype;

value : valuetype;

next : pointer

2

end;

table = array [0 . . N-1] of pointer;

HiÓn nhiªn b¶ng b¨m ®ãng biÓu diÔn b¶ng sÏ cã cÊu tróc ®-îc m« t¶ sau

:

type

table = array [0 . . N-1] of element;

trong ®ã, element lµ b¶n ghi ®· khai b¸o trong môc 6.2.2.

Trong c¸ch cµi ®Æt b¶ng bëi b¶ng b¨m (më hoÆc ®ãng), phÐp to¸n truy

xuÊt vµ söa ®æi b¶ng chÝnh lµ phÐp t×m kiÕm trªn b¶ng b¨m theo chØ sè a  A

vµ ®äc hoÆc thay ®æi gi¸ trÞ cña tr-êng value cña b¶n ghi cã tr-êng index lµ a.

Cßn phÐp to¸n xen vµo vµ lo¹i bá trªn b¶ng lµ phÐp to¸n xen vµo vµ lo¹i bá

trªn b¶ng b¨m theo chØ sè ®· cho.

6.3. B¶ng ch÷ nhËt

Trong môc nµy chóng ta sÏ xÐt viÖc cµi ®Æt c¸c b¶ng ch÷ nhËt, tøc lµ c¸c

b¶ng mµ c¸c thµnh phÇn cña b¶ng ®-îc xÕp thµnh h×nh ch÷ nhËt gåm M hµng

vµ N cét. V× tÇm quan träng ®Æc biÖt cña c¸c b¶ng ch÷ nhËt, nªn trong hÇu hÕt

c¸c ng«n ng÷ lËp tr×nh bËc cao ®Òu cã ph-¬ng tiÖn thuËn tiÖn vµ hiÖu qu¶ ®Ó

biÓu diÔn b¶ng ch÷ nhËt, ®ã lµ m¶ng hai chiÒu. Ch¼ng h¹n, trong Pascal mét

b¶ng ch÷ nhËt M hµng vµ N cét cã khai b¸o

type

table = array [1 . . M, 1 . . N] of elementtype;

trong ®ã elementtype lµ kiÓu cña c¸c phÇn tö cña b¶ng.

C¸ch tù nhiªn nhÊt ®Ó ®äc th«ng tin trong mét b¶ng ch÷ nhËt lµ lÇn l-ît

theo hµng vµ trong mét hµng tõ tr¸i sang ph¶i. §ã còng chÝnh lµ c¸ch mµ c¸c

ch-¬ng tr×nh dÞch xÕp c¸c thµnh phÇn vµo c¸c vïng nhí liªn tiÕp cña bé nhí

trong. Do ®ã, nÕu T lµ mét TABLE vµ biÕt ®-îc ®Þa chØ cña vïng nhí l-u gi÷

thµnh phÇn T [o, ¬], ta sÏ x¸c ®Þnh ®-îc ngay ®Þa chØ cña T [i, j]. M¶ng T sÏ

®-îc giµnh riªng mét kh«ng gian nhí cè ®Þnh gåm M x N ®¬n vÞ nhí liªn tiÕp

(ë ®©y, ®¬n vÞ nhí ®-îc xem lµ vïng nhí ®Ó l-u gi÷ mét thµnh phÇn cña

m¶ng).

Trong nhiÒu bµi to¸n, ta kh«ng cÇn thiÕt ph¶i biÓu diÔn th«ng tin ë t¹i

mäi vÞ trÝ trong b¶ng. Cã thÓ xÈy ra, trong mét b¶ng chØ cã mét sè gi¸ trÞ t¹i

mét sè vÞ trÝ lµ cã nghÜa, cßn c¸c gi¸ trÞ t¹i c¸c vÞ trÝ cßn l¹i lµ b»ng nhau hoÆc

ta kh«ng cÇn quan t©m ®Õn. Ch¼ng h¹n nh- b¶ng c¸c sè nguyªn trong h×nh 6.1.

3

H×nh 6.1 Mét vÝ dô vÒ b¶ng th-a thít

B¶ng nµy chØ chøa 6 thµnh phÇn kh¸c kh«ng, cßn 14 thµnh phÇn cßn l¹i

b»ng 0. C¸c b¶ng nh- thÕ gäi lµ c¸c b¶ng th-a thít. HiÓn nhiªn nÕu cµi ®Æt c¸c

b¶ng th-a thít bëi m¶ng hai chiÒu sÏ l·ng phÝ nhiÒu bé nhí. Ch¼ng h¹n mét

ma trËn nguyªn 200 x 200, mçi hµng kh«ng cã qu¸ 4 thµnh phÇn kh¸c 0, nÕu

dïng m¶ng sÏ dïng ®Õn 80.000 byte. Trong khi ®ã, nÕu dïng ph-¬ng ph¸p

thÝch hîp, cã thÓ chØ cÇn ®Õn 1/10 kh«ng gian nhí ®ã. Sau ®©y ta sÏ nghiªn cøu

viÖc cµi ®Æt nh÷ng b¶ng cã d¹ng ®Æc biÖt.

6.3.1. B¶ng tam gi¸c vµ b¶ng r¨ng l-îc.

B¶ng tam gi¸c lµ b¶ng vu«ng (sè dßng b»ng sè cét) mµ tÊt c¶ c¸c thµnh

phÇn cã nghÜa trong b¶ng ®Òu n»m ë c¸c vÞ trÝ (i, j) víi j  i). VÝ dô b¶ng trong

h×nh 6.2a lµ b¶ng tam gi¸c, phÇn chøa th«ng tin cã nghÜa ®Òu n»m ë c¸c vÞ trÝ

(i, j) víi j  i. Víi b¶ng tam gi¸c n dßng, ta chØ cÇn l-u gi÷ 1 + 2 + . . . + n =

n (n + 1)/2 thµnh phÇn. Ta sÏ dïng mét m¶ng mét chiÒu ®Ó l-u gi÷ c¸c thµnh

phÇn cña b¶ng (h×nh 6.2b). C¸c thµnh phÇn cña b¶ng lÇn l-ît theo dßng, trong

mét dßng kÓ tõ tr¸i sang ph¶i, ®-îc l-u vµo c¸c thµnh phÇn cña m¶ng. §Ó biÕt

®-îc thµnh phÇn cña m¶ng T chøa thµnh phÇn cña b¶ng t¹i vÞ trÝ (i, j) bÊt kú, ta

®-a vµo mét m¶ng phô P. M¶ng nµy cã sè chiÒu b»ng sè dßng cña b¶ng. Víi

mçi dßng i, 1  i  n, P[i] chøa vÞ trÝ trong m¶ng T kÓ tõ ®ã ta sÏ l-u gi÷ c¸c

thµnh phÇn cña b¶ng ë dßng i (h×nh 6.2c)

4

1

2

3

4

5

1

(a)

2

b

3

c

4

d

5

e

6

f

7

8

9 10 11 12 13 14 15

a

g

h

i

k

l

m

n

o

p

(b)

1

2

3

4

5

(c)

H×nh 6.2 B¶ng tam gi¸c

Ta dÔ dµng tÝnh ®-îc c¸c gi¸ trÞ cña m¶ng P

P [1] = 0

P [2] = 1

P [3] = 2 + 1 = 3

. . . . . . . . . . .

P [] = i - 1 + P[i - 1]

BiÕt ®-îc c¸c P [i], ta x¸c ®Þnh ®-îc thµnh phÇn cña m¶ng T l-u gi÷

thµnh phÇn cña b¶ng t¹i vÞ trÝ (i, j) bÊt kú. Cô thÓ, thµnh phÇn cña b¶ng t¹i vÞ trÝ

(i, j) ®-îc l-u gi÷ t¹i vÞ trÝ P [i] + j cña m¶ng T. Ch¼ng h¹n, ký tù h ë vÞ trÝ (4,

2) trong b¶ng ®-îc l-u gi÷ ë vÞ trÝ P[4] + 2 = 6 + 2 = 8 trong m¶ng T. Nh- vËy,

ta ®· cµi ®Æt mét b¶ng tam gi¸c bëi hai m¶ng mét chiÒu T vµ P. Nh- trªn ®·

chøng tá víi c¸ch cµi ®Æt nµy ta cã thÓ truy cËp trùc tiÕp ®Õn tõng thµnh phÇn

cña b¶ng.

Mét b¶ng r¨ng l-îc lµ b¶ng ch÷ nhËt mµ trong mçi dßng c¸c th«ng tin

trong b¶ng ®-îc xÕp liªn tôc kÓ tõ cét thø nhÊt (sè phÇn tö trong mçi dßng

nhiÒu Ýt tuú ý). H×nh 6.3 minh ho¹ mét b¶ng r¨ng l-îc.

5

1

2

3

4

5

6

H×nh 6.3 Minh ho¹ mét b¶ng r¨ng l-îc

B»ng c¸ch hoµn toµn t-¬ng tù nh- ®èi víi b¶ng tam gi¸c, ta cã thÓ cµi

®Æt b¶ng r¨ng l-îc bëi hai m¶ng mét chiÒu T vµ P. C¸c thµnh phÇn cña b¶ng

r¨ng l-îc còng ®-îc xÕp vµo m¶ng T lÇn l-ît theo hµng vµ theo cét. §iÒu kh¸c

nhau duy nhÊt ë ®©y lµ, gi¸ trÞ chøa trong mçi thµnh phÇn kh¸c nhau cña m¶ng

P ®-îc x¸c ®Þnh nh- sau :

P [1] = 0,

P [i] = P [i - 1] + sè thµnh phÇn cña b¶ng ë dßng i - 1 víi mäi i > 1.

Ch¼ng h¹n, víi b¶ng trong h×nh 6.2, ta cã P [1] = 0, P [2] = 3, P [3] = 10,

[4] = 10, P [5] = 12, P [6] = 17.

P

6.3.2. B¶ng th-a thít

B¶ng th-a thít lµ b¶ng ch÷ nhËt mµ c¸c th«ng tin cã nghÜa trong b¶ng

®-îc ph©n bè mét c¸ch th-a thít, r¶i r¸c kh«ng theo mét qui luËt nµo c¶. H×nh

6.1 cho ta mét vÝ dô vÒ b¶ng th-a thít, th«ng tin chøa trong b¶ng lµ c¸c sè

nguyªn. §-¬ng nhiªn ë ®©y lµ kh«ng thÓ dïng m¶ng hai chiÒu ®Ó biÓu diÔn

mét b¶ng th-a thít, v× l·ng phÝ nhiÒu bé nhí. ta còng kh«ng thÓ dïng m¶ng

mét chiÒu ®Ó l-u gi÷ c¸c thµnh phÇn cña b¶ng nh- ta ®· lµm ®èi víi b¶ng tam

gi¸c vµ b¶ng r¨ng l-îc. Nguyªn nh©n lµ v×, c¸c thµnh phÇn cã nghi· cña b¶ng

ph©n bè kh«ng theo mét qui luËt nµo, nªn ta kh«ng thÓ ®Þnh vÞ ®-îc thµnh

phÇn cña b¶ng ë trong m¶ng mét chiÒu.

Mét ph-¬ng ph¸p tèt ®Ó cµi ®Æt c¸c b¶ng th-a thít lµ dïng c¸c danh

s¸ch liªn kÕt ®Ó biÓu diÔn c¸c hµng vµ c¸c cét cña b¶ng. Mçi thµnh phÇn cña

b¶ng ë vÞ trÝ (i, j) ®-îc ®-a vµo hai danh s¸ch : danh s¸ch c¸c thµnh phÇn cña

b¶ng ë dßng thø i vµ danh s¸ch c¸c thµnh phÇn cña b¶ng ë cét thø j. Tøc lµ mçi

thµnh phÇn cña b¶ng ®-îc biÓu diÔn bëi mét b¶n ghi cã kiÓu element ®-îc

khai b¸o nh- sau :

type

pointer = ^ element;

element = record

row : integer;

6

col : integer ;

value : valuetype;

ptrrow : pointer;

ptrcol : pointer;

end;

trong ®ã row vµ col lµ chØ sè hµng vµ cét; ptrrow vµ ptrcol lµ con trá liªn kÕt

trong danh s¸ch hµng vµ danh s¸ch cét; cßn value lµ gi¸ trÞ cña mçi thµnh

phÇn. ta sÏ biÓu diÔn mçi b¶n ghi d-íi d¹ng h×nh 6.4a. Mçi hµng vµ mçi cét

cña b¶ng ®-îc biÓu diÔn bëi danh s¸ch liªn kÕt, vßng trßn vµ cã ®Çu. §Çu cña

mçi hµng cã tr-êng col = 0, cßn ®Çu cña mçi cét cã tr-êng row = 0. Khi ®ã,

cÊu tróc d÷ liÖu biÓu diÔn b¶ng trong h×nh 6.1 ®-îc minh ho¹ trong h×nh 6.4b.

(a)

T

Mét ph-¬ng ph¸p kh¸c ®Ó cµi ®Æt mét b¶ng th-a thít lµ sö dông hai

m¶ng. Mét m¶ng hai chiÒu cã cì nh- cì cña b¶ng, m¶ng sÏ cã gi¸ trÞ lµ 1 t¹i

c¸c vÞ trÝ mµ gi¸ trÞ cña b¶ng cã ý nghÜa vµ cã gi¸ trÞ lµ 0 t¹i c¸c vÞ trÝ kh¸c. VÝ

7

dô ®Ó biÓu diÔn b¶ng trong h×nh 6.1, ta sö dông m¶ng ®-îc minh ho¹ bëi h×nh

6.5 a. Bªn c¹nh m¶ng hai chiÒu chØ chøa 1 hoÆc 0, ta sÏ sö dông mét m¶ng mét

chiÒu ®Ó l-u l¹i c¸c gi¸ trÞ cã nghÜa cña b¶ng. Ch¼ng h¹n, h×nh 6.5b minh ho¹

m¶ng mét chiÒu øng víi b¶ng trong h×nh 6.1

1

0

1

0

1

0

1

0

1

0

1

0

(a)

6

7

8

1

9

3

(b)

H×nh 6.5 M¶ng mét chiÒu øng víi b¶ng trong h×nh 6.1

HiÖu qu¶ tiÕt kiÖm bé nhí cña ph-¬ng ph¸p nµy lµ râ rµng. Ch¼ng h¹n,

®èi víi b¶ng c¸c sè nguyªn (nh- trong h×nh 6.1), thay cho viÖc sö dông m¶ng

c¸c sè nguyªn (mçi sè nguyªn cÇn 2 byte = 16 bit) ta ®· sö dông m¶ng c¸c bit.

6.4. Trß ch¬i ®êi sèng

Trong môc nµy chóng ta tr×nh bµy mét ¸p dông cña ph-¬ng ph¸p cµi ®Æt

b¶ng bëi b¶ng b¨m ®Ó gi¶i quyÕt bµi to¸n 'trß ch¬i ®êi sèng' (game of life). Trß

ch¬i ®êi sèng ®-îc nhµ to¸n häc Anh J.H Conway ®-a ra n¨m 1970.

§êi sèng cña mét céng ®ång c¸c c¬ thÓ sèng diÔn ra trªn mét l-íi «

vu«ng kh«ng giíi h¹n. Mçi « vu«ng cã thÓ cã mét c¬ thÓ sèng hoÆc kh«ng. ¤

vu«ng cã mét c¬ thÓ sèng gäi lµ tÕ bµo sèng, ng-îc l¹i lµ tÕ bµo chÕt. C¸c tÕ

bµo thay ®æi tõ thÕ hÖ nµy sang thÕ hÖ sau tuú thuéc vµo c¸c tÕ bµo sèng ë l©n

cËn. Mçi tÕ bµo h×nh vu«ng cã t¸m tÕ bµo l©n cËn tiÕp gi¸p víi tÕ bµo ®· cho

theo c¸c c¹nh vµ c¸c gãc.

C¸c tÕ bµo sÏ thay ®æi theo c¸c qui luËt sau :

1. NÕu mét tÕ bµo sèng, nh-ng sè tÕ bµo sèng l©n cËn nã kh«ng nhiÒu h¬n 1,

th× ë thÕ hÖ sau nã sÏ chÕt (chÕt v× c« ®éc)

2. NÕu mét tÕ bµo sèng, nh-ng sè tÕ bµo sèng l©n cËn nã lµ 2 hoÆc 3, th× ë thÕ

hÖ sau nã vÉn sèng.

3. NÕu mét tÕ bµo sèng, nh-ng sè tÕ bµo sèng l©n cËn nã kh«ng Ýt h¬n 4, th× ë

thÕ hÖ sau nã sÏ chÕt (chÕt v× qu¸ ®«ng!).

8

4. NÕu mét tÕ bµo chÕt vµ cã ®óng 3 tÕ bµo sèng ë l©n cËn, th× ë thÕ hÖ sau nã

sÏ trë thµnh tÕ bµo sèng. Trong tr-êng hîp cßn l¹i, mét tÕ bµo chÕt vÉn cßn

chÕt ë thÕ hÖ sau.

5. Trong mçi thÕ hÖ, sù sinh ra vµ chÕt ®i diÔn ra ®ång thêi, kh«ng ¶nh h-ëng

®Õn nhau.

Sau ®©y ta sÏ xÐt sù ph¸t triÓn cña mét sè céng ®ång tÕ bµo mµ thÕ hÖ

®Çu tiªn ®-îc cho trong c¸c h×nh 6.6 (dÊu chÐo ®¸nh dÊu tÕ bµo sèng). Céng

®ång trong h×nh 6.6a sÏ biÕn mÊt sau mét thÕ hÖ , v× c¶ hai tÕ bµo cïng chÕt do

c« ®éc. Céng ®ång trong h×nh 6.6 b sÏ æn ®Þnh tõ thÕ hÖ nµy sang thÕ hÖ kh¸c,

v× kh«ng cã tÕ bµo nµo sinh ra còng kh«ng cã tÕ bµo nµo chÕt ®i. Sù ph¸t triÓn

cña céng ®ång trong h×nh 6.6c giµnh cho b¹n ®äc.

x

(a)

(b)

x

(c)

H×nh 6.6 ThÕ hÖ ®Çu tiªn cña mét sè céng ®ång tÕ bµo

Chóng ta cã thÓ thÊy r»ng, tõ nh÷ng c¶nh huèng ban ®Çu nhá bÐ, mét sè

céng ®ång cã thÓ ph¸t triÓn thµnh nh÷ng céng ®ång réng lín, mét sè céng

®ång cã thÓ thay ®æi vµ èn ®Þnh sau mét sè thÕ hÖ, hoÆc cã thÓ lÆp ®i lÆp l¹i

mét sè c¶nh huèng nµo ®ã; mét sè kh¸c cã thÓ mÊt ®i.

9

Sau khi ra ®êi kh«ng l©u, trß ch¬i ®êi sèng ®· ®-îc Martin Gardner bµn

tíi trong b¸o 'Scientific American'. Tõ ®ã nã ®· thu hót sù chó ý cña nhiÒu

ng-êi.

Trß ch¬i ®êi sèng lµ mét bµi tËp lËp tr×nh rÊt hay cho nh÷ng ng-êi míi

häc lËp tr×nh vµ cho c¶ nhu÷ng ai ®· n¾m ®-îc nh÷ng cÊu tróc d÷ liÖu phøc

t¹p.

§Çu tiªn ta cã thÓ nghÜ ngay ®Õn dïng mét m¶ng ch÷ nhËt kh¸ lín ®Ó

biÓu diÔn c¸c thÕ hÖ cña mét céng ®ång tÕ bµo. M¶ng sÏ cã gi¸ trÞ lµ 1 t¹i c¸c

vÞ trÝ cña c¸c tÕ bµo sèng vµ 0 øng víi c¸c tÕ bµo chÕt. §Ó x¸c ®Þnh ®-îc sù

thay ®æi cña c¸c tÕ bµo tõ thÕ hÖ nµy sang thÕ hÖ kh¸c, ta chØ cÇn ®Õm sè tÕ bµo

sèng l©n cËn mçi tÕ bµo vµ ¸p dông c¸c luËt tõ 1) ®Õn 4). C¶nh huèng cña thÕ

hÖ tiÕp theo ®-îc ghi vµo mét m¶ng míi. Ta dÔ dµng viÕt ®-îc l-îc ®å ch-¬ng

tr×nh thùc hiÖn ph-¬ng ¸n trªn.

program LifeGame;

const

N = . . . ;

M = . . . ;

type

row = 1 . . N;

col = 1 . . M;

{hµng cña m¶ng}

{cét cña m¶ng}

status = (alive, dead)

{mçi tÕ bµo ë mét trong hai tr¹ng th¸i

(status ) : sèng (aive) vµ chÕt (dead)}

Table = array [row, col] of status;

var

T, new T : Table

i : row;

j : col;

again : boolean;

{Sau ®©y m« t¶ c¸c thñ tôc vµ hµm}

procedure Initiation (var T : Table);

{®-a vµo b¶ng ban ®Çu}

function

Count (i, j : integer) : 0 . . 8;

{®Õm sè tÕ bµo sèng l©n cËn tÕ bµo ë vÞ trÝ (i, j)}

procedure copy (new T : Table; v¶ T : Table);

10

{sao chÐp m¶ng new T sang m¶ngT}

begin

Initiation (T);

WriteTable (T);

repeat

for i : = 1 to N do

for j : = 1 to M do

case count (i, j) of

0,1 :

2 :

3 :

new T [i, j] : = dead;

new T [i, j] : = T [i, j];

new T [i, j] : = alive;

4, 5, 6, 7, 8 :new T[i, j] : = dead

end;

Copy (new T, T);

WriteTable (T);

Readln (again);

not again

until

end.

B¹n ®äc dÔ dµng viÕt ®-îc c¸c thñ tôc vµ hµm trong ch-¬ng tr×nh trªn.

Riªng ®èi víi hµm count, ta cÇn l-u ý r»ng, ®Ó tÝnh ®-îc sè tÕ bµo sèng l©n cËn

mét tÕ bµo ta chØ cÇn xÐt 8 tÕ bµo l©n cËn víi tÕ bµo ®· cho, nÕu nã ë gi÷a

b¶ng. Cßn nÕu nã ë r×a b¶ng th× sè tÕ bµo l©n cËn nã sÏ kh«ng ph¶i thÕ.

B©y giê ta h·y xÐt nh÷ng -u tiªn vµ h¹n chÕ cña ch-¬ng tr×nh trªn. ¦u

®iÓm cña ch-¬ng tr×nh trªn lµ ®¬n gi¶n vµ dÔ hiÓu. Song nã cã nhiÒu nh-îc

®iÓm. Tr-íc hÕt ta ®· sö dông m¶ng ®Ó m« t¶ c¶nh huèng cña c¸c thÕ hÖ tÕ bµo

tøc lµ ta ®· ®ãng khung chØ xÐt sù ph¸t triÓn cña céng ®ång tÕ bµo trong ph¹m

vi m¶ng. Trªn thùc tÕ tõ c¶nh huèng ban ®Çu, mét céng ®ång cã thÓ sÏ ph¸t

triÓn v-ît qu¸ giíi h¹n cña m¶ng, chØ sau mét sè thÕ hÖ. Ta còng ®· xÐt l-íi tÕ

bµo nh- mét b¶ng ch÷ nhËt ®Çy (mçi thµnh phÇn cña b¶ng ®Òu chøa th«ng tin),

song thùc ra, ta cã mét b¶ng th-a thít, v× kh«ng cÇn xÐt tíi c¸c tÕ bµo chÕt mµ

lµm l·ng phÝ nhiÒu thêi gian, v× kh«ng ph¶i tÊt c¶, mµ chØ cã mét sè tÕ bµo cã

11

cËn mçi tÕ bµo. Tøc lµ

var

LiveNeighbors : array [row, col] of 0 . . 8;

Khi ®ã, tõ thÕ hÖ nµy sang thÕ hÖ kh¸c, ta chØ cÇn x¸c ®Þnh l¹i c¸c gi¸ trÞ

cña m¶ng LiveNeighbors t¹i c¸c tÕ bµo kÒ víi c¸c tÕ bµo tõ sèng thµnh chÕt

hoÆc tõ chÕt thµnh sèng. Nh- vËy thay cho hµm Count, ta sö m¶ng

LiveNeighbors. B¹n ®äc h·y viÕt ch-¬ng tr×nh thùc hiÖn ®Ò ¸n nµy. Ch-¬ng

tr×nh nµy vÉn ch-a ph¶i lµ ch-¬ng tr×nh tèt, v× ta cßn ph¶i ®i qua toµn bé m¶ng

LiveNeighbors ®Ó ph¸t hiÖn ra c¸c tÕ bµo sÏ sinh hoÆc sÏ chÕt ®i ë thÕ hÖ sau.

Cßn cã nhiÒu c¸ch ®Ó c¶i tiÕn ch-¬ng tr×nh (bµi tËp)

Nh- trªn ®· nãi, viÖc sö dông m¶ng ®Ó m« t¶ c¸c thÕ hÖ tÕ bµo lµ kh«ng

thÝch hîp, nã kh«ng ph¶n ¸nh ®Çy ®ñ sù ph¸t triÓn cña c¸c céng ®ång tÕ bµo.

CÇn ph¶i xÐt b¶ng c¸c tÕ bµo lµ mét b¶ng v« h¹n, trong ®ã t-¬ng øng voÝ mçi

vÞ trÝ (i, j) lµ mét tÕ bµo ®-îc hoµn toµn x¸c ®Þnh bëi vÞ trÝ cña nã vµ sè c¸c tÕ

sÏ 'b¨m' c¸c vÞ trÝ (i; j) cña c¸c tÕ bµo vµo c¸c vÞ trÝ 0, 1, . . , N-1 cña b¶ng b¨m.

h : {(i; j) (i; j) vÞ trÝ cña tÕ bµo}  {0, 1, . . . , N-1}

Mçi tÕ bµo sÏ ®-îc ®-a vµo danh s¸ch liªn kÕt c¸c tÕ bµo thuéc mét 'ræ'

nµo ®ã cña b¶ng b¨m. Do ®ã mçi tÕ bµo ®-îc m« t¶ bëi cÊu tróc b¶n ghi sau

type cell = record

row,

col : integer;

state : (alive, dead);

count : 0 . . 8;

next : ^ cell;

end;

Table = array [0 . . N-1] of ^ cell;

Khi muèn x¸c ®Þnh c¸c tÕ bµo sÏ sèng hoÆc sÏ chÕt ë thÕ hÖ sau, ®Ó

tr¸nh ph¶i xem xÐt toµn bé b¶ng b¨m, ta ®-a vµo hai danh s¸ch. Danh c¸ch

®æi so víi ë thÕ hÖ tr-íc; do ®ã, danh s¸ch Change sÏ chøa c¸c tÕ bµo ®ang

sèng sÏ trë thµnh chÕt hoÆc ®ang chÕt sÏ trë thµnh sèng ë thÕ hÖ sau. Danh

cã thay ®æi so víi thÕ hÖ hiÖn t¹i.

12

Chóng ta cã thÓ ®-a thªm vµo mçi b¶n ghi biÓu diÔn tÕ bµo hai con trá.

Mét con trá ®Ó liªn kÕt c¸c tÕ bµo thuéc danh s¸ch Change vµ mét con trá ®Ó

liªn kÕt c¸c tÕ bµo thuéc danh s¸ch NextChange. Nh- vËy mçi b¶n ghi tÕ bµo

sÏ cã 3 tr-êng con trá. §iÒu nµy sÏ tiªu tèn nhiÒu kh«ng gian nhí, v× cã thÓ chØ

cã mét sè Ýt tÕ bµo ®-îc ®-a vµo hai danh s¸ch nµy. Do ®ã c¸ch tèt h¬n lµ ta sÏ

®-a c¸c con trá trá ®Õn c¸c tÕ bµo thuéc danh s¸ch Change (NextChange) vµo

danh s¸ch Change (NextChange) thay cho viÖc ®-a chÝnh c¸c tÕ bµo thuéc

danh s¸ch Change(NextChange) vµo danh s¸ch Change (NextChange). Nãi

mét c¸ch kh¸c, danh s¸ch Change vµ NextChange sÏ lµ c¸c danh s¸ch liªn kÕt,

gåm c¸c b¶n ghi cã cÊu tróc sau

type

node = record

entry : ^ cell;

next : ^ node;

end;

Mçi khi cÇn x¸c ®Þnh c¶nh huèng cña mét céng ®ång tÕ bµo ë mét thÕ

hÖ nµo ®ã, ta ®i qua danh s¸ch Change. Khi gÆp tÕ bµo tõ tr¹ng th¸i chÕt trë

thµnh sèng (hoÆc tõ tr¹ng th¸i sèng trá thµnh chÕt), ta chØ cÇn thay ®æi tr-êng

state cho nã nhËn gi¸ trÞ alive (hoÆc dead) ®ång thêi ta sÏ t×m trong b¶ng b¨m

tõ sèng trë thµnh chÕt) th× tr-êng count ®-îc t¨ng lªn 1 (hoÆc ®-îc gi¶m ®i 1).

Qu¸ tr×nh trªn ®-îc thùc hiÖn bëi thñ tôc Traverse (qua ®i).

Chóng ta cã ph¸c th¶o ch-¬ng tr×nh sau :

program

const

LifeGame;

; {N lµ sè thµnh phÇn cña b¶ng b¨m}

N =

type

ptrcell = cell {con trá liªn kÕt c¸c tÕ bµo trong c¸c danh

s¸ch míi cña b¶ng b¨m}

cell = record

row,

col : integer, {vÞ trÝ cña tÕ bµo}

satate : (alive, dead) {tr¹ng th¸i cña tÕ bµo}

13

next : ptrcell

end;

ptrnode = ^ node; {con trá liªn kÕt trong danh s¸ch Change vµ

NextChange}

node = record

entry : ptrcell;

next : ptrnode

end;

Table = array [0 , , N-1] of ptrcell;

var

T : Table;

Change, NextChange : ptrnode;

again : boolean;

procedure Initiation (var T : Table; var Change : ptrnode);

(ban ®Çu Change lµ danh s¸ch c¸c tÕ bµo ®ang chÕt sÏ thµnh sèng vµ ®ang sèng

sÏ thµnh chÕt) øng víi c¶nh huèng ban ®Çu}.

procedure Traverse (var Change, NextChange : ptrnode);

b¶ng NexChange}.

procedure WriteTable (var T : Table);

{viÕt ra b¶ng T}

begin {ch-¬ng tr×nh chÝnh}

Initiation (T, Change);

repeat

Traverse (Change, NextChange);

WriteTable;

Change : = NextChange;

readln (again)

until not again

end.

14

Initiation vµ WriteTable ®-îc ®Ó l¹i xem nh- bµi tËp.

thµnh sèng, (hoÆc sèng trë thµnh chÕt), ta ph¶i t×m xem trong b¶ng b¨m ®· cã

tÕ bµo ë vÞ trÝ (i, j) ch-a, nÕu ch-a th× ®-a nã vµo b¶ng b¨m (víi tr-êng state lµ

dead vµ tr-êng count b»ng 1), ta sÏ dïng biÕn con trá q ghi l¹i ®Þa chØ cña tÕ

bµo ë vÞ trÝ (i, j). Qu¸ tr×nh trªn ®-îc thùc hiÖn b»ng thñ tôc

GetTable (i, j : integer; var q : ptrcell)

Chóng ta sÏ sö dông thñ tôc

Add (q : ptrcell; var NextChange : ptrnode)

®Ó ®-a q vµo danh s¸ch NextChange.

Chóng ta cã thÓ m« t¶ thñ tôc Traverse nh- sau :

procedure

Traverse;

var

p, p1 : ptrnode;

i, j : integer;

q : ptrcell;

procedure

GetTable (i, j : integer; var q : ptrcell);

Add (q : ptrcell; var NextChange : ptrnode);

begin {b¾t ®Çu thñ tôc Traverse}

p : = Change;

NextChange : = nil;

while p < > nil do

begin

with p ^ do

with entry ^ do

begin

if (state = dead) and (count = 3) then

begin

state : = alive;

for i : = row -1 to row + 1 do

for j : = col - 1 to col + 1 do

15

if (i <> row) and (j < > col) then

GetTable (i, j, q);

begin

q ^. count : = q ^. count + 1;

Add (q, NextChange)

end

else

if (state = alive) and ( (count < = 1) or (count > = 4) )

then bigin

state : = dead;

for i : = row - 1 to row + 1 do

for j : = col - 1 to col + 1 do

if (i < > row) and (j < > col) then

begin

Get Table ( i, j, q);

q ^. count : = q ^. count - 1;

Add (q, NextChange)

end

end; {hÕt lÖnh with}

p 1 : = p;

p : = p ^ . next;

dispose (p1);

end {hÕt vßng lÆp while}

end; {hÕt thñ tôc Traverse}

Trong ch-¬ng tr×nh LifeGame, ta ®· dïng danh s¸ch Change ghi l¹i c¸c

thÕ hÖ tr-íc. Chóng ta cÇn ph¶i ®i qua danh s¸ch Change ®Ó t×m c¸c tÕ bµo

®ang chÕt sÏ trë thµnh sèng vµ ®ang sèng sÏ trë thµnh chÕt ë thÕ hÖ sau. Do ®ã

nÕu chóng ta sö dông hai danh s¸ch BecomeLive ghi l¹i c¸c tÕ bµo chÕt cã kh¶

n¨ng thµnh sèng vµ BecomeDead ghi l¹i c¸c tÕ bµo sèng cã kh¶ n¨ng thµnh

16

chÕt th× ta sÏ thu hÑp ®-îc ph¹m vi c¸c tÕ bµo cÇn xem xÐt. Chóng t«i ®Ó l¹i

cho b¹n ®äc tiÕp tôc ph¸t triÓn vµ viÕt ch-¬ng tr×nh thùc hiÖn ®Ò ¸n nµy.

17

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