Chương : TỔNG QUAN VỀ CTDL & GT Giảng viên : Nguyễn Minh Thành Email : thanhnm@itc.edu.vn Nội Dung Giới thiệu II Cấu trúc liệu Khái niệm Các cấu trúc (kiểu) liệu sở III Giải thuật IV Đánh giá độ phức tạp thuật giải I Nguyễn Minh Thành I Giới Thiệu Cấu trúc liệu giải thuật hai yếu tố quan trọng chương trình  Niklaus Wirth phát biểu :  Chương trình = Giải thuật + Cấu trúc liệu  Cấu trúc liệu  Phương pháp biểu diễn lưu trữ liệu phù hợp với thao tác xử lý giải thuật  Giải thuật  Các bước để giải vấn đề (một toán) phù hợp với cấu trúc liệu cụ thể  Nguyễn Minh Thành II Cấu trúc liệu  Để đánh giá cấu trúc liệu, phải dựa vào tiêu chí sau :  Phản ánh thực tế  Phù hợp với thao tác  Tiết kiệm tài nguyên hệ thống Nguyễn Minh Thành II.1 Khái niệm cấu trúc liệu  Cho  T = : kiểu (cấu trúc) liệu  V = {Tập giá trị}  O = {Tập thao tác xử lý phép thực hiện}  Ví dụ: Kiểu liệu số nguyên int ngôn ngữ C T = int V = {-32768, 32767} O = {+, -, *, /, %} Nguyễn Minh Thành II.1 Khái niệm cấu trúc liệu  Các thuộc tính cấu trúc (kiểu) liệu gồm: Tên  Miền giá trị  Kích thước lưu trữ  Tập thao tác tác động lên kiểu liệu   Các loại kiểu liệu Kiểu liệu bản: Cơ sở, mảng, cấu trúc  Kiểu liệu có cấu trúc : Danh sách liên kết, hàng đợi, ngăn xếp, cây, bảng băm, …  Nguyễn Minh Thành II.1 Khái niệm cấu trúc liệu  Với cấu trúc liệu, ta chọn cách để khởi tạo (cấp phát nhớ) : Tĩnh Động Tĩnh Động • Được định nghĩa thời điểm • Được gắn kết với trỏ biên dịch (tại thời điểm biên dịch chưa có) • Được cấp phát thời điểm liên • Phát sinh lúc thực thi kết • Có thể có giá trị ban đầu tùy • Khơng xác định giá trị ban đầu theo ngơn ngữ lập trình • Được giải phóng khỏi nhớ • Tồn đến kết thúc cần chương trình Nguyễn Minh Thành II.2 Các kiểu liệu sở Tên kiểu Miền giá trị Kích thước Ý nghĩa char -127  128 bit Số nguyên, ký tự Int -32767  32768 16 bit (hoặc 32, 64) Số nguyên float … 32 bit Số thực (6 thận phân) double … 64bit Số thực (10 thập phân) Các từ khoá khai báo đặc biệt • Unsigned, signed, short, long Nguyễn Minh Thành III Giải Thuật  Giải thuật hay gọi thuật toán  Một tập hợp hữu hạn thị hay phương cách định nghĩa rõ ràng cho việc hoàn tất số việc từ trạng thái ban đầu cho trước; thị áp dụng triệt để dẫn đến kết sau dự đoán Nguyễn Minh Thành III Giải Thuật  10 Các đặc trưng giải thuật  Yếu tố vào – (input/output)  Tính dừng (Finitary)  Tính xác (Exactitude)  Tính hiệu (effectiveness)  Tính tổng quát (generalliness) Nguyễn Minh Thành IV Đánh Giá Giải Thuật   11 Các độ đo dùng để đánh giá giải thuật  Độ dài chương trình (số dịng lệnh)  Dễ lập trình (phát lỗi, quản lý)  Bộ nhớ  Thời gian thực thi Thời gian thực thi tiêu chuẩn định  Có thể lượng giá dễ dàng so sánh  Thường yếu tố “cổ chai” quan trọng Nguyễn Minh Thành IV Đánh Giá Giải Thuật  12 Đánh giá độ phức tạp (thời gian) giải thuật  Một giải thuật thực thi khác tuỳ thuộc vào:  tảng phần cứng (PC, Cray, Sun)  ngôn ngữ lập trình (C, Java, C++)  lập trình viên (you, me, Bill Joy)  Tuy khác chi tiết, tất mơ hình phần cứng chương trình có điểm tương tự nhau: chúng máy Turing  Chỉ cần đếm phép toán đủ  Độ đo đơn giản có giá trị hiệu thuật toán hàm kích thước input Nguyễn Minh Thành FAQs (Hỏi - Đáp) 13 Nguyễn Minh Thành ... thiệu II Cấu trúc liệu Khái niệm Các cấu trúc (kiểu) liệu sở III Giải thuật IV Đánh giá độ phức tạp thuật giải I Nguyễn Minh Thành I Giới Thiệu Cấu trúc liệu giải thuật hai yếu tố quan trọng chương. .. liệu Kiểu liệu bản: Cơ sở, mảng, cấu trúc  Kiểu liệu có cấu trúc : Danh sách liên kết, hàng đợi, ngăn xếp, cây, bảng băm, …  Nguyễn Minh Thành II .1 Khái niệm cấu trúc liệu  Với cấu trúc liệu, ... Wirth phát biểu :  Chương trình = Giải thuật + Cấu trúc liệu  Cấu trúc liệu  Phương pháp biểu diễn lưu trữ liệu phù hợp với thao tác xử lý giải thuật  Giải thuật  Các bước để giải vấn đề (một