Chương 6 - BẢNG

Chia sẻ: Ngo DUC HAI | Ngày: | Loại File: DOC | Số trang:0

Thêm vào BST

Báo xấu

87
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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....

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Chương 6 - BẢNG

154 ¬ng Ch 6 B¶ng Trong ch¬ng ícchóng nghiªncøu tr ta ®∙ m« h×nh liÖu tËp d÷ hîp vµ mét kiÓu liÖutrõut sè d÷ îng (tõ®iÓn,hµng tiªn) îcx©y u ® dùng trªn c¬ kh¸iniÖm së tËp hîp.Trong ch¬ng nµy chóng ta sÏnghiªncøu kiÓu d÷ liÖu trõu t îng b¶ng îcx©y ® dùng së trªncë kh¸iniÖm hµm (¸nh x¹). Chóng ta còng sÏxÐt viÖc Æt cµi® mét êng Æc tr hîp ® biÖtcña b¶ng, ®ã lµc¸cb¶ng ch÷ nhËt. 6.1.KiÓu liÖu d÷ trõu îng t b¶ng : Tr íc hÕt chóng ta nh¾c i l¹ kh¸iniÖm hµm trong to¸n häc. Nhí l¹i r»ng,mét quan hÖ R tõ tËp ®Õn A tËp lµ mét B tËp con nµo cña ®ã A B, lµmét hîp nµo c¸ccÆp ∈ tÝch ®ªcac x tøc lµR tËp ®ã (a,b) víia ∈ A, b B. Mét hµm → (flµhµm ®Õn lµmét f:A B tõA B) quan ftõA hÖ ®Õn sao B cho (a,b) ∈ (a,c)∈ = nÕu fvµ fth× b c.Tøc lµ,quan flµ hÖ mét hµm, nÕu kh«ng nã chøa c¸ccÆp ≠ (a,b),(a,c)víi b c.NÕu (a,b) ∈ lµgi¸trÞcña f, tanãib th× hµm vµ hiÖu = ft¹ a ký i lµf(a), f(a). b TËp hîp tÊtc¶ ∈ sao c¸ca A, tån t¹ cÆp ∈ îcgäilµmiÒn cho i (a,b) f,® x¸c ®Þnh cña hµm ký fvµ hiÖu lµDom .(f) Cã nh÷ng hµm, ch¼ng hµm ex,ta cã h¹n f(x)= thuËtto¸n®Ó x¸c ®Þnh gi¸trÞcña hµm f(x) mçi x.Víinh÷ng víi hµm thÕ thÓ nh ta cã cµi ® Æt bëi c¸c hµm trong PascalhoÆc Tuy C. nhiªn cã rÊt nhiÒu hµm. Ch¼ng h¹n hµm cho ¬ng t øng mçi nh©n viªn lµm viÖc trong mét c¬ quan ¬ng víil hiÖn it¹ cña ngêi®ã, ta chØ thÓ cã m« t¶ bëib¶ng ¬ng. l Trong êng thÕ,®Ó c¸ctr hîp nh m« t¶mét hµm → ta ph¶il gi÷ f:A B, u mét m« t¶ c¸cth«ng c¸c®èi t ∈ vµ b¶ng tinvÒ îng a A c¸cth«ng tinvÒ c¸c®èit ∈ t îngb B ¬ng øng víimçi a. Mét b¶ng chØ A tËp lµmét víitËp sè vµ gi¸trÞB hµm fnµo tõ ®ã A ®Õn cïngvíi B phÐp c¸c to¸nsau ®©y : 1.Truy xuÊt:víi chØ cho íca sè tr thuéc miÒn x¸c®Þnh cña hµm, t×m ragi¸trÞcña hµm t¹ a. i 2. Söa ®æi :víi chØ cho íca sè tr thuéc miÒn x¸c®Þnh cña hµm, thaygi¸trÞcña hµm bëimét t¹ a i gi¸trÞkh¸ccho íc. tr 3.Xen vµo :thªm vµo miÒn x¸c®Þnh cña hµm mét chØ míivµ sè x¸c®Þnh gi¸trÞcña hµm t¹ ®ã. i 4. Lo¹ibá i :lo¹ mét chØ nµo kháimiÒn sè ®ã x¸c®Þnh cña hµm cïngvíi trÞcña gi¸ hµm t¹ ®ã. i 154
155 §èi víib¶ng, c¸c phÐp to¸n truy xuÊt vµ söa ®æi lµ quan träng nhÊt.Th«ng êng th trongc¸c¸p dông,khi®∙ u l gi÷mét b¶ng,tachØ cÇn ®Õn viÖc truyxuÊt th«ng tintõ b¶ng söa vµ ®æi th«ng tintrong b¶ng. Tuy nhiªntrong mét ¸p dông sè ta ph¶icÇn ®Õn c¸cphÐp to¸nxen vµo vµ lo¹ bá. i Sau ®©y chóng ® a mét dô ta ra vÝ vÒ b¶ng. Mét ma trËn m hµng, n = ij thÓ cétB [b] cã xem mét nh b¶ng.TËp chØ A ®©y sè ë lµ tËp c¸ccÆp , 1, 2, .. .,M j= . .N. (i víi = . vµ 1, 2, .. . NÕu j) i . , ma trËn lµ ma trËn c¸csè nguyªn,ta cã thÓ xÐt ma trËn nh mét hµm ftõ tËp chØ sè ®Õn c¸csè tËp nguyªn,trong®ã (i j)= ij F , b .sau nµy chóng tasÏgäi c¸c b¶ng mµ tËp chØ lµ tËp sè c¸ccÆp , 1, 2, .. j= (i víii= .M vµ 1, j) , 2,.. .N . lµc¸cb¶ng , ch÷ nhËtcã M hµng N vµ cét. 6.2.Cµi Æt ® b¶ng : 6.2.1Cµi Æt ® b¶ng bëim¶ng : Gi¶ tËp sö chØ cña sè b¶ng lµ mét kiÓu ®¬n thÓ cã dïng lµm kiÓu chØ cña sè mét m¶ng. Trong PascalkiÓu chØ cña sè m¶ng thÓ cã lµmiÒn con cña nguyªn,ch¼ng ..1000;cã c¸csè h¹n 1 thÓ lµkiÓu ký tù hoÆc miÒn con cña kiÓu tù,ch¼ng ký h¹n , thÓ 'A'. . 'Z' cã lµ mét kiÓu liÖtkª ho¨ch miÒn con cña kiÓu liÖtkª nµo ®ã. Trong êng tr hîp nµy,ta cã thÓ biÓu diÔn b¶ng bëim¶ng. §Ó chØ r»ng,t¹ imét chØ sè nµo hµm ®ã kh«ng x¸c®Þnh, ta ® a thªm vµo mét gi¸trÞ míiundefined (kh«ng x¸c®Þnh) kh¸cvíi c¸cgi¸trÞthuéctËp c¶ tÊt gi¸trÞcña b¶ng.T¹i c¸c chØ mµ sè hµm kh«ng x¸c ®Þnh, ta sÏg¸n cho c¸c thµnh phÇn cña m¶ng t¹ c¸cchØ ®ã i sè gi¸trÞundefined. Ta thÓ cã khaib¸o kiÓu b¶ng sau nh : type table= array[indextype] valuetype; of {indextype lµ kiÓu chØ sè, valuetupe kiÓu lµ gi¸ trÞ cña b¶ng bao gåm gi¸trÞundefine} . varT :table; i:indextype; Gi¶ value1,value2 lµchØ ®Çu cuèicïng,khi®ã sö sè tiªnvµ viÖc khëit¹omét b¶ng rçng (¸nhx¹kh«ng x¸c®Þnh kh¾p îcthùc hiÖn n¬i)® bëilÖnh For i:= value1tovalue2do T undefined; [i:= ] ViÖc Æt cµi® b¶ng bëim¶ng cho phÐp ta truycËp trùctiÕp ®Õn mçi thµnh phÇn cña b¶ng.c¸cphÐp to¸n®èi víib¶ng îcthùc hiÖn ® rÊt 155
dÔ dµng (b¹n ®äc thÓ cã thÊy ngay cÇn ph¶ilµm chØ g×) vµ ®ßi hái mét thêigian 0 (1).CÇn chó r»ng,nÕu ý tËp chØ cña sè b¶ng kh«ng thÓ dïng lµm kiÓu chØ cña sè m¶ng, nhng thÓ ho¸ bëimét cã m∙ kiÓu chØ nµo cña sè ®ã m¶ng, th× ta còng thÓ Æt cã cµi® b¶ng bëim¶ng. Qu¸ tr×nhcµi® Æt gåm haigiai®o¹n,®Çu ho¸ tËp tiªnlµm∙ chØ ®Ó sè cã mét kiÓu chØ cña sè m¶ng,sau míidïng m¶ng. ®ã 6.2.2.Cµi Æt ® b¶ng bëi danh s¸ch V× mét b¶ng chØ A tËp cã víitËp sè vµ gi¸trÞB thÓ xem mét nh tËp ®ã (a,b),trong ®ã ∈ vµ ∈ lµgi¸trÞt nµo c¸ccÆp a A b B ¬ng øng víi ®ã, tacã Do thÓ a. biÓu diÔn b¶ng bëidanh s¸chc¸ccÆp (a,b). Nãi cô thÓ h¬n, ta cã thÓ Æt cµi® b¶ng bëidanh s¸ch c¸c phÇn tö,mçi phÇn tölµmét b¶n d¹ng : ghicã type element= record index:indextype; value:valuetype end; ë ®©y danh s¸ch cã thÓ îccµi® Æt ® bëimét trongc¸cc¸ch mµ ta ®∙ xÐt trong ch¬ng 3. Tøc thÓ Æt lµ ta cã cµi® bëi danh s¸ch kÕ cËn (dïngm¶ng) hoÆc danh s¸chli phÐp ªn kÕt.C¸c to¸n®èivíi b¶ng îcqui ® vÒ c¸cphÐp to¸nt×m kiÕm, xen vµo lo¹ trªndanh vµ i bá s¸ch.Râ rµng lµ,víic¸ch cµi® Æt Æt ® nµy,c¸c phÐp to¸n®èi víib¶ng îcthùc hiÖn ® kÐm hiÖu qu¶,v× chóng ®ßi háithêigian trungb×nh lÖ thµnh tØ víi sè phÇn cña b¶ng. NÕu mét cã thø tùtuyÕn tÝnh x¸c®Þnh chØ cña trªntËp sè b¶ng, tanªn Æt cµi® b¶ng bëidanh s¸ch® îcs¾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 liÖu thÝch trócd÷ hîp nhÊt®Ó Æt cµi® mét b¶ng. ViÖc x©y dùng c¸cb¶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 tachØ cÇn u mét ®iÓm l ý sè kh¸csau ®©y. C¸c hµm b¨m sÏ"b¨m"c¸cphÇn töcña chØ A tËp sè cña b¶ng vµo c¸c 'ræ'. Tøc lµ nÕu b¶ng b¨m gåm th× hµm N ræ b¨m lµ hµm tõ tËp h chØ A sè vµo {0,1 tËp ....N1}. Trong b¶ng b¨m më, ®èi víi ®iÓn mçi ræ tõ tacã lµmét danh s¸ch c¸c phÇn tö cña tõ ®iÓn; Cßn ®èi víib¶ng,víitËp chØ A tËp sè vµ gi¸ 156
157 trÞB lµmét th× mçi ræ danh s¸ch nµo ®ã, (a,b) trong ®ã ∈ c¸ccÆp a ∈ A, b B. ChÝnh x¸ch¬n,cÊu liÖub¶ng trócd÷ b¨m më biÓu diÔn b¶ng ® îckhaib¸o nh sau : type pointer ^cel ; = l type cell = record index:indextype; value:valuetype; next: pointer end; table= array[0..N1]ofpointer ; HiÓn nhiªnb¶ng b¨m ®ãng biÓu diÔn b¶ng cÊu îcm« sÏcã tróc® t¶sau : type table= array[0..N1]ofelement; trong®ã, elementlµb¶n khaib¸o trongmôc ghi®∙ 6.2.2. Trong c¸ch cµi ® Æt b¶ng bëi b¶ng b¨m (më hoÆc ®ãng),phÐp to¸ntruyxuÊtvµ söa ®æi b¶ng chÝnh lµphÐp t×m kiÕm trªnb¶ng b¨m theo sè ∈ vµ chØ a A ®äc hoÆc thay ®æi gi¸trÞ cña êng tr value cña b¶n tr ghicã êng index lµa. Cßn phÐp to¸nxen vµo lo¹ bá vµ i trªnb¶ng lµphÐp to¸nxen vµo lo¹ bá vµ trªnb¶ng i 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 Æt cµi® 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 N tÇm vµ cét.V× quan träng ® Æc biÖtcña c¸cb¶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 hiÖu tiÖn vµ qu¶ ®Ó biÓu diÔn b¶ng ch÷ nhËt,®ã lµ m¶ng hai chiÒu.Ch¼ng h¹n,trong Pascalmét b¶ng ch÷ nhËt M hµng vµ cétcã N khaib¸o type table= array[1..M, ..N] 1 ofelementtype; trong®ã elementtypelµkiÓu cña c¸cphÇn töcña b¶ng. C¸ch tù nhiªnnhÊt ®Ó ®äc th«ng tintrong mét b¶ng ch÷ nhËt lµ lÇn îttheo l hµng trong mét vµ hµng tõ tr¸sang i ph¶i.§ã còng chÝnh lµ c¸ch mµ c¸cch¬ng tr×nh dÞch xÕp c¸cthµnh phÇn vµo c¸cvïng nhíli ªn tiÕpcña nhítrong.Do bé ®ã, nÕu lµmét T TABLE biÕt® îc®Þa vµ chØ cña vïng nhí l gi÷ thµnh u phÇn [o,¬],ta sÏ x¸c ®Þnh îc ngay T ® ®Þa chØ cña [i j] M¶ng sÏ® îcgiµnh T , . T riªngmét kh«ng gian nhí cè ®Þnh 157
gåm N M x ®¬n nhíli vÞ ªntiÕp (ë ®©y, ®¬n nhí® îcxem vÞ lµvïng nhí ®Ó u l gi÷mét thµnh phÇn cña m¶ng). Trong nhiÒu bµito¸n, kh«ng ta cÇn thiÕtph¶ibiÓu diÔn th«ng tin ë i t¹ mäi trÝ trong b¶ng.Cã vÞ thÓ xÈy ra,trong mét b¶ng chØ mét cã sè gi¸trÞt¹ mét vÞ nghÜa, cßn trÝcßn i sè trÝlµcã c¸cgi¸trÞt¹ c¸cvÞ i l¹ ilµ b»ng nhau hoÆc kh«ng ta cÇn quan t©m ®Õn. Ch¼ng h¹n nh b¶ng nguyªntrongh×nh c¸csè 6.1. 6 7 0 0 0 0 0 0 0 0 0 8 0 1 9 3 0 0 0 0 H×nh 6.1Mét dô b¶ng a t vÝ vÒ th thí B¶ng nµy chØ chøa thµnh phÇn 6 kh¸ckh«ng,cßn thµnh 14 phÇn cßn l¹ b»ng b¶ng thÕ i 0.C¸c nh gäilµc¸cb¶ng a .HiÓn th thít nhiªnnÕu cµi® Æt c¸cb¶ng a th thít m¶ng bëi haichiÒu sÏl∙ngphÝ nhiÒu nhí. bé Ch¼ng h¹n mét ma trËn nguyªn 200 x 200, mçi hµng kh«ng qu¸ 4 cã thµnh phÇn kh¸c0, 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 thÓ hîp,cã chØ cÇn ®Õn 1/10 kh«ng gian nhí ®ã. Sau ®©y ta sÏ nghiªn cøu viÖc Æt cµi ® nh÷ng b¶ng cã d¹ng ® Æc biÖt. 6.3.1. B¶ng tam b¶ng gi¸cvµ r¨ng îc. l B¶ng tam gi¸clµb¶ng vu«ng (sè dßng b»ng cét)mµ c¸c sè tÊtc¶ thµnh phÇn nghÜa cã trongb¶ng ®Òu ë trÝ(i j) j≤ n»m c¸cvÞ i) VÝ , víi . 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 ë trÝ (i víij≤ n»m c¸cvÞ , i.Víib¶ng j) tam dßng,ta gi¸cn chØ cÇn u + + n n 1)/2thµnh phÇn.Ta l gi÷ 1 2 ...+ = (n+ sÏdïng mét m¶ng mét chiÒu u ®Ó l 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 îttheo l dßng, trong mét dßng tõ tr¸sang kÓ i 158
159 ph¶i, îcl vµo u ® c¸cthµnh phÇn cña m¶ng. §Ó îcthµnh biÕt® phÇn cña m¶ng chøa T thµnh phÇn cña b¶ng trÝ(i j)bÊt kú,ta® a t¹ vÞ , vµo i mét m¶ng phô M¶ng P. nµy sè cã chiÒu b»ng dßng sè cña b¶ng. Víimçi dßng ≤ i≤ n,P[i] i, 1 chøa trÝtrongm¶ng kÓ tasÏl gi÷c¸c vÞ T tõ®ã u thµnh phÇn cña b¶ng dßng ë i(h×nh 6.2c) 1 a 2 b c 3 d e f (a) 4 g h i 5 m l n o 1 2 5 6 7 9 3 4 8 10 11 12 13 14 15 a b c d e f g h i k l m n o p (b) 1 3 6 0 2 5 1 3 4 (c) H×nh 6.2B¶ng tam gi¸c Ta dµng dÔ tÝnh îcc¸cgi¸trÞcña ® m¶ng P P 0 [1]= P 1 [2]= P 2 1 3 [3]= + = . . . . . . . . . . . 159
P i1 P[i1] [] + = BiÕt ® îcc¸cP ]ta x¸c®Þnh îcthµnh [i , ® phÇn cña m¶ng l gi÷ T u thµnh phÇn cña b¶ng i trÝ (i t¹ vÞ , bÊt j) kú. Cô thÓ, thµnh phÇn cña b¶ng trÝ(i j)® îcl gi÷t¹ vÞ [i + t¹ vÞ , u trÝP jcña i i ] m¶ng T. Ch¼ng h¹n, ký ë trÝ(4,2) trongb¶ng îcl gi÷ë trÝP[4]+ = + = tùh vÞ ® u vÞ 2 6 2 8 trong m¶ng Nh T. vËy, ta ®∙ Æt cµi® mét b¶ng tam gi¸cbëi hai m¶ng mét chiÒu vµ Nh chøng T P. trªn®∙ tá víic¸ch cµi® Æt nµy thÓ ta cã truycËp trùctiÕ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 tintrong b¶ng îcxÕp ªntôckÓ nhÊt (sè phÇn ® li tõ cétthø tö trong mçi dßng nhiÒu Ýt tuúý).H×nh 6.3minh ho¹mét b¶ng îc. r¨ngl 1 a b 2 d e f i g h 3 4 l m 5 o n p q 6 t s u H×nh 6.3Minh ho¹mét b¶ng îc r¨ngl B»ng c¸ch hoµn toµn ¬ng ®èi t tù nh víib¶ng tam gi¸c,ta cã thÓ cµi® Æt b¶ng îcbëihaim¶ng r¨ng l mét chiÒu vµ C¸c T P. thµnh phÇn cña b¶ng r¨ng l îc còng îc xÕp ® vµo m¶ng lÇn îttheo T l hµng theo vµ cét.§iÒu kh¸c nhau duy nhÊt ®©y ë lµ,gi¸trÞ chøa trong mçi thµnh phÇn kh¸cnhau cña m¶ng ® îcx¸c®Þnh sau P nh : P 0, [1]= P P sè [i = [i 1]+ thµnh ] phÇn cña b¶ng dßng víi ë i1 mäi 1. i> Ch¼ng h¹n,víib¶ng trongh×nh P 0,P 3,P 10, 6.2,tacã [1]= [2]= [3]= P 10,P 12,P 17. [4]= [5]= [6]= 6.3.2. B¶ng thít tha B¶ng a tlµ b¶ng th thí ch÷ nhËt mµ c¸c th«ng nghÜa tincã trong b¶ng îcph©n mét ® bè c¸ch th thí a tr¶ir¸ckh«ng , theo mét quiluËtnµo c¶. H×nh cho 6.1 ta mét dô b¶ng a vÝ vÒ th thít th«ng , tinchøa trong b¶ng nguyªn.§¬ng lµ c¸c sè nhiªnë ®©y lµ kh«ng thÓ dïng m¶ng hai chiÒu ®Ó biÓu diÔn mét b¶ng a l∙ng phÝ th thít v× , nhiÒu nhí.ta bé còng kh«ng thÓ dïng m¶ng mét chiÒu u ®Ó l gi÷ c¸c thµnh phÇn cña b¶ng ta®∙ nh lµm ®èi víi b¶ng tam b¶ng îc. gi¸cvµ r¨ngl Nguyªn nh©n lµ 160
161 v×,c¸cthµnh phÇn nghi∙cña cã b¶ng ph©n kh«ng bè theo mét quiluËt nµo,nªn takh«ng thÓ ®Þnh ® îcthµnh vÞ phÇn cña b¶ng trongm¶ng ë mét chiÒu. Mét ph¬ng ph¸p tèt®Ó Æt cµi® c¸cb¶ng a th thít dïng c¸cdanh lµ s¸ch ªnkÕt li ®Ó biÓu diÔn c¸c hµng c¸c cét cña vµ b¶ng. Mçi thµnh phÇn cña b¶ng vÞ , îc® a ë trÝ (i ® vµo j) haidanh s¸ch :danh s¸ch c¸c thµnh phÇn cña b¶ng dßng ë thø danh i vµ s¸ch c¸c thµnh phÇn cña b¶ng cétthø j. ë Tøc lµmçi thµnh phÇn cña b¶ng îcbiÓu ® diÔn bëimét b¶n kiÓu ghicã element® îckhaib¸o nh sau : type pointer ^ element; = element= record row :integer; col:integer ; value:valuetype; ptrrow :pointer ; ptrcol pointer : ; end; trong®ã row collµchØ hµng cét; vµ sè vµ ptrrow vµ ptrcol con ªn lµ tráli kÕt trong danh s¸ch hµng danh vµ 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 ghidíid¹ng h×nh 6.4a.Mçi hµng vµ mçi cétcña b¶ng îcbiÓu ® diÔn bëidanh s¸ch li ªnkÕt,vßng trßn vµ cã ®Çu. §Çu cña mçi hµng tr cã êng 0, cßn col= ®Çu cña tr mçi cétcã êng row 0.Khi®ã, = cÊu liÖubiÓu trócd÷ diÔn b¶ng trongh×nh 6.1 ® îcminh ho¹trongh×nh 6.4b. r col ow value ptcol ptr r r ow (a) T • 0 1 0 2 0 3 0 0 4 5 0 0 1 1 1 4 1 0 2 161
0 3 2 3 4 5 3 3 0 4 1 4 Mét ph¬ng ph¸p kh¸c®Ó Æt cµi® mét b¶ng a t dông th thí sö lµ hai m¶ng. Mét m¶ng haichiÒu cình cã cìcña b¶ng,m¶ng gi¸trÞlµ1 sÏcã t¹ c¸cvÞ trÝmµ gi¸trÞcña i b¶ng ý cã nghÜa vµ gi¸trÞlµ0 cã t¹ c¸cvÞ i trÝkh¸c.VÝ ®Ó dô biÓu diÔn b¶ng trongh×nh dông 6.1,tasö m¶ng ® îcminh ho¹ bëih×nh 6.5 a. Bªn c¹nh m¶ng haichiÒu chØ chøa hoÆc 1 0, ta sÏsö dông mét m¶ng mét chiÒu u nghÜa ®Ó l l¹ c¸cgi¸trÞcã i cña b¶ng. Ch¼ng h¹n,h×nh 6.5b minh ho¹ m¶ng mét chiÒu øng víib¶ng trongh×nh 6.1 1 0 0 1 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0 0 (a) 6 7 8 1 9 3 (b) H×nh 6.5M¶ng mét chiÒu øng víib¶ng trongh×nh 6.1 HiÖu qu¶ tiÕtkiÖm nhícña bé ph¬ng ph¸p nµy lµrâ rµng.Ch¼ng h¹n,®èi víi b¶ng nguyªn(nh trongh×nh c¸csè 6.1), thaycho viÖc sö dông m¶ng nguyªn(mçisè c¸csè nguyªncÇn byte= bit) sö 2 16 ®∙ ta dông m¶ng . c¸cbit 6.4.Trß ch¬i®êi sèng Trong môc nµy chóng ta tr×nh bµy mét dông ¸p cña ph¬ng ph¸p cµi® Æt b¶ng bëi b¶ng b¨m ®Ó gi¶iquyÕt rßch¬i®êi bµi to¸n't sèng' (game fe of li )Trß . ch¬i®êi sèng îcnhµ ® to¸nhäc Anh Conway a J.H ® ra n¨m 1970. 162
163 §êisèng cña mét céng ®ång thÓ c¸cc¬ sèng diÔn ra trªnmét íil « vu«ng kh«ng igií h¹n.Mçi vu«ng thÓ mét thÓ « cã cã c¬ sèng hoÆc kh«ng.¤ vu«ng mét thÓ cã c¬ sèng bµo gäilµtÕ sèng,ngîcl¹lµtÕ bµo i chÕt.C¸c bµo tÕ thay ®æi tõ thÕ hÖ nµy sang thÕ hÖ sau thuéc tuú vµo bµo c¸c tÕ sèng l©n ë cËn. Mçi tÕ bµo h×nh vu«ng t¸m bµo cã tÕ l©n cËn bµo cho tiÕpgi¸pvíi tÕ ®∙ theo c¸cc¹nh vµ c¸cgãc. C¸c bµo tÕ sÏthay®æi theo c¸cquiluËtsau : 1.NÕu mét bµo tÕ sèng,nhng tÕ sè bµo sèng cËn kh«ng l©n nã nhiÒu h¬n thÕ sau sÏchÕt (chÕtv× ®éc) 1,th× ë hÖ nã c« 2.NÕu mét bµo tÕ sèng,nhng tÕ sè bµo sèng cËn lµ2 l©n nã hoÆc 3, th× ë thÕ sau vÉn hÖ nã sèng. 3.NÕu mét bµo tÕ sèng,nhng tÕ sè bµo sèng cËn kh«ng l©n nã Ýt h¬n 4,th× ë thÕ sau sÏchÕt (chÕtv× hÖ nã qu¸®«ng!). 4.NÕu mét bµo tÕ chÕt vµ ®óng tÕ cã 3 bµo sèng l©n ë cËn,th× ë thÕ hÖ sau sÏtrëthµnh bµo nã tÕ sèng.Trong êng tr hîp cßn imét bµo l¹ , tÕ chÕt vÉn cßn chÕt ë thÕ sau. hÖ 5. Trong mçi thÕ hÖ, sinh ra chÕt diÔn ®ång sù vµ ®i ra thêi ,kh«ng ¶nh hëng ®Õn nhau. Sau ®©y ph¸ttr tasÏxÐt sù iÓncña mét céng sè ®ång bµo tÕ mµ thÕ ®Çu îccho hÖ tiªn® trongc¸ch×nh 6.6(dÊu chÐo ®¸nh dÊu bµo tÕ sèng).Céng ®ång trong h×nh 6.6a sÏbiÕn mÊt sau mét thÕ ,v× hÖ c¶ hai tÕ bµo cïng chÕt c« do ®éc. Céng ®ång trong h×nh 6.6 sÏ æn b ®Þnh tõthÕ nµy hÖ sang thÕ kh¸c,v× hÖ kh«ng tÕ cã bµo nµo sinh ra còng kh«ng tÕ cã bµo nµo chÕt ph¸ttr ®i.Sù iÓn cña céng ®ång trong h×nh 6.6cgiµnh cho b¹n ®äc. x x x x x x (a) (b) 163
x x x (c) H×nh 6.6 ThÕ hÖ ®Çu tiªncña mét céng sè ®ång tÕ bµo Chóng thÓ ta cã thÊy r»ng,tõ nh÷ng c¶nh huèng ban ®Çu nhá bÐ, mét céng sè ®ång thÓ iÓn thµnh cã ph¸ttr nh÷ng céng ®ång réng lín, mét céng sè ®ång thÓ cã thay®æi èn vµ ®Þnh sau mét thÕ sè hÖ, hoÆc thÓ cã lÆp lÆp ®i l¹ mét c¶nh i sè huèng nµo ®ã; mét kh¸ccã sè thÓ mÊt ®i. Sau khira ®êi kh«ng l©u,trßch¬i®êi sèng ® îcMartinGardner ®∙ bµn tí trong b¸o 'Scient f i i iAmerican' Tõ nã thu hótsù c ®ã ®∙ chó cña . ý nhiÒu ngêi. Trß ch¬i®êi sèng lµmét lËp tr×nhrÊthay bµitËp cho nh÷ng ngêi míihäc lËp tr×nh vµ cho nhu÷ng n¾m îc nh÷ng c¶ ai ®∙ ® cÊu trócd÷ liÖuphøc t¹p. §Çu thÓ tiªntacã nghÜ ngay ®Õn dïng mét m¶ng ch÷ nhËtkh¸lín ®Ó biÓu diÔn c¸cthÕ cña hÖ mét céng ®ång bµo.M¶ng gi¸trÞ tÕ sÏcã lµ1 i trÝcña bµo t¹ c¸cvÞ c¸ctÕ sèng 0 vµ øng bµo víi tÕ c¸c chÕt.§Ó x¸c ®Þnh îcsù ® thay ®æi cña bµo c¸c tÕ tõ thÕ hÖ nµy sang thÕ hÖ kh¸c,ta chØ cÇn ®Õm tÕ sè bµo sèng l©n cËn bµo ¸p dông mçi tÕ vµ c¸cluËttõ1) ®Õn 4).C¶nh huèng cña thÕ tiÕptheo ® îcghivµo hÖ mét m¶ng dÔ míi.Ta dµng îcl ch¬ng viÕt® îc®å tr×nh thùc hiÖn ph¬ng ¸n trªn. program LifeGame; const N . . = . ; M . . = . ; type row 1 = ..N; {hµng cña m¶ng} col ..M; = 1 {cétcña m¶ng} 164
165 status= ive (al , dead) {mçitÕ bµo mét ë tronghaitr¹ngth¸ i (status):sèng (aive) chÕt (dead)} vµ array[row,col] Table= of status; var T, new :Table T i: row; j:col; again:boolean; {Sau ®©y hµm} m« t¶c¸cthñtôcvµ procedure Ini i t on var T t a i :Table); ( {®a vµo b¶ng ban ®Çu} function Count(i j:integer) ..8; , 0 : {®Õm tÕ sè bµo sèng cËn bµo vÞ l©n tÕ ë trÝ(i j)} , procedure copy (new :Table;v¶ :Table); T T {sao chÐp m¶ng new sang T m¶ngT} begin Ini i t on t ai (T); WriteTable(T); repeat fori:= to N 1 do forj:= to M 1 do case , of count(i j) 0,1: new [ij] dead; T = , : 2 new [ij] T ; : T = [ij] , : , 3 new [ij] alive; : T = , : 4,5,6,7,8 : new , dead T[i := j] end; Copy (new T,T); WriteTable(T); Readln(again) ; until not again end. 165
B¹n ®äc dÔ dµng viÕt® îc c¸c thñ hµm tôc vµ trong ch¬ng tr×nh trªn. Riªng ®èi víihµm count,ta cÇn u r»ng,®Ó l ý tÝnh îcsè bµo ® tÕ sèng cËn l©n mét bµo tÕ tachØ cÇn tÕ xÐt8 bµo cËn bµo l©n víitÕ ®∙ cho,nÕu ë nã gi÷ab¶ng.Cßn nÕu ë nã r×a b¶ng tÕ th× sè bµo cËn l©n nã sÏkh«ng ph¶ithÕ. B©y giêtah∙yxÐtnh÷ng tiªnvµ u h¹n chÕ cña ch¬ng tr×nhtrªn. ¦u ®iÓm cña ch¬ng tr×nh trªnlµ ®¬n gi¶n vµ dÔ hiÓu.Song cã nã nhiÒu nhîc®iÓm. íchÕt sö Tr ta ®∙ dông m¶ng ®Ó m« t¶c¶nh huèng cña c¸c thÕ bµo ®ãng hÖ tÕ tøc lµta ®∙ khung chØ ph¸ttr xÐt sù iÓncña céng ®ång bµo tÕ trong ph¹m vim¶ng. Trªnthùc tÕ tõc¶nh huèng ban ®Çu, mét céng ®ång thÓ iÓn vîtqu¸ gií h¹n cã sÏph¸ttr i cña m¶ng, chØ sau mét thÕ sè hÖ. còng xÐt íitÕ Ta ®∙ l bµo mét nh b¶ng ch÷ nhËt ®Çy (mçithµnh phÇn cña b¶ng ®Òu chøa th«ng tin) song , thùcra,tacã mét b¶ng a kh«ng th thít v× , cÇn bµo xÐt tí c¸c tÕ i chÕt bµo mµ c¸c tÕ l©n cËn ®Òu nã chÕt.Mét nhîc®iÓm kh¸cn÷a lµ®Ó x¸c®Þnh c¸cthÕ hÖ tÕ bµo tÝnh tÕ ,ta®∙ l¹sè bµo i sèng cËn l©n cña mäi bµo.§iÒu tÕ nµy lµm l∙ngphÝ nhiÒu thêigian,v× kh«ng ph¶itÊtc¶,mµ chØ mét cã sè tÕ bµo cã tÕ sè bµo sèng cËn l©n thay®æi.§Ó kh¾c phôc nhîc®iÓm nµy,bªn c¹nh m¶ng ta ® a T vµo mét m¶ng kh¸cLive Neighbors®Ó ghi l¹sè bµo c¸ctÕ i sèng cËn bµo.Tøc l©n mçi tÕ lµ var LiveNeighbors:array[row,col] 0 of ..8; Khi ®ã, tõ thÕ nµy hÖ sang thÕ kh¸c,ta chØ hÖ cÇn x¸c®Þnh i l¹ c¸c gi¸trÞ cña m¶ng LiveNeighborst¹ bµo víic¸c tÕ i tÕ c¸c kÒ 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×nhnµy vÉn cha ph¶ilµch¬ng tr×nhtèt ta , v× cßn ph¶i ®i qua toµn m¶ng bé LiveNeighbors ®Ó ph¸thiÖn c¸c tÕ ra bµo sÏsinh hoÆc sÏchÕt ë ®i thÕ hÖ sau.Cßn nhiÒu cã c¸ch ®Ó c¶i tiÕnch¬ng tr×nh(bµitËp) Nh nãi, trªn®∙ viÖc dông sö m¶ng ®Ó m« t¶c¸cthÕ tÕ hÖ bµo lµ kh«ng thÝch kh«ng hîp,nã ph¶n ¸nh ®Çy sù iÓncña ®ñ ph¸ttr c¸ccéng ®ång bµo. CÇn tÕ ph¶ixÐt b¶ng bµo c¸c tÕ lµ mét b¶ng h¹n,trong v« ®ã ¬ng t øng voÝ trÝ(i j)lµmét bµo îchoµn mçi vÞ , tÕ ® toµn x¸c®Þnh bëivÞ trÝcña vµ c¸ctÕ nã sè bµo sèng cËn ®ã l©n nã.Do ph¬ng ph¸p tètnhÊt lµ dïng c¸c cÊu liÖu b¶ng trócd÷ b¨m më ®Ó biÓu diÔn b¶ng c¸ctÕ bµo.ë ®©y cÇn chó r»ng,hµm ý b¨m sÏ'b¨m'c¸cvÞ h trÝ(i j) ; cña c¸ctÕ bµo vµo trÝ0,1,..,N1 c¸cvÞ cña b¶ng b¨m. h trÝcña bµo}→ ; (i j) :{(ij) ; vÞ tÕ {0,1,...,N1} 166
167 Mçi tÕ bµo îc® a sÏ® vµo danh s¸ch li bµo ªnkÕt c¸ctÕ thuéc mét 'ræ'nµo cña ®ã b¶ng b¨m.Do mçi tÕ ®ã bµo îcm« ® t¶bëicÊu trócb¶n ghisau type cell record = row, col:integer; state:(al , ive dead); count:0 ..8; next:^ ; cell end; Table= array[0..N1]of^ ; cell Khi muèn x¸c ®Þnh bµo c¸c tÕ sÏ sèng hoÆc sÏ chÕt thÕ ë hÖ sau,®Ó tr¸nhph¶ixem xÐt toµn bé b¶ng b¨m, ta® a vµo haidanh s¸ch. Danh c¸ch Change bµo tÕ ghil¹ c¸ctÕ i mµ sè bµo sèng l©n cËn thÕ ë hÖ hiÖn icã t¹ thay ®æi víi thÕ tr ®ã, , so ë hÖ íc;do danh s¸ch Change sÏchøa bµo c¸ctÕ ®ang sèng sÏtrëthµnh chÕt hoÆc ®ang chÕt sÏtrë thµnh sèng thÕ ë hÖ sau.Danh s¸ch NextChange i bµo sÏ ghi l¹ c¸c tÕ mµ tÕ sè bµo sèng l©n cËn thÕ ë hÖ sau,cã thay ®æi víithÕ so hÖ hiÖn i t¹ . Chóng thÓ a ta cã ® thªm vµo mçi b¶n ghi biÓu diÔn bµo tÕ hai con trá.Mét con ªnkÕt c¸ctÕ trá®Ó li bµo thuéc danh s¸ch Change vµ mét con ªn bµo trá®Ó li c¸ctÕ kÕt thuécdanh s¸chNextChange.Nh vËy mçi b¶n bµo 3 êng ghi tÕ sÏ cã tr con trá.§iÒu nµy sÏ tiªutèn nhiÒu kh«ng gian nhí,v× thÓ cã chØ mét Ýt tÕ cã sè bµo îc® a ® vµo haidanh s¸ch nµy.Do c¸ch tèth¬n a ®ã lµta sÏ® c¸ccon trátrá®Õn bµo c¸ctÕ thuéc danh s¸ch Change (NextChange) vµo danh s¸ch Change (NextChange) thay cho viÖc a ® chÝnh c¸c bµo tÕ thuéc danh s¸ch Change(NextChange) vµo danh s¸ch Change (NextChange).Nãi mét c¸chkh¸c, danh s¸chChange NextChange vµ sÏlµc¸cdanh s¸chli ªn kÕt, gåm c¸cb¶n cÊu ghicã trócsau type node record = entry:^ ; cell next node; :^ end; 167
Mçi khicÇn x¸c ®Þnh c¶nh huèng cña mét céng ®ång bµo tÕ ë mét thÕ hÖ nµo ®ã, qua ta ®i danh s¸ch Change. Khi gÆp bµo tÕ tõ tr¹ngth¸ i chÕt trëthµnh sèng (hoÆc tõtr¹ngth¸ i sèng tráthµnh chÕt), ta chØ cÇn thay ®æi êng tr statecho nhËn nã gi¸trÞ alive(hoÆc dead) ®ång thêita sÏ t×m trong b¶ng b¨m nh÷ng bµo tÕ l©n cËn cña c¸c tÕ bµo ® a ®ã vµ chóng vµo danh s¸ch NextChange. NÕu mét bµo tÕ lµ l©n cËn cña bµo tÕ tõ chÕt trë thµnh sèng (hoÆc tõ sèng trë thµnh chÕt)th× tr count® îct¨nglªn1 êng (hoÆc îcgi¶m 1).Qu¸ ® ®i tr×nhtrªn ® îcthùchiÖn bëithñtôcTraverse(qua ®i). Chóng ph¸cth¶o ch¬ng tacã tr×nhsau : program LifeGame; const N = ;{N thµnh phÇn lµsè cña b¶ng b¨m} type ptrcel = l cell{con ªnkÕt bµo trá li c¸c tÕ trong c¸c danh s¸chmíicña b¶ng b¨m} cell record = row, col:integer, trÝcña bµo} {vÞ tÕ satate:(al ive, dead){tr i ¹ngth¸ cña bµo} tÕ count:0 cËn ..8;{sèl©n sèng cña bµo} tÕ next:ptrcel l end; ptrnode = ^ node;{con tráli ªnkÕt trong danh s¸ch Change vµ NextChange} node record = entry:ptrcel ; l next:ptrnode end; array[0,,N1]of ptrcel ; Table= l var T :Table; Change,NextChange :ptrnode; again:boolean; 168
169 procedure Ini i t on var T t a i :Table;var Change ( :ptrnode); {thñ tôc nµy x©y dùng b¶ng b¨m T vµ danh s¸ch Change (ban ®Çu Change lµdanh s¸ch c¸ctÕ bµo ®ang chÕt sÏthµnh sèng ®ang vµ sèng sÏthµnh chÕt)øng víic¶nh huèng ban ®Çu}. procedure Traverse(varChange,NextChange :ptrnode); {®iqua danh s¸ch Change, cËp nhËt b¶ng vµ T x©y dùng b¶ng NexChange}. procedure WriteTable(varT :Table); {viÕtrab¶ng T} begin ¬ng {ch tr×nhchÝnh} Ini i t on t a i Change); (T, repeat Traverse(Change,NextChange); WriteTable; Change NextChange; := readln(again) untilnotagain end. Sau ®©y chóng ta sÏm« t¶ chitiÕtthñ tôc Traverse,cßn c¸c thñ tôcIni i t on WriteTable® îc®Ó t ai vµ l¹xem bµitËp. i nh Trong thñ tôcTraverse,víi mçi l©n cËn , (i cña j) mét bµo tÕ chÕt trëthµnh sèng,(hoÆc sèng trëthµnh chÕt), ph¶it×m ta xem trongb¶ng b¨m cã bµo vÞ , ®∙ tÕ ë trÝ (i cha, nÕu j) cha a vµo th× ® nã b¶ng b¨m (ví tr êng i statelµdead tr vµ êng countb»ng 1),ta sÏdïng biÕn con tráq ghil¹ ®Þa i chØ cña bµo vÞ , . tÕ ë trÝ (i j) Qu¸ tr×nh trªn® îcthùc hiÖn b»ng thñtôc GetTable(i j:integer; :ptrcel ) , q var l Chóng dông tasÏsö thñtôc Add (q :ptrcel lvarNextChange ; :ptrnode) ®Ó a vµo ® q danh s¸chNextChange. Chóng thÓ tacã m« t¶thñtôcTraversenh sau : procedure Traverse; 169
var :ptrnode; p,p1 i, :integer j ; :ptrcel ; q l procedure GetTable(i j:integer :ptrcel ) , ;var q l; procedure l var Add (q : ptrcel ; NextChange : ptrnode); begin{b¾t®Çu thñtôcTraverse} p Change; := NextChange nil := ; whilep >
171 if > (i (j col)