Các thuật toán cơ bản về xử lý mạng trong Pascal

Các phương pháp sắp xếp sẽ được phát triển, được mô tả, được so sánh với nhau. Các thuật toán cho nhiều vấn đề có liên quan sẽ được xem xét gồm có hàng đợi ưu tiên, phép chọn và phép trộn. Một vài nền tảng trong số này được dùng như là nền tảng cho các thuật toán khác tiếp sau trong phần này.
Nội dung trích xuất từ tài liệu:
Các thuật toán cơ bản về xử lý mạng trong Pascal S¬ lîc vÒ c¸c chñ ®Ò Sau ®©y lµ s¬ lîc vÒ c¸c chñ ®Ò sÏ ®îc ®Ò cËp trong phÇn nµy cña ch¬ng tr×nh: + PhÇn c¬ së: lµ c¸c c«ng cô vµ ph¬ng ph¸p ®îc dïng xuyªn suèt cho tÊt c¶ c¸c ch¬ng sau cña phÇn nµy. Nã gåm mét phÇn bµn luËn ng¾n vÒ Pascal, theo sau lµ giíi thiÖu vÒ c¸c cÊu tróc d÷ liÖu c¬ b¶n gåm m¶ng, x©u liªn kÕt, ng¨n xÕp, hµng ®îi vµ c©y. Chóng ta sÏ bµn luËn vÒ c«ng dông thùc tiÔn ®Ö quy vµ b¾t ®Çu híng tíi viÖc ph©n tÝch vµ tiÕp cËn thùc to¸n. + S¾p xÕp: C¸c ph¬ng ph¸p s¾p xÕp sÏ ®îc ph¸t triÓn, ®îc m« t¶, ®îc so s¸nh víi nhau. C¸c thuËt to¸n cho nhiÒu vÊn ®Ò cã liªn quan sÏ ®îc xem xÐt gåm cã hµng ®îi u tiªn, phÐp chän vµ phÐp trén. Mét vµi nÒn t¶ng trong sè nµy ®îc dïng nh lµ nÒn t¶ng cho c¸c thuËt to¸n kh¸c tiÕp sau trong phÇn nµy. + Xö lý chuçi: gåm mét lo¹t c¸c ph¬ng ph¸p ®Ó ph©n tÝch c©u. C¸c ky thuËt nÐn tËp vµ mËt m· còng sÏ ®îc kh¶o s¸t. Còng vËy, mét giíi thiÖu vÒ c¸c chñ ®Ò n©ng cao cïng ®îc cung cÊp qua viÖc xem xÐt mét vµi bµi to¸n c¬ b¶n quan träng trong ph¹m vi cña chóng. + H×nh häc: lµ mét sù tËp hîp cã chän läc c¸c ph¬ng ph¸p ®Ó gi¶i quyÕt c¸c bµi to¸n liªn quan ®Õn ®iÓm vµ ®êng ( vµ c¸c ®èi t îng h×nh häc ®¬n gi¶n kh¸c ). Chóng ta sÏ xem xÐt c¸c thuËt to¸n ®Ó t×m bao låi cña mét tËp ®iÓm, phÇn giao cña c¸c ®èi t îng, ®Ó gi¶i bµi to¸n ®iÓm gÇn nhÊt, t×m kiÕm nhiÒu chiÒu ... + §å thÞ: Mét chiÕn lîc tæng qu¸t ®Ó t×m kiÕm trªn c¸c ®å thÞ sÏ ®îc ph¸t triÓn vµ ®îc ¸p dông cho c¸c bµi to¸n liªn th«ng c¬ b¶n, gåm cã ®- êng ®i ng¾n nhÊt, c©y liªn th«ng tèi thiÓu, m¹ng vµ so khíp. Mét sù xem xÐt thèng nhÊt ®èi víi c¸c thuËt to¸n nµy chøng tá r»ng tÊt c¶ ®Òu dùa vµo mét thñ tôc vµ thñ tôc nµy phô thuéc vµo mét cÊu tróc d÷ liÖu c¬ b¶n ®· ph¸t triÓn tr íc ®ã. + C¸c thuËt to¸n to¸n häc: gåm c¸c ph¬ng ph¸p c¬ b¶n tõ sè häc vµ c¸c sè nguyªn, ®a thøc, vµ ma trËn còng nh c¸c thuËt to¸n ®Ó gi¶i quyÕt cac vÊn ®Ò to¸n häc mµ nã ph¸t sinh trong nhiÒu ng÷ c¶nh : viÖc t¹o sè ngÉu nhiªn, lìi gi¶i cña c¸c ch¬ng tr×nh ®ång thêi, xÊp xØ d÷ liÖu, 1 vµ lÊy tÝch ph©n. Sù nhÊn m¹nh thiªn vÒ c¸c khÝa c¹nh thuËt to¸n cña ph¬ng ph¸p, chø kh«ng ph¶i trªn nÒn t¶ng cña to¸n häc + C¸c chñ ®Ò cao cÊp: ®îc th¶o luËn nh»m môc ®Ých liªn hÖ c¸c chñ ®Ò trong tËp s¸ch nµy víi nhiÒu lÜnh vùc nghiªn cøu cao cÊp kh¸c. PhÇn cøng chuyªn dông, quy ho¹ch ®éng, quy ho¹ch tuyÕn tÝnh, t×m kiÕm- vÐt c¹n ... I. Sắp xếp: 1. Kh¸i niÖm: a) S¾p xÕp lµ mét qu¸ tr×nh tæ chøc l¹i mét d·y c¸c d÷ liÖu theo mét trËt tù nhÊt ®Þnh. b) Môc ®Ých cña viÖc s¾p xÕp lµ nh»m gióp cho viÖc t×m kiÕm d÷ liÖu mét c¸ch dÔ dµng vµ nhanh chãng. S¾p xÕp lµ mét viÖc lµm hÕt søc c¬ b¶n vµ ®îc dïng réng r·i trong c¸c kÜ thuËt lËp tr×nh nh»m sö lý d÷ liÖu. c) C¸c gi¶i thuËt s¾p xÕp ®îc ph©n chia thµnh hai nhãm chÝnh lµ: - S¾p xÕp trong (hay s¾p xÕp m¶ng). Toµn bé c¬ së d÷ liÖu cÇn s¾p xÕp ph¶i ®îc ®a vµo bé nhí chÝnh cña m¸y tÝnh. Do ®ã nã th êng ®îc sö dông khi khèi lîng d÷ liÖu kh«ng vît qu¸ dung lîng bé nhí chÝnh. Nhãm s¾p xÕp trong bao gåm c¸c ph¬ng ph¸p : * Ph¬ng ph¸p ®Õm. * Ph¬ng ph¸p chÌn. * Ph¬ng ph¸p chän. * Ph¬ng ph¸p ®æi chæ. * Ph¬ng ph¸p trén. - S¾p xÕp ngoµi (hay s¾p xÕp tËp tin). VËn dông trong tr êng hîp ta ph¶i s¾p xÕp c¸c tËp tin chøa nhiÒu mÉu tin vµ mçi mÉu tin cã chiÒu dµi t ¬ng ®èi lín do ®ã ta kh«ng thÓ n¹p toµn bé vµo bé nhí chÝnh ®Ó s¾p xÕp thø tù. V× vËy ta ph¶i cã nh÷ng ph¬ng ph¸p thÝch hîp cho viÖc s¾p xÕp tËp tin. 2. S¾p xÕp trong: a) Kh¸i niÖm: 2 CÊu tróc d÷ liÖu thÝch hîp cho c¸c phÇn tö cÇn s¾p xÕp thø tù lµ Record. Mçi phÇn tö cã hai vïng ®Æc tr ¬ng lµ: Vïng Key ®Ó chøa kho¸ cña phÇn tö vµ ®îc sö dông trong c¸c gi¶i thuËt t×m kiÕm, vïng info dïng ®Ó chøa ®÷ liÖu c¸c phÇn tö. Ta khai b¸o : Type Item = Record key : Integer; Info : Integer; End; Var A : Array[1..n] of Item; Kho¸ cña phÇn tö cã thÓ lµ ch÷ hoÆc sè. Yªu cÇu gi¶i thÝch lµ dïng Ýt vïng nhí vµ thêi gian thùc hiÖn nhanh. b) Ph¬ng ph¸p ®Õm (Counting sort) * Gi¶i thÝch: Néi dung cña ph¬ng ph¸p nµy lµ ®Õm c¸c phÇn tö cã kho¸ nhá h¬n hay b»ng kho¸ cña c¸c phÇn tö A[i]. NÕu cã j phÇn tö cã kho¸ nhá h¬n kho¸ cña phÇn tö A[i] th× phÇn tö A[i] sÏ cã vÞ trÝ theo thø tù (j+1) trong d·y ®· cã thø tù. Trong gi¶i thuËt, ta dïng m¶ng Count[i] ( i = 1, 2, .. n ) víi Count[i] cho biÕt sè phÇn tö cã kho¸ nhá h¬n kho¸ cña phÇn tö A[i]. Nh vËy Count[i+1] lµ vÞ trÝ cña phÇn tö A[i] trong d·y ®· cã thø tù. * VÝ dô: S¾p xÕp d·y 2 3 1 5 2 7 6 9 4 i: 1 2 3 4 5 6 7 8 Count: 20416573 Nh vËy phÇn tö cã kho¸ 9 ë vÞ trÝ 8 v× Count[9]=7. * ThÓ hiÖn b»ng Pascal: Procedure Count_Sort; Var Count : Array[1..n] of Integer; A : Array[1..n] of Item; i,j : Integer; Begin 3 For i := 1 to n do Count[i] := 0; For i := n downto 2 do For j := i-1 downto 1 do If A[i].Key < A[j].Key Then Count[j] := Count[j] + 1 Else Count[i] := Count[i] + 1; For i := 1 to n do S[Count[i] + 1] := A[i]; For i := 1 to n do A[i] := S[i]; End; c) Ph¬ng ph¸p chÌn (Insertion Sort) * Gi¶i thÝch: Néi dung cña ph¬ng ph¸p nµy lµ gi¶ sö ta cã d·y A[1]..A[i-1] ®· cã thø tù, cã ph¶i x¸c ®Þnh vÞ trÝ thÝch hîp cña phÇn tö A[i] trong d·y A[1]..A[i - 1] b»ng ph¬ng ph¸p t×m kiÕm tuÇn tù tõ A[i - 1] trë vÒ A[1] ®Ó t×m ra vÞ trÝ thÝch hîp cña A[i]. Ta chÌn A[i] vµo vÞ trÝ nµy vµ kÕt qu¶ lµ ®·y A[1] .. A[i] cã thø tù. Ta ¸p dông c¸ch lµm nµy víi i = 2, 3, ..., n. * VÝ dô: Ta ph¶i s¾p xÕp d·y sè: 39 50 7 37 89 13 1 62 i=2 39 50 7 37 89 13 1 62 i=3 39 50 7 37 89 13 1 62 i=4 7 39 50 37 89 13 1 62 i=5 7 37 39 50 89 13 1 6 ...