Bài giảng:
Cấu trúc dữ liệu
và giải thuật
Biên soạn: Đoàn Trọng Huấn
BM Công Nghệ Thông Tin
Nội dung
4.1. Giới thiệu
Trong các hệ lưu trữ, quản lý dữ liệu, thao tác tìm kiếm thường được thực hiện nhất để khai thác thông tin:
Ví du: tra cứu từ điển, tìm sách trong thư viện...
Hệ thống thông tin lưu trữ một khối lượng dữ liệu đáng kể
 xây dựng các giải thuật cho phép tìm kiếm…
Nếu dữ liệu trong hệ thống được tổ chức theo một trật tự  việc tìm kiếm sẽ tiến hành nhanh chóng và hiệu quả hơn:
Ví dụ: các từ trong từ điển được sắp xếp theo từng vần, trong mỗi vần lại được sắp xếp theo trình tự alphabet; sách trong thư viện được xếp theo chủ đề…
4.1. Giới thiệu
4.2. Các giải thuật tìm kiếm
Giả sử chọn cấu trúc dữ liệu mảng để lưu trữ dãy số và khoá cần tìm là x, ta có khai báo:
int a[N];
int x;
4.2.1.Tìm kiếm tuyến tính-LinearSearch
Kết quả
Giải thuật:
Bước 1: i = 1; // bắt đầu từ phần tử đầu tiên của dãy
Bước 2: So sánh a[i] với x, có 2 khả năng:
a[i] = x: Tìm thấy. Dừng.
a[i] != x: Sang Bước 3.
Bước 3: i = i+1; // xét tiếp phần tử kế trong mảng
Nếu i > N: Hết mảng, không tìm thấy. Dừng.
Ngược lại: Lặp lại Bước 2.
Ví dụ:
Cho dãy số a:
12 2 8 5 1 6 4 15
Nếu giá trị cần tìm là x = 8, giải thuật được tiến hành như sau:
i = 1
i = 2
i = 3
Dừng: In ra kết quả.
Mã C++:
int LinearSearch (int a[], int N, int x) {
int i = 0;
while ((iif (i==N)
return -1; // tìm hết mảng nhưng không có x
return i; // a[i] là phần tử có khoá x
}
Nhận xét: mỗi lần lặp của vòng lặp while phải tiến thành kiểm tra 2 điều kiện:
ia[i]!=x: điều kiện kiểm tra chính
Mã C++ cải tiến:
int LinearSearch (int a[], int N, int x) {
int i = 0;
a[N] = x; // thêm phần tử thứ N+1
while (a[i]!=x) i++;
if (i==N)
return -1; // tìm hết mảng nhưng không có x
return i; // a[i] là phần tử có khoá x
}
Nhận xét: mỗi lần lặp của vòng lặp while chỉ tiến thành kiểm tra 1 điều kiện: a[i]!=x
Ðánh giá giải thuật:
Có thể ước lượng độ phức tạp của giải thuật tìm kiếm qua số lượng các phép so sánh được tiến hành để tìm ra x. Ta có bảng phân tích sau:
Độ phức tạp tính toán cấp n: T(n) = O(n)
Nhận xét:
Lưu ý: Kỹ thuật cài đặt ảnh hưởng đến tốc độ thực hiện của thuật toán.
4.2.2. Tìm kiếm nhị phân-BinarySearch
Kết quả
Giải thuật:
Bước 1: left = 1; right = N; // tìm kiếm trên tất cả các phần tử.
Bước 2: Nếu left ≤ right // còn phần tử chưa xét → tìm tiếp
Sang Bước 3.
Ngược lại: Dừng; // đã xét hết tất cả các phần tử
Bước 3: mid = (left + right)/2; //lấy mốc so sánh
a[mid] = x: Tìm thấy. Dừng.
a[mid] > x: // tìm tiếp x trong dãy con a[left].. a[mid -1]
right =mid - 1;
a[mid] < x: // tìm tiếp x trong dãy con a[mid+1]..a[right]
left =mid + 1;
Lặp lại Bước 2.
Ví dụ:
Cho dãy số a:
1 2 4 5 6 8 12 15
Nếu giá trị cần tìm là x = 8, giải thuật được tiến hành như sau:
left = 1
right = 8
mid = 4
left = 5
right = 8
mid = 6
Dừng: In ra kết quả.
Mã C++:
int BinarySearch(int a[],int N,int x ){
int left = 0; right = N-1;
int mid;
while (left<=right) {
mid = (left + right)/2;
if (x = a[mid]) return mid; // thấy x tại mid
else
if (x else left = mid +1;
}
return -1; // tìm hết dãy mà không có x
}
Ðánh giá giải thuật:
Ta có bảng phân tích sau:
Độ phức tạp tính toán cấp n: T(n) = O(logn)
Nhận xét:
T(nhị phân) = O(logn)
^
T(tuyến tính) = O(n)
chỉ áp dụng cho những dãy đã có thứ tự
4.3. Các giải thuật sắp xếp cơ bản
Giải thuật:
Khái niệm nghịch thế:
Xét một mảng các số a0, a1,. an.
Nếu có i < j và ai > aj, thì ta gọi đó là một nghịch thế.
Mảng chưa sắp xếp sẽ có nghịch thế.
Mảng đã có thứ tự sẽ không chứa nghịch thế. Khi đó a0 sẽ là phần tử nhỏ nhất rồi đến a1, a2,…
a0 ≤ a1 ≤ a2 ≤ … ≤ an
Như vậy, để sắp xếp một mảng, ta có thể tìm cách giảm số các nghịch thế trong mảng này bằng cách hoán vị các cặp phần tử ai, aj nếu có i < j và ai > aj theo một qui luật nào đó.
4.1. Giới thiệu
Cho trước một dãy số a1, a2,..., aN được lưu trữ trong cấu trúc dữ liệu mảng int a[N];
Sắp xếp dãy số a1, a2,..., aN là thực hiện việc bố trí lại các phần tử
dãy mới ak1, ak2,..., akN có thứ tự (giả sử xét thứ tự tăng) nghĩa là aki ≤ aki-1.
4.3.1 Sắp xếp kiểu lựa chọn (Selection Sort)
Bước 1: : i = 1; // bắt đầu từ phần tử đầu tiên của mảng.
Bước 2: Tìm phần tử a[min] nhỏ nhất trong dãy hiện hành từ a[i] đến a[N]
Bước 3: Hoán vị a[min] và a[i]
Bước 4:
Nếu i ≤ N-1 thì i = i+1; Lặp lại Bước 2
Ngược lại: Dừng. //N-1 phần tử đã nằm đúng vị trí.
Mã C++:
void SelectionSort(int a[],int N ) {
int min; // chỉ số phần tử nhỏ nhất trong dãy hiện hành
for (int i=0; imin = i;
for(int j = i+1; j if (a[j ] < a[min])
min = j; // ghi nhận vị trí phần tử hiện nhỏ nhất
Hoanvi(a[min], a[i]);
}
}
Ðánh giá giải thuật:
Ta có bảng phân tích sau:
Độ phức tạp tính toán cấp n: T(n) = O(logn)
Bài tập
Thể hiện trực quan các thao tác của thuật toán. Tính thời gian thực hiện của mỗi thuật toán.
Hãy viết hàm tìm tất cả các số nguyên tố nằm trong mảng một chiều a có n phần tử.
Cài đặt các thuật toán  sắp xếp đã trình bày. Thể hiện trực quan các thao tác của thuật toán. Tính thời gian thực hiện của mỗi thuật toán.
Cho dãy số 5 1 2 8 4 7 0 12 4 3 24 1 4, hãy minh hoạ kết qủa sắp xếp dãy số này từng bước với các giải thuật chọn trực tiếp, chèn trực tiếp, nổi bọt
Đoàn Trọng Huấn