Chương 1:
TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU
VÀ GIẢI THUẬT
 

1. Tổng quan về cấu trúc dữ liệu và giải thuật
1.1. Cấu trúc dữ liệu (Data Structure)
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à hai khái niệm nền tảng hình thành nên một
cấu trúc dữ liệu:
- Interface: Mỗi cấu trúc dữ liệu có một Interface. Interface
biểu diễn một tập hợp các phép tính mà một cấu trúc dữ liệu
hỗ trợ.
- Implementation (có thể hiểu là sự triển khai): Cung cấp sự
biểu diễn nội bộ của một cấu trúc dữ liệu.

 Đặc điểm của một Cấu trúc dữ liệu:
• Chính xác: Sự triển khai của Cấu trúc dữ liệu nên
triển khai Interface của nó một cách chính xác.
• Độ phức tạp về thời gian (Time Complexity): Thời
gian chạy hoặc thời gian thực thi của các phép tính
của cấu trúc dữ liệu phải là nhỏ nhất có thể.
• Độ phức tạp về bộ nhớ (Space Complexity): Sự sử
dụng bộ nhớ của mỗi phép tính của cấu trúc dữ liệu
nên là nhỏ nhất có thể.

Tại sao Cấu trúc dữ liệu là cần thiết ?
Hiện nay, có 3 vấn đề lớn mà mỗi lập trình viên phải đối mặt:
•Tìm kiếm dữ liệu: Giả sử có 1 triệu hàng hóa được lưu giữ
vào trong kho hàng hóa. Mỗi khi tìm kiếm, sẽ phải tìm kiếm 1
hàng hóa trong 1 triệu hàng hóa. Khi dữ liệu tăng lên thì việc
tìm kiếm sẽ càng trở lên chậm và tốn kém hơn.
•Tốc độ bộ vi xử lý: Mặc dù bộ vi xử lý có tốc độ rất cao, tuy
nhiên nó cũng có giới hạn và khi lượng dữ liệu lên tới hàng tỉ
bản ghi thì tốc độ xử lý cũng sẽ không còn được nhanh nữa.

• Đa yêu cầu: Khi hàng nghìn người dùng cùng thực hiện
một phép tính tìm kiếm trên một Web Server thì cho dù
Web Server đó có nhanh đến mấy thì việc phải xử lý hàng
nghìn phép tính cùng một lúc là thực sự rất khó.
 Để xử lý các vấn đề trên, các cấu trúc dữ liệu là một giải
pháp tuyệt vời. Dữ liệu có thể được tổ chức trong cấu trúc
dữ liệu theo một cách để khi thực hiện tìm kiếm một phần
tử nào đó thì dữ liệu yêu cầu sẽ được tìm thấy ngay lập
tức.

1.2. Giải thuật (Algorithms)
Giải thuật Algorithms (hay còn gọi là thuật toán): là một
tập hợp hữu hạn các chỉ thị được thực thi theo một thứ tự
nào đó để thu được kết quả mong muốn.
Một số giải thuật quan trọng:
•Giải thuật Tìm kiếm: Giải thuật để tìm kiếm một phần tử
trong một cấu trúc dữ liệu.
•Giải thuật Sắp xếp: Giải thuật để sắp xếp các phần tử theo
thứ tự nào đó.
•Giải thuật Chèn: Giải thuật để chèn phần tử vào trong
một cấu trúc dữ liệu.

 Đặc điểm của Giải thuật
• Tính xác định: Giải thuật nên rõ ràng và không mơ hồ.
Mỗi một giai đoạn (hay mỗi bước) nên rõ ràng và chỉ
mang một mục đích nhất định.
• Dữ liệu đầu vào xác định: Một giải thuật nên có 0 hoặc
nhiều hơn dữ liệu đầu vào đã xác định.
• Kết quả đầu ra: Một giải thuật nên có một hoặc nhiều
dữ liệu đầu ra đã xác định, và nên kết nối với kiểu kết
quả bạn mong muốn.
• Tính dừng: Các giải thuật phải kết thúc sau một số hữu
hạn các bước

 Đặc điểm của Giải thuật
• Tính hiệu quả: Một giải thuật nên là có thể thi hành
được với các nguồn có sẵn, tức là có khả năng giải quyết
hiệu quả vấn đề trong điều kiện thời gian và tài nguyên
cho phép.
• Tính phổ biến: Một giải thuật có tính phổ biến nếu giải
thuật này có thể giải quyết được một lớp các vấn đề
tương tự.
• Độc lập: Một giải thuật nên có các chỉ thị độc lập với
bất kỳ phần code lập trình nào.

 Cách viết một giải thuật?
Viết các giải thuật theo cách thức là theo từng bước một
Ví dụ: Thiết kế một giải thuật để cộng hai số và hiển thị kết
quả.

Hoặc viết:

2. Phân tích giải thuật
* Một giải thuật hiệu quả:
Chi phí cần sử dụng tài nguyên thấp (bộ nhớ, thời gian sử
dụng CPU, …)
* Độ phức tạp của giải thuật:
•Nhân tố thời gian: Thời gian được đánh giá bằng việc
tính số phép tính chính (chẳng hạn như các phép so sánh
trong thuật toán sắp xếp).
•Nhân tố bộ nhớ: Lượng bộ nhớ được đánh giá bằng việc
tính lượng bộ nhớ tối đa mà giải thuật cần sử dụng.

 Mối quan hệ giữa cấu trúc dữ liệu và giải thuật
• Giải thuật = phép xử lý.
• Đối tượng của giải thuật chính là dữ liệu được tổ chức
thành các cấu trúc.
• Cấu trúc dữ liệu và giải thuật gắn chặt với nhau:
Cấu trúc dữ liệu + Giải thuật = Chương trình
• Nếu thay đổi cấu trúc dữ liệu thì giải thuật cũng sẽ thay
đổi theo.