1. Tóm tắt môn học Môn học Cấu trúc dữ liệu và giải thuật gồm những nội dung chính sau: Tìm hiểu mối liên hệ giữa giữa cấu trúc dữ liệu và giải thuật. Cách đánh giá độ phức tạp của một giải thuật. Một số thuật toán tìm kiếm và sắp xếp phổ biến. […]
Cấu trúc dữ liệu và giải thuật
Mối liên hệ giữa cấu trúc dữ liệu và giải thuật
1. Cấu trúc dữ liệu là gì? 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 […]
Thuật toán tìm kiếm tuyến tính (Linear Search)
1. Phát biểu bài toán tìm kiếm Cho trước một danh sách gồm n phần tử. Bài toán tìm kiếm là bài toán tìm phần tử x có giá trị cho trước trong danh sách. Nếu phần tử đó tồn tại trong danh sách thì xuất vị trí của nó trong danh sách. Nếu phần […]
Thuật toán tìm kiếm nhị phân (Binary Search)
1. Thuật toán tìm kiếm nhị phân Tìm kiếm nhị phân được áp dụng trên các danh sách đã được sắp xếp theo thứ tự. Giả sử, có mảng a0,a1,a2,..,an-1 đã được sắp xếp theo thứ tự tăng dần. Các phần tử trong dãy có mối quan hệ: ai -1 ≤ ai ≤ ai+1. Ý […]
Thuật toán sắp xếp đổi chổ trực tiếp (Interchange Sort)
1. Giới thiệu bài toán sắp xếp Cho danh sách có n phần tử a0, a1, a2,…,an-1. Bài toán sắp xếp là quá trình xử lý các phần tử trong danh sách để đặt chúng theo một thứ tự thỏa mãn một số tiêu chuẩn nào đó dựa trên thông tin lưu tại mỗi phần […]
Thuật toán sắp xếp chọn trực tiếp (Selection Sort)
1. Ý tưởng thuật toán sắp xếp chọn trực tiếp Giả sử cần sắp xếp tăng dần một danh sách có n phần tử a0, a1, a2,…,an-1. Chọn phần tử nhỏ nhất trong n phần tử của danh sách ban đầu. Tìm và đổi vị trí phần tử nhỏ nhất với phần tử đầu tiên […]
Thuật toán sắp xếp nổi bọt (Bubble Sort)
1. Ý tưởng thuật toán sắp xếp nổi bọt Giả sử cần sắp xếp tăng dần một danh sách có n phần tử a0, a1, a2,…,an-1. Xuất phát từ cuối danh sách, đổi chỗ các cặp phần tử kế cận để đưa phần tử nhỏ hơn trong cặp phần tử đó về đúng vị trí […]
Thuật toán sắp xếp chèn trực tiếp (Insertion Sort)
1. Ý tưởng thuật toán sắp xếp chèn trực tiếp Giả sử cần sắp xếp tăng dần một danh sách có n phần tử a0, a1, a2,…,an-1. Giả sử đoạn a[0] trong danh sách đã được sắp xếp. Bắt đầu từ phần tử thứ i=1, tức là a1. Tìm cách chèn phần tử ai vào […]
Thuật toán sắp xếp Quick Sort
1. Ý tưởng thuật toán sắp xếp Quick Sort Giả sử cần sắp xếp tăng dần một danh sách có n phần tử a0, a1, a2,…,an-1. Đầu tiên chọn tuỳ ý phần tử x trong danh sách làm mốc (thường chọn là phần tử giữa danh sách). Ý tưởng của thuật toán Quick Sort phân […]
Danh sách liên kết (Linked List) là gì? Các loại danh sách liên kết
Bài này sẽ giới thiệu về cấu trúc dữ liệu danh sách liên kết (Linked List). Đây là một trong những cấu trúc dữ liệu kinh điển thường được nhắc đến. Linked List có nhiều loại khác nhau. Hãy cùng nhau tìm hiểu các đặc điểm của từng loại Linked List nào nhé! 1. Danh […]