Giáo trình môn học Cấu trúc dữ liệu và giải thuật
Giáo trình Cấu trúc dữ liệu và giải thuật
Trang 2 / 92
MỤC LỤC
ĐỀ MỤC
TRANG
MỤC LỤC.............................................................................................................2
2.Các kiểu dữ liệu cơ bản............................................................................18
3.Kiểu bản ghi, kiểu con trỏ ........................................................................19
3.1. Kiểu bản ghi .................................................................................19
3.2. Kiểu con trỏ..................................................................................19
Bài tập thực hành của học viên ...................................................................20
4.Các kiểu dữ liệu trừu tượng......................................................................20
5.Các cấu trúc lưu trữ..................................................................................21
5.1. Mảng.............................................................................................21
Bài tập thực hành của học viên ...................................................................25
Bài tập thực hành của học viên ...................................................................28
Gợi ý làm bài...............................................................................................28
1.Khái niệm đệ quy .....................................................................................29
2.1. Giải thuật đệ qui ...........................................................................29
3.Các bài toán đệ quy căn bản.....................................................................30
Bài tập thực hành của học viên ...................................................................31
Gợi ý làm bài...............................................................................................32
CHƯƠNG 3: DANH SÁCH ...............................................................................34
Giáo trình Cấu trúc dữ liệu và giải thuật
Trang 3 / 92
3.1. Khởi tạo danh sách rỗng...............................................................39
3.2. Kiểm tra danh sách rỗng...............................................................39
4. Danh sách đặc biệt...................................................................................42
4.1. Ngăn xếp ......................................................................................42
4.2. Hàng đợi.......................................................................................47
Bài tập thực hành của học viên ...................................................................51
Gợi ý làm bài...............................................................................................52
1.Định nghĩa bài toán sắp xếp .....................................................................53
2.2.Giải thuật.......................................................................................54
Giáo trình Cấu trúc dữ liệu và giải thuật
Trang 4 / 92
5.2.Giải thuật.......................................................................................59
6.2.Giải thuật.......................................................................................60
Bài tập thực hành của học viên ...................................................................63
CHƯƠNG 5: TÌM KIẾM....................................................................................65
1.Tìm kiếm tuyến tính .................................................................................65
1.2.Giải thuật.......................................................................................65
2.Tìm kiếm nhị phân ...................................................................................67
2.2.Giải thuật.......................................................................................67
Bài tập thực hành của học viên ...................................................................69
CHƯƠNG 6: CÂY..............................................................................................70
3. Bài toán duyệt cây nhị phân ....................................................................77
Bài tập thực hành của học viên ...................................................................79
Giáo trình Cấu trúc dữ liệu và giải thuật
Trang 5 / 92
Giáo trình Cấu trúc dữ liệu và giải thuật
Trang 6 / 92
MÔN HỌC CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
Mã môn học: MH17
* VỊ TRÍ, TÍNH CHẤT, Ý NGHĨA VÀ VAI TRÒ CỦA MÔN HỌC
Vị trí: Môn học được bố trí sau khi sinh viên học xong môn học, mô đun: Lập
trình căn bản, Cơ sở dữ liệu.
Tính chất: Là môn học chuyên ngành bắt buộc
Ý nghĩa và vai trò: Đây là môn học cơ sở ngành của các ngành liên quan đến
công nghệ thông tin, cung cấp cho sinh viên các kiến thức cơ bản về cấu trúc
dữ liệu và giải thuật để làm nền tản cho việc lập trình giải quyết các vấn đề
cần thiết.
* MỤC TIÊU MÔN HỌC:
Mô tả được các khái niệm về kiểu dữ liệu trừu tương(danh sách, cây, đồ thị),
kiểu dữ liệu, cấu trúc dữ liệu và giải thuật.
Biết được các phép toán cơ bản tương ứng với các cấu trúc dữ liệu và các giải
thuật.
Biết cách tổ chức dữ liệu hợp lý, khoa học cho một chương trình đơn giản.
Biết áp dụng thuật toán hợp lý đối với cấu trúc dữ liệu tương ứng để giải quyết
bài toán trên máy tính.
Biết và áp dụng được các phương pháp sắp xếp, tìm kiếm cơ bản
Bố trí làm việc khoa học đảm bảo an toàn cho người và phương tiện học tập.
* NỘI DUNG CỦA MÔN HỌC:
Thời gian
Số
TT
Lý
thuyế
Tên các chương trong môn
Tổng
số
Thực
hành
Kiểm tra*
t
1
Tổng quan về Cấu trúc dữ liệu và
5
4
1
giải thuật
2
3
4
5
6
7
Đệ qui và giải thuật đệ qui
Danh sách
Các phương pháp sắp xếp cơ bản
Tìm kiếm
Cây
5
2
15
10
2
6
6
2
14
11
5
4
4
1
1
1
1
30
22
8
10
10
90
Đồ thị
Cộng
45
41
4
YÊU CẦU VỀ ĐÁNH GIÁ HOÀN THÀNHMÔN HỌC/MÔ ĐUN
Giáo trình Cấu trúc dữ liệu và giải thuật
Trang 7 / 92
Về kiến thức: Đánh giá kiến thức qua bài kiểm tra viết, trắc nghiệm đạt được
các yêu cầu sau:
Hiểu được mối quan hệ giữa cấu trúc dữ liệu và giải thuật.
Phân tích được các kiểu dữ liệu, giải thuật, sự kết hợp chúng để tạo thành một
chương trình máy tính.
Biết cách tổ chức dữ liệu hợp lý, khoa học cho một chương trình đơn giản.
Biết áp dụng thuật toán hợp lý đối với cấu trúc dữ liệu tương thích để giải
quyết bài toán thực tế.
Biết và áp dụng được các phương pháp sắp xếp, tìm kiếm đơn giản.
Về kỹ năng:
Đánh giá kỹ năng thực hành của sinh viên:
Dùng ngôn ngữ lập trình bất kỳ nào đó thể hiện trên máy tính các bài toán
cần kiểm nghiệm về: đệ qui, danh sách, cây, đồ thị, sắp xếp, tìm kiếm...
Về thái độ: Cẩn thận, tỉ mỉ, thao tác chuẩn xác, tự giác trong học tập.
Giáo trình Cấu trúc dữ liệu và giải thuật
Trang 8 / 92
CHƯƠNG 1: TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
Mã chương: Mh17-01
Giới thiệu:
Tổng quan về giải thuật. Đầ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.
Mục tiêu:
- Mô tả được khái niệm giải thuật, mối quan hệ giữa cấu trúc dữ liệu và giải
thuật. Trình bày được các tiêu chuẩn để đánh giá độ phức tạp của giải thuật.
- Ghi nhớ được các kiểu dữ liệu cơ bản, kiểu dữ liệu trừu tượng và các cấu
trúc dữ liệu cơ bản.
- Thực hiện các thao tác an toàn với máy tính.
Nội dung chính:
1.Khái niệm giải thuật và đánh giá độ phức tạp của giải thuật
Mục tiêu:
Mô tả được khái niệm giải thuật, mối quan hệ giữa cấu trúc
dữ liệu và giải thuật. Trình bày được các tiêu chuẩn để đánh giá độ phức tạp
của giải thuật.
1.1. Khái niệm giải thuật
❖ Khái niệm:
Giải thuật, còn gọi là thuật toán (algorithm) là một trong những khái
niệm quan trọng nhất trong tin học. Thuật ngữ thuật toán xuất phát từ nhà toán
học Arập Abu Ja'far Mohammed ibn Musa al Khowarizmi (khoảng năm 825).
Giải thuật thể hiện một giải pháp cụ thể, thực hiện từng bước một để đưa
tới lời giải cho một bài toán.
Nói cách khác, giải thuật là một tập hữu hạn các phép toán cơ sở, được sắp
đặt theo những quy tắc chính xác, nhằm giải một bài toán, hay là một bộ các qui
tắc hay qui trình cụ thể nhằm giải quyết một vấn đề trong một số bước hữu hạn,
nhằm cung cấp một kết quả từ một tập hợp của các dữ kiện đưa vào.
Các phép toán cơ sở là những phép toán đơn giãn mà thời gian thực hiện nó
là hữu hạn và không phụ thuộc vào kích thước của dữ liệu.
Các phép toán trong giải thuật phải được xác định rỏ ràng, dễ hiểu, không
mập mờ.
Với mọi bộ dữ liệu vào thoả mãn các điều kiện của bài toán, thuật toán phải
dừng lại sau một số hữu hạn các bước cần thực hiện
Giáo trình Cấu trúc dữ liệu và giải thuật
❖ Các đặc trưng của giải thuật:
Trang 9 / 92
• Dữ liệu vào: Mỗi thuật toán đều có một số giá trị nhập vào, chúng được
gọi là Input data.
• Dữ liệu ra: Mỗi thuật toán có một số giá trị đưa ra, chúng được gọi là
Output data.
• Tính xác định: Mọi bước của một thuật toán bao giờ cũng được xác
định rõ ràng, chính xác và do đó luôn thực hiện được.
• Tính dừng: Sau một số hữu hạn các bước bài toán luôn được giải
quyết.
• Tính phổ dụng: Thuật toán có thể làm việc với các kiểu dữ liệu khác
nhau trong miền xác định và luôn dẫn đến kết quả mong muốn.
• Tính hiệu quả: Được thể hiện ở sự đúng đắn của thuật toán và độ phức
tạp của thuật toán.
Tính hiệu quả được thể hiện bởi khả năng thực thi các bước của
thuật toán để đạt được kết quả mong muốn và tổng thời gian thực
hiện thuật toán phải đủ nhỏ.
Chú ý: Trên thực tế để đánh giá tính hiệu quả của các thuật toán,
người ta thường qui về các đơn vị tính sơ cấp. Tính hiệu quả của một
thuật giải được đo bởi số lượng các đơn vị tính sơ cấp mà thuật toán này
yêu cần thực hiện. Ví dụ cho các phép tính sơ cấp đó là phép +, -, *, :
các số tự nhiên nhỏ hơn 10
1.2. Ngôn ngữ diễn đạt giải thuật
• Sử dụng ngôn ngữ tự nhiên: Sử dụng ngôn ngữ thường ngày để biểu
diễn các bước của thuật toán.
Phương pháp biểu diễn này không yêu cầu người viết thuật toán
cũng như người đọc thuật toán phải nắm các quy tắc.
Tuy vậy, cách biểu diễn này thường dài dòng, không thể hiện rõ
cấu trúc của thuật toán, đôi lúc gây hiểu lầm hoặc khó hiểu cho người
đọc.
• Sử dụng sơ đồ khối (flowchart): Lưu đồ hay sơ đồ khối là một công cụ
trực quan để diễn đạt các thuật toán.
Giáo trình Cấu trúc dữ liệu và giải thuật
Trang 10 / 92
Biểu diễn thuật toán bằng lưu đồ sẽ giúp người đọc theo dõi được
sự phân cấp các trường hợp và quá trình xử lý của thuật toán.
Phương pháp lưu đồ thường được dùng trong những thuật toán có
tính rắc rối, khó theo dõi được quá trình xử lý.
Ðể biểu diễn thuật toán theo sơ đồ khối, ta phải phân biệt hai loại
thao tác:
- Thao tác chọn lựa (decision): dựa theo một điều kiện nào đó.
Chẳng hạn : thao tác "nếu a = b thì thực hiện thao tác B2, ngược lại thực
hiện
B4"
là
thao
tác
chọn
lựa.
Thao tác chọn lựa được biểu diễn bằng một hình thoi, bên trong chứa
biểu thức điều kiện.
- Thao tác xử lý (process): Các thao tác còn lại không thuộc loại
chọn lựa được xếp vào loại hành động. Chẳng hạn, "Chọn một hộp bất
kỳ và để lên dĩa cân còn trống." là một thao tác thuộc loại hành động.
Thao tác xử lý được biểu diễn bằng một hình chữ nhật, bên trong
chứa nội dung xử lý
• Sử dụng mã giả(pseudocode): Tuy sơ đồ khối thể hiện rõ quá trình xử
lý và sự phân cấp các trường hợp của thuật toán nhưng lại cồng kềnh.
Ðể mô tả một thuật toán nhỏ ta phải dùng một không gian rất lớn.
Hơn nữa, lưu đồ chỉ phân biệt hai thao tác là rẽ nhánh (chọn lựa có
điều kiện) và xử lý mà trong thực tế, các thuật toán còn có thêm các
thao tác lặp.
Khi thể hiện thuật toán bằng mã giả, ta sẽ vay mượn các cú pháp
của một ngôn ngữ lập trình nào đó để thể hiện thuật toán. Tất nhiên,
mọi ngôn ngữ lập trình đều có những thao tác cơ bản là xử lý, rẽ nhánh
và lặp.
Dùng mã giả vừa tận dụng được các khái niệm trong ngôn ngữ lập
trình, vừa giúp người cài đặt dễ dàng nắm bắt nội dung thuật toán.
Tất nhiên là trong mã giả ta vẫn dùng một phần ngôn ngữ tự nhiên.
Một khi đã vay mượn cú pháp và khái niệm của ngôn ngữ lập trình thì
chắc chắn mã giả sẽ bị phụ thuộc vào ngôn ngữ lập trình đó. Chính vì lý
do này, chúng ta chưa vội tìm hiểu về mã giả trong bài này.
• Sử dụng ngôn ngữ lập trình(code):Pascal, C, C++, C#,...
Giáo trình Cấu trúc dữ liệu và giải thuật
1.2.1. Quy cách về cấu trúc chương trình
Trang 11 / 92
Mỗi chương trình đều được gán một tên để phân biệt, tên này được viết
bằng chữ in hoa, có thể có thêm dấu gạch nối và bắt đầu bằng từ khoá Program
Ví dụ : Prorgram NHAN-MA-TRAN
Độ dài tên không hạn chế.
Sau tên có thể kèm theo lời thuyết minh (ở đây ta quy ước dùng Tiếng
Việt) để giới thiệu tóm tắt nhiệm vụ của giải thuật hoặc một số chi tiết cần thiết.
Phần thuyết minh được đặt giữa hai dấu {...}.
Chương trình bao gồm nhiều bước, mỗi bước được phân biệt bởi số thứ tự,
có thể kèm theo những lời thuyết minh.
1.2.2. Kí tự và biểu thức
Kí tự dùng ở đây cũng giống như trong các ngôn ngữ chuẩn, nghĩa là gồm :
26 chữ cái Latinh in hoa hoặc in thường
10 chữ số thập phân
Các dấu phép toán số học: +, - , *, /, (lũy thừa)
Các dấu phép toán quan hệ: <, =, >, , , #.
Giá trị logic: true, false
Dấu phép toán logic: and, or, not
Tên biến là dãy chữ cái và chữ số, bắt đầu bằng chữ cái
Biến chỉ số có dạng :A[i], B[ij] v.v...
Còn biểu thức cũng như thứ tự ưu tiên của các phép toán trong biểu thức
cũng theo quy tắc như trong PASCAL hay các ngôn ngữ chuẩn khác.
1.2.3. Các câu lệnh
Các câu lệnh trong chương trình được viết cách nhau bởi dấu chấm phảy
chúng bao gổm :
Câu lệnh gán
Có dạng Tên biến/ Tên hàm : = Biểu thức
Ở đây cho phép dùng phép gán chung.
Ví dụ : X : = Y : = 5
Câu lệnh ghép
Có dạng : begin Câu lệnh1 ; Câu lệnh2 ; ... ; Câu lệnhn end
Nó cho phép ghép nhiều câu lệnh lại để được coi như một câu lệnh.
Câu lệnh điều kiện
Có dạng : if < Điều kiện > then < Câu lệnh >
Giáo trình Cấu trúc dữ liệu và giải thuật
Có thể diễn tả bởi sơ đồ :
Trang 12 / 92
true
Câu lệnh1
Điều kiện
false
Câu lệnh2
Hoặc
if < Điều kiện > then <Câu lệnh1>else< Câu lệnh2>
Câu lệnh
true
Điều kiện
false
Câu lệnh tuyến
Case
Điều kiện1: Câu lệnh1;
Điều kiện2: Câu lệnh2;
……
……
Điều kiệnn: Câu lệnhn;
Else: Câu lệnhn+1
End case
Câu lệnh này cho phân biệt các tình huống xử lí khác nhau trong các điều
kiện khác nhau mà không phải tới các câu lệnh if – then – else khác nhau. Có
thể diễn tả bởi sở đồ :
false
false
false
B1
B2
Bn
Sn+1
tru
Chú thích:
Bi: Điều kiện
Si: Câu lệnh
tru
tru
S1
S2
Sn
Giáo trình Cấu trúc dữ liệu và giải thuật
Trang 13 / 92
Vài điểm linh động
esle có thể không có mặt
Câu lệnhi(i = 1, 2, …, n) có thể được thay thế bằng một dãy các câu lệnh
mà không cần phải đặt giữa : begin và end .
Câu lệnh lặp
Với số lần lặp biết trước :
for i : = m to n do < Câu lệnh>.
nhằm thực hiện < Câu lệnh > với i lấy giá trị nguyên từ m tới n ( n m) với
bước nhảy tăng bằng 1,
hoặc : for i := n down to m do < Câu lệnh>
tương tự như câu lệnh trên vơi bước nhảy giảm bằng 1.
Với số lần lặp không biết trước:
While < Điều kiện >do < Câu lệnh>
true
Câu lệnh
false
Chừng nào mà < Điều kiện > có giá trị bằng true thì thực hiện < Câu lệnh>
Hoặc :
repeat < Câu lệnh>until < Điều kiện >
Lặp lại < Câu lệnh> cho tới khi < Điều kiện > có giá trị true.
fasle
Câu lệnh
true
Câu lệnh nhập: read (<danh sách biến>)
Câu lệnh xuất: write(<danh sách biến hoặc dòng kí tự>)
các biến trong danh sách cách nhau bởi dấu phẩy.
Giáo trình Cấu trúc dữ liệu và giải thuật
Trang 14 / 92
Dòng kí tự là một dãy các kí tự đặt giữa hai dấu nháy’ ‘ .
Câu lệnh kết thúc chương trình: End
1.2.4. Chương trình con
Chương trình con hàm
Có dạng :
Function <tên hàm> (<danh sách tham số>)
S1; S2; … ; Sn.
Return
Chương trình con thủ tục
Có dạng :
Function <tên hàm> (<danh sách tham số>)
S1; S2; … ; Sn.
Return
Câu lệnh kết thúc chương trình ở đây là return thay cho end.
Trong cấu tạo của chương trình con hàm bao giờ cũng có câu lệnh gán mà
tên hàm nằm ở vế trái. Còn đối với chương trình con thủ tục thì không có.
Lời gọi chương trình con hàm thể hiện bằng tên hàm cùng danh sách tham
số thực sự, nằm trong biểu thức. Còn với chương trình con thủ tục lời gọi được
thể hiện bằng câu lệnh call có dạng :
Call <tên thủ tục> (<danh sách tham số thực sự>)
Chú ý : Trong các chương trình diễn đạt một giải thuật ở đây phần khai báo
dữ liệu được bỏ qua. Nó được thay vởi phần mô ta cấu trúc dữ liệu bằng ngôn
ngữ tự nhiên, mà ta sẽ nêu ra trước khi bước vào giải thuật.
1.3. Thiết kế giải thuật
Tạo lập giải thuật để giải một bài toán là một nghệ thuật mà không bao giờ
có thể nêu đầy đủ ngay một lúc.
Có nhiều phương pháp thiết kế giải thuật khác nhau. Tuy nhiên ta cũng
thấy rằng mọi việc sẽ đơn giản hơn nếu như có thể phân chia bài toán lớn thành
những bài toán nhỏ hơn, điều đó có nghĩa là có thể coi bài toán của ta như là một
Modul chính, cần chia thành các Modul con, và trên tinh thần như vậy đến các
modul con ta có thể chia thành các modul nhỏ hơn, chia cho đến khi tới những
modul con đủ nhỏ để có thể xử lý trực tiếp. Sau đó chỉ cần tổng hợp lại các phép
xử lý để có giải thuật của bài toán gốc.
Để làm được những điều đó, đứng trước một bài toán, thông thường ta
phải:
Giáo trình Cấu trúc dữ liệu và giải thuật
Trang 15 / 92
Xác định được rõ dữ liệu và yêu cầu : cho biết cái gì ?(dữ liệu input) và đòi
hỏi cái gì ? ( dữ liệu output).
Để giải quyết được yêu cầu thì “phải làm gì ?” : ở đây mới chỉ phân hoạch
hỏi cái gì ? ( dữ liệu output).
Với mỗi công việc ấy thì “ phải làm thê nào “ ?
Trên cơ sở đó mới cụ thể hóa dần dần các phép xử lí để xây dựng giải thuật
cần thiết.
Tất nhiên, khi giải quyết câu hỏi “ làm thế nào ?” thì dữ liệu input cũng
phải được định hình về cấu trúc.
Ví dụ, ta xét bài toán :
Sắp xếp là một dãy số ( a1,a2,….,an) thành một dãy số tăng dần.
•Như vậy dãy số input, nếu có dạng, chẳng hạn :
(33, 77, 11, 55, 99, 22, 44, 88, 66)
thì dãy sốoutput phải có dạng :
(11, 22, 33, 44, 55, 66, 77, 88, 99)
•Để có được kết quả output như vậy thì phải làm gì ?
Có thể thấy rằng : sắp xếp theo thứ tự tăng dần nghĩa là :
–Số bé nhất trong n số phải được đặt vào vị trí đầu tiên ;
–Số bé nhất trong (n – 1 ) số còn lại phải được đặt vào vị trí thứ hai ; v.v…
Như vậy sẽ có hai công việc chính phải làm :
•Chọn số bé nhất trong dãy số chưa được sắp.
•Đặt nó vào vị trí sau phần tử cuối của dãy số đã được sắp ( nó lại trở
thànhphần tử cuối cho bước tiếp theo ).
Chú ý rằng : lúc đầu dãy số được sắp còn rỗng, sau đó nó được bổ sung dần
dần các phần tử vào.
Các công việc trên sẽ được lặp lại (n - 1) lần : đầu với n số, lần cuối với 2
số.
•Để thực hiện được hai công việc nêu trên thì phải “làm thế nào ?”
Trước hết phải nghĩ ngay tới : dãy số ở đây được định hình theo cấu trúc
nào ? (cấu trúc dữ liệu) và được cài đặt trong máy theo cấu trúc nào ? (mà ta sẽ
được gọi là: cấu trúc lưu trữ).
Thông thường nó được định hình và cài đặt theo cấu trúc vectơ.
Ở đây có hai vectơ : vectơ input và vectơ output.Vậy thì trong máy ta sẽ
dùng hai vectơ để lưu trữ hay chỉ dùng một ?
Giáo trình Cấu trúc dữ liệu và giải thuật
Trang 16 / 92
Giả sử ta chỉ dùng 1,nghĩa là lúc đầu vectơ lưu trữ chứa dãy số cho,nhưng
sau khi thực hiện giải thuật thì chính vectơ ấy cũng chứa dãy số đã được sắp
xếp(để tiết kiệm bộ nhớ !).
Nếu thế thì công việc “đổi chỗ” sẽ được cụ thể thêm như sau :
–Hoán vị trí của nó (số bé nhất vừa được chọn) với vị trí của số ở đầu dãy
chưa được sắp,sau đó gạt nó ra ngoài dãy chưa được sắp(tất nhiên lúc đó nó đã
trở thành phần tử cuối của dãy đã được sắp).
Tới đây ta có thể diễn ddajt sơ bộ giải thuật “sắp xếp” của ta như sau :
Procedure SELECTION-SORT(A,n);
{A là vectơ gồm n phần tử là các số cho}
1.{2 công việc được lặp lại (n-1) lần}
for i:=1 to (n-1) do begin.
2.Chọn số nhỏ nhất A[k] trong dãy các số:
A[i],A[i+1],….,A[n]
3.Hoán vị giữa A[k] và A[i]
4.
return
end;
Bây giờ ta đi sâu vào từng công việc :
•Làm thế nào để chọn được số nhỏ nhất trong dãy các số:
A[i],A[i+1],….,A[n]?
Có thể tiến hành như sau : thoạt đầu ta cứ chọn A[i],sau đó so sánh các
phần tử tiếp theo với nó,nếu phần tử nào nhỏ hơn thì lại thay phần tử đó
vào,phần tử cuối cùng được thay chính là phần tử cần tìm.
Nhưng xét cho cùng : ta chỉ cần biết chỉ số k ứng với phần tử nhỏ nhất đó
thì sẽ tìm được nó ,vì vậy công việc “chọn” ở trên chỉ cần làm với chỉ số.Có thể
diễn đạt như sau :
k:=1 ; { coi phần tử đầu là nhỏ nhất lúc đó,và giữ lại chỉ số của nó}
for j:=i+1 to n do
if A[j] < A [k] then k:=j
•Làm thế nào để thực hiện được việc hoán vị chỗ cho hai phần tử ?
Cách giải quyết ở đây giống như khi ta có 2 cốc khác nhau: một đựng
rượu,một đựng nước; mà ta lại muốn hoán vị 2 thứ chất lỏng này nghĩa là
chuyển sang cốc đang đựng rượu và chuyển rượu sang cốc đang đựng nước.
Rõ ràng điều này chỉ có thể thực hiện được khi ta dùng tới một cóc thứ ba
làm cốc trung chuyển.
Từ đó ta có thể diễn đạt việc hoán vị giữa A[k] và A[i] như sau :
Giáo trình Cấu trúc dữ liệu và giải thuật
Trang 17 / 92
LOC : = A[k] ; A[k] := A[i];A[i]:=LOC;
Tổng hợp những ghi nhận ở trên , ta đi tới một thủ tục , thể hiện giải thuật
“sắp xếp” của ta ,bằng ngôn ngữ tựa PASCAL như sau :
Procedure SELECTION-SORT (A,n);
1.for i:=1 to (n-1) do begin
2.k:=1;
3.for j:=i+1 to n do
4.if A[j] < A[k] then k:=j;
5.LOC :=A[k];A[k]:=A[i];A[i]:=LOC
end;
6.return
Chú ý:
✓ Cách làm ở trên phản ảnh một phương pháp thiết kế giải
thuật, gắn liền với lập trình được gọi là "phương pháp tinh
chỉnh từng bước" (stepwise refinement).
✓ Cách cài đặt một cấu trúc dữ liệu trong máy tính điện tử có thể khác
nhau. Vì vậy để phân biệt ta gọi cấu trúc cài đặt trong máy của một
“cấu trúc dữ liệu” là “cấu trúc lưu trữ”. Như vậy nghĩa là cấu trúc
lưu trữ có thể biểu diễn được nhiều cấu trúc dữ liệu khác nhau.
1.4. Đánh giá giải thuật
Khi giải quyết một vấn đề, chúng ta cần chọn trong số các thuật toán, một
thuật toán mà chúng ta cho là tốt nhất. Vậy ta cần lựa chọn thuật toán dựa trên
cơ sở nào? Thông thường ta dựa trên hai tiêu chuẩn sau đây:
1. Thuật toán đơn giản, dễ hiểu, dễ cài đặt (dễ viết chương trình)
2. Thuật toán sử dụng tiết kiện nhất nguồn tài nguyên của máy tính, và đặc
biệt, chạy nhanh nhất có thể được.
Khi ta viết một chương trình chỉ để sử dụng một số ít lần, và cái giá của
thời gian viết chương trình vượt xa cái giá của chạy chương trình thì tiêu chuẩn
(1) là quan trọng nhất. Nhưng có trường hợp ta cần viết các chương trình (thủ
tục hoặc hàm ) để sử dụng nhiều lần, cho nhiều người sử dụng, khi đó giá của
thời gian chạy chương trình sẽ vượt xa giá viết nó. Chẳng hạn, các thủ tục sắp
xếp, tìm kiếm được sử dụng rất nhiều lần bởi rất nhiều người trong các bài toán
khác nhau. Trong trường hợp này ta cần dựa trên tiêu chuẩn (2). Ta sẽ cài đặt
thuật toán có thể rất phức tạp, miễn là chương trình nhận được chạy nhanh hơn
các thuật toán khác.
Tiêu chuẩn (2) được xem là tính hiệu quả của thuật toán. Tính hiệu quả của
thuật toán bao gồm hai nhân tố cơ bản
Giáo trình Cấu trúc dữ liệu và giải thuật
Trang 18 / 92
1. Dung lượng không gian nhớ cần thiết để lưu giữ các dữ liệu vào, các kết
quả tính toán trung gian và các kết quả của thuật toán.
2. Thời gian cần thiết để thực hiện thuật toán (ta gọi là thời gian chạy
chương trình, thời gian này không phụ thuộc vào các yếu tố vật lý của máy tính
(tốc độ xử lý của máy tính, ngôn ngữ viết chương trình... ))
Chúng ta sẽ chỉ quan tâm đến thời gian thực hiện thuật toán. Vì vậy khi nói
đến đánh giá độ phức tạp của thuật toán, có nghĩa là ta nói đến đánh giá thời
gian thực hiện. Một thuật toán có hiệu quả được xem là thuật toán có thời gian
chạy ít hơn các thuật toán khác.
1.4.1.Đánh giá thời gian thực hiện của giải thuật
Có hai cách tiếp cận để đánh giá thời gian thực hiện của một thuật toán
Phương pháp thử nghiệm: Chúng ta viết chương trình và cho chạy chương
trình với các dữ liệu vào khác nhau trên một máy tính nào đó. Thời gian chạy
chương trình phụ thuộc vào các nhân tố sau đây:
1. Các dữ liệu vào
2. Chương trình dịch để chuyển chương trình nguồn thành chương trình mã
máy.
3. Tốc độ thực hiện các phép toán của máy tính được sử dụng để chạy
chương trình.
Vì thời gian chạy chương trình phụ thuộc vào nhiều nhân tố, nên ta không
thể biểu diễn chính xác thời gian chạy là bao nhiêuđơn vị thời gian chuẩn, chẳng
hạn nó là bao nhiêu giây.
Phương pháp lý thuyết : ta sẽ coi thời gian thực hiện của thuật toán như là
hàm số của cỡ dữ liệu vào. Cỡ của dữ liệu vào là một tham số đặc trưng cho dữ
liệu vào, nó có ảnh hưởng quyết định đến thời gian thực hiện chương trình. Cái
mà chúng ta chọn làm cỡ của dữ liệu vào phụ thuộc vào các thuật toán cụ thể.
Chẳng hạn, đối với các thuật toán sắp xếp mảng, thì cỡ của dữ liệu vào là số
thành phần của mảng; đối với thuật toán giải hệ n phương trình tuyến tính với n
ẩn, ta chọn n là cỡ. Thông thường dữ liệu vào là một số nguyên dương n. Ta sẽ
sử dụng hàm số T(n), trong đó n là cỡ dữ liệu vào, để biểu diễn thời gian thực
hiện của một thuật toán.
Ta có thể xác định thời gian thực hiện T(n) là số phép toán sơ cấp cần phải
tiến hành khi thực hiện thuật toán. Các phép toán sơ cấp là các phép toán mà
thời gian thực hiện vbị chặn trên bởi một hằng số chỉ phụ thuộc vào cách cài đặt
được sử dụng. Chẳng hạn các phép toán số học +, -, *, /, các phép toán so sánh
=, <>... là các phép toán sơ cấp.
Giáo trình Cấu trúc dữ liệu và giải thuật
Trang 19 / 92
1.4.2. Độ phức tạp tính toán của giải thuật
Khi đánh giá thời gian thực hiện bằng phương pháp toán học, chúng ta sẽ
bỏ qua nhân tố phụ thuộc vào cách cài đặt, chỉ tập trung vào xác định độ lớn của
thời gian thực hiện T(n). Ký hiệu toán học O (đọc là ô lớn) được sử dụng để mô
tả độ lớn của hàm T(n).
Giả sử n là số nguyên không âm, T(n) và f(n) là các hàm thực không âm.
Ta viết T(n) = O(f(n)) (đọc : T(n) là ô lớn của f(n)), nếu và chỉ nếu tồn tại các
hằng số dương c và n0 sao cho T(n) c.f(n), với n > n0.
Nếu một thuật toán có thời gian thực hiện T(n) = O(f(n)), chúng ta sẽ nói
rằng thuật toán có thời gian thực hiện cấp f(n).
Ví dụ : Giả sử T(n) = 10n2 + 4n + 4
Ta có : T(n) 10n2 + 4n2+ 4n2 = 12 n2 , với n 1
Vậy T(n) = O(n2). Trong trường hợp này ta nói thuật toán có độ phức tạp
(có thời gian thực hiện) cấp n2.
Bảng sau đây cho ta các cấp thời gian thực hiện thuật toán được sử dụng
rộng rãi nhất và tên gọi thông thường của chúng.
Tên gọi thông
thường
Ký hiệu ô lớn
O(1)
Hằng
O(log2n)
O(n)
logarit
Tuyến tính
nlog2n
O(nlog2n)
O(n2)
Bình phương
Lập phương
Mũ
O(n3)
O(2n)
Danh sách trên sắp xếp theo thứ tự tăng dần của cấp thời gian thực hiện
Các hàm như log2n, n, nlog2n, n2, n3 được gọi là các hàm đa thức. Giải
thuật với thời gian thực hiện có cấp hàm đa thức thì thường chấp nhận được.
Các hàm như 2n, n!, nn được gọi là hàm loại mũ. Một giải thuật mà thời
gian thực hiện của nó là các hàm loại mũ thì tốc độ rất chậm.
2.Các kiểu dữ liệu cơ bản
Mục tiêu:Ghi nhớ được các kiểu dữ liệu cơ bản.
Giáo trình Cấu trúc dữ liệu và giải thuật
Trang 20 / 92
Kiểu dữ liệu là một tập hợp các giá trị và một tập hợp các phép toán trên
các giá trị đó.
Ví dụ: Kiểu Integer là tập hợp các số nguyên có giá trị từ -32768 đến 32767
cùng các phép toán như {+, -, *, /, div, mod,...}. Kiểu Boolean là một tập hợp
gồm 2 giá trị {True, Fasle} và các phép toán trên nó như {and, or, not,...}.
Kiểu dữ liệu sơ cấp là kiểu dữ liệu mà giá trị của nó là đơn nhất.
Thông thường trong một hệ kiểu của ngôn ngữ lập trình sẽ có một số kiểu
dữ liệu được gọi là kiểu dữ liệu sơ cấp hay kiểu dữ liệu phân tử (atomic).
Thông thường, các kiểu dữ liệu cơ bản bao gồm :
Kiểu có thứ tự rời rạc : số nguyên, ký tự, logic, liệt kê, miền con
Kiểu không rời rạc : số thực
Tuỳ từng ngôn ngữ lập trình, các kiểu dữ liệu định nghĩa sẵn này có thể
khác nhau đôi chút. Chẳng hạn, với ngôn ngữ C, các kiểu dữ liệu này chỉ gồm số
nguyên, số thực, ký tự. Và theo quan điểm của C, kiểu ký tự thực chất cũng là
kiểu số nguyên về mặt lưu trữ, chỉ khác về cách sử dụng. Ngoài ra, giá trị logic
đúng (TRUE) và giá trị logic sai (FALSE) được biểu diễn trong ngôn ngữ C như
là các giá trị nguyên khác 0 và bằng 0. Trong khi đó Pascal định nghĩa tất cả các
kiểu dữ liệu đã liệt kê ở trên và phân biệt chúng một cách chặt chẽ.
Sau đây là hệ kiểu của Pascal:
1. Kiểu integer
2. Kiểu real
3. Kiểu boolean
4. Kiểu char
5. Kiểu string
Là kiểu dữ liệu chứa các giá trị là nhóm các ký tự hoặc chỉ một ký tự kể cả
chuổi rổng. Độ dài tối đa của một biến String là 255 ký tự, tức là nó có thể chứa
tối đa một dãy gồm 255 ký tự.
Kiểu dữ liệu String trong pascal được khai báo như sau:
Var Biến1 , Biến 2 ,… Biếnn : String[số ký tự tối đa]
3.Các kiểu dữ liệu trừu tượng
Mục tiêu:Ghi nhớ được khái niệm kiểu dữ liệu trừu tượng.
Kiểu dữ liệu trừu tượng là một mô hình toán học cùng một tập hợp các phép
toán trừu tượng được định nghĩa trên mô hình đó. Có thể nói kiểu dữ liệu trừu
tượng là một kiểu dữ liệu do chúng ta định nghĩa mức khái niệm, chưa được cài
đặt bởi ngôn ngữ lập trình.
Giáo trình Cấu trúc dữ liệu và giải thuật
Trang 21 / 92
Khi cài đặt một kiểu dữ liệu trừu tượng trên một ngôn ngữ lập trình ta thực
hiện hai nhiệm vụ:
•Biểu diễn kiểu dữ liệu trừu tượng bằng một cấu trúc dữ liệu hoặc bằng
một kiểu dữ liệu trừu tượng khácđãđược càiđặt.
•Viết chương trình con thực hiện các phép toán trên kiểu dữ liệu trừu
tượng
Một số kiểu dữ liệu trừu tượng: Danh sách, cây, đồ thị,...
3. Kiểu bản ghi, kiểu con trỏ
Mục tiêu:Ghi nhớ được các kiểu dữ liệu bản ghi và kiểu dữ liệu con trỏ
Kiêu dữ liệu có cấu trúc hay còn gọi là cấu trúc dữ liệu là kiểu dữ liệu mà
các dữ liệu của nó là sự kết hợp của các giá trị khác.
Một số kiểu dữ liệu có cấu trúc như: Bản ghi, con trỏ, Array,...
3.1. Kiểu bản ghi
Bản ghi là một cấu trúc bao gồm một số các phần tử có kiểu khác nhau
nhưng liên quan với nhau. Các phần tử này gọi là các trường, có thể có những
trường trong một bản ghi mà là một bản ghi.
Kiểu dữ liệu bản ghi trong pascal được khai báo như sau:
Type
<Tên kiểu> = Record
<Tên trường 1> : Kiểu;
<Tên trường 2> : Kiểu;
...
<Tên trường n> : Kiểu;
End;
Ví dụ: Khai báo kiểu dữ liệu bảng điểm gồm một số trường nhằm phục vụ
quản lý điểm như sau:
Type
BangDiem = Record
Hoten : String[30];
Lop : String[6];
Diachi : String;
DiemLT, DiemTH : real;
End;
Tải về để xem bản đầy đủ
92 trang
05/05/2022
4040
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình môn học Cấu trúc dữ liệu và giải thuật", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- giao_trinh_mon_hoc_cau_truc_du_lieu_va_giai_thuat.docx
