Cấu trúc dữ liệu & giải thuật là gì?

Trong khoá học này, chúng ta sẽ cùng nhau tìm hiểu về cấu trúc dữ liệu và giải thuật. Trước hết, hãy xem cấu trúc dữ liệu và giải thuật là gì nhé!

---

Nội dung

Trong bài học này chúng ta sẽ cùng nhau tìm hiểu về:

• Giới thiệu khái niệm cấu trúc dữ liệu và giải thuật
• Tầm quan trọng của cấu trúc dữ liệu và giải thuật
• Cài đặt môi trường

---

Khái niệm cấu trúc dữ liệu và giải thuật

Cấu trúc dữ liệu là gì?

Cấu trúc dữ liệu là một cách lưu dữ liệu trong máy tính sao cho nó có thể được sử dụng một cách hiệu quả. Trong thiết kế nhiều loại chương trình, việc chọn cấu trúc dữ liệu là vấn đề quan trọng. Thông thường, một cấu trúc dữ liệu được chọn cẩn thận sẽ cho phép thực hiện thuật toán hiệu quả hơn. Khi đi vào chi tiết từng cấu trúc dữ liệu, mình sẽ cho các bạn thấy được việc áp dụng chính xác cấu trúc dữ liệu sẽ giúp cho chúng ta giải quyết vấn đề hiệu quả như thế nào.

Lưu ý: 

• Cấu trúc dữ liệu là tập hợp các kiểu dữ liệu được sắp xếp theo một trật tự cụ thể
• Cấu trúc dữ liệu khác với kiểu dữ liệu cấu trúc
• Mỗi cấu trúc dữ liệu đều có điểm mạnh và điểm yếu
• Không có một cấu trúc dữ liệu nào tốt cho mọi bài toán

Một số cấu trúc dữ liệu cơ bản: stack, queue, array, list, graph, tree, … 

Cấu trúc dữ liệu cây nhị phân

Cấu trúc dữ liệu được chi thành 2 loại là : tuyến tính và phi tuyến tính. Bạn có thể dễ dàng tìm thấy định nghĩa lý thuyết cũng như ưu nhược điểm của từng dạng cấu trúc dữ liệu này nên để đơn giản hóa, ở đây mình chỉ tập trung vào việc so sánh giữa 2 loại trong bảng sau:

CTDL TUYẾN TÍNH	CTDL PHI TUYẾN TÍNH
Các phần tử được sắp xếp theo thứ tự lần lượt, nối tiếp nhau.	các phần tử được sắp xếp theo thứ bậc trong đó một phần tử sẽ được kết nối với một hoặc nhiều phần tử.
Có thể được duyệt qua tất cả các phần tử một cách tuần tự trong một lần chạy. (nếu bắt đầu ở phần tử đầu tiên)	Có thể không duyệt qua tất cả các phần tử trong một lần chạy do cấu trúc thứ bậc.
Độ phức tạp về thời gian tăng theo kích thước dữ liệu.	Độ phức tạp về thời gian thường không đổi
Không phải là lựa chọn tốt nhất vì sự phức tạp trong hoạt động của các chương trình có độ phức tạp cao	Các cấu trúc khác nhau sử dụng bộ nhớ theo những cách hiệu quả khác nhau tùy thuộc vào nhu cầu.
Ví dụ: 1. Mảng - Arrays: các phần tử trong mảng có cùng kiểu dữ liệu, được sắp xếp liên tục trong bộ nhớ. 2. Ngăn xếp - Stack: các phần tử được lưu trữ theo nguyên tắc LIFO. Nghĩa là, phần tử cuối cùng được lưu trữ trong ngăn xếp sẽ bị xóa đầu tiên. 3. Hàng đợi - Queue: Cấu trúc dữ liệu hàng đợi hoạt động theo nguyên tắc FIFO trong đó phần tử đầu tiên được lưu trữ trong hàng đợi sẽ bị loại bỏ trước. 4. Danh sách liên kết - Linked List: các phần tử dữ liệu được kết nối thông qua một loạt các nút. Và, mỗi nút chứa các mục dữ liệu và địa chỉ của nút tiếp theo.	Ví dụ: Đồ thị - Graph: mỗi nút được gọi là đỉnh và mỗi đỉnh được nối với các đỉnh khác thông qua các cạnh. Cây - Tree: Tương tự như đồ thị, cây cũng là một tập hợp các đỉnh và các cạnh. Tuy nhiên, trong cấu trúc dữ liệu cây, chỉ có thể có một cạnh giữa hai đỉnh.

Vậy như thế nào là một cấu trúc dữ liệu hiệu quả?

• Lưu trữ chính xác, đầy đủ, phù hợp dữ liệu lưu trữ 
• Thuận tiện truy xuất và xử lý dữ liệu
• Tối ưu về bộ nhớ
• Tốc độ truy vấn nhanh

---

Giải thuật là gì?

Một giải thuật (thuật toán), là một tập hợp hữu hạn các hướng dẫn được xác định rõ ràng, có thể thực hiện được bằng máy tính, thường để giải quyết một lớp vấn đề hoặc để thực hiện một phép tính. Các thuật toán luôn rõ ràng và được sử dụng chỉ rõ việc thực hiện các phép tính, xử lý dữ liệu, suy luận tự động và các tác vụ khác.

Nói một cách đơn giản

Thuật toán là tập hợp các hướng dẫn được xác định rõ để giải quyết một vấn đề cụ thể. 

Vậy như thế nào là một giải thuật (thuật toán) tốt?

• Có đầu vào và đầu ra được xác định chính xác.
• Mỗi bước trong thuật toán phải rõ ràng.
• Thuật toán hiệu quả (tốn ít bộ nhớ, hiểu & xử lý nhanh, chính xác,...) trong số nhiều cách khác nhau để giải quyết một vấn đề.
• Nên được viết theo cách có thể được sử dụng trong các ngôn ngữ lập trình khác nhau chứ không phụ thuộc vào một ngôn ngữ bất kỳ.

Một số các thuật toán phổ biến như sắp xếp, tìm kiếm, DFS, BFS, … 

Ví dụ: Thuật toán tính và hiển thị tổng 2 số nguyên a,b được nhập vào từ bàn phím:

• Bước 1: Bắt đầu chương trình
• Bước 2: Nhập 2 số a, b từ bàn phím
• Bước 3: Kiểm tra 2 số a,b có phải số nguyên. 
  • 3.1 Nếu 2 số a,b không là số nguyên thì đi tới bước 6.
  • 3.2. Nế 2 số a,b là số nguyên thì đi tới bước 4
• Bước 4: Gán tổng 2 số a,b cho biến s
• Bước 5: Hiển thị biến s ra màn hình
• Bước 6: Kết thúc chương trình

Để dễ hiểu hơn, mình có vẽ ra Flowchart minh họa thuật toán trên. Hoặc bạn có thể tham khảo cách triển khai từ yêu cầu bài toán ra thuật toán và viết chương trình với python qua bài Tính & hiển thị tổng 2 số nguyên

1. Tìm và hiển thị ra màn hình số lớn nhất trong 3 số a,b,c nhập từ bàn phím.
2. Tính và hiển thị giai thừa một số n nhập từ bàn phím.
3. Giải phương trình ax² + bx + c = 0

Đừng quên để lại đáp án và thảo luận với cộng đồng ở phần bình luận nhé!

---

Tầm quan trọng của cấu trúc dữ liệu và giải thuật

Chúng ta hãy tưởng tượng mình là quản lý của một thư viện. Chúng ta để sách ngổn ngang ở khắp mọi nơi không theo một nguyên tắc nào cả. Do đó mỗi khi có ai đó muốn mượn sách thì chúng ta lại phải đi tìm từng cuốn một. Chúng ta cũng không có một quy trình rõ ràng cho việc cho mượn sách hoặc nhập sách vào kho để quản lý sách. Hậu quả cho những việc trên là thư viện trở nên rất hỗn loạn và hoạt động không hiệu quả.

Bây giờ hãy tưởng tượng lại theo một hướng khác. Chúng ta có những kệ sách được gắn chủ đề như Tiểu thuyết, Truyện ngắn, Thơ, … Mỗi khi cần một cuốn sách, ta biết ngay nơi chứa cuốn sách đó và tìm kiếm rất dễ dàng. Chúng ta có một quy trình mượn, nhập sách rõ ràng nên có thể biết ngay sự thay đổi của sách trong thư viện. Kết quả là thư viện hoạt động rất hiệu quả. Ở đây, việc quản lý sách theo thư mục chính là “cấu trúc dữ liệu” còn quy trình mượn, nhập sách chính là “thuật toán”.

Qua ví dụ trên các bạn có thể thấy: một cấu trúc dữ liệu tốt sẽ giúp ta quản lí dữ liệu một cách hiệu quả, chính xác hơn; một thuật toán tốt sẽ giúp xử lí dữ liệu nhanh chóng, rõ ràng hơn.

Vậy theo bạn, không học cấu trúc dữ liệu & Giải thuật thì có làm được phần mềm không và sản phẩm dạng nào sẽ bị ảnh hưởng bởi CTDL và GT trong thực tế?

Đôi khi trong quá trình học, chúng ta dễ dàng bỏ qua hoặc xem nhẹ việc áp dụng cấu trúc dữ liệu và giải thuật vì ít gây ảnh hưởng đến phần mềm của bạn. Tuy nhiên, để xử lý một bài toán trong thực tế, bạn nên lưu ý đến các vấn đề sau:

• Không gian lưu trữ 
• Thời gian thực hiện 
• Khả năng lập trình
• Yêu cầu chất lượng sản phẩm 

Chỉ sau khi phân tích yêu cầu bài toán một cách cẩn thận chúng ta mới có thể biết được cấu trúc dữ liệu và giải thuật nào là thích hợp nhất để giải quyết ứng dụng thực tế.

---

Cài đặt môi trường

Xuyên suốt khoá học này, mình sẽ sử dụng IDE chính là CodeBlocks bản 20.03, phiên bản g++ sẽ là phiên bản đi liền với CodeBlocks. Nào! chúng ta cùng tiến hành cài đặt.

Bước 1: Bạn truy cập vào trang chủ CodeBlocks theo đường dẫn bên dưới rồi chọn Download ở góc bên trái màn hình 

Code::Blocks - Code::Blocks (codeblocks.org)

 

Bước 2: Tiếp theo, bạn chọn Download the binary release

Bước 3: Chọn phiên bản codeblocks-20.03mingw-setup. Các bạn có thể chọn download qua FossHUB hoặc Sourceforge.net.

Bước 4: Các bạn giữ nguyên tất cả các lựa chọn mặc định và cài đặt CodeBlocks

Bước 5: Sau khi hoàn tất cài đặt, các bạn khởi động CodeBlocks. Chọn mục Settings > Compiler

Bước 6: Các bạn tích vào mục Have g++ follow the C++14 ISO C++ language standard

Bước 7: Các bạn chọn mục Toolchain executables. Nếu hiện đường dẫn trong mục Compiler's installation directory là được. Nếu không hiện các bạn chọn Auto-detect

Vậy là chúng ta đã hoàn thành việc cài đặt chương trình Codeblocks. Việc cài đặt này tương đối đơn giản, tuy nhiên nếu trong quá trình thực hiện bạn gặp bất kỳ khó khăn gì thì đừng ngần ngại để lại comment bên dưới để được hỗ trợ nhé!

---

Kết luận

Qua bài này chúng ta đã nắm được khái niệm cấu trúc dữ liệu và giải thuật, tầm quan trọng của chúng cũng như cài đặt môi trường.

Bài sau chúng ta sẽ tìm hiểu về Độ phức tạp thời gian BigO.

Cảm ơn các bạn đã theo dõi bài viết. Hãy để lại bình luận hoặc góp ý của mình để phát triển bài viết tốt hơn. Đừng quên “Luyện tập – Thử thách – Không ngại khó”.

---

Thảo luận

Nếu bạn có bất kỳ khó khăn hay thắc mắc gì về khóa học, đừng ngần ngại đặt câu hỏi trong phần BÌNH LUẬN bên dưới hoặc trong mục HỎI & ĐÁP trên thư viện Howkteam.com để nhận được sự hỗ trợ từ cộng đồng.