Bài giảng Cấu trúc dữ liệu cơ bản và giải thuật

Nội dung text: Bài giảng Cấu trúc dữ liệu cơ bản và giải thuật

1. Chương I CẤU TRÚC DỮ LIỆU CƠ BẢN VÀ GIẢI THUẬT
2. 1. Vai trò của cấu trúc dữ liệu: Xây dựng một đề án tin học thực chất là chuyển bài toán thực tế thành một bài toán có thể giải quyết trên máy tính Mà một bài toán thực tế bất kỳ đều bao gồm các đối tượng dữ liệu và các yêu cầu xử lý trên các đối tượng đó.
3. - Tổ chức biểu diễn các đối tượng thực tế: Công việc này được gọi là xây dựng cấu trúc dữ liệu cho bài toán.
4. - Xây dựng các thao tác xử lý dữ liệu: Từ những yêu cầu xử lý thực tế, cần tìm ra các giải thuật tương ứng để xác định trình tự các thao tác máy tính phải tác động lên dữ liệu để cho ra kết quả mong muốn, đây là bước xây dựng giải thuật cho bài toán.
5. - Giải thuật và cấu trúc dữ liệu có mối quan hệ với nhau Cấu trúc dữ liệu + Giải thuật = Chương trình
6. - Một cấu trúc dữ liệu tốt sẽ giúp giải thuật xử lý trên đó có thể phát huy tác dụng tốt hơn, vừa đáp ứng nhanh vừa tiết kiệm tài nguyên, đồng thời giải thuật cũng dễ hiểu và đơn giản hơn.
7. 2. Các tiêu chuẩn đánh giá cấu trúc dữ liệu: ◼ Phản ảnh đúng thực tế: Đây 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. Cần xem xét kỹ lưỡng cũng như dự trù các trạng thái biến đổi của dữ liệu trong chu trình sống để có thể chọn cấu trúc dữ liệu lưu trữ thể hiện chính xác đối tượng thực tế.
8. Ví dụ: Trường hợp chọn cấu trúc dữ liệu sai: ◼ Chọn một số nguyên int để lưu trữ điểm trung bình của sinh viên (được tính theo công thức trung bình cộng của các môn học có hệ số)
9. ◼ Phù hợp với các thao tác xử lý: Tiêu chuẩn này giúp tăng tính hiệu quả của đề án: phát triển các thuật toán đơn giản, tự nhiên hơn; chương trình đạt hiệu quả cao hơn về tốc độ xử lý.