Giáo trình Lý thuyết cơ sở dữ liệu và giải thuật chuẩn nhất

MUÏC LUÏC

Muïc Trang

CHÖÔNG 1: TOÅNG QUAN VEÀ CAÁU TRUÙC DÖÕ LIEÄU & GT ...........3

1.1. Taàm quan troïng cuûa CTDL & GT trong moät ñeà aùn tin hoïc........................ 3

1.1.1. Xaây döïng caáu truùc döõ lieäu ......................................................................... 3

1.1.2. Xaây döïng giaûi thuaät ................................................................................... 3

1.1.3. Moái quan heä giöõa caáu truùc döõ lieäu vaø giaûi thuaät ....................................... 3

1.2. Ñaùnh giaù Caáu truùc döõ lieäu & Giaûi thuaät....................................................... 3

1.2.1. Caùc tieâu chuaån ñaùnh giaù caáu truùc döõ lieäu ................................................. 3

1.2.2. Ñaùnh giaù ñoä phöùc taïp cuûa thuaät toaùn ........................................................ 4

1.3. Kieåu döõ lieäu..................................................................................................... 4

1.3.1. Khaùi nieäm veà kieåu döõ lieäu.......................................................................... 4

1.3.2. Caùc kieåu döõ lieäu cô sôû ............................................................................... 4

1.3.3. Caùc kieåu döõ lieäu coù caáu truùc...................................................................... 5

1.3.4. Kieåu döõ lieäu con troû................................................................................... 5

1.3.5. Kieåu döõ lieäu taäp tin.................................................................................... 5

Caâu hoûi vaø baøi taäp ................................................................................................. 6

CHÖÔNG 2: KYÕ THUAÄT TÌM KIEÁM (Searching).............................8

2.1. Khaùi quaùt veà tìm kieám.................................................................................... 8

2.2. Caùc giaûi thuaät tìm kieám noäi ........................................................................... 8

2.2.1. Ñaët vaán ñeà................................................................................................. 8

2.2.2. Tìm tuyeán tính............................................................................................ 8

2.2.3. Tìm nhò phaân............................................................................................ 10

2.3. Caùc giaûi thuaät tìm kieám ngoaïi ..................................................................... 14

2.3.1. Ñaët vaán ñeà............................................................................................... 14

2.3.2. Tìm tuyeán tính.......................................................................................... 14

2.3.3. Tìm kieám theo chæ muïc............................................................................. 16

Caâu hoûi vaø baøi taäp ............................................................................................... 17

CHÖÔNG 3: KYÕ THUAÄT SAÉP XEÁP (SORTING) .............................19

3.1. Khaùi quaùt veà saép xeáp.................................................................................... 19

3.2. Caùc giaûi thuaät saép xeáp noäi............................................................................ 19

3.2.1 Saép xeáp baèng phöông phaùp ñoåi choã.......................................................... 20

3.2.2. Saép xeáp baèng phöông phaùp choïn ............................................................. 28

3.2.3. Saép xeáp baèng phöông phaùp cheøn ............................................................. 33

3.2.4. Saép xeáp baèng phöông phaùp troän .............................................................. 40

3.3. Caùc giaûi thuaät saép xeáp ngoaïi........................................................................ 60

3.3.1. Saép xeáp baèng phöông phaùp troän .............................................................. 60

3.3.2. Saép xeáp theo chæ muïc............................................................................... 79

Caâu hoûi vaø baøi taäp ............................................................................................... 82

Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät

Trang: 2

CHÖÔNG 4: DANH SAÙCH (LIST).....................................................84

4.1. Khaùi nieäm veà danh saùch............................................................................... 84

4.2. Caùc pheùp toaùn treân danh saùch..................................................................... 84

4.3. Danh saùch ñaëc ............................................................................................... 85

4.3.1. Ñònh nghóa............................................................................................... 85

4.3.2. Bieåu dieãn danh saùch ñaëc.......................................................................... 85

4.3.3. Caùc thao taùc treân danh saùch ñaëc ............................................................. 85

4.3.4. Öu nhöôïc ñieåm vaø ÖÙng duïng ................................................................... 91

4.4. Danh saùch lieân keát ........................................................................................ 92

4.4.1. Ñònh nghóa............................................................................................... 92

4.4.2. Danh saùch lieân keát ñôn ............................................................................ 92

4.4.3. Danh saùch lieân keát keùp .......................................................................... 111

4.4.4. Öu nhöôïc ñieåm cuûa danh saùch lieân keát .................................................. 135

4.5. Danh saùch haïn cheá...................................................................................... 135

4.5.1. Haøng ñôïi................................................................................................ 135

4.5.2. Ngaên xeáp ............................................................................................... 142

4.5.3. ÖÙng duïng cuûa danh saùch haïn cheá.......................................................... 147

Caâu hoûi vaø baøi taäp ............................................................................................. 147

CHÖÔNG 5: CAÂY (TREE) ...............................................................149

5.1. Khaùi nieäm – Bieåu dieãn caây......................................................................... 149

5.1.1. Ñònh nghóa caây ...................................................................................... 149

5.1.2. Moät soá khaùi nieäm lieân quan ................................................................... 149

5.1.3. Bieåu dieãn caây......................................................................................... 151

5.2. Caây nhò phaân ............................................................................................... 152

5.2.1. Ñònh nghóa............................................................................................. 152

5.2.2. Bieåu dieãn vaø Caùc thao taùc ..................................................................... 152

5.2.3. Caây nhò phaân tìm kieám........................................................................... 163

5.3. Caây caân baèng............................................................................................... 188

5.3.1. Ñònh nghóa – Caáu truùc döõ lieäu............................................................... 188

5.3.2. Caùc thao taùc .......................................................................................... 189

Caâu hoûi vaø baøi taäp ............................................................................................. 227

OÂN TAÄP (REVIEW)..........................................................................224

Heä thoáng laïi caùc Caáu truùc döõ lieäu vaø caùc Giaûi thuaät ñaõ hoïc.......................... 224

Caâu hoûi vaø Baøi taäp oân taäp toång hôïp................................................................. 227

TAØI LIEÄU THAM KHAÛO.................................................................229

By Hút thuốc lá có hại cho sức khỏe at 9:19 pm, Jun 25, 2007

Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät

Trang: 3

Chöông 1: TOÅNG QUAN VEÀ CAÁU TRUÙC DÖÕ LIEÄU VAØ GIAÛI THUAÄT

1.1. Taàm quan troïng cuûa caáu truùc döõ lieäu vaø giaûi thuaät trong moät

ñeà aùn tin hoïc

1.1.1. Xaây döïng caáu truùc döõ lieäu

Coù theå noùi raèng khoâng coù moät chöông trình maùy tính naøo maø khoâng coù döõ lieäu ñeå xöû lyù.

Döõ lieäu coù theå laø döõ lieäu ñöa vaøo (input data), döõ lieäu trung gian hoaëc döõ lieäu ñöa ra

(output data). Do vaäy, vieäc toå chöùc ñeå löu tröõ döõ lieäu phuïc vuï cho chöông trình coù yù

nghóa raát quan troïng trong toaøn boä heä thoáng chöông trình. Vieäc xaây döïng caáu truùc döõ

lieäu quyeát ñònh raát lôùn ñeán chaát löôïng cuõng nhö coâng söùc cuûa ngöôøi laäp trình trong vieäc

thieát keá, caøi ñaët chöông trình.

1.1.2. Xaây döïng giaûi thuaät

Khaùi nieäm giaûi thuaät hay thuaät giaûi maø nhieàu khi coøn ñöôïc goïi laø thuaät toaùn duøng ñeå chæ

phöông phaùp hay caùch thöùc (method) ñeå giaûi quyeát vaàn ñeà. Giaûi thuaät coù theå ñöôïc minh

hoïa baèng ngoân ngöõ töï nhieân (natural language), baèng sô ñoà (flow chart) hoaëc baèng maõ

giaû (pseudo code). Trong thöïc teá, giaûi thuaät thöôøng ñöôïc minh hoïa hay theå hieän baèng

maõ giaû töïa treân moät hay moät soá ngoân ngöõ laäp trình naøo ñoù (thöôøng laø ngoân ngöõ maø

ngöôøi laäp trình choïn ñeå caøi ñaët thuaät toaùn), chaúng haïn nhö C, Pascal, …

Khi ñaõ xaùc ñònh ñöôïc caáu truùc döõ lieäu thích hôïp, ngöôøi laäp trình seõ baét ñaàu tieán haønh

xaây döïng thuaät giaûi töông öùng theo yeâu caàu cuûa baøi toaùn ñaët ra treân cô sôû cuûa caáu truùc

döõ lieäu ñaõ ñöôïc choïn. Ñeå giaûi quyeát moät vaán ñeà coù theå coù nhieàu phöông phaùp, do vaäy

söï löïa choïn phöông phaùp phuø hôïp laø moät vieäc maø ngöôøi laäp trình phaûi caân nhaéc vaø tính

toaùn. Söï löïa choïn naøy cuõng coù theå goùp phaàn ñaùng keå trong vieäc giaûm bôùt coâng vieäc

cuûa ngöôøi laäp trình trong phaàn caøi ñaët thuaät toaùn treân moät ngoân ngöõ cuï theå.

1.1.3. Moái quan heä giöõa caáu truùc döõ lieäu vaø giaûi thuaät

Moái quan heä giöõa caáu truùc döõ lieäu vaø Giaûi thuaät coù theå minh hoïa baèng ñaúng thöùc:

Caáu truùc döõ lieäu + Giaûi thuaät = Chöông trình

Nhö vaäy, khi ñaõ coù caáu truùc döõ lieäu toát, naém vöõng giaûi thuaät thöïc hieän thì vieäc theå hieän

chöông trình baèng moät ngoân ngöõ cuï theå chæ laø vaán ñeà thôøi gian. Khi coù caáu truùc döõ lieäu

maø chöa tìm ra thuaät giaûi thì khoâng theå coù chöông trình vaø ngöôïc laïi khoâng theå coù

Thuaät giaûi khi chöa coù caáu truùc döõ lieäu. Moät chöông trình maùy tính chæ coù theå ñöôïc hoaøn

thieän khi coù ñaày ñuû caû Caáu truùc döõ lieäu ñeå löu tröõ döõ lieäu vaø Giaûi thuaät xöû lyù döõ lieäu

theo yeâu caàu cuûa baøi toaùn ñaët ra.

1.2. Ñaùnh giaù caáu truùc döõ lieäu vaø giaûi thuaät

1.2.1. Caùc tieâu chuaån ñaùnh giaù caáu truùc döõ lieäu

Ñeå ñaùnh giaù moät caáu truùc döõ lieäu chuùng ta thöôøng döïa vaøo moät soá tieâu chí sau:

- Caáu truùc döõ lieäu phaûi tieát kieäm taøi nguyeân (boä nhôù trong),

By Hút thuốc lá có hại cho sức khỏe at 9:19 pm, Jun 25, 2007

Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät

Trang: 4

- Caáu truùc döõ lieäu phaûi phaûn aûnh ñuùng thöïc teá cuûa baøi toaùn,

- Caáu truùc döõ lieäu phaûi deã daøng trong vieäc thao taùc döõ lieäu.

1.2.2. Ñaùnh giaù ñoä phöùc taïp cuûa thuaät toaùn

Vieäc ñaùnh giaù ñoä phöùc taïp cuûa moät thuaät toaùn quaû khoâng deã daøng chuùt naøo. ÔÛ daây,

chuùng ta chæ muoán öôùc löôïng thôøi gian thöïc hieän thuaän toaùn T(n) ñeå coù theå coù söï so

saùnh töông ñoái giöõa caùc thuaät toaùn vôùi nhau. Trong thöïc teá, thôøi gian thöïc hieän moät

thuaät toaùn coøn phuï thuoäc raát nhieàu vaøo caùc ñieàu kieän khaùc nhö caáu taïo cuûa maùy tính,

döõ lieäu ñöa vaøo, …, ôû ñaây chuùng ta chæ xem xeùt treân möùc ñoä cuûa löôïng döõ lieäu ñöa vaøo

ban ñaàu cho thuaät toaùn thöïc hieän.

Ñeå öôùc löôïng thôøi gian thöïc hieän thuaät toaùn chuùng ta coù theå xem xeùt thôøi gian thöïc hieän

thuaät toaùn trong hai tröôøng hôïp:

- Trong tröôøng hôïp toát nhaát: Tmin

- Trong tröôøng hôïp xaáu nhaát: Tmax

Töø ñoù chuùng ta coù theå öôùc löôïng thôøi gian thöïc hieän trung bình cuûa thuaät toaùn: Tavg

1.3. Kieåu döõ lieäu

1.3.1. Khaùi nieäm veà kieåu döõ lieäu

Kieåu döõ lieäu T coù theå xem nhö laø söï keát hôïp cuûa 2 thaønh phaàn:

- Mieàn giaù trò maø kieåu döõ lieäu T coù theå löu tröõ: V,

- Taäp hôïp caùc pheùp toaùn ñeå thao taùc döõ lieäu: O.

T = <V, O>

Moãi kieåu döõ lieäu thöôøng ñöôïc ñaïi dieän bôûi moät teân (ñònh danh). Moãi phaàn töû döõ lieäu coù

kieåu T seõ coù giaù trò trong mieàn V vaø coù theå ñöôïc thöïc hieän caùc pheùp toaùn thuoäc taäp hôïp

caùc pheùp toaùn trong O.

Ñeå löu tröõ caùc phaàn töû döõ lieäu naøy thöôøng phaûi toán moät soá byte(s) trong boä nhôù, soá

byte(s) naøy goïi laø kích thöôùc cuûa kieåu döõ lieäu.

1.3.2. Caùc kieåu döõ lieäu cô sôû

Haàu heát caùc ngoân ngöõ laäp trình ñeàu coù cung caáp caùc kieåu döõ lieäu cô sôû. Tuøy vaøo moãi

ngoân ngöõ maø caùc kieåu döõ lieäu cô sôû coù theå coù caùc teân goïi khaùc nhau song chung quy

laïi coù nhöõng loaïi kieåu döõ lieäu cô sôû nhö sau:

- Kieåu soá nguyeân: Coù theå coù daáu hoaëc khoâng coù daáu vaø thöôøng coù caùc kích thöôùc sau:

+ Kieåu soá nguyeân 1 byte

+ Kieåu soá nguyeân 2 bytes

+ Kieåu soá nguyeân 4 bytes

Kieåu soá nguyeân thöôøng ñöôïc thöïc hieän vôùi caùc pheùp toaùn: O = {+, -, *, /, DIV, MOD, <,

>, <=, >=, =, …}

Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät

Trang: 5

- Kieåu soá thöïc: Thöôøng coù caùc kích thöôùc sau:

+ Kieåu soá thöïc 4 bytes

+ Kieåu soá thöïc 6 bytes

+ Kieåu soá thöïc 8 bytes

+ Kieåu soá thöïc 10 bytes

Kieåu soá thöïc thöôøng ñöôïc thöïc hieän vôùi caùc pheùp toaùn: O = {+, -, *, /, <, >, <=, >=, =, …}

- Kieåu kyù töï: Coù theå coù caùc kích thöôùc sau:

+ Kieåu kyù töï byte

+ Kieåu kyù töï 2 bytes

Kieåu kyù töï thöôøng ñöôïc thöïc hieän vôùi caùc pheùp toaùn: O = {+, -, <, >, <=, >=, =, ORD,

CHR, …}

- Kieåu chuoãi kyù töï: Coù kích thöôùc tuøy thuoäc vaøo töøng ngoân ngöõ laäp trình

Kieåu chuoãi kyù töï thöôøng ñöôïc thöïc hieän vôùi caùc pheùp toaùn: O = {+, &, <, >, <=, >=, =,

Length, Trunc, …}

- Kieåu luaän lyù: Thöôøng coù kích thöôùc 1 byte

Kieåu luaän lyù thöôøng ñöôïc thöïc hieän vôùi caùc pheùp toaùn: O = {NOT, AND, OR, XOR, <, >,

<=, >=, =, …}

1.3.3. Caùc kieåu döõ lieäu coù caáu truùc

Kieåu döõ lieäu coù caáu truùc laø caùc kieåu döõ lieäu ñöôïc xaây döïng treân cô sôû caùc kieåu döõ lieäu

ñaõ coù (coù theå laïi laø moät kieåu döõ lieäu coù caáu truùc khaùc). Tuøy vaøo töøng ngoân ngöõ laäp

trình song thöôøng coù caùc loaïi sau:

- Kieåu maûng hay coøn goïi laø daõy: kích thöôùc baèng toång kích thöôùc cuûa caùc phaàn töû

- Kieåu baûn ghi hay caáu truùc: kích thöôùc baèng toång kích thöôùc caùc thaønh phaàn (Field)

1.3.4. Kieåu döõ lieäu con troû

Caùc ngoân ngöõ laäp trình thöôøng cung caáp cho chuùng ta moät kieåu döõ lieäu ñaëc bieät ñeå löu

tröõ caùc ñòa chæ cuûa boä nhôù, ñoù laø con troû (Pointer). Tuøy vaøo loaïi con troû gaàn (near

pointer) hay con troû xa (far pointer) maø kieåu döõ lieäu con troû coù caùc kích thöôùc khaùc

nhau:

+ Con troû gaàn: 2 bytes

+ Con troû xa: 4 bytes

1.3.5. Kieåu döõ lieäu taäp tin

Taäp tin (File) coù theå xem laø moät kieåu döõ lieäu ñaëc bieät, kích thöôùc toái ña cuûa taäp tin tuøy

thuoäc vaøo khoâng gian ñóa nôi löu tröõ taäp tin. Vieäc ñoïc, ghi döõ lieäu tröïc tieáp treân taäp tin

raát maát thôøi gian vaø khoâng baûo ñaûm an toaøn cho döõ lieäu treân taäp tin ñoù. Do vaäy, trong

thöïc teá, chuùng ta khoâng thao taùc tröïc tieáp döõ lieäu treân taäp tin maø chuùng ta caàn chuyeån

töøng phaàn hoaëc toaøn boä noäi dung cuûa taäp tin vaøo trong boä nhôù trong ñeå xöû lyù.

Giáo trình Lý thuyết cơ sở dữ liệu và giải thuật

Chủ đề:

Tài liệu liên quan

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

Hỗ trợ

Phương thức thanh toán

Theo dõi chúng tôi