TÀI LIỆU Cấu trúc dữ liệu và giải thuật pdf

Yopovn · 3/4/24

TÀI LIỆU Cấu trúc dữ liệu và giải thuật pdf được soạn dưới dạng file pdf gồm 144 trang. Các bạn xem và tải về ở dưới.
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT

(Dùng cho sinh viên hệ đào tạo đại học từ xa)

Lưu hành nội bộ

HÀ NỘI - 2007

LỜI NÓI ĐẦU

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: Chương trình = Cấu trúc dữ liệu +
Giải thuật (Programs = Data Structures + Algorithms). 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 có thể được xem như là 1 phương pháp lưu trữ dữ liệu trong máy tính
nhằm sử dụng một cách có hiệu quả các dữ liệu này. Và để sử dụng các dữ liệu một cách hiệu quả
thì cần phải có các thuật toán áp dụng trên các dữ liệu đó. Do vậy, cấu trúc dữ liệu và giải thuật là
2 yếu tố không thể tách rời và có những liên quan chặt chẽ với nhau. Việc lựa chọn một cấu trúc
dữ liệu có thể sẽ ảnh hưởng lớn tới việc lựa chọn áp dụng giải thuật nào.
Tài liệu “Cấu trúc dữ liệu và giải thuật” bao gồm 7 chương, trình bày về các cấu trúc dữ liệu
và các giải thuật cơ bản nhất trong tin học.
Chương 1 trình bày về phân tích và thiết kế thuật toán. Đầu tiên là cách phân tích 1 vấn đề,
từ thực tiễn cho tới chương trình, cách thiết kế một giải pháp cho vấn đề theo cách giải quyết bằng
máy tính. Tiếp theo, các phương pháp phân tích, đánh giá độ phức tạp và thời gian thực hiện giải
thuật cũng được xem xét trong chương. Chương 2 trình bày về đệ qui, một khái niệm rất cơ bản
trong toán học và khoa học máy tính. Việc sử dụng đệ qui có thể xây dựng được những chương
trình giải quyết được các vấn đề rất phức tạp chỉ bằng một số ít câu lệnh, đặc biệt là các vấn đề
mang bản chất đệ qui.
Chương 3, 4, 5, 6 trình bày về các cấu trúc dữ liệu được sử dụng rất thông dụng như mảng
và danh sách liên kết, ngăn xếp và hàng đợi, cây, đồ thị. Đó là các cấu trúc dữ liệu cũng rất gần
gũi với các cấu trúc trong thực tiễn. Chương 7 trình bày về các thuật toán sắp xếp và tìm kiếm.
Các thuật toán này cùng với các kỹ thuật được sử dụng trong đó được coi là các kỹ thuật cơ sở
cho lập trình máy tính. Các thuật toán được xem xét bao gồm các lớp thuật toán đơn giản và cả
các thuật toán cài đặt phức tạp nhưng có thời gian thực hiện tối ưu.
Cuối mỗi phần đều có các câu hỏi và bài tập để sinh viên ôn luyện và tự kiểm tra kiến thức
của mình. Cuối tài liệu có các phụ lục hướng dẫn trả lời câu hỏi, mã nguồn tham khảo và tài liệu
tham khảo.
Về nguyên tắc, các cấu trúc dữ liệu và các giải thuật có thể được biểu diễn và cài đặt bằng
bất cứ ngôn ngữ lập trình hiện đại nào. Tuy nhiên, để có được các phân tích sâu sắc hơn và có kết
quả thực tế hơn, tác giả đã sử dụng ngôn ngữ lập trình C để minh hoạ cho các cấu trúc dữ liệu và
thuật toán. Do vậy, ngoài các kiến thức cơ bản về tin học, người đọc cần có kiến thức về ngôn ngữ
lập trình C.
Cuối cùng, mặc dù đã hết sức cố gắng nhưng chắc chắn không tránh khỏi các thiếu sót. Tác
giả rất mong nhận được sự góp ý của bạn đọc và đồng nghiệp để tài liệu được hoàn thiện hơn.

Hà Nội, tháng 10/2007

3

CHƯƠNG 1

PHÂN TÍCH VÀ THIẾT KẾ GIẢI THUẬT

Chương 1 trình bày các khái niệm về giải thuật và phương pháp tinh chỉnh từng bước
chương trình được thể hiện qua ngôn ngữ diễn đạt giải thuật. Chương này cũng nêu phương pháp
phân tích và đánh giá một thuật toán, các khái niệm liên quan đến việc tính toán thời gian thực
hiện chương trình.
Trong mỗi phần đều có các minh hoạ cụ thể. Phần đầu đưa ra ví dụ về bài toán nút giao
thông và phương pháp giải quyết bài toán từ phân tích vấn đề cho đến thiết kế giải thuật, tinh
chỉnh từng bước cho tới mức cụ thể hơn. Phần 2 đưa ra một ví dụ về phân tích và tính toán thời
gian thực hiện giải thuật sắp xếp nổi bọt.
Để học tốt chương này, sinh viên cần nắm vững phần lý thuyết và tìm các ví dụ tương tự để
thực hành phân tích, thiết kế, và đánh giá giải thuật.
1.1 GIẢI THUẬT VÀ NGÔN NGỮ DIỄN ĐẠT GIẢI THUẬT
1.1.1 Giải thuật
Trong thực tế, khi gặp phải một vấn đề cần phải giải quyết, ta cần phải đưa ra 1 phương
pháp để giải quyết vấn đề đó. Khi muốn giải quyết vấn đề bằng cách sử dụng máy tính, ta cần
phải đưa ra 1 giải pháp phù hợp với việc thực thi bằng các chương trình máy tính. Thuật ngữ
“thuật toán” được dùng để chỉ các giải pháp như vậy.
Thuật toán có thể được định nghĩa như sau:
Thuật toán là một chuỗi hữu hạn các lệnh. Mỗi lệnh có một ngữ nghĩa rõ ràng và có thể
được thực hiện với một lượng hữu hạn tài nguyên trong một khoảng hữu hạn thời gian.
Chẳng hạn lệnh x = y + z là một lệnh có các tính chất trên.
Trong một thuật toán, một lệnh có thể lặp đi lặp lại nhiều lần, tuy nhiên đối với bất kỳ bộ dữ
liệu đầu vào nào, thuật toán phải kết thúc sau khi thực thi một số hữu hạn lệnh.
Như đã nói ở trên, mỗi lệnh trong thuật toán phải có ngữ nghĩa rõ ràng và có thể được thực
thi trong một khoảng thời gian hữu hạn. Tuy nhiên, đôi khi một lệnh có ngữ nghĩa rõ ràng đối với
người này nhưng lại không rõ ràng đối với người khác. Ngoài ra, thường rất khó để chứng minh
một lệnh có thể được thực hiện trong 1 khoảng hữu hạn thời gian. Thậm chí, kể cả khi biết rõ ngữ
nghĩa của các lệnh, cũng khó để có thể chứng minh là với bất kỳ bộ dữ liệu đầu vào nào, thuật
toán sẽ dừng.
Tiếp theo, chúng ta sẽ xem xét một ví dụ về xây dựng thuật toán cho bài toán đèn giao
thông:
Giả sử người ta cần thiết kế một hệ thống đèn cho một nút giao thông có nhiều đường giao
nhau phức tạp. Để xây dựng tập các trạng thái của các đèn giao thông, ta cần phải xây dựng một
chương trình có đầu vào là tập các ngã rẽ được phép tại nút giao thông (lối đi thẳng cũng được
xem như là 1 ngã rẽ) và chia tập này thành 1 số ít nhất các nhóm, sao cho tất cả các ngã rẽ trong
nhóm có thể được đi cùng lúc mà không xảy ra tranh chấp. Sau đó, chúng ta sẽ gắn trạng thái của
các đèn giao thông với mỗi nhóm vừa được phân chia. Với cách phân chia có số nhóm ít nhất, ta
sẽ xây dựng được 1 hệ thống đèn giao thông có ít trạng thái nhất.

4
Chẳng hạn, ta xem xét bài toán trên với nút giao thông được cho như trong hình 1.1 ở
dưới. Trong nút giao thông trên, C và E là các đường 1 chiều, các đường còn lại là 2 chiều. Có tất
cả 13 ngã rẽ tại nút giao thông này. Một số ngã rẽ có thể được đi đồng thời, chẳng hạn các ngã rẽ
AB (từ A rẽ sang B) và EC. Một số ngã rẽ thì không được đi đồng thời (gây ra các tuyến giao
thông xung đột nhau), chẳng hạn AD và EB. Hệ thống đèn tại nút giao thông phải hoạt động sao
cho các ngã rẽ xung đột (chẳng hạn AD và EB) không được cho phép đi tại cùng một thời điểm,
trong khi các ngã rẽ không xung đột thì có thể được đi tại cũng 1 thời điểm.

Hình 1.1 Nút giao thông

Chúng ta có thể mô hình hóa vấn đề này bằng một cấu trúc toán học gọi là đồ thị (sẽ được
trình bày chi tiết ở chương 5). Đồ thị là một cấu trúc bao gồm 1 tập các điểm gọi là đỉnh và một
tập các đường nối các điểm, gọi là các cạnh. Vấn đề nút giao thông có thể được mô hình hóa bằng
một đồ thị, trong đó các ngã rẽ là các đỉnh, và có một cạnh nối 2 đỉnh biểu thị rằng 2 ngã rẽ đó
không thể đi đồng thời. Khi đó, đồ thị của nút giao thông ở hình 1.1 có thể được biểu diễn như ở
hình 1.2.

Hình 1.2 Đồ thị ngã rẽ
B A

C

D E

AB AC AD

BA BC BD

DA DB DC

EA EB EC ED

5
Ngoài cách biểu diễn trên, đồ thị còn có thể được biểu diễn thông qua 1