1. Sắp xếp mảng cấu trúc
Khi làm việc với mảng cấu trúc bạn cần thành thạo thao tác sắp xếp, ví dụ bạn muốn sắp xếp sinh viên theo tên, theo gpa hay vừa sắp xếp theo gpa vừa sắp xếp theo tên.
Trong các ví dụ ở bài viết này mình sẽ sử dụng cấu trúc sinh viên để demo
struct SinhVien{ char hoten[50]; char lop[50]; double gpa; };
Muốn làm được các bài tập sắp xếp mảng cấu trúc bạn cần biết một vài thuật toán sắp xếp cơ bản hoặc nếu bạn được sử dụng hàm sắp xếp thì có thể sử dụng luôn qsort.
Trong các ví dụ này mình sẽ ko in ra các câu dẫn khi nhập thông tin nữa, các bạn có thể tham khảo input và output để chạy thử code
Sắp xếp mảng cấu trúc bằng hàm tự xây dựng
Thực ra thì sắp xếp dãy số hay sắp xếp mảng cấu trúc không có gì khác nhau về thuật toán, khi sắp xếp bạn cần lấy ra tiêu chí sắp xếp để so sánh giữa các phần tử trong mảng với nhau.
Ví dụ bạn muốn sắp xếp theo gpa thì khi so sánh 2 đối tượng trong mảng thì bạn lấy gpa ra để so sánh
Ví dụ 1 : Hàm sắp xếp sinh viên theo gpa giảm dần
//Selection sort : thuat toan sap xep chon void sapxep(SinhVien a[], int n){ for(int i = 0; i < n; i++){ int max_idx = i; for(int j = i + 1; j < n; j++){ //so sanh thuoc tinh gi ? if(a[j].gpa > a[max_idx].gpa){ max_idx = j; } } SinhVien tmp = a[i]; a[i] = a[max_idx]; a[max_idx] = tmp; } }
Ví dụ 2 : Sắp xếp danh sách sinh viên theo tên tăng dần về từ điển
Lưu ý : Ở đây khi sắp xếp mình sẽ lấy toàn bộ tên để so sánh, tức là sẽ xét họ, đệm rồi mới đến tên.
Trong trường hợp bạn muốn sắp xếp theo tên trước thì cần xử lý thêm
void sapxep(SinhVien a[], int n){ for(int i = 0; i < n; i++){ int min_idx = i; for(int j = i + 1; j < n; j++){ //so sanh thuoc tinh gi ? if(strcmp(a[j].hoten, a[min_idx].hoten) < 0){ min_idx = j; } } SinhVien tmp = a[i]; a[i] = a[min_idx]; a[min_idx] = tmp; } }
Sắp xếp mảng cấu trúc bằng hàm qsort()
Cách này sẽ tối ưu hơn so với cách bạn tự code, nếu bạn muốn tự code mà vẫn tối ưu như qsort() thì bạn phải sử dụng các thuật toán sắp xếp có độ phức tạp tốt như : Quicksort, merge sort, heapsort...
Nếu bạn sử dụng các thuật toán sắp xếp như chọn, chèn, đổi chỗ trực tiếp hay nổi bọt thì đều không tối ưu bằng cách dùng hàm này.
Nếu bạn chưa biết sử dụng hàm sắp xếp qsort() trong C thì có thể tham khảo tại đây
Ví dụ 1 : Hàm sắp xếp sinh viên theo gpa giảm dần
int cmp1(const void *a, const void *b){ SinhVien *x = (SinhVien*)a; SinhVien *y = (SinhVien*)b; if(x->gpa < y->gpa) return -1; else return 1; } void sapxep(SinhVien a[], int n){ qsort(a, n, sizeof(SinhVien), cmp1); }
Ví dụ 2 : Sắp xếp danh sách sinh viên theo tên tăng dần về từ điển
int cmp1(const void *a, const void *b){ SinhVien *x = (SinhVien*)a; SinhVien *y = (SinhVien*)b; return strcmp(x->hoten, y->hoten); } void sapxep(SinhVien a[], int n){ qsort(a, n, sizeof(SinhVien), cmp1); }
2. Ví dụ
Bài toán 1. Sắp xếp danh sách sinh viên theo gpa giảm dần
Thuật toán sắp xếp mình dùng cho bài này là sắp xếp chọn
Code :
#include "stdio.h" #include "string.h" struct SinhVien{ char hoten[50]; char lop[50]; double gpa; }; typedef struct SinhVien SinhVien; //Selection sort : thuat toan sap xep chon void sapxep(SinhVien a[], int n){ for(int i = 0; i < n; i++){ int max_idx = i; for(int j = i + 1; j < n; j++){ //so sanh thuoc tinh gi ? if(a[j].gpa > a[max_idx].gpa){ max_idx = j; } } SinhVien tmp = a[i]; a[i] = a[max_idx]; a[max_idx] = tmp; } } SinhVien nhap(SinhVien x){ gets(x.hoten); gets(x.lop); scanf("%lf", &x.gpa); getchar(); // xoa enter sau khi nhap scanf return x; } void nhapDS(SinhVien a[], int n){ for(int i = 0; i < n; i++){ a[i] = nhap(a[i]); //phai gan lai cho a[i] } } void xuat(SinhVien x){ printf("------------------------\n"); printf("Ho ten : %s\n", x.hoten); printf("Lop : %s\n", x.lop); printf("Gpa : %.2lf\n", x.gpa); printf("------------------------\n"); } void xuatDS(SinhVien a[], int n){ for(int i = 0; i < n; i++){ printf("Thong tin sinh vien thu %d :\n", i + 1); xuat(a[i]); } } int main(){ SinhVien a[5000]; int n; // so luong sinh vien scanf("%d", &n); getchar(); nhapDS(a, n); sapxep(a, n); xuatDS(a, n); return 0; }
Input :
5 Tran Van Nam CNTT1 2.6 Hoang Van 28Tech CNTT2 3.2 Vo Phuong Nam DTVT1 2.9 Vu Thanh Lam DTVT3 2.1 Nguyen Vu Phong CNTT2 3.7
Output :
Thong tin sinh vien thu 1 : ------------------------ Ho ten : Nguyen Vu Phong Lop : CNTT2 Gpa : 3.70 ------------------------ Thong tin sinh vien thu 2 : ------------------------ Ho ten : Hoang Van 28Tech Lop : CNTT2 Gpa : 3.20 ------------------------ Thong tin sinh vien thu 3 : ------------------------ Ho ten : Vo Phuong Nam Lop : DTVT1 Gpa : 2.90 ------------------------ Thong tin sinh vien thu 4 : ------------------------ Ho ten : Tran Van Nam Lop : CNTT1 Gpa : 2.60 ------------------------ Thong tin sinh vien thu 5 : ------------------------ Ho ten : Vu Thanh Lam Lop : DTVT3 Gpa : 2.10 ------------------------
Bài toán 2. Sắp xếp danh sách sinh viên theo gpa giảm dần, nếu 2 sinh viên có cùng gpa thì sắp xếp tên tăng dần theo thứ tự từ điển
Đối với kiểu bài sắp xếp dựa trên nhiều tiêu chí thì bạn cứ xét tiêu chí chính trước nếu tiêu chí chính bằng nhau thì mới xét tiêu chí phụ
Code :
#include "stdio.h" #include "string.h" struct SinhVien{ char hoten[50]; char lop[50]; double gpa; }; typedef struct SinhVien SinhVien; //Selection sort : thuat toan sap xep chon void sapxep(SinhVien a[], int n){ for(int i = 0; i < n; i++){ int max_idx = i; for(int j = i + 1; j < n; j++){ //so sanh thuoc tinh gi ? if(a[j].gpa > a[max_idx].gpa){ max_idx = j; } else if(a[j].gpa == a[max_idx].gpa){ if(strcmp(a[j].hoten, a[max_idx].hoten) < 0){ max_idx = j; } } } SinhVien tmp = a[i]; a[i] = a[max_idx]; a[max_idx] = tmp; } } SinhVien nhap(SinhVien x){ gets(x.hoten); gets(x.lop); scanf("%lf", &x.gpa); getchar(); // xoa enter sau khi nhap scanf return x; } void nhapDS(SinhVien a[], int n){ for(int i = 0; i < n; i++){ a[i] = nhap(a[i]); //phai gan lai cho a[i] } } void xuat(SinhVien x){ printf("------------------------\n"); printf("Ho ten : %s\n", x.hoten); printf("Lop : %s\n", x.lop); printf("Gpa : %.2lf\n", x.gpa); printf("------------------------\n"); } void xuatDS(SinhVien a[], int n){ for(int i = 0; i < n; i++){ printf("Thong tin sinh vien thu %d :\n", i + 1); xuat(a[i]); } } int main(){ SinhVien a[5000]; int n; // so luong sinh vien scanf("%d", &n); getchar(); nhapDS(a, n); sapxep(a, n); xuatDS(a, n); return 0; }
Input :
5 Tran Van Nam CNTT1 3.2 Hoang Van 28Tech CNTT2 2.6 An Van long CNTT3 3.2 Pham Thu Phuong CNTT1 2.6 Nguyen Van Hoang CNTT2 3.7
Output :
Thong tin sinh vien thu 1 : ------------------------ Ho ten : Nguyen Van Hoang Lop : CNTT2 Gpa : 3.70 ------------------------ Thong tin sinh vien thu 2 : ------------------------ Ho ten : An Van long Lop : CNTT3 Gpa : 3.20 ------------------------ Thong tin sinh vien thu 3 : ------------------------ Ho ten : Tran Van Nam Lop : CNTT1 Gpa : 3.20 ------------------------ Thong tin sinh vien thu 4 : ------------------------ Ho ten : Hoang Van 28Tech Lop : CNTT2 Gpa : 2.60 ------------------------ Thong tin sinh vien thu 5 : ------------------------ Ho ten : Pham Thu Phuong Lop : CNTT1 Gpa : 2.60 ------------------------
Video Struct :
