Thiết kế trang và lập trình - Tổng lượng tri thức cốt lõi và thực hành

0өc Lөc

1 Cҩu trúc dӳ liӋu ...............................................................................................................1

1.1 Cҩu trúc dӳ liӋu là gì? ...............................................................................................2

1.2 Cҩu trúc dӳ liӋu cѫ sӣ ...............................................................................................3

1.2.1 KiӇu dӳ liӋu cѫ sӣ ..............................................................................................3

1.2.2 KiӇu có cҩu trúc .................................................................................................4

1.2.3 KiӇu dӳ liӋu trӯu tѭӧng ......................................................................................7

1.3 Cҩu trúc dӳ liӋu hѭӟng vҩn ÿӅ...................................................................................8

1.3.1 Cҩu trúc danh sách .............................................................................................8

1.3.2 Ngăn xӃp..........................................................................................................10

1.3.3 Hàng ÿӧi ..........................................................................................................11

1.3.4 Cҩu trúc cây .....................................................................................................12

1.3.5 Băm .................................................................................................................17

2 Thuұt toán......................................................................................................................23

2.1 Cѫ sӣ vӅ thuұt toán..................................................................................................24

2.1.1 Thuұt toán là gì?...............................................................................................24

2.1.2 Thuұt toán và cҩu trúc dӳ liӋu...........................................................................26

2.2 Các thuұt toán .........................................................................................................30

2.2.1 Thuұt toán duyӋt...............................................................................................30

2.2.2 Thuұt toán sҳp xӃp............................................................................................34

2.2.3 Thuұt toán ÿӋ qui..............................................................................................49

2.2.4 Xӱ lí xâu kí tӵ ..................................................................................................51

2.2.5 Xӱ lí tӋp ...........................................................................................................55

2.2.6 VӁ hình ............................................................................................................63

2.2.7 Ĉӗ thӏ...............................................................................................................67

2.2.8 Tính toán sӕ .....................................................................................................71

2.2.9 Thuұt toán ÿӕi sánh ..........................................................................................78

2.2.10 Thuұt toán xҩp xӍ và xác suҩt ........................................................................82

2.3 Ĉánh giá thuұt toán .................................................................................................87

2.3.1 Ĉánh giá theo ÿӝ phӭc tҥp tính toán..................................................................87

2.3.2 Ĉánh giá theo tính hӧp lӋ..................................................................................88

2.3.3 Ĉánh giá theo biӇu diӉn....................................................................................88

2.4 Cách thiӃt kӃ thuұt toán...........................................................................................89

3 ThiӃt kӃ trong ................................................................................................................95

3.1 ThiӃt kӃ trong là gì? ................................................................................................96

3.1.1 Mөc ÿích cӫa thiӃt kӃ trong và nhӳng ÿLӇm cҫn lѭu ý .......................................96

3.1.2 Thӫ tөc thiӃt kӃ trong .......................................................................................97

3.2 Phân hoҥch và cҩu trúc chӭc năng .........................................................................101

3.2.1 Các ÿѫn vӏ cӫa viӋc phân hoҥch và cҩu trúc chӭc năng...................................101

3.2.2 Các thӫ tөc phân hoҥch và cҩu trúc chӭc năng................................................103

3.2.3 Phѭѫng pháp thiӃt kӃ có cҩu trúc....................................................................109

3.3 ThiӃt kӃ dӳ liӋu vұt lí ............................................................................................112

3.3.1 Thӫ tөc thiӃt kӃ dӳ liӋu vұt lí..........................................................................112

3.3.2 Tә chӭc dӳ liӋu vұt lí......................................................................................117

3.4 ThiӃt kӃ vào ra chi tiӃt...........................................................................................120

3.4.1 ThiӃt kӃ dӳ liӋu vào chi tiӃt ............................................................................120

3.4.2 ThiӃt kӃ màn hình...........................................................................................123

2 Chѭѫng 1 Cҩu trúc dӳ liӋu

3.4.3 ThiӃt kӃ dӳ liӋu ÿѭa ra chi tiӃt ........................................................................132

3.5 Tҥo ra và dùng lҥi các bӝ phұn ..............................................................................136

3.5.1 Khái niӋm vӅ tҥo ra và dùng lҥi các bӝ phұn...................................................136

3.5.2 Dùng gói phҫn mӅm .......................................................................................136

3.6 Tҥo ra tài liӋu thiӃt kӃ trong...................................................................................137

3.6.1 Tә chӭc tài liӋu thiӃt kӃ trong .........................................................................137

3.6.2 Các ÿLӇm cҫn lѭu ý khi tҥo ra tài liӋu thiӃt kӃ trong ........................................139

3.6.3 KiӇm ÿLӇm thiӃt kӃ .........................................................................................140

4 ThiӃt kӃ chѭѫng trình...................................................................................................140

4.1 Mөc ÿích và nhiӋm vө cӫa thiӃt kӃ chѭѫng trình ...................................................144

4.1.1 Mөc ÿích cӫa thiӃt kӃ chѭѫng trình.................................................................144

4.1.2 NhiӋm vө thiӃt kӃ chѭѫng trình ......................................................................145

4.2 ThiӃt kӃ có cҩu trúc cho chѭѫng trình....................................................................148

4.2.1 Thӫ tөc thiӃt kӃ có cҩu trúc.............................................................................148

4.2.2 Các kƭ thuұt phân hoҥch mô ÿun ÿLӇn hình......................................................151

4.2.3 Tiêu chí cho viӋc phân hoҥch mô ÿun.............................................................160

4.2.4 Phân hoҥch chѭѫng trình ................................................................................171

4.3 Tҥo ra ÿһc tҧ mô ÿun và ÿһc tҧ kiӇm thӱ................................................................173

4.3.1 Tҥo ra ÿһc tҧ mô ÿun ......................................................................................173

4.3.2 Tҥo ra ÿһc tҧ kiӇm thӱ ....................................................................................175

4.4 Tҥo ra tài liӋu thiӃt kӃ chѭѫng trình.......................................................................177

4.4.1 Tҥo ra tài liӋu thiӃt kӃ chѭѫng trình và nӝi dung.............................................177

4.4.2 Nhӳng ÿLӇm cҫn lѭu ý khi tҥo ra tài liӋu thiӃt kӃ chѭѫng trình........................179

4.4.3 Hӑp kiӇm ÿLӇm thiӃt kӃ ..................................................................................179

5 Thӵc hiӋn chѭѫng trình................................................................................................183

5.1 Lұp trình ...............................................................................................................184

5.1.1 Mô thӭc lұp trình............................................................................................184

5.1.2 Phong cách lұp trình .......................................................................................185

5.1.3 Dùng bӝ xӱ lí ngôn ngӳ..................................................................................186

5.1.4 Môi trѭӡng lұp trình .......................................................................................187

5.2 KiӇm thӱ...............................................................................................................189

5.2.1 Tәng quan vӅ kiӇm thӱ...................................................................................189

5.2.2 KiӇm thӱÿѫn vӏ .............................................................................................190

5.2.3 KiӇm thӱ tích hӧp...........................................................................................190

5.2.4 KiӇm thӱ hӋ thӕng..........................................................................................195

5.2.5 Các kiӇm thӱ khác..........................................................................................197

5.2.6 KӃ hoҥch và nhiӋm vө kiӇm thӱ .....................................................................197

6 Cұp nhұt vұn hành và phát triӇn hӋ thӕng.....................................................................204

6.1 ThiӃt kӃ chѭѫng trình............................................................................................205

6.1.1 ThiӃt kӃ chѭѫng trình hѭӟng ÿӕi tѭӧng ..........................................................205

1 &ҩu trúc dӳ liӋu

0өc ÿích cӫa chѭѫng

ViӋc chӑn cҩu trúc dӳ liӋu thích hӧp nhҩt và thӫ tөc mô

Wҧ dӳ liӋu là mҩu chӕt ÿӇ tҥo ra chѭѫng trình hiӋu quҧ,

GӉ hiӇu.

Chѭѫng này mô tҧ các cҩu trúc dӳ liӋu ÿa dҥng bҥn cҫn

Qҳm ÿѭӧc xem nhѭ bѭӟc ÿҫu tiên ÿӇ hӑc lұp trình.

• HiӇu cách phân loҥi các cҩu trúc dӳ liӋu ÿa dҥng

‚ HiӇu các kiӇu dӳ liӋu cѫ sӣ thông dөng nhҩt và

Pҧng dӳ liӋu

ƒ HiӇu các ÿһc trѭng và cѫ chӃ cӫa cҩu trúc dӳ liӋu

Kѭӟng vҩn ÿӅÿѭӧc dùng ÿӇ giҧi quyӃt các bài toán

ÿһc biӋt, cNJng nhѭ cách dùng cҩu trúc dӳ liӋu cѫ sӣ

cho viӋc cài ÿһt chѭѫng trình

2 Chѭѫng 1 Cҩu trúc dӳ liӋu

1.1 &ҩu trúc dӳ liӋu là gì?

7ұp các dӳ liӋu cùng mӝt loҥi ÿѭӧc máy tính xӱ lí ÿѭӧc gӑi là "kiӇu dӳ liӋu." Trong giai ÿRҥn

thiӃt kӃ chѭѫng trình, cách thӭc dӳ liӋu nên ÿѭӧc biӇu diӉn và lұp trình trong máy tính phҧi

ÿѭӧc xem xét cҭn thұn, ÿӇ có thӇ chӑn ÿѭӧc kiӇu dӳ liӋu thích hӧp nhҩt. Mӝt kiӇu dӳ liӋu

ÿѭӧc biӇu diӉn và lұp trình ÿѭӧc gӑi là "cҩu trúc dӳ liӋu."

Hình 1-1-1 chӍ ra phân lӟp vӅ các cҩu trúc dӳ liӋu.

Hình 1-1-1 Phân lӟp vӅ các cҩu trúc dӳ liӋu

&ҩu trúc dӳ liӋu cѫ sӣ có thӇÿѭӧc biӇu diӉn trong hҫu hӃt tҩt cҧ các ngôn ngӳ lұp trình. Cҩu

trúc dӳ liӋu hѭӟng vҩn ÿӅ là cҩu trúc dӳ liӋu có thӇÿѭӧc dùng mӝt cách có hiӋu quҧÿӇ giҧi

quyӃt nhӳng vҩn ÿӅ chuyên dөng. Có mӝt sӕ cҩu trúc dӳ liӋu hѭӟng vҩn ÿӅ mà không thӇ

ÿѭӧc biӇu diӉn trong ngôn ngӳ lұp trình. Trong trѭӡng hӧp ÿó, cҩu trúc dӳ liӋu cѫ sӣÿѭӧc

dùng.

&ҩu trúc

Gӳ liӋu

&ҩu trúc dӳ

liӋu hѭӟng

Yҩn ÿӅ

(Tҥo ra tӯ

Fҩu trúc dӳ

liӋu cѫ sӣ)

&ҩu trúc danh sách

Ngăn xӃp

Hàng ÿӧi

&ҩu trúc cây

%ăm

KiӇu dӳ liӋu

Fѫ sӣ

KiӇu con trӓ

KiӇu ÿѫn

KiӇu nguyên

KiӇu thӵc

KiӇu kí tӵ

KiӇu logic

KiӇu liӋt kê

KiӇu bӝ phұn

KiӇu có

Fҩu trúc

KiӇu mҧng

KiӇu bҧn ghi

&ҩu trúc dӳ

liӋu cѫ sӣ

KiӇu dӳ liӋu

trӯu tѭӧng

1.2 Cҩu trúc dӳ liӋu cѫ sӣ 3

1.2 &ҩu trúc dӳ liӋu cѫ sӣ

1.2.1 KiӇu dӳ liӋu cѫ sӣ

KiӇu dӳ liӋu cѫ sӣ là tұp các dӳ liӋu riêng lҿ và thѭӡng ÿѭӧc dùng ÿӇ tҥo ra chѭѫng trình. Nó

ÿѭӧc phân loҥi thành các kiӇu ÿѫn và con trӓ.

(1) KiӇu ÿѫn

KiӇu ÿѫn là kiӇu dӳ liӋu cѫ sӣ nhҩt. Khi dùng kiӇu ÿѫn cho lұp trình, kiӇu dӳ liӋu thѭӡng

ÿѭӧc khai báo theo qui tҳc cú pháp cӫa ngôn ngӳ.

• KiӇu nguyên

KiӇu nguyên biӇu diӉn cho sӕ nguyên, và ÿѭӧc biӇu diӉn bên trong máy tính nhѭ sӕ nhӏ

phân theo sӕ dҩu phҧy tƭnh, không có chӳ sӕ có nghƭa sau dҩu chҩm thұp phân. Giá trӏ tӕi ÿa

hay tӕi thiӇu cӫa kiӇu nguyên là ÿѫn vӏ cӫa dӳ liӋu mà máy tính có thӇ xӱ lí vào mӝt lúc, và

nó ÿѭӧc xác ÿӏnh bӣi chiӅu dài tӯ.

‚ KiӇu sӕ thӵc

KiӇu sӕ thӵc biӇu diӉn cho sӕ thӵc. Nó ÿѭӧc dùng ÿӇ biӇu diӉn cho sӕ dҩu phҭy tƭnh và dҩu

phҭy ÿӝng.

ƒ KiӇu kí tӵ

KiӇu kí tӵ biӇu diӉn cho chӳ cái, sӕ và các kí hiӋu nhѭ các kí tӵ. Mӝt mã kí tӵÿѭӧc biӇu

diӉn nhѭ sӕ nhӏ phân trong máy tính.

„ KiӇu logic

KiӇu logic ÿѭӧc dùng ÿӇ thӵc hiӋn các phép toán logic nhѭ các phép toán AND, OR và

NOT.

… KiӇu liӋt kê

KiӇu liӋt kê ÿѭӧc ÿӏnh nghƭa nhѭ kiӇu dӳ liӋu kê ra tҩt cҧ các giá trӏ có thӇ cӫa biӃn. Trong

trѭӡng hӧp kiӇu liӋt kê, có thӇ kӇ tên kiӇu sӕ nguyên.

† KiӇu bӝ phұn

KiӇu bӝ phұn ÿѭӧc dùng ÿӇ xác ÿӏnh mӝt tұp con các giá trӏ nguyên thuӹ bҵng cách hҥn chӃ

các kiӇu dӳ liӋu hiӋn có. KiӇu dӳ liӋu có các giӟi hҥn trên và dѭӟi nhѭ các ràng buӝc ÿѭӧc

Jӑi là kiӇu miӅn bӝ phұn.

(2) KiӇu con trӓ

KiӇu con trӓ có ÿӏa chӍÿѭӧc cҩp trong ÿѫn vӏ bӝ nhӟ chính. Nó ÿѭӧc dùng ÿӅ tham chiӃu tӟi

các biӃn, các bҧn ghi tӋp hay các hàm. Nó ÿѭӧc dùng cho Pascal và C nhѭng không dùng cho

FORTRAN và COBOL.

4 Chѭѫng 1 Cҩu trúc dӳ liӋu

Hình 1-2-1 Hình ҧnh vӅ kiӇu con trӓ

1.2.2 KiӇu có cҩu trúc

&ҩu trúc dӳ liӋu có chӭa mӝt cҩu trúc dӳ liӋu cѫ sӣ hay bҩt kì kiӇu dӳ liӋu ÿѭӧc xác ÿӏnh nào

nhѭ phҫn tӱ cӫa nó (dӳ liӋu), ÿѭӧc gӑi là kiӇu có cҩu trúc. KiӇu có cҩu trúc ÿѭӧc phân loҥi

thành kiӇu mҧng và kiӇu bҧn ghi.

(1) KiӇu mҧng

0ҧng ÿѭӧc gӑi là bҧng. KiӇu mҧng là dӳ liӋu có cҩu trúc có chӭa dӳ liӋu thuӝc cùng kiӇu và

kích cӥ. Tӯng dӳ liӋu cá nhân ÿѭӧc gӑi là mӝt phҫn tӱ mҧng, phҫn tӱ bҧng hay phҫn tӱ. Cách

Pҧng ÿѭӧc mô tҧ hoһc cách dӳ liӋu ÿѭӧc bӕ trí có thay ÿәi tuǤ theo ngôn ngӳ lұp trình ÿѭӧc

dùng.

• Mҧng mӝt chiӅu

0ҧng mӝt chiӅu có cҩu trúc dӳ liӋu mà dӳ liӋu ÿѭӧc sҳp thành mҧng theo mӝt hàng. ĈӇ xác

ÿӏnh mӝt phҫn tӱ trong mҧng này, trѭӟc hӃt ÿѭa vào dҩu ngoһc tròn mӣ ( hay dҩu ngoһc

vuông [ sau tên cӫa mҧng, rӗi ÿѭa vào chӍ sӕ và dҩu ngoһc tròn ÿóng ) hay dҩu ngoһc vuông

ÿóng ]. ChӍ sӕ chӍ ra sӕ thӭ tӵ tính tӯÿӍnh cӫa mҧng, nѫi phҫn tӱ xác ÿӏnh ÿó ÿѭӧc ÿӏnh vӏ.

0ҧng "A" có sӕ phҫn tӱÿѭӧc kí hiӋu là "i" ÿѭӧc biӇu diӉn là A (i).

Hình 1-2-2 Mҧng mӝt chiӅu

Thӭ 1 thӭ 2 thӭ 3 … thӭ I …

Phҫn tӱ Phҫn tӱ Phҫn tӱ

… Phҫn tӱ

…

A(1) A(2) A(3) … A(I) …

‚ Mҧng hai chiӅu

0ӝt cҩu trúc dӳ liӋu trong ÿó dӳ liӋu ÿѭӧc sҳp hàng theo cҧ hai chiӅu ngang và ÿӭng ÿѭӧc

Jӑi là mҧng hai chiӅu. Dӳ liӋu theo chiӅu ÿӭng ÿѭӧc gӑi là cӝt và dӳ liӋu theo chiӅu ngang

ÿѭӧc gӑi là hàng. ĈӇ xác ÿӏnh phҫn tӱ nào ÿó trong mҧng này, hai chӍ sӕ trӣ nên cҫn thiӃt:

Pӝt chӍ sӕ thӭ tӵ theo chiӅu ÿӭng (trên hàng nào) nѫi phҫn tӱ xác ÿӏnh ÿó ÿѭӧc ÿӏnh vӏ và

chӍ sӕ kia chӍ ra sӕ thӭ tӵ nào theo chiӅu ngang (trong cӝt nào) mà nó ÿѭӧc ÿӏnh vӏ. Chҷng

Kҥn, mҧng "A" ÿѭӧc ÿӏnh vӏӣ hàng "i" và cӝt "j" có thӇÿѭӧc diӉn tҧ là A (i, j).

Ĉӏa chӍ cӫa biӃn "b" 'ӳ liӋu

BiӃn kiӇu con trӓ BiӃn "b"

1.2 Cҩu trúc dӳ liӋu cѫ sӣ 5

Hình 1-2-3 Mҧng hai chiӅu (vӟi ba hàng và hai cӝt)

&ӝt 1

Hàng 1 A(1, 1) A(1, 2)

A(2, 1) A(2, 2)

A(3, 1) A(3, 2)

Khi mҧng hai chiӅu ÿѭӧc lѭu giӳ trong ÿѫn vӏ bӝ nhӟ chính, nó lҩy dҥng cӫa mҧng mӝt chiӅu.

0ҧng hai chiӅu ÿѭӧc vӁ trong Hình 1-2-3 lҩy dҥng cӫa mҧng mӝt chiӅu có sáu phҫn tӱ. Nhѭ

ÿѭӧc vӁ trong Hình 1-2-4, dӳ liӋu ÿѭӧc lѭu giӳ theo kiӇu tuҫn tӵ hoһc theo chiӅu cӫa hàng

hoһc theo chiӅu cӫa cӝt. ChiӅu theo ÿó dӳ liӋu ÿѭӧc lѭu giӳ thay ÿәi tùy theo trình biên dӏch

Fӫa ngôn ngӳ lұp trình ÿѭӧc dùng. Nói chung, dӳ liӋu ÿѭӧc lѭu giӳ theo chiӅu ÿӭng khi

Fortran ÿѭӧc dùng và theo chiӅu ngang khi COBOL ÿѭӧc dùng.

Hình 1-2-4 Cách dӳ liӋu cӫa mҧng hai chiӅu ÿѭӧc lѭu giӳ trong ÿѫn vӏ bӝ nhӟ chính

A(1,1) A(1,2)

A(2,1) A(2,2)

A(3,1) A(3,2)

ƒ Mҧng ba chiӅu

0ҧng ba chiӅu có cҩu trúc dӳ liӋu nhiӅu hѫn mҧng hai chiӅu. Nó có cҩu trúc ba chiӅu chӭa các

Pһt phҷng, các hàng và cӝt cNJng nhѭ các phҫn tӱ. Bҵng viӋc xây dӵng mҧng ba chiӅu trong

Pҧng hai chiӅu, có thӇ xӱ lí mҧng ba chiӅu theo cùng cách nhѭ mҧng hai chiӅu.

0ҧng 2 chiӅu %ӝ nhӟ chính

A(1,1)

A(1,2)

A(2,1)

A(2,2)

A(3,1)

A(3,2)

A(1,1)

A(2,1)

A(3,1)

A(1,2)

A(2,2)

A(3,2)

'ӳ liӋu ÿѭӧc Dӳ liӋu ÿѭӧc

Oѭu trӳ lѭu trӳ

theo hàng theo cӝt

6 Chѭѫng 1 Cҩu trúc dӳ liӋu

Hình 1-2-5 Xây dӵng mҧng ba chiӅu thành mҧng hai chiӅu

0ҧng nhiӅu chiӅu nhѭ các mҧng bӕn, năm hay nhiӅu chiӅu cNJng có thӇÿѭӧc ÿӏnh nghƭa.

Tuy nhiên, có thӇ có nhӳng giӟi hҥn nào ÿó vӅ sӕ chiӅu, tùy theo kiӇu cӫa ngôn ngӳ lұp trình

hay trình biên dӏch.

0ҧng có thӇÿѭӧc phân loҥi thành mҧng tƭnh và mҧng ÿӝng theo phѭѫng pháp ÿѭӧc dùng ÿӇ

siӃt chһt mӝt miӅn.

- Mҧng tƭnh: Mҧng mà vùng ÿѭӧc yêu cҫu do chѭѫng trình xác ÿӏnh

- Mҧng ÿӝng: Mҧng mà vùng ÿѭӧc yêu cҫu sӁÿѭӧc xác ÿӏnh ra sau khi chӍ sӕÿѭӧc

dùng cho viӋc tҥo mҧng ÿѭӧc cung cҩp qua mӝt biӇu thӭc và biӇu

thӭc ÿó ÿѭӧc tính trong khi thӵc hiӋn chѭѫng trình

(2) KiӇu bҧn ghi

0һc dҫu dӳ liӋu kiӇu có cҩu trúc là cao cҩp hѫn trong viӋc dӉ tham chiӃu và thӵc hiӋn thao tác

trên các phҫn tӱ, nó cNJng có nhѭӧc ÿLӇm ӣ chӛ nó chӍ có thӇ giҧi quyӃt dӳ liӋu thuӝc cùng mӝt

kiӇu. Do ÿó, dӳ liӋu có chӭa các dӳ liӋu vӟi kiӇu khác nhau phҧi lҩy dҥng cӫa dӳ liӋu kiӇu bҧn

ghi. KiӇu bҧn ghi này cNJng còn ÿѭӧc gӑi là kiӇu cҩu trúc.

Hình 1-2-6 KiӇu bҧn ghi

Hình 1-2-6 chӍ ra cҩu trúc dӳ liӋu cӫa kiӇu bҧn ghi. Mӝt bҧn ghi chӭa sӕ hiӋu sinh viên (kiӇu

nguyên), tên (kiӇu kí tӵ) và ÿLӇm (kiӇu nguyên). Mӝt dӳ liӋu kiӇu bҧn ghi chӭa mӝt tұp các

Eҧn ghi có cùng ÿӏnh dҥng này. Mһc dҫu dӳ liӋu kiӇu bҧn ghi mӝt chiӅu có thӇÿѭӧc giҧi quyӃt

A(1,1,1) A(1,1,2)

A(1,2,1) A(2,2,2)

A(1,3,1) A(1,3,2)

A(1,1,1) A(1,1,2)

A(1,2,1) A(1,2,2)

A(1,3,1) A(1,3,2)

A(2,1,1) A(2,1,2)

A(2,1,1) A(2,1,2)

A(2,2,1) A(2,2,2)

A(2,3,1) A(2,3,2)

&ӝt

0һt phҷng

Hàng

0һt phҷng

thӭ hai

0һt phҷng

thӭ nhҩt

6ӕ Tên ĈLӇm Sӕ Tên ĈLӇm

sinh viên sinh viên

%ҧn ghi (dӳ liӋu vӅ sinh viên) KiӇu nguyên KiӇu kí tӵ (kiӇu xâu chuӛi) KiӇu sҳp xӃp

1.2 Cҩu trúc dӳ liӋu cѫ sӣ 7

theo cùng cách nhѭ mҧng mӝt chiӅu, tӯng dӳ liӋu vүn phҧi ÿѭӧc ÿһt tên ÿӇ nhұn diӋn vì tӯng

phҫn tӱ chӭa nhiӅu dӳ liӋu.

1.2.3 KiӇu dӳ liӋu trӯu tѭӧng

'ӳ liӋu chӭa cҩu trúc dӳ liӋu nào ÿó và kiӇu cӫa các phép toán ÿѭӧc gӑi là kiӇu dӳ liӋu trӯu

Wѭӧng. ĈӇ truy nhұp vào kiӇu dӳ liӋu này, bҥn không cҫn biӃt vӅ cҩu trúc bên trong cӫa nó. Tҩt

Fҧ các dӳ liӋu ÿӅu ÿѭӧc che dҩu ngoҥi trӯ dӳ liӋu bҥn truy nhұp ÿӇ tham chiӃu, thêm vào hay

xoá ÿi. ĈLӅu này ÿѭӧc gӑi là che giҩu thông tin. Che giҩu thông tin hoһc che giҩu dӳ liӋu ӣ

Pӭc ÿӝ kiӇu dӳ liӋu ÿѭӧc gӑi là bao bӑc dӳ liӋu.

Hình 1-2-7 KiӇu dӳ liӋu trӯu tѭӧng

(Các phép toán +

Fҩu trúc dӳ liӋu) Chѭѫng trình

.Ӄt quҧ

'ӳ liӋu <Cҩu trúc dӳ liӋu trӯu tѭӧng>

8 Chѭѫng 1 Cҩu trúc dӳ liӋu

1.3 &ҩu trúc dӳ liӋu hѭӟng vҩn

ÿӅ

Các cҩu trúc dӳ liӋu hѭӟng vҩn ÿӅ khác nhau có thӇÿѭӧc trù tính bҵng viӋc dùng các kiӇu

Pҧng, kiӇu con trӓ và các cҩu trúc dӳ liӋu cѫ sӣ khác.

1.3.1 &ҩu trúc danh sách

Không giӕng kiӇu dӳ liӋu cѫ sӣ giҧi quyӃt cho tӯng dӳ liӋu riêng lҿ, cҩu trúc danh sách cho

phép dӳ liӋu ÿѭӧc móc nӕi lүn nhau và giҧi quyӃt cҧ mӝt cөc. Dӳ liӋu ÿѭӧc bӕ trí theo cҩu trúc

danh sách này ÿѭӧc gӑi là mӝt danh sách.

(1) Cҩu trúc danh sách và các ô

%ҵng viӋc dùng chӍ sӕ cho tӯng phҫn tӱ trong mҧng, có thӇ truy nhұp nhanh chóng vào bҩt kì

phҫn tӱ nào. Tѭѫng tӵ nhѭ vұy, viӋc thay ÿәi dӳ liӋu có thӇÿѭӧc thӵc hiӋn dӉ dàng. NӃu bҥn

chèn mӝt dӳ liӋu vào ÿâu ÿó trong mҧng, bҥn phҧi dӏch chuyӇn toàn bӝ tӯng dӳ liӋu sau ÿó lùi

Oҥi mӝt vӏ trí. NӃu bҥn xoá mӝt dӳ liӋu trong mҧng, tѭѫng tӵ, bҥn phҧi dӏch chuyӇn toàn bӝ

Wӯng dӳ liӋu sau dӳ liӋu bӏ xoá ÿó nhích lên mӝt vӏ trí.

Hình 1-3-1 Chèn thêm mӝt phҫn tӱ mҧng

Không giӕng nhѭ cҩu trúc kiӇu mҧng, cҩu trúc danh sách cho phép phҫn tӱ dӳ liӋu cӫa cùng

kiӇu ÿѭӧc sҳp hàng tuҫn tӵ. KiӇm mҧng ÿòi hӓi rҵng viӋc bӕ trí logic cho các phҫn tӱ là giӕng

KӋt nhѭ viӋc bӕ trí vұt lí cӫa chúng trong bӝ nhӟ chính. Trong trѭӡng hӧp cӫa cҩu trúc danh

sách, viӋc bӕ trí logic không sánh hӋt nhѭ viӋc bӕ trí vұt lí.

Danh sách chӭa các ô và mӛi ô bao gӗm nhӳng phҫn tӱ sau:

- Phҫn dӳ liӋu chӭa phҫn tӱ dӳ liӋu

- Phҫn con trӓ chӭa ÿӏa chӍ

Do ÿó, phҫn dӳ liӋu cӫa ô có cùng cҩu trúc dӳ liӋu nhѭ cҩu trúc dӳ liӋu cӫa dӳ liӋu ÿѭӧc lѭu

giӳ và phҫn con trӓ cӫa ô có cҩu trúc dӳ liӋu kiӇu con trӓ. ĈLӅu này nghƭa là các ô biӇu diӉn

cho dӳ liӋu (cҩu trúc) kiӇu bҧn ghi chӭa các phҫn tӱ có cҩu trúc dӳ liӋu khác nhau. Danh sách

chӭa ÿӏa chӍ ô trong phҫn con trӓ và ô này ÿѭӧc móc nӕi sang ô kia qua con trӓ.

Arai Ueki Endou Okada

9ӏ trí mҧng ÿѭӧc chèn

Trѭӟc khi chèn

Sau khi chèn Arai Inoue Ueki Endou Okada

0ӛi dӳ liӋu ÿѭӧc dӏch vӅ phía sau

<Ӄu tӕ Inoue

ÿѭӧc chèn

1.3 Cҩu trúc dӳ liӋu hѭӟng vҩn ÿӅ 9

Hình 1-3-2 Cҩu trúc danh sách

(2) Chèn dӳ liӋu vào danh sách

ĈӇ chèn dӳ liӋu vào danh sách, mӑi ÿLӅu bҥn cҫn làm là thay thӃ các con trӓ tӟi dӳ liӋu ÿi

trѭӟc và ÿi sau dӳ liӋu ÿѭӧc chèn vào ÿó. Bӣi vì bҥn không phҧi dӏch chuyӇn các phҫn tӱ nhѭ

trѭӡng hӧp dӳ liӋu kiӇu mҧng, nên bҥn có thӇ chèn thêm dӳ liӋu mӝt cách dӉ dàng và nhanh

chóng. (Xem Hình 1-3-3.)

Hình 1-3-3 Chèn dӳ liӋu vào danh sách

(3) Xoá dӳ liӋu khӓi danh sách

ĈӇ xoá dӳ liӋu khӓi danh sách, mӑi ÿLӅu bҥn cҫn phҧi làm là thay thӃ các con trӓ nhѭ khi bҥn

chèn dӳ liӋu vào danh sách. Ô chӭa dӳ liӋu (Inoue) vүn còn trong vùng bӝ nhӟ nhѭ rác sau khi

Gӳ liӋu ÿã bӏ xoá, nhѭÿѭӧc vӁ trong Hình 1-3-4.

Hình 1-3-4 Xoá dӳ liӋu khӓi danh sách

0һc dҫu cҩu trúc danh sách cho phép dӳ liӋu ÿѭӧc chèn thêm hay ÿѭӧc xoá ÿi chӍ bҵng cách

thay thӃ các con trӓ, nó có nhѭӧc ÿLӇm là bҥn phҧi lҫn theo tӯng con trӓ mӝt tӯÿҫu nӃu bҥn

muӕn truy nhұp vào dӳ liӋu ÿһc biӋt.

(4) KiӇu cҩu trúc danh sách

Các cҩu trúc danh sách tiêu biӇu bao gӗm:

- Danh sách mӝt chiӅu

- Danh sách hai chiӅu

- Danh sách vòng.

%ӣi vì nhӳng danh sách này ÿѭӧc biӇu diӉn dѭӟi dҥng tuyӃn thҷng, nên nói chung chúng ÿѭӧc

Jӑi là danh sách tuyӃn tính.

• Danh sách mӝt chiӅu

Danh sách mӝt chiӅu cNJng còn ÿѭӧc gӑi là danh sách mӝt hѭӟng. Phҫn con trӓ cӫa ô chӭa

Phҫn dӳ liӋu Phҫn con trӓ Phҫn dӳ liӋu Phҫn con trӓ

Arai Inoue Ueki

Phҫn dӳ liӋu Phҫn con trӓ

Arai

Arai

Inoue

Ueki Endou

Ueki Endou

Ô ÿѭӧc chèn

1ѫi dӳ liӋu ÿѭӧc chèn

Trѭӟc khi chèn

Sau khi chèn

Phҫn dӳ liӋu Phҫn con trӓ

Arai Inoue Ueki Endou

Arai Inoue Ueki Endou

Ô bӏ xóa

Sau khi

xóa

Trѭӟc

khi xóa

10 Chѭѫng 1 Cҩu trúc dӳ liӋu

ÿӏa chӍ cӫa ô mà trong ÿó dӳ liӋu tiӃp ÿѭӧc lѭu giӳ. Bҵng viӋc lҫn theo nhӳng ÿӏa chӍ này

Wӯng ô mӝt, bҥn có thӇ thӵc hiӋn viӋc duyӋt dӳ liӋu.

Hình 1-3-5 Danh sách mӝt chiӅu

Con trӓ thӭ nhҩt ÿѭӧc gӑi là gӕc hay ÿҫu. Bӣi vì phҫn con trӓ cӫa ô cuӕi không có bҩt kì ÿӏa

chӍ nào trong ÿó dӳ liӋu có thӇÿѭӧc lѭu giӳ, nên NULL (giá trӏ sӕ là không) hay 㨈0 ÿѭӧc

chèn thêm vào phҫn này.

‚ Danh sách hai chiӅu

Danh sách hai chiӅu có hai phҫn con trӓ (٠ và ٟ (chӭa ÿӏa chӍ các ô nhѭÿѭӧc vӁ trong

Hình 1-3-6.

Hình 1-3-6 Danh sách hai chiӅu

Phҫn con trӓ ٠ và uÿѭӧc vӁ trong Hình 1-3-6 chӭa ÿӏa chӍ cӫa ô kӃ tiӃp và ÿӏa chӍ cӫa ô

ÿӭng trѭӟc tѭѫng ӭng. Ĉӏa chӍ cӫa ô cuӕi cùng ÿѭӧc chӭa trong con trӓÿuôi. Trong trѭӡng

Kӧp danh sách hai chiӅu, dӳ liӋu có thӇÿѭӧc lҫn theo tӯ ô ÿҫu hoһc ÿuôi.

ƒ Danh sách vòng

Danh sách hai chiӅu chӭa NULL ӣ ô ÿҫu tiên ÿѭӧc gӑi là danh sách vòng. Phҫn con trӓ cӫa

ô thӭ nhҩt này và phҫn con trӓ chӭa NULL cӫa ô cuӕi cùng chӭa ÿӏa chӍ ô khác, do vұy dӳ

liӋu có dҥng cái vòng. Dӳ liӋu có thӇÿѭӧc duyӋt theo cùng cách nhѭ trong danh sách hai

chiӅu.

Hình 1-3-7 Danh sách vòng

1.3.2 Ngăn xӃp

Ngăn xӃp là cҩu trúc dӳ liӋu ÿѭӧc thiӃt kӃ dӵa trên mҧng mӝt chiӅu. Phҫn tӱ cuӕi cùng ÿѭӧc

Oѭu giӳ sӁÿѭӧc ÿӑc ra trѭӟc hӃt. Nó ÿѭӧc so sánh vӟi trò chѫi ném vòng.

Arai Inoue Wada NULL

Ĉҫu Ô

Arai ٠ ٟ Inoue ٠ ٟ Wada

ٟ

NULL NULL

Ĉҫu Ĉuôi

ٟ Arai ٠ ٟ Inoue ٠ ٟ Wada ٠

٠

Ĉҫu

9ӏ trí ÿuôi

9ӏ trí ÿҫu

1.3 Cҩu trúc dӳ liӋu hѭӟng vҩn ÿӅ 11

Hình 1-3-8 Trò chѫi ném vòng

Trò chѫi ném vòng ÿѭӧc chѫi bҵng cách ném các vòng mҫu theo thӭ tӵÿӓ, lөc, vàng và lam

ÿѭa vào dӳ liӋu). Chúng ÿѭӧc lҩy ra tӯng cái mӝt (ÿѭa ra dӳ liӋu) theo thӭ tӵÿҧo lҥi viӋc ném

vào, tӭc là lam, vàng, lөc và ÿӓ. Tӭc là vòng lam ÿѭӧc ném vào cuӕi cùng sӁÿѭӧc lҩy ra ÿҫu

tiên.

KiӇu cҩu trúc dӳ liӋu này mà có thӇÿѭӧc so sánh vӟi trò chѫi ném vòng ÿѭӧc gӑi là ngăn xӃp.

+Ӌ thӕng này còn có thuұt ngӳ là hӋ thӕng vào-sau-ra-trѭӟc (LIFO). ViӋc lѭu trӳ dӳ liӋu trong

ngăn xӃp ÿѭӧc gӑi là "ҩn vào (PUSH)" và viӋc lҩy dӳ liӋu ra tӯ ngăn xӃp ÿѭӧc gӑi là "bұt ra

(POP)." BiӃn ÿLӅu khiӇn viӋc ҩn vào và bұt ra ÿѭӧc gӑi là con trӓ ngăn xӃp.

Ҩn dӳ liӋu vào ngăn xӃp, ÿһt con trӓ ngăn xӃp "sp" là +1 và lѭu giӳ dӳ liӋu trong phҫn tӱ

Pҧng ÿѭӧc viӃt là "sp." ĈӇ làm bұt ra dӳ liӋu tӯ ngăn xӃp, hãy lҩy dӳ liӋu ÿã ÿѭӧc lѭu giӳ

trong mҧng ÿѭӧc chӍ bӣi "sp" và ÿһt con trӓ ngăn xӃp là sp-1.

Hình 1-3-9 Cҩu trúc ngăn xӃp

1.3.3 Hàng ÿӧi

Hàng ÿӧi là cҩu trúc dӳ liӋu dӵa trên mҧng mӝt chiӅu. Dӳ liӋu ÿѭӧc lѭu giӳÿҫu tiên ÿѭӧc ÿӑc

ra ÿҫu tiên. Nó ÿѭӧc so sánh vӟi hàng ngѭӡi ÿang ÿӧi trѭӟc máy trҧ tiӅn cӫa ngân hàng.

Hình 1-3-10 Hàng ÿӧi

&ҩu trúc dӳ liӋu cho phép khách hàng ÿѭӧc phөc vө trên cѫ sӣÿӃn trѭӟc phөc vө trѭӟc ÿѭӧc

Jӑi là hàng ÿӧi. HӋ thӕng này ÿѭӧc gӑi là hӋ thӕng (FIFO). Hai con trӓ chӍ ra ÿҫu và ÿuôi cӫa

hàng ÿӧi là cҫn cho viӋc kiӇm soát hàng ÿӧi. Con trӓ chӍ ra ÿҫu và ÿuôi cӫa hàng ÿӧi ÿѭӧc

'ӳ liӋu D

'ӳ liӋu C

'ӳ liӋu B

'ӳ liӋu A

Ngăn xӃp (4)

Ngăn xӃp (3)

Ngăn xӃp (2)

Ngăn xӃp (1)

'ӳ liӋu lҩy ra 'ӳ liӋu nhұp vào

4

Con trӓ ngăn xӃp sp

ra

POP PUSH

sp - 1 sp + 1

12 Chѭѫng 1 Cҩu trúc dӳ liӋu

biӇu diӉn nhѭ biӃn ÿҫu và biӃn ÿuôi tѭѫng ӭng. (Xem Hình 1-3-11.)

Hình 1-3-11 Cҩu trúc hàng ÿӧi

<Thӫ tөc vұn hành hàng ÿӧi>

1. ĈӇ lѭu giӳ dӳ liӋu vào hàng ÿӧi (enqueue), ÿһt biӃn trӓÿuôi tăng thêm 1 và cҩt giӳ dӳ

liӋu.

2. ĈӇ lҩy ra dӳ liӋu tӯ hàng ÿӧi (dequeue), lҩy dӳ liӋu ra và ÿһt biӃn trӓÿҫu tăng lên 1.

1.3.4 &ҩu trúc cây

&ҩu trúc cây là mӝt trong nhӳng cҩu trúc dӳ liӋu rҩt hӳu dөng vì nó có thӇ kiӇm soát dӳ liӋu

phӭc tҥp tӕt hѫn các cҩu trúc dӳ liӋu kiӇu mҧng hay danh sách.

%ӣi vì nó có cҩu trúc phân cҩp nhѭ tә chӭc cӫa công ti hay cây gia ÿình, nên nó thích hӧp cho

kiӇu làm viӋc bao gӗm phân loҥi tӯng bѭӟc.

Hình 1-3-12 Sѫÿӗ tә chӭc

0һc dҫu tӯng ô ÿѭӧc sҳp theo thӭ tӵ tuyӃn tính trong cҩu trúc danh sách, dӳ liӋu ÿѭӧc sҳp

trong khi nó phân nhánh trong cҩu trúc cây.

&ҩu trúc cây bao gӗm các phҫn tӱÿѭӧc vӁ dѭӟi ÿây:

- Nút: Tѭѫng ӭng vӟi dӳ liӋu

- Nhánh: Nӕi nút này vӟi nút khác

- Gӕc: Nút ӣ cҩp cao nhҩt, không có cha mҽ

- Con: Nút rӁ nhánh ra dѭӟi mӝt nút khác

- Cha mҽ: Dӳ liӋu gӕc trѭӟc khi nó chia nhánh

- Lá: Nút ӣ cҩp thҩp nhҩt không có con

Hình 1-3-13 vӁ ra cҩu trúc cây

Hình 1-3-13 Cҩu trúc cây

'ӳ liӋu A Dӳ liӋu B Dӳ liӋu C Dӳ liӋu D

6ҳp xӃp (1) (2) (3) (4) (5) (6)

Hàng ÿӧi

Con trӓÿҫu Con trӓ cuӕi

7әng thӕng

Quҧn lý

hành chính

Quҧn lý

nhà máy

Quҧn lý

bán hàng

Quҧn lý bӝ phұn

hành chính

Quҧn lý bӝ phұn

NӃ toán

Quҧn lý bӝ phұn

bán hàng thӭ 1

Quҧn lý bӝ phұn

bán hàng thӭ 2

Quҧn lý bӝ phұn kӃ

hoҥch và bán hàng

Quҧn lý bӝ phұn

quҧn lý chҩt lѭӧng

Quҧn lý bӝ phұn

Vҧn phҭm

Quҧn lý bӝ phұn

Mua bán

A

B C

D E

F G H Lá

Nhánh

Nút

*ӕc

. A là cha nút C

. Nút D và E là con nút C.

1.3 Cҩu trúc dӳ liӋu hѭӟng vҩn ÿӅ 13

(1) Cây nhӏ phân

1Ӄu sӕ nhánh chӁ ra tӯ mӝt nút là "n" hay ít hѫn, tӭc là nӃu sӕ con là 0 cho tӟi "n", mӝt cҩu

trúc cây nhѭ vұy ÿѭӧc gӑi là cây N ngôi. Cây N-ngôi có 2 nhánh (n=2), tӭc là cây N ngôi

không có con, có mӝt hay hai con, ÿѭӧc gӑi là cây nhӏ phân, thѭӡng là cҩu trúc dӳ liӋu thѭӡng

dùng nhҩt. Mһt khác, cҩu trúc cây có ba hay nhiӅu nhánh (n>2) ÿѭӧc gӑi là cây nhiӅu nhánh.

Cây nhӏ phân bao gӗm mӝt phҫn dӳ liӋu và hai phҫn con trӓ. Con trӓ trái chӍ ra vӏ trí cӫa nút

kéo dài sang bên trái và các nhánh chӁ ra trong khi phҫn con trӓ phҧi chӍ ra vӏ trí cӫa nút kéo

dài sang bên phҧi và các nhánh chӁ ra.

Hình 1-3-14 Cҩu trúc cây nhӏ phân

Phҫn con trӓ trái Phҫn dӳ liӋu Phҫn con trӓ phҧi

Cây nhӏ phân có cҩu trúc phân cҩp cha mҽ - con, nhѭÿѭӧc vӁ trong Hình 1-3-15.

Hình 1-3-15 Cҩu trúc cây nhӏ phân cѫ sӣ

<Cách thӵc hiӋn viӋc duyӋt dӳ liӋu cây nhӏ phân>

ĈӇ duyӋt dӳ liӋu ÿһc biӋt trong dӳ liӋu cây nhӏ phân, phҧi lҫn theo tӯng nút mӝt. Có ba

phѭѫng pháp thӵc hiӋn duyӋt dӳ liӋu cây nhӏ phân. Vì khó giҧi thích bҵng lӡi nên hãy kiӇm lҥi

Hình 1-3-16 và xem cách dӳ liӋu ÿѭӧc duyӋt bҵng viӋc dùng tӯng phѭѫng pháp.

Hình 1-3-16 Cách thӵc hiӋn duyӋt dӳ liӋu cây nhӏ phân

- Thӭ tӵ gӕc trѭӟc (Pre-order): Vӟi gӕc là ÿLӇm bҳt ÿҫu, nút bên trái cӫa mӛi nút ÿѭӧc

duyӋt qua theo cách tuҫn tӵ.

- Thӭ tӵ gӕc giӳa (Mid-order): Vӟi lá tҥi ÿáy bên trái làm ÿLӇm bҳt ÿҫu, rӗi duyӋt qua nút

cha nó và tiӃp ÿó duyӋt qua phҫn còn lҥi cӫa nút ÿó theo cách tuҫn tӵ.

- Thӭ tӵ gӕc sau (Post order): Vӟi lá tҥi ÿáy bên trái làm ÿLӇm bҳt ÿҫu, phҫn bên phҧi mӛi

nút ÿѭӧc duyӋt qua theo cách tuҫn tӵ rӗi mӟi ÿӃn nút cha cӫa nó.

(2) Cây nhӏ phân hoàn chӍnh

1Ӄu cây nhӏ phân ÿѭӧc xây dӵng theo cách sӕ các nhánh tӯ gӕc tӟi tӯng lá dӑc theo mӝt

nhánh là bҵng hoһc sai khác mӝt so vӟi sӕ các nhánh tӯ gӕc tӟi tӯng lá dӑc theo nhánh khác

(hoһc nӃu chiӅu cao tӯ gӕc tӟi tӯng lá là bҵng hay sai khác mӝt vӟi chiӅu cao tӯ gӕc tӟi tӯng

lá thuӝc vào nhánh khác), thì cây ÿó ÿѭӧc gӑi là cây nhӏ phân hoàn chӍnh. Hình 1-3-17 vӁ ra

cây nhӏ phân hoàn chӍnh có mѭӡi nút.

Cha

Con Con