intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

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

Chia sẻ: Nguyễn Duy | Ngày: | Loại File: PDF | Số trang:94

Thêm vào BST
Báo xấu
66
lượt xem 6
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Với kết cấu nội dung gồm 4 chương, giáo trình "Cấu trúc dữ liệu và thuật toán 2" giới thiệu đến các bạn những nội dung về cấu trúc cây, cây, bảng băm,... Với các bạn đang học chuyên ngành Toán học thì đây là tài liệu tham khảo hữu ích cho các bạn.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Giáo trình Cấu trúc dữ liệu và thuật toán 2

  1. TRÖÔØNG ÑAÏI HOÏC ÑAØ LAÏT F7G GIAÙO TRÌNH CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 2 Trương Chí Tín
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. Giaùo trình caáu truùc döõ lieäu vaø thuaät toaùn 2 - 10 – 3/ Ghi 1 kyù töï. BienFileHinhThuc.put(char c); Haøm ghi moät kyù töï ra file ñöôïc chæ ñònh bôûi BienFileHinhThuc. 4) Ñoïc 1 kyù töï. char BienFileHinhThuc.get(); * Haøm naøy ñoïc moät kyù töï töø file ñöôïc chæ ñònh bôûi BienFileHinhThuc vaø laøm dôøi choã vò trí con troû ñònh vò vieäc ñoïc trong taäp tin ñeán vò trí keá tieáp. * Haøm get traû veà kyù töï ñoïc ñöôïc, neáu thaønh coâng. C/. Caùc phöông thöùc duøng cho taäp tin kieåu nhò phaân 1/ Ghi moät soá bytes: BienFileHinhThuc.write(const char *buf, int size); Haøm naøy ghi vaøo file ñöôïc chæ ñònh bôûi BienFileHinhThuc moät soá size bytes, baét ñaàu töø ñòa chæ buf. 2/ Ñoïc moät soá bytes: BienFileHinhThuc.read(char *buf, int size); Haøm naøy ñoïc töø file ñöôïc chæ ñònh bôûi BienFileHinhThuc moät soá size bytes vaø gaùn chuùng vaøo maûng caùc kyù töï ñöôïc xaùc ñònh bôûi buf. Coù theå duøng phöông thöùc int BienFileHinhThuc.gcount() ñeå bieát soá bytes vöøa ñoïc ñöôïc. 3/ Chuyeån con troû ñònh vò vieäc ghi trong file: BienFileHinhThuc.seekp(long offset, int origin); Ñeå truy caäp ngaãu nhieân taäp tin khi ghi ta duøng haøm naøy ñeå ñaët con troû ñònh vò vieäc ghi trong taäp tin ñöôïc chæ ñònh bôûi BienFileHinhThuc di chuyeån offset bytes töø vò trí xuaát phaùt ñöôïc xaùc ñònh theo moät trong caùc giaù trò sau cuûa origin: ios::beg tìm töø ñaàu taäp tin ios::cur tìm töø vò trí hieän haønh ios::end tìm töø cuoái taäp tin Phöông thöùc long BienFileHinhThuc.tellp(); traû veà vò trí hieän haønh cuûa con troû ñònh vò vieäc ghi trong taäp tin. Tröông Chí Tín Khoa Toaùn - Tin
  11. Giaùo trình caáu truùc döõ lieäu vaø thuaät toaùn 2 - 11 – 4/ Chuyeån con troû ñònh vò vieäc ñoïc trong file: BienFileHinhThuc.seekg(long offset, int origin); Ñeå truy caäp ngaãu nhieân taäp tin khi ñoïc ta duøng haøm naøy ñeå ñaët con troû ñònh vò vieäc ñoïc trong taäp tin ñöôïc chæ ñònh bôûi BienFileHinhThuc di chuyeån offset bytes töø vò trí xuaát phaùt ñöôïc xaùc ñònh theo giaù trò cuûa origin. Phöông thöùc long BienFileHinhThuc.tellg(); traû veà vò trí hieän haønh cuûa con troû ñònh vò vieäc ñoïc trong taäp tin. Löu yù khi truy caäp ngaãu nhieân taäp tin ñeå ñoïc hay ghi, caùc bytes ñöôïc ñaùnh soá baét ñaàu töø 0. I.3. Toå chöùc taäp tin Döïa treân caùc thao taùc sô caáp truy nhaäp file treân ñaây, ta coù theå xaây döïng caùc thuaät toaùn phöùc taïp vaø höõu ích khaùc treân file chöùa caùc ñoái töôïng coù cuøng caáu truùc. Khi xeùt ñeán ñoä hieäu quaû cuûa caùc thuaät toaùn naøy (ñaëc bieät veà maët thôøi gian), ta coù theå toå chöùc file theo 2 kieåu: tuaàn töï hay coù chæ muïc. * Khi löu vaø truy caäp caùc ñoái töôïng theo kieåu tuaàn töï trong moät file, ta coù kieåu file tuaàn töï. Ví duï 1: Giaû söû ta caàn löu caùc ñoái töôïng A, C, B cuøng kieåu T vaøo file f. f A C B Tuy caùch löu tröõ naøy raát ñôn giaûn khi caøi ñaët nhöng ta seõ gaëp nhieàu nhöôïc ñieåm (veà maët thôøi gian) khi gaëp caùc tình huoáng sau. Neáu ta caàn cheøn theâm 1 ñoái töôïng D vaøo tröôùc A thì ta phaûi dôøi moïi phaàn töû töø A qua phaûi moät vò trí; neáu ta muoán xoùa ñoái töôïng A, thì ta phaûi dôøi moïi phaàn töû töø A qua traùi moät vò trí. Ñoái vôùi caùc taäp tin löu nhieàu ñoái töôïng coù cuøng kieåu döõ lieäu T (treân thöïc teá, ta thöôøng gaëp tröôøng hôïp T coù kích thöôùc (bytes) löu tröõ lôùn), neáu phaûi duøng nhieàu thao taùc cheøn vaø xoùa seõ maát raát nhieàu thôøi gian cho vieäc dôøi choã caùc phaàn töû. Ñeå khaéc phuïc nhöôïc ñieåm treân, ta coù theå toå chöùc taäp tin theo kieåu chæ muïc ñôn giaûn nhö sau: * Khi caàn löu moät daõy caùc ñoái töôïng coù cuøng kieåu T vaøo file f, ngoaøi vieäc duøng file f nhö caùch toå chöùc tuaàn töï nhö treân, ta duøng keøm theâm moät file Tröông Chí Tín Khoa Toaùn - Tin
  12. Giaùo trình caáu truùc döõ lieäu vaø thuaät toaùn 2 - 12 – chæ muïc f_idx töông öùng ñeå chöùa caùc ñòa chæ (hay thöù töï) cuûa caùc ñoái töôïng thöïc söï trong file f. Khi ñoù, caùc thao taùc cheøn, xoùa seõ thöïc hieän nhanh hôn. Ví duï 2: vôùi cuøng muïc ñích nhö ví duï 1, ta duøng 2 file: file f ñeå chöùa caùc ñoái töôïng thöïc söï A, B, C vaø file f_idx duøng ñeå chöùa soá thöù töï baét ñaàu cuûa caùc ñoái töôïng töông öùng trong f nhö sau: 0 1 2 f A B C f_idx 0 1 2 -1 trong ñoù: caùc phaàn töû cuûa f_idx: 0,1,2 laàn löôït chæ soá thöù töï (baét ñaàu) cuûa ñoái töôïng A, B, C trong file f; coøn –1 (EOF) ñeå chæ söï kieän keát thuùc file. Vieäc cheøn D vaøo f tröôùc A, seõ thöïc hieän nhö sau: 0 1 2 3 f A B C D f_idx 3 1 2 -1 0 Vieäc xoùa A, ta coù theå ñaùnh daáu xoùa A (neáu caàn thieát !) baèng caùch gaùn chæ soá –2 (XOA) cho maåu tin töông öùng trong f_idx vaø ñoåi laïi soá thöù töï baét ñaàu trong caùc maåu tin töông öùng trong f tröôùc A (laø D) nhö sau: 0 1 2 3 f A B C D f_idx 3 -2 2 -1 1 Taát nhieân, vieäc duøng keøm theâm file chæ muïc nhö treân coù öu ñieåm laø laøm taêng toác ñoä thöïc hieän caùc thao taùc cheøn, xoùa; ngöôïc laïi, noù seõ toán theâm boä nhôù cho f_idx vaø cuõng laøm phöùc taïp theâm khi vieát caùc thao taùc cô baûn treân file, ñaëc bieät laø caùc thuaät toaùn cheøn, xoùa moät ñoái töôïng. * Vaøi löu yù khi thieát keá caùc thuaät toaùn treân taäp tin: Khi thieát keá caùc thuaät toaùn treân taäp tin, ngoaøi caùc pheùp toaùn cô baûn ñaëc tröng cho thuaät toaùn (chaúng haïn: ñoái vôùi caùc thuaät toaùn tìm kieám, ta caàn ñeå yù ñeán soá caùc pheùp toaùn so saùnh; ñoái vôùi caùc thuaät toaùn saép xeáp thì neân ñeå yù ñeán soá caùc pheùp toaùn so saùnh vaø hoaùn vò hay pheùp gaùn; …), ta coøn phaûi Tröông Chí Tín Khoa Toaùn - Tin
  13. Giaùo trình caáu truùc döõ lieäu vaø thuaät toaùn 2 - 13 – chuù yù nhieàu tôùi soá laàn ñoïc vaø ghi ñoái töôïng leân file, vì thôøi gian cho caùc thao taùc naøy chieám thôøi gian khaù lôùn. II. CAÙC THAO TAÙC CÔ BAÛN TREÂN FILE Caùc thao taùc cô baûn thöôøng söû duïng khi laøm vieäc treân file chöùa caùc ñoái töôïng coù cuøng caáu truùc laø: taïo (xaây döïng) file, duyeät vaø khai thaùc file, tìm hay xoùa moät ñoái töôïng coù moät tính chaát naøo ñoù cuûa file, cheøn (theâm) moät ñoái töôïng vaøo sau moät ñoái töôïng thoûa moät tính chaát naøo ñoù treân file, söûa (thay theá) moät ñoái töôïng thoûa moät tính chaát naøo ñoù treân file bôûi moät ñoái töôïng khaùc. II.1. Taäp tin tuaàn töï * Thao taùc taïo file (hay nhaäp lieäu vaøo file) f : thao taùc naøy xaây döïng file maø döõ lieäu laáy töø moät nguoàn naøo ñoù, trong ñoù ta duøng haøm Boolean LaáyÑöôïcMoätÑoáiTöôïng(ÑT) Haøm naøy traû veà trò true neáu coøn laáy ñöôïc moät ñoái töôïng vaø traû veà trò false trong tröôøng hôïp ngöôïc laïi. TaïoFile (f) - Böôùc 1: Môû file f ñeå ghi môùi (hay noái theâm); - Böôùc 2: Trong khi coøn LaáyÑöôïcMoätÑoáiTöôïng(ÑT) GhiMoätÑoáiTöôïng(ÑT) vaøo file f; - Böôùc 3: Ñoùng file f; * Thao taùc duyeät file (hay khai thaùc file) f : thao taùc naøy xöû lyù taát caû caùc ñoái töôïng (moãi ñoái töôïng xeùt ñuùng moät laàn) thoûa moät tính chaát TC naøo ñoù cuûa file f. DuyeätFile (f, TC) - Böôùc 1: Môû file f ñeå ñoïc - Böôùc 2: Trong khi coøn ÑoïcÑöôïcMoätÑoáiTöôïng(ÑT) töø file f Neáu (ÑT coù tính chaát TC) thì XöûLyùÑoáiTöôïng(ÑT); // khoâng laøm thay ñoåi ÑT trong f - Böôùc 3: Ñoùng file f; Tröông Chí Tín Khoa Toaùn - Tin
  14. Giaùo trình caáu truùc döõ lieäu vaø thuaät toaùn 2 - 14 – * Thao taùc tìm (tuaàn töï) moät ñoái töôïng A ñaàu tieân coù moät tính chaát TC naøo ñoù treân file f: thao taùc naøy traû veà trò True neáu tìm thaáy vaø False trong tröôøng hôïp ngöôïc laïi. Ngoaøi ra trong tröôøng hôïp tìm thaáy ñoái töôïng A, noù coøn traû laïi vò trí baét ñaàu ÑoáiTöôïngThöù (caùc maãu tin ñöôïc ñaùnh soá baét ñaàu töø 0) cuûa A trong file f. Boolean Tìm (f, TC, &A, &ÑoáiTöôïngThöù) - Böôùc 1: Môû file f ñeå ñoïc; Thaáy ← False; ÑoáiTöôïngThöù ← -1; - Böôùc 2: Laëp laïi caùc böôùc sau: Ñoïc moät ñoái töôïng B (töø file f ); ÑoáiTöôïngThöù ← ÑoáiTöôïngThöù +1; Neáu (B coù tính chaát TC) thì: A ← B; Thaáy ← True; Cho ñeán khi: ((keát thuùc file f) hoaëc Thaáy); - Böôùc 3: Ñoùng file f; - Böôùc 4: Traû veà trò Thaáy; * Thao taùc söûa moät ñoái töôïng ñaàu tieân coù moät tính chaát TC naøo ñoù treân file f thaønh ñoái töôïng B (cuøng kieåu vôùi A): thao taùc naøy traû veà trò True neáu tìm thaáy vaø False trong tröôøng hôïp ngöôïc laïi. Boolean Söûa (f, TC, B) - Böôùc 1: Thaáy ← Tìm(f, TC, A, Thöù); - Böôùc 2: If not(Thay) SöûaÑöôïc ← False; Else Böôùc 21: Môû file f ñeå ghi (vaø ñoïc); Böôùc 22: Nhaûy ñeán ñaàu ñoái töôïng thöù Thöù; Ghi B vaøo file f; Böôùc 23: Ñoùng file f ; Böôùc 24: SöûaÑöôïc ←True; - Böôùc 3: Traû veà trò SöûaÑöôïc; * Thao taùc xoaù moät ñoái töôïng ñaàu tieân coù moät tính chaát TC naøo ñoù treân file f : thao taùc naøy traû veà trò True neáu tìm thaáy ñoái töôïng coù tính chaát TC vaø False trong tröôøng hôïp ngöôïc laïi. Boolean Xoaù (f, TC) - Böôùc 1: Thaáy ← Tìm(f, TC, A, Thöù); - Böôùc 2: If not(Thay) XoaùÑöôïc ← False; Else Tröông Chí Tín Khoa Toaùn - Tin
  15. Giaùo trình caáu truùc döõ lieäu vaø thuaät toaùn 2 - 15 – Böôùc 21: Môû file f ñeå ñoïc; Môû file phuï f_phu ñeå ghi; Böôùc 22: for (ñeám←0; ñeám
  16. Giaùo trình caáu truùc döõ lieäu vaø thuaät toaùn 2 - 16 – II.2. Taäp tin chæ muïc Khi laøm vieäc vôùi file chæ muïc, ta luoân xeùt file f (chöùa caùc ñoái töôïng thaät söï) keøm vôùi file chæ muïc f_idx töông öùng (chöùa soá thöù töï baét ñaàu cuûa caùc ñoái töôïng töông öùng trong file f). Kyù hieäu:F=(f,f_idx), EOF = -1 laø chæ soá keát thuùc file, CHÆSOÁXOÙA = -2 laø chæ soá maåu tin bò xoùa. Trong caùc thuaät toaùn cô baûn trình baøy trong phaàn naøy, ta seõ söû duïng nhöõng thao taùc sô caáp sau ñaây: - Ñoïc1ÑoáiTöôïngTrongFileDat(f, Thöù_Dat, &ÑoáiTöôïng): coù taùc duïng ñoïc 1 ñoái töôïng ÑoáiTöôïng ôû vò trí thöù Thöù_Dat töø file döõ lieäu f. Vieäc ñoïc bò thaát baïi neáu Thöù_Dat=EOF (heát file logic !) hoaëc Thöù_Dat= CHÆSOÁXOÙA (maåu tin ñaõ bò xoùa); 0 1 2=ThöùDat 3 f E C = ÑoáiTöôïng D A f_idx 3 -2 2 -1 1 Ñaõ xoùa Keát thuùc file logic - Ñoïc1ÑoáiTöôïngTrongFileIdx (f_idx, Thöù_Idx, &ChæSoáDat): coù taùc duïng ñoïc noäi dung trong file chæ muïc f_idx taïi vò trí thöù Thöù_Idx, cho keát quaû laø chæ soá ChæSoáDat trong file f (neáu ChæSoáDat =EOF: heát file logic !); 0 1 2 3 f E C D A f_idx 3 -2 2 -1 1 Thöù_Idx = 0; 1=Thöù_Idx; 2 3 Thöù_Idx =4 ChæSoáDat = 3; ChæSoáDat = -2 = CHÆSOÁXOÙA; ChæSoáDat = -1 = EOF Ñaõ xoùa Keát thuùc file logic Tröông Chí Tín Khoa Toaùn - Tin
  17. Giaùo trình caáu truùc döõ lieäu vaø thuaät toaùn 2 - 17 – - Ghi_1_PTöûTaïiVòTrí(g, Thöù, PTöû): coù taùc duïng ghi moät phaàn töû PTöû taïi vò trí thöù Thöù vaøo file g. - ThöùSau_Dat = NextDat(f_idx, ThöùTröôùc_Dat): coù taùc duïng traû laïi soá thöù töï baét ñaàu ThöùSau_Dat cuûa maåu tin keá tieáp (theo chæ muïc) cuûa maåu tin taïi vò trí thöù ThöùTröôùc_Dat trong file f (chính laø noäi dung cuûa maåu tin thöù ThöùTröôùc_Dat+1 trong file f_idx) (neáu ThöùSau_Dat =EOF: heát file logic !); 0 ThöùSau_Dat=1 2 ThöùTröôùc_Dat=3 f E C D A f_idx 3 -2 2 -1 1 (neáu ThöùTröôùc_Dat =2 thì ThöùSau_Dat=-1=EOF: heát file loâgic) - ThöùSau_Idx = NextIdx (f_idx, ThöùTröôùc_Idx, &ChæSoáDat): coù taùc duïng traû laïi noäi dung ChæSoáDat cuûa maåu tin thöù ThöùTröôùc_Idx trong file f_idx vaø soá thöù töï baét ñaàu ThöùSau_Idx (ThöùSau_Idx chính laø ChæSoáDat +1) cuûa maåu tin keá tieáp theo thöù töï chæ muïc cuûa maåu tin taïi vò trí thöù ThöùTröôùc_Idx trong file f_idx. 0 1 2 ChæSoáDat=3 f E C D A f_idx 3 -2 2 -1 1 ThöùTröôùc_Idx = 0 1 2 3 ThöùSau_Idx=4 * Thao taùc taïo file (hay nhaäp lieäu vaøo file) chæ muïc F : thao taùc naøy xaây döïng file maø döõ lieäu laáy töø moät daõy caùc ñoái töôïng naøo ñoù, trong ñoù ta duøng haøm Boolean LaáyÑöôïcMoätÑoáiTöôïng(ÑT) Haøm naøy traû veà trò true neáu coøn laáy ñöôïc moät ñoái töôïng vaø traû veà trò false trong tröôøng hôïp ngöôïc laïi. Taïo 0 1 2 3 Tröông Chí Tín Khoa Toaùn - Tin
  18. Giaùo trình caáu truùc döõ lieäu vaø thuaät toaùn 2 - 18 – f B C D A f_idx 0 1 2 3 -1 0 1 2 3 4 TaïoFileIdx (f) - Böôùc 1: Môû file F ñeå ghi; SoáÑoáiTöôïngLaáyÑöôïc ← 0; - Böôùc 2: Trong khi coøn (LaáyÑöôïcMoätÑoáiTöôïng(ÑT)), laëp laïi caùc böôùc sau: Böôùc 21: GhiMoätÑoáiTöôïng(ÑT) vaøo cuoái file f; Böôùc 22: GhiMoätSoá (SoáÑoáiTöôïngLaáyÑöôïc) vaøo cuoái file f_idx; Böôùc 23: SoáÑoáiTöôïngLaáyÑöôïc ← SoáÑoáiTöôïngLaáyÑöôïc + 1; - Böôùc 3: GhiMoätSoá (EOF) vaøo cuoái file f_idx; Ñoùng file F; * Thao taùc duyeät file chæ muïc F: thao taùc naøy xöû lyù taát caû caùc ñoái töôïng thoûa moät tính chaát TC naøo ñoù cuûa file F. Duyeät 0 1 2 3 F E C D A f_idx 3 -2 2 -1 1 ChæSoáDat = 3 0 1 2 3 Thöù_Idx =4 Ñaõ xoùa Keát thuùc file logic DuyeätIdx (F, TC) - Böôùc 1: Môû file F ñeå ñoïc; Ñoïc1ÑoáiTöôïngTrongFileIdx (f_idx, 0, &ChæSoáDat); // hay: Ñoïc 1 maåu tin (ñaàu) ChæSoáDat cuûa f_idx; - Böôùc 2: Trong khi (ChæSoáDat ≠ EOF) // hay chöa heát file loâgic laëp laïi caùc böôùc sau: Ñoïc1ÑoáiTöôïngTrongFileDat(f,ChæSoáDat,ÑoáiTöôïng); If (ÑoáiTöôïng coù tính chaát TC) XöûLyù(ÑoáiTöôïng); ChæSoáDat = NextDat(f_idx, ChæSoáDat); - Böôùc 3: Ñoùng file F; Tröông Chí Tín Khoa Toaùn - Tin
  19. Giaùo trình caáu truùc döõ lieäu vaø thuaät toaùn 2 - 19 – * Thao taùc tìm (tuaàn töï) moät ñoái töôïng ñaàu tieân (chöa bò xoùa) A coù moät tính chaát TC naøo ñoù treân file chæ muïc F: thao taùc naøy traû veà trò True neáu tìm thaáy vaø False trong tröôøng hôïp ngöôïc laïi. Ngoaøi ra, trong tröôøng hôïp tìm thaáy, noù coøn traû laïi vò trí Thöù_Idx cuûa maåu tin trong file chæ muïc f_idx maø noäi dung cuûa noù laø vò trí baét ñaàu cuûa ñoái töôïng tìm thaáy A. Tìm 0 (TC) 1 2 3 f B C D A f_idx 3 1 2 -1 0 0 1 2 3 Thöù_Idx = 4 Boolean TìmIdx (F, TC, &A, &Thöù_Idx) - Böôùc 1: Môû file F ñeå ñoïc; Thaáy ← False; Thöù_Idx ← 0; ThöùSau_Idx = NextIdx (f_idx, Thöù_Idx,ChæSoáDat); - Böôùc 2: Trong khi (ChæSoáDat ≠ EOF or Chöa Thaáy) laëp laïi caùc böôùc sau: Ñoïc1ÑoáiTöôïngTrongFileDat(f,ChæSoáDat,ÑoáiTöôïn g); If (ChæSoáDat == CHÆSOÁXOÙA) Thoâng baùo loãi caäp nhaät sai ñoái töôïng ñaõ bò xoaù; Chuyeån sang böôùc 3; If (ÑoáiTöôïng coù tính chaát TC) A ← ÑoáiTöôïng; Thaáy ← True; Else Thöù_Idx ← ThöùSau_Idx; ThöùSau_Idx = NextIdx (f_idx, Thöù_Idx,ChæSoáDat); - Böôùc 3: Ñoùng file F; - Böôùc 4: Traû veà trò Thaáy; * Thao taùc söûa moät ñoái töôïng ñaàu tieân (chöa bò xoaù) coù moät tính chaát TC naøo ñoù treân file chæ muïc F thaønh ñoái töôïng B: thao taùc naøy traû veà trò True neáu tìm thaáy ñoái töôïng caàn söûa vaø False trong tröôøng hôïp ngöôïc laïi. Tìm 0 (TC) 1 2 3 Tröông Chí Tín Khoa Toaùn - Tin
  20. Giaùo trình caáu truùc döõ lieäu vaø thuaät toaùn 2 - 20 – f E C D A f_idx 3 1 2 -1 0 0 1 2 3 Thöù_Idx =4 Söûa ChæSoáDat = 0 (TC) 1 2 3 F E C D B f_idx 3 1 2 -1 0 0 1 2 3 Thöù_Idx =4 Boolean SöûaIdx (F, TC, B) - Böôùc 1: Thaáy ← TìmIdx (F, TC, A, Thöù_Idx); - Böôùc 2: If not(Thaáy) SöûaÑöôïc ← False; Else Böôùc 21: Môû file F ñeå ghi (vaø ñoïc); Böôùc 22: Ñoïc1ÑoáiTöôïngTrongFileIdx (f_idx,Thöù_Idx,ChæSoáDat); Ghi_1_PTöûTaïiVòTrí(f, ChæSoáDat, B); Böôùc 23: Ñoùng file F; SöûaÑöôïc ←True; - Böôùc 3: Traû veà trò SöûaÑöôïc; * Thao taùc xoaù moät ñoái töôïng ñaàu tieân (chöa bò xoaù) coù moät tính chaát TC naøo ñoù treân file chæ muïc F: thao taùc naøy traû veà trò True neáu tìm thaáy ñoái töôïng caàn xoùa vaø False trong tröôøng hôïp ngöôïc laïi. Tìm 0 (TC) 1 2 3 f B C D A f_idx 3 1 2 -1 0 0 1 2 3 Thöù_Idx =4 ThöùSau_Idx = 1; ChæSoáDatSau=1 Tröông Chí Tín Khoa Toaùn - Tin
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2