Cấu Trúc Dữ Liệu & Giải Thuật

Có thể bạn quan tâm

Cấu trúc dữ liệu & Giải thuật

Danh sách các bài viết trong chuyên mục Cấu trúc dữ liệu & Giải thuật, đây là những bài viết mới nhất được cập nhật trong mục Giải thuật.

Để trở thành một lập trình viên chuyên nghiệp thì đòi hỏi bạn phải có tư duy lập trình vững chắc, hay còn gọi là background vững chắc, vì vậy hầu như các trường cao đẳng và đại học luôn cho học sinh học những ngôn ngữ như C, C++ trước để rèn luyện tư duy của họ.

Khi bạn đã biết về cú pháp và cách sử dụng các ngôn ngữ đó thì bạn phải tìm hiểu thêm về thuật toán và giải thuật, sau đó áp dụng nó để đưa vào bài toán lập trình cụ thể, điều này sẽ được trình bày trong chuỗi bài học này.

Thuật toán là gì? Giải thuật là gì?

Nếu định nghĩa chính xác thì rất là khó hiểu, vì vậy mình dùng lời văn đơn giản cho gần gũi với mọi người nhé.: Thuật toán trong tiếng anh có nghĩa là Algorithms, ngoài ra nó còn được gọi là giải thuật, là tập hợp những bước thực hiện để giải quyết một bài toán cụ thể.

Ví dụ để kiểm tra một số có chia hết cho 2 hay không thì ta sẽ áp dụng vào định nghĩa như sau: Một số chia hết cho 2 là số chẵn, và không chia hết cho 2 là số lẻ.

b = c thì P(x) có nghiệm bất kì
b ≠ c thì P(c) vô nghiệm

Khi viết một giải thuật bạn phải vẽ sơ đồ, hoặc bạn dùng lời văn cũng được, nhưng phải trình bay rõ ràng về input, output, cũng như là quy trình thực hiện.

Ví dụ: thuật toán để giải phương trình bậc nhất P(x): ax + b = c, (a, b, c là các số thực), trong tập hợp các số thực có thể là một bộ các bước sau đây:

Input: a, b, c

Output: nghiệm

Quy trình:

Nếu a = 0
- b = c thì P(x) có nghiệm bất kì
- b ≠ c thì P(c) vô nghiệm
Nếu a ≠ 0
- P(x) có duy nhất một nghiệm x = (c - b)/a

Trên là mình đưa ra một ví dụ ở trên wikipedia.

Tại sao cần học giải thuật và thuật toán

Để có tư duy lập trình tốt thì bạn phải học thuật toán thật nhiều, code thật nhiều, điều này sẽ giúp bạn phản xạ cực nhanh. Bản thân mình hiện đang làm PHP là chủ yếu, và do trước đây có học qua C, C++ nên khi tìm hiểu PHP mình cảm thấy rất dễ, bởi mình đã có một nền tảng để có thể tìm hiểu bất kì một ngôn ngữ nào khác.

Các bài toán đơn giản khi vào thực tế đôi khi lại rất quan trọng, nó sẽ giúp bạn xử lý cho một công đoạn nào đó trong chương trình của bạn. Như mình khi đang làm với PHP, mình xử lý vòng lặp cần bổ sung một chức năng nào đó với những lần lặp chẵn, tức là các lần thứ 0, 2, 4, 6 ... như vậy là mình sử dụng thuật toán kiểm tra số chẵn để xử lý.

Và để giúp bạn luyện tư duy, luyện khả năng code của mình thì trong chuỗi bài viết này mình sẽ giới thiệu các bài toán hay gặp nhất, hy vọng sẽ giúp ích cho các bạn.

1THUẬT TOÁN CĂN BẢN
1	Thuật toán kiếm tra số nguyên tố
2	Thuật toán tìm ước chung lớn nhất trong C/C++
3	Thuật toán tính lũy thừa nhanh trong C/C++
4	Thuật toán kiểm tra số chẵn hay lẽ
5	Thuật toán kiểm tra năm nhuận
6	Thuật toán kiểm tra số hoàn hảo trong C++
7	Thuật toán kiểm tra số chính phương C++
8	Danh sách liên kết là gì? Sự khác nhau giữa DSLK và mảng

2SẮP XẾP & TÌM KIẾM
9	Sắp xếp và tìm kiếm là gì?
10	Thuật toán tìm kiếm tuyến tính (Linear search)
11	Thụât toán tìm kiếm nhị phân (Binary Search)
12	Thuật toán tìm kiếm nội suy (Interpolation Search)
13	Thuật toán sắp xếp nổi bọt (Bubble Sort)
14	Thuật toán sắp xếp chèn (Insertion Sort)
15	Thuật toán sắp xếp chọn (Selection Sort)
16	Thuật toán sắp xếp trộn (Merge Sort)
17	Thuật toán sắp xếp nhanh (Quick Sort)

3GIẢI THUẬT ĐỆ QUY
18	Hàm đệ quy là gì? Hoạt động ra sao?
19	Đệ quy tuyến tính (Linear Recursion)
20	Đệ quy đuôi (Tail Recursion)
21	Đệ quy nhị phân (Binary Recursion)
22	Đệ quy đa tuyến (Exponential Recursion)
23	Đệ quy lồng (Nested Recursion)
24	Đệ quy tương hỗ (Mutual Recursion)
25	Bài toán tháp Hà Nội: Sử dụng đệ quy để giải

4DANH SÁCH LIÊN KẾT ĐƠN
26	Cấu trúc dữ liệu của danh sách liên kết đơn
27	Tạo Node mới trong danh sách liên kết đơn
28	Chèn Node vào danh sanh liên kết đơn
29	Xóa Node trong danh sách liên kết đơn
30	Tìm kiếm và sắp xếp trong danh sách liên kết đơn
31	Quản lý sinh viên sử dụng danh sách liên kết đơn
32	Bài tập thực hành với danh sách liên kết đơn

5DANH SÁCH LIÊN KẾT ĐÔI
33	Danh sách liên kết đôi là gì? Cấu trúc dữ liệu của nó
34	Tạo Node mới trong danh sách liên kết đôi
35	Duyệt danh sách liên kết đôi
36	Chèn Node vào danh sách liên kết đôi
37	Xóa Node trong danh sách liên kết đôi
38	Tìm kiếm phần tử k trong danh sách liên kết đôi
39	Gộp hai danh sách liên kết đôi

6CẤU TRÚC CÂY
Cây nhị phân
1	Cấu trúc cây nhị phân là gì? Hoạt động ra sao?
2	Thêm Node vào cây nhị phân tìm kiếm
3	Duyệt cây nhị phân tìm kiếm
4	Tìm kiếm Node trên cây nhị phân tìm kiếm
5	Xuất Node con và lá trong cây nhị phân tìm kiếm
6	Tìm Node MAX và MIN trong cây nhị phân tìm kiếm
7	Xóa Node khỏi cây nhị phân tìm kiếm
Cây đỏ đen
8	Cây đỏ đen là gì? Cấu trúc của Red-Black Tree
9	Thêm Node mới vào cây đỏ đen
10	Xóa Node khỏi cây đỏ đen

7NGĂN XẾP STACK
11	Ngăn xếp Stack là gì? Cấu trúc và cơ chế hoạt động ra sao?
12	Cài đặt Stack bằng danh sách liên kết
13	Cài đặt Stack bằng mảng một chiều
14	Bài tập chuyển đổi cơ số bằng Stack
15	Bài tập kiểm tra số nguyên tố bằng Stack

8HÀNG ĐỢI QUEUE
16	Hàng đợi Queue là gì? Cấu trúc dữ liệu và các cách cài đặt Queue
17	Cài đặt hàng đợi Queue bằng danh sách liên kết
18	Cài đặt hàng đợi Queue bằng mảng một chiều
19	Tìm các số chẵn lẻ bằng Queue và Stack