Cấu trúc dữ liệu và giải thuật là một trong những môn học cơ bản của sinh viên ngành Công nghệ thông tin. Các cấu trúc dữ liệu và các giải thuật được xem như là 2 yếu tố quan trọng nhất trong lập trình, đúng như câu nói nổi tiếng của Niklaus Wirth:
Nắm vững các cấu trúc dữ liệu và các giải thuật là cơ sở để sinh viên tiếp cận với việc thiết kế và xây dựng phần mềm cũng như sử dụng các công cụ lập trình hiện đại. Cấu trúc dữ liệu [Data Structure] là cách lập trình để lưu trữ dữ liệu để dữ liệu có thể được sử dụng một cách hiệu quả. Hầu hết mọi ứng dụng doanh nghiệp đều sử dụng nhiều kiểu cấu trúc dữ liệu khác nhau theo cách này hay cách khác, vì nó mang lại nhiều lợi ích rất lớn không chỉ cho việc lưu trữ dữ liệu.Chương trình = Cấu trúc dữ liệu + Giải thuật [Programs = Data Structures + Algorithms].
Nội dung chính
- 2. Tại sao phải học cấu trúc dữ liệu và giải thuật?
- 3. Ứng dụng của nó
- 4. Tài liệu và lộ trình học
- Cấu trúc dữ liệu là gì?
- Một số khái niệm về Giải thuật
- Video liên quan
Thuật toán [Algorithms] là một thủ tục từng bước, xác định một tập hợp các lệnh được thực hiện theo một thứ tự nhất định để có được đầu ra mong muốn. Các thuật toán thường được tạo độc lập với các ngôn ngữ cơ bản, tức là một thuật toán có thể được triển khai bằng nhiều ngôn ngữ lập trình[C/C++, Java, Python, PHP…], với series tự học này sẽ cung cấp cho các bạn các ví dụ, code mẫu trên nhiều ngôn ngữ khác nhau…
Cấu trúc dữ liệu và giải thuật [CTDL & GT] là sự kết hợp và áp dụng một hoặc nhiều cấu trúc dữ liệu nào đó vào một hoặc nhiều thuật toán nào đó để có được đầu ra mong muốn một cách tối ưu và tốt nhất khi dữ liệu có số.
2. Tại sao phải học cấu trúc dữ liệu và giải thuật?
Khi các ứng dụng ngày càng phức tạp và nhiều dữ liệu, có ba vấn đề phổ biến mà các ứng dụng phải đối mặt ngay bây giờ.Tìm kiếm dữ liệu – Tìm kiếm một sản phẩm nào đó trong cả tỉ tỉ dữ liệu càng ngày càng lớn. Khi dữ liệu phát triển, tìm kiếm sẽ trở nên chậm hơn. Vì vậy cần CTDL & GT để nâng cao hiệu suất hơn.
Tốc độ bộ xử lý – Tốc độ bộ xử lý mặc dù rất cao nhưng sẽ bị giới hạn nếu dữ liệu tăng lên đến hàng tỷ dữ liệu.
Nhiều yêu cầu – Vì hàng nghìn người dùng có thể tìm kiếm dữ liệu đồng thời trên một máy chủ web, ngay cả máy chủ nhanh cũng bị lỗi trong khi tìm kiếm dữ liệu. Để giải quyết các vấn đề nêu trên, cấu trúc dữ liệu ra đời để giải cứu. Dữ liệu có thể được tổ chức theo cấu trúc dữ liệu theo cách mà tất cả các mục có thể không được yêu cầu tìm kiếm và dữ liệu cần thiết có thể được tìm kiếm gần như ngay lập tức.
Hầu hết các chương trình, ứng dụng hiện nay đều phải có dữ liệu và xử lý chúng, vì vậy CTDL> rất quan trọng trong cả học tập và đi làm.
3. Ứng dụng của nó
Từ quan điểm cấu trúc dữ liệu, sau đây là một số loại thuật toán quan trọng mà chúng ta thường dùng trong thực tế như:Tìm kiếm – Thuật toán tìm kiếm một mục trong cấu trúc dữ liệu.
Sắp xếp – Thuật toán sắp xếp các mục theo một thứ tự nhất định.
Chèn – Thuật toán chèn mục trong cấu trúc dữ liệu.
Cập nhật – Thuật toán cập nhật một mục hiện có trong cấu trúc dữ liệu.
Xóa – Thuật toán xóa một mục hiện có khỏi cấu trúc dữ liệu.
Các vấn đề sau có thể được giải quyết bằng cách sử dụng Cấu trúc dữ liệu:
- Chuỗi số Fibonacci - Vấn đề Knapsack - Tháp Hà Nội - Tất cả các cặp đường đi ngắn nhất của Floyd-Warshall - Con đường ngắn nhất của Dijkstra- Lập kế hoạch dự án
4. Tài liệu và lộ trình học
Yêu cầu đầu tiên bản phải thành thạo ít nhất một trong các ngôn ngữ lập trình sau: C/C++ Java, Python, C#, PHP,…Để bạn có thể thực hành cấu trúc dữ liệu và giải thuật để từ đó bạn sẽ hiểu, nhớ lâu hơn về chúng.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ì?
- Cấu trúc dữ liệu là gì ?
- Cài đặt môi trường
Một số khái niệm về Giải thuật
Quảng cáo
- Cấu trúc dữ liệu mảng [Array]
- Cấu trúc dữ liệu ngăn xếp - Stack
- Cấu trúc dữ liệu hàng đợi - Queue
Quảng cáo
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.
VIETJACK xin chân thành cảm ơn và chúc các bạn học tốt !!!
Đã có app VietJack 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à iOS.
Follow fanpage của team //www.facebook.com/vietjackteam/ hoặc facebook cá nhân Nguyễn Thanh Tuyền //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.
Cấu trúc dữ liệu [data structure] là cách thức tổ chức dữ liệu sao cho phù hợp với bài toán và có thể dùng máy tính để xử lý các dữ liệu đó một cách hiệu quả.
Các tiêu chuẩn của một cấu trúc dữ liệu:
- Phải biểu diễn đầy đủ thông tin
- Phải phù hợp với các thao tác xử lý
- Phù hợp với điều kiện cho phép của ngôn ngữ lập trình
- Tiết kiệm được tài nguyên hệ thống
Có nhiều loại cấu trúc dữ liệu nhưng có thể chia thành 2 loại: cấu trúc dữ liệu tuyến tính [linear] và phi tuyến tính [non-linear].
Các loại cấu trúc dữ liệuGiải thuật là tên gọi khác của thuật toán. Thuật toán [algorithm] là tập hợp hữu hạn các thao tác được định nghĩa rõ ràng nhằm giải quyết một bài toán cụ thể nào đó.
Một thuật toán phải đảm bảo 5 tính chất sau:
– Tính chính xác: quá trình tính toán hay các thao tác máy tính thực hiện là chính xác.
– Tính rõ ràng: các câu lệnh minh bạch được sắp xếp theo thứ tự nhất định.
– Tính khách quan: được viết bởi nhiều người trên máy tính nhưng kết quả phải như nhau.
– Tính phổ dụng: có thể áp dụng cho một lớp các bài toán có đầu vào tương tự nhau.
– Tính kết thúc: hữu hạn các bước tính toán.
Các bạn có thể đọc thêm bài Thuật toán là gì? Các phương pháp biểu diễn thuật toán để hiểu rõ hơn về thuật toán.
Thuật toán và cấu trúc dữ liệu có mối quan hệ chặt chẽ với nhau. Cuốn sách “Algorithms + Data Structures = Programs” là một trong những cuốn sách kinh điển của nhà khoa học máy tính Niklaus Wirth viết vào năm 1976 nói lên điều đó.
Thật vậy, bất kỳ một chương trình nào cũng cần có dữ liệu để tính toán, xử lý. Nhiệm vụ tính toán, xử lý sẽ được giao cho thuật toán. Để chương trình hoạt động tốt, ổn định thì thuật toán phải xử lý tốt và chính xác trên dữ liệu. Do đó, những dữ liệu này cần được lưu trữ, tổ chức một cách hợp lý với thuật toán.
Rõ ràng, cấu trúc dữ liệu đóng vai trò quan trọng trong việc kết hợp và đưa ra cách giải quyết bài toán. Cấu trúc dữ liệu cũng hỗ trợ cho các thuật toán thao tác, xử lý hiệu quả hơn.
Với một bài toán, chúng ta có thể có nhiều thuật toán để giải quyết bài toán đó. Nhưng một câu hỏi đặt ra là thuật toán nào tốt hơn thuật toán nào? Để trả lời câu hỏi này, cần xem xét thế nào là một thuật toán hiệu quả?
Một thuật toán hiệu quả thì chi phí sử dụng tài nguyên như bộ nhớ, thời gian sử dụng CPU,… thấp. Người ta thường phân tích độ phức tạp thuật toán để đánh giá sự hiệu quả của thuật toán. Có hai phương pháp đánh giá độ phức tạp của thuật toán là:
- Phương pháp thực nghiệm
- Phương pháp xấp xỉ toán học
Phương pháp thực nghiệm
Cài thuật toán rồi chọn các bộ dữ liệu thử nghiệm. Chạy thuật toán rồi thống kê các thông số [thời gian chạy thuật toán, dung lượng bộ nhớ,…] khi chạy thuật toán với các bộ dữ liệu đó.
Ưu điểm: Dễ thực hiện.
Nhược điểm:
- Chịu sự hạn chế của ngôn ngữ lập trình
- Ảnh hưởng bởi trình độ của người lập trình
- Chọn được các bộ dữ liệu thử đặc trưng cho tất cả tập các dữ liệu đầu vào của thuật toán thì khó khăn và tốn nhiều chi phí
- Phụ thuộc vào phần cứng
Trong nghiên cứu khoa học, phương pháp này được sử dụng rất nhiều.
Phương pháp xấp xỉ toán học
Đánh giá độ phức tạp thuật toán theo hướng xấp xỉ tiệm cận qua các khái niệm O[]. Hiểu đơn giản là xấp xỉ số lần thực hiện các phép toán của thuật toán. Số lần thực hiện phép toán càng ít thì thuật toán càng ít phức tạp [càng tốt] và ngược lại.
Ưu điểm: Ít phụ thuộc ngôn ngữ lập trình cũng như phần cứng hơn.
Nhược điểm: Cách tính phức tạp, cần có kiến thức toán học.
Người ta sử dụng các ký hiệu BigO bên dưới để đánh giá độ phức tạp thuật toán theo độ phức tạp tăng dần.
- Hằng số: O[c]
- logN: O[logN]
- N: O[N]
- NlogN: O[NlogN]
- N2: O[N2]
- N3: O[N3]
- 2N: O[2N]
- N!: O[N!]