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é!
Tóm Tắt
Nội dung
Trong bài học kinh nghiệm này tất cả chúng ta sẽ cùng nhau khám phá 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.
Bạn đang đọc: Cấu trúc dữ liệu & giải thuật là gì? | How Kteam
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 hoàn toàn có thể thuận tiện tìm thấy định nghĩa triết lý cũng như ưu điểm yếu ké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 chuyên sâu 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 : những thành phần 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 : những thành phần được tàng trữ theo nguyên tắc LIFO. Nghĩa là, thành phần sau cuối được tàng trữ trong ngăn xếp sẽ bị xóa tiên phong . 3. Hàng đợi – Queue : Cấu trúc dữ liệu hàng đợi hoạt động giải trí theo nguyên tắc FIFO trong đó thành phần tiên phong được tàng trữ trong hàng đợi sẽ bị vô hiệu trước . 4. Danh sách link – Linked List : những thành phần dữ liệu được liên kết trải qua một loạt những nút. Và, mỗi nút chứa những mục dữ liệu và địa chỉ của nút tiếp theo . |
Ví dụ :
|
Vậy như thế nào là một cấu trúc dữ liệu hiệu suất cao ?
- 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 những hướng dẫn được xác lập rõ để xử lý một yếu tố đơn cử .
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ố những thuật toán phổ cập 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 hiển thị
- 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
Khá đơn thuần phải không nào ? Bạn hoàn toàn có thể củng cố bằng cách tự mình viết ra thuật toán và vẽ flowchart tương ứng cho những nhu yếu sau :
- 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.
- Tính và hiển thị giai thừa một số n nhập từ bàn phím.
- Giải phương trình ax2 + bx + c = 0
Đừng quên để lại đáp án và bàn luận với hội đồng ở phần phản hồi 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 trị của một thư viện. Chúng ta để sách bộn bề ở 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ì tất cả 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 quá trình rõ ràng cho việc cho mượn sách hoặc nhập sách vào kho để quản trị 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 giải trí không hiệu suất cao .
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 và Giải thuật thì có làm được ứng dụng không và loại sản phẩm dạng nào sẽ bị ảnh hưởng tác động bởi CTDL và GT trong trong thực tiễn ?
Đôi khi trong quy trình học, tất cả chúng ta thuận tiện bỏ lỡ hoặc xem nhẹ việc vận dụng cấu trúc dữ liệu và giải thuật vì ít gây ảnh hưởng tác động đến ứng dụng của bạn. Tuy nhiên, để giải quyết và xử lý một bài toán trong trong thực tiễn, bạn nên quan tâm đến những yếu tố 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 nghiên cứu và phân tích nhu yếu bài toán một cách cẩn trọng tất cả chúng ta mới hoàn toàn 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 để xử lý ứng dụng thực tiễn .
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
.jpg)
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.
.jpg)
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à tất cả chúng ta đã triển khai xong việc thiết lập chương trình Codeblocks. Việc thiết lập này tương đối đơn thuần, tuy nhiên nếu trong quy trình triển khai bạn gặp bất kể khó khăn vất vả gì thì đừng ngần ngại để lại comment bên dưới để được tương hỗ nhé !
Kết luận
Qua bài này tất cả 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ư thiết lập thiên nhiên và 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ó”.
Xem thêm: Trí Tuệ Nhân Tạo AI là gì?
Thảo luận
Nếu bạn có bất kể khó khăn vất vả hay vướng mắc gì về khóa học, đừng ngần ngại đặt câu hỏi trong phần bên dưới hoặc trong mục HỎI và ĐÁP trên thư viện Howkteam. com để nhận được sự tương hỗ từ hội đồng .
Source: https://final-blade.com
Category : Kiến thức Internet
