Chương 4 Tìm kiếm

Chia sẻ: Lelong Bao | Ngày: | Loại File: PPT | Số trang:40

Thêm vào BST

Báo xấu

68
lượt xem 7
download

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

Mô hình chung của bài toán tìm kiếm: Có một tập n đối tượng. Mỗi đối tượng có nhiều thuộc tính, được thể hiện bằng một kiểu bản ghi gồm nhiều trường. Trong đó có 1 trường mà giá trị của nó đặc trưng cho đối tượng, cho phép xác định hoàn toàn đối tượng, thường gọi là khóa. Bài toán tìm kiếm: Có một tập các đối tượng và cho trước một đối tượng x. Cần tìm xem x có mặt trong tập hợp đã cho hay không?...

Chủ đề:

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

Lưu

Nội dung Text: Chương 4 Tìm kiếm

CHƯƠNG 4- TIM KIÊM ̀ ́ 1
CHƯƠNG 4. TIM KIÊM ̀ ́ 4.1 Cac phương phap tim kiêm trong danh sach ́ ́ ̀ ́ ́ ̀ ́ ́ ́ 4.1.1 Tim kiêm tuyên tinh 4.1.2 Tim kiêm nhị phân ̀ ́ ̀ ́ ̣ 4.1.1 Tim kiêm nôi suy 4.2 Cây nhị phân tim kiêm ̀ ́ ̣ ̃ 4.2.1 Đinh nghia ́ ́ ́ 4.2.2 Cac phep toan 2
4.1 Cac phương phap tim kiêm ́ ́ ̀ ́ ́ trong danh sach Mô hinh chung cua bai toan tim kiêm: Có môt ̀ ̉ ̀ ́ ̀ ́ ̣ tâp n đôi tượng. Môi đôi tượng có nhiêu thuôc ̣ ́ ̃ ́ ̀ ̣ tinh, được thể hiên băng môt kiêu ban ghi gôm ́ ̣ ̀ ̣ ̉ ̉ ̀ nhiêu trường. Trong đó có 1 trường mà giá trị cua ̀ ̉ nó đăc trưng cho đôi tượng, cho phep xac đinh ̣ ́ ́ ́ ̣ hoan toan đôi tượng, thường goi là khoa. ̀ ̀ ́ ̣ ́ Bai toan tim kiêm: Có môt tâp cac đôi tượng và ̀ ́ ̀ ́ ̣ ̣ ́ ́ cho trước môt đôi tượng x. Cân tim xem x có măt ̣ ́ ̀ ̀ ̣ trong tâp hợp đã cho hay không? ̣ 3
4.1 Cac phương phap tim kiêm ́ ́ ̀ ́ ́ trong danh sach ̀ ́ ̣ ̉ ̀ ́ ̀ Mô hinh toan hoc cua bai toan tim kiêm: ́ Có tâp hợp n giá trị khoa k1, k2, ..kn. Cho giá trị ̣ ́ khoa x. Tim xem x có tôn tai ki=x? ́ ̀ ̀ ̣ Công viêc tim kiêm sẽ hoan thanh khi: ̣ ̀ ́ ̀ ̀ – Tim được 1 ban ghi có giá trị khoa =x, luc đó phep ̀ ̉ ́ ́ ́ tim kiêm được thanh công successful. ̀ ́ ̀ – Không tim thây ban ghi nao có khoa băng x, goi là tim ̀ ́ ̉ ̀ ́ ̀ ̣ ̀ kiêm không thanh công unsuccessful. Luc nay có thể ́ ̀ ́ ̀ xuât hiên yêu câu bổ sung giá trị x vao tâp hợp, goi là ́ ̣ ̀ ̀ ̣ ̣ tim kiêm có bổ sung. ̀ ́ 4
4.1.1 Tim kiêm tuân tự (sequential ̀ ́ ̀ searching)  Là phương phap tim kiêm đơn gian và cổ ́ ̀ ́ ̉ ̉ điên. Ý tưởng: Băt đâu từ ban ghi thứ nhât, lân ́ ̀ ̉ ́ ̀ lượt so sanh khoa tim kiêm với khoa tương ́ ́ ̀ ́ ́ ứng cua ban ghi trong bang, cho tới khi tim ̉ ̉ ̉ ̀ được ban ghi mong muôn hoăc đã hêt bang ̉ ́ ̣ ́ ̉ mà chưa tim thây. ̀ ́ 5
4.1.1 Tim kiêm tuân tự (sequential ̀ ́ ̀ searching) ̉ ̣  Giai thuât 1: SEQUEN-SEARCH(k,n,x) SEQUEN-SEARCH(k,n,x) 1. //Khở đâù̀ 1. //Khởii đâu i=1; k[i+1]=x i=1; k[i+1]=x ̀̀ ́́ 2. // Tim khoa trong day 2. // Tim khoa trong day ̃̃ while (k[i] !=x) do i++; while (k[i] !=x) do i++; ̀̀ ́́ 3. // Tim thây hay không 3. // Tim thây hay không ̀̀ ́́ If (i==n+1) return 0 //không tim thây If (i==n+1) return 0 //không tim thây else return i; else return i; 6
4.1.1 Tim kiêm tuân tự (sequential ̀ ́ ̀ searching)  Giai thuât 2 (giai thuât đệ quy-tim trong ̉ ̣ ̉ ̣ ̀ ́ ́ danh sach 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 Tim kiêm tuân tự (sequential ̀ ́ ̀ searching)  Đanh giá 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 binh Ttb= O(n) 8
4.1.2. Tim kiêm nhị phân (Binary ̀ ́ Serching)  Là phương phap tim kiêm thông dung. ́ ̀ ́ ̣  Ý tưởng: – Day khoa đã được săp xêp theo thứ tự (tăng dân ̃ ́ ́ ́ ̀ ̣ hoăc giam dân). ̉ ̀ – Giả sử day khoa đang xet là kl và kr thì khoa ở giữa ̃ ́ ́ ́ day sẽ là ki với i = (l+r)/2. ̃ – Tim kiêm sẽ kêt thuc nêu x=ki. Ngược lai, nêu xki, phep tim kiêm sẽ được thực hiên tiêp với ́ ́ ̀ ́ ̣ ́ ki+1 với kr. – Quá trinh tim kiêm sẽ dừng khi tim thây khoa hoăc ̀ ̀ ́ ̀ ́ ́ ̣ day đang xet trở nên rông. ̃ ́ ̃ 9
4.1.2. Tim 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ở đâu b1. l=1; r=n;//khởiiđâù̀ b2. while (l
4.1.2. Tim 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
4.1.2. Tim kiêm nhị phân (Binary ̀ ́ Serching)  Đanh giá giai thuât: ́ ̉ ̣ – Trường hợp tôt nhât Tmin =1, tim đượ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). Trong tât cả cac giai thuât tim kiêm, tim ́ ́ ̉ ̣ ̀ ́ ̀ kiêm nhị phân là nhanh nhât, nhưng nó ́ ́ có nhược điêm là day phai được săp xêp. ̉ ̃ ̉ ́ ́ 12
Bai tâp về nhà ̀ ̣ B1. Viêt chương trinh thực hiên cac viêc ́ ̀ ̣ ́ ̣ sau: a. Nhâp cac giá trị nguyên dương từ ban phim ̣ ́ ̀ ́ (tổ chức theo kiêu danh sach liên kêt). ̉ ́ ́ b. In ra man hinh day số đã nhâp ̀ ̀ ̃ ̣ c. Nhâp môt giá trị X từ ban phim, kiêm tra X ̣ ̣ ̀ ́ ̉ có trong danh sach hay không. Nêu có thì trả ́ ́ về vị trí cua X, nêu không chen X vao vị trí ̉ ́ ̀ ̀ cuôi cua danh sach.(Viêt cả 2 giai thuât Tim ́ ̉ ́ ́ ̉ ̣ ̀ kiêm tuân tự và tim kiêm nhị phân). ́ ̀ ̀ ́ 13
4.2. Cây nhị phân tim kiêm ̀ ́  Viêc tổ chức tâp hợp khoa theo câu truc ̣ ̣ ́ ́ ́ danh sach thì phep tim kiêm noi chung là ́ ́ ̀ ́ ́ chi phí cao, nêu khoa đã săp xêp thì phep ́ ́ ́ ́ ́ tim 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 truc cây nhị phân tim kiêm được ́ ́ ̀ ́ xây dựng để khăc phuc cac nhược điêm ́ ̣ ́ ̉ trên. 14
̣ ̃ 4.2.1 Đinh nghia Đinh nghia: Cây nhị phân tim kiêm là cây ̣ ̃ ̀ ́ nhị phân mà tai môi nut có môt giá trị khoa ̣ ̃ ́ ̣ ́ thuôc kiêu dữ liệu có thứ tự nao đo, đông ̣ ̉ ̀ ́ ̀ thời thoa man điêu kiên sau: ̉ ̃ ̀ ̣ – Moi khoa thuôc cây con trai đêu nhỏ hơn khoa ̣ ́ ̣ ́ ̀ ́ ở nut cha. ́ – Moi khoa thuôc cây con phai đêu lớn hơn ̣ ́ ̣ ̉ ̀ khoa ở nut cha. ́ ́ Theo đinh nghia, bât kỳ cây con nao cua cây ̣ ̃ ́ ̀ ̉ nhị phân tim kiêm đêu là cây tim kiêm. ̀ ́ ̀ ̀ ́ 15
̣ ̃ 4.2.1 Đinh nghia Ví dụ: 34 17 66 25 50 71 68 75 16
̣ ̃ 4.2.1 Đinh nghia Bai tâp tai lớp ̀ ̣ ̣ – Vẽ 4 cây nhị phân tim kiêm với cac giá trị sau: ̀ ́ ́ 3, 4, 6, 8, 9, 10, 14, 15, 17. – Vẽ cây nhị phân tim kiêm cân đôi cho cac giá ̀ ́ ́ ́ trị trên với số nut rông là it nhât. ́ ̃ ́ ́ 17
́ ́ ́ 4.2.2 Cac phep toan ́ ̀ Phep tim kiêm ́ ́ ̀ Phep chen thêm môt nuṭ ́ Phep gỡ loai bỏ môt nut ́ ̣ ̣ ́ 18
́ ̀ ́ 4.2.2.1 Phep tim kiêm Mô tả cac bước: ́ Băt đâu từ gôc cua cây, goi nut đang xet là V. ́ ̀ ́ ̉ ̣ ́ ́ Nêu V rông, kêt thuc và tim không thây. ́ ̃ ́ ́ ̀ ́ Ngược lai, so sanh x với khoa cua nut hiên tai V: ̣ ́ ́ ̉ ́ ̣ ̣ – Nêu x< khoa cua V, lăp lai bước tim kiêm với cây con ́ ́ ̉ ̣ ̣ ̀ ́ ́ trai; – Nêu x> khoa cua V, lăp lai bước tim kiêm với cây con ́ ́ ̉ ̣ ̣ ̀ ́ phai; ̉ – Nêu x = khoa cua V, kêt thuc và tim thây ́ ́ ̉ ́ ́ ̀ ́ 19
́ ̀ ́ 4.2.2.1 Phep tim kiêm Thủ tuc đệ 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 < root->element) timdequy(x,root->left); if (x < root->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