TRẮC NGHIỆM (3đ)
(Đánh giá giải thuật, sắp xếp hiệu quả cao, stack – queue)
Đánh giá giải thuật
Tính thời gian chạy của chương trình T(n)
Lệnh cơ bản: T(n) = 1. Bao gồm: câu lệnh gán, return,cout, cin và các phép toán cộng, trừ, nhân, chia,…
Cấu trúc lựa chọn: T(n) = số điều kiện + max (khối lệnh sau if, khối lệnh sau else). Bao gồm: câu lệnh if-else, switch- case.
Cấu trúc lặp: T(n) = số lần lặp * (khối lệnh lặp + 1 + số điều kiện). Bao gồm: câu lệnh for, while, do-while).
Lưu ý: câu lệnh khai báo biến không tốn thời gian.
Ví dụ:
Tính thời gian thực hiện hàm hoán vị
void hoan_vi(int &a,int &b)
{
int t = a;
a=b;
b=t;
}
Giải:
Câu lệnh “int t=a;” : lệnh gồm khai báo biến t và gán giá trị “a” cho “t” => lệnh cơ bản => T(n) = 1.
Câu lệnh “a=b;” => lệnh cơ bản => T(n) = 1.
Câu lệnh “b=t;” => lệnh cơ bản => T(n) = 1.
Vậy thời gian thực hiện hàm hoán vị T(n) = 1+1+1=3.
Tính thời gian thực hiện hàm so sánh:
void so_sanh(int a, int b)
{
if (a>b)
{
cout<< “a lon hon b”;
cout<<”\n”;
}
else
cout<< “a nho hon b”;
}
Giải:
Cấu trúc lựa chọn
Điều kiện : có một điều kiện duy nhất là “a>b” => số điều kiện = 1.
Khối lệnh sau if gồm hai câu lệnh cơ bản => T(n)=1+1=2.
Khối lệnh sau else gồm 1 câu lệnh cơ bản => T(n)=1.
Vậy thời gian thực hiện của chương trình là T(n)=1+max(2,1)=1+2=3.
Tính thời gian thực hiện của hàm tính giai thừa
int Giai_thua(int n)
{
int kq=1;
for (int i=1; i <= n; i++)
kq=kq*i;
return kq;
}
Giải:
Câu lệnh “int kq = 1;” là câu lệnh cơ bản => T(n) = 1;
Cấu trúc lặp
i chạy từ 1 tới n => số lần lặp = n.
Khối lệnh trong for gồm 1 câu lệnh cơ bản “kq=kq*i” => T(n) = 1.
Điện trong for là “i <= n” => số điều kiện =1.
Câu lệnh “return kq;” là câu lệnh cơ bản => T(n) = 1;
Vậy thời gian thực hiện chương trình T(n) = 1 + n*(1+1+1) + 1 = 3n + 2.
Bài tập: Tính thời gian chạy của đoạn chương trình sau :
int Linear( int a[], int n, int x)
{
int i=0;
while (a[i] != x && i<n)
i++;
if (i<n)
return i;
return (-1);
}
Đáp án : 4n+4
Độ phức tạp của giải thuật
Tỷ suất tăng f(n) = ni
T(n) = c => f(n) = 1
T(n) = c.n => f(n) = n
T(n) = a.n2 + b.n + c => f(n) = n2
T(n) = a.n3 + b.n2 + c.n + d => f(n) = n3
( với a, b, c, d là hằng số)
Độ phức tạp : O(f(n))
Quy tắc cộng : P = P1 + P2
P1 có tỷ suất tăng f(n)
P2 có tỷ suất tăng g(n)
=> Độ phức tạp: O(max{ f(n), g(n) })
Quy tắc cộng : P = P1 * P2
P1 có tỷ suất tăng f(n)
P2 có tỷ suất tăng g(n)
=> Độ phức tạp: O(f(n) * g(n))
Ví dụ: Tính độ phức tạp của đoạn chương trình sau :
int Lon_Nhat(int a[], int n)
{
int max = a[0]; // T(1)
for (int i = 0; i<n ; i++)
if (a[i] > max) max = a[i]; // T(2)
return max;//T(3)
}
Giải :
T(1) = 1 => f(1) = 1;
T(2) = 4n => f(2) = n;
T(3) = 1 => f(3) = 1;
Độ phức tạp O(max{f(1), f(2), f(3)} = O(n)
Sắp xếp hiệu quả cao
Quick Soft
Ý tưởng :
Phân chia mảng ban đầu thành 3 mảng con :
Mảng con 1 : gồm các phần tử nhỏ hơn X
Mảng con 2 : gồm một phần tử X
Mảng con 3 : gồm các phần tử lớn hơn X
Tiếp túc áp dụng Quick Soft cho mảng con 1 và mảng con 3
Độ phức tạp thuật toán của Quick sort :
Trường hợp tốt: O(nlog(n))
Trung bình: O(nlog(n))
Trường hợp xấu: O(n^2)
Merge Soft
Mảng gồm một phần tử là mảng đã sã sắp xếp. Mảng gồm n phần tử là một tập hợp n mảng con đã sắp xếp.
Ý tưởng :
Phân hoạch mảng ban đầu thành các mảng con rồi chia thành hai mảng phụ theo nguyên tắc phân phối luân phiên
Tộn từng cặp mảng con của 2 mảng phụ thành một mản con của dãy ban đầu
Lặp lại cho đến khi xong
Độ phức tạp thuật toán của Quick sort :
Trường hợp tốt: O(nlog(n))
Trung bình: O(nlog(n))
Trường hợp xấu: O(nlog(n))
Stack – Queue
Stack – Ngăn xếp
Stack là vật chứa dữ liệu
Cô chế LIFO (Last In First Out)
Tháo tác trên Stack :
Push: Thêm một phần tử vào đỉnh của ngăn xếp, số phần tử của ngăn xếp tăng lên 1.
Pop: Xóa bỏ phần tử đầu tiên ở đỉnh của ngăn xếp, số phần tử của ngăn xếp giảm đi 1.
Top: Lấy giá trị của phần tử đầu tiên ở đỉnh của ngăn xếp, số phần tử của ngăn xếp không thay đổi.
IsEmpty: Kiểm tra ngăn xếp trống hay không. Ngăn xếp trống là ngăn xếp không có phần tử nào.
Size: Lấy số lượng phần tử stack đang có.
Queue – Hàng đợi
Queue là vật chứa dữ liệu
Cơ chế LIFO (Last In First Out)
Các thao tác trên Queue
Enqueue: thêm 1 phần tử vào hàng đợi.
Dequeue: xóa 1 phần tử khỏi hàng đợi.
Peek: lấy 1 phần tử đầu của hàng đợi mà không xóa nó.
IsEmpty: kiểm tra hàng đợi có rỗng không
Thời gian thực hiện: 75 phút
CODE (7đ)
Giới thiệu
HSNV(MSNV, Ho, Ten, NgaySinh, ThamNien, HeSo) Cấu trúc hỗ trợ quản lý hồ sơ nhân viên gồm các thông tin: Mã số nhân viên; Họ, Tên nhân viên; Ngày sinh được thể hiện dạng ddmmyy, ví dụ 230600 nghĩa là sinh ngày 23/06/2000; Thâm niên (ThamNien) công tác và Hệ số (HeSo) thâm niên.
Mô tả cấu trúc được yêu cầu, chọn cơ sở dữ liệu để thể hiện, khai báo/định nghĩa cấu trúc.
Thông tin nhân viên cần quản lý gồm:
– MSNV: mã số nhân viên, là một chuỗi có độ dài 6 kí tự.
– HO: Họ và tên lót, là chuỗi có độ dài 20 kí tự.
-TEN: Tên nhân viên, là chuỗi có độ dài 20 kí tự.
-NTNSINH: ngày tháng năm sinh của nhân viên theo dạng ddmmyy (tức 120401 là 12/04/2001), có kiểu dữ liệu là số nguyên.
– THAMNIEN: Số năm công tác của nhân viên, có kiểu dữ liệu là số thực (double).
– HESO: Là hệ số lương nhân viên, có kiểu dữ liệu là số thực (double).
Cấu trúc dữ liệu hỗ trợ quản lý thông tin sinh viên:
– MSNN: Chuỗi có độ dài 6 kí tự.
– HO: Chuỗi có độ dài 20 kí tự.
– TEN: Chuỗi có độ dài 20 kí tự.
– NTNSINH: Số nguyên, ngày tháng năm lớn hơn 1. Các tháng 1,3,5,7,8,10,12 có 31 ngày, các tháng 4,6,9,11 có 30 ngày. Riêng tháng 2 có 28 hoặc 29 (năm nhuận) ngày.
– THAMNIEN: Kiểu dữ liệu là số thực (double), không âm.
– HESO: Kiểu dữ liệu là số thực (double), không âm.
Định nghĩa cấu trúc sinh viên:
typedef struct
{
string msnv;
string ho;
string ten;
string ngaysinh;
double thamnien;
double heso;
}nvType;
Ta tạo ra một mảng cấu trúc có các kiểu dữ liệu như trên:
Mã số nhân viên: kiểu số nguyên.
Họ, tên, ngày tháng năm sinh: kiểu chuỗi string.
Thâm niên và hệ số kiểu số thực.
Các chức năng trên mảng cấu trúc ( 3.5đ )
Nhập danh sách nhân viên.
Xuất danh sách nhân viên.
Tìm thông tin nhân viên theo mã số nhân viên (dùng Linear Search và Binary Search).
Tìm thông tin nhân viên theo tên (dùng Linear Search và Binary Search).
Sắp xếp danh sách theo MSNV ( dùng Shaker Sort).
Sắp xếp danh sách theo MSNV ( dùng Selection Sort).
Sắp xếp danh sách theo tên ((dùng Interchange Sort).
Sắp xếp danh sách theo THÂM NIÊN (dùng Bubble Sort).
Sắp xếp danh sách theo HỆ SỐ (dùng Insertion Sort).
Trình chọnđơn (Menu)
Các chức năng trên danh sách liên kết ( 3.5đ )
Nhập danh sách nhân viên.
Xuất danh sách nhân viên.
Tìm thông tin nhân viên theo mã số (dùng Linear Search ).
Tìm thông tin nhân viên theo tên (dùng Linear Search ).
Sắp xếp danh sách theo MSNV ( dùng Shaker Sort).
Sắp xếp danh sách theo MSNV ( dùng Selection Sort).
Sắp xếp danh sách theo tên ((dùng Interchange Sort).
Sắp xếp danh sách theo THÂM NIÊN (dùng Bubble Sort).
Sắp xếp danh sách theo HỆ SỐ (dùng Insertion Sort).
Trình đơn (Menu)
TÌM KIẾM VÀ SẮP XẾP TRÊN MẢNG CẤU TRÚC
Xây dựng một mảng cấu trúc quản lý thông tin nhân viên.
Chương trình con: Để nhập danh sách sinh viên cần nhập hai chương trình con gồm:
Void nhap_o(nhanvien &a): Hỗ trợ nhập thông tin một nhân viên gồm: mã số nhân viên, họ, tên, ngày tháng năm sinh, thâm hiên, hệ số.
void Nhap_NV(nvType& nv)
{
cout << “MSNV: “; getline(cin, nv.msnv);
cout << “Ho: “; getline(cin, nv.ho);
cout << “Ten: “; getline(cin, nv.ten);
cout << “Ngaysinh: “; getline(cin, nv.ngaysinh);
cout << “Tham nien: “; cin >> (nv.thamnien);
cout << “he so: “; cin >> (nv.heso);
}
void nhapmang(sinh_vien a[], int n): Hỗ trợ nhập danh sách sinh viên.
void nhapmang(nhanvien a[], int n)
{
for (int i = 0; i < n; i++)
{
cout << “Nhan vien ” << i + 1 << “: \n”;
nhap_o(a[i]);
cout << endl;
}
}
void xuat_o(nhanvien a)
{
cout << “\t” << a.msnv;
cout << “\t\t” << a.ho << “\t” << a.ten << “\t\t”;
cout << a.ntnsinh << “\t”;
cout << “\t” << a.thamnien;
cout << “\t” << a.heso << endl;
}
void xuat_nhan_vien(nhanvien a[], int i)
{
cout << “\n\t” << a[i].msnv;
cout << “\t” << a[i].ho << ” ” << a[i].ten;
cout << “\t” << a[i].ntnsinh;
cout << “\t” << a[i].thamnien;
cout << “\t” << a[i].heso << “\n\n\n”;
}
Xuất mảng: hỗ trợ xuất thông tin của mảng sinh viên
void xuatmang(nhanvien a[], int n)
{
cout << “\nThong tin nhan vien la: \n”;
for (int i = 0; i < n; i++)
{
xuat_o(a[i]);
}
}
Tìm thông tin nhân viên theo mã số nhân viên (dùng Linear Search)
int LinearSearch_F(nhanvien a[], int n, int x)
{
for (int i = 0; i < n; i++)
{
if (a[i].msnv == x)
return i;
}
return (-1);
}
Tìm thông tin nhân viên theo mã số nhân viên (dùng Binary Search)
Lưu ý: Nếu tìm kiếm bằng hàm Binary Search thì mã số nhân viên phải được sắp xếp tăng dần ngay từ đầu.
int BinarySearch(nhanvien a[], int n, int x)
{
int left = 0;
int right = n – 1;
int mid = (left + right) / 2;
while (left <= right && a[mid].msnv != x)
{
if (x < a[mid].msnv)
right = mid – 1;
else
left = mid + 1;
mid = (left + right) / 2;
}
if (left > right)
return (-1);
return mid;
}
Sắp xếp danh sách theo MSNV (dùng Shaker Sort)
Hàm Shaker Sort sẽ sắp xếp danh sách nhân nhiên theo chiều tăng dần mã số nhân viên.
void Sapxep_MSNV_Shaker_sort(nhanvien a[], int n)
{
int left = 0; int right = n – 1; int k = n – 1;
while (left < right)
{
//luot di: day phan tu nho nhat ve dau mang
for (int i = right; i > left; i–)
if (a[i – 1].msnv > a[i].msnv)
{
swap(a[i – 1], a[i]);
k = i;
}
left = k;
//luot ve: day phan tu lon nhat ve cuoi mang
for (int j = left; j < right; j++)
if (a[j].msnv > a[j + 1].msnv)
{
swap(a[j], a[j + 1]);
k = j;
}
right = k;
}
}
Sắp xếp danh sách theo mã số nhân viên (dùng Selection Sort)
Hàm Selection Sort sẽ sắp xếp danh sách nhân nhiên theo chiều tăng dần mã số nhân viên.
void Sapxep_MSNV_Selection_sort(nhanvien a[], int n)
{
for (int i = 0; i < n – 1; i++)
{
int min_index = i;
for (int j = i + 1; j < n; j++)
if (a[j].msnv < a[min_index].msnv) min_index = j;
swap(a[i], a[min_index]);
}
}
Sắp xếp danh sách theo tên ((dùng Interchange Sort).
Dùng để sắp xếp danh sách theo tên dựa vào độ tăng dần của tên theo thứ tự bảng chữ cái.
void Sapxep_Ten_Interchange_sort(nhanvien a[], int n)
{
for (int i = 0; i < n – 1; i++)
for (int j = i + 1; j < n; j++)
if (a[i].ten > a[j].ten)
swap(a[i], a[j]);
}
Sắp xếp danh sách theo THÂM NIÊN (dùng Bubble Sort).
Hàm Bubble Sort sắp xếp theo thâm niên từ nhỏ đến lớn.
void Sapxep_Thamnien_Bubble_sort(nhanvien a[], int n)
{
for (int i = 0; i < n – 1; i++)
for (int j = n – 1; j > i; j–)
if (a[j].thamnien < a[j – 1].thamnien)
swap(a[j – 1], a[j]);
}
Sắp xếp danh sách theo HỆ SỐ (dùng Insertion Sort).
Hàm Insertion Sort sắp xếp danh sách nhân viên theo chiều tăng dần của hệ số.
void Sapxep_Heso_Insertion_sort(nhanvien a[], int n)
{
for (int i = 1; i < n; i++)
{
nhanvien t = a[i];
int temp = a[i].heso;
int j = i – 1;
while ((temp < a[j].heso) && (j >= 0))
{
a[j + 1] = a[j];
j = j – 1;
}
a[j + 1] = t;
}
}
Gồm hai chương trình con nhỏ kết hợp với nhau.
void trinhDon()
{
system(“cls”);
cout << “\nTHAO TAC MANG CO BAN”;
cout << “\n1 Nhap mang”;
cout << “\n2 Xuat mang”;
cout << “\n3 Tim kiem voi LinearSearch”;
cout << “\n4 Tim kiem voi BinarySearch”;
cout << “\n5 Sap xep voi Selection Sort”;
cout << “\n6 Sap xep voi Saker Sort”;
cout << “\n7 Sap xep voi Interchange Sort”;
cout << “\n8 Sap xep voi Bubble Sort”;
cout << “\n9 Sap xep voi Insection Sort”;
cout << “\n10 thoat”;
}
void chonTrinhDon(nhanvien a[], int& n, int c)
{
int x; int kq;
switch (c)
{
case 1:
nhap_sopt(n, 3, MAX);
nhapmang(a, n);
break;
case 2:
cout << “\nthong tin mang\n”;
xuatmang(a, n);
system(“pause”);
break;
case 3:
cout << “\nnhap gia tri can tim: “;
cin >> x;
kq = LinearSearch_F(a, n, x);
if (kq == -1)
cout << “\nkhong tim thay\n”;
else
cout << “\ntim thay ” << x << “\ttai vi tri” << kq << endl;
system(“pause”);
break;
case 4:
cout << “\nnhap gia tri can tim: “;
cin >> x;
kq = BinarySearch(a, n, x);
if (kq == -1)
cout << “\nkhong tim thay\n”;
else
cout << “\ntim thay ” << x << “\ttai vi tri” << kq << endl;
system(“pause”);
break;
case 5:
cout << “\nmang truoc khi sap xep: “;
xuatmang(a, n);
Sapxep_MSNV_Selection_sort(a, n);
cout << “\nmang sau khi sap xep: “;
xuatmang(a, n);
system(“pause”);
break;
case 6:
cout << “\nmang truoc khi sap xep: “;
xuatmang(a, n);
Sapxep_MSNV_Shaker_sort(a, n);
cout << “\nmang sau khi sap xep: “;
xuatmang(a, n);
system(“pause”);
break;
case 7:
cout << “\nmang truoc khi sap xep: “;
xuatmang(a, n);
Sapxep_Ten_Interchange_sort(a, n);
cout << “\nmang sau khi sap xep: “;
xuatmang(a, n);
system(“pause”);
break;
case 8:
cout << “\nmang truoc khi sap xep: “;
xuatmang(a, n);
Sapxep_Thamnien_Bubble_sort(a, n);
cout << “\nmang sau khi sap xep: “;
xuatmang(a, n);
system(“pause”);
break;
case 9:
cout << “\nmang truoc khi sap xep: “;
xuatmang(a, n);
Sapxep_Heso_Insertion_sort(a, n);
cout << “\nmang sau khi sap xep: “;
xuatmang(a, n);
system(“pause”);
break;
}
}
int main()
{
nhanvien a[MAX];
int sopt = 0;
int chon;
do
{
trinhDon();
cout << “\nchon thao tac can thuc hien (1-10): \n”;
cin >> chon;
chonTrinhDon(a, sopt, chon);
} while (chon != 10);
cout << “\nchao tam biet\n”;
system(“pause”);
}
TÌM KIẾM VÀ SẮP XẾP TRÊN DANH SÁCH LIÊN KẾT
Định nghĩa danh sách liên kết: Một Danh sách liên kết (Linked List) là một dãy các cấu trúc dữ liệu được kết nối với nhau thông qua các liên kết (link). Hiểu một cách đơn giản thì Danh sách liên kết là một cấu trúc dữ liệu bao gồm một nhóm các nút (node) tạo thành một chuỗi. Mỗi nút gồm dữ liệu ở nút đó và tham chiếu đến nút kế tiếp trong chuỗi.
Sau đây là bài xây dựng danh sách liên kết quản lý thông tin nhân viên:
Mã số nhân viên, họ, tên, ngày sinh có kiểu dữ liệu là chuỗi (string).
Thâm niên và hệ số có kiểu dữ liệu là số thực double
typedef struct
{
string msnv;
string ho;
string ten;
string ngaysinh;
double thamnien;
double heso;
}nvType;
Tạo các hàm định nghĩa như định nghĩa node, định nghĩa danh sách liên kết, khởi tạo con trỏ đầu và cuối (hình 3.2).
typedef struct Node
{
nvType infor; // phần thông tin
struct Node* next; //cho con trỏ chỉ vào node sau
}nvNodeType;
//định nghĩa danh sách lk quản lý ds nhân viên
typedef struct
{
nvNodeType* head;
nvNodeType* tail;
}dsnv_LList;
void Init_dsnv_LList(dsnv_LList* l)
{
l->head = NULL;
l->tail = NULL;
}
Tạo các hàm nhập thông tin nhân viên và hàm thêm thông tin vào đầu mảng (Add First).
Hàm add first dùng để thêm thông tin vào đầu mảng, thông tin thêm sau sẽ đứng trước và thông tin được thêm từ trước bị đẩy về sau.
void Nhap_NV(nvType& nv)
{
cout << “MSNV: “; getline(cin, nv.msnv);
cout << “Ho: “; getline(cin, nv.ho);
cout << “Ten: “; getline(cin, nv.ten);
cout << “Ngaysinh: “; getline(cin, nv.ngaysinh);
cout << “Tham nien: “; cin >> (nv.thamnien);
cout << “he so: “; cin >> (nv.heso);
}
//tạo node từ ô đc nhập
nvNodeType* Get_nvNode(nvType x)
{
//tạo con trỏ kiểu Node để chứa kết quả
nvNodeType* p;
p = new nvNodeType;
p->infor = x;
p->next = NULL;
return p;
}
void Add_First(dsnv_LList* l, nvNodeType* n)
{
if (l->head == NULL)// nếu ds rỗng
{
l->head = n;
l->tail = n;
}
else
{
n->next = l->head;
l->head = n;
}
}
Các hàm xuất thông tin nhân viên
Chương trình xuất và in node nhân viên:
void Xuat_NV(nvType nv)
{
cout << “\t” << nv.msnv;
cout << “\t” << nv.ho;
cout << “\t” << nv.ten;
cout << “\t” << nv.thamnien;
cout << “\t” << nv.ngaysinh;
cout << “\t” << nv.heso << “\n”;
}
//In Node ra màn hình
void Print_nvNode(nvNodeType* n)
{
Xuat_NV(n->infor);
}
//in danh sách liên kết
void Print_List(dsnv_LList* l)
{
nvNodeType* p;
p = l->head;
while (p != NULL)
{
Xuat_NV(p->infor);
p = p->next;
}
}
Tìm kiếm bằng Linear Search (theo tên nhân viên):
Tìm kiếm thông tin nhân viên dựa vào tên nhân viên dùng hàm LinearSearch:
nvNodeType* Find_Llist(dsnv_LList* l, string ma)
{
nvNodeType* p;
for (p = l->head; p != NULL; p = p->next)
{
if (p->infor.ten == ma)
return p;
}
return NULL;
}
Chương trình con selection Sort sắp xếp mảng nhân viên theo mã số nhân viên từ nhỏ đến lớn.
void SelectionSort_Llist(dsnv_LList* list)
{
nvNodeType* p, *q, *min;
//con trỏ p dùng duyệt qua dslk
//con trỏ q dùng tìm min
p = list->head;
while (p != list->tail)
{
q = p->next;
//tìm min
min = p;
while (q != NULL)
{
if (q->infor.msnv < min->infor.msnv)
min = q;
q = q->next;
}
swap(min->infor, p->infor);
p = p->next;
}
}
void Insert_Sorted(dsnv_LList* list, nvNodeType* n)
{
nvNodeType* p;
p = list->head;
if (p == NULL || p->infor.heso > n->infor.heso)
Add_First(list, n);
else
{
while (p->next != NULL && p->next->infor.heso < n->infor.heso)
p = p->next;
n->next = p->next;
p->next = n;
}
}
void InsertionSort_Llist(dsnv_LList* list)
{
dsnv_LList* res;
res = new dsnv_LList;
Init_dsnv_LList(res);
nvNodeType* p, *q;
p = list->head;
while (p != NULL)
{
q = p->next;
p->next = NULL;
Insert_Sorted(res, p);
p = q;
}
list->head = res->head;
list->tail = res->tail;
}
Chương trình con interchange Sort sắp xếp mảng nhân viên theo Tên nhân viên.
void InterchangeSort_Llist(dsnv_LList* list)
{
nvNodeType* p, *q;
//con trỏ p dùng duyệt qua dslk
//con trỏ q đi quét
p = list->head;
while (p != list->tail)//vòng lặp ngoài
{
q = p->next;
while (q != NULL)
{
if (q->infor.ten < p->infor.ten)
swap(q->infor, p->infor);
q = q->next;
}
p = p->next;
}
}
Chương trình con Bubble Sort sắp xếp mảng nhân viên theo thâm niên từ nhỏ đến lớn.
void BubbleSort_Llist(dsnv_LList* list)
{
nvNodeType* p1, *p2, *q1, *q2;
p1 = list->head;
p2 = list->tail;
while (p1 != p2)
{
q1 = p1;
q2 = q1->next;
while (q2 != NULL)
{
if (q1->infor.thamnien > q2->infor.thamnien)
swap(q1->infor, q2->infor);
if (q2 != p2)
{
q1 = q1->next;
q2 = q2->next;
}
else
q2 = NULL;
}
p2 = p1;
}
}
void trinhDon()
{
system(“cls”);
cout << “\nTHAO TAC Danh Sach Lien Ket”;
cout << “\n1 Nhap mang”;
cout << “\n2 Xuat mang”;
cout << “\n3 Tim kiem voi LinearSearch”;
cout << “\n4 Sap xep voi Selection Sort”;
cout << “\n5 Sap xep voi Interchange Sort”;
cout << “\n6 Sap xep voi Bubble Sort”;
cout << “\n7 Sap xep voi Insection Sort”;
cout << “\n8 thoat”;
}
int main()
{
dsnv_LList* list;
list = new dsnv_LList;
Init_dsnv_LList(list);
int pressKey;
nvType nv;
nvNodeType* n;
while (1)
{
trinhDon();
cout << “\nNhap lua chon (1-8):”;
cin >> pressKey;
switch (pressKey)
{
case 1:
{
//nhập xuất danh sách
char t = ‘y’;
cout << “Nhap thong tin nhan vien: \n” << endl;
while (t == ‘y’ || t == ‘Y’)
{
cin.ignore();
Nhap_NV(nv);
n = new nvNodeType;
n = Get_nvNode(nv);
Add_First(list, n);
cout << “\nNhap y hoac Y để tiep tuc: “;
cin >> t;
}
system(“pause”);
break;
}
case 2:
{
Print_List(list);
system(“pause”);
break;
}
case 3:
{
cout << “Tim kiem nhan vien theo manv bang Linear Search: “;
string ma = “”;
cout << “Nhap vao ma NV can tim: “; cin >> ma;
nvNodeType* result = Find_Llist(list, ma);
if (result == NULL) cout << “Khong tim thay nhan vien phu hop!\n”;
else {
cout << “Thong tin nhan vien can tim: “;
Print_nvNode(result);
}
system(“pause”);
break;
}
case 4:
{
SelectionSort_Llist(list);
Print_List(list);
system(“pause”);
break;
}
case 5:
{
SelectionSort_Llist(list);
Print_List(list);
system(“pause”);
break;
break;
}
case 6:
{
InterchangeSort_Llist(list);
Print_List(list);
system(“pause”);
break;
break;
}
case 7:
{
BubbleSort_Llist(list);
Print_List(list);
system(“pause”);
break;
break;
}
case 8:
{
InsertionSort_Llist(list);
Print_List(list);
system(“pause”);
break;
return 0;
}
default:
break;
}
}
}
Tác giả : Bùi Kiều Trang, Trần Minh Nhựt ( sinh viên lớp 19DHT02, khoa Công nghệ thông tin)
Tài liệu Kết Nối Trẻ 