Giáo trình Cấu trúc dữ liệu và giải thuật
Chương 1: TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
1.1. Tầm quan trọng của cấu trúc dữ liệu và giải thuật trong một đề án tin học
1.1.1. Xây dựng cấu trúc dữ liệu
Có thể nói rằng không có một chương trình máy tính nào mà không có dữ liệu để xử lý. Dữ
liệu có thể là dữ liệu đưa vào (input data), dữ liệu trung gian hoặc dữ liệu đưa ra (output data). Do
vậy, việc tổ chức để lưu trữ dữ liệu phục vụ cho chương trình có ý nghĩa rất quan trọng trong toàn bộ
hệ thống chương trình. Việc xây dựng cấu trúc dữ liệu quyết định rất lớn đến chất lượng cũng như
công sức của người lập trình trong việc thiết kế, cài đặt chương trình.
1.1.2. Xây dựng giải thuật
Khái niệm giải thuật hay thuật giải mà nhiều khi còn được gọi là thuật toán dùng để chỉ
phương pháp hay cách thức (method) để giải quyết vần đề. Giải thuật có thể được minh họa bằng
ngôn ngữ tự nhiên (natural language), bằng sơ đồ (flow chart) hoặc bằng mã giả (pseudo code).
Trong thực tế, giải thuật thường được minh họa hay thể hiện bằng mã giả tựa trên một hay một số
ngôn ngữ lập trình nào đó (thường là ngôn ngữ mà người lập trình chọn để cài đặt thuật toán), chẳng
hạn như C, Pascal, …
Khi đã xác định được cấu trúc dữ liệu thích hợp, người lập trình sẽ bắt đầu tiến hành xây
dựng thuật giải tương ứng theo yêu cầu của bài toán đặt ra trên cơ sở của cấu trúc dữ liệu đã được
chọn. Để giải quyết một vấn đề có thể có nhiều phương pháp, do vậy sự lựa chọn phương pháp phù
hợp là một việc mà người lập trình phải cân nhắc và tính toán. Sự lựa chọn này cũng có thể góp phần
đáng kể trong việc giảm bớt công việc của người lập trình trong phần cài đặt thuật toán trên một
ngôn ngữ cụ thể.
1.1.3. Mối quan hệ giữa cấu trúc dữ liệu và giải thuật
Mối quan hệ giữa cấu trúc dữ liệu và Giải thuật có thể minh họa bằng đẳng thức:
Cấu trúc dữ liệu + Giải thuật = Chương trình
Như vậy, khi đã có cấu trúc dữ liệu tốt, nắm vững giải thuật thực hiện thì việc thể hiện
chương trình bằng một ngôn ngữ cụ thể chỉ là vấn đề thời gian. Khi có cấu trúc dữ liệu mà chưa tìm
ra thuật giải thì không thể có chương trình và ngược lại không thể có Thuật giải khi chưa có cấu trúc
dữ liệu. Một chương trình máy tính chỉ có thể được hoàn thiện khi có đầy đủ cả Cấu trúc dữ liệu để
lưu trữ dữ liệu và Giải thuật xử lý dữ liệu theo yêu cầu của bài toán đặt ra.
1.2. Đánh giá cấu trúc dữ liệu và giải thuật
1.2.1. Các tiêu chuẩn đánh giá cấu trúc dữ liệu
Để đánh giá một cấu trúc dữ liệu chúng ta thường dựa vào một số tiêu chí sau:
- Cấu trúc dữ liệu phải tiết kiệm tài nguyên (bộ nhớ trong),
- Cấu trúc dữ liệu phải phản ảnh đúng thực tế của bài toán,
- Cấu trúc dữ liệu phải dễ dàng trong việc thao tác dữ liệu.
1.2.2. Đánh giá độ phức tạp của thuật toán
Việc đánh giá độ phức tạp của một thuật toán quả không dễ dàng chút nào. Ở dây, chúng ta
chỉ muốn ước lượng thời gian thực hiện thuận toán T(n) để có thể có sự so sánh tương đối giữa các
thuật toán với nhau. Trong thực tế, thời gian thực hiện một thuật toán còn phụ thuộc rất nhiều vào
các điều kiện khác như cấu tạo của máy tính, dữ liệu đưa vào, …, ở đây chúng ta chỉ xem xét trên
mức độ của lượng dữ liệu đưa vào ban đầu cho thuật toán thực hiện.
Để ước lượng thời gian thực hiện thuật toán chúng ta có thể xem xét thời gian thực hiện thuật
toán trong hai trường hợp:
- Trong trường hợp tốt nhất: Tmin
- Trong trường hợp xấu nhất: Tmax
Từ đó chúng ta có thể ước lượng thời gian thực hiện trung bình của thuật toán: Tavg
1.3. Kiểu dữ liệu
1.3.1. Khái niệm về kiểu dữ liệu
Kiểu dữ liệu T có thể xem như là sự kết hợp của 2 thành phần:
- Miền giá trị mà kiểu dữ liệu T có thể lưu trữ: V,
- Tập hợp các phép toán để thao tác dữ liệu: O.
T = <V, O>
Mỗi kiểu dữ liệu thường được đại diện bởi một tên (định danh). Mỗi phần tử dữ liệu có kiểu
T sẽ có giá trị trong miền V và có thể được thực hiện các phép toán thuộc tập hợp các phép toán
trong O.
Để lưu trữ các phần tử dữ liệu này thường phải tốn một số byte(s) trong bộ nhớ, số byte(s)
này gọi là kích thước của kiểu dữ liệu.
1.3.2. Các kiểu dữ liệu cơ sở
Hầu hết các ngôn ngữ lập trình đều có cung cấp các kiểu dữ liệu cơ sở. Tùy vào mỗi ngôn
ngữ mà các kiểu dữ liệu cơ sở có thể có các tên gọi khác nhau song chung quy lại có những loại kiểu
dữ liệu cơ sở như sau:
- Kiểu số nguyên: Có thể có dấu hoặc không có dấu và thường có các kích thước sau:
+ Kiểu số nguyên 1 byte
+ Kiểu số nguyên 2 bytes
+ Kiểu số nguyên 4 bytes
Kiểu số nguyên thường được thực hiện với các phép toán: O = {+, -, *, /, DIV, MOD, <, >,
<=, >=, =, …}
- Kiểu số thực: Thường có các kích thước sau:
+ Kiểu số thực 4 bytes
+ Kiểu số thực 6 bytes
+ Kiểu số thực 8 bytes
+ Kiểu số thực 10 bytes
Kiểu số thực thường được thực hiện với các phép toán: O = {+, -, *, /, <, >, <=, >=, =, …}
- Kiểu ký tự: Có thể có các kích thước sau:
+ Kiểu ký tự byte
+ Kiểu ký tự 2 bytes
Kiểu ký tự thường được thực hiện với các phép toán: O = {+, -, <, >, <=, >=, =, ORD, CHR,
…}
- Kiểu chuỗi ký tự: Có kích thước tùy thuộc vào từng ngôn ngữ lập trình
Kiểu chuỗi ký tự thường được thực hiện với các phép toán: O = {+, &, <, >, <=, >=, =,
Length, Trunc, …}
- Kiểu luận lý: Thường có kích thước 1 byte
Kiểu luận lý thường được thực hiện với các phép toán: O = {NOT, AND, OR, XOR, <, >, <=,
>=, =, …}
1.3.3. Các kiểu dữ liệu có cấu trúc
Kiểu dữ liệu có cấu trúc là các kiểu dữ liệu được xây dựng trên cơ sở các kiểu dữ liệu đã có
(có thể lại là một kiểu dữ liệu có cấu trúc khác). Tùy vào từng ngôn ngữ lập trình song thường có các
loại sau:
- Kiểu mảng hay còn gọi là dãy: kích thước bằng tổng kích thước của các phần tử
- Kiểu bản ghi hay cấu trúc: kích thước bằng tổng kích thước các thành phần (Field)
1.3.4. Kiểu dữ liệu con trỏ
Các ngôn ngữ lập trình thường cung cấp cho chúng ta một kiểu dữ liệu đặc biệt để lưu trữ các
địa chỉ của bộ nhớ, đó là con trỏ (Pointer). Tùy vào loại con trỏ gần (near pointer) hay con trỏ xa (far
pointer) mà kiểu dữ liệu con trỏ có các kích thước khác nhau:
+ Con trỏ gần: 2 bytes
+ Con trỏ xa: 4 bytes
1.3.5. Kiểu dữ liệu tập tin
Tập tin (File) có thể xem là một kiểu dữ liệu đặc biệt, kích thước tối đa của tập tin tùy thuộc
vào không gian đĩa nơi lưu trữ tập tin. Việc đọc, ghi dữ liệu trực tiếp trên tập tin rất mất thời gian và
không bảo đảm an toàn cho dữ liệu trên tập tin đó. Do vậy, trong thực tế, chúng ta không thao tác
trực tiếp dữ liệu trên tập tin mà chúng ta cần chuyển từng phần hoặc toàn bộ nội dung của tập tin vào
trong bộ nhớ trong để xử lý.
Câu hỏi và Bài tập
1. Trình bày tầm quan trọng của Cấu trúc dữ liệu và Giải thuật đối với người lập trình?
2. Các tiêu chuẩn để đánh giá cấu trúc dữ liệu và giải thuật?
3. Khi xây dựng giải thuật có cần thiết phải quan tâm tới cấu trúc dữ liệu hay không? Tại sao?
4. Liệt kê các kiểu dữ liệu cơ sở, các kiểu dữ liệu có cấu trúc trong C, Pascal?
5. Sử dụng các kiểu dữ liệu cơ bản trong C, hãy xây dựng cấu trúc dữ liệu để lưu trữ trong bộ nhớ
trong (RAM) của máy tính đa thức có bậc tự nhiên n (0 ≤ n ≤ 100) trên trường số thực (ai , x R):
푛
푖
( )
푓푛 푥 = ∑ 푎푖푥
푖=0
Với cấu trúc dữ liệu được xây dựng, hãy trình bày thuật toán và cài đặt chương trình để thực hiện các
công việc sau:
- Nhập, xuất các đa thức.
- Tính giá trị của đa thức tại giá trị x0 nào đó.
- Tính tổng, tích của hai đa thức.
6. Tương tự như bài tập 5. nhưng đa thức trong trường số hữu tỷ Q (các hệ số ai và x là các phân số
có tử số và mẫu số là các số nguyên).
7. Cho bảng giờ tàu đi từ ga Saigon đến các ga như sau (ga cuối là ga Hà Nội):
Sử dụng các kiểu dữ liệu cơ bản, hãy xây dựng cấu trúc dữ liệu thích hợp để lưu trữ bảng giờ
tàu trên vào bộ nhớ trong và bộ nhớ ngoài (disk) của máy tính.
Với cấu trúc dữ liệu đã được xây dựng ở trên, hãy trình bày thuật toán và cài đặt chương trình
để thực hiện các công việc sau:
- Xuất ra giờ đến của một tàu T0 nào đó tại một ga G0 nào đó.
- Xuất ra giờ đến các ga của một tàu T0 nào đó.
- Xuất ra giờ các tàu đến một ga G0 nào đó.
- Xuất ra bảng giờ tàu theo mẫu ở trên.
Lưu ý:
- Các ô trống ghi nhận tại các ga đó, tàu này không đi đến hoặc chỉ đi qua mà không dừng lại.
- Dòng “HÀNH TRÌNH” ghi nhận tổng số giờ tàu chạy từ ga Saigon đến ga Hà Nội.
8. Tương tự như bài tập 7. nhưng chúng ta cần ghi nhận thêm thông tin về đoàn tàu khi dừng tại các
ga chỉ để tránh tàu hay để cho khách lên/xuống (các dòng in nghiêng tương ứng với các ga có khách
lên/xuống, các dòng khác chỉ dừng để tránh tàu).
9. Sử dụng kiểu dữ liệu cấu trúc trong C, hãy xây dựng cấu trúc dữ liệu để lưu trữ trong bộ nhớ trong
(RAM) của máy tính trạng thái của các cột đèn giao thông (có 3 đèn: Xanh, Đỏ, Vàng). Với cấu trúc
dữ liệu đã được xây dựng, hãy trình bày thuật toán và cài đặt chương trình để mô phỏng (minh họa)
cho hoạt động của 2 cột đèn trên hai tuyến đường giao nhau tại một ngã tư.
10. Sử dụng các kiểu dữ liệu cơ bản trong C, hãy xây dựng cấu trúc dữ liệu để lưu trữ trong bộ nhớ
trong (RAM) của máy tính trạng thái của một bàn cờ CARO có kích thước M×N (0 ≤ M, N ≤ 20).
Với cấu trúc dữ liệu được xây dựng, hãy trình bày thuật toán và cài đặt chương trình để thực hiện các
công việc sau:
- In ra màn hình bàn cờ CARO trong trạng thái hiện hành.
- Kiểm tra xem có ai thắng hay không? Nếu có thì thông báo “Kết thúc”, nếu không có thì
thông báo “Tiếp tục”.
Chương 2: KỸ THUẬT TÌM KIẾM (SEARCHING)
2.1. Khái quát về tìm kiếm
Trong thực tế, khi thao tác, khai thác dữ liệu chúng ta hầu như lúc nào cũng phải thực hiện
thao tác tìm kiếm. Việc tìm kiếm nhanh hay chậm tùy thuộc vào trạng thái và trật tự của dữ liệu trên
đó. Kết quả của việc tìm kiếm có thể là không có (không tìm thấy) hoặc có (tìm thấy). Nếu kết quả
tìm kiếm là có tìm thấy thì nhiều khi chúng ta còn phải xác định xem vị trí của phần tử dữ liệu tìm
thấy là ở đâu? Trong phạm vi của chương này chúng ta tìm cách giải quyết các câu hỏi này.
Trước khi đi vào nghiên cứu chi tiết, chúng ta giả sử rằng mỗi phần tử dữ liệu được xem xét có một
thành phần khóa (Key) để nhận diện, có kiểu dữ liệu là T nào đó, các thành phần còn lại là thông tin
(Info) liên quan đến phần tử dữ liệu đó. Như vậy mỗi phần tử dữ liệu có cấu trúc dữ liệu như sau:
typedef struct DataElement {
T Key;
InfoType Info;
} DataType;
Trong tài liệu này, khi nói tới giá trị của một phần tử dữ liệu chúng ta muốn nói tới giá trị
khóa (Key) của phần tử dữ liệu đó. Để đơn giản, chúng ta giả sử rằng mỗi phần tử dữ liệu chỉ là
thành phần khóa nhận diện.
Việc tìm kiếm một phần tử có thể diễn ra trên một dãy/mảng (tìm kiếm nội) hoặc diễn ra trên
một tập tin/ file (tìm kiếm ngoại). Phần tử cần tìm là phần tử cần thỏa mãn điều kiện tìm kiếm
(thường có giá trị bằng giá trị tìm kiếm). Tùy thuộc vào từng bài toán cụ thể mà điều kiện tìm kiếm
có thể khác nhau song chung quy việc tìm kiếm dữ liệu thường được vận dụng theo các thuật toán
trình bày sau đây.
2.2. Các giải thuật tìm kiếm nội (Tìm kiếm trên dãy/mảng)
2.2.1. Đặt vấn đề
Giả sử chúng ta có một mảng M gồm N phần tử. Vấn đề đặt ra là có hay không phần tử có giá
trị bằng X trong mảng M? Nếu có thì phần tử có giá trị bằng X là phần tử thứ mấy trong mảng M?
2.2.2. Tìm tuyến tính (Linear Search)
Thuật toán tìm tuyến tính còn được gọi là Thuật toán tìm kiếm tuần tự (Sequential Search).
a. Tư tưởng:
Lần lượt so sánh các phần tử của mảng M với giá trị X bắt đầu từ phần tử đầu tiên cho đến
khi tìm đến được phần tử có giá trị X hoặc đã duyệt qua hết tất cả các phần tử của mảng M thì kết
thúc.
b. Thuật toán:
B1: k = 1
// Duyệt từ đầu mảng
B2: IF M[k] ≠ X AND k ≤ N // Nếu chưa tìm thấy và cũng chưa duyệt hết mảng
B2.1: k++
B2.2: Lặp lại B2
B3: IF k ≤ N
Tìm thấy tại vị trí k
B4: ELSE
Không tìm thấy phần tử có giá trị X
B5: Kết thúc
c. Cài đặt thuật toán:
Hàm LinearSearchcó prototype: int LinearSearch (T M[], int N, T X);
Hàm thực hiện việc tìm kiếm phần tử có giá trị X trên mảng M có N phần tử. Nếu tìm thấy,
hàm trả về một số nguyên có giá trị từ 0 đến N-1 là vị trí tương ứng của phần tử tìm thấy. Trong
trường hợp ngược lại, hàm trả về giá trị -1 (không tìm thấy). Nội dung của hàm như sau:
int LinearSearch (T M[], int N, T X){
int k = 0;
while (M[k] != X && k < N)
k++;
if (k < N)
return (k);
return (-1);
}
d. Phân tích thuật toán:
- Trường hợp tốt nhất khi phần tử đầu tiên của mảng có giá trị bằng X:
Số phép gán: Gmin = 1
Số phép so sánh: Smin = 2 + 1 = 3
- Trường hợp xấu nhất khi không tìm thấy phần tử nào có giá trị bằng X:
Số phép gán: Gmax = 1
Số phép so sánh: Smax = 2N+1
- Trung bình:
Số phép gán: Gavg = 1
Số phép so sánh: Savg = (3 + 2N + 1) : 2 = N + 2
e. Cải tiến thuật toán:
Trong thuật toán trên, ở mỗi bước lặp chúng ta cần phải thực hiện 2 phép so sánh để kiểm tra
sự tìm thấy và kiểm soát sự hết mảng trong quá trình duyệt mảng. Chúng ta có thể giảm bớt 1 phép
so sánh nếu chúng ta thêm vào cuối mảng một phần tử cầm canh (sentinel/stand by) có giá trị bằng X
để nhận diện ra sự hết mảng khi duyệt mảng, khi đó thuật toán này được cải tiến lại như sau:
B1: k = 1
B2: M[N+1] = X
B3: IF M[k] ≠ X
B3.1: k++
// Phần tử cầm canh
B3.2: Lặp lại B3
B4: IF k < N
Tìm thấy tại vị trí k
B5: ELSE
// k = N song đó chỉ là phần tử cầm canh
Không tìm thấy phần tử có giá trị X
B6: Kết thúc
Hàm LinearSearch được viết lại thành hàm LinearSearch1 như sau:
int LinearSearch1 (T M[], int N, T X){
int k = 0;
M[N] = X;
while (M[k] != X)
k++;
if (k < N)
return (k);
return (-1);
}
f. Phân tích thuật toán cải tiến:
- Trường hợp tốt nhất khi phần tử đầu tiên của mảng có giá trị bằng X:
Số phép gán: Gmin = 2
Số phép so sánh: Smin = 1 + 1 = 2
- Trường hợp xấu nhất khi không tìm thấy phần tử nào có giá trị bằng X:
Số phép gán: Gmax = 2
Số phép so sánh: Smax = (N+1) + 1 = N + 2
- Trung bình:
Số phép gán: Gavg = 2
Số phép so sánh: Savg = (2 + N + 2) : 2 = N/2 + 2
- Như vậy, nếu thời gian thực hiện phép gán không đáng kể thì thuật toán cải tiến sẽ chạy nhanh hơn
thuật toán nguyên thủy.
2.2.3. Tìm nhị phân (Binary Search)
Thuật toán tìm tuyến tính tỏ ra đơn giản và thuận tiện trong trường hợp số phần tử của dãy
không lớn lắm. Tuy nhiên, khi số phần tử của dãy khá lớn, chẳng hạn chúng ta tìm kiếm tên một
khách hàng trong một danh bạ điện thoại của một thành phố lớn theo thuật toán tìm tuần tự thì quả
thực mất rất nhiều thời gian. Trong thực tế, thông thường các phần tử của dãy đã có một thứ tự, do
vậy thuật toán tìm nhị phân sau đây sẽ rút ngắn đáng kể thời gian tìm kiếm trên dãy đã có thứ tự.
Trong thuật toán này chúng ta giả sử các phần tử trong dãy đã có thứ tự tăng (không giảm dần), tức
là các phần tử đứng trước luôn có giá trị nhỏ hơn hoặc bằng (không lớn hơn) phần tử đứng sau nó.
Khi đó, nếu X nhỏ hơn giá trị phần tử đứng ở giữa dãy (M[Mid]) thì X chỉ có thể tìm thấy ở
nửa đầu của dãy và ngược lại, nếu X lớn hơn phần tử M[Mid] thì X chỉ có thể tìm thấy ở nửa sau của
dãy.
a. Tư tưởng:
Phạm vi tìm kiếm ban đầu của chúng ta là từ phần tử đầu tiên của dãy (First = 1) cho đến
phần tử cuối cùng của dãy (Last = N).
So sánh giá trị X với giá trị phần tử đứng ở giữa của dãy M là M[Mid].
Nếu X = M[Mid]: Tìm thấy
Nếu X < M[Mid]: Rút ngắn phạm vi tìm kiếm về nửa đầu của dãy M (Last = Mid-1)
Nếu X > M[Mid]: Rút ngắn phạm vi tìm kiếm về nửa sau của dãy M (First = Mid+1)
Lặp lại quá trình này cho đến khi tìm thấy phần tử có giá trị X hoặc phạm vi tìm kiếm của
chúng ta không còn nữa (First > Last).
b. Thuật toán đệ quy (Recursion Algorithm):
B1: First = 1
B2: Last = N
B3: IF (First > Last) // Hết phạm vi tìm kiếm
B3.1: Không tìm thấy
B3.2: Thực hiện Bkt
B4: Mid = (First + Last)/ 2
B5: IF (X = M[Mid])
B5.1: Tìm thấy tại vị trí Mid
B5.2: Thực hiện Bkt
B6: IF (X < M[Mid])
Tìm đệ quy từ First đến Last = Mid – 1
B7: IF (X > M[Mid])
Tìm đệ quy từ First = Mid + 1 đến Last
Bkt: Kết thúc
c. Cài đặt thuật toán đệ quy:
Hàm BinarySearch có prototype: int BinarySearch (T M[], int N, T X);
Hàm thực hiện việc tìm kiếm phần tử có giá trị X trong mảng M có N phần tử đã có thứ tự
tăng. Nếu tìm thấy, hàm trả về một số nguyên có giá trị từ 0 đến N-1 là vị trí tương ứng của phần tử
tìm thấy. Trong trường hợp ngược lại, hàm trả về giá trị –1 (không tìm thấy). Hàm BinarySearch sử
dụng hàm đệ quy RecBinarySearch có prototype: int RecBinarySearch(T M[], int First, int
Last, T X);
Hàm RecBinarySearch thực hiện việc tìm kiếm phần tử có giá trị X trên mảng M trong phạm
vi từ phần tử thứ First đến phần tử thứ Last. Nếu tìm thấy, hàm trả về một số nguyên có giá trị từ
First đến Last là vị trí tương ứng của phần tử tìm thấy.
Trong trường hợp ngược lại, hàm trả về giá trị –1 (không tìm thấy). Nội dung của các hàm
như sau:
int RecBinarySearch (T M[], int First, int Last, T X) {
if (First > Last)
return (-1);
int Mid = (First + Last)/2;
if (X == M[Mid])
return (Mid);
if (X < M[Mid])
return(RecBinarySearch(M, First, Mid – 1, X));
else
return(RecBinarySearch(M, Mid + 1, Last, X));
}
int BinarySearch (T M[], int N, T X){
return (RecBinarySearch(M, 0, N – 1, X));
}
d. Phân tích thuật toán đệ quy:
- Trường hợp tốt nhất khi phần tử ở giữa của mảng có giá trị bằng X:
Số phép gán: Gmin = 1
Số phép so sánh: Smin = 2
- Trường hợp xấu nhất khi không tìm thấy phần tử nào có giá trị bằng X:
Số phép gán: Gmax = log2N + 1
Số phép so sánh: Smax = 3log2N + 1
- Trung bình:
Số phép gán: Gavg = ½ log2N + 1
Số phép so sánh: Savg = ½(3log2N + 3)
e. Thuật toán không đệ quy (Non-Recursion Algorithm):
B1: First = 1
B2: Last = N
B3: IF (First > Last)
B3.1: Không tìm thấy
B3.2: Thực hiện Bkt
B4: Mid = (First + Last)/ 2
B5: IF (X = M[Mid])
B5.1: Tìm thấy tại vị trí Mid
B5.2: Thực hiện Bkt
B6: IF (X < M[Mid])
B6.1: Last = Mid – 1
B6.2: Lặp lại B3
B7: IF (X > M[Mid])
B7.1: First = Mid + 1
B7.2: Lặp lại B3
Bkt: Kết thúc
f. Cài đặt thuật toán không đệ quy:
Hàm NRecBinarySearchcó prototype: int NRecBinarySearch (T M[], int N, T X);
Hàm thực hiện việc tìm kiếm phần tử có giá trị X trong mảng M có N phần tử đã có thứ tự tăng. Nếu
tìm thấy, hàm trả về một số nguyên có giá trị từ 0 đến N-1 là vị trí tương ứng của phần tử tìm thấy.
Trong trường hợp ngược lại, hàm trả về giá trị -1 (không tìm thấy).
Nội dung của hàm NRecBinarySearchnhư sau:
int NRecBinarySearch (T M[], int N, T X){
int First = 0;
int Last = N – 1;
while (First <= Last){
int Mid = (First + Last)/2;
if (X == M[Mid])
return(Mid);
if (X < M[Mid])
Last = Mid – 1;
else
First = Mid + 1;
}
return(-1);
}
g. Phân tích thuật toán không đệ quy:
- Trường hợp tốt nhất khi phần tử ở giữa của mảng có giá trị bằng X:
Số phép gán: Gmin = 3
Số phép so sánh: Smin = 2
- Trường hợp xấu nhất khi không tìm thấy phần tử nào có giá trị bằng X:
Số phép gán: Gmax = 2log2N + 4
Số phép so sánh: Smax = 3log2N + 1
- Trung bình:
Số phép gán: Gavg = log2N + 3.5
Số phép so sánh: Savg = ½(3log2N + 3)
h. Ví dụ:
Giả sử ta có dãy M gồm 10 phần tử có khóa như sau (N = 10):
1
3
4
5
8
15
17
22
25
30
- Trước tiên ta thực hiện tìm kiếm phần tử có giá trị X = 5 (tìm thấy):
Kết quả sau 3 lần lặp (đệ quy) thuật toán kết thúc.
- Bây giờ ta thực hiện tìm kiếm phần tử có giá trị X = 7 (không tìm thấy):
Kết quả sau 4 lần lặp (đệ quy) thuật toán kết thúc.
Lưu ý:
. Thuật toán tìm nhị phân chỉ có thể vận dụng trong trường hợp dãy/mảng đã có thứ tự.
Trong trường hợp tổng quát chúng ta chỉ có thể áp dụng thuật toán tìm kiếm tuần tự.
. Các thuật toán đệ quy có thể ngắn gọn song tốn kém bộ nhớ để ghi nhận mã lệnh
chương trình (mỗi lần gọi đệ quy) khi chạy chương trình, do vậy có thể làm cho
chương trình chạy chậm lại. Trong thực tế, khi viết chương trình nếu có thể chúng ta
nên sử dụng thuật toán không đệ quy.
2.3. Các giải thuật tìm kiếm ngoại (Tìm kiếm trên tập tin)
2.3.1. Đặt vấn đề
Giả sử chúng ta có một tập tin F lưu trữ N phần tử. Vấn đề đặt ra là có hay không phần tử có
giá trị bằng X được lưu trữ trong tập tin F? Nếu có thì phần tử có giá trị bằng X là phần tử nằm ở vị
trí nào trên tập tin F?
2.3.2. Tìm tuyến tính
a. Tư tưởng:
Lần lượt đọc các phần tử từ đầu tập tin F và so sánh với giá trị X cho đến khi đọc được phần
tử có giá trị X hoặc đã đọc hết tập tin F thì kết thúc.
b. Thuật toán:
B1: k = 0
B2: rewind(F)
// Về đầu tập tin F
B3: read(F, a)
// Đọc một phần tử từ tập tin F
// Vị trí phần tử hiện hành (sau phần tử mới đọc)
B4: k = k + sizeof(T)
B5: IF a ≠ X AND !(eof(F))
Lặp lại B3
B6: IF (a = X)
Tìm thấy tại vị trí k byte(s) tính từ đầu tập tin
B7: ELSE
Không tìm thấy phần tử có giá trị X
B8: Kết thúc
c. Cài đặt thuật toán:
Hàm FLinearSearchcó prototype: long FLinearSearch (char * FileName, T X);
Hàm thực hiện tìm kiếm phần tử có giá trị X trong tập tin có tên FileName. Nếu tìm thấy,
hàm trả về một số nguyên có giá trị từ 0 đến filelength(FileName)là vị trí tương ứng của phần tử
tìm thấy so với đầu tập tin (tính bằng byte). Trong trường hợp ngược lại, hoặc có lỗi khi thao tác trên
tập tin hàm trả về giá trị -1 (không tìm thấy hoặc lỗi thao tác trên tập tin). Nội dung của hàm như sau:
long FLinearSearch (char * FileName, T X){
FILE *Fp;
Fp = fopen(FileName, “rb”);
if (Fp == NULL)
return (-1);
long k = 0;
T a;
int SOT = sizeof(T);
while (!feof(Fp)) {
if (fread(&a, SOT, 1, Fp) == 0)
break;
k = k + SOT;
if (a == X)
break;
}
fclose(Fp);
if (a == X)
return (k - SOT);
return (-1);
}
d. Phân tích thuật toán:
- Trường hợp tốt nhất khi phần tử đầu tiên của tập tin có giá trị bằng X:
Số phép gán: Gmin = 1 + 2 = 3
Số phép so sánh: Smin = 2 + 1 = 3
Số lần đọc tập tin: Dmin = 1
- Trường hợp xấu nhất khi không tìm thấy phần tử nào có giá trị bằng X:
Số phép gán: Gmax = N + 2
Số phép so sánh: Smax = 2N + 1
Số lần đọc tập tin: Dmax = N
- Trung bình:
Số phép gán: Gavg = ½(N + 5)
Số phép so sánh: Savg = (3 + 2N + 1) : 2 = N + 2
Số lần đọc tập tin: Davg = ½(N + 1)
2.3.3. Tìm kiếm theo chỉ mục (Index Search)
Như chúng ta đã biết, mỗi phần tử dữ liệu được lưu trữ trong tập tin dữ liệu F thường có kích
thước lớn, điều này cũng làm cho kích thước của tập tin F cũng khá lớn. Vì vậy việc thao tác dữ liệu
trực tiếp lên tập tin F sẽ trở nên lâu, chưa kể sự mất an toàn cho dữ liệu trên tập tin. Để giải quyết
vấn đề này, đi kèm theo một tập tin dữ liệu thường có thêm các tập tin chỉ mục (Index File) để làm
nhiệm vụ điều khiển thứ tự truy xuất dữ liệu trên tập tin theo một khóa chỉ mục (Index key) nào đó.
Mỗi phần tử dữ liệu trong tập tin chỉ mục IDX gồm có 2 thành phần: Khóa chỉ mục và Vị trí vật lý
của phần tử dữ liệu có khóa chỉ mục tương ứng trên tập tin dữ liệu. Cấu trúc dữ liệu của các phần tử
trong tập tin chỉ mục như sau:
typedef struct IdxElement {
T IdxKey;
long Pos;
} IdxType;
Tập tin chỉ mục luôn luôn được sắp xếp theo thứ tự tăng của khóa chỉ mục. Việc tạo tập tin
chỉ mục IDX sẽ được nghiên cứu trong Chương 3, trong phần này chúng ta xem như đã có tập tin chỉ
mục IDX để thao tác.
a. Tư tưởng:
Lần lượt đọc các phần tử từ đầu tập tin IDX và so sánh thành phần khóa chỉ mục với giá trị X
cho đến khi đọc được phần tử có giá trị khóa chỉ mục lớn hơn hoặc bằng X hoặc đã đọc hết tập tin
IDX thì kết thúc. Nếu tìm thấy thì ta đã có vị trí vật lý của phần tử dữ liệu trên tập tin dữ liệu F, khi
đó chúng ta có thể truy cập trực tiếp đến vị trí này để đọc dữ liệu của phần tử tìm thấy.
b. Thuật toán:
B1: rewind(IDX)
B2: read(IDX, ai)
B3: IF ai.IdxKey < X AND !(eof(IDX))
Lặp lại B2
B4: IF ai.IdxKey = X
Tìm thấy tại vị trí ai.Pos byte(s) tính từ đầu tập tin
B5: ELSE
Không tìm thấy phần tử có giá trị X
B6: Kết thúc
c. Cài đặt thuật toán:
Hàm IndexSearch có prototype: long IndexSearch (char * IdxFileName, T X);
Hàm thực hiện tìm kiếm phần tử có giá trị X dựa trên tập tin chỉ mục có tên IdxFileName.
Nếu tìm thấy, hàm trả về một số nguyên có giá trị từ 0 đến filelength(FileName)-1là vị trí tương
ứng của phần tử tìm thấy so với đầu tập tin dữ liệu (tính bằng byte). Trong trường hợp ngược lại,
hoặc có lỗi khi thao tác trên tập tin chỉ mục hàm trả về giá trị -1 (không tìm thấy). Nội dung của hàm
như sau:
long IndexSearch (char * IdxFileName, T X) {
FILE * IDXFp;
IDXFp = fopen(IdxFileName, “rb”);
if (IDXFp == NULL)
return (-1);
IdxType ai;
int SOIE = sizeof(IdxType);
while (!feof(IDXFp)){
if (fread(&ai, SOIE, 1, IDXFp) == 0)
break;
if (ai.IdxKey >= X)
break;
}
fclose(IDXFp);
if (ai.IdxKey == X)
return (ai.Pos);
return (-1);
}
d. Phân tích thuật toán:
- Trường hợp tốt nhất khi phần tử đầu tiên của tập tin chỉ mục có giá trị khóa chỉ mục lớn hơn hoặc
bằng X:
Số phép gán: Gmin = 1
Số phép so sánh: Smin = 2 + 1 = 3
Số lần đọc tập tin: Dmin = 1
- Trường hợp xấu nhất khi mọi phần tử trong tập tin chỉ mục đều có khóa chỉ mục nhỏ hơn giá trị X:
Số phép gán: Gmax = 1
Số phép so sánh: Smax = 2N + 1
Số lần đọc tập tin: Dmax = N
- Trung bình:
Số phép gán: Gavg = 1
Số phép so sánh: Savg = (3 + 2N + 1) : 2 = N + 2
Số lần đọc tập tin: Davg = ½(N + 1)
Câu hỏi và Bài tập
1. Trình bày tư tưởng của các thuật toán tìm kiếm: Tuyến tính, Nhị phân, Chỉ mục? Các thuật toán
này có thể được vận dụng trong các trường hợp nào? Cho ví dụ?
2. Cài đặt lại thuật toán tìm tuyến tính bằng các cách:
- Sử dụng vòng lặp for,
- Sử dụng vòng lặp do … while?
Có nhận xét gì cho mỗi trường hợp?
3. Trong trường hợp các phần tử của dãy đã có thứ tự tăng, hãy cải tiến lại thuật toán tìm tuyến tính?
Cài đặt các thuật toán cải tiến? Đánh giá và so sánh giữa thuật toán nguyên thủy với các thuật toán
cải tiến.
4. Trong trường hợp các phần tử của dãy đã có thứ tự giảm, hãy trình bày và cài đặt lại thuật toán tìm
nhị phân trong hai trường hợp: Đệ quy và Không đệ quy?
5. Vận dụng thuật toán tìm nhị phân, hãy cải tiến và cài đặt lại thuật toán tìm kiếm dựa theo tập tin
chỉ mục? Đánh giá và so sánh giữa thuật toán nguyên thủy với các thuật toán cải tiến?
6. Sử dụng hàm random trong C để tạo ra một dãy (mảng) M có tối thiểu 1.000 số nguyên, sau đó
chọn ngẫu nhiên (cũng bằng hàm random) một giá trị nguyên K. Vận dụng các thuật toán tìm tuyến
tính, tìm nhị phân để tìm kiếm phần tử có giá trị K trong mảng M. Với cùng một dữ liệu như nhau,
cho biết thời gian thực hiện các thuật toán.
7. Trình bày và cài đặt thuật toán tìm tuyến tính đối với các phần tử trên mảng hai chiều trong hai
trường hợp:
- Không sử dụng phần tử “Cầm canh”.
- Có sử dụng phần tử “Cầm canh”.
Cho biết thời gian thực hiện của hai thuật toán trong hai trường hợp trên.
8. Sử dụng hàm random trong C để tạo ra tối thiểu 1.000 số nguyên và lưu trữ vào một tập tin có tên
SONGUYEN.DAT, sau đó chọn ngẫu nhiên (cũng bằng hàm random) một giá trị nguyên K. Vận
dụng thuật toán tìm tuyến tính để tìm kiếm phần tử có giá trị K trong tập tin SONGUYEN.DAT.
9. Thông tin về mỗi nhân viên bao gồm: Mã số - là một số nguyên dương, Họ và Đệm - là một chỗi
có tối đa 20 ký tự, Tên nhân viên - là một chuỗi có tối đa 10 ký tự, Ngày, Tháng, Năm sinh - là các
số nguyên dương, Phái - Là “Nam” hoặc “Nữ”, Hệ số lương, Lương căn bản, Phụ cấp - là các số
thực. Viết chương trình nhập vào danh sách nhân viên (ít nhất là 10 người, không nhập trùng mã giữa
các nhân viên với nhau) và lưu trữ danh sách nhân viên này vào một tập tin có tên NHANSU.DAT,
sau đó vận dụng thuật toán tìm tuyến tính để tìm kiếm trên tập tin NHANSU.DAT xem có hay không
nhân viên có mã là K (giá trị của K có thể nhập vào từ bàn phím hoặc phát sinh bằng hàm random).
Nếu tìm thấy nhân viên có mã là K thì in ra màn hình toàn bộ thông tin về nhân viên này.
10. Với tập tin dữ liệu có tên NHANSU.DAT trong bài tập 9, thực hiện các yêu cầu sau:
- Tạo một bảng chỉ mục theo Tên nhân viên.
- Tìm kiếm trên bảng chỉ mục xem trong tập tin NHANSU.DAT có hay không nhân viên có
tên là X, nếu có thì in ra toàn bộ thông tin về nhân viên này.
- Lưu trữ bảng chỉ mục này vào trong tập tin có tên NSTEN.IDX.
- Vận dụng thuật toán tìm kiếm dựa trên tập tin chỉ mục NSTEN.IDX để tìm xem có hay
không nhân viên có tên là X trong tập tin NHANSU.DAT, nếu có thì in ra toàn bộ thông tin về nhân
viên này.
- Có nhận xét gì khi thực hiện tìm kiếm dữ liệu trên tập tin bằng các phương pháp: Tìm tuyến
tính và Tìm kiếm dựa trên tập tin chỉ mục.
Chương 3: KỸ THUẬT SẮP XẾP (SORTING)
3.1. Khái quát về sắp xếp
Để thuận tiện và giảm thiểu thời gian thao tác mà đặc biệt là để tìm kiếm dữ liệu dễ dàng và
nhanh chóng, thông thường trước khi thao tác thì dữ liệu trên mảng, trên tập tin đã có thứ tự. Do vậy,
thao tác sắp xếp dữ liệu là một trong những thao tác cần thiết và thường gặp trong quá trình lưu trữ,
quản lý dữ liệu.
Thứ tự xuất hiện dữ liệu có thể là thứ tự tăng (không giảm dần) hoặc thứ tự giảm (không tăng
dần). Trong phạm vi chương này chúng ta sẽ thực hiện việc sắp xếp dữ liệu theo thứ tự tăng. Việc
sắp xếp dữ liệu theo thứ tự giảm hoàn toàn tương tự.
Có rất nhiều thuật toán sắp xếp song chúng ta có thể phân chia các thuật toán sắp xếp thành
hai nhóm chính căn cứ vào vị trí lưu trữ của dữ liệu trong máy tính, đó là:
- Các giải thuật sắp xếp thứ tự nội (sắp xếp thứ tự trên dãy/mảng),
- Các giải thuật sắp xếp thứ tự ngoại (sắp xếp thứ tự trên tập tin/file).
Cũng như trong chương trước, chúng ta giả sử rằng mỗi phần tử dữ liệu được xem xét có một
thành phần khóa (Key) để nhận diện, có kiểu dữ liệu là T nào đó, các thành phần còn lại là thông tin
(Info) liên quan đến phần tử dữ liệu đó. Như vậy mỗi phần tử dữ liệu có cấu trúc dữ liệu như sau:
typedef struct DataElement {
T Key;
InfoType Info;
} DataType;
Trong chương này nói riêng và tài liệu này nói chung, các thuật toán sắp xếp của chúng ta là
sắp xếp sao cho các phần tử dữ liệu có thứ tự tăng theo thành phần khóa (Key) nhận diện. Để đơn
giản, chúng ta giả sử rằng mỗi phần tử dữ liệu chỉ là thành phần khóa nhận diện.
3.2. Các giải thuật sắp xếp nội (Sắp xếp trên dãy/mảng)
Ở đây, toàn bộ dữ liệu cần sắp xếp được đưa vào trong bộ nhớ trong (RAM). Do vậy, số phần
tử dữ liệu không lớn lắm do giới hạn của bộ nhớ trong, tuy nhiên tốc độ sắp xếp tương đối nhanh.
Các giải thuật sắp xếp nội bao gồm các nhóm sau:
- Sắp xếp bằng phương pháp đếm (counting sort),
- Sắp xếp bằng phương pháp đổi chỗ (exchange sort),
- Sắp xếp bằng phương pháp chọn lựa (selection sort),
- Sắp xếp bằng phương pháp chèn (insertion sort),
- Sắp xếp bằng phương pháp trộn (merge sort).
Trong phạm vi của giáo trình này chúng ta chỉ trình bày một số thuật toán sắp xếp tiêu biểu trong các
thuật toán sắp xếp ở các nhóm trên và giả sử thứ tự sắp xếp N phần tử có kiểu dữ liệu T trong mảng
M là thứ tự tăng.
3.2.1. Sắp xếp bằng phương pháp đổi chỗ (Exchange Sort)
Các thuật toán trong phần này sẽ tìm cách đổi chỗ các phần tử đứng sai vị trí (so với mảng đã
sắp xếp) trong mảng M cho nhau để cuối cùng tất cả các phần tử trong mảng M đều về đúng vị trí
như mảng đã sắp xếp.
Các thuật toán sắp xếp bằng phương pháp đổi chỗ bao gồm:
- Thuật toán sắp xếp nổi bọt (Bubble sort),
- Thuật toán sắp xếp lắc (Shaker sort),
- Thuật toán sắp xếp giảm độ tăng hay độ dài bước giảm dần (Shell sort),
- Thuật toán sắp xếp dựa trên sự phân hoạch (Quick sort).
Ở đây chúng ta trình bày hai thuật toán phổ biến là thuật toán sắp xếp nổi bọt và sắp
xếp dựa trên sự phân hoạch.
a. Thuật toán sắp xếp nổi bọt (Bubble Sort):
- Tư tưởng:
+ Đi từ cuối mảng về đầu mảng, trong quá trình đi nếu phần tử ở dưới (đứng phía sau) nhỏ
hơn phần tử đứng ngay trên (trước) nó thì theo nguyên tắc của bọt khí phần tử nhẹ sẽ bị “trồi” lên
phía trên phần tử nặng (hai phần tử này sẽ được đổi chỗ cho nhau). Kết quả là phần tử nhỏ nhất (nhẹ
nhất) sẽ được đưa lên (trồi lên) trên bề mặt (đầu mảng) rất nhanh.
+ Sau mỗi lần đi chúng ta đưa được một phần tử trồi lên đúng chỗ. Do vậy, sau N - 1 lần đi
thì tất cả các phần tử trong mảng M sẽ có thứ tự tăng.
- Thuật toán:
B1: First = 1
B2: IF (First = N)
Thực hiện Bkt
B3: ELSE
B3.1: Under = N
B3.2: If (Under = First)
Thực hiện B4
B3.3: Else
B3.3.1: if (M[Under] < M[Under - 1])
Swap(M[Under], M[Under -1]) //Đổi chỗ 2 phần tử cho nhau
B3.3.2: Under--
B3.3.3: Lặp lại B3.2
B4: First++
B5: Lặp lại B2
Bkt: Kết thúc
- Cài đặt thuật toán:
Hàm BubbleSortcó prototype như sau: void BubbleSort(T M[], int N);
Hàm thực hiện việc sắp xếp N phần tử có kiểu dữ liệu T trên mảng M theo thứ tự tăng dựa
trên thuật toán sắp xếp nổi bọt. Nội dung của hàm như sau:
void BubbleSort(T M[], int N) {
for (int I = 0; I < N-1; I++)
for (int J = N-1; J > I; J--)
if (M[J] < M[J-1])
Swap(M[J], M[J-1]);
return;
}
Hàm Swapcó prototype như sau: void Swap(T &X, T &Y);
Hàm thực hiện việc hoán vị giá trị của hai phần tử X và Y cho nhau. Nội dung của hàm như sau:
void Swap(T &X, T &Y) {
T Temp = X;
X = Y;
Y = Temp;
return;
}
- Ví dụ minh họa thuật toán:
Giả sử ta cần sắp xếp mảng M có 10 phần tử sau (N = 10):
M:
15
10
2
20
10
5
25
35
22
30
Ta sẽ thực hiện 9 lần đi (N - 1 = 10 - 1 = 9) để sắp xếp mảng M:
Tải về để xem bản đầy đủ
246 trang
04/05/2022
7080
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Cấu trúc dữ liệu và giải thuật", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- giao_trinh_cau_truc_du_lieu_va_giai_thuat.pdf
