Cải tiến thuật toán tìm kiếm trong tree C++

#1

Mình có đề bài na ná nhau như này:
-Tìm sinh viên theo lớp
-Tìm sinh viên theo tên
-Tìm sinh viên theo khóa

điểm chung là 3 cái trên đều là chuỗi ký tự,mình đang viết 3 hàm tìm kiếm dạng như này :

void TimSV_Ten(DSSV root, char hoTen[30])
{
	stack <NodePointer> ST;
	int dem = 0;
	NodePointer t;
	ST.push(root);
	while (!ST.empty())
	{
		t = ST.top();
		ST.pop();


//Xử lý 
//--------------------------------------------------------------------------
		if (_stricmp(t->Key.tenSV, hoTen) == 0)
		{
			dem++;
			Xuat1NV(t->Key);
		}
//--------------------------------------------------------------------------

		if (t->RightChild != NULL)
			ST.push(t->RightChild);
		if (t->LeftChild != NULL)
			ST.push(t->LeftChild);

	}
	if (dem == 0)
		cout << "\nTrong danh sach khong co sinh vien nao co ten la : " <<hoTen;
}

Các hàm tìm kiếm khác mình đều dùng thuật toán trên,mình muốn hỏi có cách nào dùng 1 hàm tìm kiếm duy nhất ,truyền vào các tham số khác nhau để tìm không,mình không muốn tạo ra 3 hàm,bài vừa xấu mà vừa không hay,với cả chỉ khác nhau phần " Xử lý " trong code thôi.

Như thường lệ,mình xin thuật toán,có code mẫu càng hay hoặc chỉ đơn giản là keyword :stuck_out_tongue:
Mình xin trân trọng cảm ơn

#2

Tạo callback function để so sánh.

search(DSSV r, int (*cmp)(sv, sv)) { 
 cmp(sv_a, sv_b);
 ...
}
3 Likes
#3

Em chưa hiểu lắm,đó là so sánh 2 sinh viên,còn em là nhập thông tin từ bàn phím ( ví dụ nhập tên ) để so sánh với SV trong DSSV , code trên em nghĩ chỉ áp dụng khi so sánh 2 sinh viên trong danh sách thôi.

Mong bạn giúp đỡ

#4

Ý tưởng là, vì hàm search thân hàm y chang nhau, chỉ có phần so sánh khác nhau nên ta sẽ tách ra thành 1 callback function định nghĩa bên ngoài để gọi sau.

Thay vì tạo ra 3 hàm search thì bh chỉ cần tạo 3 hàm callback và thêm 3 hàm wrap lại để dễ xài
-> Bây giờ sẽ thành

bool equalsByAge(sv sv_a, sv sv_b) {
 return sv_a.age == sv_b.age
}

sv search(DSSV ds, sv searchValue, bool (*equals)(sv a, sv b)) {
 for sv in ds
  if(equals(sv, searchValue)) return sv
 return null //ko có sv nào thõa
}

sv searchByAge() {
 get(age)
 return search(DSSV, new sv(age), equalsByAges); // tạo object sv mới chỉ có age
}

-> Hàm seaerch ko bị lặp lại, nếu có thêm thông tin cần search chỉ cần tạo thêm hàm callback và truyền vào.

2 Likes
#5

Hi Nguyễn Văn Vương.
Dùng template. @_@!

2 Likes
#6

Anh rất hay chỉ bài cơ mà mỗi lần anh chỉ là em phải lục tung google lên tìm tòi :stuck_out_tongue:
Cảm ơn anh đã gợi ý :stuck_out_tongue:

#7

thắc mắc là đã dùng cây mà sao phải duyệt tất cả các node như vậy? cây không có sắp xếp theo tiêu chuẩn gì hết sao? Còn đơn giản nhất là viết hàm so sánh 2 sv, chỉ cần 1 trong 3 tiêu chí ok thì trả về true. Nhập vào cái gì thì cập nhật thông tin cái đó, hai cái còn lại để trống, khỏi cần quan tâm đến template làm gì.

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?