Chapter 3 - DANH SÁCH

Trong chương này, chúng ta sẽ nghiên cứu danh sách, một trong các mô hình dữ liệu quan trọng nhất, được sử dụng thường xuyên trong các thuật toán. Các phương pháp khác nhau để cài đặt danh sách sẽ được xét. Chúng ta sẽ phân tích hiệu quả của các phép toán trên danh sách trong mỗi cách cài đặt. Hai kiểu dữ liệu trừu tượng đặc biệt quan trọng là stack (ngăn xếp) và hàng (hàng đợi) sẽ được nghiên cứu. Chúng ta cũng sẽ trình bày một số ứng dụng của danh sách....
Nội dung trích xuất từ tài liệu:
Chapter 3 - DANH SÁCH Ch¬ng 3 danh s¸ch Trong ch¬ng nµy, chóng ta sÏ nghiªn cøu danh s¸ch, mét trong c¸cm« h×nh d÷ liÖu quan träng nhÊt, ®îc sö dông thêng xuyªn trong c¸cthuËt to¸n. C¸c ph¬ng ph¸p kh¸c nhau ®Ó cµi ®Æt danh s¸ch sÏ ®îc xÐt.Chóng ta sÏ ph©n tÝch hiÖu qu¶ cña c¸c phÐp to¸n trªn danh s¸ch trongmçi c¸ch cµi ®Æt. Hai kiÓu d÷ liÖu trõu tîng ®Æc biÖt quan träng lµstack (ng¨n xÕp) vµ hµng (hµng ®îi) sÏ ®îc nghiªn cøu. Chóng ta còngsÏ tr×nh bµy mét sè øng dông cña danh s¸ch. 3.1. Danh s¸ch.cïng mét líp c¸c ®èi tîng nµo ®ã. Ch¼ng h¹n, ta cã thÓ VÒ mÆtto¸n häc, danh s¸ch lµ mét d·y h÷u h¹n c¸c phÇn tö thuéc nãi ®Õn danhs¸ch c¸c sinh viªn cña mét líp, danh s¸ch c¸c sè nguyªn nµo ®ã, danhs¸ch c¸c b¸o xuÊt b¶n hµng ngµy ë thñ ®«, ... Gi¶ sö L lµ danh s¸ch cã n (n ≥ 0) phÇn tö L = (a1, a2, ..., an) Ta gäi sè n lµ ®é dµi cña cña danh s¸ch. NÕu n ≥1 th× a1 ®îc gäilµ phÇn tö ®Çu tiªn cña danh s¸ch, cßn an lµ phÇn tö cuèi cïng cñadanh s¸ch. NÕu n = 0 tøc danh s¸ch kh«ng cã phÇn tö nµo, th× danhs¸ch ®îc gäi lµ rçng. Mét tÝnh chÊt quan träng cña danh s¸ch lµ c¸c phÇn tö cña nã ®-îc s¾p tuyÕn tÝnh : nÕu n > 1 th× phÇn tö ai ®i tríc phÇn tö ai+1 hay®i s©u phÇn tö ai víi i = 1,2, ..., n-1. Ta sÏ nãi ai (i = 1,2, ..., n) lµ phÇntö ë vÞ trÝ thø i cña danh s¸ch. CÇn chó ý r»ng, mét ®èi tîng cã thÓ xuÊt hiÖn nhiÒu lÇn trongmét danh s¸ch. Ch¼ng h¹n nh trong danh s¸ch c¸c sè ngµy cña c¸c th¸ngtrong mét n¨m (31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31) Danh s¸ch con. NÕu L = (a1, a2, ..., an) lµ mét danh s¸ch vµ i, j lµ c¸c vÞ trÝ, 1 ≤ i ≤j ≤ n th× danh s¸ch L = (b1, b2, ..., bj-i+1) trong ®ã b1 = ai , b2 = ai+1) ... bj-i+1=aj, Nh vËy, danh s¸ch con L gåm tÊt c¶ c¸c phÇn tö tõ a i ®Õn aj cñadanh s¸ch L. Danh s¸ch rçng ®îc xem lµ danh s¸ch con cña mét danhs¸ch bÊt kú. 32 Danh s¸ch con bÊt kú gåm c¸c phÇn tö b¾t ®Çu tõ phÇn tö ®Çutiªn cña danh s¸ch L ®îc gäi lµ phÇn ®Çu (prefix) cña danh s¸ch L.PhÇn cuèi (postfix) cña danh s¸ch L lµ mét danh s¸ch con bÊt kú kÕtthóc ë phÇn tö cuèi cïng cña danh s¸ch L. D·y con Mét danh s¸ch ®îc t¹o thµnh b»ng c¸ch lo¹i bá mét sè (cã thÓb»ng kh«ng) phÇn tö cña danh s¸ch L ®îc gäi lµ d·y con cña danh s¸chL. VÝ dô. XÐt danh s¸ch L = (black, blue, green, cyan, red, brown, yellow) Khi ®ã danh s¸ch (blue, green, cyan, red) lµ danh s¸ch con cña L.Danh s¸ch (black, green, brown) lµ d·y con cña L. Danh s¸ch (black,blue, green) lµ phÇn ®Çu, cßn danh s¸ch (red, brown, yellow) lµ phÇncuèi cña danh s¸ch L. C¸c phÐp to¸n trªn danh s¸ch. Chóng ta ®· tr×nh bµy kh¸i niÖm to¸n häc danh s¸ch. Khi m« t¶mét m« t¶ mét m« h×nh d÷ liÖu, chóng ta cÇn x¸c ®Þnh c¸c phÐp to¸ncã thÓ thùc hiÖn trªn m« h×nh to¸n häc ®îc dïng lµm c¬ së cho m«h×nh d÷ liÖu. Cã rÊt nhiÒu phÐp to¸n trªn danh s¸ch. Trong c¸c øngdông, th«ng thêng chóng ta chØ sö dông mét nhãm c¸c phÐp to¸n nµo®ã. Sau ®©y lµ mét sè phÐp to¸n chÝnh trªn danh s¸ch. Gi¶ sö L lµ mét danh s¸ch (List), c¸c phÇn tö cña nã cã kiÓu d÷liÖu Item nµo ®ã, p lµ mét vÞ trÝ (position) trong danh s¸ch. C¸c phÐpto¸n sÏ ®îc m« t¶ bëi c¸c thñ tôc hoÆc hµm. 1. Khëi t¹o danh s¸ch rçng procedure Initialize (var L : List) ; 2. X¸c ®Þnh ®é dµi cña danh s¸ch. function Length (L : List) : integer 3. Lo¹i phÇn tö ë vÞ trÝ thø p cña danh s¸ch procedure Delete (p : position ; var L : List) ; 4. Xen phÇn tö x vµo danh s¸ch sau vÞ trÝ thø p procedure Insert After (p : position ; x : Item ; var L: List) ; 5. Xen phÇn tö x vµo danh s¸ch tríc vÞ trÝ thø p procedure Insert Before (p : position ; x : Item ; var L:List) ; 6. T×m xem trong danh s¸ch cã chøa phÇn tö x hay kh«ng ? procedure Search (x : Item ; L : List : var found : boolean) ; 33 7. KiÓm tra danh s¸ch cã rçng kh«ng ? function Empty (L : List) : boolean ; 8. KiÓm tra danh s¸ch cã ®Çy kh«ng ? function Full (L : List) : boolean ; 9. §i qua dah s¸ch. Trong nhiÒu ¸p dông chóng ta cÇn ph¶i ®i quadanh s¸ch, tõ ®Çu ®Õn hÕt danh s¸ch, vµ thùc hiÖn mét nhãm hµnh®éng nµo ®ã víi mçi phÇn tö cña danh s¸ch. procedure Traverse (var L : List) ; 10. C¸c phÐp to¸n kh¸c. Cßn cã thÓ kÓ ra nhiÒu phÐp to¸n kh¸c.Ch¼ng h¹n truy cËp ®Õn phÇn tö ë vÞ trÝ thø i cña danh s¸ch (®Ótham kh¶o hoÆc thay thÕ), kÕt hîp hai danh s¸ch thµnh mét danh s¸ch,ph©n tÝch mét danh s¸ch thµnh nhiÒu danh s¸ch, ... VÝ dô : Gi¶ sö L lµ danh s¸ch L = (3,2,1,5). Khi ®ã, thùc hiÖnDelete (3,L) ta ®îc danh s¸ch (3,2,5). KÕt qu¶ cña InsertBefor (1, 6, L)lµ danh ...