Cấu trúc dữ liệu

Lêi nãi ®Çu Gi¸o tr×nh nµy ®­îc viÕt cho sinh viªn c¸c tr­êng Cao ®¼ng Đại học §Ó häc tèt gi¸o tr×nh nµy sinh viªn cÇn cã kiÕn thøc vÒ tin häc c¬ së vµ ®· biÕt mét ng«n ng÷ lËp tr×nh bËc cao nh­ Pascal, Delphi, C hay C++... Gi¸o tr×nh ®­îc viÕt nh»m nh÷ng môc tiªu sau ®©y: Giíi thiÖu cho häc sinh vÒ kh¸i niÖm vÒ kiÓu d÷ liÖu trõu t­îng. Cung cÊp cho häc sinh kiÕn thøc c¬ b¶n vÒ nh÷ng kiÓu d÷ liÖu trõu t­îng, cÊu tróc d÷ liÖu th«ng dông, n©ng cao vµ nh÷ng thao t¸c trªn c¸c cÊu tróc ®ã. Cung cÊp mét sè thuËt to¸n c¬ b¶n vµ rÌn luyÖn mét sè kÜ n¨ng ph©n tÝch thuËt to¸n cho häc sinh. RÌn luyÖn cho häc sinh c¸ch ¸p dông c¸c cÊu tróc d÷ liÖu ®· häc vµ t­ duy thuËt to¸n ®Ó cã thÓ thiÕt kÕ vµ cµi ®Æt mét sè ch­¬ng tr×nh b»ng mét ng«n ng÷ bËc cao. §Ó cã thÓ häc tèt c¸c ch­¬ng sau, sinh viªn cÇn ®äc kÜ ch­¬ng 1 vµ ch­¬ng 2. Ch­¬ng 1 giíi thiÖu nh÷ng kh¸i niÖm c¬ b¶n vÒ thuËt gi¶i. Ch­¬ng 2 giíi thiÖu nh÷ng kh¸i niÖm c¬ b¶n vÒ kiÓu d÷ liÖu trõu t­îng. §©y lµ kh¸i niÖm míi ®èi víi häc sinh. Mét kiÓu d÷ liÖu trõu t­îng lµ mét tËp hîp c¸c ®èi t­îng vµ ®­îc x¸c ®Þnh hoµn toµn bëi c¸c phÐp to¸n cã thÓ biÓu diÔn trªn c¸c ®èi t­îng ®ã. Ng­êi sö dông ®­îc phÐp t×m hiÓu c¸c ®èi t­îng vµ thùc hiÖn c¸c thao t¸c trªn c¸c ®èi t­îng cña kiÓu d÷ liÖu th«ng qua c¸c phÐp to¸n ®ã mµ kh«ng cÇn quan t©m ®Õn viÖc ®èi t­îng ®­îc cµi nh­ thÕ nµo trong ng«n ng÷ lËp tr×nh. Chóng t«i cã ®­a ra mét vµi vÝ dô ®¬n gi¶n vÒ kiÓu d÷ liÖu trõu t­îng, c¸ch ®Æc t¶ vµ x©y dùng chóng ®Ó ®Þnh h­íng cho viÖc ®Æc t¶ vµ x©y dùng nh÷ng kiÓu d÷ liÖu trõu t­îng trong nh÷ng ch­¬ng sau. Trong khi tr×nh bµy mçi kiÓu d÷ liÖu trõu t­îng ë mçi ch­¬ng sau, chóng t«i cè g¾ng khuyÕn khÝch sinh viªn tr­íc hÕt ph¶i hiÓu mét c¸ch kh¸i qu¸t vÒ kiÓu d÷ ®ã tr­íc khi quan t©m ®Õn viÖc cµi ®Æt chi tiÕt bªn trong. §iÒu ®ã kh«ng cã nghÜa lµ chóng t«i kh«ng coi träng viÖc cµi ®Æt. ViÖc t¸ch riªng ®Æc t¶ bªn ngoµi vµ bªn trong cho phÐp ta nh×n râ tr­íc hÕt vµo b¶n chÊt cña mét kiÓu d÷ liÖu trõu t­îng lµ tËp c¸c thao t¸c trªn c¸c ®èi t­îng cña kiÓu d÷ liÖu ®ã. Vµ chØ khi ®· hiÓu râ b¶n chÊt cña c¸c thao t¸c trªn mét kiÓu d÷ liÖu trõu t­îng chóng ta míi chuyÓn tíi viÖc cµi ®Æt nh÷ng thao t¸c ®ã b»ng mét ng«n ng÷ bËc cao nµo ®ã. C«ng cô cho phÐp ta bãc t¸ch mét c¸ch kh¸i niÖm h×nh thøc bªn ngoµi vµ chi tiÕt bªn trong ®ã chÝnh lµ kiÓu d÷ liÖu trõu t­îng. Tõ ch­¬ng 3 ®Õn ch­¬ng 6 dµnh cho viÖc nghiªn cøu mét sè kiÓu d÷ liÖu trõu t­îng c¬ b¶n tuyÕn tÝnh vµ phi tuyÕn. §ã lµ c¸c kiÓu d÷ liÖu trõu t­îng ng¨n xÕp, hµng ®îi, c©y, b¶ng t×m kiÕm, tËp hîp vµ ®å thÞ... Víi mçi kiÓu d÷ liÖu trõu t­îng ®­a ra, chóng ®Òu ®­îc ®Æc t¶ bëi c¸c thao t¸c c¬ b¶n vµ h­íng dÉn cµi ®Æt mét sè thao t¸c. Nh÷ng thao t¸c ®­a ra lµ nh÷ng thao t¸c c¬ b¶n nhÊt. Tuy nhiªn, tuú theo ®iÒu kiÖn vµ hoµn c¶nh, häc sinh cã thÓ bæ sung thªm mét sè nh÷ng thao t¸c kh¸c. Trong viÖc x©y dùng c¸c kiÓu d÷ liÖu trõu t­îng, chóng t«i rÊt nhÊn m¹nh viÖc quan t©m ®Çu tiªn lµ ®Æc t¶ ®­îc c¸c thao t¸c cÇn thiÕt (x©y dùng m« ®un ngoµi), sau ®ã míi ®Õn viÖc cµi ®Æt c¸c thao t¸c (x©y dùng m« ®un trong). Ngoµi ra, chóng t«i còng quan t©m ®Õn viÖc h­íng dÉn sö dông c¸c kiÓu d÷ liÖu trõu t­îng th«ng qua nh÷ng vÝ dô vÒ nh÷ng m« ®un øng dông. Sinh viªn ¾t h¼n ®· ®­îc giíi thiÖu mét vµi thuËt to¸n s¾p xÕp ®¬n gi¶n trªn m¶ng tõ phÇn Tin häc ®¹i c­¬ng. Tuy nhiªn, bµi to¸n s¾p xÕp vµ t×m kiÕm lµ bµi to¸n hÕt søc c¬ b¶n ®èi víi mçi sinh viªn Cao ®¼ng vµ §¹i häc nªn chóng t«i dµnh riªng ch­¬ng 7 ®Ó nãi vÒ mét sè gi¶i thuËt s¾p xÕp ®¬n gi¶n còng nh­ mét sè gi¶i thuËt s¾p xÕp n©ng cao, cÇn ®Õn mét chót kiÕn thøc vÒ kiÓu d÷ liÖu trõu t­îng võa häc trong c¸c ch­¬ng tr­íc. Mét sè phÐp so s¸nh c¸c gi¶i thuËt s¾p xÕp còng ®­îc ®Ò cËp trong ch­¬ng nµy. §Ó gióp häc sinh cã thªm mét sè kiÕn thøc vÒ thuËt gi¶i, trong ch­¬ng 8, chóng t«i tr×nh bµy mét sè ph­¬ng ph¸p thiÕt kÕ thuËt gi¶i nh­ ®Ö qui, quay lui, chia dÓ trÞ, tham lam, qui ho¹ch ®éng. §©y lµ nh÷ng ph­¬ng ph¸p rÊt c¬ b¶n vµ th«ng dông trong khoa häc m¸y tÝnh. B¹n ®äc cã thÓ t×m thÊy nhiÒu vÝ dô minh ho¹ cho nh÷ng ph­¬ng ph¸p nµy. C¸c vÝ dô ®Òu ®­îc cµi ®Æt cô thÓ b»ng ng«n ng÷ lËp tr×nh Pascal. Cuèi mçi ch­¬ng ®Òu cã hÖ thèng bµi tËp ®Ó häc sinh lµm vµ tù kiÓm tra kiÕn thøc cña m×nh. Cuèi cïng lµ phÇn phô lôc, trong ®ã chóng t«i cã ®­a ra mét sè bµi tËp lín, ®Ó häc sinh ¸p dông nh÷ng kiÕn thøc ®· häc tËp gi¶i quyÕt nh÷ng vÊn ®Ò phøc t¹p h¬n so víi bµi tËp sau mçi ch­¬ng. Víi nh÷ng bµi tËp lín nµy, ®Ó n©ng cao hiÖu qu¶, yªu cÇu häc sinh cÇn ®Æc t¶ râ bµi to¸n, ph©n tÝch vµ thiÕt kÕ thuËt gi¶i, sau ®ã cµi ®Æt trªn mét ng«n ng÷ cô thÓ. TiÕp theo häc sinh cÇn ph¶i kiÓm thö phÇn mÒm m×nh võa cµi ®Æt vµ cã nh÷ng nhËn xÐt vÒ ®é phøc t¹p cña thuËt to¸n m×nh thiÕt kÕ, vÒ c¸c h­íng cÇn më réng cho c¸c bµi tËp nµy. ChØ khi nµo häc sinh lµm tèt c¸c bµi tËp lín ®ã míi cã thÓ nãi lµ hä ®· thµnh c«ng trong viÖc häc tËp m«n häc nµy. Chñ biªn vµ hiÖu ®Ýnh toµn bé néi dung b¶n th¶o: Ch­¬ng 1: Më ®Çu ch­¬ng 2: . Ch­¬ng 3: . Ch­¬ng 4, Ch­¬ng 6: Ch­¬ng 7: Ch­¬ng 8: Ch­¬ng I: Më ®Çu Ch­¬ng nµy tr×nh bµy mét sè kh¸i niÖm c¬ b¶n ®Çu tiªn vÒ bµi to¸n theo quan ®iÓm Tin häc, thuËt gi¶i, cÊu tróc d÷ liÖu, mèi quan hÖ gi÷a cÊu tróc d÷ liÖu vµ thuËt gi¶i. Nh÷ng kh¸i niÖm vÒ ®é phøc t¹p cña thuËt gi¶i vµ ph©n tÝch thuËt gi¶i còng ®­îc giíi thiÖu trong ch­¬ng. Kh¸i niÖm vÒ cÊu tróc d÷ liÖu vµ thuËt gi¶i 1.1.1. Kh¸i niÖm bµi to¸n Trong ph¹m vi Tin häc, ta cã thÓ quan niÖm bµi to¸n lµ bÊt cø viÖc g× ta muèn m¸y tÝnh thùc hiÖn. Nh­ vËy nh÷ng viÖc nh­ viÕt mét dßng ch÷ ra mµn h×nh, gi¶i ph­¬ng tr×nh bËc hai, gi¶i hÖ ph­¬ng tr×nh bËc nhÊt hai Èn sè, qu¶n lý c¸c c¸n bé trong mét c¬ quan... ®Òu lµ c¸c vÝ dô vÒ bµi to¸n. Khi dïng m¸y tÝnh gi¶i bµi to¸n, ta chØ cÇn quan t©m ®Õn hai yÕu tè: ®­a vµo m¸y th«ng tin g× (th«ng tin vµo) vµ cÇn lÊy ra th«ng tin g× (th«ng tin ra), Th«ng tin vµo cßn ®­îc gäi lµ Input, th«ng tin ra cßn ®­îc gäi lµ Output. Nh­ vËy ®Ó ph¸t biÓu mét bµi to¸n, ta chØ cÇn ®Æc t¶ Input vµ Output cña bµi to¸n. VÝ dô 1. Bµi to¸n t×m ­íc chung lín nhÊt Input. Hai sè nguyªn d­¬ng M vµ N Output. ¦íc chung lín nhÊt cña M vµ N VÝ dô 2. Bµi to¸n t×m nghiÖm cña ®a thøc mét biÕn: Input: sè nguyªn d­¬ng n; c¸c sè thùc a0, a1, . . ., an; Output: Tr¶ lêi c©u hái cã bao nhiªu sè thùc x kh¸c nhau vµ gi¸ trÞ cña chóng (nÕu cã) sao cho a0 + a1x +...+ anxn = 0 VÝ dô 3. Bµi to¸n ph©n tÝch sè: Input: Sè nguyªn d­¬ng N(2; Output: C¸c sè nguyªn tè p1,..., pk; c¸c sè nguyªn d­¬ng 1,...,k; sao cho n = p11...pkk; VÝ dô 4. Bµi to¸n kiÓm tra tÝnh nguyªn tè: Input: Sè nguyªn d­¬ng n; Output: Tr¶ lêi c©u hái n lµ sè nguyªn tè hay kh«ng?. VÝ dô 5. Bµi to¸n qu¶n lý hå s¬ c¸n bé: Input: Hå s¬ gèc cña c¸c c¸n bé trong c¬ quan; Output: Nh÷ng biÓu b¶ng thèng kª, ph©n lo¹i c¸n bé, c¸c quy tr×nh l­u tr÷, qu¶n lý hå s¬ c¸n bé. VÝ dô 6. Bµi to¸n thø 10 cña Hilbert: Input: P lµ ®a thøc (nhiÒu Èn) víi hÖ sè nguyªn; Output: Tr¶ lêi c©u hái P cã nghiÖm nguyªn hay kh«ng? Qua c¸c vÝ dô trªn, ta thÊy c¸c bµi to¸n ®­îc cÊu t¹o bëi hai thµnh phÇn c¬ b¶n: - Th«ng tin vµo (input): Cho ta biÕt nh÷ng th«ng tin ®· cã (c¸c gi¶ thiÕt); - Th«ng tin ra (output): C¸c th«ng tin cÇn t×m tõ input (kÕt luËn); 1.1.2. Kh¸i niÖm thuËt gi¶i Nh­ vËy trong gi¸o tr×nh nµy, viÖc cho mét bµi to¸n cã nghÜa lµ cho input vµ m« t¶ output cÇn t×m. VÊn ®Ò ®Æt ra lµ thÕ nµo lµ gi¶i mét bµi to¸n? Tr­íc hÕt cÇn l­u ý r»ng trong to¸n häc cã mét xu h­íng nghiªn cøu ®Þnh tÝnh c¸c bµi to¸n. Theo xu h­íng nµy, khi xem xÐt c¸c bµi to¸n, ng­êi ta chØ cÇn chøng tá sù tån t¹i cña output khi cho input vµ nÕu cã thÓ, xÐt xem cã bao nhiªu "lêi gi¶i" vµ nghiªn cøu d¸ng ®iÖu cña chóng. Trong c¸c nghiªn cøu nh­ vËy, nhiÒu khi ta kh«ng cÇn t×m ra lêi gi¶i mét c¸ch t­êng minh nh­ng b»ng c¸ch dïng c¸c c«ng cô to¸n häc kh¸c nhau mét c¸ch thÝch hîp ta vÉn cã thÓ chøng minh chÆt chÏ c¸c ®iÒu kh¼ng ®Þnh liªn quan ®Õn lêi gi¶i. Môc tiªu cña xu h­íng nghiªn cøu nµy lµ chØ ra ®iÒu kiÖn tån t¹i vµ nÕu cã thÓ, sù duy nhÊt cña lêi gi¶i. Sù tån t¹i lêi gi¶i theo nghÜa nµy kh«ng lu«n cho ta c¸ch thøc thùc tÕ ®Ó t×m ra lêi gi¶i. Trong khu«n khæ cña Tin häc, viÖc gi¶i bµi to¸n cã nghÜa trao ®­îc cho m¸y tÝnh c¸ch gi¶i. §Ó giao bµi to¸n cho m¸y tÝnh, ta cÇn h­íng dÉn cho m¸y c¸c thao t¸c mµ vÒ nguyªn t¾c m¸y cã thÓ thùc hiÖn ®­îc. Mét c¸ch gi¶i bµi to¸n nh­ vËy ®­îc gäi lµ mét thuËt gi¶i (cßn gäi lµ thuËt to¸n hay gi¶i thuËt). Nãi mét c¸ch ®Çy ®ñ h¬n, ThuËt gi¶i A ®Ó gi¶i bµi to¸n P lµ mét d·y h÷u h¹n c¸c thao t¸c ®¬n gi¶n ®­îc s¾p xÕp theo mét tr×nh tù x¸c ®Þnh sao cho sau khi thùc hiÖn d·y thao t¸c ®ã, tõ Input cña bµi to¸n, ta nhËn ®­îc Output cÇn t×m. ChÝnh quan niÖm vÒ viÖc gi¶i bµi to¸n nh­ vËy lµ cèt lâi ®Ó ta cã thÓ chuyÓn giao c«ng viÖc ®ã cho m¸y tÝnh. Nh­ vËy, kh¸c víi quan niÖm vÒ viÖc gi¶i mét bµi to¸n theo to¸n häc truyÒn thèng, viÖc gi¶i bµi to¸n theo quan niÖm cña Tin häc lµ qu¸ tr×nh thùc hiÖn mét d·y h÷u h¹n c¸c thao t¸c ®¬n gi¶n ®Ó cã thÓ tõ Input dÉn ra Output mét c¸ch t­êng minh. Trong ®Þnh nghÜa nªu trªn, thao t¸c ®¬n gi¶n ®­îc hiÓu lµ thao t¸c mµ m¸y tÝnh cã thÓ thùc hiÖn ®­îc. VÝ dô c¸c phÐp to¸n sè häc, c¸c phÐp so s¸nh hai gi¸ trÞ sè lµ c¸c thao t¸c ®¬n gi¶n. M« t¶ thuËt gi¶i Ngay tõ khi häc m«n Tin häc c¬ së häc sinh ®· ®­îc lµm quen víi kh¸i niÖm thuËt gi¶i vµ ®­îc häc c¸ch m« t¶ hay diÔn ®¹t nh÷ng thuËt gi¶i ®¬n gi¶n. ThuËt gi¶i cho nh÷ng bµi to¸n nhá hay thuËt gi¶i cho nh÷ng bµi to¸n lín khi ®­îc thiÕt kÕ ë møc th« hay ®­îc m« t¶ b»ng s¬ ®å khèi. C¸ch dïng s¬ ®å khèi ®Ó minh häa thuËt gi¶i cã lîi thÕ lµ rÊt trùc quan, dÔ hiÓu. Tuy nhiªn, víi nh÷ng bµi to¸n lín, phøc t¹p, viÖc dïng s¬ ®å khèi ®Ó m« t¶ thuËt gi¶i cã nh÷ng h¹n chÕ nhÊt ®Þnh. H¹n chÕ nµy lµ cã thÓ lµ do khu«n khæ giÊy hay mµn h×nh ta dïng ®Ó vÏ s¬ ®å hay tÇm bao qu¸t, theo dâi cña m¾t ta trªn s¬ ®å. H¹n chÕ nµy còng n¶y sinh khi bµi to¸n cña ta phøc t¹p, cã nhiÒu vßng lÆp lång nhau, khi ®ã viÖc tr×nh bµy s¬ ®å cã rÊt nhiÒu h¹n chÕ. Ta còng hay dïng ph­¬ng ph¸p liÖt kª c¸c b­íc gi¶i ®Ó m« t¶ thuËt gi¶i. Ph­¬ng ph¸p nµy còng rÊt dÔ hiÓu ®èi víi c¸c bµi to¸n nhá. Tuy nhiªn, ®èi víi c¸c bµi to¸n lín, viÖc liÖt kª sÏ trë nªn khã kh¨n vµ nÕu ®­îc th× còng g©y khã khã theo dâi, nhÊt lµ ®èi víi vßng lÆp. H¬n thÕ n÷a viÖc liÖt kª c¸c b­íc gi¶i ta hay ph¶i dïng ng«n ng÷ tù nhiªn ®Ó m« t¶ c¸c thao t¸c nªn viÖc diÔn ®¹t nhiÒu khi rÊt khã chÝnh x¸c. Ph­¬ng ph¸p thø ba hay ®­îc dïng ®Ó m« t¶ thuËt gi¶i lµ dïng gi¶ m· hay ng«n ng÷ pháng tr×nh. ViÖc dïng ng«n ng÷ pháng tr×nh kh¾c phôc ®­îc nh÷ng nhiÒu nh­îc ®iÓm cña hai ph­¬ng ph¸p trªn, ®Æc biÖt ®èi víi nh÷ng bµi to¸n lín, phøc t¹p. Còng cã ý kiÕn lµ ta nªn chän mét ng«n ng÷ lËp tr×nh th«ng dông lµm c«ng cô ®Ó diÔn ®¹t thuËt gi¶i. Tuy nhiªn, ai còng biÕt lµ thuËt gi¶i cÇn ph¶i ®éc lËp víi ng«n ng÷ lËp tr×nh. Khi thuËt gi¶i ®­îc viÕt tèt nã cã thÓ ®­îc cµi ®Æt b»ng bÊt cø ng«n ng÷ lËp tr×nh nµo, tïy theo tÝnh thÝch hîp cña bµi to¸n vµ ý muèn cña ng­êi lËp tr×nh. H¬n thÕ n÷a, thiÕt kÕ thuËt gi¶i lµ mét trong nh÷ng c«ng viÖc quan träng nhÊt cña ng­êi lËp tr×nh. NÕu ta chän mét ng«n ng÷ lËp tr×nh ®Ó m« t¶ thuËt gi¶i th× lóc nµo ta còng ph¶i chó ý tu©n thñ c¸c tiÓu tiÕt có ph¸p cña ng«n ng÷. §iÒu ®ã sÏ g©y mÊt th× giê vµ ¶nh h­ëng lín ®Õn sù tËp trung vµo c«ng viÖc chÝnh lµ thiÕt kÕ vµ m« t¶ thuËt gi¶i. Sau ®©y lµ vÝ dô vÒ m« t¶ thuËt gi¶i t×m ­íc chung lín nhÊt cña hai sè nguyªn m vµ n. C¸ch 1: Dïng s¬ ®å khèi H×nh 1.1: S¬ ®å khèi diÔn t¶ thuËt gi¶i t×m ­íc chung lín nhÊt cña hai sè nguyªn kh«ng ©m -------------------------------------- C¸ch thø hai: Dïng ph­¬ng ph¸p liÖt kª c¸c b­íc gi¶i, ta cã thÓ viÕt nh­ sau:. B­íc 1. Khi m > 0 thùc hiÖn t ( m m ( n mod m n ( t B­íc 2. KiÓm tra xem nÕu m > 0, quay l¹i b­íc 1 B­íc 3. In kÕt qu¶ lµ n vµ kÕt thóc C¸ch thø ba: Dïng ng«n ng÷ pháng tr×nh. Function Ucln(m,n) var t Begin While m > 0 do t ( m m ( n mod m n ( t Return n ----------------------------- Trong thùc tÕ, tïy theo tõng giai ®o¹n thiÕt kÕ thuËt gi¶i, tïy theo møc ®é, vµ ®èi t­îng tr×nh bµy mµ ng­êi lËp tr×nh th­êng hay chän ph­¬ng ph¸p thÝch hîp nhÊt trong ba ph­¬ng tiÖn nªu trªn. Nh­ vËy, viÖc diÔn t¶ mét thuËt gi¶i gi¶i mét bµi to¸n nµo ®ã cã nghÜa lµ tr×nh bµy tr×nh tù c¸c thao t¸c cÇn thùc hiÖn. Tuy nhiªn, ®ã chØ lµ c¸ch diÔn t¶ thuËt gi¶i gi÷a ng­êi víi ng­êi. Ngay khi thuËt gi¶i ®· ®­îc diÔn t¶ nh­ vËy, con ng­êi cã thÓ dïng ®Ó gi¶i bµi to¸n víi mçi bé d÷ liÖu vµo. Tuy nhiªn, theo c¸ch diÔn t¶ nµy, m¸y tÝnh vÉn ch­a thÓ thùc hiÖn c¸c thao t¸c trong thuËt gi¶i dï c¸c thao t¸c ®ã rÊt ®¬n gi¶n. ThuËt gi¶i cÇn ®­îc diÔn t¶ thµnh mét ch­¬ng tr×nh gåm nh÷ng dßng lÖnh. Mçi lÖnh lµ mét viÖc nµo ®ã mµ ta ®ßi hái m¸y tÝnh thùc hiÖn. Ng«n ng÷ dïng ®Ó viÕt ch­¬ng tr×nh ®­îc gäi lµ ng«n ng÷ lËp tr×nh. PhÇn ®äc thªm Kh¸i niÖm thuËt gi¶i tr×nh bµy ë trªn ®ñ ®Ó ta cã thÓ h×nh dung ®Ó cã thÓ chuyÓn giao cho m¸y tÝnh viÖc gi¶i mét bµi to¸n ta cÇn diÔn t¶ c¸ch gi¶i nh­ thÕ nµo vµ còng lµ c¸ch nhËn biÕt thÕ nµo lµ thuËt gi¶i ®èi víi mét bµi to¸n nµo ®ã. Trong qu¸ tr×nh nghiªn cøu c¸ch gi¶i bµi to¸n theo nghÜa nªu trªn,trong to¸n häc ®· diÔn ra mét qu¸ tr×nh ph¸t triÓn ®Çy kÞch tÝnh. Cho tíi ®Çu thÕ kû 20, víi lßng tin tiªn nghiÖm vµo viÖc mäi bµi to¸n ®­îc ph¸t biÓu ®óng ®¾n ®Òu cã thuËt gi¶i gi¶i, nhiÒu nhµ to¸n häc ®Çy tµi n¨ng vµ t©m huyÕt ®· tiÕn c«ng vµo c¸c bµi to¸n ®ang tån t¹i nh­ nh÷ng lêi th¸ch ®è trÝ tuÖ con ng­êi. VÊn ®Ò then chèt nhÊt cña lý thuyÕt tÝnh to¸n ph¸t sinh ë ®©y. §Ó chøng minh mét bµi to¸n nµo ®ã cã thuËt gi¶i gi¶i nã, ta chØ cÇn ®Ò ra mét thuËt gi¶i theo quan niÖm trùc gi¸c cña kh¸i niÖm nµy vµ kiÓm ®Þnh tÝnh ®óng ®¾n cña nã ®èi víi bµi to¸n ®· cho. Tuy nhiªn, khi cÇn chøng minh viÖc kh«ng cã thuËt gi¶i gi¶i mét bµi to¸n nµo ®ã, quan niÖm trùc quan vÒ thuËt gi¶i kh«ng thÓ lµ c¬ së b¶o ®¶m cho mét chøng minh to¸n häc chÆt chÏ ®­îc. Do ®ã, muèn chøng minh nh÷ng ®iÒu kh¼ng ®Þnh "kh«ng cã thuËt gi¶i gi¶i mét bµi to¸n nµo dã", ta cÇn cã mét ®Þnh nghÜa to¸n häc cho kh¸i niÖm thuËt gi¶i. Vµo kho¶ng nh÷ng n¨m 1930-1936, lÇn l­ît c¸c nhµ to¸n häc K.Gâdel, S. Kleene, A.Church, A.Turing ®· ®Ò ra mét sè ®Þnh nghÜa kh¸c nhau cho kh¸i niÖm thuËt gi¶i. Trong sè c¸c ®Þnh nghÜa to¸n häc kh¸c nhau (nh­ng t­¬ng ®­¬ng) vÒ thuËt gi¶i, c¸c kh¸i niÖm M¸y Turing (1936) vµ Hµm ®Ö quy (1931-1936) ®­îc sö dông réng r·i h¬n v× cã nhiÒu thuËn tiÖn cho c¸c nghiªn cøu c¶ vÒ lý thuyÕt lÉn thùc hµnh. Ta cã thÓ xem m¸y Turing lµ mét m« h×nh to¸n häc cña m¸y tÝnh. ChÝnh nhê cã ®­îc ®Þnh nghÜa to¸n häc vÒ thuËt gi¶i, ng­êi ta ®· chøng minh ®­îc cã nh÷ng bµi to¸n kh«ng cã thuËt gi¶i gi¶i. Ch¼ng h¹n, bµi to¸n thø 10 cña Hilbert (VÝ dô 5 nªu trªn) kh«ng cã thuËt gi¶i ®Ógi¶i. 1.1.4. Mét sè vÝ dô vÒ thuËt gi¶i VÝ dô 1. Mét thuËt gi¶i t×m ­íc chung lín nhÊt (viÕt t¾t lµ UC) cña hai sè nguyªn d­¬ng M vµ N.(B¹n ®äc cã thÓ thÊy sù kh¸c nhau chót Ýt gi÷a thuËt to¸n nµy vµ thuËt to¸n tr×nh bµy ë phÇn trªn). B­íc 1. NÕu M=N th× UC=M vµ kÕt thóc, nÕu kh«ng th× chuyÓn ®Õn b­íc 2. B­íc 2. NÕu M<N th× thay N b»ng N-M vµ chuyÓn ®Õn b­íc 1, nÕu kh«ng th× thay M b»ng M-N vµ chuyÓn ®Õn b­íc 1. D·y thao t¸c trong thuËt gi¶i diÔn ra trong nhiÒu nhÊt Max(M,N) b­íc. Tuy nhiªn, víi c¸ch diÔn t¶ thuËt gi¶i trªn, m¸y ch­a cã kh¶ n¨ng trùc tiÕp thùc hiÖn. Ta cÇn diÔn t¶ thuËt gi¶i ®ã b»ng mét ng«n ng÷ mµ m¸y tÝnh cã thÓ “hiÓu” vµ thùc hiÖn ®­îc. C¸ch diÔn t¶ mét thuËt gi¶i nh­ vËy ®­îc gäi lµ mét ch­¬ng tr×nh, ng«n ng÷ dïng ®Ó viÕt ch­¬ng tr×nh ®­îc gäi lµ ng«n ng÷ lËp tr×nh. VÝ dô 2. ThuËt gi¶i t×m gi¸ trÞ lín nhÊt vµ nhá nhÊt cña mét d·y sè Ta xÐt bµi to¸n sau: Input: Sè nguyªn d­¬ng n vµ d·y n sè a1, . . ., an. Output: Gi¸ trÞ lín nhÊt Max vµ gi¸ trÞ nhá nhÊt Min cña d·y sè Sau ®©y lµ thuËt gi¶i ®èi víi bµi to¸n nµy: B­íc 1. §Æt Max= a1, Min= a1, i=2. B­íc 2. NÕu i<N th× thùc hiÖn b­íc 3, nÕu kh«ng th× kÕt thóc. B­íc 3 3.1. NÕu ai>Max th× Max= ai. 3.2. NÕu ai<Min th× Min= ai. T¨ng i mét ®¬n vÞ vµ quay vÒ b­íc 2. Râ rµng sè thao t¸c cÇn tiÕn hµnh kh«ng qu¸ n. VÝ dô 3. ThuËt gi¶i ®Ó s¾p xÕp mét d·y sè cho tr­íc thµnh mét d·y ®¬n ®iÖu kh«ng t¨ng. Ta xÐt bµi to¸n sau: Input: Sè nguyªn d­¬ng n vµ d·y n sè a1, . . ., an. Output: D·y sè trªn ®­îc s¾p xÕp l¹i thµnh mét d·y sè kh«ng t¨ng tøc lµ sè h¹ng tr­íc lín h¬n hay b»ng sè h¹ng sau. Mét thuËt gi¶i gi¶i bµi to¸n nµy cã thÓ nãi v¾n t¾t nh­ sau: víi mçi chØ sè i, 1in-1, xÐt c¸c chØ sè j ®øng sau i, i+1jn, nÕu ai<aj th× ta tr¸o ®æi hai sè h¹ng nµy cho nhau. Mét c¸ch cô thÓ h¬n: B­íc 1. i=1; B­íc 2. NÕu i=n th× kÕt thóc, nÕu kh«ng ( tøc lµ i<n) th× B­íc 2.1. j=i+1; B­íc 2.2. NÕu (jn) vµ (ai<aj) th× tr¸o ®æi gi¸ trÞ cña hai sè nµy B­íc 2.3. NÕu j<n th× (t¨ng J mét ®¬n vÞ vµ quay l¹i B­íc 2.2), nÕu kh«ng ( tøc lµ j=n), chuyÓn sang b­íc 3. B­íc 3. T¨ng i mét ®¬n vÞ vµ quay l¹i B­íc 2. Râ rµng sè b­íc thao t¸c cÇn tiÕn hµnh kh«ng qu¸ n(n+1). 1.1.5 Kh¸i niÖm vÒ cÊu tróc d÷ liÖu vµ mèi quan hÖ víi thuËt gi¶i ë trªn ta ®· nªu râ kh¸i niÖm thuËt gi¶i. §èi t­îng cña thuËt gi¶i chÝnh lµ d÷ liÖu hay thuËt gi¶i bao giê còng ph¶i t¸c ®éng lªn d÷ liÖu ®Ó cã kÕt qu¶ cña bµi to¸n. Mét tËp d÷ liÖu cã thÓ gåm nh÷ng phÇn tö rêi r¹c, ch¼ng cã quan hÖ g× víi nhau, nh­ng còng cã thÓ gåm nh÷ng phÇn tö cã quan hÖ, rµng buéc nhÊt ®Þnh. Khi nh÷ng thµnh phÇn cña tËp d÷ liÖu cã mèi quan hÖ víi nhau, chóng cÇn ®­îc tæ chøc theo nh÷ng ph­¬ng thøc nhÊt ®Þnh thµnh nh÷ng cÊu tróc d÷ liÖu ®Ó thuËt gi¶i t¸c ®éng lªn ®ã ®­îc hiÖu qu¶. Trong gi¸o tr×nh Tin häc c¬ së, ta ®· lµm quen víi mét sè cÊu tróc d÷ liÖu ®¬n gi¶n nh­ b¶n ghi, m¶ng...Trong gi¸o tr×nh nµy ta sÏ lÇn l­ît nghiªn cøu nh÷ng cÊu tróc d÷ liÖu phøc t¹p h¬n c¶ tuyÕn tÝnh vµ phi tuyÕn tÝnh. Khi lËp ch­¬ng tr×nh cho m¸y tÝnh, c«ng viÖc tæ chøc d÷ liÖu vµ thiÕt kÕ nh÷ng thuËt gi¶i t­¬ng thÝch, hiÖu qu¶ lµ rÊt quan träng. ChÝnh v× thÕ cÊu tróc d÷ liÖu vµ thuËt gi¶i lµ hai thµnh tè quan träng cña ch­¬ng tr×nh m¸y tÝnh vµ ®Òu lµ nh÷ng ®èi t­îng nghiªn cøu quan träng cña khoa häc m¸y tÝnh. H¬n n÷a, chóng cã quan hÖ mËt thiÕt víi nhau, ¶nh h­ëng vµ ®iÒu phèi lÉn nhau ®Ó t¹o ra lêi gi¶i cho bµi to¸n. Trong ph¹m vi cña gi¸o tr×nh nµy, ta nghiªn cøu nh÷ng cÊu tróc d÷ liÖu c¬ b¶n vµ nh÷ng thuËt gi¶i hay thao t¸c th­êng thùc hiÖn trªn c¸c cÊu tróc d÷ liÖu ®ã. 1.2. Kh¸i niÖm vÒ ®é phøc t¹p cña thuËt gi¶i Mçi thuËt gi¶i chØ gi¶i mét bµi to¸n nµo ®ã nh­ng cã thÓ cã nhiÒu thuËt gi¶i kh¸c nhau gi¶i cïng mét bµi to¸n. VÝ dô, ®Ó s¾p xÕp mét d·y sè bÊt kú thµnh mét d·y ®¬n ®iÖu, cã rÊt nhiÒu thuËt gi¶i kh¸c nhau. Cïng mét bµi to¸n, cã thÓ cã nhiÒu thuËt gi¶i kh¸c nhau. ViÖc lùa chän mét thuËt gi¶i thÝch hîp nhÊt hay tèt nhÊt cho mét bµi to¸n lu«n lµ mèi quan t©m cña ng­êi lËp tr×nh. VËy lµm thÕ nµo ®Ó chän ®­îc thuËt gi¶i thÝch hîp nhÊt trong nh÷ng thuËt gi¶i cña mét bµi to¸n? Nãi cô thÓ h¬n, nh÷ng tiªu chÝ nµo lµ quan träng ®Ó ®¸nh gi¸ mét thuËt gi¶i? ThuËt gi¶i cµng trong s¸ng, cã cÊu tróc tèt th× m· hãa cµng nhanh, b¶o tr× ch­¬ng tr×nh cµng dÔ dµng vµ do ®ã gi¶m ®­îc gi¸ thµnh cña phÇn mÒm. Tuy nhiªn, cã nh÷ng thuËt gi¶i rÊt trong s¸ng, dÔ hiÓu nh­ng l¹i kh«ng kh¶ thi vÒ mÆt thêi gian thùc hiÖn hay kh«ng gian nhí cÇn thiÕt khi thùc hiÖn nã. VËy lµm thÕ nµo ®Ó ®¸nh gi¸ ®­îc thêi gian thùc hiÖn vµ kh«ng gian nhí dµnh cho mét thuËt gi¶i? C¸ch ®¬n gi¶n nhÊt lµ ta cµi ®Æt thuËt gi¶i råi cho m¸y ch¹y ch­ong tr×nh víi mét tËp d÷ liÖu vµo nµo ®ã vµ ®o thêi gian thùc hiÖn ch­¬ng tr×nh còng nh­ tÝnh kh«ng gian nhí cÇn thiÕt cho nã vµ ta cã kÕt qu¶ vÒ thêi gian vµ kh«ng gian cÇn thiÕt cho thuËt gi¶i. Tuy nhiªn, c¸ch tÝnh nµy chØ míi ¸p dông trªn mét tËp d÷ liÖu ®Çu vµo cô thÓ. SÏ lµ kh«ng thÝch hîp nÕu ta dïng kÕt qu¶ nµy ®Ó ¸p dông chung cho c¸c tËp d÷ liÖu ®Çu vµo kh¸c. NÕu bµi to¸n ®¬n gi¶n vµ ®Çu vµo chØ gåm mét sè Ýt phÇn tö th× ta còng ch¼ng cÇn quan t©m nhiÒu ®Õn viÖc lùa chän thuËt gi¶i lµm g×. VÝ dô nh­ bµi to¸n sau: Ta cÇn chän ra sè lín nhÊt trong 3 sè nguyªn hay thËm chÝ trong vµi chôc sè nguyªn ®· cho. B¹n cã thÓ dïng bÊt cø thuËt gi¶i nµo b¹n nghÜ ra hay b¹n thÝch, miÔn lµ nã ®óng, cã lÏ thêi gian thùc hiÖn chóng còng kh«ng kh¸c nhau bao nhiªu. Mét thuËt to¸n t×m kiÕm tuÇn tù ®Ó t×m mét sè ®iÖn tho¹i trong mét danh s¸ch ®iÖn tho¹i gåm 50 sè th× cã thÓ chÊp nhËn ®­îc nh­ng nÕu ¸p dông thuËt to¸n ®ã cho mét danh s¸ch gåm hµng chôc ngµn sè ®iÖn tho¹i trong mét thµnh phè, h¼n lµ kh«ng thÓ chÊp nhËn ®­îc. Nh­ vËy, vÊn ®Ò ®Æt ra rÊt tù nhiªn lµ khi gi¶i mét bµi to¸n, ta muèn chän mét thuËt gi¶i tèt. Chóng ta cÇn t×m ra mét ph­¬ng ph¸p nµo ®ã ®Ó cã thÓ cho phÐp ta ®¸nh gi¸ ®­îc thuËt gi¶i nµy tèt h¬n thuËt gi¶i kia víi mét tËp d÷ liÖu vµo bÊt k×. VÝ dô, khi mét danh b¹ ®iÖn tho¹i gåm tõ mét tr¨m sè ®iÖn tho¹i trë lªn, c¸ch tæ chøc thµnh th­ môc vµ viÖc t×m kiÕm theo th­ môc ch¾c ch¾n sÏ gióp ta t×m kiÕm tèt h¬n lµ viÖc t×m kiÕm tuÇn tù. Nh­ng thÕ nµo lµ thuËt gi¶i tèt. §©y lµ néi dung nghiªn cøu cña lý thuyÕt ®é phøc t¹p tÝnh to¸n. Lý thuyÕt nµy cã thÓ ®­îc x©y dùng trªn mét nÒn t¶ng to¸n häc chÆt chÏ tõ mét hÖ tiªn ®Ò. Tuy nhiªn, trong ph¹m vi gi¸o tr×nh nµy, chóng t«i chØ giíi thiÖu mét sè vÊn ®Ò ®¬n gi¶n . Khi dïng m¸y tÝnh thùc hiÖn mét ch­¬ng tr×nh thÓ hiÖn mét thuËt gi¶i nµo ®ã, hÖ ®iÒu hµnh cÇn cung cÊp cho ch­¬ng tr×nh ®ã c¸c tµi nguyªn nh­ giê CPU, bé nhí, . . . §é phøc t¹p cña mét thuËt gi¶i ®­îc ®o b»ng sè l­îng c¸c tµi nguyªn cÇn dïng ®Ó thùc hiÖn ch­¬ng tr×nh ®ã. Khi so s¸nh hai thuËt gi¶i cïng gi¶i mét bµi to¸n, mét thuËt gi¶i nµy ®­îc xem lµ tèt h¬n thuËt gi¶i kia nÕu nã dïng Ýt tµi nguyªn h¬n. Trong c¸c tµi nguyªn cÇn dïng ®Ó ch¹y ch­¬ng tr×nh, hiÖn nay ng­êi ta quan t©m nhiÒu nhÊt ®Õn thêi gian v× ®ã lµ d¹ng tµi nguyªn kh«ng t¸i t¹o ®­îc. Mét thuËt gi¶i ®­îc xem lµ tèt nÕu ch­¬ng tr×nh t­¬ng øng ch¹y nhanh hay chÝnh x¸c h¬n, ch¹y trong thêi gian chÊp nhËn ®­îc. Do ®ã, ®Ó ®¸nh gi¸ ®é phøc t¹p cña mét thuËt gi¶i, ta th­êng ­íc tÝnh sè thao t¸c c¬ b¶n cÇn dïng ®Ó thùc hiÖn thuËt gi¶i. Thao t¸c c¬ b¶n cña mét thuËt gi¶i lµ thao t¸c mµ sè lÇn thùchiÖn nã kh«ng Ýt h¬n sè lÇn thùc hiÖn c¸c thao t¸c kh¸c. VÝ dô vÒ thao t¸c c¬ b¶n: Bµi to¸n  Thao t¸c c¬ b¶n   T×m phÇn tö x trong mét danh s¸ch  So s¸nh x víi mét phÇn tö cña danh s¸ch   Nh©n hai ma trËn thùc  PhÐp nh©n hai sè thùc, phÐp céng hai sè thùc   S¾p xÕp mét danh s¸ch  So s¸nh hai phÇn tö cña danh s¸ch   Víi mçi bµi to¸n, ta xÐt kÝch th­íc ®Çu vµo hay gäi ®¬n gi¶n lµ kÝch th­íc cña bµi to¸n. KÝch th­íc ®Çu vµo mét bµi to¸n ®­îc ®o b»ng sè l­îng d÷ liÖu vµo cÇn xö lý. VÝ dô nÕu d÷ liÖu vµo lµ mét d·y sè cã N sè h¹ng th× kÝch th­íc bµi to¸n d­îc xem b»ng N, nÕu d÷ liÖu vµo lµ mét ®å thÞ cã N ®Ønh, kÝch th­íc bµi to¸n b»ng N, nÕu d÷ liÖu vµo lµ mét x©u ký tù ®é dµi L th× kÝch th­íc bµi to¸n b»ng L, nÕu d÷ liÖu vµo lµ mét b¶ng cã M dßng vµ N cét th× kÝch th­íc bµi to¸n b»ng MxN. . . Khi ®ã, sè c¸c thao t¸c c¬ b¶n mµ mét thuËt gi¶i sÏ ®­îc biÓu thÞ nh­ mét hµm f(K) cña biÕn sè K lµ kÝch th­íc cña bµi to¸n. Khi ®¸nh gi¸ hµm f(K) ng­êi ta th­êng dïng ký hiÖu O hay chÝnh x¸c h¬n lµ kh¸i niÖm ( cña gi¶i tÝch cã nghÜa lµ cïng bËc. VÝ dô, gi¶i thuËt t×m Min-Max cña mét d·y sè trong Môc 8.1 cã ®é phøc t¹p 2N, ta nãi ®é phøc t¹p ®ã cì ((N) cã nghÜa lµ cïng bËc víi N khi N tiÕn ®Õn v« cïng; t­¬ng tù, gi¶i thuËt s¾p xÕp d·y sè cã ®é phøc t¹p cë ((N2). ViÖc dïng ký hiÖu ( ®Ó thÓ hiÖn ®é phøc t¹p cña gi¶i thuËt cho ta mét ®¸nh gi¸ tæng thÓ kh«ng bÞ sa vµo nh÷ng tÝnh to¸n tØ mØ h¬n nh­ng kh«ng thËt cÇn thiÕt. VÝ dô, cïng lµ hai phÐp to¸n céng vµ nh©n hai sè, râ rµng phÐp céng thùc hiÖn nhanh h¬n nhiÒu so víi phÐp nh©n nh­ng sù kh¸c biÖt ®ã chØ thÓ hiÖn b»ng viÖc thêi gian tÝnh to¸n sai kh¸c mét h»ng sè nh©n. Do ®ã, nÕu dïng ký hiÖu (, ta cã thÓ bá qua sù kh¸c biÖt ®ã. Khi nãi vÒ ®é phøc t¹p vÒ thêi gian, cã mét sè bËc ®­îc sö dông th­êng xuyªn vµ ng­êi ta ®· ®Æt tªn cho chóng. Mét c¸ch v¾n t¾t, nÕu mét thuËt to¸n cã ®é phøc t¹p lµ t vµ t n0 vµ c lµ mét h»ng sè d­¬ng, cßn n lµ kÝch cì ®Çu vµo th× ng­êi ta gäi thuËt to¸n ®ã cã ®é phøc t¹p tuyÕn tÝnh. NÕu t < cn2 th× t ®­îc gäi lµ cã ®é phøc t¹p b×nh ph­¬ng. T­¬ng tù t ®­îc gäi lµ cã ®é phøc t¹p lËp ph­¬ng, ®a thøc hay mò nÕu nã cã bËc lÇn l­ît cña c¸c hµm n3, nk hay an , víi k vµ a lµ nh÷ng h»ng sè nµo ®ã. §Ó dÔ h×nh dung vÒ sù t¨ng cña mét sè hµm víi n lµ kÝch th­íc cña bµi to¸n, d­íi ®©y ta ph¸c häa mét sè ®å thÞ cña ®é phøc t¹p loga, ®é phøc t¹p tuyÕn tÝnh, ®é phøc t¹p b×nh ph­¬ng, ®é phøc t¹p lËp ph­¬ng vµ ®é phøc t¹p mò. H×nh 2.1: Ph¸c ho¹ c¸c ®­êng biÓu diÔn ®é phøc t¹p cña mét sè thuËt gi¶i ----------------------------------------- 1.3. Ph©n tÝch thuËt to¸n 1.3.1. Kh¸i niÖm vÒ ph©n tÝch thuËt to¸n Ph©n tÝch mét gi¶i thuËt cã nghÜa lµ ®¸nh gi¸ ®é phøc t¹p cña gi¶i thuËt ®ã. Thùc ra kh«ng cã mét cÈm nang ®Ó ph©n tÝch thuËt to¸n mµ chñ yÕu lµ ta sö dông kiÕn thøc to¸n häc, sù trùc quan, suy luËn, vµ mét sè kÜ thuËt c¬ b¶n ®Ó tÝnh ®é phøc t¹p cña mét thuËt gi¶i. Cã mét sè cÊu tróc phæ biÕn trong c¸c thuËt gi¶i: cÊu tróc tuÇn tù, cÊu tróc lÆp vµ cÊu tróc ®Ö quy. Víi cÊu tróc tuÇn tù: NÕu ta cã hai ®o¹n tr×nh thùc hiÖn tuÇn tù lµ P1 vµ P2 , ®é phøc t¹p cña chóng lÇn l­ît lµ t1 = O(f(n)), t2 = O(g(n)) th× ®é phøc t¹p cña c¶ hai ®o¹n P1 vµ P2 chÝnh lµ O(max(f(n), g(n)). VÝ dô: Khi ta thùc hiÖn tuÇn tù hai ®o¹n tr×nh P1 vµ P2, P1 cã ®é phøc t¹p lµ O(n2) vµ P2 cã ®é phøc t¹p lµ O(n3) th× hîp hai ®o¹n P1 vµ P2 sÏ cã ®é phøc t¹p lµ O(n3). T­¬ng tù, nÕu P1 cã ®é phøc t¹p lµ O(2n) cßn P2 cã ®é phøc t¹p lµ O(n5) th× ®é phøc t¹p cña ®o¹n tr×nh hîp lµ O(2n). §Ó ý r»ng, víi n ®ñ lín ta lu«n cã: n! > an > nk > logn. CÊu tróc lÆp th­êng cã mét trong c¸c d¹ng sau For i:=a to b do ; (1) While Do ; (2) Repeat Until ; (3) Sè thao t¸c cÇn thùc hiÖn trong mét cÊu tróc lÆp cã thÓ ®Ô dµng ­íc tÝnh ®­îc sau khi ®· tÝnh ®­îc c¸c thao t¸c cÇn thùc hiÖn trong . §èi víi cÊu tróc lÆp lo¹i (1), nÕu sè thao t¸c trong lµ S th× sè thao t¸c cÇn thùc hiÖn tæng céng kh«ng lín h¬n S(b-a). VÝ dô: trong phÐp nh©n hai ma trËn vu«ng A vµ B cÊp n ta cã: Procedure Nhanmatran(A,B) Var C; Begin for i ( 1 to n do for j ( 1 to n do Begin C[i,j] ( 0 for k ( 1 to n do C[i,j] ( C[i,j] + a[i,k] * b[k,j] End; Return C; End Ta thÊy ngay lµ vßng lÆp trong cïng (k lµ biÕn ch¹y) cã ®é phøc t¹p O(n), vßng lÆp trong tiÕp theo (j lµ biÕn ch¹y) còng cã ®é phøc t¹p O(n) vµ vßng lÆp ngoµi cïng (víi i lµ biÕn ch¹y) víi ®é phøc t¹p O(n). Do ®ã toµn bé ch­¬ng tr×nh cña ta cã ®é phøc t¹p O(n3). §èi víi cÊu tróc lÆp lo¹i (2) vµ (3), c¨n cø vµo ®iÒu kiÖn l« gic, ta cã thÓ ­íc l­îng ®­îc sè lÇn lÆp tèi ®a do ®ã cã thÓ tÝnh ®­îc sè tèi ®a c¸c thao t¸c cÇn thùc hiÖn. §èi víi c¸c cÊu tróc ®Ö quy, viÖc ­íc l­îng sè thao t¸c khã kh¨n h¬n v× nãi ta ph¶i tiÕn hµnh tÝnh sè thao t¸c theo mét c«ng thøc truy håi. Sau ®©y ta sÏ xÐt mét sè vÝ dô n÷a. VÝ dô 1. XÐt bµi to¸n Input. M¶ng mét chiÒu A[1..N] gåm c¸c sè nguyªn; Output. Gi¸ trÞ nhá nhÊt Min vµ gi¸ trÞ lín nhÊt Max cña c¸c phÇn tö cña m¶ng; XÐt thuËt gi¶i cã tªn FindMin-Max(1,N) sau: B­íc 1. NÕu N=1 th× nÕu Min = Max = A[1] vµ kÕt thóc nÕu kh«ng th× chuyÓn sang B­íc 2. B­íc 2. NÕu N=2 th× (A[1](A[2] th× Min = A[1] vµ Max = A[2] nÕu kh«ng th× Min = A[2] vµ Max = A[1] vµ kÕt thóc nÕu kh«ng th× chuyÓn sang B­íc 3. B­íc 3. Gäi FindMin1-Max1(1,N Div 2) vµ FindMin2-Max2(N div 2 +1,N); nÕu Min1(Min2 th× Min = Min1 nÕu kh«ng th× Min=Min2 vµ nÕu Max1(Max2 th× Max = Max1 nÕu kh«ng th× Max=Max2; kÕt thóc. NÕu dé phøc t¹p tÝnh theo sè lÇn so s¸nh C(N) c¸c sè th× ta cã C(2) = 1; C(2K) = 2C(K) +2 víi K>1; C(2K+1) = C(K) + C(K+1) + 2; Tõ ®ã ta cã thÓ tÝnh ®­îc C(N) = 3N/2 - 2. VÝ dô 2. Bµi to¸n Th¸p Hµ Néi Ta sÏ diÔn t¶ bµi to¸n nµy b»ng ng«n ng÷ th«ng th­êng. Cã N ®Üa trßn ®­êng kÝnh kh¸c nhau víi lç thñng ë t©m vµ ba cäc 1, 2, 3. Ban ®Çu N ®Üa ®Æt trªn cäc 1, ®Üa lín h¬n n»m d­íi ®Üa nhá h¬n. Mét di chuyÓn ®Üa thùc hiÖn b»ng c¸ch chuyÓn ®Üa trªn cïng ë cäc A (nÕu cã) ®Æt lªn trªn cïng mét cäc B kh¸c víi ®iÒu kiÖn ®Üa ®ã nhá h¬n ®Üa (nÕu cã) ®ang n»m trªn cïng ®Üa ë cäc B. CÇn tiÕn hµnh mét d·y c¸c di chuyÓn ®Üa sao cho cuèi cïng, N ®Üa ®­îc chuyÓn sang cäc 2. Bµi to¸n nµy g¾n víi mét giai tho¹i vÒ sù thö th¸ch cña Th­îng ®Õ ®èi víi lßng kiªn tr× cña con ng­êi. NÕu sè ®Üa b»ng 64, mçi di chuyÓn ®Üa thùc hiÖn trong 1 gi©y vµ mét ng­êi thùc hiÖn mét d·y c¸c di chuyÓn ®óng ®¾n th× ng­êi ®ã ph¶i mÊt 500 tû n¨m míi di chuyÓn xong. ViÖc cÇn chuyÓn N ®Üa tõ cäc 1 sang cäc 2 mét c¸ch hîp lÖ vµ tèt nhÊt cã thÓ xem lµ tr­êng hîp riªng cña viÖc chuyÓn M ®Üa nhá nhÊt tõ cäc i sang cäc j ,1(i(3, 1(j(3, i(j, mét c¸ch hîp lÖ vµ tèt nhÊt cã thÓ. NÕu ta thÓ hiÖn viÖc ®ã b»ng mét thñ tôc Procedure Hanoi(m,i,j); ViÖc ta cÇn lµm chÝnh lµ Hanoi(N,1,2); §Ó lµm viÖc ®ã, do quy ®Þnh cña mét di chuyÓn ®Üa, ta cÇn chuyÓn m-1 ®Üa nhá nhÊt tõ cäc i sang cäc thø ba, ®ã lµ cäc k = 6-i-j, chuyÓn ®Üa thø M tõ cäc i sang cäc j vµ sau ®ã chuyÓn M-1 ®Üa tõ cäc k sang cäc j. NÕu viÕt b»ng Pascal, ta cã Procedure Hanoi(M,i,j: Byte); Begin If m=0 then Exit; Hanoi(M-1,i,6-i-j); Writeln(i,’ – ‘,j); Hanoi(M-1,6-i-j,j); End; NÕu ký hiÖu T(M) lµ sè di chuyÓn cÇn thùc hiÖn (xem nh­ mét thao t¸c c¬ b¶n), ta cã T(M) = 2.T(M-1) - 1 (*) Nh­ vËy nÕu xem N lµ kÝch th­íc cña bµi to¸n th× ®é phøc t¹p tÝnh to¸n cña thuËt gi¶i trªn lµ T(N). Tõ hÖ thøc (*), ta cã thÓ suy ra T(N) = 2N - 1. HÖ thøc (*) lµ mét hÖ thøc truy håi. 1.3.2. Mét sè quan ®iÓm ph©n tÝch thuËt to¸n C¸ch ph©n tÝch thuËt to¸n trong môc 8.2.2 cßn ®­îc gäi lµ ph©n tÝch theo t×nh huèng xÊu nhÊt (Worst-Case Analysis). Víi mçi thuËt gi¶i ®èi víi bµi to¸n kÝch th­íc K, ta lu«n ®¸nh gi¸ sè tèi ®a c¸c thao t¸c c¬ b¶n cÇn tiÕn hµnh lµ bao nhiªu. Cã nhiÒu c¸ch kh¸c ®Ó ph©n tÝch thuËt gi¶i nh­ ph©n tÝch trung b×nh (Average Analysis), ph©n tÝch tiÖm cËn (Asymptotic Analysis). Ta sÏ giíi thiÖu c¸ch ph©n tÝch trung b×nh. C©u chuyÖn b¾t ®Çu tõ viÖc xem xÐt thuËt gi¶i ®¬n h×nh ®èi víi bµi to¸n Quy ho¹ch tuyÕn tÝnh. Bµi to¸n nµy cã thÓ ph¸t biÓu trong ng«n ng÷ ®¹i sè tuyÕn tÝnh nh­ sau: I. Ma trËn A gåm M dßng, N cét; VÐc t¬ cét B M chiÒu; vÐc t¬ dßng C N chiÒu; O. CÇn t×m vÐc t¬ cét N chiÒu X sao cho AX(B vµ CX ®¹t gi¸ trÞ nhá nhÊt. Theo c¸ch ®¸nh gi¸ xÊu nhÊt, ®é phøc t¹p cña thuËt to¸n ®¬n h×nh cì hµm mò. Tuy nhiªn, tr¶i qua mÊy chôc n¨m dïng thuËt gi¶i nµy ®Ó gi¶i rÊt nhiÒu bµi to¸n ph¸t sinh trong nhiÒu lÜnh vùc kh¸c nhau, c¸c ch­¬ng tr×nh vÉn ch¹y trong thêi gian chÊp nhËn ®­îc. C«ng tr×nh nghiªn cøu cña nhµ to¸n häc S.. Smale cho kÕt qu¶ ®é phøc t¹p trung b×nh cña thuËt to¸n ®¬n h×nh lµ ®a thøc (thËm chÝ bËc thÊp) ®èi víi kÝch th­íc bµi to¸n. Sau kÕt qu¶ nµy, ng­êi ta còng chøng tá ®­îc cã nhiÒu thu©t gi¶i kh«ng tèt theo c¸ch ®¸nh gi¸ xÊu nhÊt nh­ng tÝnh trung b×nh vÉn tèt. VÒ ®¹i thÓ, ®Ó ®¸nh gi¸ ®é phøc t¹p trung b×nh mét thuËt gi¶i, ta gi¶ sö mäi d÷ liÖu ®Òu cã x¸c xuÊt xuÊt hiÖn nh­ nhau, trªn c¬ së ®ã, ®é phøc t¹p trung b×nh ®­îc tÝnh nh­ trung b×nh x¸c suÊt cña c¸c sè b­íc tÝnh to¸n ®èi víi c¸c t×nh huèng cña d÷ liÖu. Chi tiÕt vÒ vÊn ®Ò nµy còng sÏ ®­îc lµm râ trong m«n lý thuyÕt ®é phøc t¹p tÝnh to¸n. Bµi tËp H·y ph¸t biÓu theo quan niÖm cña Tin häc vÒ bµi to¸n vµ tr×nh bµy thuËt gi¶i cho mçi mét trong c¸c bµi to¸n sau. §¸nh gi¸ ®é phøc t¹p cña tõng thuËt gi¶i. Bµi 1. Gi¶i vµ biÖn luËn ph­¬ng tr×nh bËc nhÊt tæng qu¸t: aX + b = 0. Bµi 2. Gi¶i vµ biÖn luËn ph­¬ng tr×nh bËc hai tæng qu¸t: aX2 + bX + c = 0. Bµi 3. Gi¶i vµ biÖn luËn hÖ ph­¬ng tr×nh bËc nhÊt hai Èn sè tæng qu¸t. Bµi 4. Gi¶i vµ biÖn luËn ph­¬ng tr×nh trïng ph­¬ng tæng qu¸t: aX4 + bX2 + c = 0. Bµi 5. Gi¶i vµ biÖn luËn hÖ hai ph­¬ng tr×nh bËc hai a1X2 + b1X + c1 = 0 vµ a2X2 + b2X + c2 = 0. Bµi 6. Cho mét h×nh ch÷ nhËt ABCD víi hai c¹nh nguyªn d­¬ng AB = M vµ BC = N. H×nh ch÷ nhËt ®­îc chia thµnh c¸c « vu«ng ®¬n vÞ. H·y t×m sè « vu«ng cã ®iÓm chung víi ®­êng chÐo AC. Bµi 7. Cho mét h×nh ch÷ nhËt ABCD víi hai c¹nh nguyªn d­¬ng AB=M vµ BC= N. H×nh ch÷ nhËt ®­îc chia thµnh c¸c « vu«ng ®¬n vÞ. H·y t×m sè « vu«ng cã ®iÓm trong chung víi ®­êng chÐo AC. Bµi 8. XÐt d·y v« h¹n c¸c ch÷ sè A nhËn ®­îc b»ng c¸ch viÕt liªn tiÕp c¸c sè nguyªn d­¬ng liªn tiÕp t¨ng dÇn b¾t ®Çu tõ 1, 2, 3, 4, . . . . 1234567891011121314151617181920212223..... Cho sè nguyªn d­¬ng N. H·y t×m ch÷ sè thø N cña d·y A. VÝ dô víi N =13, ch÷ sè thø N cña d·y trªn lµ 1. Bµi 9. Cho sè nguyªn d­¬ng N. LËp d·y B c¸c ch÷ sè nhËn ®­îc b»ng c¸ch viÕt c¸c sè nguyªn d­¬ng liªn tiÕp t¨ng dÇn b¾t ®Çu tõ 1, 2, 3, 4, . . . cho tíi N. H·y t×m ch÷ sè thø N tÝnh tõ ch÷ sè cuèi cïng cña d·y B. Bµi 10. XÐt tËp A c¸c sè nguyªn d­¬ng ®­îc x¸c ®Þnh nh­ sau: 1A. NÕu KA th× 2K+1 vµ 3K+1 A. A gåm vµ chØ gåm c¸c sè tho¶ m·n mét trong hai ®iÒu kiªn 1 vµ 2. Cho mét sè nguyªn d­¬ng N kh«ng lín h¬n 60000. H·y t×m sè c¸c sè thuéc A kh«ng lín h¬n N. Bµi 11. Hai ng­êi A vµ B ch¬i trß ch¬i sau: A bÝ mËt chän mét sè nguyªn d­¬ng N vµ nãi râ N kh«ng lín mét sè M nguyªn d­¬ng vµ B ®o¸n xem A chän sè nµo. B ®­îc quyÒn hái A mét sè c©u hái vµ A sÏ chØ tr¶ lêi ®óng hay sai vµ mäi c©u tr¶ lêi cña A lµ chÝnh x¸c. H·y chän cho B mét sè Ýt nhÊt c©u hái ®Ó sau khi hái xong, B ®o¸n ®óng ®­îc sè N. Bµi 12. §Ó tæng kÕt ®iÓm cuèi häc kú vµ tiÕn hµnh ph©n lo¹i kÕt qu¶ häc tËp cña c¸c häc sinh trong mét líp häc, gi¸o viªn chñ nhiÖm cã sæ ®iÓm cña líp. CÇn tÝnh ®iÓm trung b×nh tõng m«n häc vµ tÝnh ®iÓm trung b×nh toµn häc kú cho tõng häc sinh. Víi mçi m«n häc, c¸c ®iÓm kiÓm tra miÖng, kiÓm tra 15 phót tÝnh hÖ sè 1, c¸c ®iÓm kiÓm tra 1 tiÕt tÝnh hÖ sè 2, ®iÓm kiÓm tra häc kú tÝnh hÖ sè 3. Khi tÝnh ®iÓm trung b×nh toµn häc kú, c¸c ®iÓm trung b×nh m«n cña V¨n, To¸n tÝnh hÖ sè 3, cña Lý, Ho¸, Ngo¹i ng÷ - hÖ sè 2, c¸c m«n cßn l¹i - hÖ sè 1. Cã n¨m møc ph©n lo¹i häc tËp: kÐm, trung b×nh, kh¸, giái vµ xuÊt s¾c t­¬ng øng víi ®iÓm trung b×nh toµn häc kú thuéc c¸c miÒn: <5, [5,7), [7,8), [8,9) vµ [9,10]. H·y viÕt ra cho gi¸o viªn chñ nhiÖm c¸c b­íc tiÕn hµnh c«ng viÖc nµy. Bµi 13. Trªn mÆt ph¼ng to¹ ®é cho to¹ ®é cña bèn ®iÓm A, B, C, D trong ®ã kh«ng cã ba ®iÓm nµo th¼ng hµng. H·y cho biÕt hai ®o¹n AB vµ CD cã ®iÓm chung hay kh«ng. Bµi 14. Trªn mÆt ph¼ng to¹ ®é cho to¹ ®é cña bèn ®iÓm A, B, C, D trong ®ã kh«ng cã ba ®iÓm nµo th¼ng hµng. H·y cho biÕt hai ®o¹n AB vµ CD cã ®iÓm trong chung hay kh«ng. Bµi 15. Cho h×nh ch÷ nhËt ABCD vµ mét ®iÓm M trªn mÆt ph¼ng to¹ ®é. BiÕt to¹ ®é cña A, B, C, D, M. H·y cho biÕt kh¶ n¨ng nµo trong hai kh¶ n¨ng sau x¶y ra: M thuéc h×nh ch÷ nhËt ABCD. M kh«ng thuéc h×nh ch÷ nhËt ABCD. Bµi 16. Cho h×nh ch÷ nhËt ABCD vµ hai ®iÓm kh¸c nhau M, N trªn mÆt ph¼ng to¹ ®é. BiÕt to¹ ®é cña A, B, C, D, M, N. H·y cho biÕt kh¶ n¨ng nµo trong ba kh¶ n¨ng sau x¶y ra: §o¹n MN n»m trong (cã thÓ cã ®iÓm trªn biªn) h×nh ch÷ nhËt ABCD. §o¹n MN n»m ngoµi h×nh ch÷ nhËt ABCD. §o¹n MN cã ®iÓm n»m ngoµi h×nh ch÷ nhËt ABCD vµ cã ®iÓm n»m trong h×nh ch÷ nhËt ABCD. Bµi 17. Trªn mÆt ph¼ng to¹ ®é cho ®a gi¸c P1 . . .PN. §a gi¸c ®­îc gäi lµ tù c¾t nÕu cã hai c¹nh PIPI+1 vµ PJPJ+1 víi I<J-1 (quy ­íc ®Ønh PN+1 lµ ®Ønh P1) cã ®iÓm chung. §a gi¸c ®­îc gäi lµ låi nÕu víi bÊt kú c¹nh nµo cña ®a gi¸c, toµn bé ®a gi¸c n»m vÒ mét phÝa cña ®­êng th¼ng ®i qua c¹nh ®ã. BiÕt to¹ ®é c¸c ®Ønh cña ®a gi¸c. H·y cho biÕt ®a gi¸c cã tù c¾t kh«ng? NÕu ®a gi¸c kh«ng tù c¾t, h·y cho biÕt ®a gi¸c cã låi kh«ng?. NÕu ®a gi¸c kh«ng låi, h·y chän mét sè Ýt nhÊt c¸c ®Ønh sao cho mäi ®Ønh P1, . .,PN ®Òu thuéc ®a gi¸c låi cã c¸c ®Ønh lµ c¸c ®Ønh ®­îc chän (®a gi¸c nµy ®­îc gäi lµ bao låi cña tËp ®iÓm P1, . .,PN). ch­¬ng 2: Tæng quan vÒ kiÓu d÷ liÖu trõu t­îng Ch­¬ng nµy giíi thiÖu vÒ kiÓu d÷ liÖu trõu t­îng, ®ã lµ mét kh¸i niÖm rÊt quan träng trong lËp tr×nh. Kh¸i niÖm nµy cho phÐp ta t¹o ra nh÷ng ®¬n vÞ ch­¬ng tr×nh dÔ b¶o tr×, an toµn vµ cã thÓ ®­îc dïng bëi nhiÒu ch­¬ng tr×nh kh¸c nhau. §Ó hiÓu tèt tõ ch­¬ng 3 ®Õn ch­¬ng 6, b¹n ®äc cÇn dµnh thêi gian ®äc kÜ ch­¬ng nµy. Kh¸i niÖm vÒ kiÓu d÷ liÖu trõu t­îng Khi lËp tr×nh vµ gi¶i quyÕt c¸c bµi to¸n trªn m¸y tÝnh, mét trong nh÷ng ý t­ëng cã ý nghÜa nhÊt, cã søc m¹nh nhÊt lµ kh¸i niÖm trõu t­îng ho¸. §ã chÝnh lµ c¸ch nh×n bµi to¸n mét c¸ch kh¸i qu¸t, t¹m thêi bá qua tÊt c¶ nh÷ng chi tiÕt cô thÓ. Còng cã thÓ m« t¶ sù trõu t­îng ho¸ sù vËt lµ viÖc nh×n nh÷ng nÐt bao qu¸t bªn ngoµi mµ ch­a ®Ó ý ®Õn nh÷ng chi tiÕt bªn trong. Trong c«ng viÖc nãi chung, nÕu kh«ng cã kh¸i niÖm trõu t­îng ho¸ th× khã cã thÓ hiÓu vµ qu¶n lý ®­îc nh÷ng hÖ thèng lín vµ phøc t¹p. Ch¼ng h¹n, ta h·y h×nh dung tæng gi¸m ®èc cña mét nhµ m¸y kh«ng qu¶n lý nhµ m¸y ®ã th«ng qua c¸c ph©n x­ëng mµ l¹i trùc tiÕp qu¶n lý tõng c«ng nh©n, tõng d©y chuyÒn s¶n xuÊt, tõng ®Çu m¸y th× sù viÖc sÏ khã biÕt chõng nµo. Khi häc phÇn ®¹i c­¬ng vÒ lËp tr×nh, häc sinh ®· ®­îc lµm quen víi nh÷ng vÝ dô ®iÓn h×nh vÒ trõu t­îng ho¸: Trõu t­îng ho¸ thao t¸c, ®ã chÝnh lµ viÖc x©y dùng vµ sö dông c¸c ch­¬ng tr×nh con. Mçi ch­¬ng tr×nh con thùc hiÖn mét t¸c vô x¸c ®Þnh nµo ®ã vµ trong ch­¬ng tr×nh chÝnh, cã thÓ xem nã nh­ mét thao t¸c mÆc dï trong thùc tÕ nã cã thÓ ®­îc cµi ®Æt b»ng mét d·y gåm rÊt nhiÒu thao t¸c. Ch¼ng h¹n, dïng c¬ chÕ thñ tôc vµ hµm trong ng«n ng÷ Pascal, häc sinh ®· ®­îc häc c¸ch x©y dùng nh÷ng ®¬n vÞ ch­¬ng tr×nh vµ ®­a nã vµo th­ viÖn ®Ó sö dông. VÝ dô, ta cã ch­¬ng tr×nh con s¾p xÕp nhanh Quicksort nh­ sau: Procedure Quicksort (A,n), s¾p sÕp mét m¶ng A gåm n sè thùc theo chiÒu t¨ng dÇn. Ta cã thÓ cµi ®Æt vµ ®­a nã vµo th­ viÖn vµ sau ®ã nã ®­îc xem nh­ lµ mét bé phËn cña ng«n ng÷. ë giai ®o¹n thiÕt kÕ thuËt to¸n, ta chØ quan t©m ®Õn viÖc mµ thñ tôc sÏ thùc hiÖn mµ kh«ng cÇn quan t©m nã thùc hiÖn viÖc ®ã nh­ thÕ nµo. Ch¼ng h¹n, nÕu ta viÕt ®o¹n ch­¬ng tr×nh sau ®©y For i:=1 to 300 do Read (DiemThi[i]); Quicksort (DiemThi, 300); Ng­êi ®äc sÏ thÊy hoµn toµn dÔ hiÓu cho dï hä ch­a cÇn biÕt chi tiÕt bªn trong thñ tôc Quicksort, tøc lµ ch­a cÇn biÕt nã s¾p xÕp c¸c phÇn tö cña m¶ng nh­ thÕ nµo. ViÖc giÊu ®­îc nh÷ng chi tiÕt cµi ®Æt bªn trong ch­¬ng tr×nh con lµm cho c¬ chÕ sö dông ch­¬ng tr×nh con trë thµnh mét trong nh÷ng phÇn quan träng nhÊt cña bÊt k× mét ng«n ng÷ lËp tr×nh bËc cao nµo. C¸ch trõu t­îng ho¸ ta võa nªu chÝnh lµ trõu t­îng ho¸ thao t¸c. Chän nh÷ng thao t¸c thÝch hîp thùc hiÖn trªn c¸c cÊu tróc d÷ liÖu hîp lý lµ mét c«ng viÖc hÕt søc quan träng cña lËp tr×nh. Còng nh­ viÖc cÇn thiÕt ph¶i trõu t­îng ho¸ thao t¸c, b©y giê ta më réng ý t­ëng trõu t­îng ho¸ cho cÊu tróc d÷ liÖu. Chóng ta sÏ x©y dùng kh¸i niÖm kiÓu d÷ liÖu trõu t­îng. §Ó gi¶i thÝch kh¸i niÖm nµy, tr­íc hÕt ta xÐt s¬ ®å sau vÒ c¸c møc cÊu tróc d÷ liÖu: KiÓu d÷ liÖu ®­îc x©y dùng bëi ng­êi lËp tr×nh ®Ò gi¶i nh÷ng bµi to¸n nµo ®ã.   Møc C. KiÓu d÷ liÖu ®­îc trùc tiÕp hç trî bëi phÇn cøng.   KiÓu d÷ liÖu ®­îc cung cÊp bëi c¸c ng«n ng÷ lËp tr×nh bËc cao.   Møc B. Møc A. ë møc thÊp nhÊt, møc A trong biÓu ®å chÝnh lµ nh÷ng kiÓu d÷ liÖu ®­îc trùc tiÕp hç trî bëi phÇn cøng, vÝ dô kiÓu sè nguyªn, kiÓu sè thùc vµ kiÓu kÝ tù. Nh÷ng kiÓu d÷ liÖu nµy cßn ®­îc gäi lµ kiÓu d÷ liÖu nguyªn thuû hay kiÓu ®¬n. Trong ®a sè c¸c ng«n ng÷ lËp tr×nh bËc cao, c¸c kiÓu d÷ liÖu ®· rÊt phong phó: KiÓu miÒn con, kiÓu v« h­íng, kiÓu boolean, kiÓu m¶ng, kiÓu b¶n ghi, kiÓu tËp hîp, kiÓu con trá... Nh÷ng kiÓu nµy kh«ng thùc sù tån t¹i theo nghÜa ®­îc trùc tiÕp hç trî bëi phÇn cøng. NhiÒu khi chóng cßn ®­îc gäi lµ kiÓu d÷ liÖu ¶o. Mét ch­¬ng tr×nh, gäi lµ ch­¬ng tr×nh dÞch ®· t¹o ra c¸c kiÓu d÷ liÖu nµy, chóng còng cßn ®­îc gäi lµ c¸c kiÓu d÷ liÖu cña ng«n ng÷ bËc cao. Ch¼ng h¹n, ch­¬ng tr×nh dÞch cã thÓ x©y dùng kiÓu d÷ liÖu Boolean b»ng viÖc ¸nh x¹ c¸c gi¸ trÞ logic True vµ False lªn tËp hai gi¸ trÞ nguyªn –1 vµ +1. ChÝnh ch­¬ng tr×nh dÞch còng chuyÓn c¸c thao t¸c nh­ Not, And, Or thµnh c¸c thao t¸c trªn tËp hai sè nguyªn –1 vµ +1. §èi víi ng­êi lËp tr×nh nh÷ng kiÓu d÷ liÖu ¶o nµy tån t¹i gièng nh­ nh÷ng kiÓu d÷ liÖu nguyªn thñy (møc A) vµ ng­êi lËp tr×nh cã thÓ trùc tiÕp sö dông nã trong c¸c ch­¬ng tr×nh. ViÖc chuyÓn nh÷ng cÊu tróc d÷ liÖu ®ã thµnh c¸c chØ thÞ theo ng«n ng÷ m¸y hoÆc c¸c cÊu tróc d÷ liÖu nguyªn thñy lµ cña ch­¬ng tr×nh dÞch chø kh«ng ph¶i cña ng­êi lËp tr×nh. Lµ mét ng­êi lËp tr×nh, ng­êi thiÕt kÕ ch­¬ng tr×nh, chóng ta kh«ng muèn m×nh chØ bÞ giíi h¹n bëi nh÷ng g× mµ phÇn cøng trùc tiÕp cho phÐp, chóng ta cã thÓ sö dông tÊt c¶ nh÷ng cÊu tróc d÷ liÖu ¶o mµ ng­êi x©y dùng ng«n ng÷ ®· t¹o ra. H¬n thÕ n÷a, ta còng kh«ng nªn chØ giíi h¹n m×nh bëi nh÷ng kiÓu d÷ liÖu mµ ng«n ng÷ cung cÊp. Ta cã thÓ t¹o ra nh÷ng kiÓu d÷ liÖu kh«ng cã s½n trong ng«n ng÷. Cô thÓ lµ ta cã thÓ s¸ng t¹o, x©y dùng nh÷ng kiÓu d÷ liÖu míi, phôc vô cho bµi to¸n cña ta. Ngay tõ ®Çu, ta ch­a cÇn ph¶i lo l¾ng ®Õn viÖc lµm thÕ nµo ®Ó dïng nh÷ng cÊu tróc d÷ liÖu s½n cã cña ng«n ng÷ ®Ó cµi ®Æt c¸c kiÓu d÷ liÖu míi ®ã. §ã chÝnh lµ mét trong nh÷ng c«ng viÖc quan träng nhÊt mµ ta cÇn thùc hiÖn - C«ng viÖc t¹o ra nh÷ng kiÓu d÷ liÖu míi - KiÓu d÷ liÖu ®­îc s¸ng t¹o bëi ng­êi lËp tr×nh hay ta cßn gäi lµ kiÓu d÷ liÖu trõu t­îng. (Trong tiÕng Anh, kiÓu d÷ liÖu trõu t­îng ®­îc gäi lµ Abstract Data Type vµ viÕt t¾t lµ ADT). C¬ chÕ trªn cho phÐp ng­êi lËp tr×nh kh«ng bÞ giíi h¹n vµo chØ nh÷ng cÊu tróc d÷ liÖu ng«n ng÷ lËp tr×nh cung cÊp mµ cho phÐp hä t¹o ra nh÷ng kiÓu d÷ liÖu míi, phï hîp víi bµi to¸n mµ hä cÇn gi¶i. ViÖc trõu t­îng ho¸ d÷ liÖu t¹o ra mét sù t¸ch biÖt (vÒ kh¸i niÖm) gi÷a c¸i nh×n kh¸i qu¸t mét kiÓu d÷ liÖu cña ng­êi lËp tr×nh vµ sù cµi ®Æt cô thÓ kiÓu d÷ liÖu ®ã. VËy kiÓu d÷ liÖu trõu t­îng lµ g×? Cã nhiÒu ®Þnh nghÜa cho kh¸i niÖm nµy nh­ng chóng ®Òu cã nh÷ng nÐt c¬ b¶n thèng nhÊt: Mét kiÓu d÷ liÖu trõu t­îng lµ mét tËp hîp c¸c ®èi t­îng vµ ®­îc x¸c ®Þnh hoµn toµn bëi c¸c phÐp to¸n cã thÓ biÓu diÔn trªn c¸c ®èi t­îng ®ã. Ng­êi sö dông ®­îc phÐp t×m hiÓu c¸c ®èi t­îng vµ thùc hiÖn c¸c thao t¸c trªn c¸c ®èi t­îng cña kiÓu d÷ liÖu th«ng qua c¸c phÐp to¸n ®ã mµ kh«ng cÇn quan t©m ®Õn viÖc ®èi t­îng ®­îc cµi nh­ thÕ nµo trong ng«n ng÷ lËp tr×nh. Cã hai lo¹i kiÓu d÷ liÖu trõu t­îng: lo¹i nguyªn tö (cßn gäi lµ ®¬n) vµ lo¹i cã cÊu tróc (cßn gäi lµ phøc hîp). C¬ së cña viÖc ph©n lo¹i ®ã lµ dùa trªn miÒn c¸c gi¸ trÞ cña kiÓu d÷ liÖu, tøc lµ tËp c¸c gi¸ trÞ mµ c¸c biÕn thuéc kiÓu d÷ liÖu ®ã cã thÓ nhËn. KiÓu d÷ liÖu trõu t­îng ®¬n lµ kiÓu cã miÒn gi¸ trÞ lµ nh÷ng gi¸ trÞ ®¬n (kh«ng t¸ch ra ®­îc n÷a), ch¼ng h¹n nh­ kiÓu sè nguyªn, sè thùc, kÝ tù. KiÓu d÷ liÖu cã cÊu tróc hay kiÓu phøc hîp lµ kiÓu mµ gi¸ trÞ cña nã cã thÓ chia thµnh nh÷ng thµnh phÇn ®¬n gi¶n h¬n hay nhá h¬n, vÝ dô nh­ m¶ng sè nguyªn gåm 5 phÇn tö [3, 7, -3, -7, 8] cã thÓ chia thµnh 5 thµnh phÇn, mçi thµnh phÇn lµ mét sè nguyªn. B¶n ghi còng lµ lo¹i cã cÊu tróc v× mçi b¶n ghi cã thÓ chia thµnh nh÷ng thµnh phÇn nhá h¬n, ®ã lµ nh÷ng tr­êng. Víi mçi kiÓu d÷ liÖu trõu t­îng phøc hîp, khi thiÕt kÕ ta cßn ph¶i chØ ra kiÓu d÷ liÖu cña c¸c thµnh phÇn cña nã, mçi quan hÖ cÊu tróc gi÷a c¸c thµnh phÇn cña nã. Cuèi cïng ta ph¶i chØ ra c¸c phÐp to¸n trªn kiÓu d÷ liÖu. §­¬ng nhiªn ®èi víi kiÓu d÷ liÖu ®¬n ta kh«ng cÇn ph¶i nãi tíi kiÓu d÷ liÖu cña c¸c thµnh phÇn vµ quan hÖ cÊu tróc gi÷a c¸c thµnh phÇn. Nh­ vËy, ta thÊy cã hai tÝnh chÊt lµm cho kiÓu d÷ liÖu trõu t­îng trë nªn quan träng vµ h÷u dông. Thø nhÊt, ta ®· gom côm ®­îc tËp c¸c gi¸ trÞ vµ c¸c thao t¸c trªn c¸c phÇn tö l¹i. ViÖc ®ã cßn cã tªn gäi lµ ®ãng gãi d÷ liÖu. (Trong tiÕng Anh nã ®­îc gäi lµ Data Encapsulation). Thùc ra c¸c kiÓu d÷ liÖu trong c¸c ng«n ng÷ lËp tr×nh còng cã tÝnh chÊt nµy. VÝ dô: kiÓu sè nguyªn bao hµm c¸c sè nguyªn thuéc kho¶ng –Maxint ®Õn +Maxint vµ c¸c thao t¸c (céng: +, trõ: -, nh©n: *, chia: Div, lín h¬n: >, nhë h¬n: <,...). TÝnh chÊt quan träng thø hai cña kiÓu d÷ liÖu trõu t­îng lµ khi x©y dùng chóng ta cã thÓ kh«ng cho phÐp ng­êi sö dông biÕt hay can thiÖp vµo qu¸ tr×nh cµi ®Æt bªn trong. Ng­êi sö dông chØ ®­îc phÐp truy cËp c¸c ®èi t­îng cña kiÓu d÷ liÖu th«ng qua c¸c thao t¸c trªn kiÓu d÷ liÖu mµ th«i. TÝnh chÊt nµy cßn ®­îc gäi lµ tÝnh che giÊu th«ng tin. TÝnh chÊt nµy tr¸nh ®­îc viÖc ng­êi sö dông v« t×nh hay h÷u ý sö dông sai dÉn ®Õn cã thÓ lµm háng ch­¬ng tr×nh. Nh­ vËy, viÖc ®ãng gãi d÷ liÖu vµ che giÊu th«ng tin lµ hai tÝnh chÊt quan träng nhÊt cña kiÓu d÷ liÖu trõu t­îng. Ng­êi sö dông chØ ®­îc phÐp truy cËp ®èi t­îng cña kiÓu d÷ liÖu trõu t­îng th«ng qua c¸c thao t¸c trªn ®èi t­îng. §Ó lµm vÝ dô, ta h·y h×nh dung trong MicrosoftWord, ng­êi sö dông chØ ®­îc phÐp thao t¸c trªn c¸c tÖp tin (file) th«ng qua nh÷ng thao t¸c vÒ tÖp tin ®· ®­îc cung cÊp trªn menu file. S¬ ®å sau minh ho¹ ý t­ëng ®ã. 2. Mét sè vÝ dô vÒ kiÓu d÷ liÖu trõu t­îng 2.1. Líp häc: Mét kiÓu d÷ liÖu trõu t­îng ®¬n Trong phÇn nµy ta sÏ ®­a ra hai vÝ dô. Ta sÏ dïng tiÕng Anh ®Ó ®Æt tªn cho c¸c thao t¸c, kiÓu d÷ liÖu, ®­¬ng nhiªn chóng ®­îc gi¶i thÝch ý nghÜa.TiÕng ViÖt lµ tiÕng cña d©n téc ta, cÇn ph¶i sö dông nã ë mäi n¬i cã thÓ. Tuy nhiªn, do tiÕng ViÖt cã dÊu nªn viÖc sö dông nã trong mét sè tr­êng hîp sÏ g©y khã hiÓu. Do ®ã, b¹n ®äc th«ng c¶m cho viÖc t¸c gi¶ dïng tiÕng Anh ®Ó ®Æt tªn mét sè thao t¸c trong c¸c vÝ dô sau. H¬n n÷a, yªu cÇu cña häc phÇn nµy lµ häc sinh còng ®· biÕt sö dông tiÕng Anh cho chuyªn ngµnh m¸y tÝnh. §Ó lµm vÝ dô ®Çu tiªn, chóng ta t¹o ra mét kiÓu d÷ liÖu trõu t­îng lµ Líp häc. Ch¼ng h¹n, ta quy ­íc mét líp häc cã thÓ cã tè ®a lµ 40 häc sinh. Mét ®èi t­îng cña kiÓu d÷ liÖu trõu t­îng nµy biÓu diÔn mét líp häc. §Ó ®¬n gi¶n ho¸, ta gi¶ ®Þnh mçi líp häc ®­îc hoµn toµn ®Æc tr­ng bëi sè häc sinh cña líp. MiÒn gi¸ trÞ cña kiÓu d÷ liÖu nµy lµ nh÷ng sè nguyªn tõ 0 ®Õn 40. Mçi gi¸ trÞ ®ã lµ mét ®¹i l­îng ®¬n lÎ, kh«ng ph©n t¸ch ®­îc n÷a, nªn ®©y lµ kiÓu d÷ liÖu trõu t­îng nguyªn thuû. (§­¬ng nhiªn ta còng cã thÓ thiÕt kÕ kiÓu líp häc phøc t¹p h¬n vÝ dô ngoµi sè häc sinh ta cßn cã thÓ cã sè häc sinh nam, sè häc sinh n÷,...). Víi kiÓu d÷ liÖu nguyªn thuû nµy ta kh«ng cÇn ph¶i quan t©m ®Õn c¸c thµnh phÇn cña mét ®èi t­îng hay quan hÖ gi÷a c¸c thµnh phÇn cña mét ®èi t­îng. Ta chØ cÇn quan t©m ®Õn nh÷ng thao t¸c cã thÓ trªn kiÓu d÷ liÖu mµ th«i. Thùc ra, b­íc thiÕt kÕ hay x©y dùng c¸c thao t¸c cña mét kiÓu d÷ liÖu trõu t­îng bao giê còng rÊt quan träng, bëi v× ng­êi sö dông chØ truy cËp ®Õn ®èi t­îng th«ng qua c¸c thao t¸c mµ ta cung cÊp. NÕu ta bá sãt mét thao t¸c cÇn thiÕt nµo ®ã th× ng­êi sö dông sÏ kh«ng thÓ hoµn thµnh c«ng viÖc mµ ta mong muèn, còng ®¬n gi¶n nh­ lµ ®Ó lµm mét viÖc ta l¹i bÞ thiÕu c«ng cô hay ph­¬ng tiÖn. ChÝnh v× vËy mµ viÖc thiÕt kÕ cÇn ph¶i ®­îc thùc hiÖn cÈn träng vµ ®¶m b¶o r»ng kiÓu d÷ liÖu ph¶i cã mäi thao t¸c cÇn thiÕt. Th«ng th­êng, cã 5 líp thao t¸c trªn mçi kiÓu d÷ liÖu trõu t­îng. Líp thao t¸c thø nhÊt cã nhiÖm vô t¹o lËp ra nh÷ng ®èi t­îng míi cho kiÓu d÷ liÖu. Ta cã thÓ kÝ hiÖu to¸n tö t¹o lËp nh­ sau: TaoLap: () --> T, hay dïng tiÕng Anh ta cã: Creator: () --> T KÝ hiÖu nµy cã nghÜa lµ mét ®èi t­îng míi cña kiÓu d÷ liÖu T ®­îc t¹o lËp. VÝ dô, víi kiÓu líp häc nãi ë trªn, muèn t¹o lËp ra mét líp häc míi C, ch­a cã häc sinh nµo trong líp, ta cã thÓ viÕt: C := TaoLop() hay C := CreateClass () Trong ®ã to¸n tö CreateClass () lµ kÝ hiÖu to¸n tö t¹o lËp cña kiÓu d÷ liÖu Líp häc mµ ta kÝ hiÖu chung lµ T, gåm c¸c líp häc. Líp thao t¸c thø hai gåm nh÷ng thao t¸c ®Ó biÕn ®æi (transform) c¸c ®èi t­îng cña kiÓu d÷ liÖu. Nh÷ng thao t¸c nµy khi thùc hiÖn trªn c¸c ®èi t­îng sÏ mang l¹i nh÷ng thay ®æi cÇn thiÕt trªn c¸c ®èi t­îng ®ã. Líp nµy th­êng ®­îc kÝ hiÖu lµ: Biendoi: T --> T hay Transformer: T --> T Víi kiÓu líp häc, cã mét sè phÐp biÕn ®æi cÇn thiÕt nh­: thªm häc sinh vµo líp, chuyÓn häc sinh khái líp. Ch¼ng h¹n, C := ThemHocsinh (C,n) hay C :=AddStudent (C,n) PhÐp biÕn ®æi nµy thªm n häc sinh vµo líp häc C. Sè häc sinh cña líp C b©y giê b»ng sè häc sinh cò céng thªm n. NÕu sè ®ã lín h¬n 40 th× ®Æt nã b»ng 40. PhÐp biÕn ®æi C := ChuyenHocsinh (C,n) hay C := RemoveStudent (C,n) thùc hiÖn phÐp chuyÓn n häc sinh khái líp C. Sè häc sinh cña líp C b»ng sè häc sinh cò trõ ®i n. NÕu sè n lín h¬n sè häc sinh ®· cã trong líp C th× ®Æt sè häc sinh míi trong C b»ng 0. Líp thao t¸c thø 3 lµ líp thao t¸c quan s¸t. NhiÖm vô cña líp thao t¸c nµy lµ cho biÕt nh÷ng th«ng tin vÒ tr¹ng th¸i hiÖn t¹i cña ®èi t­îng ®­îc quan s¸t. §èi t­îng ®­îc qua s¸t kh«ng hÒ bÞ thay ®æi. Th«ng th­êng, nh÷ng thao t¸c nµy lµ nh÷ng mÖnh ®Ò hay hµm Boolean. Tuy nhiªn còng cã nh÷ng hµm tr¶ ra nh÷ng gi¸ trÞ cô thÓ, kiÓu sè nguyªn hay kiÓu sè thùc, m« t¶ ®Æc tr­ng cña ®èi t­îng. Líp nµy th­êng ®­îc kÝ hiÖu lµ: QuanSat : T --> Boolean Observer: T --> Boolean, hay T --> Interger T --> Real Víi kiÓu d÷ liÖu líp häc, ta cã thÓ cã 3 hµm sau: Hµm cho biÕt sè häc sinh cña líp: I := Number (C). Hµm cho biÕt líp häc ®· ®ñ häc sinh ch­a: B := IsFull (C) Hµm cho biÕt líp häc ®· cã häc sinh ch­a: B := IsEmpty (C) Líp thao t¸c thø t­ bao gåm nh÷ng thao t¸c biÕn ®æi. Nã cho phÐp chuyÓn nh÷ng ®èi t­îng thuéc c¸c kiÓu kh¸c, ch¼ng h¹n kiÓu sè nguyªn, kiÓu sè thùc thµnh nh÷ng ®èi t­îng thuéc kiÓu d÷ liÖu trõu t­îng T. Ta cã thÓ kÝ hiÖu chóng nh­ sau: i: Integer --> T r: Real --> T a: Array --> T Ch¼ng h¹n, trong kiÓu trõu t­îng líp häc T ë trªn, ta cã thÓ cã to¸n tö i chuyÓn mét sè nguyªn n, 0< n <= 40 thµnh sè häc sinh trong mét líp häc nµo ®ã mµ kh«ng cÇn ®Ó ý ®Õn sè häc sinh hiÖn t¹i cña líp. Ta cã thÓ viÕt nã nh­ sau: C:= SetNumberStudent (C,n)