Slide bài giảng cấu trúc dữ liệu

ðại Học Sư Phạm Tp. Hồ Chí Minh

Chương 2: Tìm kiếm & Sắp xếp

CẤU TRÚC DỮ LIỆU 1

2

Thông tin giảng viên

• LƯƠNG TRẦN HY HIẾN

• Bộ Môn Tin Học

• Khoa Toán – Tin học

• Phone: 0989 366 990

• Email: [email protected]

3

Tìm kiếm & Sắp xếp

Muïc tieâu:

Giôùi thieäu moät soá thuaät toaùn tìm kieám vaø saép xeáp noäi.

Phaân tích, ñaùnh giaù ñoä phöùc taïp cuûa caùc giaûi thuaät tìm

kieám, saép xeáp.

Noäi dung:

Nhu caàu tìm kieám vaø saép xeáp döõ lieäu trong moät heä

thoáng thoâng tin.

Caùc giaûi thuaät tìm kieám noäi.

Caùc giaûi thuaät saép xeáp noäi.

4

Caùc giaûi thuaät

tìm kieám noäi

• Tìm tuần tự

• Tìm nhị phân

Tìm kiếm

5

Caùc giaûi thuaät tìm kieám noäi

Baøi toaùn: Tìm vò trí xuaát hieän cuûa phaàn töû coù

giaù trò x treân danh saùch ñaëc a

Taäp döõ lieäu ñöôïc löu tröõ laø daõy soá a1

, a2

, ... ,aN

int a[N];

Khoaù caàn tìm laø x

int x;

6

Tìm kieám tuaàn töï

Böôùc 1: i = Vò trí ñaàu;

Böôùc 2: Neáu a[i] = x : Tìm thaáy. Döøng, vò trí

xuaát hieän: i

Böôùc 3 : i = Vò trí keá(i);// xeùt tieáp phaàn töû keá

trong maûng

Böôùc 4: Neáu i >Vò trí cuoái: //Heát maûng

Khoâng tìm thaáy. Döøng.

Ngöôïc laïi: Laëp laïi Böôùc 2.

7

Tìm kieám tuaàn töï

Ví duï: Cho daõy soá a

12 2 8 5 1 6 4 15

Giaù trò caàn tìm: 8

i = 1

8

Tìm kieám tuaàn töï

• i = 2

• i = 3

9

Tìm kieám tuaàn töï

int LinearSearch(int a[], int N, int x)

{

for (int i=0; (i<N)&&(a[i]!=x ); i++);

if (i<N)

return i; // a[i] laø phaàn töû coù khoaù x

return -1; // tìm heát maûng nhöng khoâng coù x

}

10

Tìm kieám tuaàn töï

Caûi tieán caøi ñaët: duøng phöông phaùp “ñặt lính

canh”

– Ñaët theâm moät phaàn töû coù giaù trò x vaøo cuoái maûng

– Baûo ñaûm luoân tìm thaáy x trong maûng

– Sau ñoù döïa vaøo vò trí tìm thaáy ñeå keát luaän.

11

Tìm kieám tuaàn töï

int LinearSearch(int a[], int N, int x)

{

// maûng goàm N phaàn töû töø a[0]..a[N-1]

a[N] = x; // theâm lính canh vaøo cuoái daõy

for (int i=0; (a[i]!=x); i++);

if (i<N)

return i; // a[i] laø phaàn töû coù khoaù x

return -1; // tìm heát maûng nhöng khoâng coù x

}

12

Tìm kieám tuaàn töï

Ñaùnh giaù giaûi thuaät:

Vaäy giaûi thuaät tìm tuaàn töï coù ñoä phöùc taïp

tính toaùn caáp n: T(n) = O(n)

13

Tìm kieám tuaàn töï

Nhaän xeùt:

– Giaûi thuaät tìm tuyeán tính khoâng phuï thuoäc vaøo

thöù töï cuûa caùc phaàn töû trong danh saùch, do vaäy

ñaây laø phöông phaùp toång quaùt nhaát ñeå tìm kieám

treân moät danh saùch baát kyø.

– Moät thuaät toaùn coù theå ñöôïc caøi ñaët theo nhieàu

caùch khaùc nhau, kyõ thuaät caøi ñaët aûnh höôûng ñeán

toác ñoä thöïc hieän cuûa thuaät toaùn.

14

Tìm kieám nhò phaân

Ñoái vôùi nhöõng daõy ñaõ sắp thöù töï (giaû söû thöù töï

taêng), caùc phaàn töû trong daõy coù quan heä

ai -1 ≤ ai ≤ ai+1

Neáu x > ai

thì x chæ coù theå xuaát hieän trong

ñoaïn [ai+1 ,aN

] cuûa daõy

Neáu x < ai

thì x chæ coù theå xuaát hieän trong

ñoaïn [a1 ,ai-1] cuûa daõy

15

Tìm kieám nhò phaân

YÙ töôûng cuûa giaûi thuaät laø taïi moãi böôùc tieán

haønh so saùnh x vôùi phaàn töû naèm ôû vò trí giöõa

cuûa daõy tìm kieám hieän haønh, döïa vaøo keát quaû

so saùnh naøy ñeå quyeát ñònh giôùi haïn daõy tìm

kieám ôû böôùc keá tieáp laø nöûa treân hay nöûa döôùi

cuûa daõy tìm kieám hieän haønh

16

Tìm kieám nhò phaân

Böôùc 1: left = VTÑ; right = VTC;

Böôùc 2: Trong khi left ≤ right laëp: //ñoaïn tìm kieám chöa roãng

Böôùc 21: mid = (left+right)/2; // laáy moác so saùnh

Böôùc 22: Neáu a[mid] = x: //Tìm thaáy.

Döøng, vò trí xuaát hieän: mid

Böôùc 23: Neáu a[mid] > x: //tìm x trong daõy con aleft .. amid -1

right = mid - 1;

Ngöôïc laïi //tìm x trong daõy con amid +1 .. aright

left = mid + 1;

//Heát laëp

Böôùc 3: Döøng, khoâng tìm thaáy.

17

Tìm kieám nhò phaân

Ví duï: Cho daõy soá a goàm 8 phaàn töû:

1 2 4 5 6 8 12 15

Giaù trò caàn tìm laø 8

18

Tìm kieám nhò phaân

• left = 1, right = 8, mid = 4