Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 2 - ThS. Nguyễn Hà Giang

Số trang: 63 Loại file: pdf Dung lượng: 2.03 MB Lượt xem: 8 Lượt tải: 0

10.10.2023

Phí tải xuống: 36,000 VND

Xem trước 7 trang đầu tiên của tài liệu này:

Thông tin tài liệu:

Chương 2 cung cấp kiến thức về tìm kiếm và sắp sếp trong tin học. Những nội dung chính được trình bày trong chương này gồm có: Tìm kiếm tuyến tính, tìm kiếm nhị phân, selection sort, bubble sort, insertion sort, interchange sort, PP shellsort, PP quicksort, PP radixsort. Mời các bạ cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 2 - ThS. Nguyễn Hà GiangHUTECHTRƯỜNG ĐẠI HỌC DÂN LẬP KỸ THUẬT CÔNG NGHỆ------------CẤU TRÚC DỮ LIỆUCHƯƠNG 2CTDL & GTGV: ThS. NGUYỄN HÀ GIANGTP. HCM – 1/20081HUTECHNội dung trình bàyCTDL & GT• Tìm kiếm• Sắp xếp2HUTECH2.1 Tìm kiếm• Tìm kiếm là thao tác quan trọng & thường xuyêntrong tin học.CTDL & GT– Tìm kiếm một nhân viên trong danh sách nhân viên.– Tìm một sinh viên trong danh sách sinh viên của mộtlớp…– Tìm kiếm một tên sách trong thư viện.3CTDL & GTHUTECH2.1 Tìm kiếm (2)• Tìm kiếm là quá trình xác định một đối tượngnào đó trong một tập các đối tượng. Kết quả trảvề là đối tượng tìm được (nếu có) hoặc một chỉsố (nếu có) xác định vị trí của đối tượng trongtập đó.• Việc tìm kiếm dựa theo một trường nào đó củađối tượng, trường này là khóa (key) của việctìm kiếm.• VD: đối tượng sinh viên có các dữ liệu{MaSV, HoTen, DiaChi,…}. Khi đó tìm kiếmtrên danh sách sinh viên thì khóa thường chọnlà MaSV hoặc HoTen.4HUTECH2.1 Tìm kiếm (3)Tìm kiếmTìm kiếm tuyến tínhTập dữ liệubất kỳTìm kiếm nhị phânTập dữ liệu đãđược sắp xếpCTDL & GT• Bài toán được mô tả như sau:– Tập dữ liệu được lưu trữ là dãy a1, a2,..,an. Giả sử chọn cấutrúc dữ liệu mảng để lưu trữ dãy số này trong bộ nhớ chính,có khai báo: int a[n];– Khóa cần tìm là x, có kiểu nguyên: int x;5