Giáo trình Cấu trúc dữ liệu - thuật toán – PGS. TS. Đinh Mạnh Tường

Nội dung của giáo trình "Cấu trúc dữ liệu - thuật toán" bao gồm 8 chương với các nội dung: thuật toán và phân tích thuật toán; kiểu dữ liệu, cấu trúc dữ liệu và mô hình dữ liệu; danh sách; cây; tập hợp; bảng; các cấu trúc dữ liệu ở bộ nhớ ngoài.
Nội dung trích xuất từ tài liệu:
Giáo trình Cấu trúc dữ liệu - thuật toán – PGS. TS. Đinh Mạnh TườngGT Cấu Trúc Dữ Liệu – Thuật Toán PTS- Đinh Mạnh Tường Lêi nãi ®Çu S¸ch nµy tr×nh bµy c¸c cÊu tróc d÷ liÖu (CTDL) vµ thuËt to¸n. C¸c kiÕn thøcvÒ CTDL vµ thuËt to¸n ®ãng vai trß quan träng trong viÖc ®µo t¹o cö nh©n tin häc.S¸ch nµy ®ù¬c h×nh thµnh trªn c¬ së c¸c bµi gi¶ng vÒ CTDL vµ thuËt to¸n mµ t«i®· ®äc nhiÒu n¨m t¹i khoa To¸n-C¬-Tin häc vµ khoa C«ng nghÖ th«ng tin §¹i häckhoa häc tù nhiªn, §¹i häc quèc gia Hµ néi. S¸ch ®îc viÕt chñ yÕu ®Ó lµm tµi liÖutham kh¶o cho sinh viªn c¸c Khoa C«ng nghÖ th«ng tin, nhng nã còng rÊt bæ Ýchcho c¸c ®éc gi¶ kh¸c cÇn cã hiÓu biÕt ®Çy ®ñ h¬n vÒ CTDL vµ thuËt to¸n. Chóng t«i m« t¶ c¸c CTDL vµ c¸c thuËt to¸n trong ng«n ng÷ Pascal, v×Pascal lµ ng«n ng÷ ®îc nhiÒu ngêi biÕt ®Õn vµ lµ ng«n ng÷ ®îc sö dông nhiÒu®Ó tr×nh bµy thuËt to¸n trong s¸ch b¸o. S¸ch nµy gåm hai phÇn. PhÇn 1 nãi vÒ c¸c CTDL, phÇn 2 nãi vÒ thuËt to¸n.Néi dung cña phÇn 1 gåm c¸c ch¬ng sau ®©y. Ch¬ng 1 tr×nh bµy c¸c kh¸i niÖmc¬ b¶n vÒ thuËt to¸n vµ ph©n tÝch thuËt to¸n. Ch¬ng 2 tr×nh bµy c¸c kh¸i niÖmCTDL, m« h×nh d÷ liÖu, kiÓu d÷ liÖu trõu tîng (DLTT). Ch¬ng 3 tr×nh bµy c¸cm« h×nh d÷ liÖu, danh s¸ch vµ c¸c ph¬ng ph¸p cµi ®Æt danh s¸ch (bëi m¶ng vµ bëiCTDL danh s¸ch liªn kÕt). Hai kiÓu DLTT ®Æc biÖt quan träng lµ hµng vµ ng¨n xÕp(stack) còng ®îc xÐt trong ch¬ng nµy. Ch¬ng nµy còng tr×nh bµy mét sè øngdông cña danh s¸ch, hµng, ng¨n xÕp trong thiÕt kÕ thuËt to¸n. Ch¬ng 4 tr×nh bµym« h×nh d÷ liÖu c©y, c¸c ph¬ng ph¸p cµi ®Æt c©y, c©y nhÞ ph©n, c©y t×m kiÕm nhÞph©n vµ c©y c©n b»ng. Ch¬ng 5 nãi vÒ m« h×nh d÷ liÖu tËp hîp, c¸c ph¬ng ph¸pcµi ®Æt tËp hîp, tõ ®iÓn vµ cµi ®Æt tõ ®iÓn bëi b¶ng b¨m, hµng u tiªn vµ cµi ®Æthµng u tiªn bëi heap. Ch¬ng 6 ®Ò cËp ®Õn ph¬ng ph¸p cµi ®Æt c¸c d¹ng b¶ngkh¸c nhau. C¸c CTDL ë bé nhí ngoµi (file b¨m, file chØ sè, B-c©y) ®îc tr×nh bµytrong ch¬ng 7. T¸c gi¶ PTS §inh M¹nh Têng.Sưu Tầm Bởi : daihoc.com.vn 2GT Cấu Trúc Dữ Liệu – Thuật Toán PTS- Đinh Mạnh Tường môc lôcCh¬ng I: ThuËt to¸n vµ ph©n tÝch thuËt to¸n 5 1.1. ThuËt to¸n 5 1.1.1. Kh¸i niÖm thuËt to¸n. 5 1.1.2. BiÓu diÔn thuËt to¸n. 7 1.1.3. C¸c vÊn ®Ò liªn quan ®Õn thuËt to¸n. 8 1.2. Ph©n tÝch thuËt to¸n 9 1.2.1. TÝnh hiÖu qu¶ cña thuËt to¸n. 9 1.2.2. T¹i sao l¹i cÇn thuËt to¸n cã hiÖu qu¶. 10 1.2.3. §¸nh gi¸ thßi gian thùc hiÖn thuËt to¸n nh thÕ n¸o. 11 1.2.4. Ký hiÖu « lín vµ ®¸nh gi¸ thêi gian thùc hiÖn thuËt to¸n b»ng ký hiÖu « lín. 12 1.2.5. C¸c qui t¾c ®¸nh gi¸ thêi gian thùc hiÖn thuËt to¸n. 14 1.2.6. Ph©n tÝch mét sè thuËt to¸n. 17Ch¬ng II: KiÓu d÷ liÖu, cÊu tróc d÷ liÖu vµ m« h×nh d÷ liÖu. 20 2.1. BiÓu diÔn d÷ liÖu. 20 2.2. KiÓu d÷ liÖu vµ cÊu tróc d÷ liÖu. 21 2.3. HÖ kiÓu cña ng«n ng÷ Pascal. 23 2.4. M« h×nh d÷ liÖu vµ kiÓu d÷ liÖu trõu tîng. 27Ch¬ng III: Danh s¸ch 32 3.1. Danh s¸ch. 32 3.2. Cµi ®Æt danh s¸ch bëi m¶ng. 34 3.3. T×m kiÕm trªn danh s¸ch. 37 3.3.1. VÊn ®Ò t×m kiÕm. 37 3.3.2. T×m kiÕm tuÇn tù. 38 3.3.3. T×m kiÕm nhÞ ph©n. 39 3.4. CÊu tróc d÷ liÖu danh s¸ch liªn kÕt. 41 3.4.1. Danh s¸ch liªn kÕt. 41 3.4.2. C¸c phÐp to¸n trªn danh s¸ch liªn kÕt. 42 3.4.3. So s¸nh hai ph¬ng ph¸p. 47 3.5. C¸c d¹ng danh s¸ch liªn kÕt kh¸c. 47 3.5.1. Danh s¸ch vßng trßn. 47 3.5.2. Danh s¸ch hai liªn kÕt. 51 3.6. øng dông danh s¸ch. 53 3.7. Stack. 57 3.7.1. Stack. 57 3.7.2. Cµi ®Æt stack bëi m¶ng. 58 3.7.3. Cµi ®Æt stack bëi danh s¸ch liªn kÕt. 60 3.8. Gi¸ trÞ cña mét biÓu thøc. 63 3.9. Hµng. 68Sưu Tầm Bởi : daihoc.com.vn 3GT Cấu Trúc Dữ Liệu – Thuật Toán PTS- Đinh Mạnh Tường 3.9.1. Hµng. 68 3.9.2. Cµi ®Æt hµng bëi m¶ng. 68 3.9.3. Cµi ®Æt hµng bëi m¶ng vßng trßn. 71 3.9.4. Cµi ®Æt hµng bëi danh s¸ch liªn kÕt. 73Ch¬ng IV: C©y. 76 4.1. C©y vµ c¸c kh¸i ...