Về việc dùng con trỏ trong hàm tìm kiếm

#1

Mình đang làm bài tập lớn môn Cấu trúc dữ liệu với đề tài là áp dụng cây nhị phân ( Binary Search Tree ) để quản lí nhân viên của một công ty:
Source Code:

#include <iostream>
#include <string>
using namespace std;
struct Nhanvien
{
	int idnv;
	string hoten;
	string gioitinh;
	string diachi;
	int namsinh;
	Nhanvien* left;
	Nhanvien* right;
};

class BSTree
{
public:
	BSTree() // ham tao
	{
		root = NULL;
		size = 0;
	}

	void insert(Nhanvien nv) //ham nhap
	{
		insert(nv, root);
		size++;
	}

	void viewAll1() //duyet giua cay
	{
		viewAll1(root);
	}

	void viewAll2() //duyet truoc cay
	{
		viewAll2(root);
	}

	void viewAll3() //duyet sau cay
	{
		viewAll3(root);
	}

	~BSTree() // ham huy
	{
		makeEmpty();
	}

	bool isEmpty() // ham kiem tra rong
	{
		if (root == NULL) 
			cout << " Khong co nhan vien nao!" << endl;
		return false;
	}

	void makeEmpty() // ham xoa cay
	{
		makeEmpty(root);
	}
	int currentsize() // ham tra ve so phan tu tren cay
	{
		return size;
	}

	int findMin() // tim phan tu nho nhat tren cay
	{
		Nhanvien* v = findMin(root);
		return v->idnv;
	}
	int findMax()  // tim phan tu lon nhat tren cay
	{
		Nhanvien* v = findMax(root);
		return v->idnv;
	}

	void remove(int x) // xoa 1 con tren cay
	{
		remove(x, root);
	}
	Nhanvien* search(int id)
	{
		return search(id, root);
	}

private:
	Nhanvien* root; //root = goc
	int size; //kick thuoc cay

	void makeEmpty(Nhanvien*& t)
	{
		if (t == NULL)
			return;

		makeEmpty(t->left);
		makeEmpty(t->right);
		delete t;
		t = NULL;
		size = 0;
	}

	void insert(Nhanvien nv, Nhanvien*& t)
	{

			if (t == NULL)
			{
				t = new Nhanvien;
				cout << "___________Thong tin nhan vien___________" << endl;
				cout << " Nhap ma ID nhan vien: " << endl;  cin >> t->idnv; cin.ignore(); //cin.ignore() tranh nhay sang phan khac khi nhap
				cout << " Ho ten nhan vien: " << endl; getline(cin, t->hoten); cin.ignore();
				cout << " Gioi tinh: " << endl; getline(cin, t->gioitinh); cin.ignore();
				cout << " Dia chi: " << endl; getline(cin, t->diachi); cin.ignore();
				cout << "Nam sinh: " << endl; cin >> t->namsinh; cin.ignore();
				t->left = NULL;
				t->right = NULL;
			}
			else if (nv.idnv < t->idnv)
				insert(nv, t->left);
			else if (nv.idnv > t->idnv)
				insert(nv, t->right);
			else
				cout<<"ID da ton tai!"; // so bao danh da ton tai, khong lam gi ca
	}

	void viewAll1(Nhanvien*& t) //duyet kieu giua
	{
		if (t != NULL)
		{
			viewAll1(t->left);
			cout << "Ma ID: " << t->idnv << endl;
			cout << "Ho ten: " << t->hoten << endl;
			cout << "Gioi tinh: " << t->gioitinh << endl;
			cout << "Dia chi: " << t->diachi << endl;
			cout << "Nam sinh: " << t->namsinh << endl;
			cout << "__________________________________________" << endl;
			viewAll1(t->right);
		}
	}
	void viewAll2(Nhanvien*& t) //duyet kieu truoc
	{
		if (t != NULL)
		{
			
			cout << "Ma ID: " << t->idnv << endl;
			cout << "Ho ten: " << t->hoten << endl;
			cout << "Gioi tinh: " << t->gioitinh << endl;
			cout << "Dia chi: " << t->diachi << endl;
			cout << "Nam sinh: " << t->namsinh << endl;
			cout << "__________________________________________"<<endl;
			viewAll2(t->left);
			viewAll2(t->right);
		}
	}
	void viewAll3(Nhanvien*& t) //duyet kieu sau
	{
		if (t != NULL)
		{
			viewAll3(t->left);
			viewAll3(t->right);
			cout << "Ma ID: " << t->idnv << endl;
			cout << "Ho ten: " << t->hoten << endl;
			cout << "Gioi tinh: " << t->gioitinh << endl;
			cout << "Dia chi: " << t->diachi << endl;
			cout << "Nam sinh: " << t->namsinh << endl;
			cout << "__________________________________________"<<endl;
			
		}
	}
	void remove(int x, Nhanvien*& t) {
		if (t == NULL) return; 
		if (x < t->idnv)
			remove(x, t->left); // de quy xoa con trai
		else if (x > t->idnv)
			remove(x, t->right); // de quy xoa con phai
		else if (t->left != NULL && t->right != NULL) { //TH neu co 2 con 
			t->idnv = findMin(t->right)->idnv;
			remove(t->idnv, t->right);
		}
		else { // xoa 1 con hoac 1 la
			Nhanvien* old = t;
			t = (t->left != NULL) ? t->left : t->right; //neu t->left rong thi gia tri t la t->left con khong se la t->right
			delete old;
			size--;
		}
	}

	Nhanvien* findMin(Nhanvien* t) {
		if (t == NULL)
			return NULL;
		if (t->left == NULL)
			return t;
		return findMin(t->left);
	}

	Nhanvien* findMax(Nhanvien* t) {
		if (t != NULL)
			while (t->right != NULL)
				t = t->right;
		return t;
	}

	Nhanvien* search(int id, Nhanvien* t)
	{
		if (t == NULL)
			return NULL;
		if (id < t->idnv)
			return search(id,t->left);
		else if (id > t->idnv)
			return search(id, t->right);
		else
			return t;
	}
};

int main()
{
	int select, n; //bien select: lua chon nhap tu ban phim
	BSTree bst;
	while (true) //luon hien thi menu khi thuc hien dc 1 chuc nang
	{
		cout << "__________________CHUONG TRINH QUAN LI NHAN VIEN___________________" << endl;
		cout << endl;
		cout << " 1. Them nhan vien " << endl;
		cout << endl;
		cout << " 2. Xoa nhan vien" << endl;
		cout << endl;
		cout << " 3. Xem so luong nhan vien hien co " << endl;
		cout << endl;
		cout << " 4. Tim kiem nhan vien" << endl;
		cout << endl;
		cout << " 5. Hien thi danh sach nhan vien " << endl;
		cout << endl;
		cout << " 6. Hien thi nhan vien co ma id max, min" << endl;
		cout << endl;
		cout << " 7. Xoa toan bo du lieu!" << endl;
		cout << endl;
		cout << " 8. Thoat chuong trinh" << endl;
		cout << endl;
		cout << " __________________________________________________________________" << endl;
		cout << " Nhap lua chon cua ban: ";
		cin >> select;

		switch (select)
		{
		case 1:
			system("cls");
			cout << " Nhap so luong nhan vien: " << endl;
			cin >> n;

			for (int i = 0; i < n; i++)
			{
				Nhanvien nv;
				bst.insert(nv);
			}
			break;
		case 2:
			system("cls");
			int x;
			do {
				cout << "Nhap ma id nhan vien can xoa: " << endl;;
				cin >> x;
				bst.remove(x);
				cout << "So luong nhan vien hien con lai: " << bst.currentsize() << " nguoi " << endl;
				break;
			} while (!bst.isEmpty());
			break;
		case 3:
			system("cls");
			cout << "So luong nhan vien hien co: " << bst.currentsize() << " nguoi "<<endl;
			break;
		case 4:
			system("cls");
			do
			{		
				int id;
				cout << " Nhap ma nhan vien can tim kiem ";
				cin >> id;
				Nhanvien* n1 = bst.search(id);
				if (n1 != NULL)
				{
					cout << "Ma ID: " << n1->idnv << endl;
					cout << "Ho ten: " << n1->hoten << endl;
					cout << "Gioi tinh: " << n1->gioitinh << endl;
					cout << "Dia chi: " << n1->diachi << endl;
					cout << "Nam sinh: " << n1->namsinh << endl;
					cout << "__________________________________________" << endl;
				}
				else
					cout << " ma ID khong ton tai hoac danh sach rong!"<<endl;
				break;
			} while (!bst.isEmpty());
			break;
		case 5:
			system("cls");
			int m;
			do
			{
				cout << " Co 3 kieu hien thi (xet theo ma ID): 1. Duyet truoc, 2. Duyet giua, 3. Duyet sau" << endl;
				cout << " Hay chon 1 trong 3 kieu: "; cin >> m;
				switch (m)
				{
				case 1:
					system("cls");
					bst.viewAll2();
					break;
				case 2:
					system("cls");
					bst.viewAll1();
					break;
				case 3:
					system("cls");
					bst.viewAll3();
					break;
				default:
					cout << " Lua chon khong hop le!";
					break;
				}
				break;
			} while (!bst.isEmpty());
			break;
		case 6:
			system("cls");
			do
			{
				cout << " Ma id lon nhat la: " << bst.findMax() << endl;
				cout << " Ma id nho nhat la: " << bst.findMin() << endl;
				break;
			} while (!bst.isEmpty());
			break;
		case 7:
			system("cls");
			do
			{ 
				bst.makeEmpty();
				if (bst.isEmpty())
				cout << bst.currentsize() << endl;
				break;
			} while (!bst.isEmpty());
			break;
		case 8:
			return 0;
		}
	}
	return 0;
}

Mình đang thắc mắc case 4: ( bắt đầu dùng hàm tìm kiếm (search) bằng việc nhập số 4 tương ứng menu) thì con trỏ n1 chỉ luôn trỏ vào phần tử đầu tiên mình đã khai báo ở hàm insert(). Còn nếu nhập mã id để tìm kiếm mà mà id không phải là của đối tượng nhân viên đầu tiên như mình nói trên thì sẽ báo lỗi null pointer. Tiện đây mình xin ý kiến về code của mình để mình rút kinh nghiệm sau này! Cảm ơn mọi người đã bỏ thời gian!

#2

hãy dùng debug để kiểm tra lỗi,
code của bạn cần chú ý cách đặt tên. ko nên đặt viewAll1 rồi ghi chú kiểu vậy, tên hàm tên biến cần ngắn gọn nhưng giúp người đọc code nhìn vào hiểu được method hay biến đó có chức năng gì. Đặt tên đôi khi rất mất thời gian và không có cái tên nào là hoàn hảo!
đối với C++, bạn cần cẩn thận để tránh memory leak, nếu chưa có kinh nghiệm bạn cần kiểm tra với trường hợp đơn giản nhất là có ít nhất 2 hay 3 nhân viên trong cây BST của bạn, debug để chắc chắn rằng các node được free. Ngoài ra điều này cũng giúp bạn chắc chắn code bạn đã duyệt đúng tất cả các node trong cây.
bạn nên tạo cho mình một thư viện đọc ghi file, thay vì ngồi gõ console nhập dữ liệu hãy cho máy đọc file có cấu trúc và insert tự động vào cây của bạn, đây là một đề bài khá cơ bản khi bạn học oop.
đã xài oop thì xài cho tới, nhân viên bạn có thể khai báo cho nó thành một class kế thừa từ một abstract class, cây của bạn sẽ chứa tụi abstract này. Bạn có thể mở rộng ra không chỉ quản lý nhân viên mà có thể quản lý bất kỳ class nào được kế thừa từ lớp abstract trên.
PS: debug là một kỹ năng rất quan trọng, bạn cần tự debug để tìm ra lỗi từ đó fix thay vì phải đi hỏi, điều này cũng giúp cho kỹ năng lập trình của bạn được cải thiện đáng kể.

5 Likes
#3

Cảm ơn bạn đã góp ý! Nhưng mình đang thắc mắc phần case 4: của mình tại sao nó chỉ nhận mỗi nhân viên đầu tiên mình khai báo khi dùng hàm insert (nhập khi chạy console) còn lại thì đều báo lỗi là null pointer?

#4

vì mình làm biếng đọc code của bạn nên không biết chắc bạn đang gặp lỗi gì, nhưng có thể đoán rằng bạn đã chưa insert được thằng thứ 2 vào bst, và hình như bạn chưa cấp phát bộ nhớ cho bst.

4 Likes
#5

Close, mình đã fix đc r, cảm ơn bạn @kiencon

#6

Nếu vậy thì dùng template phù hợp hơn :smiley:

Kéo left với right ra khỏi Nhanvien vì nó là của Node<T>.

6 Likes
#7 
NhanVien nv;
bst.insert(nv);

:smiling_imp::scream:

private:
    void insert(NhanVien nv, NhanVien*& t)

Bạn hạn chế dùng nhập/xuất trong 1 lớp dữ liệu nhé. Việc nhập/xuất thì thực hiện tại 1 hàm/lớp khác.

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