CẤU TRÚC DỮ LIỆU & GIẢI THUẬT

Giới thiệu vai trò của tổ chức dữ liệuMối quan hệ giữa giải thuật và cấu trúc dữ liệuCác khái niệm và yêu cầu về cấu trúc dữ liệuTổng quan về đánh giá độ phức tạp giải thuật
Nội dung trích xuất từ tài liệu:
CẤU TRÚC DỮ LIỆU & GIẢI THUẬT CẤU TRÚC DỮ LIỆU & GIẢI THUẬT LT:45 TIẾT TH:60 TIẾT Gi ản g v ie â n : HOÀ Ñ AÉC QUAÙN Em a il : h o d a c q u a n 9 9 @g m a il. c o m1 Ba ø i g ia û n g : h o d a c q u a n . w o rd p re s s . c o m MỤC TIÊU BUỔI HỌC Chương 1. Tổng quan về CTDL > Giới thiệu vai trò của tổ chức dữ liệu Mối quan hệ giữa giải thuật và cấu trúc dữ liệu Các khái niệm và yêu cầu về cấu trúc dữ liệu Tổng quan về đánh giá độ phức tạp 2 giải thuậtSUY NGHĨ ? Theo bạn: trước khi viết một chương trình để giải quyết một bài toán nào đó trên máy tính thì cần phải làm những việc gì? 3VAI TRÒ CỦA CẤU TRÚC DỮ LIỆU Cấu trúc Giải dữ thuật liệu Chương trình 4CÁC TIÊU CHUẨN ĐÁNH GIÁ CTDL Phản ánh đúng thực tếoo Phù hợp với thao táco Tiết kiệm tài nguyên hệ thống 5KHÁI NIỆM VỀ KIỂU DỮ LIỆUT = V = {Tập các giá trị}O = {Tập các thao tác xử lý được phépthực hiện}Ví d ụ: Kiểu d ữ liệu s ố n g u y ê n in t t ro n gngôn ngữ C T = int 6 V = {-32768, 32767}KHÁI NIỆM VỀ KIỂU DỮ LIỆU Các thuộc tính của một kiểu dữ liệu gồm: Tên Miền giá trị Kích thước lưu trữ Tập các thao tác tác động lên kiểu dữ liệu đó Các loại kiểu dữ liệu Kiểu dữ liệu cơ bản: Cơ sở, mảng, cấu trúc cơ bản 7 Kiểu dữ liệu có cấu trúc hướng giải quyếtKHÁI NIỆM VỀ KIỂU DỮ LIỆU Động Tĩnh• Được định nghĩa ở thời • Được gắn kết với một conđiểm biên dịch. trỏ (tại thời điểm biên dịch chưa có).• Được cấp phát ở thời điểm • Phát sinh lúc thực thi.liên kết.• Có thể có giá trị ban đầu tùy • Không xác định giá trị bantheo từng ngôn ngữ lập trình. đầu.• Tồn tại đến khi kết thúc • Được giải phóng khỏi bộchương trình. nhớ khi cần. 8ĐÁNH GIÁ ĐỘ PHỨC TẠP GIẢI THUẬT Do phải cài đặt bằng một ngôn ngữ lập trình cụ thể nên thuật toán sẽ chịu sự hạn chế của ngôn ngữ lập trình này. Đồng thời, hiệu quả của thuật toán sẽ bị ảnh hưởng bởi trình độ của người cài đặt. Việc chọn được các bộ dữ liệu thử đặc trưng cho tất cả tập các dữ liệu vào của thuật toán là rất khó khăn và tốn nhiều chi phí. Các số liệu thu nhận được phụ thuộc nhiều vào phần cứng mà thuật toán được thử nghiệm trên đó. Điều này khiến cho việc so sánh các thuật toán khó khăn nếu 9 chúng được thử nghiệm ở những nơi khác