Mở Đầu
Chào các bạn! Hôm nay mình xin chia sẻ với các bạn một chủ đề thú vị về các cấu trúc dữ liệu và thuật toán thường được sử dụng trong lập trình Android. Việc áp dụng các kỹ thuật này không chỉ giúp ích cho việc phát triển ứng dụng mượt mà mà còn giúp tiết kiệm tài nguyên hệ thống. Hãy cùng mình khám phá nhé!
Cấu Trúc Dữ Liệu Thường Gặp
1. List
- Là một tập hợp các phần tử được sắp xếp theo thứ tự.
- Mỗi phần tử trong danh sách có chỉ số (index) duy nhất, bắt đầu từ 0.
- Các phần tử có thể trùng lặp.
- Có thể truy cập, thêm, xóa hoặc sửa đổi phần tử trong danh sách thông qua chỉ số.
- Các loại List phổ biến: ArrayList, LinkedList, Vector, Stack, Queue.
Demo Code
java
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
List<String> myList = new ArrayList<>();
myList.add("Apple");
myList.add("Banana");
myList.add("Orange");
for (String fruit : myList) {
System.out.println(fruit);
}
}
}2. Map
- Được cấu thành từ cặp key-value.
- Mỗi khóa độc nhất và ánh xạ đến giá trị tương ứng.
- Không có thứ tự rõ ràng, trừ khi dùng LinkedHashMap hoặc TreeMap.
- Có thể truy cập, thêm, xóa hoặc sửa đổi giá trị qua khóa.
- Các loại phổ biến: HashMap, TreeMap, LinkedHashMap.
Demo Code
java
import java.util.HashMap;
import java.util.Map;
public class Main {
public static void main(String[] args) {
Map<String, Integer> myMap = new HashMap<>();
myMap.put("Alice", 25);
myMap.put("Bob", 30);
myMap.put("Charlie", 28);
for (Map.Entry<String, Integer> entry : myMap.entrySet()) {
System.out.println(entry.getKey() + " is " + entry.getValue() + " years old.");
}
}
}3. Stack
- Cấu trúc dữ liệu theo cơ chế LIFO (Last In, First Out).
- Phần tử cuối cùng được thêm vào là phần tử đầu tiên được lấy ra.
Demo Code
java
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Stack<Integer> myStack = new Stack<>();
myStack.push(10);
myStack.push(20);
myStack.push(30);
while (!myStack.isEmpty()) {
System.out.println(myStack.pop());
}
}
}Các Thuật Toán Thông Dụng
1. Thuật Toán Sắp Xếp
Một trong những thuật toán đơn giản nhất là Bubble Sort. Nó hoạt động bằng cách so sánh cặp phần tử liên tiếp và hoán đổi nếu cần.
Demo Thuật Toán Bubble Sort
java
public class Main {
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(arr);
System.out.println("Sorted array:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}2. Đệ Quy
Khái niệm đệ quy mô tả kỹ thuật hàm tự gọi để giải quyết bài toán phức tạp bằng cách chia nhỏ thành các bài toán con dễ hơn.
Demo Tính Giai Thừa
java
public class Main {
public static int factorial(int n) {
if (n == 0 || n == 1) {
return 1;
} else {
return n * factorial(n - 1);
}
}
public static void main(String[] args) {
int number = 5;
int result = factorial(number);
System.out.println("Giai thừa của " + number + " là: " + result);
}
}3. Tìm Kiếm Nhị Phân
Sử dụng để tìm kiếm phần tử trong mảng đã được sắp xếp, giúp giảm đáng kể số lần so sánh.
Demo Tìm Kiếm Nhị Phân
java
public class Main {
public static int binarySearch(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
}
if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // Không tìm thấy
}
public static void main(String[] args) {
int[] arr = {2, 3, 4, 10, 40};
int target = 10;
int result = binarySearch(arr, target);
if (result == -1) {
System.out.println("Phần tử không có trong mảng");
} else {
System.out.println("Phần tử được tìm thấy tại chỉ số " + result);
}
}
}4. Chia Để Trị
Kỹ thuật giúp giải quyết bài toán lớn bằng cách chia thành các bài toán nhỏ.
Demo Thuật Toán Merge Sort
java
public class MergeSort {
public static void merge(int[] arr, int left, int middle, int right) {
int n1 = middle - left + 1;
int n2 = right - middle;
int[] leftArr = new int[n1];
int[] rightArr = new int[n2];
for (int i = 0; i < n1; ++i) leftArr[i] = arr[left + i];
for (int j = 0; j < n2; ++j) rightArr[j] = arr[middle + 1 + j];
int i = 0, j = 0;
int k = left;
while (i < n1 && j < n2) {
if (leftArr[i] <= rightArr[j]) {
arr[k] = leftArr[i];
i++;
} else {
arr[k] = rightArr[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = leftArr[i];
i++;
k++;
}
while (j < n2) {
arr[k] = rightArr[j];
j++;
k++;
}
}
public static void sort(int[] arr, int left, int right) {
if (left < right) {
int middle = left + (right - left) / 2;
sort(arr, left, middle);
sort(arr, middle + 1, right);
merge(arr, left, middle, right);
}
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6, 7};
sort(arr, 0, arr.length - 1);
System.out.println("Mảng sau khi sắp xếp:");
for (int val : arr)
System.out.print(val + " ");
}
}Kết Luận
Khi tìm hiểu kiến thức mới, hãy luôn chủ động và tìm hiểu kỹ để nắm vững bản chất. Việc áp dụng đúng cấu trúc dữ liệu và thuật toán sẽ giúp bạn trở thành lập trình viên giỏi hơn.
Tài Nguyên Tham Khảo:
- VNOI: VNOI
- Data Structures: YouTube Playlist
- Ông Dev: YouTube Video
- Thuật Toán Ứng Dụng: Daotao.ai
- Git Thuật Toán Java: GitHub
- GpCoder: GpCoder
source: viblo
