TÀI LIỆU GIÁO KHOA CHUYÊN TIN - QUYỂN 2

Chia sẻ: Nguyễn Văn Toàn | Ngày: | Loại File: PDF | Số trang:240

Thêm vào BST

Báo xấu

312
lượt xem 104
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tham khảo sách 'tài liệu giáo khoa chuyên tin - quyển 2', tài liệu phổ thông, tin học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:

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

Lưu

Nội dung Text: TÀI LIỆU GIÁO KHOA CHUYÊN TIN - QUYỂN 2

Hå sÜ ®µm (Chñ biªn) ®ç ®øc ®«ng – lª minh hoµng – nguyÔn thanh hïng tµi liÖu gi¸o khoa chuyªn tin quyÓn 2 Nhµ xuÊt b¶n gi¸o dôc viÖt nam
C«ng ty Cæ phÇn dÞch vô xuÊt b¶n Gi¸o dôc H Néi - Nh xuÊt b¶n Gi¸o dôc ViÖt Nam gi÷ quyÒn c«ng bè t¸c phÈm. 349-2009/CXB/43-644/GD M sè : 8I746H9 2
L I NÓI ð U B Giáo d c và ðào t o ñã ban hành chương trình chuyên tin h c cho các l p chuyên 10, 11, 12. D a theo các chuyên ñ chuyên sâu trong chương trình nói trên, các tác gi biên so n b sách chuyên tin h c, bao g m các v n ñ cơ b n nh t v c u trúc d li u, thu t toán và cài ñ t chương trình. B sách g m ba quy n, quy n 1, 2 và 3. C u trúc m i quy n bao g m: ph n lí thuy t, gi i thi u các khái ni m cơ b n, c n thi t tr c ti p, thư ng dùng nh t; ph n áp d ng, trình bày các bài toán thư ng g p, cách gi i và cài ñ t chương trình; cu i cùng là các bài t p. Các chuyên ñ trong b sách ñư c l a ch n mang tính h th ng t cơ b n ñ n chuyên sâu. V i tr i nghi m nhi u năm tham gia gi ng d y, b i dư ng h c sinh chuyên tin h c c a các trư ng chuyên có truy n th ng và uy tín, các tác gi ñã l a ch n, biên so n các n i dung cơ b n, thi t y u nh t mà mình ñã s d ng ñ d y h c v i mong mu n b sách ph c v không ch cho giáo viên và h c sinh chuyên PTTH mà c cho giáo viên, h c sinh chuyên tin h c THCS làm tài li u tham kh o cho vi c d y và h c c a mình. V i kinh nghi m nhi u năm tham gia b i dư ng h c sinh, sinh viên tham gia các kì thi h c sinh gi i Qu c gia, Qu c t H i thi Tin h c tr Toàn qu c, Olympiad Sinh viên Tin h c Toàn qu c, Kì thi l p trình viên Qu c t khu v c ðông Nam Á, các tác gi ñã l a ch n gi i thi u các bài t p, l i gi i có ñ nh hư ng ph c v cho không ch h c sinh mà c sinh viên làm tài li u tham kh o khi tham gia các kì thi trên. L n ñ u t p sách ñư c biên so n, th i gian và trình ñ có h n ch nên ch c ch n còn nhi u thi u sót, các tác gi mong nh n ñư c ý ki n ñóng góp c a b n ñ c, các ñ ng nghi p, sinh viên và h c sinh ñ b sách ñư c ngày càng hoàn thi n hơn . Các tác gi 3
4
Chuyên ñ 6 KI U D LI U TR U TƯ NG VÀ C U TRÚC D LI U Ki u d li u tr u tư ng là m t mô hình toán h c v i nh ng thao tác ñ nh nghĩa trên mô hình ñó. Ki u d li u tr u tư ng có th không t n t i trong ngôn ng l p trình mà ch dùng ñ t ng quát hóa ho c tóm lư c nh ng thao tác s ñư c th c hi n trên d li u. Ki u d li u tr u tư ng ñư c cài ñ t trên máy tính b ng các c u trúc d li u: Trong k thu t l p trình c u trúc (Structural Programming), c u trúc d li u là các bi n cùng v i các th t c và hàm thao tác trên các bi n ñó. Trong k thu t l p trình hư ng ñ i tư ng (Object- Oriented Programming), c u trúc d li u là ki n trúc th b c c a các l p, các thu c tính và phương th c tác ñ ng lên chính ñ i tư ng hay m t vài thu c tính c a ñ i tư ng. Trong chương này, chúng ta s kh o sát m t vài ki u d li u tr u tư ng cũng như cách cài ñ t chúng b ng các c u trúc d li u. Nh ng ki u d li u tr u tư ng ph c t p hơn s ñư c mô t chi ti t trong t ng thu t toán m i khi th y c n thi t. 1. Danh sách 1.1. Khái ni m danh sách Danh sách là m t t p s p th t các ph n t cùng m t ki u. ð i v i danh sách, ngư i ta có m t s thao tác: Tìm m t ph n t trong danh sách, chèn m t ph n t vào danh sách, xóa m t ph n t kh i danh sách, s p x p l i các ph n t trong danh sách theo m t tr t t nào ñó v.v… Vi c cài ñ t m t danh sách trong máy tính t c là tìm m t c u trúc d li u c th mà máy tính hi u ñư c ñ lưu các ph n t c a danh sách ñ ng th i vi t các ño n chương trình con mô t các thao tác c n thi t ñ i v i danh sách. 5
J Vì danh sách là m t t p s p th t các ph n t cùng ki u, ta ký hi u J có là ki u d li u c a các ph n t trong danh sách, khi cài ñ t c th , th là b t c ki u d li u nào ñư c chương trình d ch ch p nh n (S nguyên, s th c, ký t , …). 1.2. Bi u di n danh sách b ng m ng Khi cài ñ t danh sách b ng m ng m t chi u , ta c n có m t bi n nguyên J lưu s ph n t hi n có trong danh sách. N u m ng ñư c ñánh s b t ñ u t 1 thì các ph n t trong danh sách ñư c c t gi trong m ng b ng các ph n t ñư c ñánh s t 1 t i J: I{ J{ a) a) Truy c p ph n t trong m ng v trí J trong m ng có th th c hi n r t d dàng qua Vi c truy c p m t ph n t ph n t I . Vì các ph n t c a m ng có kích thư c b ng nhau và ñư c lưu tr liên t c trong b nh , vi c truy c p m t ph n t ñư c th c hi n b ng m t phép toán tính ñ a ch ph n t có th i gian tính toán là h ng s . Vì v y n u cài ñ t t p là ß{ {. b ng m ng, vi c truy c p m t ph n t trong danh sách v trí b t kỳ có ñ ph c b) b) Chèn ph n t vào m ng vào m ng t i v trí J, trư c h t ta d n t t c các ph n t ð chèn m t ph n t t v trí J t i t i v trí J v sau m t v trí (t o ra “ch tr ng” t i v trí J), ñ t giá tr vào v trí J, và tăng s ph n t c a m ng lên 1. procedure Insert(p: Integer; const v: TElement); //Th t c chèn ph n t v vào v trí p var i: Integer; begin for i := n downto p do a[i + 1] := a[i]; a[p] := v; n := n + 1; end; (J J - ), khi ñó th i gian th c hi n c a phép chèn là ß{ {. Trư ng h p x u Trư ng h p t t nh t, v trí chèn n m sau ph n t cu i cùng c a danh sách nh t, ta c n chèn t i v trí 1, khi ñó th i gian th c hi n c a phép chèn là ß{J{. 6
chèn là ß{J{. Cũng d dàng ch ng minh ñư c r ng th i gian th c hi n trung bình c a phép c) c) Xóa ph n t kh i m ng ð xóa m t ph n t t i v trí J c a m ng mà v n gi nguyên th t các ph n t còn l i: Trư c h t ta ph i d n t t c các ph n t t v trí J - t i J lên trư c m t v trí (thông tin c a ph n t th J b ghi ñè), sau ñó gi m s ph n t c a m ng (J) ñi . procedure Delete(p: Integer); //Th t c xóa ph n t t i v trí p var i: Integer; begin for i := p to n - 1 do a[i] := a[i + 1]; n := n - 1; end; Trư ng h p t t nh t, v trí xóa n m cu i danh sách (J J{, khi ñó th i gian th c hi n c a phép xóa là ß{ {. Trư ng h p x u nh t, ta c n xóa t i v trí 1, khi ñó th i gian th c hi n c a phép xóa là ß{J{. Cũng d dàng ch ng minh ñư c r ng th i gian th c hi n trung bình c a phép xóa là ß{J{. Trong trư ng h p c n xóa m t ph n t mà không c n duy trì th t c a các ph n ph n t c a m ng (J) ñi 1. Khi ñó th i gian th c hi n c a phép xóa ch là ß{ {. t khác, ta ch c n ñưa giá tr ph n t cu i cùng vào v trí c n xóa r i gi m s 1.3. Bi u di n danh sách b ng danh sách n i ñơn Danh sách n i ñơn (Singly-linked list) g m các nút ñư c n i v i nhau theo m t chi u. M i nút là m t b n ghi (record) g m hai trư ng: Trư ng J J ch a giá tr lưu trong nút ñó Trư ng J ch a liên k t (con tr ) t i nút k ti p, t c là ch a m t thông tin ñ ñ bi t nút k ti p nút ñó trong danh sách là nút nào, trong trư ng h p là nút cu i cùng (không có nút k ti p), trư ng liên k t này ñư c gán m t giá tr ñ c bi t, ch ng h n con tr J . JJ J type PNode = ^TNode; //Ki u con tr t i m t nút TNode = record; //Ki u bi n ñ ng ch a thông tin trong m t nút 7
info: TElement; link: PNode; end; Nút ñ u tiên trong danh sách ( I ) ñóng vai trò quan tr ng trong danh sách n i ñơn. ð duy t danh sách n i ñơn, ta b t ñ u t nút ñ u tiên, d a vào trư ng liên k t ñ ñi sang nút k ti p, ñ n khi g p giá tr ñ c bi t (duy t qua nút cu i) thì d ng l i a b c d e I Hình 1.1. Danh sách n i ñơn a) Truy c p ph n t trong danh sách n i n B n thân danh sách n i ñơn ñã là m t ki u d li u tr u tư ng. ð cài ñ t ki u d li u tr u tư ng này, chúng ta có th dùng m ng các nút (trư ng J ch a ch s c a nút k ti p) ho c bi n c p phát ñ ng (trư ng J ch a con tr t i nút k ti p). Tuy nhiên vì c u trúc n i ñơn, vi c xác ñ nh ph n t ñ ng th J trong danh sách b t bu c ph i duy t t ñ u danh sách qua J nút, vi c này m t th i gian trung bình ß{J{, và t ra không hi u qu như thao tác trên m ng. Nói cách khác, danh sách n i ñơn ti n l i cho vi c truy c p tu n t nhưng không hi u qu n u chúng ta th c hi n nhi u phép truy c p ng u nhiên. b) Chèn ph n t vào danh sách n i n ð chèn thêm m t nút ch a giá tr vào v trí c a nút J trong danh sách n i J ch a giá tr và cho nút này liên ñơn, trư c h t ta t o ra m t nút m i k t t i J. N u J ñang là nút ñ u tiên c a danh sách ( I ) thì c p nh t l i I J , còn n u J không ph i nút ñ u tiên c a danh sách, ta tìm nút J b ng là nút ñ ng li n trư c nút J và ch nh l i liên k t: J liên k t t i J thay vì liên k t t i th ng J (h.1.2). 8
a b c d e I J J a b c d e I J J J Hình 1.2. Chèn ph n t vào danh sách n i ñơn procedure Insert(p: PNode; const v: TElement); //Th t c chèn ph n t v vào v trí nút p var NewNode, q: PNode; begin New(NewNode); NewNode^.info := v; NewNode^.link := p; if head = p then head := NewNode else begin q := head; while q^.link ≠ p do q := q^.link; q^.link := NewNode; end; end; gian ß{ {, tuy nhiên vi c tìm nút ñ ng li n trư c nút J yêu c u ph i duy t t Vi c ch nh l i liên k t trong phép chèn ph n t vào danh sách n i ñơn m t th i ñ u danh sách, vi c này m t th i gian trung bình ß{J{. V y phép chèn m t ph n t vào danh sách n i ñơn m t th i gian trung bình ß{J{ ñ th c hi n. c) Xóa ph n t kh i danh sách n i n: ð xóa nút J kh i danh sách n i ñơn, g i J là nút ñ ng li n sau J trong danh sách. Xét hai trư ng h p: N u J là nút ñ u tiên trong danh sách I J thì ta ñ t l i I b ng J. 9
N u J không ph i nút ñ u tiên trong danh sách, tìm nút J là nút ñ ng li n trư c nút J và ch nh l i liên k t: J liên k t t i J thay vì liên k t t i J (h.1.3) Vi c cu i cùng là hu nút J. procedure Delete(p: PNode); //Th t c xóa nút p c a danh sách n i ñơn var next, q: PNode; begin next := p^.link; if p = head then head := next else begin q := head; while q^.link p do q := q^.link; q^.link := next; end; Dispose(p); end; a b c d e J J J I a b d e J J I Hình 1.3. Xóa ph n t kh i danh sách n i ñơn m t th i gian trung bình ß{J{ ñ th c hi n. Cũng gi ng như phép chèn, phép xóa m t ph n t kh i danh sách n i ñơn cũng Trên ñây mô t các thao tác v i danh sách bi u di n dư i d ng danh sách n i ñơn các bi n ñ ng. Chúng ta có th cài ñ t danh sách n i ñơn b ng m t m ng, m i nút ch a trong m t ph n t c a m ng và trư ng liên k t J chính là ch s c a nút k ti p. Khi ñó m i thao tác chèn/xóa ph n t cũng ñư c th c hi n tương t như trên: const max = ...; //S ph n t c c ñ i type TNode = record 10
info: TElement; link: Integer; end; TList = array[1..max] of TNode; var Nodes: TList; head: Integer; 1.4. Bi u di n danh sách b ng danh sách n i kép Vi c xác ñ nh nút ñ ng li n trư c m t nút J trong danh sách n i ñơn b t bu c ph i duy t t ñ u danh sách, thao tác này m t th i gian trung bình ß{J{ ñ th c hi n và nh hư ng tr c ti p t i th i gian th c hi n thao tác chèn/xóa ph n t . ð kh c ph c như c ñi m này, ngư i ta s d ng danh sách n i kép. Danh sách n i kép g m các nút ñư c n i v i nhau theo hai chi u. M i nút là m t b n ghi (record) g m ba trư ng: Trư ng info ch a giá tr lưu trong nút ñó. Trư ng J ch a liên k t (con tr ) t i nút k ti p, t c là ch a m t thông tin ñ ñ bi t nút k ti p nút ñó là nút nào, trong trư ng h p nút ñ ng cu i cùng trong danh sách (không có nút k ti p), trư ng liên k t này ñư c gán m t giá tr ñ c bi t (ch ng h n con tr J ) Trư ng JJ ch a liên k t (con tr ) t i nút li n trư c, t c là ch a m t thông tin ñ ñ bi t nút li n trư c nút ñó là nút nào, trong trư ng h p nút JJ JJ J ñ ng ñ u tiên trong danh sách (không có nút li n trư c), trư ng liên k t này ñư c gán m t giá tr ñ c bi t (ch ng h n con tr J ) type PNode = ^TNode; //Ki u con tr t i m t nút TNode = record; //Ki u bi n ñ ng ch a thông tin trong m t nút info: TElement; next, prev: PNode; end; Khác v i danh sách n i ñơn, trong danh sách n i kép ta quan tâm t i hai nút: Nút ñ u tiên ( JJ ) và ph n t cu i cùng ( IJ ). Có hai cách duy t danh sách JJ , d a vào liên k t J n i kép: Ho c b t ñ u t ñ ñi sang nút k ti p, ñ n 11
khi g p giá tr ñ c bi t (duy t qua IJ ) thì d ng l i. Ho c b t ñ u t IJ , d a vào liên k t JJ ñ ñi sang nút li n trư c, ñ n khi g p giá tr ñ c bi t (duy t qua JJ ) thì d ng l i JJ a b c d e IJ Hình 1.4. Danh sách n i kép Gi ng như danh sách n i ñơn, vi c chèn/xóa nút trong danh sách n i kép cũng ñơn gi n ch là k thu t ch nh l i các m i liên k t gi a các nút cho h p lý. Tuy trong th i gian ß{ {, nên các thao tác chèn/xóa trên danh sách n i kép ch m t nhiên ta có th xác ñ nh ñư c d dàng nút ñ ng li n trư c/li n sau c a m t nút th i gian ß{ {, t t hơn so v i cài ñ t b ng m ng hay danh sách n i ñơn. 1.5. Bi u di n danh sách b ng danh sách n i vòng ñơn Trong danh sách n i ñơn, ph n t cu i cùng trong danh sách có trư ng liên k t ñư c gán m t giá tr ñ c bi t (thư ng s d ng nh t là giá tr J ). N u ta cho trư ng liên k t c a ph n t cu i cùng tr th ng v ph n t ñ u tiên c a danh sách thì ta s ñư c m t ki u danh sách m i g i là danh sách n i vòng ñơn. a b c d e Hình 1.5. Danh sách n i vòng ñơn ð i v i danh sách n i vòng ñơn, ta ch c n bi t m t nút b t kỳ c a danh sách là ta có th duy t ñư c h t các nút trong danh sách b ng cách ñi theo hư ng liên k t. Chính vì lý do này, khi chèn/xóa vào danh sách n i vòng ñơn, ta không ph i n i vòng ñơn v n c n th i gian trung bình ß{J{ ñ th c hi n thao tác chèn/xóa x lý các trư ng h p riêng khi nút ñ ng ñ u danh sách. M c dù v y, danh sách vì vi c xác ñ nh nút ñ ng li n trư c m t nút cho trư c cũng g p tr ng i như v i danh sách n i ñơn. 12
1.6. Bi u di n danh sách b ng danh sách n i vòng kép Danh sách n i vòng ñơn ch cho ta duy t các nút c a danh sách theo m t chi u, n u cài ñ t b ng danh sách n i vòng kép thì ta có th duy t các nút c a danh sách c theo chi u ngư c l i n a. Danh sách n i vòng kép có th t o thành t danh sách n i kép n u ta cho trư ng JJ c a nút JJ tr t i nút HIJ còn trư ng J c a nút IJ thì tr t i nút JJ . chèn/xóa ph n t có th th c hi n trong th i gian ß{ {. Tương t như danh sách n i kép, danh sách n i vòng kép cho phép thao tác a b c d e Hình 1.6. Danh sách n i vòng kép 1.7. Bi u di n danh sách b ng cây Có nhi u thao tác trên danh sách, nhưng nh ng thao tác ph bi n nh t là truy c p ph n t , chèn và xóa ph n t . Ta ñã kh o sát cách cài ñ t danh sách b ng m ng ho c danh sách liên k t, n u như m ng cho phép thao tác truy c p ng u nhiên t t hơn danh sách liên k t, thì thao tác chèn/xóa ph n t trên m ng l i m t khá nhi u th i gian. Dư i ñây là b ng so sánh th i gian th c hi n các thao tác trên danh sách. Phương pháp Truy c p ng u nhiên Chèn Xóa Θ{ { Θ{J{ Θ{J{ M ng Θ{J{ Θ{J{ Θ{J{ Danh sách n i ñơn Θ{J{ Θ{ { Θ{ { Danh sách n i kép Θ{ { Θ{J{ Θ{J{ Danh sách n i vòng ñơn Θ{J{ Θ{ { Θ{ { Danh sách n i vòng kép Cây là m t ki u d li u tr u tư ng mà trong m t s trư ng h p có th gián ti p dùng ñ bi u di n danh sách. V i m t cách ñánh s th t cho các nút c a cây (duy t theo th t gi a), m i phép truy c p ng u nhiên, chèn, xóa ph n t trên 13
danh sách có th th c hi n trong th i gian { J{. Chúng ta s ti p t c ch ñ này trong m t bài riêng. Bài t p 1.1. Vi t chương trình th c hi n các phép chèn, xóa, và tìm ki m m t ph n t trong danh sách các s nguyên ñã s p x p theo th t tăng d n bi u di n b i: M ng Danh sách n i ñơn Danh sách n i kép 1.2. Vi t chương trình n i hai danh sách s nguyên ñã s p x p, t ng quát hơn, vi t chương trình n i danh sách s nguyên ñã s p x p ñ ñư c m t danh sách g m t t c các ph n t . 1.3. Gi s chúng ta bi u di n m t ña th c J{ { I# - I$ -- I , trong ñó I# 2 I$ 2 2 I dư i d ng m t danh sách n i ñơn mà nút th c a danh sách ch a h s I , s mũ I và con tr t i nút k ti p (nút - ). Hãy tìm thu t toán c ng và nhân hai ña th c theo các bi u di n này. 1.4. M t s nh phân I I # I" , trong ñó I { { có giá tr b ng (" I . Ngư i ta bi u di n s nh phân này b ng m t danh sách n i ñơn g m J nút, có nút ñ u danh sách ch a giá tr I , m i nút trong danh sách ch a m t ch s nh phân I và con tr t i nút k ti p là nút ch a ch s nh phân I # . Hãy l p chương trình th c hi n phép toán “c ng 1” trên s nh phân ñã cho và ñưa ra bi u di n nh phân c a k t qu . G i ý: S d ng phép ñ quy 2. Ngăn x p và hàng ñ i Ngăn x p và hàng ñ i là hai ki u d li u tr u tư ng r t quan tr ng và ñư c s d ng nhi u trong thi t k thu t toán. V b n ch t, ngăn x p và hàng ñ i là danh sách t c là m t t p h p các ph n t cùng ki u có tính th t . 14
Trong ph n này chúng ta s tìm hi u ho t ñ ng c a ngăn x p và hàng ñ i và cách cài ñ t chúng b ng các c u trúc d li u. Tương t như danh sách, ta g i J. ki u d li u c a các ph n t s ch a trong ngăn x p và hàng ñ i là J có th là ki u s nguyên, s Khi cài ñ t chương trình c th , ki u th c, ký t , hay b t kỳ ki u d li u nào ñư c chương trình d ch ch p nh n. 2.1. Ngăn x p Ngăn x p (Stack) là m t ki u danh sách mà vi c b sung m t ph n t và lo i b m t ph n t ñư c th c hi n cu i danh sách. Có th hình dung ngăn x p như m t ch ng ñĩa, ñĩa nào ñư c ñ t vào ch ng sau cùng s n m trên t t c các ñĩa khác và s ñư c l y ra ñ u tiên. Vì nguyên t c “vào sau ra trư c”, ngăn x p còn có tên g i là danh sách ki u LIFO (Last In First Out). V trí cu i danh sách ñư c g i là ñ nh (top) c a ngăn x p. ð i v i ngăn x p có sáu thao tác cơ b n: HJ : Kh i t o m t ngăn x p r ng HJ J : Cho bi n ngăn x p có r ng không? HJ : Cho bi t ngăn x p có ñ y không? : ð c giá tr ph n t ñ nh ngăn x p J : ð y m t ph n t vào ngăn x p JJ: L y ra m t ph n t t ngăn x p a) a) Bi u di n ng n x p b ng m ng Cách bi u di n ngăn x p b ng m ng c n có m t m ng H J ñ lưu các ph n t trong ngăn x p và m t bi n nguyên JJ ñ lưu ch s c a ph n t t i ñ nh ngăn x p. Ví d : const max = ...; //Dung lư ng c c ñ i c a ngăn x p type TStack = record items: array[1..max] of TElement; top: Integer; end; var Stack: TStack; Sáu thao tác cơ b n c a ngăn x p có th vi t như sau: 15
//Kh i t o ngăn x p r ng procedure Init; begin Stack.top := 0; end; //Hàm ki m tra ngăn x p có r ng không? function IsEmpty: Boolean; begin Result := Stack.top = 0; end; //Hàm ki m tra ngăn x p có ñ y không? function IsFull: Boolean; begin Result := Stack.top = max; end; //ð c giá tr ph n t ñ nh ngăn x p function Get: TElement; begin if IsEmpty then Error ← "Stack is Empty" //Báo l i ngăn x p r ng else with Stack do Result := items[top]; //Tr v ph n t ñ nh ngăn x p end; //ð y m t ph n t x vào ngăn x p procedure Push(const x: TElement); begin if IsFull then Error ← "Stack is Full" //Báo l i ngăn x p ñ y else with Stack do begin top := top + 1; //Tăng ch s ñ nh Stack items[top] := x; //ð t x vào v trí ñ nh Stack end; end; //L y m t ph n t ra kh i ngăn x p function Pop: TElement; begin 16
if IsEmpty then Error ← "Stack is Empty" //Báo l i ngăn x p r ng else with Stack do begin Result := items[top]; //Tr v ph n t ñ nh ngăn x p top := top - 1; //Gi m ch s ñ nh ngăn x p end; end; b) b) Bi u di n ng n x p b ng danh sách n i n ki u LIFO Ta s trình bày cách cài ñ t ngăn x p b ng danh sách n i ñơn các bi n ñ ng và con tr . Trong cách cài ñ t này, ngăn x p s b ñ y n u như vùng không gian nh dùng cho các bi n ñ ng không còn ñ ñ thêm m t ph n t m i. Tuy nhiên, vi c ki m tra ñi u này ph thu c vào máy tính, chương trình d ch và ngôn ng l p trình. M t khác, không gian b nh dùng cho các bi n ñ ng thư ng r t l n nên ta s không vi t mã cho hàm HJ : Ki m tra ngăn x p tràn. Các khai báo d li u: type PNode = ^TNode; //Ki u con tr liên k t gi a các nút TNode = record //Ki u d li u cho m t nút info: TElement; link: PNode; end; var top: PNode; //Con tr t i ph n t ñ nh ngăn x p Các thao tác trên ngăn x p: //Kh i t o ngăn x p r ng procedure Init; begin top := nil; end; //Ki m tra ngăn x p có r ng không function IsEmpty: Boolean; begin Result := top = nil; end; 17
//ð c giá tr ph n t ñ nh ngăn x p function Get: TElement; begin if IsEmpty then Error ← "Stack is Empty" //Báo l i ngăn x p r ng else Result := top^.info; end; //ð y m t ph n t x vào ngăn x p procedure Push(const x: TElement); var p: PNode; begin New(p); //T o nút m i p^.info := x; p^.link := top; //N i vào danh sách liên k t top := p; //D ch con tr ñ nh ngăn x p end; //L y m t ph n t kh i ngăn x p function Pop: TElement; var p: PNode; begin if IsEmpty then Error ← "Stack is Empty" //Báo l i ngăn x p r ng else begin Result := top^.info; //L y ph n t t i con tr top p := top^.link; Dispose(top); //Gi i phóng b nh top := P; //D ch con tr ñ nh ngăn x p end; end; 2.2. Hàng ñ i Hàng ñ i (Queue) là m t ki u danh sách mà vi c b sung m t ph n t ñư c th c hi n cu i danh sách và vi c lo i b m t ph n t ñư c th c hi n ñ u danh sách. 18
Khi cài ñ t hàng ñ i, có hai v trí quan tr ng là v trí ñ u danh sách ( JJJ ), nơi các ph n t ñư c l y ra, và v trí cu i danh sách (J IJ), nơi ph n t cu i cùng ñư c ñưa vào. Có th hình dung hàng ñ i như m t ñoàn ngư i x p hàng mua vé: Ngư i nào x p hàng trư c s ñư c mua vé trư c. Vì nguyên t c “vào trư c ra trư c”, hàng ñ i còn có tên g i là danh sách ki u FIFO (First In First Out). Tương t như ngăn x p, có sáu thao tác cơ b n trên hàng ñ i: HJ : Kh i t o m t hàng ñ i r ng HJ J : Cho bi n hàng ñ i có r ng không? HJ : Cho bi t hàng ñ i có ñ y không? : ð c giá tr ph n t ñ u hàng ñ i J : ð y m t ph n t vào hàng ñ i JJ: L y ra m t ph n t t hàng ñ i a) Bi u di n hàng i b ng m ng Jñ Ta có th bi u di n hàng ñ i b ng m t m ng lưu các ph n t trong hàng ñ i, m t bi n nguyêfJJJ ñ lưu ch s ph n t ñ u hàng ñ i và m t bi n nguyên J IJ ñ lưu ch s ph n t cu i hàng ñ i. Ch m J t ph n c a m ng t v trí JJJ t i J IJ ñư c s d ng lưu tr các ph n t trong hàng ñ i. Ví d : const max = ...; //Dung lư ng c c ñ i type TQueue = record items: array[1..max] of TElement; front, rear: Integer; end; var Queue: TQueue; Sáu thao tác cơ b n trên hàng ñ i có th vi t như sau: //Kh i t o hàng ñ i r ng procedure Init; begin Queue.front := 1; Queue.rear := 0; end; //Ki m tra hàng ñ i có r ng không 19
function IsEmpty: Boolean; begin Result := Queue.front > Queue.rear; end; //Ki m tra hàng ñ i có ñ y không function IsFull: Boolean; begin Result := Queue.rear = max; end; //ð c giá tr ph n t ñ u hàng ñ i function Get: TElement; begin if IsEmpty then Error ← "Queue is Empty" //Báo l i hàng ñ i r ng else with Queue do Result := items[front]; end; //ð y m t ph n t x vào hàng ñ i procedure Push(const x: TElement); begin if IsFull then Error ← "Queue is Full" //Báo l i hàng ñ i ñ y else with Queue do begin rear := rear + 1; items[rear] := x; end; end; //L y m t ph n t kh i hàng ñ i function Pop: TElement; begin if IsEmpty then Error ← "Queue is Empty" //Báo l i hàng ñ i r ng else with Queue do begin Result := items[front]; 20