Cấu trúc dữ liệu và giải thuật

Chia sẻ: 4 4 | Ngày: | Loại File: PDF | Số trang:308

Thêm vào BST

Báo xấu

55
lượt xem 9
download

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

Tham khảo sách 'cấu trúc dữ liệu và giải thuật', công nghệ thông tin, kỹ thuật lập trình 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: Cấu trúc dữ liệu và giải thuật

Please purchase a personal license. CHƯƠNG 1
Thông tin và d li u Thông tin là gì? – Là nh ng tín hi u, ký hi u, hình nh tác đ ng vào các giác quan đem l i s hi u bi t cho con ngư i – Thông tin là ngu n g c c a nh n th c D li u là gì? – Là nh ng thông tin đư c lưu tr trên các v t mang tin – B nh máy tính
Khái ni m c u trúc d li u D li u đư c lưu trong b nh máy tính và đư c x lý nên nó ph i có c u trúc D li u l n đư c xây d ng t các d li u nguyên t C u trúc d li u là mô hình c a d li u đư c lưu trong b nh Trong các ngôn ng l p trình c u trúc d li u chính là các ki u d li u
Khái ni m gi i thu t Phòng h c R i phòng h c Ð n c u thang Xu ng t ng h m Ði Các bư c th c hi n khi n quán m t ngư i mu n i n ăn t ph c v quán ăn t ph c v t phòng h c Cafeteria
Khái ni m gi i thu t Gi i thu t là dãy các bư c có th t chính xác đ gi i quy t đư c m t bài toán c th , theo đó v i m i b d li u vào gi i thu t cho m t k t qu Ví d : Gi i phương trình b c 2 – Bư c 1: Tính delta – Bư c 2 so sánh delta v i 0 >0: tính 2 nghi m x1=.., x2=… và thông báo nghi m =0: tính nghi m kép và thông báo
Các đ c trưng c a gi i thu t B d li u vào: Các DL mà gi i thu t x lý B d li u ra: Là k t qu c a vi c th c hi n gi i thu t, DL ra có quan h xác đ nh v i DL vào Tính t t đ nh: m i bư c c a gi i thu t ch cho m t k t qu duy nh t Tính d ng: Sau h u h n bư c gi i thu t d ng l i và cho k t qu Tính đúng đ n: Gi i thu t th c s gi i quy t đư c yêu c u c a bài toán Tính ph d ng: Gi i thu t gi i quy t đư c m t l p bài toán
M i quan h gi a CTDL và GT C u trúc d li u và gi i thu t là hai ph n c a m t bài toán Gi i thu t là mã l nh x lý d li u có c u trúc đ nh s n trong b nh và t o ra d li u m i Gi i thu t qui đ nh c u trúc d li u và ngư c l i C u trúc d li u + Gi i thu t = Chương trình
M i quan h gi a CTDL và GT Ví d : Bài toán tìm max c a 4 s nguyên Cách 1: Cách 2: D li u đư c lưu tr b i 4 bi n D li u đư c lưu tr b i m ng đ c l p: a, b, c, d. A[4] có 4 ph n t Khi đó gi i thu t như sau: Khi đó gi i thu t như sau: max = a; max = A[0]; if (max
Ngôn ng di n đ t gi i thu t Ngôn ng t nhiên Lư c đ kh i Ngôn ng l p trình Là các phương ti n đ ghi l i các thi t k c u trúc d li u và gi i thu t Thư ng s d ng nh t là ngôn ng l p trình
Đánh giá gi i thu t Đánh giá v b nh đ lưu tr b d li u mà gi i thu t s x lý Đánh giá v gi i thu t – Tính kh thi c a gi i thu t – Th i gian mà gi i thu t th c hi n x lý d li u
Đánh giá b nh Có 2 quan ni m: – Quan ni m 1: T ng dung lư ng nh đ lưu tr t t c các d li u mà gi i thu t x lý (tính b ng đơn v nh - bit, byte, KB…) – Quan ni m 2: T ng s ch nh đ lưu t t c các d li u T ng s ch nh g m DL vào, DL ra, và các bi n ph
Đánh giá th i gian th c hi n GT Có 2 quan ni m – Quan ni m 1: Là t ng th i gian mà gi i thu t th c hi n x lý d li u (tính b ng đơn v th i gian) – Quan ni m 2: Là t ng s phép toán cơ b n mà gi i thu t ph i th c hi n đ x lý d li u (các phép toán cơ b n: c ng, tr , nhân, chia, gán, các phép toán logic…)
Đ ph c t p gi i thu t Có 3 ki u đánh giá – Đ ph c t p trong trư ng h p t t nh t: S phép toán ít nh t mà gi i thu t ph i th c hi n đ x lý m i b d li u vào – Đ ph c t p trung bình: S phép toán trung bình mà gi i thu t ph i th c hi n đ x lý m i b d li u vào – Đ ph c t p trong trư ng h p x u nh t: S phép toán nhi u nh t mà gi i thu t ph i th c hi n đ x lý m i b d li u vào
M t s ví d Bài toán max – Vào: Dãy X có n s : X1, X2, …, Xn – Ra: Max – Gi i thu t Max = X[1]; for (i=2; i
M t s ví d Bài toán Max Xét dãy X={34 32 45 65 23 54}, n=6 Đ ph c t p b nh : 9 ch nh vào: 7 ch nh (X1, …, X6, n) ph : 1 (i) ra: 1 (Max) Đ ph c t p th i gian: 8 phép toán
Max = X[1]; for (i=2; i Max Max=45 2 phép toán i=4 -> Max Max=65 2 phép toán i=5 -> Max không gán 1 phép toán i=6 -> Max không gán 1 phép toán
M t s ví d Bài toán Max Xét dãy X={65 32 45 34 23 54}, n=6 Đ ph c t p b nh : 9 vào: 7 ph : 1 ra: 1 Đ ph c t p th i gian: 6 phép toán
M t s ví d Bài toán Max Xét dãy X={23 32 34 45 54 65}, n=6 Đ ph c t p b nh : 9 vào: 7 ph : 1 ra: 1 Đ ph c t p th i gian: 11 phép toán
M t s ví d Bài toán max – Đánh giá t ng quát – Vào: Dãy X có n s : X1, X2, …, Xn – Ra: Max Max = X[1]; – Gi i thu t for (i=2; i
M t s ví d Bài toán s p x p n i b t – Vào: Dãy X có n s : X1, X2, …, Xn – Ra: Dãy X đư c s p theo chi u tăng d n – Gi i thu t for (i=1; i