Bài giảng Cấu trúc dữ liệu - Chương 4: Tìm kiếm
lượt xem 4
download
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.
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Bài giảng Cấu trúc dữ liệu - Chương 4: Tìm kiếm
- CHƯƠNG 4 TÌM KIẾM 1
- 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
- 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.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
- 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
- 4.1.1 Tìm kiếm tuần tự (sequential searching) ̉ ̣ Giai thuât 1: SEQUENSEARCH(k,n,x) SEQUENSEARCH(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
- 4.1.1 Tìm kiếm tuần tự (sequential searching) ̉ ̣ ̉ ̣ ̣ Giai thuât 2 (giai thuât đê quyti ̀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
- 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
- ̣ 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
- ̣ 4.1.2. Tìm kiếm nhi phân (Binary Serching) ̉ ̣ Giai thuât 1: BINARYSEARCH(k,n,x) BINARYSEARCH(k,n,x) b1. l=1; r=n;//khởởi đâ b1. l=1; r=n;//kh i đầ̀uu b2. while (l
- ̣ 4.1.2. Tìm kiếm nhi phân (Binary Serching) ̉ ̣ ̉ ̣ ̣ Giai thuât 2(giai thuât đê quy): RBINARYSEARCH(l,r,k,x) RBINARYSEARCH(l,r,k,x) b1. if l
- ̣ 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
- ̣ 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
- ̣ 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
- ̣ 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
- ̣ 4.2.1 Đinh nghi ̃a Ví dụ: 34 17 66 25 50 71 68 75 16
- ̣ 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
- 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
- 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
- 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
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Bài giảng Cấu trúc dữ liệu - Bài 1:Tổng quan về cấu trúc dữ liệu và giải thuật
47 p | 174 | 17
-
Bài giảng Cấu trúc dữ liệu 1: Chương 1 - Lương Trần Hy Hiến
7 p | 162 | 9
-
Bài giảng Cấu trúc dữ liệu và giải thuật trong C++ - Bài 8: Cấu trúc dữ liệu ngăn xếp
28 p | 77 | 9
-
Bài giảng Cấu trúc dữ liệu giải thuật: Các kiểu dữ liệu trừu tượng cơ bản - Cấu trúc dữ liệu tuyến tính
92 p | 116 | 9
-
Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 17: Cấu trúc dữ liệu dạng cây
21 p | 77 | 8
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Các cấu trúc dữ liệu
193 p | 57 | 7
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 - Trần Minh Thái (Trường Đại học Hồng Bàng )
62 p | 157 | 6
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây AA - Bùi Tiến Lên
30 p | 35 | 6
-
Bài giảng Cấu trúc dữ liệu - Chương 3: Cấu trúc cây
65 p | 58 | 6
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 - Trần Minh Thái (2016)
62 p | 94 | 6
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu mảng với danh sách liên kết - Bùi Tiến Lên
36 p | 41 | 5
-
Bài giảng Cấu trúc dữ liệu: Chương 1 - ThS. Thiều Quang Trung (2018)
44 p | 43 | 4
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 – Trần Minh Thái (2017)
67 p | 105 | 4
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 7 - Châu Thị Bảo Hà
133 p | 113 | 4
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây AVL - Bùi Tiến Lên
38 p | 46 | 4
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 5 - Ngô Quang Thạch
24 p | 58 | 3
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 2 - Th.S Thiều Quang Trung
41 p | 68 | 3
-
Bài giảng Cấu trúc dữ liệu giải thuật: Cấu trúc dữ liệu
17 p | 50 | 2
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