[Cấu trúc dữ liệu và giải thuật] – Áp dụng các thuật toán tìm kiếm và sắp xếp cơ bản vào mảng cấu trúc

Dưới đây là một vài ví dụ về việc áp dụng các thuật toán tìm kiếm và sắp xếp cơ bản vào mảng cấu trúc các bạn có thể tham khảo.

[CẤU TRÚC DỮ LIỆU & GIẢI THUẬT] – BÀI TẬP DANH SÁCH LIÊN KẾT: QUẢN LÝ SINH VIÊN

Đề bài: Xây dựng chương trình quản lý sinh viên bằng danh sách liên kết đơn, bao gồm các thông tin: Mã số sinh viên (MSSV), Họ và tên (HoTen), Điểm trung bình (DTB).

[Cấu trúc dữ liệu và giải thuật] – Bài tập sắp xếp: Quản lý thực đơn

Yêu cầu: Viết các hàm sắp xếp danh sách các món ăn trên mảng cấu trúc.

[Cấu trúc dữ liệu & giải thuật] – Bài tập tìm kiếm trong mảng cấu trúc

Đề bài: Tìm thông tin điện thoại dùng Linear Search và Binary Search

1. Tìm thông tin điện thoại dùng Linear Search

Để tìm thông tin điện thoại theo mã sản phẩm x dùng Linear Search, cần xây dựng chương trình con gồm:

void LinearSearch_MaSP(dien_thoai a[], int n, char x[]):  hỗ trợ tìm kiếm và xuất ra thông tin điện thoại có MaSP cần tìm (nếu có)

• Chương trình con:

int LinearSearch_MaSP(dien_thoai a[], int n, char x[])

{

[Cấu trúc dữ liệu và giải thuật] – Thuật toán sắp xếp ShakerSort

++ ShakerSort hay còn được gọi là thuật toán sắp xếp lắc, đây là một thuật toán cải tiến của thuật toán BubbleSort.
ShakerSort sau khi đưa phần tử nhỏ/lớn nhất lên đầu dãy, sau đó lại đưa phần tử lớn/nhỏ nhất về cuối dãy. Như vậy, trong một lần duyệt, ShakerSort sẽ đưa ít nhất hai số  về đúng với vị trí của nó. Giả sử ta xét mảng gồm các phần tử {6; 7; 8; 9 ;0}
Với ShakerSort trong một lần duyệt, các phần tử đã trở về đúng vị trí của nó: {0;6;7;8;9}. Khác với BubbleSort ta cần tới 4 lần duyệt để đưa các phần tử về đúng vị trí. Vậy đối với một số mảng đã gần như có thứ tự, ShakerSort sẽ chạy nhanh hơn so với BubbleSort. Nếu như ta xét các mảng sinh các số ngẫu nhiên thì thời gian chạy của hai thuật toán này là tương đương nhau.

 THIẾT KẾ THUẬT TOÁN 

• 

  Code chương trình con Shakersort

[Cấu trúc dữ liệu và giải thuật] – Nội dung ôn tập cuối kì

• Cấu trúc của một bài thi sẽ xoay quanh các vấn đề sau nên các bạn phải cực kì lưu ý:
  
• Nhắc lại kiến thức ( Các phương pháp có thể hay gây nhầm lẫn nên các bạn cần nắm chắc):

[Cấu trúc dữ liệu và giải thuật] – Thuật toán tìm kiếm

1. Thuật toán tìm kiếm tuyến tính:

Thật ra trước giờ chúng ta vẫn thường hay sử dụng thuật toán tìm kiếm tuyến tính, chỉ là do chúng ta không biết tên gọi của nó mà thôi.

Ví dụ như, cho một giá trị x bất kì và một dãy số ngẫu nhiên. Tìm trong dãy số đó phần tử có giá trị bằng với x và chỉ ra vị trí của phần tử đó trong dãy. Đến đây, chắc nhiều bạn đã hình dung ra được cách code rồi đúng không? Ta sẽ đi so sánh lần lượt từng phần tử trong dãy với x theo hướng từ trái sang phải, không bỏ sót phần tử nào cả (Dùng vòng lặp for để thực hiện). Cách làm này chính là thuật toán tìm kiếm tuyến tính.

[Cấu Trúc Dữ Liệu & Giải Thuật] – Sắp xếp Nhanh-QuickSort

Ý tưởng:

• Chọn một phần tử trong dãy làm khóa
• Đưa các phần tử nhỏ hơn về bên trái của khóa, các phần tử lớn hơn đưa về bên phải khóa.
• Tiếp tục phân hạch với các dãy con cho đến khi dãy được sắp xếp.

Gỉa sử ta có dãy, hãy sắp xếp tăng dần.

Dãy từ i=0 đến i=7, lấy trung bình chọn phần tử giữa làm khóa là i₃=5 làm phần tử khóa.

Bây giờ ta sẽ xét 2 phần tử là 12 và 15:

Ta thấy 12 và 15 không thỏa điều kiện, nên đẩy tiến tới xét cặp 12 và 4:

Ta thấy 4<12 thỏa điều kiện tăng dần nên ta hoán đổi 2 vị trí.

[Cấu Trúc Dữ Liệu & Giải Thuật] – Bài tập trọng tâm_Part 2

Bài tập trọng tâm_Part 2

[Cấu Trúc Dữ Liệu & Giải Thuật] – Bài tập trọng tâm_Part 1

Bài tập trọng tâm_Part 1