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.

ỉ ố

ị

ả

không đòi h i các ỏ đ c bi

t

 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ế đ aủ cượ tìm th yấ , ch s c cượ trả về.N u tìm ki m đ nó(v trí trong m ng) ế ế không thành công thì tr v -1. ả ề  L u ý r ng tìm ki m tu n t ầ ự c đ t theo 1 th t ặ

ế i đ ả ượ

ứ ự ặ

ệ

ằ ư f n t c a list f ầ ử ủ 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 int sequential_search(char* items,int count,char key) {

Register int t; for(t=0;t

} 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

Chúng ta có thể tránh ki mể tra cu iố m ngả cướ l pặ b ngằ cách chèn 1 giá nầ

đ hành.

ầ ị ị

Ta đặt nó t

trong m iỗ b tr đích (giá tr mà ta c n tìm) nh là 1 f ư tử ”lính canh” vào cu iố c aủ m ngả .

iạ vị trí n và làm theo thu tậ toán

sau:

Sentinel

Tìm ki mế tu nầ tự từ vị trí 0 cho đ nế khi giá

ị ắ cượ tìm th yấ .(Giá tr này ch c

c tìm th y)

ắ ế

trị đích đ ch n s đ ẽ ượ N u giá tr đ ị ượ canh đã đ ượ ế

ấ c tìm th y v trí n thì lính ấ ở ị c tìm th y, tìm ki m th t b i. ấ ấ ạ N u không thì tìm ki m thành công, tr v ả ề ế đó giá tr đích đ c ượ ị ở

ế ch s đ u tiên mà ỉ ố ầ tìm th y.ấ

Tìm ki mế lính canh

int LinearSentinelSearch (T M[], int N, T X){ int k = 0; M[N]=X; while (M[k] != X) k++; return k-1; }

Exercise 6-1

tế 1 quy nể danh bạ.

ngườ

tế 1

 Giả sử r ngằ b nạ vi  Khai báo 1 c uấ trúc “Address” ch aứ ít nh tấ các tr name, telephone number, email address, và vi chương trình có thể thao tác v iớ 100 đ aị

chỉ.

 Đ cọ kho ngả 10 đ aị

ằ

chỉ từ file đ uầ vào, tìm ki mế 1 name ìm ki mế tu nầ tự, và ghi dữ li uệ fù h pợ đ uầ tiên ra

-

ấ

-

ươ ươ

ng trình này s d ng m ng c u trúc. ả ử ụ ử d ngụ danh sách liên ng trình này s cượ tăng

b ng t file đ uầ ra. (1) Tri nể khai ch (2) Tri nể khai ch k tế đơn ho cặ đôi. Xác th cự tìm ki mế thứ 2 đã đ t cố b ngằ cách chuy nể dữ li uệ fù h pợ lên đ uầ c aủ list. (Tìm ki m t

ch c). ứ

t ự ổ

ế

Exercise 6-2: tìm ki mế m ngả b ngằ tìm ki mế tu nầ tự Đ cọ 11 số nguyên từ 1 đ uầ vào chu nẩ và

N uế số nguyên thứ 11 có ở trong m ngả

gán 10 số đ uầ tiên vào m ngả .

thì in ra vị trí c aủ nó, n uế không thì in ra 0.

Queue (chuy nể lên tr

c)ướ

 T oạ 1 hàng đ iợ ch aứ các số nguyên, kích th

cướ

queue đ

cượ nấ đ nhị  Đ cọ các số nguyên đ

là 10. cượ fân cách b iở d uấ

kho ngả tr ngố từ 1 đ uầ vào chu nẩ , và thêm chúng vào queue.Khi chương trình đ cọ đ nế số thứ 11, iả lo iạ bỏ số đ uầ hàng đ iợ đã đ yầ .Chương trình f tiên và thêm vào số thứ 11.In ra số bị lo iạ bỏ theo đ uầ ra chu nẩ .

 Ti nế hành v iớ t

tấ cả các số theo cách này.

c)

Tìm ki mế tự s p x p (chuy n lên tr

ế

ể

ắ

ướ

M iỗ f nầ tử đ

cượ tìm ki mế /yêu c uầ đ cượ

Xem hình trong Slide ti ngế anh.

chuy nể lên fía tr cướ .

Tìm ki mế tự s pắ x pế

int search( int key,int r[], int n ) {

int i,j; int tempr; for ( i=0; i0 ) {

tempr = r[i]; for (j=0, j

} return( i ); } else return( -1 );

Tìm ki mế tự s pắ x pế

int search( int key,int r[], int n ) { int i; int tempr; for ( i=0; i0 ) {

c ***/

ướ

/*** Đ iổ chỗ v iớ f nầ tử đi tr tempr = r[i]; r[i] = r[i-1]; r[--i] = tempr; }; return( i ); } else return( -1 );

Exercise : List tự sắp x pế

Sửa 1 list mà b nạ đã t oạ ở bài t pậ tr

cướ

cượ

Phát tri nể hàm tìm ki mế 1 f nầ tử trong list.

c”. mà đ cượ tự s pắ x pế b ngằ chi nế l “chuy n lên tr ể ướ

Exercise : List tự s pắ x pế

Tri nể khai 1 list tự s pắ x pế b ngằ cách sử

d ngụ chi nế l cượ đ iổ chỗ (hoán v ).ị

Exercises  Vi

tế 1 chương trình theo đ cặ tả sau:

[Format] look character_string// đinh dang nh pậ vào [mô t

] ả T tấ cả các từ b tắ đ uầ v iớ xâu kí tự string đã ghi trong file

/user/share/dict/words đ

cượ đưa ra màn hình.

[Ví d ]ụ % look computer computer computerize computerized computerizes computerizing Computers  G iợ ý: Sử d ngụ tham số trong hàm main() để th cự hi nệ yêu c uầ đề

bài.