Luận văn tốt nghiệp: Cấu trúc dữ liệu mẫu với C++

CÊu tróc d÷ liÖu mÉu víi C++

Lêi c¶m ¬n

Tríc tiªn, t«i xin bµy tá lßng biÕt ¬n s©u s¾c tíi thÇy gi¸o

híng dÉn TS §oµn V¨n Ban, phßng CSDL< ViÖn C«ng NghÖ

Th«ng Tin thuéc trung t©m Khoa Häc Tù Nhiªn vµ C«ng NghÖ

Quèc Gia ®· tËn t×nh gióp ®ì t«i hoµn thµnh bµi luËn v¨n nµy.

T«i xin ch©n thµnh c¶m ¬n c¸c thÇy, c« gi¸o khoa C«ng NghÖ

Th«ng Tin trêng §HDL §«ng §« ®· gi¶ng d¹y vµ gióp ®ì em

trong qu¸ tr×nh häc tËp ë trêng.

Cuèi cïng, xin ch©n thµnh c¶m ¬n nh÷ng ngêi th©n trong

gia ®×nh vµ b¹n bÌ ®· gióp ®ì, ®éng viªn trong qu¸ tr×nh häc tËp.

Hµ néi th¸ng 6 n¨m 2000

more information and additional documents connect with me here: http://facebook.com/ngphutien/ file đồ án kèm theo: Cau truc du lieu voi C++.rar 259 KB https://mega.co.nz/#!FgU3nAKa!-VgkoAGeGZtP3Q2LwN2LKMQXE4Uj67Q4nbAJrT4aGB8

CÊu tróc d÷ liÖu mÉu víi C++

Môc lôc

Lêi c¶m ¬n PhÇn A Ch¬ng I. Ng«n ng÷ C++ vµ lËp tr×nh híng ®èi tîng

I.1. LËp tr×nh híng ®èi tîng lµ g×?.............................................................4

I.2. C¸c u ®iÓm cña lËp tr×nh híng ®èi tîng............................................5

I.3. §èi tîng ...............................................................................................6

I.4. C¸c líp ®èi tîng....................................................................................7

I.5. Trõu tîng ho¸ d÷ liÖu vµ bao gãi th«ng tin...........................................8

I.6. Thõa kÕ....................................................................................................8

I.7. T¬ng øng béi.........................................................................................9

I.8. TruyÒn th«ng b¸o..................................................................................10

I.9. Nh÷ng øng dông cña lËp tr×nh híng ®èi tîng....................................11 Ch¬ng II. ThiÕt kÕ vµ cµi ®Æt c¸c líp ®èi tîng

II.1. §Þnh nghÜa líp.....................................................................................13

II.1.1. Khai b¸o líp tªn ®èi tîng................................................................13

II.1.2. T¹o lËp c¸c líp ®èi tîng..................................................................14

II.1.3. C¸c thµnh phÇn d÷ liÖu......................................................................15

II.2. TÝnh t¬ng øng béi...............................................................................16

II.2.1. Hµm t¶i béi.......................................................................................17

II.2.2. ChuyÓn ®æi kiÓu................................................................................21

II.3. KÕ thõa vµ sù më réng c¸c líp............................................................22

II.3.1. KÕ thõa ®¬n.......................................................................................23

II.3.2. KÕ thõa ®a møc.................................................................................27

II.3.3. KÕ thõa ph©n cÊp...............................................................................28

II.3.4. KÕ thõa béi........................................................................................28

II.3.5. KÕ thõa kÐp.......................................................................................29

II.3.6. C¸c líp c¬ së ¶o................................................................................29 more information and additional documents connect with me here: http://facebook.com/ngphutien/ file đồ án kèm theo: Cau truc du lieu voi C++.rar 259 KB https://mega.co.nz/#!FgU3nAKa!-VgkoAGeGZtP3Q2LwN2LKMQXE4Uj67Q4nbAJrT4aGB8

CÊu tróc d÷ liÖu mÉu víi C++

II.3.7. CÊu tö trong c¸c líp dÉn xuÊt...........................................................30

Ch¬ng III. Hµm vµ líp mÉu

II.3.8. Hµm ¶o.............................................................................................32

III.1. Hµm mÉu............................................................................................34

III.1.1. §Þnh nghÜa.......................................................................................34

III.1.2. Hµm mÉu cã nhiÒu tham sè h×nh thøc.............................................35

III.1.3. Hµm mÉu cã nhiÒu tham sè kh¸c nhau...........................................36

III.2. Líp mÉu.............................................................................................38

III.2.1 §Þnh nghÜa.......................................................................................38

III.2.2. Líp mÉu cã tham sè ......................................................................39

Ch¬ng IV CÊu tróc d÷ liÖu vµ c¸c líp mÉu

III.3. KÕt luËn ............................................................................................39

IV. CÊu tróc d÷ liÖu....................................................................................40

IV.1.1. Líp chøa.........................................................................................41

IV.1.2. Líp chøa thÇn ¶o............................................................................41

IV.2.1. Ng¨n xÕp........................................................................................42

IV.2.2. Lu tr÷ ng¨n xÕp b»ng m¶ng.........................................................42

IV.2.3. X©y dùng líp ng¨n xÕp mÉu............................................................43

IV.3.1. Hµm ®îi...........................................................................................44

IV.3.2. X©y dùng líp hµm ®îi mÉu.............................................................45

IV.4. Hµng quay trßn...................................................................................47

IV.5. Danh s¸ch liªn kÕt..............................................................................48

IV.6 Danh s¸ch liªn kÕt ®¬n........................................................................48

IV.7 Danh s¸ch liªn kÕt ®«i.........................................................................56

IV.8. C©y nhÞ ph©n.......................................................................................64

IV.9. NhËn xÐt.............................................................................................74

CÊu tróc d÷ liÖu mÉu víi C++

PhÇn B

I. Ch¬ng tr×nh qu¶n lý sinh viªn................................................................76

II. Ch¬ng tr×nh thèng kª tõ tiÕng ViÖt.......................................................85

KÕt luËn.......................................................................................................92

Tµi liÖu tham kh¶o.......................................................................................93

CÊu tróc d÷ liÖu mÉu víi C++

Ch¬ng I

Ng«n ng÷ C++ vµ lËp tr×nh híng ®èi tîng

I.1. LËp tr×nh híng ®èi tîng lµ g×?

LËp tr×nh híng ®èi tîng dùa trªn nÒn t¶ng lµ c¸c ®èi tîng. §èi tîng ®îc x©y dùng trªn c¬ së g¾n cÊu tróc d÷ liÖu víi c¸c phÐp to¸n sÏ thÓ ®îc ®óng c¸ch mµ chóng ta suy nghÜ, bao qu¸t vÒ thÕ giíi thùc. [3]

LËp tr×nh híng ®èi tîng cho phÐp chóng ta kÕt hîp nh÷ng tri thøc bao qu¸t vÒ c¸c qu¸ tr×nh víi nh÷ng kh¸i niÖm trõu tîng ®îc sö dông trong m¸y tÝnh .

LËp tr×nh híng ®èi tîng lµ ph¬ng ph¸p lËp tr×nh lÊy ®èi tîng lµm nÒn t¶ng ®Ó x©y dùng thuËt gi¶i, x©y dùng ch¬ng tr×nh, lµ c¸ch tiÕp cËn ®Ó ph©n chia ch¬ng tr×nh thµnh c¸c ®¬n thÓ (modul) b»ng c¸ch t¹o ra c¸c vïng bé nhí cho c¶ d÷ liÖu lÉn hµm vµ chóng sÏ ®îc sö dông nh c¸c mÉu ®Ó t¹o ra b¶n sao tõng ®¬n thÓ khi cÇn thiÕt. §èi tîng ë ®©y ®îc xem nh lµ vïng ph©n chia chia bé nhí trong m¸y tÝnh ®Ó lu tr÷ d÷ liÖu vµ tËp c¸c hµm t¸c ®éng trªn d÷ liÖu g¾n víi chóng.

Kh¸i niÖm “Híng ®èi tîng” ®îc x©y dùng trªn nÒn t¶ng cña kh¸i niÖm “LËp tr×nh cã cÊu tróc“ vµ ”Sù trõu tîng ho¸ d÷ liÖu” sù thay ®æi c¨n b¶n lµ ë chç mét ch¬ng tr×nh híng ®èi tîng ®îc thiÕt kÕ xoay quanh c¸c d÷ liÖu mµ ta lµm viÖc trªn nã, h¬n lµ theo b¶n th©n chøc n¨ng cña ch¬ng tr×nh.

LËp tr×nh híng ®èi tîng ®Æt träng t©m vµo ®èi tîng, yÕu tè quan träng trong qu¸ tr×nh ph¸t triÓn ch¬ng tr×nh vµ nã kh«ng cho phÐp d÷ liÖu chuyÓn ®éng tù do trong hÖ thèng. D÷ liÖu ®îc g¾n chÆt víi tõng hµm thµnh c¸c vïng riªng mµ c¸c hµm ®ã t¸c ®éng lªn vµ nã ®îc b¶o vÖ cÊm c¸c hµm ngo¹i lai truy nhËp tuú tiÖn. Tuy nhiªn c¸c ®èi tîng cã thÓ trao ®æi th«ng tin víi nhau th«ng qua viÖc trao ®æi th«ng b¸o.[5]

CÊu tróc d÷ liÖu mÉu víi C++

Tãm l¹i, so s¸nh lËp tr×nh cÊu tróc lÊy ch¬ng tr×nh con lµm nÒn

t¶ng:

Ch¬ng tr×nh = CÊu tróc d÷ liÖu + Gi¶i ThuËt

Trong lËp tr×nh híng ®èi tîng chóng ta cã :

§èi tîng =D÷ LiÖu + Hµnh vi cña d÷ liÖu

LËp tr×nh híng ®èi tîng cã nh÷ng ®Æc tÝnh chñ yÕu sau:

 TËp trung vµo d÷ liÖu thay cho c¸c hµm.

 Ch¬ng tr×nh ®îc chia thµnh tËp c¸c líp ®èi tîng.

 CÊu tróc d÷ liÖu ®îc thiÕt kÕ sao cho ®Æc t¶ c¸c ®èi tîng.

 C¸c hµm ®îc x¸c ®Þnh trªn c¸c vïng d÷ kiÖu cña ®èi tîng ®îc

g¾n víi nhau trªn cÊu tróc cña d÷ liÖu ®ã.

 D÷ liÖu ®îc bao bäc, che dÊu vµ kh«ng cho phÐp c¸c hµm ngo¹i

lai truy nhËp tù do.

 C¸c ®èi tîng trao ®æi th«ng tin víi nhau qua c¸c hµm.

 D÷ liÖu vµ c¸c hµm míi cã thÓ dÔ dµng bæ xung vµo ®èi tîng nµo

®ã khi cÇn thiÕt.

 Ch¬ng tr×nh ®îc thiÕt kÕ theo c¸ch tiÕp cËn bottom-up.

I.2. C¸c u ®iÓm cña lËp tr×nh híng ®èi tîng

 Th«ng qua nguyªn lý thõa kÕ, chóng ta cã thÓ lo¹i bá ®îc nh÷ng ®o¹n ch¬ng tr×nh lÆp l¹i, d thõa trong qu¸ tr×nh m« t¶ c¸c líp vµ kh¶ n¨ng sö dông c¸c líp ®· ®îc x©y dùng.

 Ch¬ng tr×nh ®îc x©y dùng tõ c¸c ®¬n thÓ (module) trao ®æi víi nhau nªn viÖc thiÕt kÕ vµ lËp tr×nh sÏ ®îc thùc hiÖn theo quy tr×nh

CÊu tróc d÷ liÖu mÉu víi C++

nhÊt ®Þnh chø kh«ng ph¶i dùa vµo kinh nghiÖm vµ kü thuËt nh tríc. §iÒu nµy ®¶m b¶o rót ng¾n ®îc thêi gian x©y dùng hÖ thèng vµ t¨ng n¨ng xuÊt lao ®éng.

 Nguyªn lý che dÊu th«ng tin gióp ngêi lËp tr×nh t¹o ra ®îc nh÷ng ch¬ng tr×nh an toµn kh«ng bÞ thay ®æi bëi nh÷ng ch¬ng tr×nh kh¸c.

 Cã thÓ x©y dùng ®îc c¸c ¸nh x¹ ®èi tîng cña bµi to¸n vµo ®èi

tîng cña ch¬ng tr×nh.

 C¸ch tiÕp cËn thiÕt kÕ ®Æt träng t©m vµo d÷ liÖu gióp ta x©y dùng

®îc m« h×nh chi tiÕt vµ gÇn víi d¹ng cµi ®Æt h¬n.

 Nh÷ng hÖ thèng híng ®èi tîng dÔ më réng, n©ng cÊp thµnh nh÷ng

hÖ thèng lín h¬n.

 Kü thuËt truyÒn th«ng b¸o trong viÖc tao trao ®æi th«ng tin gi÷a c¸c ®èi tîng gióp cho viÖc m« t¶ giao diÖn víi c¸c hÖ thèng bªn ngoµi ®¬n gi¶n h¬n.

 Cã thÓ qu¶n lý ®é phøc t¹p cña nh÷ng s¶n phÈm phÇn mÒm.

I.3. §èi tîng

§èi tîng lµ thùc thÓ ®îc x¸c ®Þnh trong thêi h¹n hÖ thèng híng ®èi tîng ho¹t ®éng. Nh vËy ®èi tîng lµ con ngêi, sù vËt, thiÕt bÞ, b¶ng d÷ liÖu cÇn xö lý trong ch¬ng tr×nh. Mçi ®èi tîng gåm cã: tËp c¸c thuéc tÝnh (attribute) vµ tËp c¸c hµm (function) ®Ó xö lý c¸c thuéc tÝnh ®ã.[5]

Mét ®èi tîng cã thÓ ®îc minh ho¹ nh sau :

§èi Tîng

Thuéc TÝnhHµm

H×nh 1. CÊu tróc tæng qu¸t cña mét ®èi tîng.

CÊu tróc d÷ liÖu mÉu víi C++

Ch¼ng h¹n chóng ta xÐt ®èi tîng h×nh ch÷ nhËt bao gåm c¸c thuéc tÝnh (x1,y1) to¹ ®é gãc trªn bªn tr¸i, d, r lµ chiÒu dµi chiÒu réng cña h×nh ch÷ nhËt. C¸c hµm: nhËp sè liÖu cho h×nh ch÷ nhËt, hµm tÝnh diÖn tÝch, chu vi vµ hµm hiÓn thÞ. Nh vËy ®èi tîng h×nh ch÷ nhËt cã thÓ ®îc m« t¶ nh sau:

§èi tîng: h×nh ch÷ nhËt

Thuéc tÝnh: x1, y1, d, r

Ph¬ng thøc: NhËp sè liÖu DiÖn tÝch Chu vi HiÓn thÞ

H×nh 2. M« t¶ ®èi tîng h×nh ch÷ nhËt.

I.4. C¸c líp ®èi tîng

Mét tËp d÷ liÖu vµ c¸c hµm cña mét tËp ®èi tîng cã thÓ ®îc xem nh mét kiÓu d÷ liÖu ®îc ®Þnh nghÜa bëi ngêi sö dông. KiÓu d÷ liÖu ë ®©y ®îc gäi lµ líp (class), ®ã lµ mét tËp c¸c thuéc tÝnh vµ c¸c hµm m« t¶ thÕ giíi thùc, mét ®èi tîng lµ thÓ hiÖn cña mét líp. Líp lµ kh¸i niÖm trung t©m cña lËp tr×nh híng ®èi tîng, nã lµ sù më réng cÊu tróc (struct) cña C vµ b¶n ghi (record) cña Pascal. Trong lËp tr×nh híng ®èi tîng, líp hÇu nh ®ång nhÊt víi kiÓu d÷ liÖu trõu tîng. Líp lµ kh¸i niÖm tÜnh, cã thÓ nhËn biÕt ngay tõ v¨n b¶n ch¬ng tr×nh. Ngîc l¹i ®èi tîng lµ kh¸i niÖm ®éng, nã ®îc x¸c ®Þnh trong bé nhí cña m¸y tÝnh n¬i ®èi tîng chiÕm mét vïng cña bé nhí lóc thùc hiÖn ch¬ng tr×nh. §èi tîng ®îc t¹o ra ®Ó xö lý th«ng tin, thùc hiÖn nhiÖm vô ®îc thiÕt kÕ vµ sau ®ã bÞ huû bá khi ®èi tîng ®ã hÕt vai trß. Khi mét líp ®îc ®Þnh nghÜa, th× nã cã thÓ t¹o ra sè more information and additional documents connect with me here: http://facebook.com/ngphutien/ file đồ án kèm theo: Cau truc du lieu voi C++.rar 259 KB https://mega.co.nz/#!FgU3nAKa!-VgkoAGeGZtP3Q2LwN2LKMQXE4Uj67Q4nbAJrT4aGB8

CÊu tróc d÷ liÖu mÉu víi C++

lîng c¸c ®èi tîng tuú ý cña líp ®ã. Nh vËy líp lµ tËp hîp c¸c ®èi tîng cïng kiÓu. Sù kh¸c biÖt gi÷a líp vµ ®èi tîng còng gièng nh sù kh¸c biÖt gi÷a tËp hîp c¸c phÇn tö vµ mét phÇn tö trong tËp hîp.[5]

I.5. Trõu tîng ho¸ d÷ liÖu vµ bao gãi th«ng tin

ViÖc ®ãng gãi d÷ liÖu vµ c¸c hµm vµo mét ®¬n vÞ cÊu tróc ®îc xem nh mét nguyªn t¾c (che dÊu) th«ng tin, d÷ ®îc tæ chøc sao cho thÕ giíi bªn ngoµi kh«ng truy nhËp ®îc vµo mµ chØ cho phÐp c¸c hµm trong cïng líp hoÆc trong nh÷ng líp cã quan hÖ thõa víi nhau ®îc quÒn truy nhËp. ChÝnh c¸c hµm thµnh phÇn cña líp sÏ ®ãng vai trß nh lµ giao diÖn gi÷a d÷ liÖu cña ®èi tîng vµ phÇn cßn l¹i cña ch¬ng tr×nh. Nguyªn t¾c bao gãi d÷ liÖu ®Ó ng¨n cÊm sù truy nhËp trùc tiÕp trong lËp tr×nh ®îc gäi lµ che dÊu th«ng tin.

Trõu tîng ho¸ lµ c¸ch biÓu diÔn nh÷ng ®Æc tÝnh chÝnh vµ bá qua nh÷ng chi tiÕt vôn vÆt hoÆc nh÷ng gi¶i thÝch. §Ó x©y dùng c¸c líp chóng ta ph¶i sö dông kh¸i niÖm trõu tîng ho¸. Trong lËp tr×nh híng ®èi tîng líp ®îc sö dông nh d÷ liÖu trõu tîng. VÝ dô nh chóng ta cã thÓ ®Þnh nghÜa mét líp lµ danh s¸ch c¸c thuéc tÝnh trõu tîng nh lµ kÝch thíc, h×nh d¸ng mÇu vµ c¸c hµm x¸c ®Þnh trªn c¸c thuéc tÝnh nµy ®Ó m« t¶ c¸c ®èi tîng trong kh«ng gian h×nh häc.

I.6. Thõa KÕ

Thõa kÕ lµ qu¸ tr×nh trong ®ã c¸c ®èi tîng cña líp nµy ®îc quyÒn

sö dông mét sè tÝnh chÊt cña c¸c ®èi tîng cña c¸c líp kh¸c.

Nguyªn lý thõa kÕ hç trî cho viÖc t¹o ra cÊu tróc ph©n cÊp c¸c líp. Nã ®îc thùc hiÖn dùa trªn nguyªn lý tæng qu¸t ho¸ hoÆc chi tiÕt ho¸ c¸c ®Æc tÝnh cña c¸c ®èi tîng trong c¸c líp.

CÊu tróc d÷ liÖu mÉu víi C++

Trong lËp tr×nh híng ®èi tîng, kh¸i niÖm thõa kÕ kÐo theo ý tëng sö dông l¹i. NghÜa lµ mét líp ®· ®îc x©y dùng (líp cha hay líp c¬ së) cña chóng cã thÓ bæ sung thªm c¸c tÝnh chÊt míi ®Ó t¹o c¸c líp míi (líp con hay líp dÉn xuÊt) m« t¶ chi tiÕt h¬n vÒ mét nhãm ®èi tîng cô thÓ (theo nguyªn lý chi tiÕt ho¸) hoÆc tõ mét nhãm líp cã sè ®Æc tÝnh gièng nhau gép chung c¸c ®Æc tÝnh ®ã l¹i ®Ó t¹o ra mét líp míi, ®îc gäi lµ líp trõu tîng (nguyªn lý tæng qu¸t ho¸).

Kh¸i niÖm kÕ thõa ®îc hiÓu nh c¬ chÕ sao chÐp ¶o kh«ng ®¬n ®iÖu. Trong thùc tÕ, mäi viÖc x¶y ra tùa nh nh÷ng líp c¬ së ®Òu ®îc sao vµo trong líp dÉn xuÊt mÆc dï ®iÒu nµy kh«ng ®îc cµi ®Æt têng minh (gäi lµ sao chÐp ¶o) vµ viÖc sao chÐp chØ ®îc x¸c ®Þnh trong líp c¬ së (sao chÐp kh«ng ®¬n ®iÖu).

Mét líp cã thÓ kÕ thõa c¸c tÝnh chÊt cña mét hay nhiÒu líp c¬ së ë c¸c møc kh¸c nhau, do ®ã cã n¨m d¹ng kÕ thõa ®îc sö dông trong lËp tr×nh híng ®èi tîng lµ: kÕ thõa ®¬n, kÕ thõa béi, kÕ thõa ph©n cÊp, kÕ thõa ®a møc vµ kÕ thõa phøc hîp (ch¬ng sau sÏ nãi râ vÒ c¸c d¹ng kÕ thõa nµy).[3]

I.7. T¬ng øng béi

T¬ng øng béi lµ mét kh¸i niÖm cã kh¶ n¨ng nh c¸c phÐp to¸n cã thÓ ®îc thùc hiÖn ë nhiÒu d¹ng kh¸c nhau. Hµnh vi cña c¸c phÐp to¸n t¬ng øng béi phô thuéc vµo kiÓu d÷ liÖu mµ nã sö dông ®Ó xö lý. T¬ng øng béi ®ãng vai trß quan träng trong viÖc t¹o ra c¸c ®èi tîng cã cÊu tróc bªn trong kh¸c nhau nhng cã kh¶ n¨ng dïng chung mét giao diÖn bªn ngoµi (nh tªn gäi). §iÒu nµy cã nghÜa lµ mét líp c¸c phÐp to¸n ®îc ®Þnh nghÜa theo nh÷ng thuËt to¸n kh¸c nhau, nhng cã kh¶ n¨ng sö dông theo cïng mét c¸ch gièng nhau.T¬ng øng béi lµ sù më réng kh¸i niÖm sö dông l¹i trong nguyªn lý kÕ thõa. Liªn kÕt ®éng lµ d¹ng liªn kÕt c¸c hµm, thñ tôc khi ch¬ng tr×nh thùc hiÖn c¸c lêi gäi tíi c¸c hµm, thñ tôc ®ã. Nh vËy, trong liªn kÕt ®éng néi dung cña ®o¹n ch¬ng tr×nh øng víi thñ tôc, hµm cho ®Õn khi thùc hiÖn c¸c lêi gäi tíi c¸c thñ tôc vµ hµm ®ã. Nã cho phÐp chóng ta can thiÖp vµo sù ho¹t ®éng cña c¸c thùc thÓ mµ kh«ng cÇn biªn dÞch l¹i toµn bé ch¬ng tr×nh, chóng ta cã thÓ truyÒn vµ nhËn th«ng tin tõ c¸c ®èi tîng míi nµy gièng nh c¸c ®èi tîng ®· cã. Liªn kÕt ®éng liªn

CÊu tróc d÷ liÖu mÉu víi C++

quan chÆt chÏ tíi t¬ng øng béi vµ kÕ thõa, ®«i khi liªn kÕt ®éng cßn gäi lµ liªn kÕt trÔ hay liªn kÕt vµo lóc ch¹y (v× c¸c ph¬ng thøc chØ ®îc gäi vµo lóc ch¬ng tr×nh biªn dÞch ch¬ng tr×nh biªn dÞch ra ng«n ng÷ m¸y).[3]

Ch¼ng h¹n nh hµm VE() trong h×nh 3, theo nguyªn lý kÕ thõa th× mäi ®èi tîng ®Òu cã thÓ sö dông hµm nµy ®Ó vÏ theo yªu cÇu. Tuy nhiªn, thuËt to¸n thùc hiÖn hµm VE() lµ duy nhÊt ®èi víi tõng ®èi tîng H×nh_TRßn, §a_Gi¸c, §¬ng_th vµ v× vËy hµm VE() sÏ ®îc ®Þnh nghÜa l¹i khi c¸c ®èi tîng t¬ng øng ®îc x¸c ®Þnh.

H×nh Häc

VE()

§A_GIAC §¦¥NG_TH

HINH_TRON N VE(TRON) VE(§A_GIAC) VE(§¦¥NG_TH)

H×nh 3. T¬ng øng béi cña hµm VE().

I.8. TruyÒn th«ng b¸o

C¸c ®èi tîng göi vµ nhËn th«ng tin víi nhau gièng nh con ngêi trao ®æi th«ng tin víi nhau. ChÝnh nguyªn lý trao ®æi th«ng tin víi nhau b»ng c¸ch truyÒn th«ng b¸o cho phÐp chóng ta dÔ dµng x©y dùng ®îc hÖ thèng m« pháng gÇn nh÷ng hÖ thèng trong thÕ giíi thùc. TruyÒn th«ng b¸o cho mét ®èi tîng tøc lµ b¸o cho nã ph¶i thùc hiÖn mét viÖc g× ®ã. C¸ch øng xö c¶ ®èi tîng sÏ ®îc m« t¶ ë trong líp th«ng qua c¸c hµm (hay cßn ®îc gäi lµ líp dÞch vô). Th«ng b¸o truyÒn ®i ph¶i chØ ra ®îc hµm cÇn thùc more information and additional documents connect with me here: http://facebook.com/ngphutien/ file đồ án kèm theo: Cau truc du lieu voi C++.rar 259 KB https://mega.co.nz/#!FgU3nAKa!-VgkoAGeGZtP3Q2LwN2LKMQXE4Uj67Q4nbAJrT4aGB8

CÊu tróc d÷ liÖu mÉu víi C++

hiÖn trong ®èi tîng nhËn th«ng b¸o. H¬n thÕ n÷a th«ng b¸o truyÒn ®i ph¶i x¸c ®Þnh tªn ®èi tîng, tªn hµm vµ th«ng tin truyÒn ®i.

VÝ dô: Líp CONG_NHAN cã thÓ lµ ®èi tîng cô thÓ ®îc x¸c ®Þnh bëi HO_TEN nhËn ®îc th«ng b¸o cÇn TINH_LUONG ®· ®îc x¸c ®Þnh trong líp CONG_NHAN. Th«ng b¸o ®ã sÏ ®îc xö lý nh sau:

CONG_NHAN.TINH_LUONG(HO_TEN)

®èi tîng th«ng b¸o th«ng tin

Mçi ®èi tîng chØ tån t¹i trong mét thêi gian nhÊt ®Þnh. §èi tîng t¹o ra khi nã ®îc khai b¸o vµ sÏ bÞ huû bá khi ch¬ng tr×nh ra khái miÒn x¸c ®Þnh cña ®èi tîng ®ã. Sù trao ®æi th«ng tin chØ cã thÓ thùc hiÖn trong thêi gian ®èi tîng tån t¹i.

I.9. Nh÷ng øng dông cña lËp tr×nh híng ®èi tîng

LËp tr×nh híng ®èi tîng lµ mét trong nh÷ng thuËt ng÷ ®îc nh¾c ®Õn nhiÒu nhÊt trong c«ng nghÖ phÇn mÒm vµ nã ®îc øng dông ®Ó ph¸t triÓn phÇn mÒm vµ nhiÒu lÜnh vùc kh¸c nhau. Trong sè ®ã cã øng dông quan träng vµ næi tiÕng nhÊt hiÖn nay lµ lÜnh vùc thiÕt kÕ giao diÖn víi ngêi sö dông. VÝ dô nh Windows, hµng tr¨m hÖ thèng víi giao diÖn Windows ®· dîc ph¸t triÓn dùa trªn kü thuËt lËp tr×nh híng ®èi tîng. Nh÷ng hÖ th«ng tin doanh nghiÖp trong thùc tÕ rÊt phøc t¹p, chøa nhiÒu ®èi tîng, c¸c thuéc tÝnh vµ hµm. §Ó gi¶i quyÕt nh÷ng hÖ thèng phøc hîp nh thÕ th× lËp tr×nh híng ®èi tîng l¹i tá ra kh¸ hiÖu qu¶. Tãm l¹i nh÷ng lÜnh vùc øng dông cña kü thuËt lËp tr×nh híng ®èi tîng bao gåm:

 Nh÷ng hÖ th«ng tin lµm viÖc theo thêi gian thùc.

 Trong lÜnh vùc m« h×nh ho¸ hoÆc m« pháng qu¸ tr×nh.

 C¸c c¬ së d÷ liÖu híng ®èi tîng.

 HÖ siªu v¨n b¶n vµ ®a ph¬ng tiÖn.

CÊu tróc d÷ liÖu mÉu víi C++

 LÜnh vùc trÝ tuÖ nh©n t¹o vµ c¸c hÖ chuyªn gia.

 LËp tr×nh song song vµ c¸c m¹ng n¬_ron.

 Nh÷ng hÖ tù ®éng ho¸ v¨n phßng vµ trî gióp quyÕt ®Þnh.

 Nh÷ng hÖ CAD/CAM.

Víi nhiÒu ®Æc tÝnh cña lËp tr×nh híng ®èi tîng nãi riªng, c¶ ph¬ng ph¸p ph¸t triÓn híng ®èi tîng nãi chung, chóng ta hy väng nÒn c«ng nghiÖp phÇn mÒm sÏ c¶i tiÕn kh«ng nh÷ng vÒ chÊt lîng mµ cßn gia t¨ng nhanh vÒ sè lîng trong t¬ng lai. Kü nghÖ híng ®èi tîng sÏ lµ thay ®æi c¸ch suy nghÜ vµ c¸ch thùc hiÖn qu¸ t×nh ph©n tÝch, thiÕt kÕ vµ cµi ®Æt c¸c hÖ thèng, gãp phÇn gi¶i quyÕt nh÷ng vÊn ®Ò tån t¹i trong c«ng nghÖ phÇn mÒm.

C++ cô lËp ®èi tr×nh c«ng híng lµ mét

tîng C++ lµ c«ng cô lËp tr×nh híng ®èi tîng. Ban ®Çu ®îc gäi lµ "C with class" (C víi c¸c líp) sau ®ã C++ ®îc ph¸t triÓn vµo nh÷ng n¨m ®Çu thËp kØ 80 ë AT&T Bell Laboratories. Nã ®îc ph¸t triÓn trªn nÒn ng«n ng÷ C. C++ lµ mét tËp më réng cña C, v× thÕ hÇu hÕt c¸c tÝnh chÊt cña C vÉn ®îc sö dông trong C++. §iÒu nµy cã nghÜa lµ hÇu nh toµn bé c¸c ch¬ng tr×nh ®îc viÕt b»ng C th× còng lµ ch¬ng tr×nh cña C++ . Tuy nhiªn còng cã mét sè kh¸c biÖt lµm cho ch¬ng tr×nh C kh«ng thùc ®îc díi ch¬ng tr×nh C++.

Ba kh¸i niÖm quan träng cña C++ ®îc bæ xung vµo C lµ: líp, hµm t¶i béi vµ to¸n tö t¶i béi. Nh÷ng kh¸i niÖm cho phÐp chóng ta t¹o ra nh÷ng kiÓu d÷ liÖu trõu tîng, kÕ thõa nhiÒu tÝnh chÊt cña nh÷ng kiÓu d÷ liÖu ®· x©y dùng vµ hç trî cho viÖc sö dông c¬ chÕ t¬ng øng béi cho C++ trë thµnh ng«n ng÷ híng ®èi tîng thùc sù. C¸c ®Æc tÝnh cña C++ cho phÐp ngêi lËp tr×nh dÔ dµng x©y dùng ®îc c¸c ch¬ng tr×nh lín, cã tÝnh më, dÔ thÝch nghi, c«ng viÖc b¶o tr× Ýt tèn kÐm h¬n. C++ lµ c«ng cô thÝch øng cho vÖc x©y dùng c¸c ch¬ng tr×nh lín nh c¸c hÖ so¹n th¶o ch¬ng, tr×nh dÞch, c¸c hÖ c¬ së d÷ liÖu, nh÷ng hÖ thèng truyÒn tin vµ nhiÒu øng dông phøc t¹p kh¸c.

C++ hç trî cho viÖc t¹o ra cÊu tróc ph©n cÊp c¸c ®èi tîng gióp chóng ta cã thÓ x©y dùng nh÷ng th viÖn c¸c ®èi tîng ®Ó cho nhiÒu ngêi lËp sö

CÊu tróc d÷ liÖu mÉu víi C++

dông ®îc. Do C++ lµ ng«n ng÷ lËp tr×nh híng ®èi tîng nªn tÊt nhiªn nã sÏ cã nh÷ng g× mµ "híng ®èi tîng" cã.

Ch¦¬ng ii

ThiÕt kÕ vµ cµi ®Æt c¸c líp ®èi tîng trong c++

II.1. §Þnh nghÜa líp

II.1.1. Khai b¸o líp tªn ®èi tîng

Khai b¸o líp lµ m« t¶ kiÓu vµ nhiÒu miÒn x¸c ®Þnh c¸c thµnh phÇn cña líp, khai b¸o líp còng nh khai b¸o c¸c kiÓu d÷ liÖu quen thuéc kh¸c, nã cã d¹ng nh sau:

CÊu tróc d÷ liÖu mÉu víi C++

class class_name

{

private: // vïng riªng (mÆc ®Þnh)

... // khai b¸o d÷ liÖu vµ c¸c hµm

public:// vïng c«ng céng

... // khai b¸o d÷ liÖu vµ c¸c hµm

};

// kÕt thóc b»ng dÊu ";"

Tõ kho¸ class ®Þnh nghÜa mét kiÓu d÷ liÖu trõu tîng cã tªn gäi lµ class_name. Trong néi dung líp cã c¸c biÕn vµ hµm, c¸c biÕn vµ hµm ®îc tæ chøc thµnh hai nhãm: dïng chung (public) vµ së h÷u riªng (private, protected). Nh÷ng thµnh phÇn ®îc khai b¸o private, protected chØ ®îc truy nhËp bëi c¸c hµm thµnh phÇn cña líp, riªng ®èi víi c¸c hµm kiÓu protected th× cho phÐp c¸c hµm thµnh phÇn trong c¸c líp cã quan hÖ kÕ thõa (líp dÉn xuÊt) míi ®îc truy nhËp. Ngîc l¹i c¸c thµnh phÇn kiÓu public cã thÓ ®îc truy nhËp tõ bªn ngoµi líp. Nguyªn lÝ che dÊu th«ng tin cña C++ ®îc thùc hiÖn b»ng c¸ch sö dông d¹ng khai b¸o private hoÆc protected. Tõ kho¸ private lµ tuú chän, nÕu mÆc ®Þnh th× nh÷ng thµnh phÇn kh«ng ®îc khai b¸o lµ public sÏ lµ private.

Nh÷ng biÕn ®îc khai b¸o trong c¸c líp ®îc gäi lµ d÷ liÖu thµnh phÇn, cßn c¸c hµm ®îc gäi lµ hµm thµnh phÇn. C¸c hµm thµnh phÇn kiÓu private chØ cã thÓ truy nhËp ®îc c¸c d÷ liÖu vµ hµm trong vïng private, cßn c¸c hµm thµnh phÇm kiÓu public th× truy nhËp ®îc tÊt c¶ c¸c kiÓu d÷ liÖu vµ c¸c hµm trong cïng líp.

class A

Trong líp Point th× c¸c biÕn ®îc khai b¸o trong vïng private (vïng riªng) lµ d÷ liÖu thµnh phÇn, cßn c¸c hµm trong vïng public (vïng chung) lµ c¸c thµnh phÇn. D÷ liÖu thµnh phÇn cña líp kh«ng thÓ cã kiÓu cña chÝnh líp ®ã, nhng cã thÓ lµ kiÓu con trá cña líp nµy, vÝ dô:

{

A x; // kh«ng cho phÐp, v× x kh«ng cã kiÓu líp A

A *p; // cho phÐp v× p lµ con trá kiÓu líp A

};

CÊu tróc d÷ liÖu mÉu víi C++

d÷ liÖu thµnh phÇn cña líp còng cã thÓ lµ liÓu cña líp kh¸c.

class A

{

- - -

};

class B

{

A a:

- - -

};

VÝ dô:

II.1.2. T¹o lËp c¸c ®èi tîng

Trong C++, mét ®èi tîng lµ mét phÇn tö d÷ liÖu ®îc khai b¸o kiÓu lµ mét class. Trong vÝ dô trªn, khai b¸o líp Point míi chØ x¸c ®Þnh c¸c thµnh phÇn cña líp Point chø cha t¹o ra mét ®èi tîng cô thÓ. Líp lµ mét kiÓu ®èi tîng trõu tîng, nªn sau khi ®Þnh nghÜa líp chóng ta cã thÓ khai b¸o c¸c biÕn gièng nh ®èi víi kiÓu ®îc ®Þnh nghÜa bëi ngêi sö dông.

Khi c¸c ®èi tîng ®îc t¹o lËp th× sÏ cã mét chïm bé nhí ®îc cÊp ph¸t ®Ó chøa c¸c thµnh phÇn d÷ liÖu cña mçi ®èi tîng. C¸c ®èi tîng cña cïng mét líp cã thÓ ®îc khëi ®Çu vµ g¸n cho mét ®èi tîng kh¸c. theo ngÇm ®Þnh, viÖc sao mét ®èi tîng lµ t¬ng ®¬ng víi viÖc sao mét thµnh phÇn cña nã.

CÊu tróc d÷ liÖu mÉu víi C++

C¸c ®èi tîng cßn cã thÓ ®îc cÊp ph¸t ®éng trong heap, gièng nh

nh÷ng phÇn tö kh¸c.

II.1.3. C¸c thµnh phÇn d÷ liÖu

C¸c thµnh phÇn d÷ liÖu trong mét líp kh«ng thÓ ®îc khai b¸o kiÓu auto, register, hay extern. Chóng cã thÓ lµ c¸c enum, nhãm bit vµ c¸c kiÓu d÷ liÖu cã s½n hoÆc cña ngêi sö dông ®Þnh nghÜa. Thµnh phÇn d÷ liÖu còng cã thÓ lµ mét ®èi tîng, tuy nhiªn chóng chØ cã thÓ lµ nh÷ng ®èi tîng cña c¸c líp ®· ®îc khai b¸o hoÆc ®· ®îc ®Þnh nghÜa tríc ®ã.

*D÷ liÖu thµnh phÇn kiÓu private

Khi c¸c thµnh phÇn d÷ liÖu mét líp ®îc khai b¸o theo kiÓu private th× chØ cã th¸nh phÇn cña chÝnh líp ®ã hoÆc c¸c líp b¹n cña nã míi ®îc truy nhËp ®Õn c¸c thµnh phÇn nµy.

*D÷ liÖu thµnh phÇn public

NÕu ta khai b¸o l¹i c¸c thµnh phÇn d÷ liÖu trong líp Point sang d¹ng public, tøc lµ: Lóc ®ã méi thµnh phÇn trong líp Point ®Òu cã thÓ ®îc truy nhËp tõ thÕ giíi bªn ngoµi.

*D÷ liÖu thµnh phÇn protected

§Ó sö dông ®îc c¸c thµnh phÇn d÷ liÖu cña mét líp tõ c¸c líp kh¸c nhng ph¶i b¶o ®¶m nguyªn lý che dÊu th«ng tin th× chóng ta ph¶i khai b¸o kiÓu protected. C¸c thµnh phÇn d÷ liÖu trong protected chØ cho phÐp c¸c thµnh phÇn trong cïng líp vµ trong dÉn xuÊt truy nhËp ®Õn.

*D÷ liÖu thµnh phÇn tÜnh static

D÷ liÖu thµnh phÇn tÜnh lµ d÷ liÖu ®îc khai b¸o víi tõ kho¸ static ë ®Çu. Khi d÷ liÖu thµnh phÇn tÜnh th× tÊt c¶ c¸c thÓ hiÖn cña líp ®ã ®Òu ®îc phÐp dïng chung thµnh phÇn d÷ liÖu nµy. D÷ liÖu theo kiÓu static ®îc ph©n bè ë mét vïng bé nhí cè ®Þnh trong qu¸ tr×nh liªn kÕt còng gièng nh c¸c biÕn ®îc khai b¸o theo kiÓu tæng thÓ (global).

BiÕn d÷ liÖu tÜnh cã nh÷ng tÝnh chÊt sau:

CÊu tróc d÷ liÖu mÉu víi C++

 Khi ®èi tîng ®Çu tiªn cña líp ®îc t¹o lËp th× c¸c biÕn d÷ liÖu

tÜnh ®îc g¸n lµ 0.

 ChØ cã mét b¶n sao cña biÕn tÜnh ®îc t¹o ra cho c¶ líp vµ sÏ

®îc sö dông chung cho tÊt c¶ c¸c ®èi tîng trong cïng líp.

 ChØ ®îc sö dông trong líp, nhng nã tån t¹i trong suèt thêi gian

ho¹t ®éng cña ch¬ng tr×nh.

II.2. TÝnh t¬ng øng béi

Nh trªn ®· nãi t¬ng øng béi lµ kh¶ n¨ng sö dông mét tªn gäi díi nhiÒu d¹ng kh¸c nhau. Hµm vµ to¸n tö t¶i béi lµ hai trêng hîp ®iÓn h×nh cña t¬ng øng béi. Hµm, to¸n tö t¶i béi sÏ ®îc ph©n tÝch ®Ó ®èi s¸nh vÒ kiÓu, sè lîng tham biÕn trong thêi gian dÞch ®Ó chän ra hµm, to¸n tö t¬ng øng. Liªn kÕt ®îc thùc hiÖn trong thêi gian biªn dÞch ®îc gäi lµ thêi gian tÜnh.

ThÕ m¹nh cña t¬ng øng béi cã hai cÊp:

 Cho phÐp chóng ta xö lý c¸c kh¸i niÖm cã liªn hÖ nhau theo mét c¸ch gièng nhau, lµm cho ch¬ng trÝnh tæng qu¸t h¬n vµ dÔ hiÓu h¬n.

 TÝnh t¬ng øng béi cã thÓ ®îc dïng ®Ó viÕt ch¬ng tr×nh cã thÓ më réng nhiÒu h¬n. Khi mét lo¹i míi ®îc thªm vµo cã liªn hÖ víi c¸c kiÓu ®ang cã th× b¶n chÊt t¬ng øng béi cña nã sÏ lµm cho lo¹i míi nµy thÝch hîp ngay vµo hÖ thèng mµ kh«ng ®ßi hái ph¶i thay phÇn cßn l¹i cña ch¬ng tr×nh.

C¬ chÕ thùc hiÖn t¬ng øng béi:

T¬ng øng béi

T¬ng øng béi trong thêi gian dÞch T¬ng øng béi trong thêi gian thùc hiÖn

CÊu tróc d÷ liÖu mÉu víi C++

II.2.1. Hµm t¶i béi

Ng«n ng÷ C kh«ng cho phÐp ngêi lËp tr×nh sö dông cïng mét tªn cho nhiÒu hµm trong mét ch¬ng tr×nh. Tuy vËy trong C++, viÖc ®Þnh nghÜa nµy lµ hoµn toµn hîp lÖ, c¸c hµm nµy kh¸c nhau vÒ sè lîng hoÆc kiÓu cña c¸c ®èi sè cho hµm. C¸c hµm nh vËy ®îc gäi lµ hµm t¶i béi (kÓ c¶ cÊu tõ).

II.2.2. To¸n tö t¶i béi.

§· nhiÒu lÇn chóng ta kh¼ng ®Þnh r»ng trong C++ chóng ta cã thÓ t¹o ra nh÷ng kiÓu d÷ liÖu míi cã hµnh vi gièng nh c¸c kiÓu d÷ liÖu c¬ së. H¬n thÕ n÷a chóng ta cßn cã thÓ ®a thªm ®Þnh nghÜa míi cho nh÷ng to¸n tö ®îc ®Þnh nghÜa tríc. Nh÷ng to¸n tö cïng tªn thøc hiÖn ®îc nhiÒu chøc n¨ng kh¸c nhau ®îc gäi lµ toµn tö t¶i béi.

Quy t¾c x©y dùng to¸n tö t¶i béi:

1. ChØ cã thÓ x©y dùng nh÷ng to¸n tö ®· cã trong C++ ®Ó thµnh to¸n tö

béi . Kh«ng thÓ tù ý t¹o ra nh÷ng to¸n tö míi .

2. To¸n tö t¶i béi ph¶i cã Ýt nhÊt mét to¸n h¹ng cã kiÓu lµ kiÓu ®îc

®Þnh nghÜa bëi ngêi sö dông .

CÊu tróc d÷ liÖu mÉu víi C++

3. Chóng ta kh«ng thÓ tù ý lµm thay ®æi ý nghÜa c¬ b¶n cña to¸n tö ®· ®îc ®Þnh nghÜa tríc . VÝ dô, chóng ta kh«ng thÓ ®Þnh nghÜa l¹i ®îc c¸c phÐp +, - ®èi víi c¸c kiÓu c¬ së ( int, float).

4. To¸n tö t¶i béi ®îc x©y dùng vµ sö dông tu©n theo quy t¾c có ph¸p cña to¸n tö c¬ së nh ®· ®îc ®Þnh nghÜa trong ng«n ng÷.

5. Mét sè to¸n tö kh«ng thÓ ®Þnh nghÜa thµnh to¸n tö t¶i béi ®îc (

b¶ng 3-1).

6. Mét sè to¸n tö kh«ng thÓ sö sông víi friend ®Ó thµnh hµm to¸n tö t¶i béi( b¶ng 3-2), nhng cã thÓ sö dông hµm thµnh phÇn ®Ó ®æi thµnh hµm to¸n tö t¶i béi.

7. Hµm thµnh phÇn to¸n tö t¶i béi mét ng«i kh«ng cã tham biÕn vµ tr¶ l¹i gi¸ trÞ têng minh. Hµm th©n thiÖn to¸n tö t¶i béi mét ng«i cã tham biÕn lµ ®èi tîng.

8. Hµm thµnh phÇn lµ to¸n tö t¶i béi hai ng«i cã mét tham biÕn vµ hµm th©n thiÖn lµ to¸n tö t¶i béi nhÞ nguyªn cã hai tham biÕn.

9. Khi sö dông hµm thµnh phÇn lµ to¸n tö t¶i béi nhÞ nguyªn th× to¸n h¹ng bªn tr¸i cña to¸n tö ph¶i lµ ®èi tîng trong líp chøa hµm thµnh phÇn ®ã .

10. Nh÷ng to¸n tö sè häc nhÞ nguyªn +, -, *. Vµ / ph¶i tr¶ l¹i gi¸ trÞ

mét c¸ch têng minh.

sizeof To¸n tö x¸c ®Þnh kÝch thíc

To¸n tö x¸c ®Þnh thµnh phÇn .

.* To¸n tö x¸c ®Þnh thµnh phÇn mµ con trá tíi

:: To¸n tö ph©n gi¶i miÒn x¸c ®Þnh

?: To¸n tö ®iÒu kiÖn

B¶ng 3-1. Nh÷ng to¸n tö kh«ng thÓ t¶i béi

CÊu tróc d÷ liÖu mÉu víi C++

 To¸n tö g¸n

( ) To¸n tö gäi thùc hiÖn mét hµm

[ ] To¸n tö x¸c ®Þnh mét phÇn tö cña b¶ng

- > To¸n tö truy cËp tíi phÇn tö cña líp

B¶ng 3-2. Nh÷ng to¸n tö kh«ng sö dông ®îc víi friend

§Þnh nghÜa to¸n tö t¶i béi

§Þnh nghÜa tæng qu¸t cña to¸n tö t¶i béi lµ:

return-type class-name::operator op(arg-list)

{

------------;// phÇn th©n cña c¸c hµm to¸n tö

}

§Ó ®a thªm mét chøc n¨ng míi cho to¸n tö, chóng ta ph¶i biÕt ®îc ý nghÜa cña chøc n¨ng ®ã liªn quan nh thÕ nµo víi c¸c líp mµ to¸n tö ®ã sÏ ®îc ¸p dông.

Trong ®ã return-type lµ kiÓu cña kÕt qu¶ thùc hiÖn c¸c phÐp to¸n, op lµ to¸n tö t¶i béi ®øng sau lµ tõ kho¸ operator op ®îc gäi lµ hµm c¸c to¸n tö víi c¸c tham biÕn lµ arg-list.

Hµm c¸c to¸n tö t¶i béi ph¶i lµ hµm thµnh phÇn (kh«ng ph¶i lµ hµm tÜnh) hoÆc lµ hµm th©n thiÖn (friendly). Sù kh¸c nhau c¬ b¶n gi÷a chóng lµ:

 Hµm thµnh phÇn t¶i béi kh«ng cã ®èi sè cho hµm to¸n tö mét ng«i

vµ mét ®èi sè cho hµm to¸n tö hai ng«i .

 Hµm t¶i béi th©n thiÖn cã mét ®èi sè cho hµm to¸n tö mét ng«i ,

hai ®èi sè cho hµm to¸n tö hai ng«i .

CÊu tróc d÷ liÖu mÉu víi C++

Cã sù kh¸c nhau nµy bëi v× ®èi víi hµm thµnh phÇn th× ®èi tîng ®îc sö dông liªn quan ®Õn hµm thµnh phÇn ®ù¬c tù ®éng truyÒn vµo tham sè cho nã cßn hµm th©n thiÖn th× kh«ng lµm ®îc ®iÒu ®ã.

VÝ dô:

class Vector

{

private:

int v[100];

public:

openrator + (vector); // céng vector, hµm thµnh phÇn.

openrator - (vector & a); // trõ vector, hµm thµnh phÇn.

openrator  (const vector & a); // phÐp g¸n vector, hµm thµnh phÇn.

openrator -(); // ®æi dÊu vector, hµm thµnh phÇn.

friend vector+(vector, vector);// céng vector hµm th©n thiÖn.

int oprator  (vector);// so s¸nh hµm thµnh phÇn.

friend int  (vector, vector);// so s¸nh, hµm th©n thiÖn.

};

Trong ®ã c¸c vector lµ líp c¸c ®èi tîng.

Qu¸ tr×nh x¸c ®Þnh c¸c hµm to¸n tö t¶i béi ®îc thùc hiÖn nh sau:

 §Þnh nghÜa líp ®Ó x¸c ®Þnh kiÓu d÷ liÖu sÏ ®îc x¸c ®Þnh trong

phÐp to¸n t¶i béi.

 Khai b¸o hµm operator op trong vïng chung public cña líp. Nã cã

thÓ lµ hµm thµnh phÇn, hoÆc lµ hµm th©n thiÖn.

CÊu tróc d÷ liÖu mÉu víi C++

 §Þnh nghÜa néi dung c«ng viÖc cÇn thùc hiÖn.

Hµm thµnh phÇn op x (hoÆc x op) sÏ lµ:

operator op(x) ®èi víi hµm th©n thiÖn. BiÓu thøc x op y sÏ ®îc chuyÓn sang s¹ng: x.operator op(y) ®èi víi hµm thµnh phÇn vµ operator op (x,y) ®èi víi hµm th©n thiÖn.

To¸n tö t¶i béi sö dông víi friend:

§Ó sö dông hµm to¸n tö t¶i béi th©n thiÖn ta chØ viÖc khai b¸o tõ kho¸ friend ë ®Çu, sau ®ã ®Þnh nghÜa l¹i to¸n tö. Trong nhiÒu trêng hîp, kÕt qu¶ cña viÖc sö dông hµm thµnh phÇn gièng hÖt nh hµm th©n thiÖn. Mét c©u hái ®Æt ra lµ t¹i sao ph¶i ph©n biÖt hai trêng hîp nh thÕ? HiÓn nhiªn lµ v× cã nh÷ng t×nh huèng ®ßi hái ph¶i sö dông hµm th©n thiÖn mµ kh«ng sö dông hµm thµnh phÇn ®îc.

II.2.2 ChuyÓn ®æi kiÓu

ChuyÓn ®æi kiÓu lµ mét trong nh÷ng ®Æc tÝnh m¹nh cña C mµ c¸c ng«n ng÷ kh¸c hÇu nh kh«ng cã ®îc. Mét biÓu thøc cã thÓ cã nh÷ng h»ng, biÕn ë nhiÒu kiÓu kh¸c nhau vµ khi thùc hiÖn sÏ ¸p dông quy t¾c chuyÓn ®æi kiÓu tù ®éng ®îc ch¬ng tr×nh dÞch cµi ®Æt s½n, kiÓu d÷ liÖu ë bªn ph¶i phÐp g¸n sÏ tù ®éng chuyÓn ®æi sang kiÓu ë bªn tr¸i. Tuy nhiªn ®iÒu nµy sÏ khã thùc hiÖn ®îc ®èi víi kiÓu d÷ liÖu do ngêi sö dông ®Þnh nghÜa, b©y giê ta xÐt c¸c phÐp to¸n chuyÓn kiÓu trªn líp.

 Tõ kiÓu c¬ së sang kiÓu líp. §Ó thùc hiÖn ®æi kiÓu d÷ liÖu sang

líp chóng ta sö dông to¸n tö khëi t¹o ®èi tîng.

 Tõ kiÓu líp sang kiÓu c¬ së. C++ cho phÐp ®Þnh nghÜa to¸n tö quy håi kiÓu t¶i béi ®Ó chuyÓn d÷ liÖu kiÓu líp sang d¹ng kiÓu c¬ së. D¹ng tæng qu¸t cña to¸n tö quy håi kiÓu t¶i béi ë d¹ng hµm: operator double() chuyÓn líp vector sang kiÓu double. Khi ®ã trong ch¬ng tr×nh chóng ta cã thÓ viÕt:

double len  double(v1); // v1 lµ ®èi tîng trong líp vector hoÆc:

double len  v1;

CÊu tróc d÷ liÖu mÉu víi C++

Hµm to¸n tö kiÓu quy håi ph¶i tháa m·n nh÷ng tÝnh chÊt sau:

- Nã ph¶i lµ hµm thµnh phÇn cña mét líp.

- Nã kh«ng chØ ®Þnh kiÓu gi¸ trÞ quay trë l¹i.

- Nã kh«ng cã ®èi sè.

 Tõ mét líp sang mét líp kh¸c: viÖc chuyÓn ®æi kiÓu gi÷a nh÷ng ®èi tîng ë nhiÒu líp kh¸c nhau ®îc thùc hiÖn th«ng qua to¸n tö khëi t¹o ®èi tîng hoÆc hµm ®æi kiÓu. Hµm ®æi kiÓu ph¶i lµ hµm thµnh phÇn: operator type_name0. ChuyÓn ®èi tîng trong líp chøa nã sang kiÓu type_name. Type_name cã thÓ lµ kiÓu bÊt kú. NÕu chuyÓn kiÓu gi÷a c¸c ®èi tîng th«ng qua cÊu tö th× thùc chÊt lµ sao chÐp d÷ liÖu gi÷a c¸c ®èi tîng.

II.3. KÕ thõa vµ sù më réng c¸c líp

Kh¶ n¨ng sö dông l¹i lµ ®Æc tÝnh quan träng cña lËp tr×nh híng ®èi tîng. ViÖc sö dông l¹i nh÷ng ®¬n thÓ ch¬ng tr×nh, nh÷ng líp ®· ®îc ph¸t triÓn tèt, ®· ®îc kiÓm nghiÖm kh«ng nh÷ng tiÕp kiÖm ®îc tiÒn cña, thêi gian mµ cßn lµm t¨ng thªm nh÷ng kh¶ n¨ng t¬ng thÝch, ®é tin cËy cña hÖ thèng.

C++ hç trî rÊt m¹nh cho nh÷ng kh¸i niÖm vÒ sö dông l¹i. Líp ®îc thiÕt kÕ trong C++ lu«n lu«n cã thÓ ®îc sö dông l¹i theo nhiÒu c¸ch kh¸c nhau. Khi mét líp ®· ®îc ®Þnh nghÜa, ®îc kiÓm nghiÖm th× ngêi lËp tr×nh kh¸c cã thÓ sö dông nã trong c¸c môc ®Ých riªng cña m×nh. Nh÷ng líp nµy lµ líp c¬ së ®Ó t¹o ra nh÷ng líp míi (líp dÉn xuÊt), sö dông l¹i nh÷ng tÝnh chÊt trong nh÷ng líp ®· ®îc x¸c ®Þnh. C¬ chÕ dÉn xuÊt ra nh÷ng líp míi tõ nh÷ng líp tríc gäi lµ sù kÕ thõa (hoÆc dÉn xuÊt).

Líp dÉn xuÊt cã thÓ kÕ thõa mét sè hoÆc tÊt c¶ nh÷ng ®Æc tÝnh cña líp c¬ së, vµ cã thÓ kÕ thõa mét hay nhiÒu líp ë c¸c møc kh¸c nhau. C++ cung cÊp cho chóng ta 5 lo¹i kÕ thõa sau:[3]

1. KÕ thõa ®¬n.

2. KÕ thõa ®a møc.

CÊu tróc d÷ liÖu mÉu víi C++

3. KÕ thõa ph©n cÊp.

4. KÕ thõa béi.

5. KÕ thõa kÐp (phøc hîp).

class derrved_class_name: mode base_class_name

{

----------

----------// c¸c thµnh phÇn cña líp dÉn xuÊt

----------

};

C¸ch t¹o ra líp dÉn xuÊt (derrved_class_name) tõ mét líp c¬ së (base_class_name):

DÊu

':' chØ ra r»ng líp derrved_class-name ®îc dÉn ra tõ base_class_name. Tõ mode lµ thÓ khai b¸o tuú chän, cã thÓ lµ private hoÆc lµ public. MÆc nhiªn lµ private (kh«ng cã mode).

Khi líp dÉn xuÊt khai b¸o kÕ thõa theo kiÓu private th× tÊt c¶ nh÷ng thµnh phÇn chung public cña líp c¬ së trë thµnh phÇn riªng private cña líp dÉn xuÊt vµ v× vËy nh÷ng thµnh phÇn public cña líp c¬ së chØ cã thÓ truy nhËp ®îc th«ng qua hµm thµnh phÇn cña líp kÕ thõa.

Ngîc l¹i, khi khai b¸o kÕ thõa theo kiÓu public th× c¸c thµnh phÇn chung cña líp c¬ së còng trë thµnh phÇn chung cña líp dÉn xuÊt, nªn c¸c ®èi tîng cña líp dÉn xuÊt cã thÓ truy nhËp ®Õn thµnh phÇn public cña, líp c¬ së (h×nh 3-3).

Trong c¶ hai trêng hîp, thµnh phÇn private cña líp c¬ së hoµn toµn kh«ng ®îc kÕ thõa. V× thÕ nh÷ng thµnh phÇn private cña líp c¬ së kh«ng khi nµo trë thµnh thµnh phÇn cña lãp dÉn xuÊt.

II.3.1. KÕ thõa ®¬n

KÕ thõa ®¬n lµ mét líp chØ kÕ thõa mét líp ®· cã.

CÊu tróc d÷ liÖu mÉu víi C++

A Líp c¬ së

B Líp dÉn xuÊt

Chóng ta cã thÓ m« t¶ nh sau:

class A

private D÷ liÖu vµ hµm

protected D÷ liÖu vµ hµm Líp c¬ së A

public D÷ liÖu vµ hµm Líp dÉn xuÊt B

class B: public A

{

---------// D÷ liÖu vµ hµm vïng private

*Líp B kÕ thõa kiÓu public tõ líp A:

---------// D÷ liÖu vµ hµm vïng protected

---------// D÷ liÖu vµ hµm vïng public

};

CÊu tróc d÷ liÖu mÉu víi C++

líp B ®îc m« t¶ nh sau:

class B

Vïng puclic Vïng private Vïng private Vïng protected

D÷ liÖu vµ hµm public A D÷ liÖu vµ hµm protected A

D÷ liÖu vµ D÷ liÖu vµ hµm private B hµm private B

D÷ liÖu vµ hµm public B D÷ liÖu vµ hµm protected B

Líp B kÕ thõa nh÷ng thµnh phÇn chung cña A. Nh÷ng thµnh phÇn chung cña A kh«ng ®îc kÕ thõa. §Ó truy nhËp ®îc tíi thµnh private cña A nh a (nh÷ng thµnh phÇn kh«ng ®îc kÕ thõa) ë trong B th× chóng ta ph¶i sö dông tíi hµm thµnh phÇn ®îc kÕ thõatõ A lµ get_a().

* Líp B kÕ thõa kiÓu private tõ líp A. Lóc ®ã d÷ liÖu vµ hµm cña líp

B ®îc m« t¶ nh trong h×nh trªn.

Ta thÊy víi c¬ chÕ kÕ thõa kiÓu private th× ®èi tîng X cña líp B kh«ng thÓ sö dông trùc tiÕp nh÷ng thµnh phÇn public cña A. do vËy cã lÖnh:

X.get_ab();

X.get_a();

X.show_a();

®Òu kh«ng thùc hiÖn ®îc, bëi v× chóng ®· trë thµnh private cña líp B.

class B

Vïng public Vïng private

more information and additional documents D÷ liÖu vµ hµm connect with me here: http://facebook.com/ngphutien/ public A file đồ án kèm theo: Cau truc du lieu voi C++.rar 259 KB D÷ liÖu vµ hµm public B https://mega.co.nz/#!FgU3nAKa!-VgkoAGeGZtP3Q2LwN2LKMQXE4Uj67Q4nbAJrT4aGB8

D÷ liÖu vµ hµm private B

CÊu tróc d÷ liÖu mÉu víi C++

H×nh 3-5 Bæ sung thµnh phÇn kÕ thõa vµo vïng private.

Chóng ta thÊy r»ng, nh÷ng thµnh phÇn khai b¸o ë vïng private cña líp c¬ së kh«ng ®îc kÕ thõa. Do vËy mµ líp kÕ thõa cña líp dÉn xuÊt kh«ng sö dông ®îc nh÷ng thµnh phÇn mµ nã kÕ thõa. Chóng ta sÏ thùc hiÖn nh thÕ nµo khi trong líp dÉn xuÊt cã nhu cÇu kÕ thõa nh÷ng thµnh phÇn d÷ liÖu private cña líp c¬ së. §iÒu nµy cã thÓ thùc hiÖn ®îc b»ng c¸ch chuyÓn d÷ kiÖu thµnh phÇn ®Æc khai b¸o trong vïng private sang vïng public. Nhng khi ®ã th× d÷ liÖu ®ã l¹i cã thÓ truy nhËp bëi tÊt c¶ nh÷ng thµnh phÇn kh¸c trong ch¬ng tr×nh. §iÒu nµy ph¸ vì nguyªn lý che dÊu th«ng tin mµ chóng ta cÇn thùc hiÖn.

class A

{

private:

_ _ _ _ _

protected:

_ _ _ _ _

public:

§Ó gi¶i quyÕt vÊn ®Ò trªn, C++ ®a thªm thÓ khai b¸o protected (®îc b¶o vÖ) cho nh÷ng thµnh phÇn cña líp c¬ së cÇn ®îc kÕ thõa chØ trong nh÷ng líp dÉn xuÊt trùc tiÕp. Nh÷ng thµnh phÇn ®îc khai b¸o protected cã thÓ ®îc truy nhËp bëi nh÷ng thµnh phÇn trong cïng líp vµ trong nh÷ng líp dÉn xuÊt trùc tiÕp tõ líp c¬ së. Nh vËy, ®Ó cã nh÷ng thµnh phÇn protected ta chØ cÇn khai b¸o nh sau:

_ _ _ _ _

};

Mèi quan hÖ gi÷a c¸c thµnh phÇn cña líp c¬ së vµ líp dÉn xuÊt ®îc m« t¶ trong b¶ng 3- 3 vµ h×nh 3-7.

CÊu tróc d÷ liÖu mÉu víi C++

Líp c¬ së Líp dÉn xuÊt

KiÓu dÉn xuÊt public KiÓu dÉn xuÊt private

private Kh«ng ®îc kÕ thõa Kh«ng ®îc kÕ thõa

protected protected private

B¶ng 3-3. Nh÷ng thµnh phÇn ®îc kÕ thõa.

public public private

private Kh«ng ®îc thõa kÕ Kh«ng ®îc thõa kÕ

protected

public

class D1: public B class D2: private B class B

private private

protected protected

public public

class X: public D1: public D2

CÊu tróc d÷ liÖu mÉu víi C++

H×nh 3-6 Sù t¬ng øng trong kÕ thõa

II.3.2. KÕ thõa ®a møc

Trong kÕ thõa ®a møc, c¸c líp ®îc tæ chøc nh sau:

A Líp «ng

Líp cha B Líp dÉn xuÊt trung gian

C Líp dÉn xuÊt Líp con

H×nh 3-7 KÕ thõa ®a møc

class A {. . .};// líp c¬ së

class B: public A {. . .};// B dÉn xuÊt tõ A

class C: public B {. . . }// C dÉn xuÊt tõ B

Líp dÉn xuÊt cña kÕ thõa ®a møc ®îc khai b¸o nh sau:

Qu¸ tr×nh kÕ thõa cã thÓ ®îc më réng tuú ý, nghÜa c¸c líp kÕ thõa nhau víi sè møc tuú ý. Trong kÕ thõa ®a møc th× nguyªn t¾c truy nhËp cña c¸c líp dÉn xuÊt ®èi víi c¸c líp c¬ së còng gièng nh trong kÕ thõa ®¬n vµ nã kh«ng bÞ h¹n chÕ bëi c¸c líp trung gian. Cã nghÜa lµ líp B truy nhËp ®îc ®Õn thµnh phÇn (d÷ liÖu vµ hµm trong vïng protected vµ public) cña líp A, líp C truy nhËp ®îc ®Õn thµnh phÇn cña líp B vµ còng truy nhËp trùc tiÕp ®îc ®Õn c¸c thµnh phÇn cña líp A mµ kh«ng cÇn ph¶i th«ng qua líp B.

II.3.3. KÕ thõa ph©n cÊp

KÕ thõa lµ sù ph©n cÊp c¸c líp, c¸c líp kÕ thõa nhau theo mét cÊu tróc ph©n cÊp ®îc gäi lµ kÕ thõa ph©n cÊp. C++ hç trî cho viÖc sö dông c¬ chÕ kÕ thõa ®Ó ph©n cÊp c¸c líp m« t¶ nh÷ng cÊu tróc ®îc thiÕt kÕ theo c¸ch tiÕp cËn ph©n cÊp. Cã thÓ m« t¶ tæng qu¸ nh sau:

CÊu tróc d÷ liÖu mÉu víi C++

A2 A3

A1 11

A11 A31 A32 A33 A21 A22

H×nh 3-8 KÕ thõa ph©n cÊp

II.3.4. KÕ thõa béi

Mét líp cã thÓ kÕ thõa thuéc tÝnh cña nhiÒu líp ®îc gäi lµ kÕ thõa béi. KÕ thõa béi cho phÐp chóng ta kÕt hîp ®Æc trng cña mét sè líp t¹o ra líp míi.

A1 A2 ............................. An

H×nh 3-9. KÕ thõa béi

Mét líp ®îc dÉn xuÊt tõ nhiÒu líp c¬ së ®îc khai b¸o nh sau:

class B: mode A1, mode A2, ..., mode An

{- - - - };

víi mode lµ kiÓu khai b¸o: public hoÆc private, vµ c¸c líp c¬ së ph¶i ®îc khai b¸o tríc.

II.3.5. KÕ thõa kÐp

KÕ thõa kÐp lµ sù kÕt hîp cña kÕ thõa ®a thøc vµ kÕ thõa béi. NghÜa lµ mét líp dÉn xuÊt cã thÓ kÕ thõa nhiÒu líp c¬ së vµ ë nhiÒu møc kh¸c nhau.

CÊu tróc d÷ liÖu mÉu víi C++

B C

H×nh 3-10. KÕ thõa kÐp

II.3.6. C¸c líp c¬ së ¶o

Trong thøc tÕ ®«i khi chóng ta gÆp t×nh huèng ®ßi hái ph¶i sö dông kÕt hîp c¶ ba lo¹i kÕ thõa: kÕ thõa béi, ®a møc vµ ph©n cÊp gäi lµ kÕ thõa lai ghÐp.

VÝ dô:

«ng_bµ

cha mÑ

con

H×nh 3-11 KÕ thõa lai kÐp

Líp kÕ thõa trùc tiÕp hai líp con CHA vµ MÑ. Ngoµi ra nã cßn kÕ thõa tõ «ng bµ theo hai ®êng kh¸c nhau. Nã kÕ thõa trùc tiÕp, mét sè ®Æc tÝnh cña «ng bµ (theo ®êng - - - ) vµ g¸n tiÕp qua cha, mÑ ( hai líp c¬ së trung gian). Nh vËy nh÷ng thµnh phÇn public vµ protected cña «ng bµ sÏ ®îc kÕ thõa ®óp ë líp con, lÇn thø nhÊt lµ kÕ thõa tõ cha, lÇn thø hai kÕ thõa tõ mÑ. NghÜa lµ líp con sÏ cã hai tËp c¸c thµnh phÇn kÕ thõa gièng nhau. Do vËy chóng ta ph¶i lo¹i bá d thõa. Trong C++ cho phÐp lo¹i bá nh÷ng thµnh phÇn d thõa nµy b»ng c¸ch khai b¸o líp c¬ së ¶o (virtual base class). Lóc ®ã chóng ta khai b¸o nh sau:

class ONG_BA

{------};

class CHA: virtual ONG_BA // hoÆc public virtual

{------};

class ME: virtual public ONG_BA

{------};

class CON: public CHA, public ME

{------};

CÊu tróc d÷ liÖu mÉu víi C++

Lóc nµy chØ cã mét b¶n sao cña ONG_BA sÏ ®îc kÕ thõa ë líp CON. Khi mét líp ®îc khai b¸o kÕ thõa tõ c¸c líp c¬ së ¶o th× chØ cã mét b¶n sao cña nh÷ng thµnh phÇn kÕ thõa ®îc chuyÓn cho líp dÉn xuÊt, bÊt luËn bao nhiªu ®êng kÕ thõa còng thÕ.

II.3.7 CÊu tö trong c¸c líp dÉn xuÊt

CÊu tö ®îc sö dông ®Ó t¹o lËp c¸c ®èi tîng. Nhng viÖc t¹o lËp c¸c ®èi tîng trong nh÷ng líp kÕ thõa ®îc thùc hiÖn nh thÕ nµo? Chóng ta thÊy cã nh÷ng ®iÓm kh¸c biÖt nh sau: nÕu trong líp c¬ së kh«ng cã mét cÊu tö nµo cã tham biÕn th× trong líp dÉn xuÊt kh«ng ph¶i cã hµm cÊu tö. Song nÕu mét líp c¬ së nµo ®ã cã chøa cÊu tö cã tham biÕn th× líp dÉn xuÊt còng ph¶i cã cÊu tö vµ c¸c tham sè thùc sù sÏ ®îc truyÒn t¬ng øng cho c¸c cÊu tö cã tham biÕn trong c¸c líp c¬ së. C¶ hai líp c¬ së vµ dÉn xuÊt ®Òu cã cÊu tö th× cÊu tö cña líp c¬ së thùc hiÖn tríc råi sau ®ã ®Õn líp cÊu tö cña líp dÉn xuÊt. Trong trêng hîp kÕ thõa béi th× c¸c cÊu tö cña líp ®îc thùc hiÖn lÇn lît theo thø tù mµ chóng ®îc khai b¸o trong líp dÉn xuÊt.

Trong trêng hîp kÕ thõa ®a møc th× c¸c cÊu tö ®îc thùc hiÖn theo

thø tù kÕ thõa theo ®a møc.

CÊu tö cña líp dÉn xuÊt ®îc ®Þnh nghÜa nh sau:

Ph¬ng_thøc_thiÕp_lËp_dÉn_xuÊt (DS1, DS2, ..., DSn, DSDX):

C¬_së_1 (DS1),

C¬_së_1 (DS2),

-------------------

{

------// Néi dung cÊu tö ë líp dÉn xuÊt

CÊu tróc d÷ liÖu mÉu víi C++

D (int a1, a2, float b1, float b2, int d1):

A(a1, a2), // gäi cÊu tö A trong líp A

B(b1, b2), // gäi cÊu tö B trong líp B

{

d = d1;

}

Trong ®ã phÇn ®Çu cña ph¬ng_thøc_thiÕt_lËp_tö_dÉn_xuÊt bao gåm hai thµnh phÇn c¸ch nhau b»ng hai dÊu chÊm ‘:’.§Çu tiªn lµ khai b¸o danh s¸ch nh÷ng tham biÕn sÏ ®îc truyÒn cho c¸c cÊu tö ë líp dÉn xuÊt lµ ph¬ng_thøc_thiÕt_lËp_dÉn_xuÊt (DS1, DS2, ...,DSn, DSDX), sau ®ã lµ c¸c lêi gäi tíi c¸c hµm cÊu tö ®· ®îc ®Þnh nghÜa ë nh÷ng líp c¬ së lµ C¬_së_1(DS1), ..., C¬_së_n(DSn). Trong ®ã DS1, DS2, ...., DSn lµ nh÷ng danh s¸ch tham biÕn ®îc sö dông ®Ó t¹o lËp c¸c ®èi tîng. VÝ dô:

CÊu tö D() cung cÊp c¸c gi¸ trÞ a1, a2 vµ b1, b2 ®Ó thùc hiÖn cÊu tö

A(a1, a2) trong líp A, B(b1, b2) trong líp B.

II.3.8. Hµm ¶o

T¬ng øng béi lµ cÊu tróc cho phÐp nh÷ng ®èi tîng cña nhiÒu líp kh¸c nhau cã kh¶ n¨ng xö lý cïng mét th«ng tin gièng nhau nhng ë nhiÒu d¹ng kh¸c nhau. Mét nhu cÇu ®Æt ra lµ lµm thÕ nµo xö lý ®îc c¸c ®èi tîng ®ã mµ kh«ng cÇn chó ý ®Õn c¸c líp cña chóng. ®Ó thùc hiÖn ®îc yªu cÇu trªn ®èi víi t¬ng øng béi ta cã thÓ sö dông hµm ¶o (virtual function).

CÊu tróc d÷ liÖu mÉu víi C++

C¸ch ®Þnh nghÜa hµm ¶o

Gi¶ sö A lµ líp c¬ së, c¸c líp B, C, D dÉn xuÊt ( trùc tiÕp hoÆc gi¸n tiÕp) tõ A. gi¶ sö trong 4 líp trªn ®Òu cã ph¬ng thøc trïng tªn, kiÓu, c¸c ®èi sè. ®Ó ®Þnh nghÜa c¸c ph¬ng thøc nµy lµ ph¬ng thøc ¶o, ta chØ cÇn:

 HoÆc thªm tõ kho¸ virtual vµo dßng tiªu ®Ò cña ph¬ng thøc bªn

trong ®Þnh nghÜa cña líp c¬ së.

 HoÆc thªm tõ kho¸ virtual vµo dßng tiªu ®Ò bªn trong ®Þnh nghÜa

cña tÊt c¶ c¸c líp A, B, C, D.

Quy t¾c gäi ph¬ng thøc ¶o

Ph¬ng thøc ¶o ®îc gäi th«ng qua mét con trá cña líp c¬ së, lóc ®ã ph¬ng thøc cña líp nµo ®îc gäi phô thuéc vµo ®èi tîng mµ con trá ®ang trá tíi.

Víi c¸c líp A, B, C, D ®· ®îc ®Þnh nghÜa, ®Ó truy nhËp ®Õn hµm

hiÓn_thÞ() cña c¸c líp ta khai b¸o nh sau:

A*p; // p lµ con trá kiÓu A

A a; B b; Cc; Dd; //khai b¸o c¸c ®èi tîng

p=&a;// p trá tíi ®èi tîng a cña líp A

p->hiÓn_thÞ(); // gäi tíi A:: hiÓn_thÞ()

p=&b; // p trá tíi ®èi tîng b cña líp B

p->hiÓn_thÞ(); // gäi tíi B::hiÓn_thÞ()

p=&c;// p trá tíi ®èi tîng c cña líp C

p->hiÓn_thÞ(); // gäi tíi C::hiÓn_thÞ()

Hµm ¶o ph¶i tu©n theo nh÷ng quy t¾c sau:

1. Hµm ¶o ph¶i lµ hµm thµnh phÇn cña líp.

2. Nh÷ng thµnh phÇn tÜnh kh«ng thÓ khai b¸o ¶o ®îc.

CÊu tróc d÷ liÖu mÉu víi C++

3. Sö dông con trá ®Ó truy nhËp ®Õn c¸c hµm ¶o.

4. Hµm ¶o cã thÓ lµ hµm th©n thiÖn (friend) cña líp kh¸c.

5. Hµm ¶o ph¶i ®îc ®Þnh nghÜa trong líp c¬ së hoÆc c¶ trong líp c¬

së vµ líp dÉn xuÊt, ngay c¶ khi kh«ng sö dông nã.

6. MÉu cña tÊt c¶ c¸c phiªn b¶n (líp c¬ së vµ líp dÉn xuÊt) ph¶i gièng nhau. NÕu hai hµm cïng tªn nhng gièng nhau th× C++ xem lµ to¸n tö t¶i béi.

7. Kh«ng ®îc t¹o ra to¸n tö ¶o, nhng cã thÓ t¹o ra ®îc ph¬ng

thøc huû bá ¶o.

8. Con trá kiÓu líp c¬ së cã thÓ dïng ®Ó x¸c ®Þnh ®èi tîng líp dÉn

xuÊt, nhng ngîc l¹i th× kh«ng.

9. Kh«ng dïng ®îc phÐp t¨ng gi¶m gi¸ trÞ con trá ®èi víi líp dÉn

xuÊt, mµ chØ cã t¸c dông víi líp c¬ së.

Ch¬ng III

Hµm vµ líp mÉu

CÊu tróc d÷ liÖu mÉu víi C++

III.1. Hµm mÉu

III.1.1. §Þnh nghÜa

int Square(int x){

return x*x;

}

vµ

float Square(float x){

return x*x;

}

Khi chóng ta muèn t¹o ra mét ch¬ng tr×nh C++ thùc hiÖn c¸c c«ng viÖc nµo ®ã cho tÊt c¶ c¸c kiÓu d÷ liÖu tÊt nhiªn ta sÏ sö dông hµm n¹p chång (function overloading). Ch¼ng h¹n ta muèn t¹o c¸c hµm tÝnh b×nh ph¬ng sè int vµ float, ta sÏ ph¶i t¹o hai hµm:

template

T Square (T x){

return x*x;

}

T¬ng tù nh vËy, cho mçi kiÓu d÷ liÖu kh¸c nhau ph¶i t¹o ra mét hµm Square míi. Ta nhËn thÊy r»ng m· lÖnh kh«ng ®æi chØ cã kiÓu d÷ liÖu lµ kh¸c nhau. ChÝnh v× vËy, ng«n ng÷ lËp tr×nh híng ®èi tîng C++ cho phÐp cµi ®Æt hµm tæng qu¸t vÒ d÷ liÖu, khi sö dông sÏ chØ ®Þnh cô thÓ ®Ó tr×nh biªn dÞch hiÓu ®îc. Hµm nh vËy ®îc gäi lµ hµm mÉu (template) nh vÝ dô trªn ta cã thÓ viÕt l¹i nh sau:

Trong ®ã T lµ tªn gäi mÉu cña kiÓu d÷ liÖu sö dông trong hµm. Víi

c¸ch viÕt nµy, cã thÓ sö dông mét kiÓu d÷ liÖu bÊt kú nµo kh¸c.

VÝ dô:

void main(){

cout << “Square(2)=”<

cout << “Square(7.1)=”<

}

CÊu tróc d÷ liÖu mÉu víi C++

Trong lÇn gäi thø nhÊt, hµm Square cã tham sè lµ int nªn tr×nh biªn dÞch sÏ t¹o ra hµm int Square (int), lÇn hai t¹o ra hµm cã d¹ng float Square (float).

III.1.2. Hµm mÉu cã nhiÒu tham sè h×nh thøc

VÝ dô:

template

T max

{

return (a>b)?a:b;

}

void main(){

float a,b;

cout << “ Vµo 2 sè:”<

cin >> a>>b>>endl;

cout << “ Sè lín h¬n:”<< max(a,b);

Trêng hîp hµm mÉu cã nhiÒu tham sè cïng kiÓu, khi tr×nh biªn dÞch biÕt ®îc kiÓu thø nhÊt th× c¸c tham sè cßn l¹i mang cïng kiÓu mÉu sÏ nhËn kiÓu cña tham sè thø nhÊt.

}

CÊu tróc d÷ liÖu mÉu víi C++

Trong trêng hîp nµy tr×nh biªn dÞch t¹o ra hµm float max(float,

float) theo d¹ng cña mÉu

III.1.3. Hµm mÉu cã nhiÒu tham sè kh¸c nhau

Hµm template cã nhiÒu tham sè víi kiÓu kh¸c nhau. Tuy nhiªn nã

VÝ dô:

template

A factorial (B n){

if (n>0) return n*factorial(n-1);

else return 1;

}

void main(){

float f;

f=factorial(20);

cout <<”20!=”<< f<< endl;

}

vÉn mang ®Çy ®ñ tÝnh chÊt cña hµm mÉu ®¬n gi¶n.

Chó ý:

 Trong viÖc t¹o ra hµm mÉu, chóng ta cã thÓ sö dông bÊt kú kiÓu

d÷ liÖu nµo kÓ c¶ do ngêi sö dông t¹o ra.

 Chóng ta vÉn cã thÓ x©y dùng hµm trïng tªn víi hµm template

nh hiÖn t¬ng n¹p chång.

template

T abs (T a){

return (a<0)?-a:a;

}

float abs(float a){

for (int i=0,float s=0;i<5;i++)

s+=abs(a[i]);

return s;

}

void main(){

float a[5]={2,-4,-3,5,-6};

cout <<”chuÈn cña vecto a lµ:”<

cout << “abs(-5.3)=”<

}

CÊu tróc d÷ liÖu mÉu víi C++

§Çu tiªn ch¬ng tr×nh sÏ t×m hµm cã tham sè phï hîp nÕu kh«ng t×m thÊy nã sÏ gäi hµm mÉu. Trong ch¬ng tr×nh cã hai hµm abs nhng do c¸ch truyÒn tham sè thùc vµ sù hiÖn diÖn cña hµm float abs(float). Ch¬ng tr×nh dÞch sÏ lùa chän ®óng ®Ó thùc hiÖn vµ biªn dÞch.

 Mét hµm mÉu ra lÖnh cho ch¬ng tr×nh dÞch c¸ch t¹o ra mét tËp c¸c hµm n¹p chång. Ch¬ng tr×nh dÞch chØ sinh ra m· cho c¸c kiÓu d÷ liÖu khi nã gäi hµm mÉu.

CÊu tróc d÷ liÖu mÉu víi C++

III.2. Líp mÉu

III.2.1. §Þnh nghÜa

Vi dô:

Template

class Record {

K key ;

D data;

public:

Record(K kx,D dx);

K GetKey(){return key;}

DgetData(){return data;}

}

template

Record ::Record(K kx,D dx){

key=kx;

data=dx;

Còng gièng nh hµm mÉu, líp mÉu còng mang ®Çy ®ñ tÝnh chÊt, t tëng cña hµm mÉu b»ng c¸ch cµi ®Æt mét líp chung tæng qu¸t nµo ®ã. Khi sö dông cho tõng trêng hîp cô thÓ líp sÏ mang kiÓu d÷ liÖu x¸c ®Þnh. §©y lµ c«ng cô m¹nh ®Ó x©y dùng c¸c líp chøa.

}

CÊu tróc d÷ liÖu mÉu víi C++

Lu ý:

 Khi néi dung cña ph¬ng thøc viÕt bªn ngoµi líp chóng ta ph¶i m« t¶ l¹i khai b¸o template phÝa tríc tÊt c¶ kÓ c¶ kiÓu tr¶ vÒ cña ph¬ng thøc. Cßn c¸c tham chiÕu bªn trong líp mÉu kh«ng ph¶i khai b¸o.

 C¸c líp mÉu cã thÓ thõa kÕ tõ c¸c líp mÉu kh¸c.

template

class Object: Record

{...}

VÝ dô:

 Líp mÉu cã thÓ lµ tham sè cho mét líp mÉu kh¸c:

Record > rec;

III.2.2. Líp mÉu cã tham sè

template

class Stack{...}

Ng«n ng÷ lËp tr×nh híng ®èi tîng C++ cho phÐp t¹o ra c¸c líp mÉu linh ®éng b»ng c¸ch cho phÐp thay ®æi gi¸ trÞ cña c¸c thµnh phÇn bªn trong líp. Khi ®ã líp cã d¹ng cña mét hµm víi tham sè h×nh thøc.

Chó ý:

Khi ®Þnh nghÜa mét líp mÉu, mçi líp mÉu cã ph¬ng thøc vµ d÷ liÖu riªng cña nã. Cho nªn cµng nhiÒu líp mÉu th× ch¬ng tr×nh cµng cÇn nhiÒu bé nhí. PhÇn lín c¸c mÉu sÏ ®îc ®Þnh nghÜa trong c¸c tÖp chøa khai b¸o vµ sÏ ®îc dÞch gép (include) khi sö dông líp ®ã.

III.3. KÕt luËn

CÊu tróc d÷ liÖu mÉu víi C++

C¸c hµm vµ líp mÉu cho phÐp t¹o ra mét hä c¸c hµm vµ c¸c líp ®Ó t¸c ®éng ®Õn c¸c kiÓu d÷ liÖu kh¸c nhau. Víi nh÷ng ®Æc ®iÓm næi bËt nµy, ch¬ng tr×nh híng ®èi tîng hoµn toµn linh ®éng vµ mang tÝnh kÕ thõa cao. §ång thêi nã gióp cho ngêi lËp tr×nh kh«ng ph¶i viÕt l¹i nh÷ng ®o¹n m· gièng nhau, còng nh lµm thiÓu m· nguån mét c¸ch ®¸ng kÓ.

Ch¬ng IV

CÊu tróc d÷ liÖu & C¸c líp mÉu

IV. CÊu tróc d÷ liÖu

C¸c ch¬ng tr×nh thêng chøa hai phÇn: gi¶i thuËt vµ cÊu tróc d÷ liÖu. Mét ch¬ng tr×nh tèt lµ ch¬ng tr×nh hoµ hîp ®îc c¶ hai vÊn ®Ò nµy. Sù chän lùa vµ thi hµnh cña mét cÊu tróc d÷ liÖu ®îc xem lµ quan träng ngang víi c¸c tr×nh vËn dông nã. Do ®ã, viÖc cã ph¬ng ph¸p ®óng lu vµ truy xuÊt d÷ liÖu trong mét sè trêng hîp lµ rÊt quan träng.

CÊu tróc d÷ liÖu ®îc xem nh mét tËp c¸c dÞch vô cung cÊp cho thÕ giíi bªn ngoµi, Ngêi sö dông kh«ng quan t©m ®Õn viÖc lu tr÷ cô thÓ trªn c¸c thiÕt bÞ vËt lý nh thÕ nµo,mµ chØ quan t©m ®Õn viÖc truy cËp – tøc lµ lu vµo vµ phôc håi nh thÕ nµo.

C¸c kiÓu cÊu tróc d÷ liÖu c¬ b¶n sau mµ t«i ®Ò cËp trong cuèn tiÓu

luËn nµy:

 Hµng ®îi (Queue).

 Hµng quay trßn (Circle).

 Ng¨n xÕp (Stack).

 Danh s¸ch liªn kÕt ®¬n (Simple List).

CÊu tróc d÷ liÖu mÉu víi C++

 Danh s¸ch liªn kÕt ®«i (double List).

 C©y nhÞ ph©n (Binary Tree).

IV.1.1. Líp chøa

Do c¸c tÝnh chÊt chung c¬ b¶n cña c¸c biÓu cÊu tróc d÷ liÖu tuyÕn tÝnh ng¨n xÕp hµng vµ hµng xoay nªn t«i ®· x©y dùng líp chøa thuÇn ¶o Sequence v× c¸c lý do sau:

 Sö dông ®îc sù thõa kÕ, tr¸nh ph¶i viÕt l¹i c¸c ph¬ng thøc d÷

liÖu ë c¸c líp kh¸c nhau.

 TËn dông ®îc søc m¹nh còng nh tÝnh linh ho¹t cña ph¬ng thøc

¶o vµo c¸c øng dông ®a d¹ng sau nµy.

Sequence

Stack Queue Circle

H×nh Líp chøa thuÇn ¶o Sequence

// SEQUENCE template class Sequence {

IV.1.2. Líp chøa thuÇn ¶o

protected:

size_t count; T data[size]; void Copy(const Sequence & seq);

public:

Sequence() { count=0;} Sequence(const Sequence & seq){ Copy(seq);} virtual int Put(const T & item)=0;//ph¬ng thøc ¶o virtual int Get(T & item)=0; virtual int See(T & item,int i)=0;//xem phÇn tö thø i size_t GetSize() { return size;} size_t GetCount() { return count;} void Flush() { count=0;}

}; //----------------------------------------------------------------------- template void Sequence::Copy(const Sequence & seq) {

count=seq.count; for(int i=0;i

}

CÊu tróc d÷ liÖu mÉu víi C++

IV.2.1. Ng¨n xÕp

Ng¨n xÕp lµ mét cÊu tróc tuyÕn tÝnh ®Æc biÖt nã sö dông c¸ch truy xuÊt vµo sau ra tríc, thêng ®îc gäi lµ LIFO(Last In First Out). Nãi chung ng¨n xÕp kh«ng ®îc sö dông ®Ó lu tr÷ d÷ liÖu tÜnh. Khi th«ng tin ®îc lÊy ra nã sÏ bÞ xo¸ khái ng¨n xÕp. Mét ng¨n xÕp cã thÓ rçng hoÆc cã c¸c phÇn tö.

Cã thÓ h×nh dung ng¨n xÕp nh mét chång ®Üa. C¸i ®Æt lªn bµn ®Çu tiªn sÏ ®îc sö dông sau cïng. Cßn ®Üa cuèi cïng n»m trªn ®Çu chång ®îc sö dông ®Çu tiªn. Ng¨n xÕp thêng ®îc dïng ®Ó truyÒn tham sè cho hµm.

IV.2.2. Lu tr÷ ng¨n xÕp b»ng m¶ng

Cã thÓ lu tr÷ ng¨n xÕp vµo mét m¶ng (vÐc t¬) gåm n phÇn tö nhí liªn tiÕp. Khi bæ xung mét phÇn tö sè lîng c¸c phÇn tö b»ng lªn mét, cßn khi lÊy ra mét phÇn tö sè lîng phÇn tö cña ng¨n xÕp gi¶m ®i mét, ®iÒu nµy ®îc minh ho¹ trong h×nh sau:

CÊu tróc d÷ liÖu mÉu víi C++

Get() Get() Put(A) Put(B)

A A B A

Chó ý:

 V× khèi lîng lu tr÷ cña ng¨n xÕp lµ h÷u h¹n (b»ng n) nªn khi ta bæ sung thªm mét phÇn tö cÇn ph¶i kiÓm tra sè lîng ®· ®¹t ®Õn giíi h¹n cha.

 Ngîc l¹i, khi lÊy ra mét phÇn tö tõ ng¨n xÕp, ta ph¶i kiÓm tra

cßn phÇn tö nµo trong ng¨n xÕp kh«ng.

IV.2.3. X©y dùng líp ng¨n xÕp mÉu

Líp d÷ liÖu mÉu ng¨n xÕp gåm mét sè ph¬ng thøc c¬ b¶n nh:

 LÊy mét phÇn tö Get().

 Lu tr÷ mét phÇn tö Put().

 Sè phÇn tö cña ng¨n xÕp Getcount().

 Cì cña ng¨n xÕp Getsize().

Ngoµi ra cßn cã mét sè ph¬ng thøc tiÖn Ých kh¸c hç trî cho c¸c

trêng hîp ®Æc biÖt:

 Xo¸ ng¨n xÕp Flush().

 Xem phÇn tö thø i mµ kh«ng ¶nh hëng ®Õn trËt tù cña ng¨n xÕp

See().

Líp ng¨n xÕp ®îc thõa kÕ tõ líp chøa Sequence.

//STACK template class Stack:public Sequence {

public: Stack():Sequence() {} Stack(const Stack & sta):Sequence(sta){} virtual int Put(const T & item); virtual int Get(T & item); virtual int See(T & item,int i); void operator =(const Stack & sta){ Copy(sta);}

}; //------Ghi mét phÇn tö vµo ------------------------------------------ template int Stack::Put(const T & item) {

if( count==size) return 1;// Trµn Stack data[count++]=item; return 0;

} //-------LÊy mét phÇn tö--------------------------------------------- template int Stack::Get(T & item) {

if (!count) return 1;//Stack rçng item=data[--count]; return 0;

} //-------Xem mét phÇn tö bÊt kú----------------------------------- template int Stack::See(T & item,int i) {

if(!i || i>count) return 1; item=data[--i]; return 0;

}

CÊu tróc d÷ liÖu mÉu víi C++

IV.3. Hµng ®îi

Ngîc l¹i víi ng¨n xÕp, hµng ®îi cho phÐp truy nhËp theo c¬ chÕ vµo tríc ra sau, thêng gäi lµ FIFO (first in first out), tøc lµ bæ sung d÷ liÖu ë mét ®Çu, vµ lÊy d÷ liÖu ra ë ®Çu kh¸c. Khi d÷ liÖu ®îc lÊy ra nã sÏ bÞ xo¸ khái hµng ®îi v× vËy mét hµng ®îi cã thÓ rçng hoÆc cã nhiÒu phÇn tö.

CÊu tróc d÷ liÖu mÉu víi C++

Hµng ®îi ®îc sö dông nhiÒu trong lËp tr×nh, mét trêng hîp th«ng thêng lµ viÖc m« pháng c¸c hµng ®îi còng ®îc dïng bëi bé ®Þnh lÞch cho c¸c t¸c vô cña hÖ ®iÒu hµnh vµ xuÊt nhËp.

IV.3.1. Lu tr÷ hµng ®îi b»ng m¶ng

Còng gièng nh ng¨n xÕp, hµng ®îi ®îc lu tr÷ trong m¶ng cã kÝch cì n. Ngoµi ra cßn cÇn hai biÕn chØ sè ®Ó ghi vÞ trÝ ®Çu (head) mµ mét phÇn tö cã thÓ ®îc lÊy ra, vµ vÞ trÝ ®u«i (tail) n¬i phÇn tö cuèi cã thÓ ®îc bæ sung. VÞ trÝ ®u«i ®îc t¨ng lªn khi bæ sung mét phÇn tö míi vµ khi lÊy ra mét phÇn tö th× ®Çu (head) t¨ng lªn mét. Cø nh vËy vÞ trÝ ®Çu ®uæi theo vÞ trÝ ®u«i. NÕu vÞ trÝ ®u«i vît qua chØ sè lín nhÊt cña m¶ng nã sÏ quay vÒ chØ sè nhá nhÊt. T¬ng tù nh vËy víi vÞ trÝ ®Çu.

head head

A Put(A)

tail tail

head head

A B Put(B) B Get()

tail tail

head

...

Put(E) E B C D

tail

H×nh M« t¶ c¸ch ho¹t ®éng cña Sequence

CÊu tróc d÷ liÖu mÉu víi C++

Chó ý: Tríc khi lÊy ra mét phÇn tö ph¶i kiÓm tra hµng cã rçng kh«ng, ngîc l¹i khi thªm vµo mét phÇn tö ph¶i kiÓm tra hµng ®· ®Çy cha.

IV.3.2 X©y dùng líp hµng ®îi mÉu

//QUEUE template class Queue:public Sequence {

protected: int head; int tail; public: Queue():Sequence(){ head=tail=0;} Queue(const Queue & que); virtual int Put(const T & item); virtual int Get(T & item); virtual int See(T & item,int i); void operator = (const Queue & que);

}; //---------Ph¬ng thø thiÕt lËp sao chÐp------------------------------- template Queue::Queue(const Queue & que):Sequence(que) {

head=que.head; tail=que.tail;

} //----------Ghi mét phÇn tö vµo ----------------------------------------- template int Queue::Put(const T & item) {

if(count==size) return 1;//trµn hµng if(!count){

head=tail=0; data[0]=item;

} else{

tail++; if(tail==size) tail=0; data[tail]=item;

} count++; return 0;

Còng gièng nh ng¨n xÕp, hµng ®îi cã nh÷ng ph¬ng thøc c¬ b¶n vµ mét sè ph¬ng thøc tiÖn Ých ®Æc biÖt kh¸c, ®îc thõa kÕ tõ líp chøa Sequence.

} //---------LÊy mét phÇn tö ----------------------------------------- template int Queue::Get(T & item) {

if(!count) return 1;//hµng rçng item=data[head]; count--; if(count){ head++; if(head==size) head=0;

} return 0;

} //-------Xem mét phÇn tö----------------------------------------- template int Queue::See(T & item,int i) {

if(i>count || !count) return 1; i--; int ind=i+head; if(ind>=size) ind-=size; item=data[ind]; return 0;

} //---------To¸n tö g¸n------------------------------------------ template void Queue::operator = (const Queue & que) {

head=que.head; tail=que.tail; Copy(que);

}

CÊu tróc d÷ liÖu mÉu víi C++

IV.4. Hµng quay trßn

Hµng quay trßn lµ mét cÊu tróc ®Æc biÖt khi mµ ®¹t ®Õn vÞ trÝ cuèi

cïng th× nã lÆp l¹i ë vÞ trÝ ®Çu tiªn.

Hµng quay trßn thêng ®îc sö dông trong c¸c hÖ ®iÒu hµnh, trong

//CIRCLE template

c¸c ch¬ng tr×nh øng dông thêi gian thùc.

class Circle:public Sequence {

protected: int current; public: Circle():Sequence(){ current=0;} Circle(const Circle & cir):Sequence(cir){ current=cir.current;} virtual int Put(const T & item); virtual int Get(T & item); virtual int See(T & item,int i); void operator = (const Circle & cir);

}; //---------Ghi mét phÇn tö----------------------------------------- template int Circle::Put(const T & item) {

if(count==size) return 1; data[count++]=item; return 0;

} //-----------LÊy mét phÇn tö--------------------------------------- template int Circle::Get(T & item) {

if(!count) return 1; item=data[current++]; if(current==size) current=0; return 0;

} //------Xem mét phµn tö---------------------------------------- template int Circle::See(T & item,int i) {

if(!count) return 1; if(i>count) i%=count; if(!i) i=count; item=data[--i]; current=i; return 0;

} //----------To¸n tö g¸n------------------------------------------ template void Circle::operator = (const Circle & cir) {

current=cir.current; Copy(cir);

}

CÊu tróc d÷ liÖu mÉu víi C++

IV.5. Danh s¸ch liªn kÕt more information and additional documents connect with me here: http://facebook.com/ngphutien/ file đồ án kèm theo: Cau truc du lieu voi C++.rar 259 KB https://mega.co.nz/#!FgU3nAKa!-VgkoAGeGZtP3Q2LwN2LKMQXE4Uj67Q4nbAJrT4aGB8

CÊu tróc d÷ liÖu mÉu víi C++

Nh chóng ta ®· biÕt, m¶ng (sö dông c¸c vïng bé nhí liªn tôc) ®îc sö dông réng r·i trong nhiÒu øng dông. Tuy nhiªn nã cã h¹n chÕ: kÝch thíc ph¶i biÕt tríc, thêi gian dÞch, d÷ liÖu trong m¶ng ®îc chia víi nh÷ng kho¶ng c¸ch nh nhau trong bé nhí. §iÒu nµy cã nghÜa lµ viÖc chÌn mét phÇn tö vµo m¶ng th× ph¶i dÞch chuyÓn c¸c phÇn tö kh¸c trong m¶ng, ngoµi ra cßn l·ng phÝ bé nhí khi kh«ng cßn sö dông. Sù giíi h¹n nµy ®îc kh¾c phôc b»ng viÖc sö dông cÊu tróc liªn kÕt. CÊu tróc liªn kÕt lµ mét tËp c¸c nót (node), lu tr÷ d÷ liÖu vµ c¸c liªn kÕt (links) bëi c¸c nót kh¸c. B»ng c¸ch nµy, c¸c nót cã thÓ ®Æt bÊt kú n¬i nµo trong bé nhí vµ viÖc ®i qua tõ nót nµy sang nót kh¸c ®îc thùc hiÖn b»ng lu tr÷ c¸c ®Þa chØ cña nót kh¸c trong danh s¸ch.

IV.6. Danh s¸ch liªn kÕt ®¬n

Danh s¸ch liªn kÕt ®¬n yªu cÇu mçi nót chøa mét liªn kÕt ®Õn phÇn tö kÕ tiÕp trong danh s¸ch. Riªng nót cuèi cïng kh«ng cã phÇn tö ®øng sau nªn con trá cña nót nµy chøa gi¸ trÞ ®Æc biÖt ®Ó ®¸nh dÊu kÕt thóc danh s¸ch gäi lµ nót rçng (NULL).

§Ó truy nhËp ®îc tÊt c¶ c¸c nót trong danh s¸ch th× cÇn truy nhËp

nót ®Çu tiªn.

Theo quan niÖm danh s¸ch liªn kÕt ®¬n gièng nh h×nh minh ho¹

Infor Infor Infor

Link Link Link

IV.6.1. Thªm mét phÇn tö vµo danh s¸ch

Cã hai c¸ch ®Ó x©y dùng mét danh s¸ch liªn kÕt ®¬n:

 Mçi phÇn tö míi vµo cuèi danh s¸ch.

CÊu tróc d÷ liÖu mÉu víi C++

 Thªm phÇn tö míi vµo mét vÞ trÝ ®Æc biÖt trong danh s¸ch.

Cã ba trêng hîp khi chÌn thªm mét phÇn tö míi vµo mét danh s¸ch

liªn kÕt ®¬n:

 Nót míi trë thµnh phÇn tö ®Çu tiªn míi.

 §øng gi÷a hai phÇn tö kh¸c nhau.

 Trë thµnh phÇn tö cuèi cïng.

Chó ý:

 Khi thay ®æi phÇn tö ®Çu tiªn hoÆc cuèi cïng, ta ph¶i thay ®æi ®Þa

chØ míi cho c¸c biÕn lu tr÷ t¬ng øng.

 §Ó dÔ h×nh dung t«i sÏ minh ho¹ b»ng h×nh ¶nh c¸c trêng hîp

nµy:

New New head

Info Info Info Info

head Info 0 Info 0

H×nh Nót trë thµnh phÇn tö ®Çu tiªn míi

CÊu tróc d÷ liÖu mÉu víi C++

New New

Info Info Info Info

head Info 0 Info 0

H×nh Nót chÌn gi÷a hai nót kh¸c

New

New 0

Info Info Info Info Info

head Info 0

H×nh Nót trë thµnh phÇn tö cuèi cïng

IV.6.2. Xo¸ mét phÇn tö khái danh s¸ch

T¬ng tù nh thªm mét phÇn tö cã ba trêng hîp:

 Xo¸ phÇn tö ®Çu tiªn.

 Xo¸ phÇn tö gi÷a.

 Xo¸ phÇn tö ë cuèi danh s¸ch.

Info Info Del Info

head Info 0 Info 0

H×nh Xo¸ phÇn tö ®Çu tiªn

CÊu tróc d÷ liÖu mÉu víi C++

Info Info Info Del

Info 0 head Info 0

H×nh Xo¸ phÇn tö ë gi÷a

Info Info Info Del

head Info 0 Info 0

H×nh Xo¸ phÇn tö ë cuèi

IV.6.3. X©y dùng líp danh s¸ch liªn kÕt ®¬n mÉu

Ngoµi c¸c ph¬ng thøc c¬ b¶n nh thªm vµ xo¸ phÇn tö nh ®· tr×nh bµy ë trªn. Líp danh s¸ch liªn kÕt ®¬n mÉu cßn cã mét sè ph¬ng thøc vµ d÷ liÖu kh¸c ®Ó tiÖn cho viÖc qu¶n lý còng nh sö dông. §Æc biÖt lµ ph¬ng thøc Find() t×m kiÕm vµ Sort() s¾p xÕp, ®©y lµ hai ph¬ng thøc t×m kiÕm vµ s¾p xÕp ®¬n gi¶n, dÔ hiÓu. Nã ho¹t ®éng tèt víi d÷ liÖu c¬ b¶n nh: int, float, char,... cßn ®èi víi kiÓu d÷ liÖu tù ®Þnh nghÜa nÕu muèn dïng c¸c ph¬ng thøc nµy, ph¶i ®Þnh nghÜa c¸c to¸n tö: <, >, == cho kiÓu d÷ liÖu.

VÝ dô:

struct String

{

private:

char *txt;

public:

CÊu tróc d÷ liÖu mÉu víi C++

operator > (coust String & str);

operator < (coust String & str);

operator == (coust String & str);

};

/*SLIST*/ enum direct {ASC,DESC};//híng s¾p xÕp template class SList {

protected: struct Node { //®Þnh nghÜa mét phÇn tö cña danh s¸ch

T data; Node * next;

} * head,* tail,*current; size_t counter;

public: SList() {SetNull();} SList(const SList & sli) {SetNull();Copy(sli);} ~SList() { Erase();} int operator = (const SList & sli); int Append(const T & item); int Append(const SList & sli); int Insert(const T & item); int Insert(const SList & sli); void Erase(); int Delete(); int Get(T & item); size_t Count() { return counter;} int Next(); void ToHead() { current = head;} int AtTail() { return current==tail;} int Find(const T & item); void Sort(direct dir= ASC); private: void SetNull(); int Copy(const SList & sli);

}; //--------------------------------------------------- more information and additional documents connect with me here: http://facebook.com/ngphutien/ file đồ án kèm theo: Cau truc du lieu voi C++.rar 259 KB https://mega.co.nz/#!FgU3nAKa!-VgkoAGeGZtP3Q2LwN2LKMQXE4Uj67Q4nbAJrT4aGB8

*Líp danh s¸ch liªn kÕt ®¬n mÉu

template inline void SList::SetNull() {

head=tail= current=NULL; counter=0;

} //--------------------------------------------------- template int SList::Copy(const SList & sli) {

if(!sli.counter) return 1; Node * tmp=sli.head; do{ if(Append(tmp->data)) return 1; tmp=tmp->next; } while(tmp); current = sli->current;

return 0; } //-----to¸n tö g¸n-------------------------------------------- template int SList::operator = (const SList & sli) { Erase(); if(Copy(sli))return 1; return 0; } //------Ph¬ng thøc xo¸------------------------------------- template void SList::Erase() {

current=head; while(current){ head=current->next; delete current; current=head; } SetNull();

} //-------Thªm mét phÇn tö----------------------------------- template int SList::Append(const T & item) {

Node * tmp=new Node; if(!tmp) return 1; tmp->data=item; tmp->next=NULL;

CÊu tróc d÷ liÖu mÉu víi C++

if(!tail){ head=tail=tmp; current=tmp; } else{ tail->next=tmp; tail=tmp;

} counter++; return 0;

} //---------ghÐp danh s¸ch--------------------------------------- template int SList::Append(const SList & sli) {

const Node * tmp=sli.head; while(tmp){ if(Append(tmp->data)) return 1; tmp=tmp->next; } return 0;

} //--------chÌn mét phÇn tö-------------------------------------- template int SList::Insert(const T & item) {

if(!current) return 2; Node * tmp=new Node; if(!tmp) return 1; tmp->data=item; tmp->next=current->next; current->next=tmp; current=tmp; counter++; return 0;

} //-----chÌn mét danh s¸ch---------------------------------------- template int SList::Insert(const SList & sli) {

if(!current) return 2; Node * tmp; tmp=sli.head; while(tmp){

if(Insert(tmp->data)) return 1; tmp=tmp->next;

} return 0; }

CÊu tróc d÷ liÖu mÉu víi C++

//------Xo¸ mét phÇn tö------------------------------------------ template int SList::Delete() {

if(!current) return 2; if(current==head){ if(AtTail()){

delete current; SetNull(); return 0;

} else{

head=current->next; delete current; current=head;

}

} else{ Node * tmp=head; while(tmp->next != current) tmp=tmp->next; tmp->next=current->next; if(AtTail()) tail=tmp; delete current; current=tmp->next; } counter--; return 0;

} //-------LÊy gi¸ trÞ cña phÇn tö hiÖn t¹i------------------------------ template inline int SList::Get(T & item) {

if(!current) return 1; item =current->data; return 0;

} //------chuyÓn ®Õn phÇn tö kÕ tiÕp---------------------------------- template inline int SList::Next()

{ if(!current) return 2; current=current->next; return 0; }

//------Tim kiÕm--------------------------------------------- template int SList::Find(const T & item) {

Node * tmp=head;

CÊu tróc d÷ liÖu mÉu víi C++

while(tmp){

if(tmp->data==item){ current=tmp; return 1; }

tmp=tmp->next; } return 0;

} //-------S¾p xÕp-------------------------------------------- template void SList::Sort(direct dir=ASC) { Node *lap,*tmp; T buf; int exchange=0; ToHead(); while(current){

lap=current->next; buf=current->data; exchange=0; while(lap){

if((buf > lap->data && dir ==ASC) ||

(buf < lap->data && dir ==DESC)){ buf=lap->data; tmp=lap; exchange=1; } lap=lap->next;

}

if(exchange){

tmp->data=current->data; current->data=buf; } Next(); } ToHead(); }

CÊu tróc d÷ liÖu mÉu víi C++

IV.7. Danh s¸ch liªn kÕt ®«i

Danh s¸ch liªn kÕt ®«i chøa d÷ liÖu vµ c¸c liªn kÕt ®Õn phÇn tö kÕ tiÕp vµ ®Õn phÇn tö tríc nã. ¦u ®iÓm h¬n so víi liªn kÕt ®¬n lµ cã thÓ ®äc c¶ hai chiÒu, ®¬n gi¶n ho¸ viÖc qu¶n lý danh s¸ch lµm cho viÖc chÌn vµ xo¸ dÔ h¬n.

Info

Info 0 Info 0

CÊu tróc d÷ liÖu mÉu víi C++

IV.7.1. Thªm mét phÇn tö míi

Còng gièng nh danh s¸ch liªn kÕt ®¬n cã ba c¸ch thªm mét phÇn tö

míi:

 §Çu danh s¸ch.

 Gi÷a danh s¸ch.

 Cuèi danh s¸ch.

New

Info New 0 0 0 0 0 Info Info

Info 0 Info 0 Info 0

H×nh Thªm vµo ®Çu danh s¸ch

New

Info New 0 0 0 0 Info

Info 0 Info 0 Info 0 Info 0

H×nh Thªm vµo gi÷a hai phÇn tö

CÊu tróc d÷ liÖu mÉu víi C++

New

Info New 0 0 0 0 0 Info Info Info

Info 0 Info 0

H×nh Thªm vµo cuèi danh s¸ch

IV.7.2. Xo¸ mét phÇn tö

Cã ba trêng hîp xo¸ mét phÇn tö khái danh s¸ch liªn kÕt ®«i:

 PhÇn tö ®Çu tiªn.

 PhÇn tö gi÷a.

 PhÇn tö cuèi.

Info Del

Info 0 Info 0 Info 0 Info 0

H×nh Xo¸ phÇn tö ë ®Çu danh s¸ch

Info Del

Info 0 Info 0 Info 0 Info 0

H×nh Xo¸ phÇn tö ë gi÷a.

CÊu tróc d÷ liÖu mÉu víi C++

Info Del

Info 0 Info 0 Info 0 Info 0

H×nh Xo¸ phÇn tö ë cuèi danh s¸ch

IV.7.3. X©y dùng líp danh s¸ch liªn kÕt ®«i mÉu

/*DLIST*/ enum direct {ASC,DESC}; template class DList {

protected:

struct DNode { //®Þnh nghÜa phÇn tö cña danh s¸ch

T data; DNode * next,* prev; } *head,* tail,* current; size_t counter;

public:

DList() { SetNull();} DList(const DList & dls) { SetNull(); Copy(dls);} ~DList() {Erase();} int operator = (const DList & dls); int Append(const T & item); int Append(const DList & dls); int Insert(const T & item); int Insert(const DList & item); int InsertBefore(const T & item); int InsertBefore(const DList & dls); void Erase(); int Delete(); int Get(T & item); size_t Count(){ return counter;} int AtHead() ; int AtTail() ; void ToHead(){current=head;} void ToTail { current=tail;}

Còng gièng nh danh s¸ch liªn kÕt ®¬n hai ph¬ng thøc Find() vµ Sort() cÇn ph¶i ®îc ®Þnh nghÜa c¸c phÐp to¸n >, <, == ®èi víi c¸c kiÓu d÷ liÖu do ngêi sö dông ®Þnh nghÜa.

int Prev(); int Next(); int Find(const T & item); void Sort(direct dir=ASC);

private:

void SetNull(); int Copy(const DList & dls);

}; //------------------------------------------------------- template void DList::SetNull() {

head=tail=current=NULL; counter=0;

} //------------------------------------------------------- template int DList::Copy(const DList & dls) {

if(!dls.counter)return 1; const DNode *tmp=dls.head; do{ if(Append(tmp->data)) return 1; tmp=tmp->next; } while(tmp); current=dls.current; return 0;

} //------xo¸ danh s¸ch------------------------------------------- template void DList::Erase() {

ToHead(); while(current){

head=current->next; delete current; current=head;

} SetNull();

} //---------To¸n tö g¸n--------------------------------------------- template int DList::operator = (const DList & dls) {

Erase(); return Copy(dls);

} //------thªm mét phÇn tö--------------------------------------------

CÊu tróc d÷ liÖu mÉu víi C++

template int DList::Append(const T & item) {

DNode *tmp= new DNode; if(!tmp) return 1; tmp->data=item; tmp->next=NULL; tmp->prev=tail; if(!Count()) head=tail=current=tmp; else {

tail->next=tmp; tail=tmp; } counter++; return 0;

} //---------GhÐp mét danh s¸ch--------------------------------------------- template int DList::Append(const DList & dls) {

const DNode *tmp=dls.head; while(tmp){

if(Append(tmp->data)) return 1; tmp=tmp->next;

} return 0;

} //---------chÌn mét phÇn tö--------------------------------------------- template int DList::Insert(const T & item) {

if(!current)return 2; DNode *tmp=new DNode; if(!tmp)return 1; tmp->data=item; if(current==tail){

tmp->next=NULL; tmp->prev=tail; tail->next=tmp; tail=tmp;

} else {

current->next->prev=tmp; tmp->next=current->next; tmp->prev=current; current->next=tmp;

} counter++; return 0;

CÊu tróc d÷ liÖu mÉu víi C++

} //-------------chÌn mét danh s¸ch----------------------------------------- template int DList::Insert(const DList & dls) {

if(!current) return 2; const DNode *tmp=dls.tail; while(tmp){

if(Insert(tmp->data)) return 1; tmp=tmp->prev;

} return 0;

} //------------chÌn tríc vµo vÞ trÝ hiÖn t¹i------------------------------------------- template int DList::InsertBefore(const T & item) {

if(!current) return 2; DNode * tmp=new DNode; if(!tmp) return 1; tmp->data=item; if(current==head){ tmp->next=head; tmp->prev=NULL; head->prev=tmp; head=tmp;

} else{

current->prev->next=tmp; tmp->prev=current->prev; tmp->next=current; current->prev=tmp;

} counter++; return 0;

} //----------chÌn tríc vÞ trÝ hiÖn t¹i mét danh s¸ch------------------------ template int DList::InsertBefore(const DList & dls) {

if(!current) return 2; const DNode * tmp= dls.head; while(tmp){

if(InsertBefore(tmp->data))return 1; tmp=tmp->next;

} return 0;

} //--------Xo¸ mét phÇn tö---------------------------------------------

CÊu tróc d÷ liÖu mÉu víi C++

template int DList::Delete() {

if(!current)return 2; if(current==head){ if(!current->next){ delete current; SetNull();

} else{ head=current->next; head->prev=NULL; delete current; current=head;

}

} else{ if(current==tail){

if(!current->prev){ delete current; SetNull();

} else{ tail=current->prev; tail->next=NULL; delete current; current=tail;

}

} else{

DNode * tmp=current->next; current->prev->next=current->next; current->next->prev=current->prev; delete current; current=tmp;

}

} counter--; return 0;

}

//---------lÊy gi¸ trÞ ---------------------------------------------- template int DList::Get(T & item) {

if(!current)return 2; item=current->data; return 0;

}

CÊu tróc d÷ liÖu mÉu víi C++

//------------------------------------------------------- template inline int DList::AtHead() {

if(current==head) return 1; return 0;

}

//------------------------------------------------------- template inline int DList::AtTail() {

if(current==tail)return 1; return 0;

} //------------------------------------------------------- template inline int DList::Next() { if(!current)return 2; current=current->next; return 0; } //------------------------------------------------------- template inline int DList::Prev() {

if(!current)return 2; current=current->prev; return 0;

} //------------------------------------------------------- template int DList::Find(const T & item) {

const DNode *tmp= head; while(tmp){

if(tmp->data==item)return 1; tmp=tmp->next;

} return 0;

}

//------------------------------------------------------- template void DList::Sort(direct dir=ASC) {

T item; DNode *lap,*tmp; ToHead();

CÊu tróc d÷ liÖu mÉu víi C++

while(current){

// lap=current->next;

lap=head; while(lap!=current){

if((lap->data>current->data) && (dir==ASC) ||

(lap->datadata) && (dir==DESC)) break;

lap=lap->next;

}

if(lap!=current){

item=current->data; Delete(); tmp=current; current=lap; InsertBefore(item); current=tmp;

}

else Next();

}

CÊu tróc d÷ liÖu mÉu víi C++

IV.8. C©y nhÞ ph©n

C©y nhÞ ph©n gåm mét tËp h÷u h¹n c¸c nót (hay ®Ønh) vµ mét tËp h÷u h¹n c¸c c¹nh nèi c¸c cÆp nót víi nhau. Mçi nót cña c©y bao gåm th«ng tin víi mét liªn kÕt ®Õn phÇn tö bªn tr¸i vµ mét liªn kÕt víi phÇn tö bªn ph¶i.

 Trong ®ã cã mét nót ®Æc biÖt gäi lµ nót gèc (root) lµ nót kh«ng cã

c¹nh nµo híng tíi nã.

 C¸c nót l¸ (leaf) lµ nh÷ng nót ë ®ã kh«ng cã c¹nh nµo ®i ra.

infor Root node

infor Left subtree Right subtree

infor more information and additional documents connect with me here: http://facebook.com/ngphutien/ file đồ án kèm theo: Cau truc du lieu voi C++.rar 259 KB https://mega.co.nz/#!FgU3nAKa!-VgkoAGeGZtP3Q2LwN2LKMQXE4Uj67Q4nbAJrT4aGB8 infor infor infor Leaf node

CÊu tróc d÷ liÖu mÉu víi C++

 Nót truy cËp ®Õn nót kh¸c lµ nót bè (parent) vµ nót ®îc truy cËp

lµ nót con (child).

(subtree).

 Møc cña nót lµ sè cung ®i tõ gèc ®Õn l¸ céng thªm mét. Gèc cña

 Sè con cña mét nót cã bèn trêng hîp: cã hai con, kh«ng cã con

nµo (l¸), cã mét con tr¸i vµ mét con ph¶i.

IV.8.1. Gi¸ trÞ kho¸

 C¸c gi¸ trÞ kho¸ kh«ng trïng nhau.

 §èi víi mét nót: gi¸ trÞ kho¸ cña nã lín h¬n gi¸ trÞ kho¸ cña c¸c nót con tr¸i cña nã vµ ngîc l¹i nhá h¬n so víi c¸c nót con ph¶i cña nã.

IV.8.2. T×m kiÕm

CÊu tróc d÷ liÖu mÉu víi C++

ViÖc t×m kiÕm dùa trªn kho¸ chøa trong c¸c nót:

 NÕu kho¸ phï hîp víi kho¸ t×m kiÕm dõng --> ®· t×m thÊy.

 NÕu kho¸ nhá h¬n kho¸ cña nót --> t×m nót con tr¸i cña nã.

 NÕu kho¸ lín h¬n kho¸ cña nót --> t×m nót con ph¶i cña nã.

 Quay l¹i bíc mét.

ViÖc t×m kiÕm b¾t ®Çu tõ gèc vµ lÆp theo qu¸ tr×nh ë trªn cho ®Õn khi

t×m thÊy hoÆc nót con lµ rçng lµ kh«ng t×m thÊy.

N J

H O

M P I

R N

IV.8.3. Thªm mét nót míi

Thªm mét nót míi vµo c©y rçng nã trë thµnh gèc cña c©y. Qu¸ tr×nh t×m vÞ trÝ thÝch hîp thªm vµo c©y còng gièng nh viÖc t×m kiÕm. NÕu kho¸ cña nót míi kh«ng cã trong c©y. ViÖc t×m kiÕm kÕt thóc ë vÞ trÝ rçng (NULL) nµo ®ã. Khi ®ã ta nèi nót míi vµo vÞ trÝ nµy vµ trë thµnh l¸ cña c©y.

C C C C C

R R A R R A A

K K

CÊu tróc d÷ liÖu mÉu víi C++

IV.8.4. Xo¸ mét nót

Xo¸ mét nót trªn c©y nhÞ ph©n cã ba trêng hîp: nót cÇn xo¸ cã hai con, mét con vµ kh«ng cã con nµo. ViÖc xo¸ ph¶i ®¶m b¶o tÊt c¶ c¸c nót vÉn theo quy t¾c cña c©y nhÞ ph©n cã thø tù.

G M

D V H L

W A E R

H×nh xo¸ mét l¸

G M

D V L

W A E R

H×nh xo¸ nót cã mét con

D M

A V E L

W more information and additional documents connect with me here: http://facebook.com/ngphutien/ file đồ án kèm theo: Cau truc du lieu voi C++.rar 259 KB https://mega.co.nz/#!FgU3nAKa!-VgkoAGeGZtP3Q2LwN2LKMQXE4Uj67Q4nbAJrT4aGB8 R

H×nh xo¸ mét nót cã hai con

CÊu tróc d÷ liÖu mÉu víi C++

D R

A V E L

H×nh kÕt qu¶

(Postorder).

con ph¶i.

VÝ dô:

A C

F more information and additional documents connect with me here: http://facebook.com/ngphutien/ G file đồ án kèm theo: Cau truc du lieu voi C++.rar 259 KB E https://mega.co.nz/#!FgU3nAKa!-VgkoAGeGZtP3Q2LwN2LKMQXE4Uj67Q4nbAJrT4aGB8

H×nh minh ho¹

CÊu tróc d÷ liÖu mÉu víi C++

DuyÖt trung tè: ABCDEFG.

DuyÖt tiÒn tè: DBACFEG.

DuyÖt hËu tè: ACBEGFD.

enum TravType{inord,preord,postord};

//---------------------------------------- template struct TNode{

K key; D data; TNode *parent,*lchild,*rchild; TNode(const K & k,const D & d); TNode(const TNode & node) {NCopy(node);} void operator = (const TNode & node) {NCopy(node);} private: void NCopy(const TNode & node);

}; //----------------------------------------------- template TNode::TNode(const K & k,const D & d) {

key=k; data=d; parent=lchild=rchild=NULL;

} //----------------------------------------------- template void TNode::NCopy(const TNode & node) {

key=node.key; data=node.data; parent=node.parent; lchild=node.lchild; rchild=node.rchild;

} more information and additional documents connect with me here: http://facebook.com/ngphutien/ file đồ án kèm theo: Cau truc du lieu voi C++.rar 259 KB https://mega.co.nz/#!FgU3nAKa!-VgkoAGeGZtP3Q2LwN2LKMQXE4Uj67Q4nbAJrT4aGB8

IV.8.6. Líp d÷ liÖu mÉu

//----------------------------------------------- //TREE //----------------------------------------------- template class BTree {

protected:

TNode *root; int Copy(TNode* node); void Erase(TNode * node); void (*Travfunc)(const K & key,const D & data); void Inorder(TNode * node); void Preorder(TNode * node); void Postorder(TNode * node);

public:

BTree() {root=NULL;} BTree(const BTree & tree); ~BTree() {Erase(root);} int operator =(const BTree & tree); int Insert(const K & key,const D & data); int Delete(const K & key); void Traverse(void(*func)(const K & key, const D & data),const TravType &

ord=inord);

int Change(const K & key,const D & data); int Search(const K & key,D & data);

}; //--------------------------------------------------------------------- template int BTree ::Copy(TNode * node) {

if(node){ if(Insert(node->key,node->data))return 1; Copy(node->lchild); Copy(node->rchild);

} return 0;

} //--------------------------------------------------------------------- template void BTree::Erase(TNode * node) {

if(node){

Erase(node->lchild); Erase(node->rchild); delete node;

}

//---------------------------------------------------------------------

CÊu tróc d÷ liÖu mÉu víi C++

template BTree ::BTree(const BTree & tree) {

root=NULL; Copy(tree.root);

} //--------------------------------------------------------------------- template int BTree ::operator=(const BTree & tree) {

Erase(root); root=NULL; if(Copy(tree.root))return 1; return 0;

} //--------------------------------------------------------------------- template int BTree ::Insert(const K & key,const D & data) {

TNode* newnode= new TNode(key,data); if(!newnode) return 1; if(!root) root=newnode; else{ TNode * node=root; while(1){

if(node->key < newnode->key){ if(!node->rchild){

node->rchild=newnode; newnode->parent=node; return 0;

} else node=node->rchild; } else{ if(!node->lchild){ node->lchild=newnode; newnode->parent=node; return 0; } else node=node->lchild; }

}

} return 0;

}

//--------------------------------------------------------------------- template int BTree::Search(const K & key,D & data)

CÊu tróc d÷ liÖu mÉu víi C++

{ TNode * node=root; while(node){

if(key==node->key){ data=node->data; return 0;

} if(key>node->key) node=node->rchild; else node=node->lchild;

} return 1; } //--------------------------------------------------------------------- template int BTree ::Change(const K & key,const D & data) {

TNode * node=root; while(node){ if (key==node->key) break; if(key > node->key) node=node->rchild; else node=node->lchild;

} if(node) {

node->data= data; return 0;

} else return 1;

} //--------------------------------------------------------------------- template void BTree ::Traverse(void (*func)(const K & key,const D & data),const TravType & ord) {

Travfunc=func; switch(ord) {

case preord:

Preorder(root); break;

case postord:

Postorder(root); break;

default :

Inorder(root); break;

}

} //--------------------------------------------------------------------- template

CÊu tróc d÷ liÖu mÉu víi C++

void BTree ::Inorder(TNode * node) {

if(node){ Inorder(node->lchild); Travfunc(node->key,node->data); Inorder(node->rchild);

}

} //--------------------------------------------------------------------- template void BTree ::Preorder(TNode * node) {

if(node){ Travfunc(node->key,node->data); Preorder(node->lchild); Preorder(node->rchild);

}

} //--------------------------------------------------------------------- template void BTree ::Postorder(TNode * node) {

if(node){ Postorder(node->lchild); Postorder(node->rchild); Travfunc(node->key,node->data);

}

} //--------------------------------------------------------------------- template int BTree::Delete(const K & key) {

TNode * node=root; while (node){

if(key==node->key) break; if(key > node->key) node=node->rchild; else node=node->lchild;

} if(!node) return 1; if(!node->rchild){

if(!node->lchild){

if(node==root) root=NULL; else{ if(node->parent->lchild==node) node->parent->lchild=NULL; else node->parent->rchild=NULL; }

} else{

if(node==root) root=node->lchild;

CÊu tróc d÷ liÖu mÉu víi C++

else if(node->parent->lchild==node) node->parent->lchild=node->lchild; else node->parent->rchild=node->lchild; }

} else{ if(!node->lchild){

if(node==root) root=node->rchild; else{ if(node->parent->lchild==node)node->parent->lchild=node->rchild; else node->parent->rchild=node->rchild; }

} else{ TNode *temp=node->rchild; while(temp->lchild) temp=temp->lchild; if(temp->parent->lchild==temp) temp->parent->lchild=temp->rchild; else temp->parent->rchild=temp->rchild; node->key=temp->key; node->data=temp->data; if(temp->rchild) temp->rchild->parent=temp->parent; node=temp; } }

delete node; return 0;

}

CÊu tróc d÷ liÖu mÉu víi C++

IV.9. NhËn xÐt

Ph¬ng ph¸p biÓu diÔn mãc nèi nãi chung cång kÒnh h¬n ph¬ng ph¸p biÓu diÔn liªn kÕt vµ viÖc truy nhËp tíi c¸c phÇn tö còng chËm h¬n. Ngîc l¹i, viÖc cËp nhËt kh«ng yªu cÇu c¸c ®éng t¸c sao chÐp nªn Ýt tèn kÐm h¬n so víi ph¬ng ph¸p biÓu diÔn liªn tôc. Ta thêng chän ph¬ng ph¸p biÓu diÔn mãc nèi khi vÉn ®Ó cËp nhËt trë nªn quan träng h¬n vÊn ®Ò truy nhËp vµ ngîc l¹i.

CÊu tróc d÷ liÖu mÉu víi C++

PhÇn B

C¸c ch¬ng tr×nh øng dông

CÊu tróc d÷ liÖu mÉu víi C++

I. Qu¶n lý sinh viªn

Nh ®· biÕt, c«ng viÖc qu¶n lý sinh viªn lµ rÊt quan träng ®èi víi bÊt kú mét nhµ trêng nµo. §ã lµ c«ng viÖc phøc t¹p, ®ßi hái tÝnh chÝnh x¸c. Tuy nhiªn t«i kh«ng muèn ®i s©u vµo chi tiÕt, ch¬ng tr×nh t«i x©y dùng chØ mang tÝnh m« pháng, nhng vÉn mang ®Çy ®ñ nh÷ng chøc n¨ng c¬ b¶n cÇn thiÕt.

D÷ liÖu bao gåm: m· sè, hä tªn, ngµy sinh, líp, ®iÓm trung b×nh vµ

ghi chó.

Ch¬ng tr×nh nµy ®îc x©y dùng trªn hai líp cÊu tróc d÷ liÖu ®· ®îc thiÕt kÕ ë phÇn tríc ®ã lµ: Danh s¸ch liªn kÕt ®«i vµ ng¨n xÕp. Danh s¸ch liªn kÕt ®«i dïng ®Ó lu tr÷ vµ xö lý nh÷ng b¶n ghi, cßn ng¨n xÕp ®Ó lu tr÷ nh÷ng b¶n ghi ®· bÞ xo¸ vµ cã thÓ phôc håi khi cÇn thiÕt. Nh ®· biÕt ng¨n more information and additional documents connect with me here: http://facebook.com/ngphutien/ file đồ án kèm theo: Cau truc du lieu voi C++.rar 259 KB https://mega.co.nz/#!FgU3nAKa!-VgkoAGeGZtP3Q2LwN2LKMQXE4Uj67Q4nbAJrT4aGB8

CÊu tróc d÷ liÖu mÉu víi C++

xÕp ho¹t ®éng theo nguyªn t¾c “Vµo sau ra tríc” tøc lµ nã sÏ phôc håi nh÷ng b¶n ghi tuÇn tù theo thêi gian gÇn nhÊt.

Ch¬ng tr×nh cã mét sè chøc n¨ng chÝnh sau:

 Thªm míi mét b¶n ghi, sö dông ph¬ng thøc thªm danh s¸ch liªn kÕt ®«i (Append). ViÖc trïng khãa trong d÷ liÖu kh«ng ®îc phÐp. V× vËy, tríc khi thªm míi ph¶i kiÓm tra ®· cã kho¸ (m· sinh viªn) cã trong d÷ liÖu cha. NÕu cã ®a ra th«ng b¸o, ngîc l¹i b¶n ghi ®îc cËp nhËt trong danh s¸ch. Chøc nµy sö dông ph¬ng thøc t×m kiÕm (Find) cña danh s¸ch liªn kÕt ®«i.

 ChÌn mét b¶n ghi sö dông ph¬ng thøc chÌn (Insert) còng gièng nh viÖc thªm míi, tríc khi chÌn mét b¶n ghi ph¶i kiÓm tra ®· cã kho¸ nµy trong d÷ liÖu cha b»ng ph¬ng thøc t×m kiÕm Find.

 ChuyÓn ®Õn b¶n ghi kÕ tiÕp sö dông ph¬ng thøc di chuyÓn (Next). ViÖc di chuyÓn sÏ bÞ huû bá nÕu ®ang ë cuèi danh s¸ch. Ph¬ng thøc AtTail cho biÕt cã ph¶i ®ang ë cuèi danh s¸ch kh«ng.

 ChuyÓn ®Õn b¶n ghi tríc sö dông ph¬ng thøc Prev cña danh s¸ch liªn kÕt ®«i. ViÖc di chuyÓn kh«ng ®îc thùc hiÖn nÕu ®ang ë ®Çu danh s¸ch. Ph¬ng thøc AtHead cho biÕt cã ph¶i ®ang ë ®Çu danh s¸ch kh«ng.

 Trë vÒ b¶n ghi ®Çu tiªn sö dông ph¬ng thøc Tohead.

 Trë vÒ b¶n ghi cuèi sö dông ph¬ng thøc ToTail.

 Xo¸ b¶n ghi hiÖn t¹i sö dông ph¬ng thøc Delete. Ngoµi ra b¶n ghi bÞ xo¸ ®îc lu tr÷ vµo ng¨n xÕp b»ng ph¬ng thøc ®a vµo (Put). Giíi h¹n cña ng¨n xÕp b»ng 50. NÕu trµn ng¨n xÕp ®îc tù ®éng lµm rçng b»ng ph¬ng thøc Flush.

 Xo¸ hÕt danh s¸ch sö dông ph¬ng thøc Erase. C¸c b¶n ghi bÞ xo¸ lu

tr÷ vµo ng¨n xÕp.

 S¾p xÕp danh s¸ch t¨ng hoÆc gi¶m theo tªn sinh viªn sö dông ph¬ng

thøc Sort.

CÊu tróc d÷ liÖu mÉu víi C++

 T×m kiÕm mét b¶n ghi theo m· hoÆc theo tªn sinh viªn. ViÖc t×m kiÕm theo hä tªn cã thÓ sö dông ‘*’ ®Ó thay cho c¸c ký tù bÊt kú. ViÖc t×m kiÕm ®îc sö dông ph¬ng thøc Find.

 Phôc håi c¸c b¶n ghi ®· bÞ xo¸ sö dông ph¬ng thøc lÊy d÷ liÖu cña ng¨n xÕp (Get). ViÖc lÊy d÷ liÖu ra ®îc thùc hiÖn khi ng¨n xÕp kh«ng rçng, tøc ph¬ng thøc GetCount kh¸c kh«ng.

Ngoµi ra cßn cã mét sè chøc n¨ng kh¸c nh: më tÖp, ghi vµo tÖp, trî

gióp, th«ng b¸o, sö dông chuét,...

M· nguån cña ch¬ng tr×nh cã trong ®Üa mÒm kÌm theo bµi luËn v¨n

nµy.

void Menu(); void Show(); void Hide(); void Info(); int AddNew(); void Key(); void File(); void Open(int name=0); void SaveAs(); void Save(); void Find(); void SortAsc(); void SortDesc(); int Exit(); void Begin(); void Next(); void Prev(); void End(); void New(); void Ins(); void Del(); void Erase(); void Fresh(); void Act(); void Total(); int View(); char * Table( const SV & view ); char * Vert(char *txt,int len); void InitMouse(); void ShowMouse(); void HideMouse(); void SetMousePos(int x,int y); void MouseSpeed(int sp); void GetPos(int & x,int & y); more information and additional documents connect with me here: http://facebook.com/ngphutien/ file đồ án kèm theo: Cau truc du lieu voi C++.rar 259 KB https://mega.co.nz/#!FgU3nAKa!-VgkoAGeGZtP3Q2LwN2LKMQXE4Uj67Q4nbAJrT4aGB8

int Click(int & x,int & y); int Process(char ch); char Select(int & x,int & y); void Store(SV & sta); void Restore(); void Help();

DList list; SV tmp; const int STK_LEN = 50; Stack stack; char filename[50]; FILE *f; //--------------------------------------------------- void main() {

Menu(); InitMouse(); ShowMouse(); // HideMouse();

char ch; int flag=1; int x,y; while(flag) {

if(kbhit()) {

ch=getch(); ch=toupper(ch); if(Process(ch)) flag=0;//ket thuc chuong trinh

} if(Click(x,y)==1) {

ch=Select(x,y); if(Process(ch)) flag=0;

}

} //--------------------------------------------------- int Process(char ch) //tra lai 1 khi EXIT {

int flag=0; ch=toupper(ch); switch(ch) {

case 'V':

ch=View();

case 'B':

Begin();break;

case 'N':

Next();break;

case 'P':

Prev();break;

case 'E':

End();break;

case 'W':

New();break;

CÊu tróc d÷ liÖu mÉu víi C++

case 'I':

Ins();break;

case 'D':

Del();break;

case 'L':

Erase();break;

case 'R':

Restore();break;

case 'O':

File();break;

case 'S':

Save();break;

case 'A':

SaveAs();break;

case 'F':

Find();break;

case '0':

SortAsc();break;

case '1':

SortDesc();break; case 'H':Help();break; case 'X':

if(Exit()) flag=1; break;

}

return flag;

} void Store(SV & sta) {

if(stack.GetCount()==STK_LEN) stack.Flush(); if(strlen(sta.ma)) stack.Put(sta);

} //--------------------------------------------------- void Restore() {

SV sv; char txt[100]; if( !stack.GetCount())

msg="Khong con ban ghi nao de phuc hoi...";

if(stack.Get(sv))return; Input ques(10,10,"Ban co muon hoi phuc(C\\K) ");

strcat(ques.disp,sv.hoten); strcat(ques.disp,"(ma so: "); strcat(ques.disp,sv.ma); strcat(ques.disp,")"); char *str=ques.Text(1); if(str[0]=='c' || str[0]=='C') {

list.Append(sv); list.ToTail();

} else stack.Put(sv); ques.Hide(); Act();

} //---------------------------------------------------

CÊu tróc d÷ liÖu mÉu víi C++

void Key() {

char *txt; Display guide(10,2,"Chon cach tim kiem",LIGHTGREEN); Display guid1(10,3,"1: Theo ma hoc sinh",YELLOW); Display guid2(10,4,"2: Theo ten hoc sinh",YELLOW); guide.Show(); guid1.Show(); guid2.Show(); Display choice(10,6,"Chon : ",MAGENTA); choice.Show(); char ch='0'; int mx,my; while(ch=='0') {

if(kbhit()){ch=getch();ch=toupper(ch);} if(Click(mx,my))

{

my-=2; if((my==3)&&(mx>10)&&(mx<10+strlen("1: Theo ma hoc sinh")))

ch='1';

if((my==4)&&(mx>10)&&(mx<10+strlen("1: Theo ten hoc sinh")))

ch='2'; }

} txt[0]=ch; txt[1]='\0'; strcat(choice.disp,txt); choice.Show();

Input input(10,9,"La : ",LIGHTCYAN); if(ch=='1') {

txt=input.Text(); strcpy(tmp.ma,txt);

} if(ch=='2')

{

Display guid3(10,8,"Co the dung '*' cho ki tu bat ky",CYAN); guid3.Show(); txt=input.Text(); strset(tmp.ma,NULL); strcpy(tmp.hoten,txt);

} clrscr();

} //--------------------------------------------------- void Find() {

clrscr(); Hide(); Key(); if(!strlen(tmp.ma) && !strlen(tmp.hoten)){

Act(); return;

} if(list.Find(tmp)) {

CÊu tróc d÷ liÖu mÉu víi C++

Act(); return;

} else{

msg=" Khong tim thay !"; list.ToHead(); Act();

}

} //--------------------------------------------------- void SortAsc() {

if(!list.Count())return; Hide(); clrscr(); list.Sort(); list.ToHead(); Act();

} //--------------------------------------------------- void SortDesc() {

if(!list.Count()) return; list.Sort(DESC); Hide(); clrscr(); list.ToHead(); Act();

} //--------------------------------------------------- void Begin() {

Hide(); list.ToHead(); Act();

} //--------------------------------------------------- void Next() { // Hide();

if(list.AtTail()) {

msg="Da den cuoi danh sach! "; Show(); return;

} list.Next(); Act();

} //--------------------------------------------------- void Prev() {

Hide(); if(list.AtHead()) { msg="Da den dau danh sach! "; Show();

CÊu tróc d÷ liÖu mÉu víi C++

return; } list.Prev(); Act();

} //--------------------------------------------------- void End() {

Hide(); list.ToTail(); Act();

} //--------------------------------------------------- int AddNew() {

char * txt;//[100]; txt=nhapma.Text(); if(!txt) return 1; strncpy(tmp.ma,txt,MA_LEN-1); if(list.Find(tmp)) {

msg="Da co ma hoc sinh nay trong du lieu! "; return 1;

} txt=nhapten.Text(); strncpy(tmp.hoten,txt,TEN_LEN-1); txt=nhaplop.Text(); strncpy(tmp.lop,txt,LOP_LEN-1); txt=nhapdiem.Text(); strncpy(tmp.dtb,txt,DTB_LEN-1); txt=nhapngay.Text(); strncpy(tmp.ngaysinh,txt,NGAY_LEN-1); txt=nhapchu.Text(); strncpy(tmp.ghichu,txt,GHI_LEN-1); return 0;

}

//--------------------------------------------------- void New() {

Hide(); if(AddNew()){ clrscr(); Act(); return;

} if(!strlen(tmp.ma)) {

Act(); return;

} list.Append(tmp); list.ToTail(); Act(); Total();

} //---------------------------------------------------

CÊu tróc d÷ liÖu mÉu víi C++

void Ins() {

Hide(); if(AddNew()) {

clrscr(); Act(); return;

} if(!strlen(tmp.ma)) {

Act(); return;

} list.Insert(tmp); Act(); Total();

} //--------------------------------------------------- void Del() {

Hide(); char ques[100]; strcpy(ques,"Ban co muon xoa(C\K) :"); strcat(ques,tmp.hoten); strcat(ques,"( "); strcat(ques,tmp.ma); strcat(ques," )"); Input input(10,10,ques); char *txt=input.Text(1); if(txt[0]=='c' || txt[0]=='C') { Store(tmp); list.Delete(); } clrscr(); Act();

// Total(); } //--------------------------------------------------- void Erase() {

Hide(); Input flu(10,10,"Ban muon xoa het?(C/K) ",RED); char *txt=flu.Text(1); strcat(flu.disp,txt); flu.Hide(); strcpy(flu.disp,flu.caption); if(*txt=='c' || *txt=='C') {

list.ToHead(); while(!list.Get(tmp)) {

stack.Put(tmp); list.Next();

} list.Erase();

CÊu tróc d÷ liÖu mÉu víi C++

tongso="0"; Fresh(); Show(); Total();

}

} //---------------------------------------------------

CÊu tróc d÷ liÖu mÉu víi C++

II. Thèng kª tõ tiÕng ViÖt

Trong c¸c nghµnh khoa häc, kinh tÕ, còng nh ®èi víi tin häc. Thèng kª lµ mét c«ng viÖc v« cïng quan träng, viÖc thèng kª cã bao nhiªu tõ tiÕng ViÖt còng nh sè lÇn xuÊt hiÖn cña nã kh«ng chØ cã Ých cho c¸c nhµ ng«n ng÷ häc, mµ cßn gióp cho nh÷ng ngêi lµm tin häc cã ®îc c¸ch m· ho¸ tèi u vµ phï hîp nhÊt.

Trong ch¬ng tr×nh. T«i dùa vµo tÝnh ®¬n ©m tiÕt cöa tiÕng ViÖt ®Ó lo¹i bá nh÷ng tõ kh«ng phï hîp. Sau khi thèng kª cã thÓ t×m kiÕm vµ lo¹i bá nèt nh÷ng tõ kh«ng ph¶i lµ tiÕng ViÖt. KÕt qu¶ ®îc lu vµo ®Üa theo thø tù b¶ng ch÷ c¸i hoÆc theo sè lÇn xuÊt hiÖn.

C©y nhÞ ph©n lµ cÊu tróc d÷ liÖu cã tèc ®é t×m kiÕm nhanh nhÊt, rÊt thÝch hîp ®Ó lu tr÷ mét lîng d÷ liÖu lín. Danh s¸ch liªn kÕt ®¬n ®îc sö dông ®Ó s¾p xÕp c¸c tõ theo thø tù gi¶m dÇn. KÕt qu¶ thèng kª ®îc lu vµo tÖp ®Ó nghiªn cøu.

ThuËt to¸n, khi ph©n t¸ch mét tõ vµ ph©n tÝch tõ ®ã tho¶ m·n lµ tõ tiÕng ViÖt tõ ®ã sÏ tiÕp tôc ®îc xö lý nh sau: KiÓm tra trong c©y nhÞ ph©n ®· cã tõ nµy cha b»ng ph¬ng thøc Search. NÕu cã sÏ t¨ng sè lÇn xuÊt hiÖn cña tõ nµy lªn mét b»ng ph¬ng thøc Change, ngîc l¹i nÕu cha cã th× thªm tõ nµy vµo c©y nhÞ ph©n vµ g¸n sè lÇn xuÊt hiÖn cña tõ nµy b»ng mét b»ng ph¬ng thøc Append. Sau khi thèng kª cã thÓ xem kÕt qu¶ vµ nh÷ng tõ nµo kh«ng phï hîp cã thÓ xo¸ b¨ng c¸c ph¬ng thøc duyÖt c©y nhÞ ph©n vµ ph¬ng thøc Delete.ViÖc ghi kÕt qu¶ vµo tÖp theo hai c¸ch. C¸ch thø nhÊt ghi sè tõ xuÊt hiÖn theo thø tù ch÷ c¸i b»ng ph¬ng thøc duyÖt trung thø tù. C¸ch thø hai g¸n kÕt qu¶ vµo mét danh s¸ch liªn kÕt ®¬n, sau ®ã s¾p

CÊu tróc d÷ liÖu mÉu víi C++

xÕp theo thø tù gi¶m dÇn theo sè lÇn xuÊt hiÖn b»ng ph¬ng thøc Sort vµ lu vµo tÖp.

Ngoµi ra cßn cã mét sè chøc n¨ng kh¸c nh: më tÖp, ghi vµo tÖp, trî

gióp, th«ng b¸o, sö dông chuét,...

M· nguån cña ch¬ng tr×nh cã trong ®Üa mÒm kÌm theo bµi luËn v¨n

nµy

//------------------------------------------------------ void Menu(); void Open(int name=0); void Save(); void TravAlpha(const String & txt,const size_t & num); void SaveFre(const String & txt,const size_t & num); void SaveFre(); void TravFre(const String & txt,const size_t & num); void Find(); void Del(); void View(); void TravView(const String & txt,const size_t & num); int Exit(); void InitMouse(); void ShowMouse(); void HideMouse(); void SetMousePos(int x,int y); void MouseSpeed(int sp); void GetPos(int & x,int & y); int Click(int & x,int & y); int Process(char ch); char Select(int & x,int & y); void Help(); void File(); BTree tree; SList list; char filename[100];

//------------------------------------------ void main() {

Menu(); InitMouse(); ShowMouse(); // HideMouse();

char ch; int flag=1; int x,y; while(flag) {

if(kbhit()) {

ch=getch(); ch=toupper(ch); if(Process(ch)) flag=0;//ket thuc chuong trinh

} if(Click(x,y)==1) {

ch=Select(x,y); if(Process(ch)) flag=0;

}

} //--------------------------------------------------- int Process(char ch) {

ch=toupper(ch); switch(ch) {

case 'O': File();clrscr();break; case 'S': Save();clrscr();break; case 'V': View();clrscr();break; case 'F': Find();clrscr();break; case 'D': Del(); clrscr();break; case 'H': Help();break; case 'E': if(Exit()) return 1;

} return 0;

} //--------------------------------------------------- void Open(int name) {

clrscr(); Input esc(3,5,"Ban muon dung chuong trinh ?(C/K) ",YELLOW); Display title(10,4,"Thong ke tu",LIGHTGREEN); title.Show(); ActDisp dict(10,7,"Tu dien : "); ActDisp cou(10,8,"So tu da xu ly: "); ActDisp comp(10,9,"Hoan thanh : ");

if(!name) { Input path(10,4," Ten tep:",YELLOW); char *txt=path.Text(); strcat(path.disp,txt); strcpy(filename,txt); } FILE *f,*ftmp; ftmp=fopen("temp.dat","wb"); if((f=fopen(filename,"rb"))==NULL) {

Msg msg(10,7,""); msg="Khong mo duoc tep !"; clrscr(); return;

} Display guide(10,14,"An ESC de thoat",YELLOW);

CÊu tróc d÷ liÖu mÉu víi C++

guide.Show();

const size_t MAXLEN=9; const size_t MAXBUF=3000;

String tmp(MAXLEN); char buf [ MAXBUF ];

size_t pos,numread,count; int flag=0,l=0; unsigned long sum=0;//,amount=0;

char *p;

fseek(f,sizeof(char),SEEK_END); unsigned long filesize; filesize = ftell(f); rewind(f);

while (!feof(f)) {

flag=1;pos=0; numread=fread(buf,sizeof(char),MAXBUF,f);

while(pos

p=(char *)tmp;l=0;count=0; if(buf[pos]==10) { pos++; continue; } while(IsChar(buf[pos]) && pos

tree.Change(tmp,++count);

else{

tree.Insert(tmp,1); String test;//err la bien kiem tra if(test.Err()){

Msg over(5,10,"",LIGHTRED); over="Tran bo nho"; fseek(f,filesize, SEEK_SET); break;

}

fwrite(tmp,sizeof(char),l,ftmp); fputc(' ',ftmp);

CÊu tróc d÷ liÖu mÉu víi C++

sum++; flag=1; } else if(flag) {

fputc(10,ftmp); flag=0;

}

pos++;

cou=sum; comp = ftell(f)*100/filesize; dict=tree.Count(); char ch; ch='\0'; if(kbhit()){

ch=getch(); if(ch==27) ch='C';

} int x,y; if(Click( x, y)){

// Display guide(10,14,"An ESC de thoat",YELLOW);

y-=2; if((y==14) && ((x>10) &&(x< 10+strlen("An ESC de thoat"))))

ch='C';

}

if(ch=='C') {

char * choice=esc.Text(1); if(choice[0]=='C'||choice[0]=='c') {

fseek(f,filesize, SEEK_SET); esc.Hide(); break;

} esc.Hide();

}

fclose(f); fclose(ftmp); Msg suc(10,20,"",YELLOW); suc= " Da hoan thanh ";

} //-------------------------------------- FILE *f; //-------------------------------------- void Save() {

Input path(10,5,"Ghi vao tep: "); char *txt=path.Text(); if((f=fopen(txt,"wb"))==NULL) {

Msg msg(10,7,""); msg="Khong mo duoc tep! "; return;

CÊu tróc d÷ liÖu mÉu víi C++

}

Display guide(10,2,"Chon mot trong hai cach ghi sau:",LIGHTGREEN); Display guid1(10,3,"1: Ghi theo thu tu chu cai",YELLOW); Display guid2(10,4,"2: Ghi theo so lan xuat hien",YELLOW); Display esc(3,2," An ESC de thoat",YELLOW); esc.Show(); clrscr(); guide.Show(); guid1.Show(); guid2.Show(); Display choice(10,6,"Chon : ",MAGENTA); choice.Show(); char ch='0'; int mx,my; while(ch=='0') {

if(kbhit()){ch=getch();ch=toupper(ch);} if(Click(mx,my))

{

my-=2; if((my==3)&&(mx>10)&&(mx<10+strlen("1: Ghi theo thu tu chu

cai"))) ch='1';

if((my==4)&&(mx>10)&&(mx<10+strlen("2: Ghi theo so lan xuat

hien"))) ch='2';

if((my==2)&&(mx>3)&&(mx<10+strlen("an ESC de thoat"))) ch='2'; }

} txt[0]=ch; txt[1]='\0'; strcat(choice.disp,txt); choice.Show();

Input input(10,9,"La : ",LIGHTCYAN);

if(txt[0]=='1') tree.Traverse(TravAlpha); if(txt[0]=='2') SaveFre();

Msg succ(10,20,"",YELLOW); succ="Da hoan thanh"; fclose(f); list.Erase();

} //---------------------------------------------------- int overflow; void SaveFre() {

Freq tmp; char str[10]; overflow=0; tree.Traverse(TravFre); ActDisp warning(10,14,"",YELLOW); ActDisp over(10,15,"Trao bo nho",YELLOW); if(list.Count() !=tree.Count()) {

int num=tree.Count()-list.Count(); if(overflow) over.Show(); warning.CharNum("Du lieu co the bi mat khoang: ",num);

} list.Sort(ASC);

CÊu tróc d÷ liÖu mÉu víi C++

list.ToHead(); if(!list.Count()) return ;

while(1){

if(list.Get(tmp))break; fputs(tmp.txt,f); ltoa(tmp.count,str,10); fputs(" ",f); fputs(str,f); fputc(10,f);

}

} //---------------------------------------------------- void TravFre(const String & str,const size_t & num) {

Freq fre(str,num); if(!fre.Err())return; fre.txt=str; fre.count=num; list.Append(fre);

} //---------------------------------------------------- void TravAlpha(const String & str,const size_t & num) {

static char tmp[10]; long l=long(num); ltoa(l,tmp,10); fputs(str,f); fputs(" ",f); fputs(tmp,f); fputc(10,f);

} //---------------------------------------------------- void Del() {

clrscr(); Msg msg(10,7,"",LIGHTCYAN); Input input(10,5,"Nhap tu can xoa: "); String str; str=input.Text();

// strcat(input.disp,str);

if( !tree.Delete(str)) msg="Da xoa..."; else msg="Khong xoa duoc";

} //-------------------------------------- void Find() {

clrscr(); Input input(10,5,"Tim tu: "); ActDisp act(10,7,"So lan xuat hien: "); Msg msg(10,8,"",MAGENTA); char * txt=input.Text(); size_t num; String str; str=txt; if(tree.Search(str,num)) msg="Khong tim thay"; else{

CÊu tróc d÷ liÖu mÉu víi C++

act=num; msg=" ";

}

} //--------------------------------------

CÊu tróc d÷ liÖu mÉu víi C++

KÕt luËn

Cïng víi sù ph¸t triÓn m¹nh mÏ cña c«ng nghÖ th«ng tin, th× cÊu tróc d÷ liÖu nh lµ nÒn t¶ng cña sù ph¸t triÓn nµy. Víi sù u viÖt cña ph¬ng ph¸p lËp tr×nh híng ®èi tîng lµ tÝnh kÕ thõa vµ sù linh ®éng ®èi víi c¸c kiÓu d÷ liÖu kh¸c nhau cña c¸c líp mÉu. C¸c líp cÊu tróc d÷ liÖu mÉu cña C++ rÊt phï hîp ®Ó x©y dùng c¸c ch¬ng tr×nh lín vµ ®a d¹ng.

C¸c líp cÊu tróc d÷ liÖu mÉu: ng¨n xÕp, hµng ®îi, hµng quay trßn, danh s¸ch liªn kÕt ®¬n, liªn kÕt ®«i vµ c©y nhÞ ph©n mµ t«i ®· x©y dùng ë trªn. T«i hy väng c¸c líp cÊu tróc d÷ liÖu mÉu nµy ®îc sö dông hoÆc cã Ých cho nh÷ng ngêi lËp tr×nh. Tuy r»ng ®· cè g¾ng x©y dùng x©y dùng c¸c líp mét c¸ch tæng qu¸t vµ chi tiÕt nhÊt nhng do thêi gian vµ kh¶ n¨ng cßn h¹n chÕ nªn kh«ng tr¸nh khái nh÷ng thiÕu sãt. Ngoµi c¸c kiÓu cÊu tróc ®· tr×nh bµy cßn cã mét sè kiÓu cÊu tróc d÷ liÖu kh¸c: b¶ng b¨m, c©y n ph©n, ... mµ trong khu«n khæ cña mét bµi luËn v¨n tèt nghiÖp t«i kh«ng cã ®iÒu kiÖn ®Ó tr×nh bµy. T«i sÏ cè g¾ng hoµn thiÖn vµ nghiªn cøu ®Ó lµm giµu thªm kiÕn thøc cña m×nh. Vµ t«i hy väng trong t¬ng lai cã thÓ x©y dùng ®îc c¸c ch¬ng tr×nh cã gi¸ trÞ sö dông thùc tÕ, gãp phÇn thóc ®Èy sù ph¸t triÓn nÒn c«ng nghÖ th«ng tin níc ta.

CÊu tróc d÷ liÖu mÉu víi C++

Tµi liÖu tham kh¶o

[1] J.COURTIN & I.KOWARSKI NhËp m«n thuËt to¸n vµ cÊu tróc d÷ liÖu (TËp II), ViÖn tin häc – Khoa häc ViÖt Nam 1993

[3] TrÇn V¨n L¨ng - LËp tr×nh híng ®èi tîngC++ , NXB thèng kª

[4] nguyÔn cÈn - C Tham kh¶o toµn toµn diÖn, NXB §ång Nai 1996

[5] ng« trung viÖt - Ng«n ng÷ lËp tr×nh C & C++, nhµ xuÊt b¶n Giao th«ng vËn t¶i 1996

[6] scoot robert ladd - C++ Components And Algosithms. M&T Books 1994

[7] scoot robert ladd - C++ Template And Tools. M&T Books 1995

CÊu tróc d÷ liÖu mÉu víi C++

Luận văn tốt nghiệp: Cấu trúc dữ liệu mẫu với C++ - ĐHDL Đông Đô

Lêi c¶m ¬n

Hµ néi th¸ng 6 n¨m 2000

Môc lôc

Lêi c¶m ¬n PhÇn A Ch¬ng I. Ng«n ng÷ C++ vµ lËp tr×nh híng ®èi tîng

...

PhÇn B

C¸c ch¬ng tr×nh øng dông

KÕt luËn

Tµi liÖu tham kh¶o

Có thể bạn quan tâm

Tài liêu mới

Giới thiệu

Về chúng tôi

Việc làm

Quảng cáo

Liên hệ

Chính sách

Thoả thuận sử dụng

Chính sách bảo mật

Chính sách hoàn tiền

DMCA

Hỗ trợ

Hướng dẫn sử dụng

Đăng ký tài khoản VIP

093 303 0098

support@tailieu.vn

Phương thức thanh toán

Theo dõi chúng tôi

Facebook

Youtube

TikTok

Luận văn tốt nghiệp: Cấu trúc dữ liệu mẫu với C++ - ĐHDL Đông Đô

Lêi c¶m ¬n

Hµ néi th¸ng 6 n¨m 2000

Môc lôc

Lêi c¶m ¬n PhÇn A Ch­¬ng I. Ng«n ng÷ C++ vµ lËp tr×nh h­íng ®èi t­îng

...

PhÇn B

C¸c ch­¬ng tr×nh øng dông

KÕt luËn

Tµi liÖu tham kh¶o

Có thể bạn quan tâm

Tài liêu mới

AI tóm tắt

Giới thiệu tài liệu

Đối tượng sử dụng

Từ khoá chính

Nội dung tóm tắt

Giới thiệu

Về chúng tôi

Việc làm

Quảng cáo

Liên hệ

Chính sách

Thoả thuận sử dụng

Chính sách bảo mật

Chính sách hoàn tiền

DMCA

Hỗ trợ

Hướng dẫn sử dụng

Đăng ký tài khoản VIP

093 303 0098

support@tailieu.vn

Phương thức thanh toán

Theo dõi chúng tôi

Facebook

Youtube

TikTok

Lêi c¶m ¬n PhÇn A Ch¬ng I. Ng«n ng÷ C++ vµ lËp tr×nh híng ®èi tîng

C¸c ch¬ng tr×nh øng dông