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

Chia sẻ: Batman_1 Batman_1 | Ngày: | Loại File: PPT | Số trang:9

Thêm vào BST

Báo xấu

97
lượt xem 11
download

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

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 giải thuật

Chủ đề:

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

Lưu

Nội dung Text: 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 m 1 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 &GT  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ật
SUY 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ì? 3
VAI 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 4
CÁC TIÊU CHUẨN ĐÁNH GIÁ CTDL Phản ánh đúng thực tế o o Phù hợp với thao tác o Tiết kiệm tài nguyên hệ thống 5
KHÁI NIỆM VỀ KIỂU DỮ LIỆU T = V = {Tập các giá trị} O = {Tập các thao tác xử lý được phép thực hiện} Ví d ụ: Kiểu d ữ liệu s ố n g u y ê n in t t ro n g ngô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ết
KHÁ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ị ban theo 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