- C U TRÚC D LI U GI I THU T Lê Văn Hạnh
[email protected] M C TIểU MỌN H C Sau khi hoàn tất, sinh viên có thể.
- Nhận thức đ ợc sự cần thiết của việc thiết kế cấu trúc dữ liệu.
- Rèn luyện khả năng t duy logic, phát triển các thuật toán, chọn lựa việc tổ chức dữ liệu phù hợp và các giải thuật xử lý dữ liệu có hiệu quả trong từng bài toán cụ thể.
- Hiểu và vận dụng đ ợc • Các thuật toán sắp xếp và tìm kiếm trên mảng 1 chiều.
- Các cấu trúc stacks, queues, linked list, binary tree, binary search tree, Balanced Binary Search Tree.
- Nguyễn Quốc C ng, Hoàng Đức Hải, Cấu trúc dữ liệu + Giải thuật = Chương trình, sách dịch, NXB Giáo Dục – 1999 2.
- Đinh Mạnh T ng, Cấu trúc dữ liệu và Thuật toán, NXB Khoa Học và Kỹ Thuật – 2000 3.
- 60% GI I THI U - Hầu hết các bài toán đều có nhiều giải thuật khác nhau để giải quyết chúng.
- Vậy làm thế nào chọn đ ợc m t giải thuật tốt nhất.
- Đ phức tạp tính toán của giải thuật • Nhu cầu về dung l ợng b nh.
- Giải thuật rõ ràng, dễ hiểu, dễ mã hóa và hiệu chỉnh.
- ii.Giải thuật sử dụng có hiệu quả tài nguyên của máy tính và đặc biệt chạy càng nhanh càng tốt.
- N I DUNG MỌN H C - Ch ơng 1: Ôn tập về Ngôn ngữ lập trình - Chương 2: Đệ quy - Chương 3: Các giải thuật tìm kiếm trên mảng 1 chiều - Chương 4: Các giải thuật sắp xếp trên mảng 1 chiều - Chương 5: Danh sách liên kết đ ng (Linked List.
- Gi i thiệu vai trò của tổ chức dữ liệu iii.
- Mối quan hệ giữa giải thuật & cấu trúc dữ liệu iv.
- Tổng quan về đánh giá đ phức tạp giải thuật 8 N I DUNG 1.
- Kiểu dữ liệu 2.
- Cấu trúc dữ liệu 4.
- Giải thuật 5.
- Đ phức tạp của giải thuật 6.
- Vai trò của cấu trúc dữ liệu & giải thuật 9 1.
- KI U D LI U Xét đoạn ch ơng trình sau: void main.
- KI U D LI U 1.1.
- Khái ni m v ki u d li u T.
- Các thu c tính của m t kiểu dữ liệu gồm.
- T: Tên kiểu dữ liệu • V: Miền giá trị (th ng phụ thu c vào kích th c l u trữ.
- O: Tập các xử lý tác đ ng lên kiểu dữ liệu đó Ví dụ: Kiểu dữ liệu số nguyên char trong ngôn ngữ C T = char void main() V .
- KI U D LI U 1.2.
- Phân loại ki u d li u - Ki u ếữ ệi u tĩnể (kiểu dữ liệu cơ bản.
- Kiểu cơ s : Số nguyên, số thực và kiểu logic • Kiểu dãy (mảng), xâu ký tự • Kiểu có cấu trúc • Kiểu tập tin - Ki u ếữ ệi u độnỂ • Danh sách liên kết • Hàng đợi • Ngăn xếp • Cây • Bảng băm.
- Phân loại ki u d li u Ki u ếữ ệi u Tĩnể Ki u ếữ ệi u ĐộnỂ - Đ ợc định nghĩa th i - Đ ợc gắn kết v i m t con điểm biên dịch.
- KI U D LI U 1.3.
- Ki u d li u tĩnh - Ki u s nguyên Stt Tên ki u Ghi chú Kích thước Ký tự 1 byte 1 char Sô nguyên 1 byte 2 unsigned char Sô nguyên d ơng 1 byte 3 short Sô nguyên 2 bytes 4 unsigned short Số nguyên d ơng 2 bytes 5 int Sô nguyên 4 bytes 6 unsigned int Số nguyên d ơng 4 bytes 7 long Sô nguyên 4 bytes 8 unsigned long Sô nguyên d ơng 4 bytes - Ki u s th c Stt Tên ki u Ghi chú Kích thước 1 float 4 bytes 2 double 8 bytes 3 long double 8 bytes - Ki u lu n lỦ (C.
- Ki u d li u tĩnh - Ki u m ng 1 chi u Gi t ị Vị trí hỉàsố 0 1 2 … n-2 n-1 • Khai báo.
- Ki u d li u tĩnh - Ki u có c u trúc • Khai báo stru t tê _stru t { khai o thuộ tí h.
- KI U D LI U 1.4.
- Ki u d li u đ ng ậ Bi n con tr - Khi sử dụng phải cấp phát biến con trỏ bằng lệnh new, hủy bằng lệnh delete - M ng 1 chi u.
- Ki u d li u đ ng ậ Bi n con tr - Truy c p thƠnh ph n c a bi n • Biến cấu trúc kiểu tĩnh (cấu trúc): dùng d u ch m giữa tên biến và thu c tính thành phần VD: Khai báo tr c đó: Khi sử dụng: struct stDate DATE d.
- Biến cấu trúc kiểu con trỏ: dùng dấu chấm giữa tên biến và thu c tính thành phần ->th hàphầ à ấuàtr VD: Khi sử dụng: DATE *d.
- Input: Các giả thiết, thông tin đ ợc cung cấp • Output: kết quả cần đạt đ ợc những yêu cầu nào? B2: Lựa chọn cấu trúc dữ liệu sẽ sử dụng trong cài đặt ch ơng trình (Process) B3: Thiết kế giải thuật: mô tả trình tự các thao tác trên m t số đối t ợng nào đó sao cho m t số hữu hạn lần thực hiện ta thu đ ợc kết quả nh mong đợi 19 3.C U TRÚC D LI U 3.1.
- Khái ni m - Cách thức liên kết/ tổ chức các kiểu dữ liệu cơ s / kiểu dữ liệu có cấu trúc hợp lý để sử dụng m t cách hiệu quả - Tập các thao tác để truy cập/ xử lý các thành phần dữ liệu 3.2.
- GI I THU T (HAY THU T GI I) 4.1 Khái ni m - Giải thuật là một t p ểợp ểữu ểạn của các chỉ thị hay ph ơng cách đ ợc định nghĩa rõ ràng cho việc hoàn tất m t số sự việc từ m t trạng thái ban đầu cho tr c.
- Gi i thu t 4.2.
- Các ph ng pháp bi u di n gi i thu t 4.2.1.
- Các ph ng pháp bi u di n gi i thu t 4.2.2.
- Mô t gi i thu t b ng mư gi (PSEUDOCODE.
- Các ph ng pháp bi u di n gi i thu t 4.2.3.
- Mô t gi i thu t b ng l u đ (FLOWCHART.
- CáẾ Ệý ểi u ếùnỂ mô tả Ểiải tểu t bằnỂ ệ u đ KÝ HI U Ý NGHƾA Bắt đầu/kết thúc Dữ liệu vào Xuất dữ liệu Lệnh hoặc nhóm lệnh để thực hiện 1 chức năng nào đó của ch ơng trình Ch ơng trình con đư định nghĩa tr c đó Quyết định h ng xử lý sẽ rẽ vào nhánh nào tùy vào việc thỏa điều kiện đư ghi trong khối.
- Các ph ng pháp bi u di n gi i thu t 4.2.4.
- Mô t gi i thu t b ng 3 ph ng pháp - Bài tểựẾ ểànể 1: Cho số nguyên n.
- Giải thuật dùng Mã tự nhiên.
- Giải thuật dùng Flowchart.
- Bướ à :à hậpà Bướ à :à ếuà < àth à à:=à à*à -1) BEGIN Bướ à :à uấtà n • Giải thuật dùng Pseudocode: n0