Cấu trúc dữ liệu chương 2 Sắp xếp tìm kiếm

Chương 2 : Các phương pháp tìm kiếm và sắp xếp

1. Đặt vấn đề

Trong hầu hết 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...

Do các hệ thống thông tin thường phải lưu trữ một khối lượng dữ liệu đáng kể, nên việc xây dựng các giải thuật cho phép tìm kiếm nhanh sẽ có ý nghĩa rất lớn. Nếu dữ liệu trong hệ thống đã được tổ chức theo một trật tự nào đó, thì 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ủ đề ...

Vì thế, khi xây dựng một hệ quản lý thông tin trên máy tính, bên cạnh các thuật toán tìm kiếm, các thuật toán sắp xếp dữ liệu cũng là một trong những chủ đề được quan tâm hàng đầu.

Hiện nay đã có nhiều giải thuật tìm kiếm và sắp xếp dược xây dựng, mức độ hiệu quả của từng giải thuật còn phụ thuộc vào tính chất của cấu trúc dữ liệu cụ thể mà nó tác động đến. Dữ liệu được lưu trữ chủ yếu trong bộ nhớ chính và trên bộ nhớ phụ, do đặc điểm khác nhau của thiết bị lưu trữ, các thuật toán tìm kiếm và sắp xếp được xây dựng cho các cấu trúc lưu trữ trên bộ nhớ chính hoặc phụ cũng có những đặc thù khác nhau. Chương này sẽ trình bày các thuật toán sắp xếp và tìm kiếm dữ liệu được lưu trữ trên bộ nhớ chính - gọi là các giải thuật tìm kiếm và sắp xếp nội và một số giải thuật sắp xếp trên bộ nhớ phụ hay sắp xếp ngoại

2. Đệ qui và tìm kiếm bằng đệ qui

2.1 Khái niệm
Đệ qui là một khái niệm cơ bản trong toán học và khoa học máy tính
Một đối tượng X gọi là được định nghĩa đệ qui nếu trong phát biểu của X có dùng chính đối tượng X. Một chương trình đệ qui là chương trình gọi đến chính nó trong các câu lệnh, tuy nhiên yếu tố bắt buộc đối với một chương trình đệ qui là nó phải có một điều kiện dừng

Đệ quy mạnh ở chỗ có thể định nghĩa một tập rất lớn các tác động chỉ bởi một số rất ít mệnh đề. Một chương trình viết theo giải thuật có tính đệ quy sẽ mang tính “Người” hơn do đó sẽ:

• Sáng sủa
• Dễ hiểu
• Nêu bật được vấn đề

Bản chất của đệ quy là ý tưởng quy nạp hay hạ bậc trong toán học, nghĩa là đưa một số vấn đề phức tạp về một vấn đề đơn giản hơn.
Đệ qui được ứng dụng trong rất nhiều bài toán thực tế nhưng không phải bất cứ bài toán nào được giải bằng phương pháp đệ qui đều tốt do việc sử dụng nhiều bộ nhớ để lưu trữ tạm thời các biến của chương trình đệ qui

Một định nghĩa đệ qui thường có 2 thành phần

• Thành phần cố định (điều kiện dừng) : không có lời gọi đệ qui

Ví dụ : 0! = 1! = 1

• Thành phần đệ qui : ứng với tham số có lời gọi đệ qui đến tham số khác, dần tiến về thành phần cố định

ví dụ : n! = n*(n-1)! neáu n > 1

2.2 Hàm đệ qui
Một hàm là một sự định nghĩa về một công việc nào đó, nên cũng có thể là đệ qui:
Nếu trong hàm P có lời gọi tường minh đến chính nó thì gọi là đệ qui trực tiếp
Nếu trong P có gọi Q, và trong Q lại có lời gọi P thì P được gọi là đệ qui gián tiếp.
Khi hàm gọi đệ qui đến chính nó thì mỗi lần gọi, máy sẽ tạo ra một tập biến cục bộ mới hoàn toàn độc lập với tập biến cục bộ của hàm trước đó.
Cũng như các lệnh lặp, các thủ tục đệ qui cũng có thể thực hiện các tính toán không dừng, vì thế cần chú ý vấn đề kết thúc.
Ví dụ: Xây dựng hàm tính n! theo đệ qui.

long gt(int n)
{ if (n == 0 || n == 1) return 1;
else return (n * gt(n-1));
} Ví dụ: Tính UCLN(x,y) theo thuật toán Euclide
int UCLN(int x, int y)
{ if (y == 0) return x;
else return (ucln(y, x % y));
}

Ví dụ: Dãy số Fibonacci được xác định như sau: F0=1; F1=1; Fn=Fn-1+Fn-2 với n>=2. Hãy xác định phần tử thứ n của của dãy số.

int Fibo(int n)
{ if (n == 0 || (n == 1) return 1;
else return (fibo(n - 1) + fibo(n - 2));
}

Nhận xét: Một hàm đệ quy về căn bản luôn gồm 2 phần.

• Phần dừng: Chứa các tác động của hàm ứng với 1 số giá trị ban đầu của tham số
• Phần hạ bậc: Chứa lời gọi thực hiện hàm với tham số có phạm vi nhỏ hơn.

2.3 Tìm kiếm đệ qui
Nội dung chính của thuật toán là việc xây dựng dần các thành phần của một lời giải hay một cấu hình bằng cách thử tất cả các khả năng.
Giả thiết cấu hình cần tìm được mô tả bằng một bộ n thành phần x1,x2,..,xn.
Giả sử, đã xác định được i - 1 thành phần x1,x2,..,xi-1. Ta cần tìm thành phần xi bằng cách duyệt tất cả các khả năng có thể đề cử cho nó (đánh số các khả năng từ 1 đến ni). Với mỗi khả năng j, kiểm tra xem j có chấp nhận được không:
Nếu chấp nhận j thì xác định xi theo j, sau đó nếu i = n thì ta được một cấu hình ngược lại ta tiếp tục xác định xi+1 .
Nếu thử tất cả các khả năng mà không có khả năng nào được chấp nhận thì quay lại bước trước để xác định lại xi-1 .
Mô hình quay lui được thiết kế đơn giản bằng đệ quy của hàm Try như sau:

/* Xác định thành phần xi bằng đệ quy */
void Try( int i )
{ int j;
If (i > N) < ghi nhận 1 cấu hình>;
else
{
for (j thuộc tập khả năng đề cử )
if < chấp nhận khả năng ( j )> then
{
< Xác định xi theo khả năng ( j ) >
<Ghi nhận khả năng ( j ) đã được chọn cho xi >;
Try( i+1);
< bỏ việc ghi nhận khả năng ( j ) đã chọn cho xi >;
}
}
}

Vấn đề:
Cần xác định được danh sách các khả năng đề cử
Cần ghi nhớ lại những khả năng nào đã được thử để tránh trùng lặp.
Xác định giá trị biểu thức logic . Thông thường giá trị này ngoài việc phụ thuộc j, có phụ thuộc vào việc đã chọn các khả năng tại (i -1) bước trước. Trong những trường hợp như vậy, cần ghi nhớ trạng thái mới của quá trình tìm kiếm sau khi và trả lại trạng thái cũ sau khi đã .
Sau khi xây dựng giải thuật Try, đoạn chương trình chính của bài toán liệt kê có dạng:

main()
{ Init;
Try(i);
}

Ví dụ: Liệt kê các dãy nhị phân có độ dài n.
CTDL: Mảng byte: char X[20]; chứa dãy nhị phân.
Khả năng đề cử cho 1 thành phần X[i] là: 0 và 1

void Try(int i)
{ int j;
if ( i > n ) InKetqua;
else
for (j =0; j<2; j++)
{ X[i] = j;
Try( i + 1 );
}
}

Ví dụ: Liệt kê tất cả (n!) các hoán vị của {1,2,..,n}
Giải: Mỗi hoán vị được tổ chức như 1 mảng gồm n thành phần: x[1], x[2] ,.., x[n] trong đó mỗi x[i] nhận giá trị từ 1 đến n với điều kiện (x[i] != x[j] )với ( i != j ).
Giả sử đã xác định được i -1 thành phần: x1, x2 ,.., xi-1 Ta cần tìm thành phần xi :
Khả năng đề cử cho xi là từ giá trị j =1..n, trong đó j != xk với k=1 .. i-1.
Vì thế cần phải ghi nhớ đối với mỗi khả năng đã đề cử, xem nó đã được dùng hay chưa bằng mảng int chuadung[Max]; trong đó chuadung[ j ]=1 nếu j chưa được sử dụng trong i-1 thành phần trước đó.
/* Liet ke cac Hoan vi cua day so 1..n */

int x[Max], n ;
int gn[Max];/* ghi nhan trang thai da duoc chon hay chua*/
main()
{ memset(x, 0, Max* sizeof(x[0]));
memset(gn, 0, Max * sizeof(gn[0]));
printf(“\nNhap n: “); scanf(“%d”, &n);
Try(1);
}
void Try(int i)
{ int j;
if (i > n) InMotHoanVi();
else
for (j=1; j <= n; j++)
if (!gn[j])
{ x[i] = j;
gn[j] = 1;
Try(i+1);
gn[j] = 1;
}
}
void InMotHoanVi(void)
{ int i; puts("");
for (i=0; i<n; i++)
printf("%-5d",x[i]);
}
Ví dụ: Bài toán ngựa đi tuần trên bàn cờ kích NxN
//số gia tọa độ
int a[8] ={2,1,-1,-2,-2,-1,1,2};
int b[8]={1,2,2,1,-1,-2,-2,-1};
void Try(int i)
{ int j,u,v;
if (i+1> n*n) {print ; Cóđườngđi = 1;}
else
for ( j =0; j < 8 ; j++) //
{ u=x+a[j]; v=y+b[j];
if (u>= 0 && u < n && v >=0 && v<N && h[u,v]==0)
{ h[u,v]=i; x=u; y=v;
Try(i+1);
x=u-a[j]; y=v-a[j]; h[u,v]=0
}
}
}