Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 1: Tổng quan cấu trúc dữ liệu - Thiều Quang Trung
Sự cần thiết của giải thuật
• Tại sao sử dụng máy tính để xử lý dữ liệu?
– Nhanh hơn, nhiều hơn.
– Giải quyết những bài toán mà con người không thể hoàn
thành được.
• Làm sao đạt được những mục tiêu đó?
– Nhờ vào sự tiến bộ của kỹ thuật: tăng cấu hình máy => chi
phí cao
– Nhờ vào các thuật toán hiệu quả: thông minh và chi phí
thấp
“Một máy tính siêu hạng vẫn
không thể cứu vãn một thuật toán tồi!”
44 trang |
Chia sẻ: thucuc2301 | Lượt xem: 701 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 1: Tổng quan cấu trúc dữ liệu - Thiều Quang Trung, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
CHƯƠNG I
TỔNG QUAN CẤU TRÚC DỮ LIỆU
GV Th.S. Thiều Quang Trung
Trường Cao đẳng Kinh tế Đối ngoại
• Giới thiệu đề cương môn học1
• Các khái niệm cơ bản2
Giải thuật, biểu diễn và độ phức tạp •3
• Vai trò của cấu trúc dữ liệu4
• Các tiêu chuẩn của giải thuật và cấu
trúc dữ liệu5
Nội dung
GV: Thiều Quang Trung 2
Giới thiệu đề cương môn học
• Học phần: Cấu trúc dữ liệu và giải thuật
• Số tín chỉ: 3
• Phân bổ thời gian:
– Giảng lý thuyết: 30 tiết
– Thực hành: 15 tiết
– Tự học : 60 tiết
• Công cụ thực hành lập trình: Dev C++
GV: Thiều Quang Trung 3
Giới thiệu đề cương môn học
• Tóm tắt nội dung học phần:
– Cung cấp các kiến thức cơ bản về cấu trúc dữ liệu và
giải thuật như cách tổ chức biểu diễn các đối tượng
dữ liệu từ thế giới thật, cách xây dựng các thao tác
xử lý dữ liệu tương ứng với cấu trúc dữ liệu biểu
diễn, cách đánh giá lựa chọn giải thuật xử lý dữ liệu
phù hợp với cấu trúc dữ liệu biểu diễn.
– Các kiến thức này làm nền tảng cho sinh viên học
tiếp các học phần lập trình từ căn bản đến nâng cao,
cở sở để thiết kế xây dựng các phần mềm tin học khi
làm đồ án, đề tài hay làm việc sau khi ra trường.
GV: Thiều Quang Trung 4
Giới thiệu đề cương môn học
• Tài liệu: slides bài giảng và bài tập do giảng viên biên
soạn, link: https://sites.google.com/site/thieutrung/
• Tài liệu tham khảo:
– [1] Niklaus Wirth, Data Structures and Algorithms,
Prentice Hall, 2004
– [2] Mark Allen Weiss, Data Structures and Algorithm
– Analysis in C++, Pearson, 2014
– [3] Trần Hạnh Nhi & Dương Anh Đức, Giáo trình Cấu
trúc dữ liệu và Giải thuật, Đại học quốc gia thành phố
Hồ Chí Minh, 2001.
GV: Thiều Quang Trung 5
Giới thiệu đề cương môn học
Tiêu chuẩn đánh giá sinh viên:
• Điểm trung bình bộ phận: trọng số 40%
– 02 bài kiểm tra hệ số 2:
• 01 bài kiểm tra tự luận 1 tiết
• 01 bài kiểm tra thực hành 1 tiết
• Điểm thi kết thúc học phần: trọng số 60%
– Hình thức thi: thực hành
GV: Thiều Quang Trung 6
Nội dung học
Chương 1: Giới thiệu đề cương môn học và Tổng quan về
cấu trúc dữ liệu và giải thuật
Chương 2: Các kiểu dữ liệu cơ bản và giải thuật tìm kiếm
Chương 3: Các giải thuật sắp xếp dữ liệu
Chương 4: Danh sách liên kết
Chương 5: Ngăn xếp, Hàng đợi, Đệ quy
Chương 6: Cây nhị phân
Giới thiệu đề cương môn học
GV: Thiều Quang Trung 7
Các khái niệm cơ bản
• Một chương trình máy tính (computer program) là
tập các câu lệnh để điều khiển một máy tính sinh ra
một kết quả cụ thể.
• Viết các chương trình máy tính gọi là lập trình máy
tính (computer programming).
• Ngôn ngữ để tạo các chương trình máy tính gọi là
ngôn ngữ lập trình.
• Software là một chương trình hay tập hợp các
chương trình.
GV: Thiều Quang Trung 8
Các khái niệm cơ bản
• Một số ngôn ngữ lập trình
– FORTRAN (1957), COBOL, BASIC (1960)
– PASCAL (1971), C (1980): Structure programming
– C++, Java (1985): Object-oriented programming
– Javascript, PHP (1995): Scripting programming
– Python (1990), Golang (2007)
• Cú pháp (syntax)
– Cú pháp của một ngôn ngữ lập trình là tập các luật để viết
các câu lệnh chính xác
GV: Thiều Quang Trung 9
Giải thuật là gì ?
• Giải thuật/thuật toán (Algorithm): là một
dãy hữu hạn các chỉ thị có thể thi hành để đạt
mục tiêu đề ra nào đó.
• Ví dụ: giải thuật tính tổng tất cả các số
nguyên dương nhỏ hơn n gồm các bước sau:
– Bước 1: S=0, i=1;
– Bước 2: nếu i<n thì S=S+i; ngược lại: qua bước 4;
– Bước 3: i=i+1; quay lại bước 2;
– Bước 4: Tổng cần tìm là S.
GV: Thiều Quang Trung 10
Biễu diễn giải thuật
• Dạng ngôn ngữ tự nhiên
• Dạng lưu đồ/sơ đồ khối (Flow chart)
• Dạng mã giả (Pseudocode)
• Ngôn ngữ lập trình
GV: Thiều Quang Trung 11
Biễu diễn giải thuật bằng ngôn ngữ tự
nhiên
• Ngôn ngữ tự nhiên thông qua các bước được
tuần tự liệt kê để biễu diễn thuật toán.
• Ưu điểm:
– Đơn giản, không cần kiến thức về về cách biểu
diễn (mã giả, lưu đồ,...)
• Nhược điểm:
– Dài dòng, không cấu trúc.
– Đôi lúc khó hiểu, không diễn đạt được thuật
toán.
GV: Thiều Quang Trung 12
Biễu diễn giải thuật bằng lưu đồ
• Lưu đồ là hệ thống các nút, cung hình dạng khác
nhau thể hiện các chức năng khác nhau
GV: Thiều Quang Trung 13
Ví dụ biễu diễn giải thuật bằng lưu đồ
GV: Thiều Quang Trung 14
Biễu diễn giải thuật bằng mã giả
Mã giả là n• gôn ngữ tựa ngôn ngữ lập trình:
Dùng – cấu trúc chuẩn hóa, chẳng hạn tựa Pascal, C.
Dùng – các ký hiệu toán học, biến, hàm.
Ưu • điểm:
Đỡ – cồng kềnh hơn lưu đồ khối.
Nhược • điểm:
Không – trực quan bằng lưu đồ khối.
GV: Thiều Quang Trung 15
Biễu diễn giải thuật bằng mã giả
• Một số quy ước:
– Các biểu thức toán học
– Lệnh gán: “=” (A←B)
– So sánh: “==”, “!=”
– Khai báo hàm (thuật toán)
Thuật toán ()
Input:
Output:
End
GV: Thiều Quang Trung 16
Biễu diễn giải thuật bằng mã giả
Các • cấu trúc:
Cấu trúc – chọn: if then [else ]
Vòng lặp:–
while do
do while ()
for do
Một • số câu lệnh khác:
Trả giá trị về: return [giá trị]–
Lời gọi hàm: (tham số)–
GV: Thiều Quang Trung 17
Biễu diễn giải thuật bằng mã giả
• Ví dụ: tìm phần tử lớn nhất trong mảng một
chiều.
amax = a0;
i=1;
while (i<n)
if (amax<ai) amax= ai;
i++;
end while;
GV: Thiều Quang Trung 18
Biễu diễn giải thuật bằng ngôn ngữ
lập trình
Dùng ngôn ngữ máy tính • (Pascal, C, C++, ...) để diễn
tả thuật toán, CTDL thành câu lệnh.
Kỹ • năng lập trình đòi hỏi cần học tập và thực hành.
Dùng • phương pháp tinh chế từng bước để chuyển
hoá bài toán sang mã chương trình cụ thể.
Học:•
Nhớ – giải thuật (mã giả)
Dùng – NNLT cụ thể để minh chứng
GV: Thiều Quang Trung 19
So sánh giải thuật bằng mã giả và NNLT
Ví dụ: mã giả của bubble sort
Giải thuật 1 Giải thuật 2
Algorithm Bubble sort
Input: The list A of n elements
is given
Output: The list A is sorted
1. loop for n time
1.1. for each pair in the list
1.1.1. if it is not in ordered
1.1.1.1. exchange them
End Bubble sort
Algorithm Bubble sort
Input: The list A of n elements is
given
Output: The list A is sorted
1. for outter in 0..(n-2)
1.1. for inner in 0..(n-2- outter)
1.1.1. if Ainner+1 < Ainner
1.1.1.1. swap Ainner,
Ainner+1
End Bubble sort
Giải thuật 1: Pascal Giải thuật 2: C++
procedure BubbleSort(var A: list);
var i,j: int;
begin
for i := 1 to n-1 do
for j := 1 to (n-1-i) do
if A[j+1] < A[j] then
begin
tmp := A[j]; A[j] := A[j+1];
A[j+1] := tmp;
end;
end;
void BubbleSort(int a[], int n)
{
int i, j;
for (i = 0 ; i<n-1 ; i++)
for (j =n-1; j>i ; j --)
if(a[j]< a[j-1])
Swap(a[j],a[j-1]);
}
So sánh giải thuật bằng mã giả và NNLT
Ví dụ: giải thuật bubble sort bằng 2 NNLT
Độ phức tạp của giải thuật
Một • thuật toán hiệu quả:
Chi – phí cần sử dụng tài nguyên thấp: Bộ nhớ,
thời gian sử dụng CPU,
Phân • tích độ phức tạp thuật toán:
– N là khối lượng dữ liệu cần xử lý.
Mô – tả độ phức tạp thuật toán qua một hàm f(N).
Hai – phương pháp đánh giá độ phức tạp của thuật
toán:
Phương • pháp thực nghiệm.
Phương • pháp xấp xỉ toán học.
GV: Thiều Quang Trung 22
Phương pháp thực nghiệm
• Cài thuật toán rồi chọn các bộ dữ liệu thử nghiệm.
• Thống kê các thông số nhận được khi chạy các bộ dữ liệu
• Ưu điểm: Dễ thực hiện.
• Nhược điểm:
– Chịu sự hạn chế của ngôn ngữ lập trình.
– Ảnh hưởng bởi trình độ của người lập trình.
– 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: khó khăn và tốn nhiều
chi phí.
– Phụ thuộc vào phần cứng.
GV: Thiều Quang Trung 23
Phương pháp xấp xỉ toán học
Đánh • giá giá thuật toán theo hướng tiệm xấp xỉ tiệm
cận qua các khái niệm O().
Ưu • điểm: Ít phụ thuộc môi trường cũng như phần cứng
hơn.
Nhược • điểm: Phức tạp.
Các • trường hợp độ phức tạp quan tâm:
Trường – hợp tốt nhất (phân tích chính xác)
Trường – hợp xấu nhất (phân tích chính xác)
Trường – hợp trung bình (mang tích dự đoán)
GV: Thiều Quang Trung 24
Vai trò của cấu trúc dữ liệu ?
• Thực hiện một đề án tin học là chuyển bài toán thực
tế thành bài toán có thể giải quyết trên máy tính.
• 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 những đối
tượng đó.
• Xây dựng một mô hình tin học cần chú trọng đến 2
vấn đề :
– Tổ chức biểu diễn các đối tượng thực tế
– Xây dựng các thao tác xử lý dữ liệu
GV: Thiều Quang Trung 25
• Các thành phần dữ liệu thực tế đa dạng, phong
phú và thường chứa đựng những quan hệ nào đó
với nhau => trong mô hình tin học của bài toán
cần phải tổ chức xây dựng các cấu trúc thích hợp
nhất sao cho vừa có thể phản ánh chính xác các
dữ liệu thực tế, vừa có thể dễ dàng dùng máy tính
để xử lý.
• 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.
Tổ chức biểu diễn các đối tượng thực tế
GV: Thiều Quang Trung 26
• 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 thi hành để 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.
• Giải thuật và cấu trúc dữ liệu có mối quan hệ chặt chẽ
với nhau, được thể hiện qua công thức:
Xây dựng các thao tác xử lý dữ liệu
GV: Thiều Quang Trung 27
Cấu trúc
dữ liệu
Giải
thuật
Chương
trình
• Để xác định được giải thuật phù hợp cần phải biết
nó tác động đến loại dữ liệu nào ?
• Ví dụ để làm nhuyễn các hạt đậu, người ta dùng
cách xay chứ không băm bằng dao, vì đậu sẽ văng
ra ngoài.
• Khi chọn lựa cấu trúc dữ liệu cũng cần phải hiểu
rõ những thao tác nào tác động đến nó ?
• Ví dụ để biểu diễn các điểm số của sinh viên người
ta dùng số thực thay vì chuỗi ký tự vì còn phải
thực hiện thao tác tính trung bình từ những điểm
số đó.
Tại sao chú trọng cả 2 vấn đề ?
GV: Thiều Quang Trung 28
Ví dụ về lưu trữ dữ liệu kiểu mảng
• Ví dụ: một chương trình quản lý điểm thi của
sinh viên cần lưu trữ các điểm số của 4 sv:
Sinh viên Môn 1 Môn 2 Môn 3
SV1 8 6 4
SV2 9 5 3
SV3 6 7 2
SV4 5 6 5
GV: Thiều Quang Trung 29
Ví dụ về lưu trữ dữ liệu kiểu mảng
• Có 02 phương án tổ chức lưu trữ dữ liệu sinh
viên:
– Phương án 1: sử dụng mảng một chiều:
Có tất cả 4(sv) x 3(môn) = 12 điểm số cần lưu
trữ, do đó khai báo mảng diem như sau:
int diem [12] = {8, 6, 4,
9, 5, 3,
6, 7, 2,
5, 6, 5 };
GV: Thiều Quang Trung 30
Ví dụ về lưu trữ dữ liệu kiểu mảng
• Khi đó trong mảng diem các phần tử sẽ được
lưu trữ như sau:
8 6 4 9 5 3 6 7 2 5 6 5
SV1 SV2 SV3 SV4
GV: Thiều Quang Trung 31
Ví dụ về lưu trữ dữ liệu kiểu mảng
• Để truy xuất điểm số môn j của sinh viên i (là
phần tử tại dòng i, cột j trong bảng) phải sử
dụng công thức xác định chỉ số tương ứng
trong mảng diem:
bảngđiểm(dòng i, cột j) => diem[((i-1)*số cột) +j]
GV: Thiều Quang Trung 32
Ví dụ về lưu trữ dữ liệu kiểu mảng
• Thao tác xử lý được cài đặt cho mảng 1 chiều như sau:
void indiem()
{ const int somon = 3;
int sv, mon;
for (int i=0; i<12; i++)
{ sv = i/somon;
mon=i % somon;
printf(“Điểm môn %d của SV %d là: %d”, mon, sv,
diem[i]);
}
}
GV: Thiều Quang Trung 33
Ví dụ về lưu trữ dữ liệu kiểu mảng
▪ Phương án 2: Sử dụng mảng hai chiều
Khai báo mảng 2 chiều diem có kích thước 3 cột * 4
dòng như sau:
int diem [4][3] = { {8, 6, 4},
{9, 5, 3},
{6, 7, 2},
{5, 6, 5} };
GV: Thiều Quang Trung 34
• Khi đó trong mảng diem các phần tử sẽ được
lưu trữ như sau:
Ví dụ về lưu trữ dữ liệu kiểu mảng
cột 0 cột 1 cột 2
Dòng 0 diem[0][0]=8 diem[0][1]=6 diem[0][2]=4
Dòng 1 diem[1][0]=9 diem[1][1]=5 diem[1][2]=3
Dòng 2 diem[2][0]=6 diem[2][1]=7 diem[2][2]=2
Dòng 3 diem[3][0]=5 diem[3][1]=6 diem[3][2]=5
GV: Thiều Quang Trung 35
Ví dụ về lưu trữ dữ liệu kiểu mảng
• Để truy xuất điểm số môn j của sinh viên i, là
phần tử tại dòng i, cột j trong bảng, cũng
chính là phần tử nằm ở vị trí dòng i cột j
trong mảng:
bảngđiểm(dòng i, cột j) => diem[i] [j]
GV: Thiều Quang Trung 36
Ví dụ về lưu trữ dữ liệu kiểu mảng
• Thao tác xử lý được cài đặt cho mảng 2 chiều như sau:
void indiem()
{ int somon = 3, sosv = 4;
for (int i=0; i<sosv; i++)
for(int j=0; j<somon; j++)
printf(“Điểm môn %d của SV %d là: %d”, j, i,
diem[i][j]);
}
GV: Thiều Quang Trung 37
• Nhận xét:
• Phương án 2 cung cấp một cấu trúc dữ liệu
phù hợp với dữ liệu thực tế hơn phương án
1, do đó giải thuật xử lý trên cấu trúc dữ liệu
của phương án 2 cũng đơn giản và tự nhiên
hơn
Ví dụ về lưu trữ dữ liệu kiểu mảng
GV: Thiều Quang Trung 38
Các tiêu chuẩn của giải thuật
• Xác định rõ dữ liệu đầu vào
• Xác định rõ kết quả đầu ra
• Tính xác định: cùng một dữ liệu đầu vào thì
cùng đưa đến một kết quả đầu ra
• Tính khả thi: đơn giản, làm được, thời gian
hữu hạn
• Tính dừng: sau một số bước hữu hạn thực
hiện sẽ phải kết thúc
GV: Thiều Quang Trung 39
• Phản ánh đúng thực tế => 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ế.
• Phù hợp với các thao tác trên đó => giúp tăng
tính hiệu quả của giải thuật, tốc độ xử lý tốt hơn.
• Tiết kiệm tài nguyên hệ thống => cấu trúc dữ liệu
chỉ nên sử dụng tài nguyên hệ thống (CPU và bộ
nhớ) vừa đủ để đảm nhiệm được chức năng của
nó.
Các tiêu chuẩn của cấu trúc dữ liệu
GV: Thiều Quang Trung 40
• Ví dụ tình huống chọn cấu trúc lưu trữ sai:
– Chọn một biến số nguyên int để lưu trữ tiền thưởng
bán hàng (được tính theo công thức tiền thưởng
bán hàng = trị giá hàng * 5%)
– Sai, vì số nguyên sẽ làm tròn mọi giá trị tiền thưởng
gây thiệt hại cho nhân viên bán hàng !
– Trường hợp này phải sử dụng biến số thực float để
phản ánh đúng kết quả của công thức tính thực tế.
Các tiêu chuẩn của cấu trúc dữ liệu
GV: Thiều Quang Trung 41
• Ví dụ tình huống chọn cấu trúc lưu trữ lãng
phí:
– Sử dụng biến int (2 bytes) để lưu trữ một giá trị
cho biết tháng hiện hành. Biết rằng tháng chỉ có
thể nhận các giá trị từ 1 - 12, nên chỉ cần sử dụng
kiểu char (1 byte) là đủ.
– Để lưu trữ danh sách học viên trong một lớp sử
dụng mảng 50 phần tử (giới hạn số học viên
trong lớp tối đa là 50). Nếu số học viên thật sự ít
hơn 50, thì gây lãng phí. Trường hợp này cần có
một cấu trúc dữ liệu linh động hơn mảng, như
kiểu xâu liên kết.
GV: Thiều Quang Trung 42
Các tiêu chuẩn của cấu trúc dữ liệu
Sự cần thiết của giải thuật
• Tại sao sử dụng máy tính để xử lý dữ liệu?
– Nhanh hơn, nhiều hơn.
– Giải quyết những bài toán mà con người không thể hoàn
thành được.
• Làm sao đạt được những mục tiêu đó?
– Nhờ vào sự tiến bộ của kỹ thuật: tăng cấu hình máy => chi
phí cao
– Nhờ vào các thuật toán hiệu quả: thông minh và chi phí
thấp
“Một máy tính siêu hạng vẫn
không thể cứu vãn một thuật toán tồi!”
GV: Thiều Quang Trung 43
GV: Thiều Quang Trung 44
Các file đính kèm theo tài liệu này:
- 2018chuong_1_tong_quan_cau_truc_du_lieu_6902_2046955.pdf