TAILIEUCHUNG - Bài giảng Cấu trúc dữ liệu và giải thuật: Tìm kiếm (tt)

Bài giảng Cấu trúc dữ liệu và giải thuật trình bày một số kiến thức về tìm kiếm như: Bảng băm, một số phương pháp xây dựng hàm băm, đụng độ và khắc phục,.và một số bài tập. . | Chương 6 Tìm kiếm phần 2 Hiepnd@it-hut. edu. vn Băm Các phương pháp tìm kiếm Tìm kiếm tuần tự 0 n Tìm kiếm nhị phân O logn Phương pháp tổ chức dữ liệu để tìm kiếm nào tốt hơn Ọ Bảng băm 4 7 2011 Nội dung Bảng băm Một số phương pháp xây dựng hàm băm Đụng độ và khắc phục Bài tập Băm Ý tưởng bảng băm Dùng mảng lưu trữ các phần tử bảng Mỗi phần tử sẽ được lưu tại một ô duy nhất trong bảng căn cứ vào giá trị khóa của nó Khi tìm kiếm thì căn cứ vào khóa cần tìm ta tìm đến ô tương ứng Nếu ô đó có chứa phần tử thì tìm thấy ngược lại là không tìm thấy 1 Băm VD. Sinhvien 1222 Nguyễn văn A Hà Nội Sinhvien 1101 Trần văn C Thái Bình Sinhvien 0097 Nguyễn văn A Hà Nội Sinhvien 1331 Trần văn C Thái Bình Sinhvien 1345 Nguyễn văn A Hà Nội Sử dụng bảng kích thước 100 để lưu các phần tử 1 Chỉ 22 số mảng 31 V 35 97 Sinhvien 1101 Tràn văn C Thái Bình Sinhvien 1222 Nguyễn văn A Hà Nội Sinhvien 1331 Tràn văn C Thái Bình Sinhvien 1345 Nguyễn văn A Hà Nội Sinhvien 0097 Nguyễn văn A Hà Nội Băm Hàm băm Tính toán dễ và nhanh Phân phối đều các khóa Một số phương pháp thông dụng Cắt bỏ Truncation dùng một phần của khóa làm chỉ số VD khóa có 8 chữ số và bảng băm kích thước 1000 lấy chữ số thứ 4 7 và 8 làm chỉ số 21296876- 976 Nhanh nhưng phân bố khóa không đều 4 7 2011 Băm Tốt hơn tìm kiếm tuần tự khi mà dữ liệu được lưu trữ không có thứ tự. Không dựa trên so sánh giá trị các khóa của bản ghi mà dựa trên chính bản thân giá trị các khóa. Từ giá trị khóa ta tính ra một địa chỉ địa chỉ tương đối theo một quy tắc nào đó. Địa chỉ này sẽ dùng để lưu trữ bản ghi và cũng để tìm kiếm bản ghi đó. hash function- key an index v--Ỵ---J _ Địa chỉ lưu trữ Hàm băm hoàn hảo mỗi khóa ứng với một giá trị nguyên duy nhất Thời gian tìm kiếm 0 1 Băm Gấp folding chia khóa thành nhiều phần sau đó kết hợp các phần lại thường dùng cộng hoặc nhân VD. 21296876 chia thành 3 phần 212 968 và 76 kết hợp 212 968 76 1256 cắt bỏ được 256 Giá trị các thành phần trong khóa đều ảnh hường tới chỉ số. Cho phân phối tốt hơn phương pháp

• Cơ sở dữ liệu
• Cấu trúc dữ liệu
• Phương pháp xây dựng hàm băm
• Phương pháp đánh địa chỉ mở
• Tìm kiếm tuần tự
• Tìm kiếm nhị phân
• cấu trúc dữ liệu và giải thuât
• bài giảng cấu trúc dữ liệu và giải thuât
• tài liệu cấu trúc dữ liệu và giải thuât
• giáo trình cấu trúc dữ liệu và giải thuât
• bài tập cấu trúc dữ liệu và giải thuât
• Bài giảng Cấu trúc dữ liệu
• Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu cây AVL
• Cấu trúc dữ liệu cây
• Thuật toán DSW
• Cây nhị phân tìm kiếm
• Cấu trúc dữ liệu cây đỏ đen
• Cấu trúc dữ liệu cho nút cây đỏ đen
• Phép biến đổi cây đỏ đen cân bằng
• giáo trình cấu trúc dữ liệu
• bài tập cấu trúc dữ liệu
• đề cương cấu trúc dữ liệu
• lập trình dữ liệu
• Vị trí cấu trúc dữ liệu
• Áp dụng tin học
• Cơ sở dữ liệu
• Quan hệ giải thuật
• Cấu trúc dữ liệu cơ bản
• Đánh giá cấu trúc dữ liệu
• Định nghĩa kiểu dữ liệu
• Kiểu dữ liệu có cấu trúc
• Đánh giá thuật toán
• Thiết kế cấu trúc dữ liệu
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Kiểu dữ liệu trừu tượng
• Kiểu dữ liệu cây
• Phân loại cây
• Cấu trúc dữ liệu giải thuật
• Bài giảng Cấu trúc dữ liệu giải thuật
• Ngôn ngữ lập trình
• Cấu trúc chương trình
• Cấu trúc điều khiển
• Tài liệu Cấu trúc dữ liệu
• Cấu trúc dữ liệu căn bản
• Khái niệm cấu trúc dữ liệu
• Độ phức tạp thuật toán
• tiếp cận lập trình
• thuật toán
• thuật toán trong cấu trúc dữ liệu
• cấu trúc dữ liệu động
• kỹ thuật sắp xếp