Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 - Châu Thị Bảo Hà

Chia sẻ: Kiếp Này Bình Yên | Ngày: | Loại File: PDF | Số trang:75

Thêm vào BST

Báo xấu

65
lượt xem 4
download

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

Chương 1 giúp người học ôn tập lại các kiến thức về C/C++ như: Cấu trúc chương trình C/C++, các cú pháp cơ bản, địa chỉ (Address), con trỏ (Pointer), mảng (Array),...và các nội dung khác. Mời các bạn cùng tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 - Châu Thị Bảo Hà

CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT (DATA STRUCTURE AND ALGORITHMS) GV: Châu Thị Bảo Hà 1 Email: chauthibaoha@gmail.com Blog: http://ctbha.wordpress.com
Nội dung môn học  Chương 0: Giới thiệu chung về CTDL và GT  Chương 1: Ôn tập C/C++ (C/C++ Review)  Chương 2: Đệ quy (Recursion)  Chương 3: Tìm kiếm (Searching)  Chương 4: Sắp xếp (Sorting)  Chương 5: Ngăn xếp - Hàng đợi (Stacks - Queues)  Chương 6: Danh sách liên kết (Linked List)  Chương 7: Cây (Tree) 2 Chương 1: Ôn tập C/C++
Đánh giá kết quả 1. Kiểm tra giữa kỳ: thực hành  Điểm < 4  không được thi kết thúc môn  học lại 2. Kiểm tra cuối kỳ: thực hành  Điểm < 5  không được thi kết thúc môn  học lại 3. Bài tập lớn: làm các bài tập trong module  Điểm < 5  không được thi kết thúc môn  học lại 4. Thi kết thúc môn: trắc nghiệm 5. Kiểm tra thường kỳ 3 Chương 1: Ôn tập C/C++
Tài liệu học tập  Giáo trình:  C & Data Structures, P. S. Deshpande, O. G. Kakde - CHARLES RIVER MEDIA, INC. Hingham, Massachusetts.  Tham khảo:  Giáo trình Cấu trúc dữ liệu 1, Trần Hạnh Nhi – Dương Anh Đức, Trường ĐHKHTN – ĐHQG TP.HCM.  Phần mềm lập trình:  C-Free  Borland C++  … 4 Chương 1: Ôn tập C/C++
Nhắc nhở một số quy định  Đi học đúng giờ  Đeo thẻ SV  Không để chuông điện thoại reo trong giờ học  Không nghe điện thoại, nhắn tin trong giờ học  Không nói chuyện riêng, làm ồn khi nghe giảng  Mang đầy đủ tài liệu học tập của môn học: giáo trình, bài tập, tập chép bài (hoặc slide bài giảng), usb lưu bài tập  Phải làm bài tập ở nhà  Nếu vi phạm: Nhắc nhở chung  Bị mời ra khỏi lớp  Xóa tên khỏi môn học 5 Chương 1: Ôn tập C/C++
Chương 0: Giới thiệu chung 6
Nội dung  Cấu trúc dữ liệu  Thuật toán  Độ phức tạp của thuật toán 7 Chương 1: Ôn tập C/C++
Cấu trúc dữ liệu  (1) Sự tổ chức hợp lý của các thành phần dữ liệu,  (2) Tập các thao tác để truy cập các thành phần dữ liệu.  Ví dụ:  Mảng (Array)  Danh sách liên kết (Linked List)  Ngăn xếp (Stack)  Hàng đợi (Queue)  Cây (Tree) …  (1) the logical arrangement of data elements, combined with  (2) the set of operations we need to access the elements. 8 Chương 1: Ôn tập C/C++
Thuật toán  Tập các bước có thể tính toán được để đạt được kết quả mong muốn (A computable set of steps to achieve a desired result)  Ví dụ: Tính tổng các số nguyên lẻ từ 1n  B1: S=0  B2: i=1  B3: Nếu i>n thì sang B7, ngược lại sang B4  B4: S=S+i  B5: i=i+2  B6: Quay lại B3  B7: Tổng cần tìm là S 9 Chương 1: Ôn tập C/C++
Mối quan hệ của CTDL và thuật toán CTDL + Thuật toán = Chương trình 10 Chương 1: Ôn tập C/C++
Ví dụ Cách 1: Sử dụng mảng một chiều Cách 2 : Sử dụng mảng 2 chiều int result [ 12 ] = {7, 9, 5, 2, int result[3][4] ={{ 7, 9, 5, 2}, 5, 0, 9, 4, { 5, 0, 9, 4}, 6, 3, 7, 4}; { 6, 3, 7, 4 }}; so_mon = 4; so_mon = 4, so_sv =3; for (int i=0; i
Các tiêu chuẩn đánh giá cấu trúc dữ liệu  Phản ánh đúng thực tế  là tiêu chuẩn quan trọng nhất, quyết định tính đúng đắn của toàn bộ bài toán  Phù hợp với các thao tác trên đó  tăng tính hiệu quả: phát triển các thuật toán đơn giản, tự nhiên hơn; đạt hiệu quả cao hơn về tốc độ xử lý  Tiết kiệm tài nguyên hệ thống  Cấu trúc dữ liệu chỉ nên sử dụng tài nguyên hệ thống vừa đủ để đảm nhiệm được chức năng của nó 12 Chương 1: Ôn tập C/C++
Thời gian thực hiện thuật toán  Thời gian giải quyết một bài toán phụ thuộc vào nhiều yếu tố  Tốc độ thực thi của máy tính (CPU,…)  Tài nguyên (bộ nhớ,…)  Thuật toán  Làm thế nào đánh giá? 13 Chương 1: Ôn tập C/C++
Độ phức tạp thuật toán  Để đánh giá hiệu quả của một thuật toán, có thể tính số lượng các phép tính phải thực hiện của thuật toán này:  Phép so sánh  Phép gán  Thông thường số các phép tính được thực hiện phụ thuộc vào cỡ của bài toán, tức là độ lớn của đầu vào (n)  Vì thế độ phức tạp thuật toán là một hàm phụ thuộc đầu vào  Tuy nhiên, không cần biết chính xác hàm này mà chỉ cần biết một ước lượng đủ tốt của chúng  Để ước lượng độ phức tạp của một thuật toán ta thường dùng khái niệm Big-O 14 Chương 1: Ôn tập C/C++
Ví dụ  Bước 1. Gán Tổng = 0. Gán i = 0  Bước 2. int tong=0, i=0; – Tăng i thêm 1 đơn vị do{ – Gán Tổng = Tổng + i i++;  Bước 3. So sánh i với n tong+=i; – Nếu i < n, quay lại bước 2 }while (i
Các độ phức tạp thường gặp (GT.53)  Độ phức tạp hằng số: O(1) – thời gian chạy không phụ thuộc vào độ lớn đầu vào  Độ phức tạp tuyến tính: O(n) – thời gian chạy tỉ lệ thuận với độ lớn đầu vào  Độ phức tạp logarit: O(logn)  Độ phức tạp đa thức: O(P(n)), với P là đa thức có bậc từ 2 trở lên  Độ phức tạp hàm mũ: O(2n) 16 Chương 1: Ôn tập C/C++
Bảng so sánh các độ phức tạp của thuật toán  Một số lớp thuật toán 17 Chương 1: Ôn tập C/C++
Thứ tự độ phức tạp của thuật toán O(2n) Độ phức tạp cao, khó chấp nhận 18 n! Chương 1: Ôn tập C/C++
Chương 1: Ôn tập C/C++ (Tham khảo tài liệu môn Phương Pháp Lập Trình) 1 9
Chương 1: Ôn tập C/C++ 1. Cấu trúc chương trình C/C++  2. Các cú pháp cơ bản 3. Địa chỉ (Address) 4. Con trỏ (Pointer) 5. Mảng (Array) 6. Cấu trúc (Structure) 7. Con trỏ cấu trúc (Structure pointer) 8. Chuỗi (String) 9. Tập tin (File) 10. Hàm (Function) 20