Cấu trúc dữ liệu và giải thuật là hai yếu tố quan trọng nhất của
một chương trình.
Niklaus Wirth đã phát biểu :
Chương trình = Giải thuật + Cấu trúc dữ liệu
Cấu trúc dữ liệu
Phương pháp biểu diễn và lưu trữ dữ liệu phù hợp với thao tác
xử lý trong giải thuật.
Giải thuật
Các bước để giải quyết một vấn đề (một bài toán) phù hợp với
một cấu trúc dữ liệu cụ thể.
13 trang |
Chia sẻ: lylyngoc | Lượt xem: 1750 | Lượt tải: 1
Bạn đang xem nội dung tài liệu Chương 1: Tổng quan về cấu trúc dữ liệu & giải thuật, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
Giảng viên : Nguyễn Minh Thành
Email : thanhnm@itc.edu.vn
Chương 1 : TỔNG QUAN VỀ
CTDL & GT
Nội Dung
I. Giới thiệu
II. Cấu trúc dữ liệu
1. Khái niệm
2. Các cấu trúc (kiểu) dữ liệu cơ sở
III. Giải thuật
IV. Đánh giá độ phức tạp của thuật giải
2 Nguyễn Minh Thành
I. Giới Thiệu
3 Nguyễn Minh Thành
Cấu trúc dữ liệu và giải thuật là hai yếu tố quan trọng nhất của
một chương trình.
Niklaus Wirth đã phát biểu :
Chương trình = Giải thuật + Cấu trúc dữ liệu
Cấu trúc dữ liệu
Phương pháp biểu diễn và lưu trữ dữ liệu phù hợp với thao tác
xử lý trong giải thuật.
Giải thuật
Các bước để giải quyết một vấn đề (một bài toán) phù hợp với
một cấu trúc dữ liệu cụ thể.
II. Cấu trúc dữ liệu
4 Nguyễn Minh Thành
Để đánh giá một cấu trúc dữ liệu, phải dựa vào các tiêu chí sau :
Phản ánh đúng thực tế
Phù hợp với thao tác
Tiết kiệm tài nguyên hệ thống
II.1 Khái niệm cấu trúc dữ liệu
5 Nguyễn Minh Thành
Cho
T = : kiểu (cấu trúc) dữ liệu
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ố nguyên int trong ngôn ngữ C
T = int
V = {-32768, 32767}
O = {+, -, *, /, %}
II.1 Khái niệm cấu trúc dữ liệu
6 Nguyễn Minh Thành
Các thuộc tính của một cấu trúc (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
Kiểu dữ 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, …
II.1 Khái niệm cấu trúc dữ liệu
7 Nguyễn Minh Thành
Với từng cấu trúc dữ liệu, ta có thể chọn 1 trong 2 cách để khởi
tạo (cấp phát bộ nhớ) : Tĩnh và Động
Tĩnh
• Được định nghĩa ở thời điểm
biên dịch.
• Được cấp phát ở thời điểm liên
kết.
• Có thể có giá trị ban đầu tùy
theo từng ngôn ngữ lập trình.
• Tồn tại đến khi kết thúc
chương trình.
Động
• Được gắn kết với một con trỏ
(tại thời điểm biên dịch chưa
có).
• Phát sinh lúc thực thi.
• Không xác định giá trị ban đầu.
• Được giải phóng khỏi bộ nhớ
khi cần.
II.2 Các kiểu dữ liệu cơ sở
8 Nguyễn Minh Thành
Tên kiểu Miền giá trị Kích thước Ý nghĩa
char -127 128 8 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
III. Giải Thuật
9 Nguyễn Minh Thành
Giải thuật hay còn gọi là thuật toán
Một tập hợp hữu hạn của các chỉ thị hay phương cách được
định nghĩa rõ ràng cho việc hoàn tất một số sự việc từ một
trạng thái ban đầu cho trước; khi các chỉ thị này được áp dụng
triệt để thì sẽ dẫn đến kết quả sau cùng như đã dự đoán
III. Giải Thuật
10 Nguyễn Minh Thành
Các đặc trưng cơ bản của một giải thuật
Yếu tố vào – ra (input/output)
Tính dừng (Finitary)
Tính chính xác (Exactitude)
Tính hiệu quả (effectiveness)
Tính tổng quát (generalliness)
IV. Đánh Giá Giải Thuật
11 Nguyễn Minh Thành
Các độ đo dùng để đánh giá giải thuật
Độ dài của chương trình (số dòng lệnh)
Dễ lập trình (phát hiện lỗi, quản lý)
Bộ nhớ
Thời gian thực thi
Thời gian thực thi là tiêu chuẩn quyết định
Có thể lượng giá được và dễ dàng so sánh
Thường là yếu tố “cổ chai” quan trọng
IV. Đánh Giá Giải Thuật
12 Nguyễn Minh Thành
Đánh giá độ phức tạp (thời gian) của giải thuật
Một giải thuật có thể thực thi khác nhau tuỳ thuộc vào:
nền 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 nhau về chi tiết, tất cả mô hình phần cứng và chương
trình đều có điểm tương tự nhau: chúng là các máy Turing.
Chỉ cần đếm các phép toán cơ bản là đủ.
Độ đo đơn giản nhưng có giá trị đối với hiệu quả của các thuật
toán là một hàm của kích thước input.
FAQs (Hỏi - Đáp)
13 Nguyễn Minh Thành