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à

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.
Nội dung trích xuất từ tài liệu:
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 chung6 Nội dung  Cấu trúc dữ liệu  Thuật toán  Độ phức tạp của thuật toán7 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à S9 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ình10 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ềuint 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 ...