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

Bài giảng Cấu trúc dữ liệu - Chương 4: Tìm kiếm

Chia sẻ: Đinh Gấu | Ngày: | Loại File: PPT | Số trang:40

72
lượt xem
4
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Chương 4: Tìm kiếm trong "Bài giảng Cấu trúc dữ liệu" trình bày những nội dung chính về các phương pháp tìm kiếm trong danh sách, tìm kiếm tuyến tính, tìm kiếm nhị phân, tìm kiếm nội suy và cây nhị phân tìm kiếm.

Chủ đề:
Lưu

Nội dung Text: Bài giảng Cấu trúc dữ liệu - Chương 4: Tìm kiếm

  1. CHƯƠNG 4­ TÌM  KIẾM 1
  2. CHƯƠNG 4. TÌM KIẾM 4.1 Các phương pháp tìm kiếm trong danh sách 4.1.1 Tìm kiếm tuyến tính ̣ 4.1.2 Tìm kiếm nhi phân ̣ 4.1.1 Tìm kiếm nôi suy ̣ 4.2 Cây nhi phân ti ̀m kiếm ̣ 4.2.1 Đinh nghi ̃a 4.2.2 Các phép toán   2
  3. 4.1 Các phương pháp tìm kiếm  trong danh sách Mô hì nh chung cua bả ̀ i toá n tì m kiế m:  ̣ ̣ Có môt tâp n đô ́i tượng. Mỗi đối tượng có  ̣ ́nh, được thê hiên bă nhiều thuôc ti ̉ ̣ ̣ ̀ng môt kiêu ̉ ̉ ban ghi gô ̀m nhiều trường. Trong đó có 1  trường mà giá tri cua no ̣ ̉ ̣ ưng cho đối  ́ đăc tr tượng, cho phép xác đinh hoa ̣ ̀n toàn đối tượng,  thường goi lạ ̀ khóa. Bài toán tìm kiếm: Có môt tâp ca ̣ ̣ ́c đối  tượng và cho trước môt đô ̣ ́i tượng x. Cần tìm  xem x có măt trong tâp h ̣ ̣ ợp đã cho hay không?   3
  4. 4.1 Các phương pháp tìm kiếm  trong danh sách Mô hì nh toá n hoc cua ba ̣ ̉ ̀ i toá n tì m kiế m: ̣ ợp n giá tri kho Có tâp h ̣ ́a k1, k2, ..kn. Cho giá  ̣ tri kho ̣ ́a x. Tìm xem x có tồn tai ki=x? ̣ ̀m kiếm sẽ hoàn thành khi: Công viêc ti – Tìm được 1 ban ghi co ̉ ̣ ́ giá tri kho ́a =x, lúc đó  phép tìm kiếm được thành công successful. – Không tìm thấy ban ghi na ̉ ̀o có khóa bằng x, goi  ̣ là tìm kiếm không thành công unsuccessful. Lúc  ̉ này có thê xuâ ̣ ́t hiên yêu câ ̉ ̀u bô sung gia ̣ ́ tri x  ̣ ợp, goi la vào tâp h ̣ ̀ tìm kiếm có bô sung. ̉   4
  5. 4.1.1 Tìm kiếm tuần tự  (sequential searching)  Là phương pháp tìm kiếm đơn gian  ̉ ̉ ̉ và cô điên. Ý tưởng: Bắt đầu từ ban ghi th ̉ ứ  nhất, lần lượt so sánh khóa tìm kiếm  với khóa tương ứng cua ban ghi trong  ̉ ̉ ̉ bang, cho t ới khi tìm được ban ghi mong  ̉ ̣ muốn hoăc đa ̉ ̃ hết bang ma ̀ chưa tìm  thấy.   5
  6. 4.1.1 Tìm kiếm tuần tự (sequential  searching) ̉ ̣  Giai thuât 1: SEQUEN­SEARCH(k,n,x) SEQUEN­SEARCH(k,n,x) 1. //Khởởi đâ 1. //Kh i đầ̀uu i=1; k[i+1]=x i=1; k[i+1]=x 2. // Tì̀m kho 2. // Ti m khó́a trong da a trong dã̃yy  while (k[i] !=x) do i++;  while (k[i] !=x) do i++; 3. // Tì̀m thâ 3. // Ti m thấ́y hay không y hay không If (i==n+1) return 0 //không tì̀m thâ If (i==n+1) return 0 //không ti m thấ́yy else return i; else return i;   6
  7. 4.1.1 Tìm kiếm tuần tự (sequential  searching) ̉ ̣ ̉ ̣ ̣  Giai thuât 2 (giai thuât đê quy­ti ̀m trong  danh sách liên kết): Node *timdequy(struct node *first, element_type e) Node *timdequy(struct node *first, element_type e) {{   if (first == NULL)   if (first == NULL)     return NULL;     return NULL;   else   else     if (first­>element == e)  return first;     if (first­>element == e)  return first;     else      else    return timdequy(first­>next, e);   return timdequy(first­>next, e); }}   7
  8. 4.1.1 Tìm kiếm tuần tự (sequential  searching) ̉  Đánh giá giai thuât:̣ Trường hợp tốt nhất: Tmin = 1; Trường hợp xấu nhất: Tmax = O(n); Trung bình Ttb= O(n)   8
  9. ̣ 4.1.2. Tìm kiếm nhi phân (Binary  Serching)  Là phương pháp tìm kiếm thông dung. ̣  Ý tưởng:  – Dãy khóa đã được sắp xếp theo thứ tự (tăng  ̣ ̉ dần hoăc giam dâ ̀n). – ̉ ử dãy khóa đang xét là kl và kr thì khóa  Gia s ở giữa dãy sẽ là ki với i = (l+r)/2. – Tìm kiếm sẽ kết thúc nếu x=ki. Ngược lai,  ̣ nếu xki, phép tìm kiếm sẽ  được thực hiên tiê ̣ ́p với ki+1 với kr. – Quá trình tìm kiếm sẽ dừng khi tìm thấy  ̣ khóa hoăc da ̃y đang xét trở nên rỗng.   9
  10. ̣ 4.1.2. Tìm kiếm nhi phân (Binary  Serching) ̉ ̣  Giai thuât 1: BINARY­SEARCH(k,n,x) BINARY­SEARCH(k,n,x) b1.  l=1; r=n;//khởởi đâ b1.  l=1; r=n;//kh i đầ̀uu b2.  while (l
  11. ̣ 4.1.2. Tìm kiếm nhi phân (Binary  Serching) ̉ ̣ ̉ ̣ ̣  Giai thuât 2(giai thuât đê quy): RBINARY­SEARCH(l,r,k,x) RBINARY­SEARCH(l,r,k,x) b1.  if l
  12. ̣ 4.1.2. Tìm kiếm nhi phân (Binary  Serching) ̉ ̣  Đánh giá giai thuât: – Trường hợp tốt nhất Tmin =1, tìm được  ngay lần đầu tiên. – Trường hợp xấu nhất Tmax = k+w[n/2k) – Chứng minh được Ttb = O(log2n). ̉ ́c giai thuât ti Trong tất ca ca ̉ ̣ ̀m kiếm,  ̣ tìm kiếm nhi phân la ̀ nhanh nhất,  nhưng nó có nhược điêm la ̉ ̉ ̀ dãy phai  được sắp xếp.   12
  13. ̣ Bài tâp về nhà B1. Viết chương trình thực hiên ca ̣ ̣ ́c viêc  sau: ̣ a. Nhâp ca ̣ ́c giá tri nguyên d ương từ bàn  phím (tô ch ̉ ức theo kiêu danh sa ̉ ́ch liên  kết). b. In ra màn hình dãy số đã nhâp̣ ̣ c. Nhâp môt gia ̣ ̣ ừ bàn phím, kiêm tra  ́ tri X t ̉ X có trong danh sách hay không. Nếu có  ̉ ̀ vi tri thì tra vê ̣ ́ cua X, nê ̉ ́u không chèn X  vào vi trị ́ cuối cua danh sa ̉ ̉ ́ch.(Viết ca 2  ̉ giai thuât Tị ̀m kiếm tuâ  ̀n tự và tìm kiê13́m 
  14. ̣ 4.2. Cây nhi phân tìm kiếm ̣ ̉ ức tâp h  Viêc tô ch ̣ ợp khóa theo cấu  trúc danh sách thì phép tìm kiếm  nói chung là chi phí cao, nếu khóa  đã sắp xếp thì phép tìm kiếm nhi ̣ ̣ phân hiêu qua h̉ ơn nhưng bất tiên trong  ̣ ̣ viêc thêm, b ớt phần tử. ̣  Cấu trúc cây nhi phân ti ̀m kiếm được  xây dựng đê khă ̉ ̣ ́c phuc ca ́c nhược  ̉ điêm trên.   14
  15. ̣ 4.2.1 Đinh nghi ̃a ̣ Đinh nghi ̣ ̃a: Cây nhi phân ti ̀m kiếm là  ̣ cây nhi phân ma ̣ ̀ tai mô ̣ ̃i nút có môt gia ́  ̣ tri kho ̣ ̉ ữ liệu có thứ tự  ́a thuôc kiêu d nào đó, đồng thời thoa ma ̉ ̣ ̃n điều kiên  sau: – Moi kho ̣ ̣ ́a thuôc cây con tra ̉ ơn  ́i đều nho h khóa ở nút cha. – Moi kho ̣ ̣ ̉ ̀u lớn hơn  ́a thuôc cây con phai đê khóa ở nút cha. ̣ Theo đinh nghi ̉ ̃a, bất kỳ cây con nào cua  ̣ cây nhi phân ti ̀m kiếm đều là cây tìm  kiếm.   15
  16. ̣ 4.2.1 Đinh nghi ̃a Ví dụ: 34 17 66 25 50 71 68 75   16
  17. ̣ 4.2.1 Đinh nghi ̃a Bà i tâp tai l ̣ ̣ ớ p – Vẽ 4 cây nhi phân ti ̣ ̀m kiếm với các giá  ̣ tri sau: 3, 4, 6, 8, 9, 10, 14, 15, 17. – Vẽ cây nhi phân ti ̣ ̀m kiếm cân đối cho các  ̣ giá tri trên v ới số nút rỗng là ít nhất.   17
  18. 4.2.2 Các phép toán Phé p tì m kiế m Phé p chè n thêm môt nu ̣ ́t Phé p gỡ  loai bo môt nu ̣ ̉ ̣ ́ t    18
  19. 4.2.2.1  Phép tìm kiếm ̉ ́c bước: Mô ta ca Bắt đầu từ gốc cua cây, goi nu ̉ ̣ ́t đang xét là  V. Nếu V rỗng, kết thúc và tìm không thấy. Ngược lai, so sa ̣ ́nh x với khóa cua nu ̉ ̣ ́t hiên  ̣ tai V: – Nếu x khóa cua V, lăp lai b ̉ ̣ ̣ ước tìm kiếm với  ̉ cây con phai; – Nếu x = khóa cua V, kê ̉ ́t thúc và tìm thấy   19
  20. 4.2.2.1  Phép tìm kiếm Thủ tục đệ quy: int timdequy(int x,NODE *root) int timdequy(int x,NODE *root) {{ int timthay =0; int timthay =0; if ((root ==NULL) || (timthay)) return timthay; if ((root ==NULL) || (timthay)) return timthay; else else {{ if (x element) timdequy(x,root­>left); if (x element) timdequy(x,root­>left); else if (x>root­>element) timdequy (x,root­>right); else if (x>root­>element) timdequy (x,root­>right); else timthay =1; else timthay =1; }}   20
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

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