Khám Phá Cấu Trúc Dữ Liệu và Thuật Toán
Chào mừng bạn đến với thế giới thú vị của cấu trúc dữ liệu và thuật toán! Nếu bạn đang tìm kiếm một cách để hiểu rõ hơn về cách tổ chức và xử lý dữ liệu trong lập trình, bạn đã đến đúng nơi. Trong bài viết này, chúng ta sẽ tìm hiểu về cấu trúc dữ liệu đầu tiên, đó là Mảng (Array).
Cấu Trúc Dữ Liệu Là Gì?
Cấu trúc dữ liệu là các khối dữ liệu được tổ chức một cách có hệ thống để sử dụng với các thuật toán. Đây là phương tiện mà các nhà phát triển lưu trữ và truy xuất dữ liệu một cách hiệu quả. Hãy tưởng tượng rằng các thuật toán giống như những người bạn thông minh giúp bạn giải quyết vấn đề, còn cấu trúc dữ liệu là cách bạn tổ chức dữ liệu để các thuật toán có thể hoạt động hiệu quả hơn.
Khám Phá Cấu Trúc Dữ Liệu Đầu Tiên: Mảng
Khi nghĩ về mảng, bạn có thể hình dung nó như một bộ sưu tập các hộp được sắp xếp liền kề trong bộ nhớ. Mỗi hộp chứa một giá trị và tất cả các hộp đều có cùng một kiểu dữ liệu. Kích thước của mảng là cố định, điều này có nghĩa là nếu bạn muốn thêm một phần tử mới và đã đạt đến kích thước tối đa, bạn sẽ cần tạo một mảng mới để chứa phần tử đó.
cpp
int grades[] = {1, 2, 3};
int size = sizeof(grades) / sizeof(grades[0]); // chia 12 bytes/4 bytes
// phần tử đầu tiên là int và kích thước là 4
// tổng kích thước là 12 vì chúng ta có 3 số
// vòng lặp dễ đọc
for(int i = 0; i < size; i++) {
std::cout << grades[i] << '\n';
}
// cách lập trình khác
for(int* ptr = grades; ptr < grades + size; ptr++) {
std::cout << *ptr << '\n';
}Hiểu Về Con Trỏ
Tôi hiểu rằng con trỏ có thể khiến bạn cảm thấy sợ hãi, nhưng việc hiểu rõ về chúng sẽ giúp bạn trở thành một lập trình viên thông minh hơn. Khi bạn viết ptr, bạn đang lấy địa chỉ của hộp. Khi viết *ptr, bạn thực sự đang mở hộp và xem bên trong. Hầu hết các ngôn ngữ lập trình đều xử lý điều này một cách tự động, vì vậy hãy tìm hiểu về nó thay vì coi đó là điều bí ẩn. Con trỏ rất hữu ích cho việc tối ưu hóa và tránh sao chép không cần thiết.
Mảng Động: std::vector
std::vector được sử dụng để tránh kích thước cố định và tăng kích thước một cách động. Điều này có nghĩa là ngay cả khi chúng ta đã đạt kích thước tối đa bằng cách thêm một phần tử mới, dung lượng của nó sẽ tăng gấp đôi.
- Kích thước = số lượng phần tử thực tế bạn có
- Dung lượng = không gian đã được đặt trước
cpp
std::vector<int> dummyVec{1, 2, 3};
std::cout << "Ban đầu - Kích thước: " << dummyVec.size()
<< ", Dung lượng: " << dummyVec.capacity() << std::endl;
// Kết quả: Kích thước: 3, Dung lượng: 3
dummyVec.push_back(4);
std::cout << "Sau khi push_back - Kích thước: " << dummyVec.size()
<< ", Dung lượng: " << dummyVec.capacity() << std::endl;
// Kết quả: Kích thước: 4, Dung lượng: 6
for(int i = 0; i < dummyVec.size(); i++) {
std::cout << dummyVec[i] << '\n';
}Tối Ưu Hóa với std::vector
Bạn có thể tối ưu hóa std::vector bằng cách sử dụng emplace_back(newElement) thay vì push_back(newElement) để tránh sao chép và sử dụng reserve(size) để đặt trước một số bộ nhớ cho chúng ta, giống như đặt bàn tại nhà hàng.
Thử Thách Đầu Tiên
Giả sử chúng ta muốn tìm một sinh viên đạt 100 điểm trong một bài kiểm tra, chúng ta cần truy cập vào các hộp để xem kết quả. Hãy tưởng tượng rằng tất cả các số trong mảng đều được sắp xếp theo thứ tự tăng dần:
cpp
bool search(std::vector<int>& grades, int target = 100) {
for(int i = 0; i < grades.size(); i++) {
if(grades[i] == target) { // nếu một trong những số này bằng target, trả về true
return true;
}
}
return false; // không tìm thấy
}Tìm Kiếm Nhị Phân
Thay vì kiểm tra từng điểm một, chúng ta có thể kiểm tra điểm giữa và hỏi: "Điểm này cao hay thấp hơn?" Sau đó, loại bỏ một nửa các tùy chọn còn lại và lặp lại. Điều này cho phép chúng ta đạt được O(log n) trong trường hợp xấu nhất.
cpp
bool search(std::vector<int>& grades, int target = 100) {
int low = 0;
int high = grades.size() - 1;
while(low <= high) {
int mid = low + (high - low) / 2; // Tránh tràn số nguyên
if(grades[mid] == target) {
return true;
}
if(grades[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return false;
}Kết Luận
Chúng ta đã khám phá một số khái niệm cơ bản về cấu trúc dữ liệu và thuật toán, đặc biệt là về mảng và cách tối ưu hóa việc tìm kiếm. Hãy tiếp tục theo dõi phần tiếp theo, nơi chúng ta sẽ tìm hiểu về hash sets và hash maps. Nếu bạn có bất kỳ câu hỏi nào hoặc điều gì không rõ ràng, hãy để lại trong phần bình luận nhé!
Tài Nguyên Hữu Ích
- Tìm hiểu về con trỏ
- Sử dụng đúng std::vector
Hãy nhớ rằng việc học hỏi không bao giờ ngừng lại. Hãy thực hành và tìm hiểu thêm để trở thành một lập trình viên giỏi hơn!
