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

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 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.

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 :

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 thông dụng 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 :

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 ax2 + bx + c = 0

Đừng quên để lại đáp án và luận bà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 tiến 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ị tác động ảnh hưở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 

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à tất cả chúng ta đã triển khai xong việc thiết lập chương trình Codeblocks. Việc setup này tương đối đơn thuần, tuy nhiên nếu trong quy trình thực thi 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 môi trường tự nhiên .

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 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://vh2.com.vn
Category : Bảo Mật