Giáo trình cấu trúc dữ liệu và thuật toán 2

TRÖÔØNG ÑAÏI HOÏC ÑAØ LAÏT

F 7 G

GIAÙO TRÌNH

CẤU TRÚC DỮ LIỆU VÀ THUẬT

TOÁN 2

Trương Chí Tín

Giaùo trình caáu truùc döõ lieäu vaø thuaät toaùn 2 - 2 –

MUÏC LUÏC

MUÏC LUÏC........................................................................................................................................2

LÔØI NOÙI ÑAÀU.................................................................................................................................5

CHÖÔNG I.......................................................................................................................................7

I/. GIÔÙI THIEÄU TAÄP TIN ...........................................................................................................7

I.1. Ñònh nghóa taäp tin (file).....................................................................................................7

I.2. Caùc thao taùc sô caáp treân taäp tin trong C++.......................................................................7

A/. Caùc phöông thöùc duøng chung cho caû hai kieåu taäp tin vaên baûn vaø nhò phaân.................7

1) Môû taäp tin.........................................................................................................................8

2) Ñoùng taäp tin. ....................................................................................................................9

3) Kieåm tra cuoái taäp tin........................................................................................................9

4) Kieåm tra traïng thaùi ñoïc, ghi döõ lieäu: ..............................................................................9

B/. Caùc phöông thöùc duøng cho taäp tin kieåu vaên baûn...........................................................9

1/ Ñoïc 1 chuoãi kyù töï: ...........................................................................................................9

2/ Ghi 1 chuoãi kyù töï: ............................................................................................................9

3/ Ghi 1 kyù töï. ....................................................................................................................10

4) Ñoïc 1 kyù töï. ...................................................................................................................10

C/. Caùc phöông thöùc duøng cho taäp tin kieåu nhò phaân........................................................10

1/ Ghi moät soá bytes:...........................................................................................................10

2/ Ñoïc moät soá bytes: ..........................................................................................................10

3/ Chuyeån con troû ñònh vò vieäc ghi trong file:...................................................................10

4/ Chuyeån con troû ñònh vò vieäc ñoïc trong file: ..................................................................11

I.3. Toå chöùc taäp tin.............................................................................................................11

II. CAÙC THAO TAÙC CÔ BAÛN TREÂN FILE.............................................................................13

II.1. Taäp tin tuaàn töï ................................................................................................................13

II.2. Taäp tin chæ muïc...............................................................................................................16

III. SAÉP XEÁP TREÂN FILE.........................................................................................................23

III.1. Troän tröïc tieáp (Straight Merge)....................................................................................23

III.2. Troän töï nhieân (Natural Merge).....................................................................................27

III.3. Troän nhieàu ñöôøng caân baèng (Balanced Multiway Merge)...........................................29

CHÖÔNG II: CAÁU TRUÙC CAÂY ...................................................................................................31

I. ÑÒNH NGHÓA VAØ CAÙC KHAÙI NIEÄM CÔ BAÛN..................................................................31

I.1. Ñònh nghóa caây.................................................................................................................31

I.2. Caùc khaùi nieäm khaùc.........................................................................................................31

II. CAÂY NHÒ PHAÂN...................................................................................................................33

II.1. Ñònh nghóa: caây nhò phaân laø caây (coù thöù töï) maø soá lôùn nhaát caùc nuùt con cuûa caùc nuùt laø

2..............................................................................................................................................33

II.2. Vaøi tính chaát cuûa caây nhò phaân ......................................................................................33

II.3. Bieåu dieãn caây nhò phaân..................................................................................................34

II.4. Duyeät caây nhò phaân........................................................................................................35

II.4.1. Ñònh nghóa: ..............................................................................................................35

II.4.2. Caùc thuaät toaùn duyeät caây nhò phaân.........................................................................35

II.4.3. Caøi ñaët thuaät toaùn duyeät qua caây nhò phaân LNR ...................................................36

Tröông Chí Tín Khoa Toaùn - Tin

Giaùo trình caáu truùc döõ lieäu vaø thuaät toaùn 2 - 3 –

II.5. Moät caùch bieåu dieãn khaùc cuûa caây nhò phaân ..................................................................38

II.7. Xaây döïng caây nhò phaân caân baèng hoaøn toaøn.................................................................39

II.7.1. Ñònh nghóa: ..............................................................................................................39

II.7.2. Xaây döïng caây nhò phaân caân baèng hoaøn toaøn..........................................................39

III.CAÂY NHÒ PHAÂN TÌM KIEÁM (BST)....................................................................................40

III.1. Ñònh nghóa caây nhò phaân tìm kieám (BST) ....................................................................40

III.2. Tìm kieám moät phaàn töû treân caây BST ...........................................................................41

III.2.1. Thuaät toaùn tìm kieám daïng ñeä qui:.........................................................................41

III.2.2. Thuaät toaùn tìm kieám daïng laëp: ..............................................................................41

III.3. Cheøn moät phaàn töû vaøo caây BST, xaây döïng caây BST...................................................42

III.3.1. Thao taùc cheøn moät nuùt Item vaøo caây BST (daïng laëp): ........................................43

III.3.2. Thuû tuïc cheøn moät nuùt Item vaøo caây BST (daïng ñeä qui):.....................................43

III.3.3. Xaây döïng caây BST.................................................................................................44

III.4. Phöông phaùp saép xeáp baèng caây BST............................................................................44

III.5. Xoùa moät phaàn töû khoûi caây BST, huûy caây nhò phaân .....................................................45

IV. CAÂY NHÒ PHAÂN TÌM KIEÁM CAÂN BAÈNG .......................................................................48

IV.1. Ñònh nghóa.....................................................................................................................48

IV.2. Chieàu cao cuûa caây caân baèng ........................................................................................49

IV.3. Chæ soá caân baèng vaø vieäc caân baèng laïi caây AVL..........................................................50

IV.4. Cheøn moät phaàn töû vaøo caây AVL..................................................................................56

IV.5. Xoùa moät phaàn töû khoûi caây AVL...................................................................................57

CHÖÔNG III: B - CAÂY .................................................................................................................60

I. ÑAËC ÑIEÅM CAÂY NHIEÀU NHAÙNH......................................................................................60

II. ÑÒNH NGHÓA B – CAÂY (baäc n)...........................................................................................61

III. TÌM KIEÁM MOÄT PHAÀN TÖÛ TREÂN B - CAÂY....................................................................61

IV. THEÂM MOÄT PHAÀN TÖÛ VAØO B - CAÂY ...........................................................................63

Quaù trình tìm kieám vaø theâm moät phaàn töû vaøo treân B - caây......................................................64

IV.1. Giaûi thuaät tìm vaø theâm moät phaàn töû vaøo B - caây........................................................64

IV.2. Giaûi thuaät xaây döïng B - caây .........................................................................................65

V. XOÙA MOÄT PHAÀN TÖÛ KHOÛI B - CAÂY...............................................................................67

V.1. Hai tình huoáng loaïi boû moät khoùa treân B-caây .............................................................67

V.2. Giaûi thuaät loaïi boû moät khoùa treân B-caây .....................................................................68

CHÖÔNG IV: BAÛNG BAÊM..........................................................................................................72

I.ÑAÏT VAÁN ÑEÀ, MUÏC ÑÍCH, YÙ NGHÓA................................................................................72

II. PHÖÔNG PHAÙP BIEÁN ÑOÅI KHOÙA....................................................................................72

H : K → A ....................................................................................................................................72

III. HAØM BIEÁN ÑOÅI KHOÙA (haøm baêm)..................................................................................73

H[k] = k mod M....................................................................................................................73

IV. GIAÛI QUYEÁT SÖÏ ÑUÏNG ÑOÄ.............................................................................................75

IV.1. Phöông phaùp baêm lieân keát............................................................................................75

IV.1.1. Phöông phaùp baêm lieân keát tröïc tieáp......................................................................75

IV.1.2. Phöông phaùp baêm lieân keát keát hôïp .......................................................................77

IV.2. Baêm theo phöông phaùp ñòa chæ môû ..............................................................................78

IV.2.1. Phöông phaùp baêm (thöû) tuyeán tính........................................................................79

IV.2.2. Phöông phaùp baêm (thöû) baäc hai ...........................................................................80

Tröông Chí Tín Khoa Toaùn - Tin

Giaùo trình caáu truùc döõ lieäu vaø thuaät toaùn 2 - 4 –

IV.2.3. Phöông phaùp baêm keùp ...........................................................................................81

BAØI TAÄP “CAÁU TRUÙC DÖÕ LIEÄU & THUAÄT TOAÙN 2” ............................................................85

Baøi taäp chöông 1 (File)..............................................................................................................85

Baøi taäp chöông 2 (Caáu truùc caây) ...............................................................................................88

Baøi taäp chöông 3 (B - caây).........................................................................................................91

Baøi taäp chöông 4 (Baûng baêm)....................................................................................................91

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

Tröông Chí Tín Khoa Toaùn - Tin

Giaùo trình caáu truùc döõ lieäu vaø thuaät toaùn 2 - 5 –

LÔØI NOÙI ÑAÀU

Giaùo trình naøy nhaèm cung caáp cho sinh vieân caùc kieán thöùc naâng cao veà caáu truùc

döõ lieäu vaø caùc thuaät toaùn coù lieân quan. Ñeå coù theå naém baét caùc kieán thöùc trình baøy

trong giaùo trình, sinh vieân caàn naém ñöôïc caùc kieán thöùc veà tin hoïc ñaïi cöông, kyõ thuaät

laäp trình, nhaäp moân caáu truùc döõ lieäu vaø thuaät toaùn. Caùc kieán thöùc naøy seõ taïo ñieàu kieän

cho sinh vieân hoïc tieáp caùc kieán thöùc veà kyõ thuaät laäp trình naâng cao, ñoà hoïa, laäp trình heä

thoáng, trí tueä nhaân taïo, ...

Noäi dung giaùo trình goàm 4 chöông:

- Chöông 1: Giôùi thieäu caùc thao taùc cô baûn veà file trong C++, cuõng nhö veà caùc kieåu

file tuaàn töï vaø chæ muïc.

- Chöông 2: Giôùi thieäu moät loaïi caáu truùc döõ lieäu ñoäng khaùc laø caây vaø caùc thao taùc

cô baûn treân caây nhò phaân, caây nhieàu nhaùnh vaø ñaëc bieät laø caây nhò phaân tìm kieám, caây

AVL.

- Chöông 3: Trình baøy moät loaïi caây nhieàu nhaùnh ñaëc bieät laø B – caây. Noù coù nhieàu

öùng duïng trong vieäc löu tröõ vaø tìm kieám treân caùc boä döõ lieäu lôùn.

- Chöông 4: Giôùi thieäu caùc phöông phaùp tìm kieám hieäu quaû treân caùc boä döõ lieäu lôùn

döïa vaøo baûng baêm: phöông phaùp baêm lieân keát, baêm theo ñòa chæ môû.

Chaén chaén raèng trong giaùo trình seõ coøn nhieàu khieám khuyeát, taùc giaû mong muoán

nhaän ñöôïc vaø raát bieát ôn caùc yù kieán quí baùu ñoùng goùp cuûa ñoàng nghieäp cuõng nhö baïn

ñoïc ñeå giaùo trình naøy coù theå hoaøn thieän hôn nöõa veà maët noäi dung cuõng nhö hình thöùc

trong laàn taùi baûn sau.

Ñaø laït, 06/2002

Taùc giaû

Tröông Chí Tín Khoa Toaùn - Tin

Giaùo trình caáu truùc döõ lieäu vaø thuaät toaùn 2 - 6 –

Tröông Chí Tín Khoa Toaùn - Tin

Giaùo trình caáu truùc döõ lieäu vaø thuaät toaùn 2 - 7 –

CHÖÔNG I

I/. GIÔÙI THIEÄU TAÄP TIN

I.1. Ñònh nghóa taäp tin (file)

Taäp tin laø taäp caùc thoâng tin veà caùc ñoái töôïng naøo ñoù coù quan heä vôùi

nhau, ñöôïc löu giöõ thaønh moät ñôn vò treân boä nhôù ngoaøi.

Treân thöïc teá, ta thöôøng caàn duøng ñeán taäp tin ñeå löu laâu daøi thoâng tin

vôùi soá löôïng lôùn. Caùc phöông phaùp saép xeáp vaø tìm kieám ñöôïc giôùi thieäu

trong giaùo trình “Caáu truùc döõ lieäu vaø thuaät toaùn 1” ñöôïc aùp duïng khi löôïng

döõ lieäu khoâng lôùn laém ñöôïc löu giöõ ôû boä nhôù trong.

I.2. Caùc thao taùc sô caáp treân taäp tin trong C++

Ta xeùt hai kieåu taäp tin trong ngoân ngöõ C++: taäp tin nhò phaân vaø taäp

tin vaên baûn.

- Taäp tin nhò phaân: döõ lieäu ghi treân taäp tin theo caùc bytes nhò phaân

gioáng nhö khi chuùng ñöôïc löu tröõ trong boä nhôù vaø chuùng khoâng bò bieán ñoåi

trong quaù trình nhaäp xuaát. Khi ñoïc ñeán cuoái taäp tin ta nhaän ñöôïc maõ keát

thuùc taäp tin EOF.

- Taäp tin vaên baûn: caùc taäp tin naøy löu tröõ caùc töø treân doøng. Noù khaùc

taäp tin kieåu nhò phaân khi xöû lyù kyù töï chuyeån doøng vaø kyù töï keát thuùc taäp tin

vaên baûn trong caùc thao taùc ñoïc vaø ghi.

C++ laø moät trong nhöõng ngoân ngöõ phuïc vuï cho phöông phaùp laäp

trình höôùng ñoái töôïng. Trong phöông phaùp naøy, moät trong nhöõng khaùi nieäm

quan troïng laø lôùp. Coù theå xem lôùp laø coâng cuï ñeå löu tröõ caùc ñoái töôïng thoâng

qua caáu truùc döõ lieäu ñeå bieåu dieãn chuùng vaø caû nhöõng phöông thöùc cô baûn

thao taùc treân chuùng. Khi laøm vieäc vôùi taäp tin trong C++, caùc thao taùc treân

taäp tin laø caùc phöông thöùc thuoäc caùc lôùp ifstream, ofstream, fstream, ios.

A/. Caùc phöông thöùc duøng chung cho caû hai kieåu taäp tin vaên baûn vaø nhò phaân

Tröông Chí Tín Khoa Toaùn - Tin

Giaùo trình caáu truùc döõ lieäu vaø thuaät toaùn 2 - 8 –

1) Môû taäp tin.

* Tröôùc khi laøm vieäc vôùi taäp tin (ñoïc hay ghi) ta phaûi môû noù ñeå

nhaän moät teân ngoaøi (teân file thöïc teá naèm treân ñóa), thöïc hieän moät soá vieäc

kieåm tra vaø phaân tích cuù phaùp, trao ñoåi vôùi heä ñieàu haønh roài taïo ra moät teân

noäi boä ñaïi dieän (bieán file hình thöùc) ñeå duøng veà sau trong vieäc ñoïc hay ghi

leân taäp tin. Teân noäi boä naøy laø moät con troû (goïi laø con troû taäp tin), troû tôùi caáu

truùc chöùa thoâng tin taäp tin, chaúng haïn nhö: vò trí boä ñeäm file, vò trí byte hieän

taïi trong boä ñeäm, taäp tin ñang ñoïc hay ghi, noái theâm,...

* Khai baùo vaø môû taäp tin theo cuù phaùp sau:

fstream BienFileHinhThuc(const char *FileName, int

mode);

trong ñoù FileName laø teân taäp tin coù kieåu haèng xaâu kyù töï, mode nhaän moät soá

trong caùc giaù trò sau (vaø chuùng noái keát nhau baèng toaùn töû logic treân bit ¦ ):

ios::in: môû moät taäp tin ñeå ñoïc. Neáu taäp tin chöa toàn taïi seõ bò loãi.

Phaàn choïn naøy coù theå boû qua neáu thay lôùp fstream bôûi ifstream.

ios::out: môû moät taäp tin ñeå ghi môùi. Neáu taäp tin ñaõ toàn taïi thì noù bò

xoùa. Phaàn choïn naøy coù theå boû qua neáu thay lôùp fstream bôûi ofstream.

ios::app: môû moät taäp tin ñeå ghi boå sung. Neáu taäp tin chöa toàn taïi thì

taïo taäp tin môùi.

ios::binary: môû moät taäp tin theo kieåu nhò phaân. Neáu khoâng coù phaàn naøy thì taäp

tin ñöôïc môû theo kieåu vaên baûn.

......

* Chuù yù:

- Neáu môû moät taäp tin chöa toàn taïi ñeå ghi hay noái theâm thì taäp tin seõ

ñöôïc taïo ra.

- Môû moät taäp tin ñaõ coù ñeå ghi môùi laøm cho noäi dung cuõ seõ bò maát

tröôùc khi ghi môùi!

- Môû moät taäp tin chöa coù ñeå ñoïc seõ sinh loãi.

- Neáu coù loãi khi môû taäp tin thì BienFileHinhThuc seõ nhaän giaù trò

NULL.

* Ví duï: Khai baùo

char TenFile[] = “Tam.dat”;

fstream f(TenFile, ios::in ¦ios::out ¦ ios::binary);

if (!f) cout <<”\nLoi mo file ” << TenFile << “ de doc va ghi

!”;

coù taùc duïng môû file TenFile theo kieåu nhò phaân, vöøa ñeå ñoïc vaø ñeå ghi vaø

kieåm tra vieäc môû file coù toát khoâng.

Tröông Chí Tín Khoa Toaùn - Tin

Giaùo trình caáu truùc döõ lieäu vaø thuaät toaùn 2 - 9 –

2) Ñoùng taäp tin.

Sau khi môû taäp tin vaø laøm caùc thao taùc ñoïc ghi xong, ta phaûi ñoùng taäp

tin theo cuù phaùp:

BienFileHinhThuc.close();

Phöông thöùc naøy phaù vôõ moái lieân heä giöõa BienFileHinhThuc vaø teân

ngoaøi ñaõ ñöôïc thieát laäp. Ngoaøi ra, noù coøn coù taùc duïng ñaåy noát noäi dung boä

ñeäm ra file (an toaøn döõ lieäu).

3) Kieåm tra cuoái taäp tin.

BienFileHinhThuc.eof ();

Haøm cho giaù trò khaùc 0 neáu gaëp cuoái taäp tin khi ñoïc, traùi laïi haøm cho

trò 0 (ta thöôøng duøng phöông thöùc naøy ñeå kieåm tra cuoái taäp tin sau leänh ñoïc

seõ trình baøy ôû phaàn sau).

4) Kieåm tra traïng thaùi ñoïc, ghi döõ lieäu:

BienFileHinhThuc.good();

Haøm naøy traû veà 0 neáu gaëp loãi ñoïc hay ghi vaø moät giaù trò khaùc khoâng

trong tröôøng hôïp ngöôïc laïi.

B/. Caùc phöông thöùc duøng cho taäp tin kieåu vaên baûn

1/ Ñoïc 1 chuoãi kyù töï:

char *BienFileHinhThuc.getline(char *line, int maxLine,

char delim);

Haøm naøy ñoïc moät doøng (keå caû daáu xuoáng doøng vaø caùc khoaûng traéng)

töø taäp tin ñöôïc chæ ñònh bôûi BienFileHinhThuc vaøo chuoãi kyù töï line, nhieàu

nhaát laø maxLine-1 kyù töï ñöôïc ñoïc vaøo; vieäc ñoïc seõ keát thuùc neáu gaëp kyù töï

delim . Doøng keát quûa seõ ñöôïc keát thuùc bôûi ‘\0’. Thoâng thöôøng haøm naøy traû veà

ñòa chæ chuoãi line, tröø khi gaëp cuoái taäp tin hoaëc gaëp loãi noù seõ cho trò NULL.

Phöông thöùc int BienFileHinhThuc.gcount() traû veà soá kyù töï vöøa

ñoïc ñöôïc.

2/ Ghi 1 chuoãi kyù töï:

BienFileHinhThuc << Chuoãi;

Toaùn töû naøy xuaát Chuoãi ra file ñöôïc chæ ñònh bôûi BienFileHinhThuc.

Tröông Chí Tín Khoa Toaùn - Tin