Try   HackMD

CTDL & GT

Ứng dụng Ngăn xếp (Stack) để tạo menu

Đối việc hiển thị các thông tin lựa chọn lên giao diện, ta xem màn hình đang hiển thị một Menu. Như vậy, một Menu có thể sẽ bị xếp chồng lên bởi một Menu khác và màn hình hiện tại chỉ hiển thị Menu đang ở trên đỉnh.

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

Để cài đặt, ta định nghĩa 2 lớp là Menu (định nghĩa một Menu - bao gồm các lựa chọn và tiêu đề) và MenuStack (chứa một ngăn xếp các Menu). Các phương thức trên lớp MenuStack có thể kể đến như:

  • Phương thức push(Menu): thêm một Menu lên đỉnh ngăn xếp
  • Phương thức pop(): xoá bỏ đi Menu đang ở đỉnh ngăn xếp
  • Phương thức top(): lấy ra Menu đang ở đỉnh ngăn xếp (để hiển thị)
  • Phương thức getChoice(): yêu cầu người dùng nhập vào một chọn lựa và trả về số ứng với chọn lựa (đã bao gồm việc kiểm tra hợp lệ)

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

Cài đặt của 2 lớp này có thể tìm thấy ở file mã nguồn Menu.h.

Việc định nghĩa ra các Menu và sử dụng chúng sẽ được thể hiện ở file mã nguồn main.cpp. Ở đây các Menu bao gồm: Đăng nhập, Chọn mục cần quản trị, Quản lý sách, Quản lý độc giả, Quản lý thủ thư, Quản lý mượn-trả và các Menu tìm kiếm.










const Menu loginMenu("WELCOME TO THE LIBRARY", vector<string>{"Login as librarian"});
const Menu mainMenu("WELCOME TO THE LIBRARY", vector<string>{"Books", "Readers", "Borrowing", "Librarians"});
const Menu booksMenu("BOOKS", vector<string>{"List all books", "Add book", "Edit book", "Delete book", "Search book"});
const Menu bookSearchMenu("BOOKS", vector<string>{"Search by id", "Search by title", "Search by author"});
const Menu readersMenu("READERS", vector<string>{"List all readers", "Add reader", "Edit reader", "Delete reader", "Search reader"});
const Menu readerSearchMenu("READERS", vector<string>{"Search by id", "Search by name"});
const Menu borrowingMenu("BORROWING", vector<string>{"List all borrowings", "Add borrowing", "Delete borrowing", "Search borrowing"});
const Menu borrowingSearchMenu("BORROWING", vector<string>{"Search by reader id", "Search by book id"});
const Menu librariansMenu("LIBRARIANS", vector<string>{"List all librarians", "Add librarian"});

Việc luân chuyển giữa các Menu thực hiện bằng câu lệnh switch-case, goto kết hợp phương thức getChoice().











































    // 1. Login screen
loginScreen:
    clearScreen();
    cout << menuStack;
    op = menuStack.getChoice();
	switch (op)
	{
		case 1:
			while (!enterLoginMenu());
			menuStack.push(mainMenu);
			break;
		default:
			goto exitApp;
	}
    
	// 2. Main menu
mainMenu:
	clearScreen();
	cout << menuStack;
	op = menuStack.getChoice();
	switch (op)
	{
		case 1:
			menuStack.push(booksMenu);
			goto booksMenu;
			break;
		case 2:
			menuStack.push(readersMenu);
			goto readersMenu;
			break;
		case 3:
			menuStack.push(borrowingMenu);
			goto borrowingMenu;
			break;
		case 4:
			menuStack.push(librariansMenu);
			goto librariansMenu;
			break;
		default:
			menuStack.pop();
			goto loginScreen;
	}

Ở mã nguồn trên, sau khi hiển thị Menu trên cùng của ngăn xếp MenuStack (bằng lệnh cout << menuStack;), ta sẽ dựa vào lựa chọn trả về từ phương thức getChoice() mà sẽ lựa chọn đẩy Menu nào tiếp theo vào ngăn xếp (phương thức push()) và di chuyển đến nhãn tương ứng (lệnh goto).

Bảng băm (HashTable), Danh sách liên kết (Linked List) và ứng dụng

Bảng băm là một cấu trúc dữ liệu quan trọng để phục vụ việc tối ưu hoá các truy vấn tìm kiếm, thêm mới, sửa đổi. Ta có thể ứng dụng trong việc lưu trữ các thông tin như: thông tin sách, thông tin mượn-trả hoặc thông tin độc giả. Do được sử dụng ở nhiều nơi và liên quan đến nhiều lớp, cũng như việc lựa chọn khoá để băm cũng phụ thuộc vào ngữ cảnh bài toán. Ta sẽ dựng một lớp chung để cài đặt cấu trúc dữ liệu này (có sử dụng generic).

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

Một trong những yếu tố quan trọng để xây dựng bảng băm là phải xây dựng hàm băm. Hàm băm sẽ quyết định vị trí lưu trữ của dữ liệu (ở đây là kiểu dữ liệu generic <T>) trong bảng băm.

Việc lựa chọn hàm băm sẽ được quyết định tại lúc tạo ra một đối tượng của lớp HashTableLL. Hai con trỏ hàm hash và isEqual sẽ trỏ đến hai hàm tương ứng là hàm băm khoá hash dựa trên giá trị có kiểu T - trả về một số nguyên ứng với giá trị băm được và hàm kiểm tra bằng nhau isEqual - kiểm tra xem khoá trong giá trị đứng trước và giá trị đứng sau trong tham số (đều có kiểu T) có thực sự bằng nhau hay không.

Việc kiểm tra này là cực kỳ cần thiết trong trường hợp tìm kiếm từ bảng băm, đặc biệt là khi xác suất xảy ra đụng độ luôn tồn tại.

Đối với giải thuật được cài trong lớp HashTableLL, việc xử lý đụng độ được dựa trên giải pháp sử dụng danh sách liên kết (hai chữ cái LL đại diện cho danh sách liên kết đơn - (single) Linked List). Như vậy, ta xem mỗi dòng trong bảng băm là một danh sách liên kết các Node, mà bảng băm là một mảng các Node nên sẽ có kiểu dữ liệu con trỏ cấp hai Node** (bảng sẽ có size dòng). Các phương thức insert(T) (thêm một giá trị mới vào bảng băm), remove(T) (xoá một giá trị ra khỏi bảng băm) và search(T) đều có sử dụng đến hàm hash(T) được truyền vào; hàm isEqual được sử dụng trong phương thức remove để đảm bảo xoá chính xác giá trị (khoá đúng với khoá cần xoá) và search(T) để đảm bảo tìm kiếm chính xác các giá trị chứa khoá cần tìm.
















vector<T> search(const T& searchKey) const
{
	vector<T> result;
	int index = hash(searchKey) % size;
	Node* current = table[index];
	while (current != nullptr)
	{
		if (isEqual(current->value, searchKey))
		{
			result.push_back(current->value);
		}
		current = current->next;
	}
	return result;
}

Đối với phương thức search(T), ta giả định rằng sẽ có nhiều giá trị mang cùng một khoá nên sẽ trả về không, một hoặc nhiều giá trị tìm được trong một mảng.

Cài đặt của lớp này có thể tìm thấy ở file mã nguồn HashTableLL.h.

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

Đối với từng kho chứa dữ liệu (Repository) - cụ thể là BookRepository (chứa thông tin của tất cả sách hiện có), ReaderRepository (chứa thông tin của tất cả độc giả) và BorrowingRepository (chứa thông tin của tất cả lượt mượn-trả sách) - ta sẽ tạo ra một hoặc một số bảng băm ứng với khoá là thuộc tính đang quan tâm. Ví dụ, đối với BookRepository, ta quan tâm việc tối ưu tìm kiếm theo tên tác giả hoặc mã định danh của sách. Do đó, ta sẽ tạo ra 2 bảng băm là booksByAuthorTable (ứng với hàm băm khoá là hashAuthor, hàm so sánh kiểm tra trùng khớp là isEqualAuthor) và booksByIdTable (hàm băm khoá là hashId, hàm so sánh kiểm tra trùng khớp là isEqualId).

Giải thuật trong các hàm băm khoá được sử dụng trong bài cũng hết sức đơn điệu, đó là cộng các ký tự để lấy tổng các giá trị mã hoá ký tự (theo bảng mã ASCII) và trả về tổng đó. Ví dụ đơn giản với hàm isEqualAuthor và hàm isEqualAuthor:


















// Hash function for author
static int hashAuthor(Book* const& book)
{
	// Hash author's name, return the sum of ASCII values of all characters
	int hashValue = 0;
	for (char c : toLower(book->getAuthor()))
	{
		hashValue += c;
	}
	return hashValue;
}

// Compare function for author
static bool isEqualAuthor(Book* const& book1, Book* const& book2)
{
	return toLower(book1->getAuthor()) == toLower(book2->getAuthor());
}

Cài đặt của các lớp này có thể tìm thấy ở các file mã nguồn Book.h, Reader.h và Borrowing.h.

Ngoài ra, bảng băm còn được sử dụng trong file mã nguồn Librarian.h để phục vụ tìm kiếm nhanh thủ thư để thực hiện bước đăng nhập hệ thống. Tuy nhiên, nếu số lượng thủ thư ít thì việc tối ưu này cũng không mang lại nhiều lợi ích mà ngược lại còn gây hao tổn không ít không gian bộ nhớ để chứa cả bảng băm.

Song song với việc tìm kiếm (ví dụ như phương thức getBookById(string), getBooksByAuthor(string),…), việc thực hiện các thao tác thêm hay xoá cũng sẽ làm ảnh hưởng đến dữ liệu trên bảng băm. Do đó, trên các phương thức như addBook(...), removeBook(string),… ta cũng sẽ phải xử lý cập nhật trên các bảng băm tương ứng. Dưới đây là minh hoạ cho các phương thức kể trên.



















































// This is not the final code, just for demonstrating the example above

// Find books by author
vector<Book*> getBooksByAuthor(const string& author) const
{
    Book temp("", "", author, "", "", 0, 0);
    return this->booksByAuthorTable.search(&temp);
}

// Add a new book
Book* addBook(const string& bookId, const string& title, const string& author, const string& category, const string& publisher, int year, int quantity)
{
	// Check if the book already exists
	Book* book = getBookById(bookId);
	if (book != nullptr)
	{
		cout << "Book with id " << bookId << " already exists\n";
		return nullptr;
	}

	// Create a new book
	book = new Book(bookId, title, author, category, publisher, year, quantity);
    
	// Insert to hash tables
	booksByAuthorTable.insert(books.back());
	booksByIdTable.insert(books.back());

	return book;
}

// Remove a book by id
bool removeBook(const string& bookId)
{
	// Find the book by id
	Book* book = getBookById(bookId);
	if (book == nullptr)
	{
		cout << "Book with id " << bookId << " not found\n";
		return false;
	}

	// Remove the book from the hash tables
	booksByAuthorTable.remove(book);
	booksByIdTable.remove(book);
    
	// Free memory
	delete book;

	return true;
}

Để minh hoạ cho cách hoạt động, ta giả sử có 3 cuốn sách và một bảng băm có kích thước là 5 (chỉ số dòng là 0, 1, 2, 3, 4) và 3 quyển sách có mã định danh lần lượt là:

  • BOOK00001: giá trị băm được là 66+79+79+75+48+48+48+49=492, vị trí trong bảng băm là 492 % 5 = 2
  • BOOK00002: giá trị băm được là 66+79+79+75+48+48+48+50=493, vị trí trong bảng băm là 493 % 5 = 3
  • BOOK00010: giá trị băm được là 66+79+79+75+48+48+49+48=492, vị trí trong bảng băm là 492 % 5 = 2

Vậy sau khi thêm tất cả vào bảng băm booksByIdTable, ta được kết quả như sau:

image

Cây nhị phân cân bằng AVL (AVL Tree) và ứng dụng

Ngoài việc sử dụng bảng băm, ta có thể sử dụng thêm cây nhị phân cân bằng AVL để tối ưu hoá thao tác tìm kiếm. Trong bài này, ta cũng sẽ cài đặt cây AVL dưới dạng sử dụng generic và cung cấp sẵn một số phương thức trên cây.

AVLTree

Cây AVL sử dụng chiều cao để cân bằng, do đó các thông tin cơ bản trong một nút (Node) bao gồm: value (giá trị tại nút), left (nút bên trái), right (nút bên phải) và height (chiều cao nút hiện tại).

Tương tự như cài đặt của HashTableLL, các phương thức cơ bản phải có của lớp AVLTree bao gồm: phương thức insert(T) (thêm một giá trị mới vào cây - ứng với việc tạo mới một nút), remove(T) (xoá một giá trị ra khỏi cây - ứng với việc xoá đi một nút) và search(T) (so sánh và tìm ra một hoặc một số giá trị (nút) thoả điều kiện bằng của hàm so sánh compare(T, T) truyền vào lúc tạo ra AVLTree).

Ngoài ra các phương thức hỗ trợ như tính toán chiều cao của nút height(Node*), tính độ chênh lệch chiều cao tại nút (bằng chiều cao cây con trái trừ chiều cao cây con phải) getBalance(Node*), xoay trái leftRotate(Node*), xoay phải rightRotate(Node*), thêm nút vào cây insert(Node*, T), xoá nút khỏi cây remove(Node*, T), tìm nút con bé nhất (nút trái cùng) minValueNode(Node*) cũng được cài đặt để hỗ trợ các phương thức chính phía trên.

Cài đặt của lớp này có thể tìm thấy ở file mã nguồn AVLTree.h.

Untitled

Cây AVL được sử dụng ở 2 kho chứa là BookRepository (phục vụ tìm kiếm theo tên sách) và ReaderRepository (phục vụ tìm kiếm theo tên độc giả). Ứng với đó là 2 phương thức so sánh compareTitle(Book*, Book*) và compareReaderByName(Reader*, Reader*):







// Book.h
// Compare function for title
static int compareTitle(Book* const& book1, Book* const& book2)
{
    return toLower(book1->getTitle()).compare(toLower(book2->getTitle()));
}







// Reader.h
// Compare function for reader by name
static int compareReaderByName(Reader* const& reader1, Reader* const& reader2)
{
    return toLower(reader1->getName()).compare(toLower(reader2->getName()));
}

Ở trong hai phương thức so sánh này có sử dụng đến hàm toLower() (có thể tìm thấy trong file mã nguồn StringHelper.h) để chuyển đổi chuỗi về dạng in thường, từ đó cho phép tìm kiếm không phân biệt hoa thường.

Đương nhiên, việc thêm hay xoá dữ liệu sách, độc giả cũng làm cây phải cập nhật. Do đó trong các phương thức như addBook(...), removeBook(string),… cũng sẽ phải gọi đến các phương thức cập nhật của cây.










































// This is not the final code, just for demonstrating the example above

// Add a new book
Book* addBook(const string& bookId, const string& title, const string& author, const string& category, const string& publisher, int year, int quantity)
{
    // Check if the book already exists
    Book* book = getBookById(bookId);
    if (book != nullptr)
    {
        cout << "Book with id " << bookId << " already exists\n";
        return nullptr;
    }

    // Create a new book
    book = new Book(bookId, title, author, category, publisher, year, quantity);
    
    // Construct AVL tree
    booksByTitleTree.insert(books.back());

    return book;
}

// Remove a book by id
bool removeBook(const string& bookId)
{
    // Find the book by id
    Book* book = getBookById(bookId);
    if (book == nullptr)
    {
        cout << "Book with id " << bookId << " not found\n";
        return false;
    }

    // Remove the book from the hash table and AVL tree
    booksByTitleTree.remove(book);

    // Free memory
    delete book;

    return true;
}

Cài đặt của các lớp này có thể tìm thấy ở các file mã nguồn Book.h và Reader.h.

Để minh hoạ cho cách hoạt động, ta giả sử có 3 cuốn sách có tên lần lượt là:

  • ABC
  • AAC
  • ACD
  • ACE

Vậy sau khi thêm tất cả vào cây AVL booksByTitleTree theo thứ tự, ta được kết quả như sau:

Untitled

Nếu ta thêm một cuốn sách có tiêu đề là ADE, cây sẽ bị mất cân bằng tại nút ACD và phép xoay trái xảy ra tại nút này để cây cân bằng lại như sau:

Untitled

Last changed by 
 
Lap Trinh
0
47

Read more

Bài tập Lập trình Hướng đối tượng

Định nghĩa một cấu trúc dữ liệu để lưu trữ thông tin về sinh viên, bao gồm tên, mã sinh viên, điểm trung bình, v.v.

Jun 23, 2024
Quản lý bán hàng

Untitled Diagram1.drawio

Jun 19, 2024
Read more from Lap Trinh
Published on HackMD