Chủ đề c aủ tu nầ
Các thu tậ toán tìm ki mế
Tìm ki mế tu nầ tự
Sử d ngụ lính gác
Tìm ki mế tự s pắ x pế
Tìm ki mế tu nầ tự (linear search)
Thăm t tấ cả các f nầ tử c aủ m ngả b tắ đ uầ từ f nầ
tử đ uầ tiên.
So sánh key v iớ m iỗ f nầ tử c aủ list ho cặ m ngả.
N uế f nầ tử tìm ki mế đ cượ tìm th yấ, ch s cỉ ố aủ
nó(v trí trong m ng) ị ả đ cượ trả về.N u tìm ki m ế ế
không thành công thì tr v -1.ả ề
L u ý r ng tìm ki m tu n t không đòi h i các ư ằ ế ầ ự ỏ
f n t c a list f i đ c đ t theo 1 th t đ c bi t ầ ử ủ ả ượ ặ ứ ự ặ ệ
nào.
Sequential Search (tìm ki m tu n t )ế ầ ự
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);
}
Ví dụ
#include<stdio.h>
int sequential_search(char* items,int count,char key)
{
Register int t;
for(t=0;t<count;++t)
If(key == items[t]) return t;
return-1;/*không tìm th y*/ấ
}
int main(void){
Char *str = "asdf";
Int index=sequential_search(str,4,'s');
printf("%d",index);
}
Lính canh (Sentinel)
Lưu ý r ngằ m iỗ l nầ l pặ đòi h iỏ 2 đi uề ki nệ
đ cượ ki mể tra và 1 câu l nhệ đ cượ thi
hành.
Chúng ta có thể tránh ki mể tra cu iố m ngả
trong m iỗ b cướ l pặ b ngằ cách chèn 1 giá
tr đích (giá tr mà ta c n tìm) nh là 1 fị ị ầ ư nầ
tử ”lính canh” vào cu iố c aủ m ngả.
Ta đặt nó t iạ vị trí n và làm theo thu tậ toán
sau:
