Giáo trình lập trình nâng cao - Chương 4

Tài liệu tham khảo Giáo trình lập trình nâng cao trên ngôn ngữ Pascal soạn theo chương trình đã được Bộ giáo dục và đào tạo phê chuẩn - Chương 4 Con trỏ và cấu trúc động
Nội dung trích xuất từ tài liệu:
Giáo trình lập trình nâng cao - Chương 4 Chương IV Con tr và c u trúc ñ ng Chương này ñòi h i các ki n th c c a môn C u trúc d li u và gi i thu t, ñ c bi t là ki n th c v ñ li u ki u Cây. Do cách th c b trí trong k ho ch ñào t o môn này l i h c song song v i môn L p trình nâng cao nên s có m t vài khó khăn khi trình bày cũng như khi nghe gi ng. Trong chương này b n ñ c c n chú ý các v n ñ sau: Th nào là ki u d li u con tr S khác nhau gi a ki u d li u con tr và bi n con tr S phân vùng b nh cho bi n con tr Cách th c mà h th ng c p phát b nh khi chương trình ñang làm vi c Thu h i b nh dành cho t ng bi n và thu h i hàng lo t Cây và cây nh phân B nh ki u LIFO và FIFO và ng d ng trong thi t k cây nh phân Con tr m ng và m ng con tr Trư ng ð i h c Nông nghi p 1 - Giáo trình L p trình nâng cao ..............................................................- 95 1. Khái ni m Khi khai báo m t bi n, dù là bi n ñơn hay bi n thu c ki u d li u có c u trúc m c nhiên chúng ta ñã quy ñ nh ñ l n vùng nh dành cho bi n. Ví d a: Real; bi n a c n 6 byte b: aray[1..100] of Integer; bi n m ng b c n 200 byte. Vi c khai báo như trên thư ng là ph ng ñoán dung lư ng c n thi t ch không th t chính xác. ð tránh l i chúng ta thư ng khai báo dôi ra gây nên lãng phí b nh . Vi c xác ñ nh ñ a ch lưu tr bi n và c p phát b nh ñư c th c hi n khi biên d ch, nghĩa là các ñ a ch này cũng như dung lư ng b nh c n c p phát ñã ñư c c ñ nh trư c khi th c hi n các thao tác khác. Các ñ i lư ng này không thay ñ i trong su t quá trình th c hi n chương trình, nói cách khác ñây là các ñ i lư ng tĩnh. ð ti t ki m b nh , ngay khi chương trình ñang làm vi c ngư i l p trình có th yêu c u c p phát b nh cho các bi n, ñi u này ñư c g i là c p phát b nh ñ ng. C p phát b nh ñ ng ñư c th c hi n thông qua bi n con tr . Mu n có bi n con tr chúng ta ph i ñ nh nghĩa ki u con tr trư c. 2. Ki u d li u con tr - bi n con tr 2.1 Con tr có ñ nh ki u Ki u con tr là m t ki u d li u ñ c bi t dùng ñ bi u di n các ñ a ch . Ki u con tr do ngư i l p trình ñ nh nghĩa theo cú pháp sau: Type Tên ki u con tr = ^Ki u d li u; Tên ki u con tr tuân theo quy ñ nh ñ t tên c a Pascal, Ki u d li u c a ki u con tr là các ki u d li u ñã ñ nh nghĩa trư c trong pascal. ð m t ki u con tr có th ñ i di n cho m t bi n nào ñó thì Ki u d li u vi t sau ký t ^ s ph i gi ng như ki u d li u c a bi n ñó, nói cách khác hai ki u d li u ph i tương thích. Ví d 4.1 khai báo ki u con tr : Type Chu = string[20]; CT1 = ^Byte; CT2 = ^chu; CT3 = ^Nguoi; Nguoi = record Hoten:string[20]; Namsinh: 1900..2100; End; Ví d 4.1 ñ nh nghĩa ba ki u con tr , riêng ki u CT3 cách ñ nh nghĩa có v hơi ngư c là ñ nh nghĩa ki u con tr trư c, ñ nh nghĩa ki u d li u sau. Th t ra chúng ta c nên theo thói quen là ñ nh nghĩa ki u d li u trư c r i ñ nh nghĩa ki u con tr sau, cách ñ nh nghĩa CT3 ch ng qua là mu n gi i thi u ñ chúng ta bi t r ng Pascal cho phép làm ngư c l i, tuy nhiên c n nh r ng n u ñ nh nghĩa ki u con tr trư c thì ngay trong ph n Type ph i ñ nh nghĩa ki u d li u (không nh t thi t ph i li n ngay sau ñ nh nghĩa ki u con tr ). Trư ng ð i h c Nông nghi p 1 - Giáo trình L p trình nâng cao ..............................................................- 96 C n chú ý r ng Pascal ch cho phép ñưa tr c ti p vào ñ nh nghĩa ki u con tr các ki u d li u ñơn gi n sau: s nguyên, s th c, ký t . Các ki u d li u có c u trúc mu n ñưa vào con tr thì ph i thông qua m t tên ki u khai báo trong ph n Type Cách ñ nh nghĩa hai ki u con tr Hoten và Ds sau là sai: Type Hoten = ^String[20]; Ds = ^Array[1..10] of Byte; Mu n s d ng ki u chu i và m ng cho ki u con tr chúng ta ph i ñ nh nghĩa như sau: Type S1 = string[20]; Hoten = ^S1; a = array[1..10] of byte; Ds = ^a; 2.2 Bi n con tr Bi n con tr cũng như bi n m ng, bi n ki u b n ghi hay ki u t p h p có th khai báo thông qua ki u con tr ho c khai báo tr c ti p. Bi n con tr có ñ nh ki u s tr ñ n m t ki u d li u c th . ð thu n ti n t nay chúng ta dùng thu t ng Con tr thay cho thu t ng Bi n con tr Ví d 4.2 Var So: ^Integer; Sinhvien: Ct3; Hoten: Ct2; Thutu, Mahoso: ^Word; Trong ví d 4.2 chúng ta ñã khai báo ba con tr So, Thutu, Mahoso theo ki u tr c ti p, hai con tr Sinhvien và Hoten khai báo thông qua ki u ñã ñ nh nghĩa trong ví d 4.1. Con tr So tr t i ki u d li u s nguyên, con tr Sinhvien tr t i ki u d li u b n ghi còn con tr Hoten tr t i ki u d li u chu i. ð a ch c a các bi n ñ ng và bi n tĩnh s ñư c Pascal lưu tr vào bi n con tr ñi u này có nghĩa là bi n con tr không dùng ñ lưu tr các giá tr c a bi n mà là ñ a ch c a bi n. Dù kích thư c vùng d li u mà các bi n con tr tr t i khác nhau th nào thì kích thư c c a bi n con tr cũng v n là 4 byte. Các hàm và th t c x lý bi n con tr ñư c Pascal lưu tr trong Unit System. Quy ư c: Các bi n con tr g i là tương thích n u chúng tr t i cùng m t ki u d li u 2.3 Con tr không ñ nh ki u Con tr không ñ nh ki u là ki u con tr không quan tâm ñ n ki u d li u mà nó tr t i. Pascal dùng tên chu n Pointer ñ khai báo ki u này. Trư ng ð i h c Nông nghi p 1 - Giáo trình L p trình nâng cao ..............................................................- 97 Var Tên bi n:Pointer; Con tr không ñ nh ki u ñư c coi là tương thích v i m i ki u con tr . Chú ý: * V b n ch t t t c con tr ñ u ch a ñ a ch nên ch ...