ỦY BAN NHÂN DÂN THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG CAO ĐẲNG KINH TẾ KỸ THUẬT
THÀNH PHỐ HỒ CHÍ MINH


GIÁO TRÌNH
MƠN HỌC: CẤU TRÚC DỮ LIỆU
NGÀNH: HỆ THỐNG THÔNG TIN, THIẾT KẾ TRANG WEB, CƠNG
NGHỆ THƠNG TIN (ỨNG DỤNG PHẦN MỀM)
TRÌNH ĐỘ: CAO ĐẲNG

Thành phố Hồ Chí Minh, năm 2020


ỦY BAN NHÂN DÂN THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG CAO ĐẲNG KINH TẾ KỸ THUẬT
THÀNH PHỐ HỒ CHÍ MINH


GIÁO TRÌNH
MƠN HỌC: CẤU TRÚC DỮ LIỆU
NGÀNH: HỆ THỐNG THÔNG TIN, THIẾT KẾ TRANG WEB, CƠNG
NGHỆ THƠNG TIN (ỨNG DỤNG PHẦN MỀM)
TRÌNH ĐỘ: CAO ĐẲNG

THÔNG TIN CHỦ NHIỆM ĐỀ TÀI
Họ tên: Võ Đào Thị Hồng Tuyết
Học vị: Thạc Sỹ
Đơn vị: Khoa Công Nghệ Thơng Tin
Email: [email protected]
TRƯỞNG KHOA

lựa chọn áp dụng giải thuật nào.
Bài giảng “Cấu Trúc Dữ Liệu” bao gồm 4 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 tố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. Trình bày về đệ qui, một khái niệm rất cơ bản
trong toán học. 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 2 trình bày về các thuật tố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 tố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 tốn cài đặt phức tạp nhưng có thời gian thực hiện tối ưu.
Chương 3, 4 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. Đó 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.
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 tốn. Do vậy, ngồi các kiến thức cơ bản về
tin học, sinh viên 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 đồng nghiệp và sinh viên để tài
liệu được hoàn thiện hơn.


MỤC LỤC

11

1. Một số phương pháp sắp xếp đơn giản
1.1. Đổi chỗ trực tiếp (Interchange Sort)
1.2. Nổi bọt (Bubble Sort)
1.3. Chèn trực tiếp (Insertion Sort)
1.4. Chọn trực tiếp (Selection Sort)
1.5. Phân hoạch (Quick Sort)
1.6. Nhận xét, đánh giá

11
11
14
17
20
22
25

2. Một số phương pháp tìm kiếm
2.1. Tìm kiếm tuần tự
2.2. Tìm kiếm nhị phân
2.3. Nhận xét, đánh giá:

27
27
29
32

DANH MỤC HÌNH ẢNH CHƯƠNG 2


49
50
53

DANH MỤC HÌNH ẢNH CHƯƠNG 3

56

CÂU HỎI VÀ BÀI TẬP

57

CHƯƠNG 4: CÂY

58

1. Định nghĩa và khái niệm

58

2. Cây tổng quát

58


2.1. Biểu diễn
2.2. Phép duyệt
2.3.Cây nhị phân

59

+ Trình bày được các bước phân tích, đánh giá độ phức tạp của thuật tốn
+ Trình bày được các cấu trúc kiểu dữ liệu trừu tượng, các thao tác tương
tứng trên các kiểu dữ liệu.
+ Trình bày được các thuật tốn tìm kiếm, sắp xếp
- Về kỹ năng:
+ Vận dụng cấu trúc dữ liệu, các thao tác trên cấu trúc dữ liệu đã được sử
dụng theo một bài toán cụ thể.
+ Vận dụng được các thuật tốn tìm kiếm, sắp xếp và tự cài đặt theo một
bài toán cụ thể.
+ Vận dụng các vấn đề cơ bản và mối quan hệ giữa cấu trúc dữ liệu và giải
thuật, phân tích thiết kế thuật tốn.
- Về năng lực tự chủ và trách nhiệm:
+ Sinh viên có khả năng lựa chọn thuật toán cũng như cấu trúc dữ liệu phù
hợp cho từng bài tốn.

KHOA CƠNG NGHỆ THƠNG TIN


III. Nội dung môn học:
1. Nội dung tổng quát và phân bổ thời gian:
Số
TT

Thời gian (giờ)
Tên chương, mục

Bài tập,

Tổng
số

2. Thuật giải đệ quy
2.1. Khái niệm về đệ qui
2.2.Thiết kế giải thuật đệ qui
2.3. Áp dụng thuật giải đệ
qui
Chương 2: Các thuật giải
sắp xếp và tìm kiếm
1. Một số phương pháp sắp
xếp đơn giản
1.1. Đổi chỗ trực tiếp
(Interchange Sort)
1.2. Nổi bọt (Bubble Sort)

2

1.3. Chèn trực tiếp (Insertion
Sort)
1.4. Chọn trực tiếp
(Selection Sort)
1.5. Phân hoạch (Quick Sort)
1.6 Nhận xét, đánh giá
2. Một số phương pháp tìm

KHOA CƠNG NGHỆ THƠNG TIN

1


Thời gian (giờ)


6

60

30

28

kiếm
2.1. Tìm kiếm tuần tự
2.2. Tìm kiếm nhị phân
2.3. Nhận xét, đánh giá
Chương 3: Các cấu trúc dữ
liệu
1.Danh sách liên kết đơn
3

2.Danh sách kiểu ngăn xếp
(Stack)
3.3.Danh sách kiểu hàng đợi
(Queue)
Chương 4: Cây
1. Định nghĩa và khái niệm
2. Cây tổng quát

4

2.1. Biểu diễn
2.2. Phép duyệt
2.3. Cây nhị phân

1.2. Nổi bọt (Bubble Sort)
1.3. Chèn trực tiếp (Insertion Sort)
1.4. Chọn trực tiếp (Selection Sort)
1.5. Phân hoạch (Quick Sort)
1.6 Nhận xét, đánh giá
2. Một số phương pháp tìm kiếm
2.1. Tìm kiếm tuần tự
2.2. Tìm kiếm nhị phân
2.3. Nhận xét, đánh giá
Chương 3: Các cấu trúc dữ liệu
Thời gian: 24 giờ
Mục tiêu: Trình bày được các cấu trúc dữ liệu cơ bản như ngăn xếp, hàng đợi, danh sách
liên kết. Trình bày được các thao tác cơ bản trên cấu trúc dữ liệu. Vận dụng cấu trúc dữ
liệu vào một bài tốn cụ thể
KHOA CƠNG NGHỆ THƠNG TIN


Nội dung:
1. Danh sách liên kết đơn
2. Danh sách kiểu ngăn xếp (Stack)
3. Danh sách kiểu hàng đợi (Queue)

Chương 4: Cây
Thời gian: 12 giờ
Mục tiêu: Trình bày được định nghĩa, tính chất của cây. Trình bày được cấu trúc cơ bản
của cây nhị phân, cây nhị phân tìm kiếm và các thao tác cơ bản trên cây nhị phân, cây nhị
phân tìm kiếm.
Nội dung:
1.Định nghĩa và khái niệm
2.Cây tổng quát

+ Sinh viên có khả năng lựa chọn thuật toán cũng như cấu trúc dữ liệu phù
hợp cho từng bài tốn.
2. Phương pháp:
STT

Phương pháp

Hình thức

Số cột
kiểm tra

01

Kiểm tra thường xuyên

Viết

1

02

Kiểm tra định kỳ

Viết

1

03


lớp.
+ Kết thúc khóa học, người học sẽ làm một bài kiểm tra để xác định việc
họ có hồn thành chương trình học hay khơng
+ Học sinh tham gia đầy đủ các buổi lên lớp (không nghỉ quá 30% thời
lượng học)
3. Những trọng tâm cần chú ý:
- Trình độ giáo viên: ít nhất phải có bằng cử nhân hoặc bằng cấp tương
đương tính theo kinh nghiệm dạy học trước đó. Có chứng chỉ dạy nghề.
- Nguồn lực đào tạo: Những nguồn lực sau đây được khuyến khích sử dụng
để bổ trợ những phương pháp giảng dạy đề xuất.
+ Cuốn hướng dẫn dành cho giáo viên: được biên soạn và trình bày trong
các khóa tập huấn đào tạo giáo viên.
+ Cơ sở vật chất, trang thiết bị giảng dạy: Lớp học có đầy đủ máy vi tính cho
học sinh thực tập.
+ Sách, giáo trình và tài liệu tham khảo.
+ Kế hoạch giảng dạy và giáo án chi tiết của giáo viên đóng vai trị tài liệu
chính được sử dụng trong quá trình giảng dạy.
- Phương pháp đào tạo: Giáo viên kết hợp nhiều chiến lược giảng dạy để
giúp tất cả người học thuộc mọi đối tượng có những tiến bộ nhất định nào đó.
4. Tài liệu tham khảo:
TT

Tên tác giả
PGS.TS. Hàn Viết Thuận

1

2

ThS. Nguyễn Anh Phương

Chương 1: Thiết kế giải thuật – thuật giải đệ qui

CHƯƠNG 1: THIẾT KẾ GIẢI THUẬT - THUẬT GIẢI ĐỆ QUI
Mục tiêu: Trình bày được các bước cơ bản để giải quyết bài tập và dần hình
thành việc thiết kế giải thuật để giải quyết theo yêu cầu. Trình bày được khái niệm về
giải thuật đệ quy, trình bày được các bước xây dựng thuật giải đệ quy. Qua đó đề xuất
hướng áp dụng thuật giải đệ quy cho bài toán cụ thể.
1. Thiết kế 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
Là một dãy các thao tác xác định trên một đối tượng, sao cho sau khi thực hiện
một số hữu hạn các bước thì đạt được mục tiêu. Theo R.A.Kowalski thì bản chất của
giải thuật:
Giải thuật = Logic + Điều khiển
Logic: Đây là phần khá quan trọng, nó trả lời câu hỏi "giải thuật làm gì, giải
quyết vấn đề gì?", những yếu tố trong bài tốn có quan hệ với nhau như thế nào v.v…
Ở đây bao gồm những kiến thức chuyên môn mà bạn phải biết để có thể tiến hành giải
bài tốn. Ví dụ: để giải một bài tốn tính diện tích hình cầu, mà bạn khơng cịn nhớ
cơng thức tính hình cầu thì bạn khơng thể viết chương trình cho máy để giải bài toán
này được.
Điều khiển: Thành phần này trả lời câu hỏi: giải thuật phải làm như thế nào?
Chính là cách thức tiến hành áp dụng thành phần logic để giải quyết vấn đề.
1.1.2. Ngôn ngữ diễn đạt giải thuật
Sau khi đã xây dựng được mơ hình tốn học cho vấn đề cần giải quyết, tiếp
theo, ta có thể hình thành một thuật tốn cho mơ hình đó. Phiên bản đầu tiên của thuật
toán thường được diễn tả dưới dạng các phát biểu tương đối tổng quát, và sau đó sẽ
được tinh chỉnh dần từng bước thành chuỗi các lệnh cụ thể, rõ ràng hơn.
Mối liên hệ giữa Cấu trúc dữ liệu và giải thuật
Thực hiện một đề án tin học là chuyển bài toán thực tế thành bài tốn có thể
giải quyết trên máy tính. Một bài toán thực tế bất kỳ đều bao gồm các đối tượng dữ

Chọn lọc (Selection): Chọn 1 trong 2 hay nhiều thao tác để thực hiện.
Lặp lại (Repetition): Một hay nhiều bước được thực hiện lặp lại một số lần.
Ngôn ngữ lập trình (Programming language)
Ngơn ngữ lập trình là hệ thống các ký hiệu tuân theo các qui ước về ngữ pháp
và ngữ nghĩa, dùng để xây dựng thành các chương trình cho máy tính.
Một chương trình được viết bằng một ngơn ngữ lập trình cụ thể (ví dụ Pascal,
C…) gọi là chương trình nguồn, chương trình dịch làm nhiệm vụ dịch chương trình
nguồn thành chương trình thực thi được trên máy tính.
Các bước lập trình:
Bước 1: Phân tích vấn đề và xác định các đặc điểm. (xác định I-P-O)
Bước 2: Lập ra giải pháp. (đưa ra thuật giải)
Bước 3: Cài đặt. (viết chương trình)
Bước 4: Chạy thử chương trình. (dịch chương trình)
KHOA CƠNG NGHỆ THƠNG TIN

Trang 2


Chương 1: Thiết kế giải thuật – thuật giải đệ qui
Bước 5: Kiểm chứng và hồn thiện chương trình. (thử nghiệm bằng nhiều số liệu
và đánh giá)
Kỹ thuật lập trình

I-P-O Cycle (Input-Pprocess-Output Cycle) (Quy trình nhập-xử lý-xuất)
Quy trình xử lý cơ bản của máy tính gồm I-P-O.
Input

Process

Output

Process

:

nhân lương căn bản với ngày cơng

Output

:

lương

Ví dụ 3: Xác định Input, Process, Output của chương trình giải phương trình
bậc nhất ax + b = 0
Input

:

hệ số a, b

Process

:

chia – b cho a

Output

:


khơng phải là tiêu chí quan trọng nhất. Đối với bài tốn kiểu này, thời gian để lập
trình viên xây dựng và hồn thiện thuật tốn đáng giá hơn thời gian chạy của chương
trình và như vậy những giải thuật đơn giản về mặt thiết kế và xây dựng nên được lựa
chọn.
Đối với những chương trình được thực hiện nhiều lần thì thời gian chạy của
chương trình đáng giá hơn rất nhiều so với thời gian được sử dụng để thiết kế và xây
dựng nó. Khi đó, lựa chọn một giải thuật có thời gian chạy nhanh hơn (cho dù việc
thiết kế và xây dựng phức tạp hơn) là một lựa chọn cần thiết. Trong thực tế, trong giai
đoạn đầu của việc giải quyết vấn đề, một giải thuật đơn giản thường được thực hiện
trước như là 1 nguyên mẫu (prototype), sau đó nó sẽ được phân tích, đánh giá, và cải
tiến thành các phiên bản tốt hơn.
2. Thuật giải đệ quy
2.1.Khái niệm về đệ qui
Khái niệm: Vấn đề đệ quy là vấn đề được định nghĩa bằng chính nó.
Ví dụ:
Tổng S(n) được tính thơng qua tổng S(n-1).
Cho S(n) = 1 + 2 + 3 + … + n
=>S(10)? S(11)?

Hình 1. 2 Mơ tả các bước tính tổng S(n)=1+2+3+…+n với S(10) và S(11)

KHOA CÔNG NGHỆ THÔNG TIN

Trang 4


Chương 1: Thiết kế giải thuật – thuật giải đệ qui

2 điều kiện quan trọng:
-


Đệ quy tuyến tính với V(h)=2*V(h-1) và điều kiện dừng V(0) = 2
Ví dụ 2: Gửi ngân hàng 1000 USD, lãi suất 12%/năm. Số tiền có được sau 30
năm là bao nhiêu?
Giải pháp
-

Gọi Tn là số tiền có được sau n năm.

-

Ta có:
•

Tn = Tn-1 + 0.12Tn-1 = 1.12Tn-1

•

V(0) = 1000

Đệ quy tuyến tính với T(n)=1.12*T(n-1) và điều kiện dừng V(0) = 1000
2.2.2.Chia để trị (divide & conquer)
Khái niệm:
-

Chia bài tốn thành nhiều bài tốn con.

KHOA CƠNG NGHỆ THÔNG TIN

Trang 5

-

Nếu A[mid] = x  trả về mid.

-

Ngược lại
•

Nếu x < A[mid]  tìm trong đoạn [l, mid – 1]

•

Ngược lại  tìm trong đoạn [mid + 1, r]

Sử dụng đệ quy nhị phân.
Ví dụ 2: Tính tích 2 chuỗi số cực lớn X và Y
Giải pháp
-

X = X2n-1…XnXn-1…X0, Y = Y2n-1…YnYn-1…Y0

-

Đặt XL=X2n-1…Xn, XN=Xn-1…X0  X=10nXL+XN

-

Đặt YL=Y2n-1…Yn, YN=Yn-1…Y0  Y=10nYL+YN


2.3.Áp dụng thuật giải đệ qui
Một số bài tốn kinh điển

Hình 1. 5 Một số bài tốn kinh điển
2.3.1. Tháp Hà Nội
Mơ tả bài tốn: Có 3 cột A, B và C và cột A hiện có N đĩa. Tìm cách chuyển N đĩa
từ cột A sang cột C sao cho:
-

Một lần chuyển 1 đĩa

-

Đĩa lớn hơn phải nằm dưới.

-

Có thể sử dụng các cột A, B, C làm cột trung gian.

KHOA CÔNG NGHỆ THÔNG TIN

Trang 7


Chương 1: Thiết kế giải thuật – thuật giải đệ qui

Hình 1. 6 Bài tốn tháp Hà Nội
2.3.2. Tám hậu
Mơ tả bài tốn: Cho bàn cờ vua kích thước 8x8. Hãy đặt 8 hoàng hậu lên bàn cờ
này sao cho khơng có hồng hậu nào “ăn” nhau:

KHOA CÔNG NGHỆ THÔNG TIN

Trang 9


Chương 1: Thiết kế giải thuật – thuật giải đệ qui
CÂU HỎI VÀ BÀI TẬP
1. Hãy trình bày một số ví dụ về định nghĩa theo kiểu đệ qui.
2. Một chương trình đệ qui khi gọi chính nó thì bài tốn khi đó có kích thước như
thế nào so với bài tốn ban đầu? Để chương trình đệ qui khơng bị lặp vơ hạn thì
cần phải làm gì?
3. Hãy cho biết tại sao khi chương trình có thể viết dưới dạng lặp hoặc cấu trúc
khác thì khơng nên sử dụng đệ qui?
4. Viết chương trình đệ qui tính tổng các số lẻ trong khoảng từ 1 đến 2n+1.
5. Hãy cho biết các bước thực hiện chuyển đĩa trong bài toán tháp Hà Nội với số
lượng đĩa là 5.

KHOA CÔNG NGHỆ THÔNG TIN

Trang 10


Chương 2 : Các thuật giải sắp xếp và tìm kiếm
CHƯƠNG 2: CÁC THUẬT GIẢI SẮP XẾP VÀ TÌM KIẾM
Mục tiêu: Trình bày được các giải thuật sắp xếp và tìm kiếm. Phân biệt được các thuật
tốn sắp xếp và tìm kiếm. Sinh viên có khả năng cài đặt được các thuật tốn sắp xếp và
tìm kiếm.
1. Một số phương pháp sắp xếp đơn giản
Sắp xếp là quá trình xử lý một danh sách các phần tử (hoặc các mẫu tin) để
đặt chúng theo một thứ tự thỏa mãn một tiêu chuẩn nào đó dựa trên nội dung thơng tin

làm triệt tiêu dần chúng đi
Ý tưởng:
-

Xuất phát từ đầu dãy, tìm tất cả nghịch thế chứa phần tử này, triệt tiêu
chúng bằng cách đổi chỗ phần tử này với phần tử tương ứng trong cặp
nghịch thế

-

Lặp lại xử lý trên với các phần tử tiếp theo trong dãy

c. Ví dụ:
Cho dãy số a :
12

2

8

5

1

KHOA CƠNG NGHỆ THƠNG TIN

6

4



5

1

6

4

15

i= 0, j= 4
0

1

2

3

4

5

6

7

1



1

8

12

5

2

6

4

15

i= 1, j= 3
0

1

2

3

4

5



5

6

7

1

2

12

8

5

6

4

15

i= 2, j= 3
0

1

2


4

5

6

7

i= 2, j= 4
0

1

KHOA CÔNG NGHỆ THÔNG TIN

Trang 12