Chương II - KIỂU DỮ LIỆU, CẤU TRÚC DỮ LIỆU VÀ MÔ HÌNH 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ữ...
Nội dung trích xuất từ tài liệu:
Chương II - KIỂU DỮ LIỆU, CẤU TRÚC DỮ LIỆU VÀ MÔ HÌNH DỮ LIỆU 20 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¸cnhau nh thÕ nµo (sè nguyªn, sè thùc, hay x©u ký tù, ...), ®Òu ®îc biÓudiÔ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¸csè nhÞ ph©n 0 hoÆc 1. VÒ mÆt kü thuËt ®©y lµ c¸ch biÓu diÔnthÝ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ÓudiÔ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Ðpto¸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 ®èiví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áinh÷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étnghÜa nµo ®ã, lµ sù tr×u tîng ho¸ c¸c tÝnh chÊt cña c¸c ®èi tîng trongthÕ 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µito¸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Ómtrong 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 trngvÒ mÆt sè lîng vµ c¸c quan hÖ cña c¸c ®èi tîng trong thÕ giíi hiÖnthù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«nng÷ lËp tr×nh bËc cao c¸c d÷ liÖu kiÓu nguyªn, thùc, phøc, m¶ng, b¶nghi, ... 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Ëccao lµ cha ®ñ ®Ó m« t¶ c¸c bµi to¸n. Chóng ta ph¶i cÇn ®Õn c¸c cÊutró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×nhd÷ 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. 20 21Th«ng thêng mét m« h×nh d÷ liÖu cã thÓ ®îc biÓu hiÖn bëi nhiÒu cÊutróc d÷ liÖu kh¸c nhau. Tuú tõng øng dông, ta sÏ chän cÊu tróc d÷ liÖunµo mµ c¸c thao t¸c cÇn thùc hiÖn lµ hiÖu qu¶ nhÊt cã thÓ ®îc. 2.2. KiÓu d÷ liÖu vµ cÊu tróc d÷ liÖu. Trong c¸c ng«n ng÷ lËp tr×nh bËc cao, c¸c d÷ liÖu ®îc ph©n lípthµnh c¸c líp d÷ liÖu dùa vµo b¶n chÊt cña d÷ liÖu. Mçi mét líp d÷ liÖu®îc gäi lµ mét kiÓu d÷ liÖu. Nh vËy, mét kiÓu T lµ mét tËp hîp nµo ®ã,c¸c phÇn tö cña tËp ®îc gäi lµ c¸c gi¸ trÞ cña kiÓu. Ch¼ng h¹n, kiÓuinteger lµ tËp hîp c¸c sè nguyªn, kiÓu char lµ mét tËp h÷u h¹n c¸c kýhiÖu. C¸c ng«n ng÷ lËp tr×nh kh¸c nhau cã thÓ cã c¸c kiÓu d÷ liÖu kh¸cnhau. Fortran cã c¸c kiÓu d÷ liÖu lµ integer, real, logical, complex vµdouble complex. C¸c kiÓu d÷ liÖu trong ng«n ng÷ C lµ int, float, char,con trá, struct..., KiÓu d÷ liÖu trong ng«n ng÷ Lisp l¹i lµ c¸c S-biÓuthøc. Mét c¸ch tæng qu¸t, mçi ng«n ng÷ lËp tr×nh cã mét hÖ kiÓu cñariªng m×nh. HÖ kiÓu cña mét ng«n ng÷ bao gåm c¸c kiÓu d÷ liÖu c¬ sëvµ c¸c ph¬ng ph¸p cho phÐp ta tõ c¸c kiÓu d÷ liÖu ®· cã x©y dùng nªnc¸c kiÓu d÷ liÖu míi. Khi nãi ®Õn mét kiÓu d÷ liÖu, chóng ta cÇn ph¶i ®Ò cËp ®Õnhai ®Æc trng sau ®©y : 1. TËp hîp c¸c gi¸ trÞ thuéc kiÓu. Ch¼ng h¹n, kiÓu integer trongng«n ng÷ Pascal gåm tÊt c¶ c¸c sè nguyªn ®îc biÓu diÔn bëi hai byte,tøc lµ gåm c¸c sè nguyªn tõ -32768 ®Õn + 32767. Trong c¸c ng«n ng÷lËp tr×nh bËc cao mçi h»ng, biÕn, biÓu thøc hoÆc hµm cÇn ph¶i ®îcg¾n víi mét kiÓu d÷ liÖu x¸c ®Þnh. Khi ®ã, mçi biÕn (biÓu thøc, hµm)chØ cã thÓ nhËn c¸c gi¸ trÞ thuéc kiÓu cña biÕn (biÓu thøc, hµm) ®ã. VÝ dô , nÕu X lµ biÕn cã kiÓu boolean trong Pascal (var X :boolean) th× X chØ cã thÓ nhËn mét trong hai gi¸ trÞ true, false. 2. Víi mçi kiÓu d÷ liÖu, cÇn ph¶i x¸c ®Þnh mét tËp hîp nµo ®ãc¸c phÐp to¸n cã thÓ thùc hiÖn ®îc trªn c¸c d÷ liÖu cña kiÓu. Ch¼ngh¹n, víi kiÓu real, c¸c phÐp to¸n cã thÓ thùc hiÖn ®îc lµ c¸c phÐp to¸nsè häc th«ng thêng +, -, *, / , vµ c¸c phÐp to¸n so s¸nh = , < >, < , ...