Caấu Trúc Dữ Liệu Và Giải Thuật, Có Quan Trọng Với Dân Lập Trình Hay Không
Đề thi lớp 1
Lớp 2Lớp 2 - Kết nối tri thức
Lớp 2 - Chân trời sáng tạo
Lớp 2 - Cánh diều
Tài liệu tham khảo
Lớp 3Lớp 3 - Kết nối tri thức
Lớp 3 - Chân trời sáng tạo
Lớp 3 - Cánh diều
Tài liệu tham khảo
Lớp 4Sách giáo khoa
Sách/Vở bài tập
Đề thi
Lớp 5Sách giáo khoa
Sách/Vở bài tập
Đề thi
Lớp 6Lớp 6 - Kết nối tri thức
Lớp 6 - Chân trời sáng tạo
Lớp 6 - Cánh diều
Sách/Vở bài tập
Đề thi
Chuyên đề & Trắc nghiệm
Lớp 7Lớp 7 - Kết nối tri thức
Lớp 7 - Chân trời sáng tạo
Lớp 7 - Cánh diều
Sách/Vở bài tập
Đề thi
Chuyên đề & Trắc nghiệm
Lớp 8Sách giáo khoa
Sách/Vở bài tập
Đề thi
Chuyên đề & Trắc nghiệm
Lớp 9Sách giáo khoa
Sách/Vở bài tập
Đề thi
Chuyên đề & Trắc nghiệm
Lớp 10Lớp 10 - Kết nối tri thức
Lớp 10 - Chân trời sáng tạo
Lớp 10 - Cánh diều
Sách/Vở bài tập
Đề thi
Chuyên đề & Trắc nghiệm
Lớp 11Sách giáo khoa
Sách/Vở bài tập
Đề thi
Chuyên đề & Trắc nghiệm
Lớp 12Sách giáo khoa
Sách/Vở bài tập
Đề thi
Chuyên đề & Trắc nghiệm
ITNgữ pháp Tiếng Anh
Lập trình Java
Phát triển web
Lập trình C, C++, Python
Cơ sở dữ liệu
Cấu trúc dữ liệu và giải thuật
Một số khái niệm về Giải thuật Cấu trúc dữ liệu mảng (Array)Danh sách liên kết - Linked Lists
Ngăn xếp & Hàng đợi
Một số Giải thuật tìm kiếm
Một số Giải thuật sắp xếp
Cấu trúc dữ liệu đồ thị (Graph)Cấu trúc dữ liệu cây
Đệ qui (Recursion)Tài liệu tham khảo
Với các sinh viên chuyên nghành tin học thì cụm từ Cấu trúc dữ liệu (Data Structure) không còn là xa lạ. Đây là một môn học bắt buộc và sẽ là thực sự khó cho bất kỳ sinh viên nào nếu không có sự chuẩn bị kỹ lưỡng và dành cách tiếp cận tích cực cho môn học này. Vậy Cấu trúc dữ liệu là gì?
Cấu trúc dữ liệu là cách lưu trữ, tổ chức dữ liệu có thứ tự, có hệ thống để dữ liệu có thể được sử dụng một cách hiệu quả.
Dưới đây là danh sách các bài hướng dẫn trong loạt bài Cấu trúc dữ liệu và Giải thuật:
Mục lục Cấu trúc dữ liệu và giải thuật
Cấu trúc dữ liệu là gì?
Một số khái niệm về Giải thuật
Cấu trúc dữ liệu mảng (Array)
Danh sách liên kết - Linked List
Ngăn xếp & Hàng đợi
Một số Giải thuật tìm kiếm
Một số Giải thuật sắp xếp
Cấu trúc dữ liệu đồ thị (Graph)
Cấu trúc dữ liệu cây
Đệ qui (Recursion)
Loạt bài Cấu trúc dữ liệu và Giải thuật được viết dựa trên nguồn tài liệu nước ngoài cùng với tìm hiểu một số nguồn tài liệu khác cộng với sự hiểu biết của bản thân về Cấu trúc dữ liệu và giải thuật, do đó không tránh khỏi một số thiếu sót. Nếu bạn đọc hay độc giả có bất kỳ ý kiến đóng góp nào thì mong các bạn comment ngay phần dưới trang để bọn mình kịp thời sửa chữa để có thể cung cấp cho các bạn loạt bài hướng dẫn Cấu trúc dữ liệu và Giải thuật hoàn thiện nhất.
Bạn đang xem: Caấu trúc dữ liệu và giải thuật
VIETJACK xin chân thành cảm ơn và chúc các bạn học tốt !!!
Đã có app Viet
Jack trên điện thoại, giải bài tập SGK, SBT Soạn văn, Văn mẫu, Thi online, Bài giảng....miễn phí. Tải ngay ứng dụng trên Android và i
OS.
Follow fanpage của team https://www.facebook.com/vietjackteam/ hoặc facebook cá nhân Nguyễn Thanh Tuyền https://www.facebook.com/tuyen.vietjack để tiếp tục theo dõi các loạt bài mới nhất về Java,C,C++,Javascript,HTML,Python,Database,Mobile.... mới nhất của chúng tôi.
Đối với người học lập trình nói chung, cấu trúc dữ liệu và giải thuật là một trong những môn quan trọng và thường được dạy vào khoảng năm 2 và năm 3 đại học. Cảm giác của rất nhiều bạn nếu chưa tự tin là dễ bị nản ngay từ giai đoạn đầu và dần dần sẽ khó khăn hơn để bắt nhịp. Đồng thời, học tốt cấu trúc dữ liệu và giải thuật sẽ giúp cho các dòng code của mình trở nên tối ưu hơn.
Trong bài viết này, mình sẽ tổng hợp các kiến thức cơ bản cùng các kinh nghiệm của mình để giúp các bạn đi đúng hướng và cảm thấy sự thú vị của môn học này. Tất nhiên xung quanh ta vẫn có rất nhiều cao thủ, việc giới thiệu các kiến thức khó sẽ khiến mọi người bị ngợp nên trong phạm vi bài viết này, mình sẽ giới thiệu các vấn đề cơ bản (ít nhất là trong các bài kiểm tra trên trường). Hãy cùng tham khảo bài viết dưới đây:
Chuẩn bị những gì để học thuật toán?
Đầu tiên, để học được cấu trúc dữ liệu và giải thuật (Từ giờ đến cuối bài viết mình sẽ gọi tắt là thuật toán), các bạn cần phải có khả năng tự học cao. Phải có khả năng tìm kiếm tốt. Hầu hết mọi thứ cơ bản đều có trên google, trong khuôn khổ bài viết này mình sẽ đưa ra các vấn đề quan trọng, để các bạn follow theo keyword đó, tìm kiếm cho mình một nền tảng vững chắc.
Tiếp theo, các bạn cần chọn cho mình một ngôn ngữ lập trình. Theo mình thì C/C++ là ngôn ngữ nên được sử dụng khi học thuật toán vì:
Các kiểu dữ liệu trong ngôn ngữ C/C++ được định nghĩa rõ ràng, có kiểu truyền tham chiếu và tham trị khá hay.Tốc độ thực thi nhanh.Có nhiều sách, tài liệu tham khảo trên internet về cấu trúc dữ liệu và giải thuật được viết bằng C/C++.Tuy nhiên, nếu muốn hoặc có nền tảng các ngôn ngữ khác (java, python,...) thì mọi người cũng có thể sử dụng để học được vì theo công thức sau:
Cấu trúc dữ liệu + Giải thuật = Chương trìnhViệc viết một chương trình, giải một bài toán được kết hợp bởi 2 yếu tố, lựa chọn một cấu trúc dữ liệu phù hợp, sau đó tìm ra phương hướng kết hợp mọi thứ bằng giải thuật để có thể giải được bài toán. Do đó bạn có thể lựa chọn ngôn ngữ yêu thích và bắt đầu.
Các vấn đề cần quan tâm
Trong phần này mình sẽ nói về 7 vấn đề sau:
1. Độ phức tạp thuật toán (big O)
2. Sắp xếp và tìm kiếm nhị phân
3. Các phương pháp sinh
4. Đệ quy, quay lui
5. Cấu trúc dữ liệu stack, queue, dequeue
6. Quy hoạch động
7. Đồ thị.
Xem thêm: Giáo Trình Luật Thương Mại
1. Độ phức tạp thuật toán (big O)
Khái niệm độ phức tạp thuật toán có thể hiểu đơn giản là độ nhanh hay chậm của thuật toán. Chữ O là ký hiệu được sử dụng cho độ phức tạp thuật toán. Các loại độ phức tạp thuật toán cơ bản có thể kể đến là:
Trong đó, n là biểu thị kích thước đầu vào.
Lưu ý rằng nếu các bạn sử dụng 2 vòng lặp cùng cấp thì kích thước sẽ là 2*n, nhưng độ phức tạp thuật toán biểu diễn vẫn là O(n) vì mình chỉ lấy xấp xỉ thôi.
Và nếu bạn của bạn nói là 2 vòng lặp lồng nhau thì độ phức tạp sẽ là O(n^2) thì chúng ta đôi khi phải xem xét kỹ hơn thuật toán. Như ví dụ sau:
int i = 0;int n = 1000;while (i Nếu không để ý thì có thể sẽ nhầm hàm này là O(N^2), nhưng thực tế độ phức tạp của nó là O(n). Bởi vì nếu như i
2. Sắp xếp và tìm kiếm nhị phân
a. Sắp xếpĐể có thể hiểu rõ các thuật toán chạy như nào, các bạn nên tìm các source code trên mạng về và chạy thử, sau đó tự ngẫm xem các hàm của nó chạy như nào, các phép toán có tác dụng gì. Trong các thuật toán sắp xếp thì mình thấy có rất nhiều thuật toán như:
Bubble sortSelection sort
Insertion sort
Quick sort
Heap sort...
Ngoài ra còn rất nhiều thuật toán sắp xếp khác nữa, tùy vào điều kiện môn học trên trường yêu cầu gì thì mình học theo. Còn theo kinh nghiệm của mình thì để làm bài tập và code thuật toán thì học bubble sort (O(n)) và quick sort(~O(nlog(n))) thôi là đủ code được cả nghìn bài rồi. Đa số đều sử dụng quick sort hay dùng luôn hàm sort trong thư viện( Trong C++ là hàm sort trong thư viện algorithm có độ phức tạp ~ O(nlog(n))).
Còn việc giới thiệu nhiều thuật toán sort là tùy từng điều kiện cụ thể thì từng thuật toán có những ưu điểm và khuyết điểm riêng, ứng dụng trong thực tế. ví dụ nhưinsertion sorthay sắp xếp chènthường được sử dụng trong bảng xếp hạng,đâylà thuật toán sắp xếp xử lý chèn phần tử đang xét vào vị trí thích hợp của dãy số đã sắp xếp phía trước sao cho dãy số vẫn là dãy sắp xếp có thứ tự.
b. Tìm kiếm nhị phânÝ tưởng chính của tìm kiếm có thể biểu diễn đơn giản bằng một bài toán như sau:
Có n bạn được xếp thành một hàng theo thứ tự chiều cao tăng dần. Thầy giáo nhìn vào danh sách học sinh mà không có tên, chỉ có chiều cao, do đó cần tìm bạn có chiều cao là X trong hàng.
Bình thường thì cách làm đơn giản nhất là duyệt từ đầu hàng đến cuối hàng một cách lần lượt, khi đó chắc chắn sẽ tìm được bạn có chiều cao là X đó (độ phức tạp thuật toán sẽ là O(n)). Có một cách nhanh hơn để giải bài toán này, đó là ta sẽ nhìn vào người ở giữa dãy, nếu bạn đó có chiều cao bằng X thì ta sẽ tìm được luôn, còn nếu không thì ta sẽ biết chắc chắn người đó sẽ đứng ở nửa nào trong 2 nửa còn lại của hàng, qua đó lặp lại phương pháp trên đến khi tìm ra bạn đó, đây chính là ý tưởng chính của thuật toán tìm kiếm nhị phân với độ phức tạp chỉ còn O(nlog(n)).
3. Các phương pháp sinh
Có thể bạn chưa biết, gần như tất cả các bài toán đều có thể giải bằng cách duyệt trâu từng trường hợp. Do đó các phương pháp sinh là không thể thiếu khi học thuật toán. Có 4 phương pháp sinh mà các bạn nhất định phải học:
Sinh nhị phânSinh hoán vịSinh tổ hợp
Sinh chỉnh hợp
Các bạn có thể tìm hiểu các thuật toán trên và submit trong trang sau nhé:
https://www.spoj.com/PTIT/problems/basic/
4. Đệ quy, quay lui
Nói đơn giản thì đệ quy là hàm gọi lại chính nó, biểu diễn đối tượng được định nghĩa quy nạp theo các đối tượng con đồng dạng với nó. Sau đây là một số ví dụ của hàm sử dụng vòng lặp bình thường và hàm đệ quy:
int giaithua(int n) {int res=1;for (int i = 1; i Bây giờ hãy cùng mình xem qua một số cách viết hàm tính a^b ( với a khác 0). Tất nhiên với các bài toán giới hạn lớn thì a^b sẽ rất lớn, do đó mình sẽ lấy phần dư cho mod nhé.
// dpt O(n)long long cal_pow(int a, int b, int mod) {long long res=1;for (int i = 1; i > 1, mod);}Qua đó các bạn có thể thấy các hàm đệ quy rất thú vị. Các phương pháp sinh ở trên, ngoài cách code chay sinh từng cấu hình thì cũng có thể sử dụng đệ quy để viết một cách gọn gàng hơn. Thuật toán quay lui cũng dựa trên tư tưởng của hàm đệ quy như trên, suy cho cùng các thuật toán sinh được dùng để duyệt hết các cấu hình có thể, trong một số bài toán thì có thể sử dụng nhánh cận, cài cắm các đoạn xử lý loại bỏ các trường hợp không cần thiết để chương trình được tối ưu hơn.
Tạm kết
Mình tạm dừng phần 1 ở đây, trong bài viết sau mình sẽ nói tiếp các vấn đề cần quan tâm khác, các nguồn tài liệu và trang web mình hay dùng trong quá trình học. Các bạn đón xem nhé :))
