intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Tìm kiếm và sắp xếp

Chia sẻ: Lê Quảng Vàng | Ngày: | Loại File: PPT | Số trang:0

Thêm vào BST
Báo xấu
47
lượt xem 3
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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. 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....

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tìm kiếm và sắp xếp

  1. Tìm kieám &Saép xeáp
  2. Tìm kieám & Saép xeá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. Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp 2
  3. Nhu caàu tìm kieám vaø saép xeáp döõ lieäu trong 1 heä thoáng thoâng tinheát caùc heä löu tröõ, quaûn lyù  Trong haàu döõ lieäu, thao taùc tìm kieám thöôøng ñöôïc thöïc hieän nhaát ñeå khai thaùc thoâng tin.  Do caùc heä thoáng thoâng tin thöôøng phaûi löu tröõ moät khoái löôïng döõ lieäu ñaùng keå, neân vieäc xaây döïng caùc giaûi thuaät cho pheùp tìm kieám nhanh seõ coù yù nghóa raát lôùn.  Neáu döõ lieäu trong heä thoáng ñaõ ñöôïc toå chöùc theo moät traät töï naøo ñoù, thì vieäc tìm kieám seõ tieán haønh nhanh choùng vaø hieäu quaû hôn Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp 3
  4. Nhu caàu tìm kieám vaø saép xeáp döõ lieäu trong 1 heä thoáng thoâng tingiaûi thuaät tìm kieám vaø saép  Coù nhieàu xeáp  Möùc ñoä hieäu quaû cuûa töøng giaûi thuaät phuï thuoäc vaøo tính chaát cuûa caáu truùc döõ lieäu cuï theå maø noù taùc ñoäng ñeán.  Döõ lieäu ñöôïc löu tröõ chuû yeáu trong boä nhôù chính vaø treân boä nhôù phuï, do ñaëc ñieåm khaùc nhau cuûa thieát bò löu tröõ, caùc thuaät toaùn tìm kieám vaø saép xeáp ñöôïc xaây döïng cho caùc caáu truùc löu tröõ treân boä nhôù chính hoaëc phuï cuõng coù nhöõng ñaëc thuø khaùc nhau.  Chöông naøy seõ trình baøy caùc thuaät toaùn Caáu truùc saép Döõ lieäu -xeáp vaø Tìm kieám tìm vaø Saép xeápkieám döõ lieäu ñöôïc löu 4
  5. Caùc giaûi thuaät tìm kieám noäi Tìm kieám tuaàn töï Tìm kieám nhò phaân
  6. 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; Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp 6
  7. Tìm kieám tuaàn töï
  8. 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. Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp 8
  9. 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 Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp 9
  10. Tìm kieám tuaàn töï  i=2  i=3 Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp 10
  11. Tìm kieám tuaàn töï int LinearSearch(int a[], int N, int x) { for (int i=0; (i
  12. Tìm kieám tuaàn töï  Caûi tieán caøi ñaët: duøng phöông phaùp “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. Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp 12
  13. 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
  14. 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) Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp 14
  15. 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. Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp 15
  16. Tìm kieám nhò phaân
  17. Tìm kieám nhò phaân  Ñoái vôùi nhöõng daõy ñaõ coù 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 . Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp 17
  18. 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 Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp 18
  19. 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 Caáu truùc 3: -Döøng, Döõ lieäu khoâng Tìm kieám vaø Saép xeáptìm thaáy. 19
  20. 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 Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp 20
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2