Kiểu dữ liệu, cấu trúc và mô hình dữ liệu

Ch ¬ng II

kiÓu d÷ liÖu, cÊu tróc d÷ liÖu vµ

m« h×nh d÷ liÖu

2.1. BiÓu diÔn d÷ liÖu.

Trong m¸y tÝnh ®iÖn tö (MT§T), c¸c d÷ liÖu dï cã b¶n chÊt kh¸c nhau

nh thÕ nµo (sè nguyªn, sè thùc, hay x©u ký tù, ...), ®Òu ®îc biÓu diÔn díi d¹ng

nhÞ ph©n. Mçi d÷ liÖu ®îc biÓu diÔn díi d¹ng mét d·y c¸c sè nhÞ ph©n 0 hoÆc

1. VÒ mÆt kü thuËt ®©y lµ c¸ch biÓu diÔn thÝch hîp nhÊt, v× c¸c gi¸ trÞ 0 vµ 1

dÔ dµng ®îc m· ho¸ bëi c¸c phÇn tö vËt lý chØ cã hai tr¹ng th¸i. Chóng ta sÏ

kh«ng quan t©m ®Õn c¸ch biÓu diÔn nµy cña d÷ liÖu, còng nh c¸c c¸ch tiÕn

hµnh c¸c thao t¸c, c¸c phÐp to¸n trªn c¸c d÷ liÖu ®îc biÓu diÔn díi d¹ng nhÞ

ph©n.

C¸ch biÓu diÔn nhÞ ph©n cña d÷ liÖu rÊt kh«ng thuËn tiÖn ®èi víi con

ngêi. ViÖc xuÊt hiÖn c¸c ng«n ng÷ lËp tr×nh bËc cao (FORTRAN, BASIC,

PASSCAL, C ...) ®· gi¶i phãng con ngêi khái nh÷ng khã kh¨n khi lµm viÖc

víi c¸ch biÓu diÔn trong m¸y cña d÷ liÖu. Trong c¸c ng«n ng÷ lËp tr×nh bËc

cao, c¸c d÷ liÖu, hiÓu theo mét nghÜa nµo ®ã, lµ sù tr×u tîng ho¸ c¸c tÝnh chÊt

cña c¸c ®èi tîng trong thÕ giíi hiÖn thùc. Nãi d÷ liÖu lµ sù tr×u tîng ho¸ tõ thÕ

giíi hiÖn thùc, v× ta ®· bá qua nh÷ng nh©n tè, tÝnh chÊt mµ ta cho lµ kh«ng c¬

b¶n, chØ gi÷ l¹i nh÷ng tÝnh chÊt ®Æc trng cho c¸c ®èi tîng thuéc ph¹m vi bµi

to¸n ®ang xÐt. Ch¼ng h¹n, vÞ trÝ cña mét ®èi tîng trong thùc tiÔn, ®îc ®Æc trng

bëi cÆp sè thùc (x,y) (®ã lµ to¹ ®o¹ ®ª-c¸c cña mét ®iÓm trong mÆt ph¼ng).

Do ®ã, trong ng«n ng÷ Pascal, vÞ trÝ mét ®èi tîng ®îc biÓu diÔn bëi b¶n ghi

gåm hai trêng t¬ng øng víi hoµnh ®é vµ tung ®é cña mét ®iÓm. Trong to¸n

häc cã c¸c kh¸i niÖm biÓu diÔn ®Æc trng vÒ mÆt sè lîng vµ c¸c quan hÖ cña

c¸c ®èi tîng trong thÕ giíi hiÖn thùc, ®ã lµ c¸c kh¸i niÖm sè nguyªn, sè thùc,

sè phøc, d·y, ma trËn, ... Trªn c¬ së c¸c kh¸i niÖm to¸n häc nµy, ngêi ta ®· ®a

vµo trong c¸c ng«n ng÷ lËp tr×nh bËc cao c¸c d÷ liÖu kiÓu nguyªn, thùc, phøc,

m¶ng, b¶n ghi, ... Tuy nhiªn do tÝnh ®a d¹ng cña c¸c bµi to¸n cÇn xö lý b»ng

MT§T, chØ sö dông c¸c kiÓu d÷ liÖu cã s½n trong c¸c ng«n ng÷ lËp tr×nh bËc

cao lµ cha ®ñ ®Ó m« t¶ c¸c bµi to¸n. Chóng ta ph¶i cÇn ®Õn c¸c cÊu tróc d÷

liÖu. §ã lµ c¸c d÷ liÖu phøc t¹p, ®îc x©y dùng nªn tõ c¸c d÷ liÖu ®· cã, ®¬n

gi¶n h¬n b»ng c¸c ph¬ng ph¸p liªn kÕt nµo ®ã.

§Ó gi¶i quyÕt mét bµi to¸n b»ng MT§T, ta cÇn x©y dùng m« h×nh d÷

liÖu m« t¶ bµi to¸n. §ã lµ sù tr×u tîng ho¸ c¸c ®Æc trng cña c¸c ®èi tîng thuéc

ph¹m vi vÊn ®Ò mµ ta quan t©m, c¸c mèi quan hÖ gi÷a c¸c ®èi tîng ®ã. Dïng

lµm c¸c m« h×nh d÷ liÖu trong tin häc, chóng ta sÏ sö dông c¸c m« h×nh to¸n

häc nh danh s¸ch, c©y, tËp hîp, ¸nh x¹, quan hÖ, ®å thÞ, ... M« h×nh d÷ liÖu sÏ

®îc biÓu diÔn bëi c¸c cÊu tróc d÷ liÖu. Th«ng thêng mét m« h×nh d÷ liÖu cã

thÓ ®îc biÓu hiÖn bëi nhiÒu cÊu tróc d÷ liÖu kh¸c nhau. Tuú tõng øng dông, ta

20

20

a

1

a

2

a

n

.