tailieunhanh - Giáo trình phân tích tổng quan về cấu trúc dữ liệu và giải thuật trong quá trình thiết kế phần mềm p2

Trong thực tế, khi thao tác, khai thác dữ liệu chúng ta hầu như lúc nào cũng phải thực hiện thao tác tìm kiếm. Việc tìm kiếm nhanh hay chậm tùy thuộc vào trạng thái và trật tự của dữ liệu trên đó. Kết quả của việc tìm kiếm có thể là không có (không tìm thấy) hoặc có (tìm thấy). Nếu kết quả tìm kiếm là có tìm thấy thì nhiều khi chúng ta còn phải xác định xem vị trí của phần tử dữ liệu tìm thấy là ở đâu. | ỹiá ÙU Cấu Ttú Dũ Liệu vù ỹiùi 7huật Chương 2 KỸ THUẬT TÌM KIEM SEARCHING . Khái quát về tìm kiếm Trong thực tế khi thao tác khai thác dữ liệu chúng ta hầu như lúc nào cũng phải thực hiện thao tác tìm kiếm. Việc tìm kiếm nhanh hay chàm tùy thuOc vào trạng thái và trát tư cùa dữ liệu trến đó. Kết quá cùa việc tìm kiếm co thế lá không co không tìm thấy hoác co tìm thay . Nếu kết quá tìm kiếm lá co tìm tháy thì nhiệu khi chung ta con phái xác định xếm vị trí của phán tử dữ liệu tìm thay lá ở đáu Trong phạm vi cua chương náy chung ta tìm cách giải quyết các cáu hoi náy. Trữởc khi đi váo nghiến cứu chi tiết chung ta giá sử ráng moi phán tử dữ liệu đữởc Xếm xệt co một thánh phán khoa Kệy đệ nhận diện co kiếu dữ liệu lá T náo đo các thánh phán con lai lá thong tin Info liến quan đến phán tử dữ liệu đo. Nhữ váy moi phán tữ dữ liệu co cau truc dữ liệu nhữ sau typếdếf struct DátáElệmệnt T Kệy InfoTypệ Info DataType Trong tái liệu náy khi noi tơi giá trị cua mọt phán tử dữ liệu chung tá muon noi tơi giá trị khoa Kệy cua phán tữ dữ liệu đo. Đệ đơn gián chung tá giá sử ráng moi phán tử dữ liệu chỉ lá thánh phán khoa nhán diện. Việc tìm kiếm mot phán tử co thế diện ra trện mot dãy máng tìm kiếm nOi hoác diện ra trện mOt táp tin file tìm kiếm ngoai . Phán tử cán tìm lá phán tử cán thoa mán điệu kiện tìm kiếm thữơng co giá trị báng giá trị tìm kiếm . Tuy thuOc váo tững bái toán cu thệ má điệu kiện tìm kiếm co thế khác nhau song chung quy việc tìm kiếm dữ liệu thữơng đữơc ván dụng thệo các thuát toán trình bay sau đáy. . Các giải thuát tìm kiếm nội Tìm kiếm trền dáy máng . Đặ t van đề Giá sử chung tá co mOt manj M gồm N phán tủ . Van đệ đát ra lá co hay khong phán tử co giá trị báng X trong manj M Nếu co thì phán tữ co giá trị báng X lá phán tử thứ may trong manj M . Tìm tuyền tính Linear Search Thuát toán tìm tuyến tính con đữơc goi lá Thuát toán tìm kiếm tuán tự Sệquệntiál Sệarch . a. Tư tưởng Lán lữơt so sánh các phán tử cua manj M vơi giá trị X bát đáu tữ phán